【文章內(nèi)容簡介】 過比較不同路徑的度量值決定最優(yōu)路徑，而具體的度量值則要 由 所使用的路由算法而定。 2. 數(shù)據(jù)包交換 交換算法相對路由算法來說更加簡單，而且絕大多數(shù)的路由協(xié)議都可以使用相同的交換技術(shù)。當數(shù)據(jù)包的發(fā)送方通過一定的方式獲取到路由器的地址之后，就會把數(shù)據(jù)包以該路由器的物理地址（ MAC 地址）發(fā)送出去，同時使用網(wǎng)絡(luò)層地址標識數(shù)據(jù)包的最終目的地。當路由器接收到數(shù)據(jù)包后 13 將查看標明其目的地的協(xié)議地址，并決定是否按照該地址將數(shù)據(jù)包轉(zhuǎn)發(fā)到下一臺路由器。如果路由器不知道如何把數(shù)據(jù)包轉(zhuǎn) 發(fā)到目的地的話，一般會丟棄該數(shù)據(jù)包。如果路由器知道數(shù)據(jù)包的轉(zhuǎn)發(fā)路徑， 則會將其中的物理地址改為下一臺路由器的地址，然后將其發(fā)送出去。以此類推，直到數(shù)據(jù)包到達最終的目的地。在整個過程中， 數(shù)據(jù)包的物理地址會隨著移動過程中所經(jīng)過的不同的路由器而變化， 但是代表目的地的協(xié)議地址一直保持不變。 路由算法的關(guān)鍵因素 路由算法主要由幾個關(guān)鍵因素決定。 1. 算法的設(shè)計意圖對路由協(xié)議的影響 通常，一種路由算法可以體現(xiàn)出以下幾方面的設(shè)計意圖。 (1)最優(yōu)性是指路由算法選擇最佳路徑的能力，這主要取決于計算最佳路 徑所使用的度量標準。 (2)路由協(xié)議的設(shè)計應(yīng)當盡可能的簡單。即路由算法必須能夠以最有效的方式發(fā)揮其功能，盡可能降低軟件和使用開銷。尤其是當實現(xiàn)路由算法的軟件在資源有限的機器上運行時，有效性就變得更為重要。 (3)路由算法必須具有良好的健壯性， 能夠在出現(xiàn)異?；蛲话l(fā)事件 (例如硬件損壞，負載過高以及執(zhí)行錯誤等 ) 時正常運行。因為路由器往往是網(wǎng)絡(luò)的連接節(jié)點，所以如果出現(xiàn)問題將會帶來非常嚴重的后果。因此，最好的路由算法應(yīng)當能夠經(jīng)受時間的考驗，在不同的網(wǎng)絡(luò)條件下都能夠保持穩(wěn)定的運行狀態(tài)。 (4)路由算法還應(yīng)當能夠快速聚斂。 所謂聚斂就是指所有路由器就最優(yōu)路徑重新達成一致的過程。當因為某種原因使路由器無法繼續(xù)正常使用時，路由器會發(fā)出路由更新信息傳遍整個網(wǎng)絡(luò)，重新計算最優(yōu)路徑，并最終使所有路由器就新路徑達到一致。聚斂速度慢的路由算法可能會導致路由回路的出現(xiàn)。圖 所示的路由回路中，一個數(shù)據(jù)在時間 t1到達路由器１。因為路由器１中的信息已經(jīng)被更新，所以該路由器知道到達數(shù)據(jù)包目的地的最優(yōu)路徑應(yīng)當通過路由器２。因此，路由器１把數(shù)據(jù)包轉(zhuǎn)發(fā)到路由器２。但是路由器２中的信息沒有被更新，所以仍然認為最優(yōu)路徑應(yīng)當通過路由器１，并因此把數(shù)據(jù)包又轉(zhuǎn)發(fā) 回路由器１。這樣，數(shù)據(jù)包只能在兩臺路由器之間來回傳遞，直到路由器２接收到了路由更新信息或者數(shù)據(jù)包超出了最大存活時間。 (5)路由算法還應(yīng)當具有非常好的適應(yīng)性，能夠快速準確的適應(yīng)不同的網(wǎng)絡(luò)環(huán)境 [17]。 圖 回路圖 2. 不同類型的路由算法 每一種算法對網(wǎng)絡(luò)和路由器資源都有不同的要求和影響。路由算法可以劃分成許多不同的類型。Packet to Router X Router1 Router1 Dest: Send to: X R2 Dest: Send to: X R1 路由器 1 路由器 2 14 主要的分類標準如下： (1) 靜態(tài)與動態(tài)。靜態(tài)路由算法很難算得上是算法，只不過是開始路由前由網(wǎng)管建立的表映射。這些映射自身 并不改變，除非網(wǎng)管去改動。使用靜態(tài)路由的算法較容易設(shè)計，在網(wǎng)絡(luò)通信可預測及簡單的網(wǎng)絡(luò)中工作得很好。由于靜態(tài)路由系統(tǒng)不能對網(wǎng)絡(luò)改 變做出反映，通常被認為不適用于現(xiàn)在的大型、易變的網(wǎng)絡(luò)。 20 世紀 90年代主要的路由算法都是動態(tài)路由算法，通過分析收到的路由更新信息來適應(yīng)網(wǎng)絡(luò)環(huán)境的改變。如果信息表示網(wǎng)絡(luò)發(fā)生了變化，路由軟件就重新計算路由并發(fā)出新的路由更新信息。這些信息滲入網(wǎng)絡(luò)，促使路由器重新計算并對路由表做相應(yīng)的改變。動態(tài)路由算法可以在適當?shù)牡胤揭造o態(tài)路由作為補充。例如，最后可選路由 (router of last resort)，作為所有不可路由分組的去路，保證了所有的數(shù)據(jù)至少有方法處理。 (2) 單路徑與多路徑。一些復雜的路由協(xié)議支持到同一目的地多條路徑。與單路算法不同，這些多路徑算法允許數(shù)據(jù)在多條線路上復用。多路徑算法的優(yōu)點很明顯：它們可以提供更好的吞吐量和可靠性。 (3) 平坦與分層：一些路由協(xié)議在平坦的空間里運作，其它則有路由的層次。在平坦的路由系統(tǒng)中，每個路由器與其它所有路由器是對等的；在分層次的路由系統(tǒng)中，一些路由器構(gòu)成了路由主干，數(shù)據(jù)從非主干路由器流向主干路由器，然后在主干上傳輸直到它們到達目標所在區(qū)域，在 這里，它們從最后的主干路由器通過一個或多個非主干路由器到達終點。 (4) 主機智能與路由器智能。一些路由算法假定源結(jié)點來決定整個路徑，這通常稱為源路由。在源路由系統(tǒng)中，路由器只作為存貯轉(zhuǎn)發(fā)設(shè)備，無意識地把分組發(fā)向下一跳。其它路由算法假定主機對路徑一無所知，在這些算法中，路由器基于自己的計算決定通過網(wǎng)絡(luò)的路徑。前一種系統(tǒng)中，主機具有決定路由的智能，后者則為路由器具有此能力。主機智能和路由器智能的折衷實際是最佳路由與額外開銷的平衡。主機智能系統(tǒng)通常能選擇更佳的路徑，因為它們在發(fā)送數(shù)據(jù)前探索了所有可能的路徑，然后 基于特定系統(tǒng)對“優(yōu)化”的定義來選擇最佳路徑。然而確定所有路徑的行為通常需要很多的探索通信量和很長的時間。 (5) 域內(nèi)與域間。一些路由算法只在域內(nèi)工作，其它的則既在域內(nèi)也在域間工作。這兩種算法的本質(zhì)是不同的。其遵循的理由是優(yōu)化的域內(nèi)路由算法沒有必要也成為優(yōu)化的域間路由算法。 (6) 鏈接狀態(tài)與距離向量。鏈接狀態(tài)算法把路由信息散布到網(wǎng)絡(luò)的每個節(jié)點，不過每個路由器只發(fā)送路由表中描述其自己鏈接狀態(tài)的部分。距離向量算法中每個路由器發(fā)送路由表的全部或部分，但只發(fā)給其鄰居。也就是說，鏈接狀態(tài)算法到處發(fā)送較少的更新信息， 而距離向量算法只向相鄰的路由器發(fā)送較多的更新信息。由于鏈接狀態(tài)算法聚合得較快，它們相對于距離算法產(chǎn)生路由環(huán)的傾向較小。在另一方面，鏈接狀態(tài)算法需要更多 CPU 和內(nèi)存資源，因此鏈接狀態(tài)算法的實現(xiàn)和支持較昂貴。雖然有差異，這兩種算法類型在多數(shù)環(huán)境中都可以工作得很好最后，路由算法使用不同的度量標準(metric)，從而使最優(yōu)路徑的計算結(jié)果不同。 3. 路由算法使用了許多不同的 metric 以確定最佳路徑 復雜的路由算法可以基于多個 metric 選擇路由，并把它們結(jié)合成一個復合的 metric。常用的 metric如下： (1) 路徑長度是最常用的路由 metric。一些路由協(xié)議允許網(wǎng)管給每個網(wǎng)絡(luò)鏈接人工賦以代價值， 15 這種情況下，路由長度是所經(jīng)過各個鏈接的代價總和。其它路由協(xié)議定義了跳數(shù)，即分組在從源到目的地路途中必須經(jīng)過的網(wǎng)絡(luò)產(chǎn)品，如路由器的個數(shù)。 (2) 可靠性，在路由算法中指網(wǎng)絡(luò)鏈接的可依賴性 (通常以位誤率描述 )，有些網(wǎng)絡(luò)鏈接可能比其它的失效更多，網(wǎng)路失效后，一些網(wǎng)絡(luò)鏈接可能比其它的更易或更快修復。任何可靠性因素都可以在給可靠率賦值的計算在內(nèi)，通常是由風管給網(wǎng)絡(luò)鏈接賦以 metric 值。 (3) 路由延遲指分組從源通過網(wǎng)絡(luò)到達 目的所花時間。很多因素影響到延遲，包括中間的網(wǎng)絡(luò)鏈接的帶寬、經(jīng)過的每個路由器的端口隊列、所有中間網(wǎng)絡(luò)鏈接的擁塞程度以及物理距離。因為延遲是多個重要變量的混合體，它是個比較常用且有效的 metric。 (4) 帶寬指鏈接可用的流通容量。在其它所有條件都相等時， 10Mbps的以太網(wǎng)鏈接比 64Kbps 的專線更可取。雖然帶寬是鏈接可獲得的最大吞吐量，但是通過具有較大帶寬的鏈接做路由不一定比經(jīng)過較慢鏈接路由更好。例如，如果一條快速鏈路很忙，分組到達目的地所花時間可能要更長。 (5) 負載指網(wǎng)絡(luò)資源，如路由器的繁忙程度。 負載可以用很多方面計算，包括 CPU 使用情況和每秒處理分組數(shù)。持續(xù)地監(jiān)視這些參數(shù)本身也是很耗費資源的。通信代價是另一種重要的 metric，尤其是有一些公司可能關(guān)心運作費用甚于性能。即使線路延遲可能較長，他們也寧愿通過自己的線路發(fā)送數(shù)據(jù)而不采用昂貴的公用線路。 4. 路由原理 當 IP 子網(wǎng)中的一臺主機發(fā)送 IP 分組給同一 IP 子網(wǎng)的另一臺主機時，它將直接把 IP 分組送到網(wǎng)絡(luò)上，對方就能收到。而要送給不同 IP 于網(wǎng)上的主機時，它要選擇一個能到達目的子網(wǎng)上的路由器，把 IP 分組送給該路由器，由路由器負責把 IP 分組送到目的地。如 果沒有找到這樣的路由器，主機就把 IP 分組送給一個稱為“缺省網(wǎng)關(guān) (default gateway)”的路由器上?！叭笔【W(wǎng)關(guān)”是每臺主機上的一個配置參數(shù)，它是接在同一網(wǎng)絡(luò)上的某個路由器端口的 IP 地址。 路由器轉(zhuǎn)發(fā) IP 分組時，只根據(jù) IP 分組目的 IP 地址的網(wǎng)絡(luò)號部分，選擇合適的端口，把 IP 分組送出去。同主機一樣，路由器也要判定端口所接的是否目的子網(wǎng)，如果是，就直接把分組通過端口送到網(wǎng)絡(luò)上，否則，也要選擇下一個路由器來傳送分組。路由器也有它的缺省網(wǎng)關(guān)，用來傳送不知道往哪兒送的 IP 分組。這樣，通過路由器把知道如何傳送的 IP 分組正確轉(zhuǎn)發(fā)出去，不知道的 IP 分組送給“缺省網(wǎng)關(guān)”路由器，這樣一級級地傳送， IP 分組最終將送到目的地，送不到目的地 IP 分組則被網(wǎng)絡(luò)丟棄了。 目前 TCP/IP 網(wǎng)絡(luò)，全部是通過路由器互連起來的， Inter 就是成千上萬個 IP 子網(wǎng)通過路由器互連起國際性網(wǎng)絡(luò)。這種網(wǎng)絡(luò)稱為以路由器為基礎(chǔ)的網(wǎng)絡(luò) (router based work)，形成了以路由器為節(jié)點的“網(wǎng)間網(wǎng)”。在“網(wǎng)間網(wǎng)”中，路由器不僅負責對 IP 分組的轉(zhuǎn)發(fā)，還要負責與別的路由器進行聯(lián)絡(luò)，共同確定“網(wǎng)間網(wǎng)”的路由選擇和維護路由表。 路由動作包括兩項基 本內(nèi)容：尋徑和轉(zhuǎn)發(fā)。尋徑即判定到達目的地的最佳路徑，由路由選擇算法來實現(xiàn)。由于涉及到不同的路由選擇協(xié)議和路由選擇算法，要相對復雜一些。為了判定最佳路徑，路由選擇算法必須啟動并維護包含路由信息的路由表，其中路由信息依賴于所用的路由選擇算法而不盡相同。路由選擇算法將收集到的不同信息填入路由表中，根據(jù)路由表可將目的網(wǎng)絡(luò)與下一站 (nexthop)的關(guān)系告訴路由器。路由器間互通信息進行路由更新，更新維護路由表使之正確反映網(wǎng)絡(luò)的拓撲變化， 16 并由路由器根據(jù)量度來決定最佳路徑。這就是路由選擇協(xié)議 (routing protocol)，例如路由信息協(xié)議 (RIP)、開放式最短路徑優(yōu)先協(xié)議 (OSPF)和邊界網(wǎng)關(guān)協(xié)議 (BGP)等。 轉(zhuǎn)發(fā)即沿尋徑好的最佳路徑傳送信息分組。路由器首先在路由表中查找，判明是否知道如何將分組發(fā)送到下一個站點 (路由器或主機 )，如果路由器不知道如何發(fā)送分組，通常將該分組丟棄；否則就根據(jù)路由表的相應(yīng)表項將分組發(fā)送到下一個站點，如果目的網(wǎng)絡(luò)直接與路由器相連，路由器就把分組直接送到相應(yīng)的端口上。這就是路由轉(zhuǎn)發(fā)協(xié)議 (Routed Protocol)。 路由轉(zhuǎn)發(fā)協(xié)議和路由選擇協(xié)議是相互配合又相互獨立的概念，前者使用后者維護 的路由表，同時后者要利用前者提供的功能來發(fā)布路由協(xié)議數(shù)據(jù)分組。本文中提到的路由協(xié)議，除非特別說明，都是指路由選擇協(xié)議，這也是普遍的習慣。 5. 路由算法的設(shè)計原則 各種路由算法不盡相同，主要是由于：首先，算法設(shè)計者的設(shè)計目標會影響路由選擇協(xié)議的運行結(jié)果；其次，現(xiàn)有的各種路由選擇算法對網(wǎng)絡(luò)和路由器資源的影響不同；最后，不同的計量標準也會影響最佳路徑的計算結(jié)果。 路由選擇算法設(shè)計目標主要包括正確性、簡單性、健壯性、穩(wěn)定性、公平性和最優(yōu)性。 （ 1）最優(yōu)性 最優(yōu)性指路由選擇算法選擇最優(yōu)路徑的能力，最優(yōu)路徑取決于計 量標準和用于計量的權(quán)值。 （ 2）簡易性和低開銷 所謂簡易性和低開銷指必須用最少的軟件和最低的開銷來提供最有效的功能。 （ 3）強壯性和穩(wěn)定性 強壯性和穩(wěn)定性意味著路由選擇協(xié)議必須在出現(xiàn)異常情況或突發(fā)事件時（如硬件故障，高負載狀態(tài)和不正確操作）也能正常運行。穩(wěn)定性則要求其能運行于各種不同的網(wǎng)絡(luò)環(huán)境中，并且有良好容錯性。 （ 4）快速收斂性 所謂收斂是指所有路由器在最佳路徑上取得一致的過程。當路由器發(fā)送修正路由消息，該消息在網(wǎng)絡(luò)上傳播，引發(fā)路由器重新計算最優(yōu)路由，并最終促使所有路由器承認新的最優(yōu)路由，這就是路 由收斂的過程。如果路由選擇算法收斂過慢，會導致路由循環(huán)或網(wǎng)絡(luò)發(fā)生故障。 （ 5）靈活性 靈活性要求路由選擇算法能迅速準確地適應(yīng)網(wǎng)絡(luò)環(huán)境（如網(wǎng)絡(luò)帶寬、路由器隊列大小、網(wǎng)絡(luò)延遲）的變化。 距離向量路由和鏈路狀態(tài)路由 距離向量（ distance vector ）路由選擇算法要求每個路由器將路由選擇表的全部或部分傳送到與其向鄰的路由器中。而鏈路狀態(tài)（ link state）路由選擇算法將路由選擇信息發(fā)送至互連網(wǎng)絡(luò)的所有節(jié)點上，每個路由器只能傳遞描述其自身鏈接狀態(tài)的那部分路由選擇表。實際上，鏈路狀態(tài)路由選 擇算法只傳送小部分的更新信息，而距離向量路由選擇算法將大部分或全部的更新信息傳送到與其向鄰的路由器中。 由于鏈路狀態(tài)路由選擇算法收斂速度較快，因此，它比距離向量路由選擇算法更易避免路由循環(huán)。但因鏈接狀態(tài)路由選擇算法需要占用更多的 CPU 和內(nèi)存資源，故比距離向量路由選擇算法難以支持 17 和實現(xiàn)。 距離 向量路由 1. 距離 向量路由算法 距離 向量路由算法是一種動態(tài)路由算法，是基于 BellmanFord 的數(shù)字研究結(jié)果，因此有時也將該算法稱為 BellmanFord 算法。他們證明了只要網(wǎng)絡(luò)的拓撲結(jié)構(gòu)保 持穩(wěn)定，該算法將保證網(wǎng)絡(luò)收斂到一個可知的拓撲結(jié)構(gòu)。該算法要求路由器之間周期地交換路由更新信息，路由更新信息中包含一個目的路由器的向量表，各表項中包含通告各路由器