【文章內(nèi)容簡介】 健壯性：能夠適應網(wǎng)絡的拓撲變化 （ 如節(jié)點損壞 、 增加或退出等 ） 和流量變化； ⑷ 穩(wěn)定性：算法可靠 ， 對網(wǎng)絡變化既不能因為反應太快產(chǎn)生振蕩 ， 也不因反應遲緩而使網(wǎng)絡長時間不能趨于穩(wěn)定 ， 即算法應在網(wǎng)絡變化趨于穩(wěn)定時迅速收斂于一個確定的解； ⑸ 公平性：算法對所有節(jié)點公平； ⑹ 最優(yōu)性 。 1． 靜態(tài)路由選擇算法 ⑴ 擴散式 路徑上的各節(jié)點對收到的分組進行復制 ， 并向相鄰節(jié)點轉(zhuǎn)發(fā) ， 直至到達目標節(jié)點 ， 如圖 37所示 。 擴散式又稱全路發(fā)送選擇算法 ， 其優(yōu)點是算法簡單 、成功率高 、 支持多目或廣播傳輸 、 能夠適應網(wǎng)絡的動態(tài)變化缺點是線路利用率低 、 吞吐量小 、 容易引起 “ 廣播風暴 ” ， 甚至造成系統(tǒng)癱瘓 ， 故又稱洪泛式 。 為了避免分組在轉(zhuǎn)發(fā)過程中的無限膨脹，常使用選擇擴散式和計數(shù)法加以控制。其中選擇擴散式是指僅選擇那些最接近信宿的鄰接節(jié)點進行轉(zhuǎn)發(fā)的算法。而計數(shù)法則是在每一個分組中增加一個計數(shù)字段，其初值設定為信源到信宿的最大路徑長度（即路徑上最多的轉(zhuǎn)發(fā)節(jié)點數(shù)），分組在轉(zhuǎn)發(fā)過程中，每轉(zhuǎn)發(fā)一次，計數(shù)減 1。若計數(shù)為 0的分組仍未到達目標節(jié)點，則自動丟棄該分組。 信源 信宿 圖 37 ⑵ 隨機式 由收到分組的節(jié)點隨機地選擇一個相鄰節(jié)點轉(zhuǎn)發(fā)出去 。 ⑶ 固定式單路路由算法 每個節(jié)點事先都裝有一張人工計算得到的路由表，表中給出該節(jié)點到其它所有目標節(jié)點的轉(zhuǎn)發(fā)出口（即鄰接轉(zhuǎn)發(fā)節(jié)點）的對應關(guān)系。節(jié)點在收到分組后，通過查找路由表決定轉(zhuǎn)發(fā)節(jié)點并將分組發(fā)送出去，直至到達目標節(jié)點。這種方法的健壯性較差。如圖 38所示。 A B C D E F 3 3 4 4 4 2 4 6 6 圖 38(b) 全路由表 圖 38(a) 通信子網(wǎng) — （ 4， F） （ 4， F） （ 8， D） （ 6， A） （ 4， F） F （ 4， E） — （ 3， E） （ 7， D） （ 6， E） （ 8， F） E （ 4， D） （ 3， D） — （ 4， D） （ 7， C） （ 8， F） D （ 8， D） （ 7， D） （ 4， C） — （ 3， C） （ 5， B） C （ 6， A） （ 6， B） （ 7， C） （ 3， B） — （ 2， B） B （ 4， A） （ 8， F） （ 8， F） （ 5， B） （ 2， A） — A 宿 A B C D E F 源 ⑷ 固定式多路路由算法 在單路由算法的基礎上 ， 增加多個出口選擇 ， 分別對應最佳 、 次佳 、 再次等多種選擇方案 ， 并分別以一個優(yōu)先權(quán)數(shù)表示 。 如對于 圖 38（ a） 所示的通信子網(wǎng) ， 節(jié)點 A的多路路由表可以構(gòu)造如圖 39。 （ 14， C） （ 12， B） （ 4， F） F （ 13， C） （ 8， B） （ 8， F） E （ 10， C） （ 9， B） （ 8， F） D （ 12， F） （ 6， C） （ 5， B） C （ 14， F） （ 9， C） （ 2， B） B 優(yōu)先權(quán) 轉(zhuǎn)發(fā)出口 優(yōu)先權(quán) 轉(zhuǎn)發(fā)出口 優(yōu)先權(quán) 轉(zhuǎn)發(fā)出口 第三選擇 第二選擇 第一選擇 信宿 圖 39 節(jié)點 A的多路路由表 ⑸ 孤立式路由選擇算法 孤立式算法是指節(jié)點在作路由選擇時 ， 不與其它節(jié)點交換信息 ，僅依據(jù)自身掌握的網(wǎng)絡信息對分組的輸出端口作出選擇 。 顯然 ， 孤立式算法具有最小的信息交換量 ， 信道的有效傳輸率較高 ， 算法簡單 ， 軟件開銷小 。 常見的算法主要有： ⅰ) 熱土豆法 (Hot potato)： 節(jié)點在收到分組后，立即將其置于最短的輸出隊列中，而不論去向，以期盡快出手。這種方法具有 最短的 輸出等待時間，但所選擇的未必是最佳路徑。 ⅱ ) 自學習法（ Backward Learning）： 在分組的報頭部分增加源節(jié)點地址和計數(shù)字段。分組從信源節(jié)點出發(fā)后，每轉(zhuǎn)發(fā)一次，計數(shù)便加 1，由此可知源點到達本站點的傳輸路徑長度，以此為依據(jù)與原路由表進行比較，以最小者更新路由表，達到學習的目的。這種方法不能適應網(wǎng)絡的動態(tài)變化，通常采用定期（如 30秒鐘）恢復原始路由表的方法來解決。 2． 動態(tài)路由選擇算法 ⑴ 最短通路路由選擇算法 所謂最短通路是指從信源機到信宿機之間的一條具有最小傳輸代價的傳輸路徑 。 為此需對網(wǎng)絡中各段鏈路的傳輸代價進行測量和標注 ，作為該段鏈路的權(quán) 。 狄克斯特拉 （ Dijkstra） 于 1959年提出了從一個頂點到其余所有頂點的最短路徑的計算方法 ， 其思想簡述為： 按照路徑長度遞增的順序依次求出從源點 v到其余每一個頂點的最短通路及其長度 。 首先求出 v到每一個相鄰節(jié)點的路徑長度并從中選出最小者 vi ， 以 vi作為新增的中間節(jié)點；修改所有與 vi相鄰的節(jié)點的路徑長度 ， 即求出從 v出發(fā)經(jīng) vi到達的所有節(jié)點的路徑長度 ， 再從中選取最小者 ， 將其加入中間節(jié)點 ， 以此類推 ， 直至 v到所有節(jié)點的路徑長度均被求出 ， 算法結(jié)束 。 例：從頂點 A出發(fā)到其它頂點的最短路徑 A B E G F C D H 信源 2 2 2 2 2 7 3 3 6 1 4 A B E G F C D H （ 2,A） （ 6,A） （ ∞,） （ ∞,） （ ∞,） （ ∞,） （ ∞,） A B E G F C D H （ 2,A） （ 6,A） （ 9,B） （ 4,B） （ ∞,） （ ∞,） （ ∞,） A B E G F C D H （ 2,A） （ 5,E） （ 9,B） （ 4,B） （ 6,E） （ ∞,） （ ∞,） （ 2,A） A B E G F C D H （ 5,E） （ 9,B） （ 4,B） （ 6,E） （ ∞,） （ 9,G） A B E G F C D H （ 2,A） （ 5,E） （ 9,B） （ 4,B） （ 6,E） （ ∞,） （ 8,F） A B E G F C D H （ 2,A） （ 5,E） （ 9,B） （ 4,B） （ 6,E） （ 10,H） （ 8,F） 從 A到 D的最短通路為： D→H→F→E→B→A ⑵ 集中式路由選擇算法 在網(wǎng)絡中設置一個路由控制中心 RCC(Routing Control Center),通過定期向各節(jié)點采集網(wǎng)絡狀態(tài)信息 ， 并按照某種策略為各節(jié)點計算出一張最佳路由表 ， 然后發(fā)送到各個節(jié)點 ， 更新原路由表 。 這種方法的優(yōu)點是： RCC可以及時地動態(tài)掌握網(wǎng)絡的全局信息 ，集中調(diào)度 ， 具有較強的適應性 。 缺點是對 RCC性能要求較高 ， 靠近RCC的線路上通信量過于集中 ， 可能對網(wǎng)絡 性能產(chǎn)生影響；此外 ， 各節(jié)點收到新路由表的時間不同 ， 更新期間分組的延遲更大 ， 甚至造成分組丟失或網(wǎng)絡阻塞 。 ⑶ 分布式路由選擇算法 網(wǎng)絡中的每個節(jié)點定期（如 30秒鐘）或不定期地與相鄰的所有節(jié)點交換路由信息，從中選取到各節(jié)點的最佳路徑并更新路由表。這種方法能夠適應網(wǎng)絡的拓撲及流量變化，具有較強的健壯性，但大量的信息交換需占用一定的信道資源，故它主要用于一些規(guī)模不太大的網(wǎng)絡。 流量控制與擁塞控制 擁塞是指到達通信子網(wǎng)某一部分的分組數(shù)量過多 ， 致使該部分網(wǎng)絡來不及處理 ， 引起網(wǎng)絡部分或整體性能下降的現(xiàn)象 。常見的如路由器緩沖區(qū)過小 、 CPU處理速度過慢 、 出口帶寬太小等都可能引起網(wǎng)絡阻塞 。 防止和解決擁塞的有效方法是流量控制和擁塞控制 。 1． 流量控制 ⑴ 停 — 等方式：通過調(diào)整發(fā)送窗口和接收窗口的尺寸可以對信道上的傳輸流量進行控制 。 ⑵ 緩沖區(qū)預約方式：對于面向連接的服務，當信宿節(jié)點忙碌時，整個虛電路起到了數(shù)據(jù)緩沖的作用，直至虛電路被拆除；在無連接服務方式中，源主機在發(fā)送數(shù)據(jù)前需要事先向目標主機預約緩沖區(qū)，在收到目的端的肯定應答后再發(fā)送數(shù)據(jù)。傳輸過程中，若信宿端來不及處理，則各分組將暫存在不同的節(jié)點中，整個網(wǎng)絡都起到數(shù)據(jù)緩沖的作用。 在 ISO/OSI通信子網(wǎng)的多個協(xié)議層中都提供流量控制功能 ， 不同協(xié)議層次根據(jù)服務要求實現(xiàn)不同的流量控制功能：網(wǎng)關(guān)間的數(shù)據(jù)流量通過傳輸層協(xié)議控制；自治系統(tǒng)內(nèi)部源節(jié)點至目標節(jié)點間的流量由網(wǎng)絡層協(xié)議控制；相鄰節(jié)點間的信息流量由數(shù)據(jù)鏈路層協(xié)議控制；而信關(guān)與源節(jié)點間則通過數(shù)據(jù)鏈路層協(xié)議 （ 直接相連 ） 或網(wǎng)絡層協(xié)議 （ 間接相連 ） 進行控制 ， 如圖 310所示 。 圖 310 源節(jié)點與目標節(jié)點間由 N協(xié)議控制 信關(guān) 信宿節(jié)點 相鄰節(jié)點間 由DL協(xié)議控制 信關(guān)與源節(jié)點間由 DL/N協(xié)議控制 多個自治系統(tǒng)間由 T協(xié)議控制 信源節(jié)點 中間節(jié)點 信關(guān) 中間節(jié)點 2. 擁塞控制 ⑴ 分組丟棄法： 對于無連接服務 ， 當網(wǎng)絡線路較忙時 ，子網(wǎng)自動丟棄發(fā)來的包 ， 以減少發(fā)往該方向的數(shù)據(jù)分組數(shù)量 ，被丟棄的分組由于發(fā)送端不能獲得確認而超時重發(fā) ， 因而不會產(chǎn)生信息丟失 ， 但會增加延遲；而對于面向連接的服務 ， 則被丟棄的分組將被保留在鏈路的某處 ， 待擁塞消除后重發(fā) 。 ⑵ 定額控制法： 通過計算子網(wǎng)的通信能力，發(fā)行適量的“ 許可證 ” 分組。 “ 許可證 ” 是一種特殊的控制分組，它們隨機地在網(wǎng)絡中巡航流動，任何節(jié)點必須在獲得 “ 許可證 ” 后方可發(fā)送數(shù)據(jù)。這種方法可能因為等待 “ 許可證 ” 而產(chǎn)生新的延遲，稱為網(wǎng)絡的 進場延遲 （ Admission Delay）， 此外還會部分降低子網(wǎng)的帶寬利用率。 ⑶ 阻塞分組法： 節(jié)點在轉(zhuǎn)發(fā)一個新收到的分組前 ， 先檢查輸出線路是否處于 “ 告警 ” 狀態(tài) ， 是則向源端發(fā)送一個阻塞分組 （ 也稱抑制