選路

選路

選路是一個通用的術語,用來描述某一個網路中的主機發出的分組經過若干路由器到達另一個網路中的目的主機的過程。更明確地說,選路過程是由兩個獨立的過程組成。

原理


從概念上講,IP路由選擇是比較簡單的,舉個例子,如果目的主機和源主機都在同一個子網,那麼IP分組直接送到目的主機上。否則,源主機就把IP分組發到一個默認的路由器上,再由這個路由器進行轉發。一般情況下,一台計算機既可以配置成主機,又可以配置成路由器。在它的P層維護一張路由表,當收到一個IP分組並進行發送時,它都要對路由表搜索一次。當分組來自某個網路介面時,首先檢查目的IP地址是否是本機IP地址或廣播地址,如果是,IP分組就會送到由IP首部協議欄位所指定的協議模塊進行處理。如果不是這些地址,那麼如果IP層被設置為路由器的功能,就會轉發這個分組,否則就丟棄這個IP分組。

過程


就是把分組從一個網路傳遞到另一個分組的實際過程。分組轉發的過程採用了hop-by-hop的方式,路由器將分組轉發到哪裡是由路由器自身路由轉發表的內容和分組的目的地址決定的。
路由器(或主機)在進行分組轉發時可分為直接轉發和間接轉發兩種形式。
(1)直接轉發。當轉發節點(主機或路由器)與目的節點位於同一個物理網路中時,就採用直接轉發的形式。直接轉發不需要經過其他路由器,IP分組封裝在物理幀中,直接傳送到目的節點。在路由器中,測試目的結點是否位於同一網路中的方法是,檢查目的節點IP地址中的網路號是否與本節點的網路號相同。
(2)間接轉發。當路由器與目的結點不在同一個網路中時,無法直接轉發,需採用間接轉發方式。間接轉發的過程是先通過路由選擇功能選定某台下一跳路由器,並把分組封裝到物理幀中,發送到這台下一跳路由器上,由下一跳路由器進行進一步轉發。
2、路由資料庫的管理
①各路由器都維護一個網路拓撲資料庫,在路由器中,路由資料庫是計算路由轉發表的基礎。
②對路由資料庫的維護主要包括資料庫的更新和修改等,以動態地反映網路拓撲的變動和修改。
③對路由資料庫的維護時通過各路由器之間的不斷地交換路由更新消息來進行的。
④用於在路由器之間進行路由信息交換的具體方式都是由一組動態路由協議宋定義的。維護路由資料庫的完整性、準確性,並正確建立路由轉發表所採用的處理過程、演演算法和協議等都屬於選路的範疇。

選路演演算法


距離向量選路演演算法

距離向量選路演演算法是Internet選路中的一個經典演演算法,通常也被稱為“向量一距離’’演演算法、Bellman—Ford、Ford—Fulkerson或Bellman演演算法。距離向量演演算法的思想非常簡單,即每一個路由器都可以把它所了解路由信息通知給與其相鄰路由器。路由器發布的路由信息是以距離向量的形式提供的。所謂距離向量是一個形如{network,cost}的二元組。每一個距離向量用於說明路由器到達某一個目的網路的費用。其中network表示目的網路,cost是一個相對值,它反映了在發布向量的路由器與目的網路之間轉發費用。費用可以採用不同的度量(metric),通常可使用轉發距離(hop數)。

鏈路狀態選路

從前面的分析中可見,距離向量演演算法最主要的缺點是在大型網路中性能不佳:匯聚速度比較慢,並且該演演算法進行路由交換的信息量比較大。這是因為距離向量協議要求每個路由器都必須參與操作,且各路由器發布的距離向量的數量與網際網路中的網路數量成正比,造成交換的總信息十分龐大。對距離向量演演算法的改進導致了另一類演演算法,即鏈路狀態(Link State)演演算法。鏈路狀態演演算法以圖論作為理論基礎,用圖來表示網路拓撲結構,並在利用圖論中的最短路徑演演算法來計算網路間的最佳路由,因此鏈路狀態演演算法又被稱為最短路經優先演演算法(SPF)。