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