[科普中國]-選路

原理

從概念上講，IP路由選擇是比較簡(jiǎn)單的，舉個(gè)例子，如果目的主機(jī)和源主機(jī)都在同一個(gè)子網(wǎng)，那么IP分組直接送到目的主機(jī)上。否則，源主機(jī)就把IP分組發(fā)到一個(gè)默認(rèn)的路由器上，再由這個(gè)路由器進(jìn)行轉(zhuǎn)發(fā)。一般情況下，一臺(tái)計(jì)算機(jī)既可以配置成主機(jī)，又可以配置成路由器。在它的P層維護(hù)一張路由表，當(dāng)收到一個(gè)IP分組并進(jìn)行發(fā)送時(shí)，它都要對(duì)路由表搜索一次。當(dāng)分組來自某個(gè)網(wǎng)絡(luò)接口時(shí)，首先檢查目的IP地址是否是本機(jī)IP地址或廣播地址，如果是，IP分組就會(huì)送到由IP首部協(xié)議字段所指定的協(xié)議模塊進(jìn)行處理。如果不是這些地址，那么如果IP層被設(shè)置為路由器的功能，就會(huì)轉(zhuǎn)發(fā)這個(gè)分組，否則就丟棄這個(gè)IP分組。2

過程1、分組轉(zhuǎn)發(fā)

就是把分組從一個(gè)網(wǎng)絡(luò)傳遞到另一個(gè)分組的實(shí)際過程。分組轉(zhuǎn)發(fā)的過程采用了hop-by-hop的方式，路由器將分組轉(zhuǎn)發(fā)到哪里是由路由器自身路由轉(zhuǎn)發(fā)表的內(nèi)容和分組的目的地址決定的。

路由器(或主機(jī))在進(jìn)行分組轉(zhuǎn)發(fā)時(shí)可分為直接轉(zhuǎn)發(fā)和間接轉(zhuǎn)發(fā)兩種形式。

(1)直接轉(zhuǎn)發(fā)。當(dāng)轉(zhuǎn)發(fā)節(jié)點(diǎn)(主機(jī)或路由器)與目的節(jié)點(diǎn)位于同一個(gè)物理網(wǎng)絡(luò)中時(shí)，就采用直接轉(zhuǎn)發(fā)的形式。直接轉(zhuǎn)發(fā)不需要經(jīng)過其他路由器，IP分組封裝在物理幀中，直接傳送到目的節(jié)點(diǎn)。在路由器中，測(cè)試目的結(jié)點(diǎn)是否位于同一網(wǎng)絡(luò)中的方法是，檢查目的節(jié)點(diǎn)IP地址中的網(wǎng)絡(luò)號(hào)是否與本節(jié)點(diǎn)的網(wǎng)絡(luò)號(hào)相同。

(2)間接轉(zhuǎn)發(fā)。當(dāng)路由器與目的結(jié)點(diǎn)不在同一個(gè)網(wǎng)絡(luò)中時(shí)，無法直接轉(zhuǎn)發(fā)，需采用間接轉(zhuǎn)發(fā)方式。間接轉(zhuǎn)發(fā)的過程是先通過路由選擇功能選定某臺(tái)下一跳路由器，并把分組封裝到物理幀中，發(fā)送到這臺(tái)下一跳路由器上，由下一跳路由器進(jìn)行進(jìn)一步轉(zhuǎn)發(fā)。1

2、路由數(shù)據(jù)庫的管理

①各路由器都維護(hù)一個(gè)網(wǎng)絡(luò)拓?fù)鋽?shù)據(jù)庫，在路由器中，路由數(shù)據(jù)庫是計(jì)算路由轉(zhuǎn)發(fā)表的基礎(chǔ)。

②對(duì)路由數(shù)據(jù)庫的維護(hù)主要包括數(shù)據(jù)庫的更新和修改等，以動(dòng)態(tài)地反映網(wǎng)絡(luò)拓?fù)涞淖儎?dòng)和修改。

③對(duì)路由數(shù)據(jù)庫的維護(hù)時(shí)通過各路由器之間的不斷地交換路由更新消息來進(jìn)行的。

④用于在路由器之間進(jìn)行路由信息交換的具體方式都是由一組動(dòng)態(tài)路由協(xié)議宋定義的。維護(hù)路由數(shù)據(jù)庫的完整性、準(zhǔn)確性，并正確建立路由轉(zhuǎn)發(fā)表所采用的處理過程、算法和協(xié)議等都屬于選路的范疇。1

選路算法距離向量選路算法距離向量選路算法是Internet選路中的一個(gè)經(jīng)典算法，通常也被稱為“向量一距離’’算法、Bellman—Ford、Ford—Fulkerson或Bellman算法。距離向量算法的思想非常簡(jiǎn)單，即每一個(gè)路由器都可以把它所了解路由信息通知給與其相鄰路由器。路由器發(fā)布的路由信息是以距離向量的形式提供的。所謂距離向量是一個(gè)形如{network，cost}的二元組。每一個(gè)距離向量用于說明路由器到達(dá)某一個(gè)目的網(wǎng)絡(luò)的費(fèi)用。其中network表示目的網(wǎng)絡(luò)，cost是一個(gè)相對(duì)值，它反映了在發(fā)布向量的路由器與目的網(wǎng)絡(luò)之間轉(zhuǎn)發(fā)費(fèi)用。費(fèi)用可以采用不同的度量(metric)，通?？墒褂棉D(zhuǎn)發(fā)距離(hop數(shù))。

鏈路狀態(tài)選路從前面的分析中可見，距離向量算法最主要的缺點(diǎn)是在大型網(wǎng)絡(luò)中性能不佳：匯聚速度比較慢，并且該算法進(jìn)行路由交換的信息量比較大。這是因?yàn)榫嚯x向量協(xié)議要求每個(gè)路由器都必須參與操作，且各路由器發(fā)布的距離向量的數(shù)量與互聯(lián)網(wǎng)中的網(wǎng)絡(luò)數(shù)量成正比，造成交換的總信息十分龐大。對(duì)距離向量算法的改進(jìn)導(dǎo)致了另一類算法，即鏈路狀態(tài)(Link State)算法。鏈路狀態(tài)算法以圖論作為理論基礎(chǔ)，用圖來表示網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，并在利用圖論中的最短路徑算法來計(jì)算網(wǎng)絡(luò)間的最佳路由，因此鏈路狀態(tài)算法又被稱為最短路經(jīng)優(yōu)先算法(SPF)。3