計算機網絡--iso體系結構分析(ppt62頁)(編輯修改稿)

　

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