[計算機硬件及網絡]第5章分組交換-資料下載頁

　　

【正文】 消息反應迅速 ， 但對壞消息卻反應遲鈍 。 在一個最長路徑為 N跳的子網中 ， 最多經過 N次路由信息的交換 ， 所有結點都會知道新增的鏈路和結點 。而對于壞消息 ， 所有結點慢慢地增加其距離值 ， 直至無窮大時 ，才發現網絡拓撲發生了變化 。 這就是所謂的 “ 無窮計算問題 ” 。 水平分裂算法 水平分裂 (split horizon)算法 是多種解決無窮計算問題的方法之一 。 水平分裂算法與距離向量算法工作過程一樣 ， 不同之處僅在于：任意結點到結點 X的距離如果是從結點 Y發送的路由信息中獲得的 ， 那么該結點不向 Y報告其到 x的真實距離 (報告的距離值為無窮大 )。 使用水平分裂法 ， 壞消息以每交換一次路由信息傳播一個結點的速度傳播 ， 這比不用水平分裂方法要好得多 。 糟糕的是水平分裂法也有失敗的時候 。 交 換 技 術第 5 章分 組 交 換70 距離向量路由算法存在很大的缺陷 ， 很快被一種全新的 鏈路狀態路由 （ link state routing） 算法所替代 。 鏈路狀態路由算法的思想十分簡單 ， 可以分 五部分加以描述 。 每個路由器必須： 1） 發現它的鄰居結點 ， 并獲取其網絡地址； 2） 測量到各鄰居結點的時延 （ 或代價 ） ； 3） 組裝一個分組通告它剛知道的路由信息； 4） 將這個分組發送給所有其它網絡結點； 5） 計算到所有其它結點的最短路徑 。 事實上 ， 完整的拓撲結構和所有的鏈路時延都通過試驗測量并發布到網絡中每一個結點 。 各個結點可以用Dijkstra算法來找出它到所有其它結點的最短路徑 。 （ 2）鏈路狀態路由算法 交 換 技 術第 5 章分 組 交 換71 當一個結點被激活以后 ， 它的第一個任務就是要知道誰是它的 鄰居 ， 這是通過向每條點到點鏈路發送特殊的 Hello分組來實現的 。 在另一端的結點應發回一個應答分組 ， 以說明它是誰 。 所有網絡結點的名字必須是全局唯一的 。 當兩個或多個結點通過一個局域網 (LAN)連接時 ， 引入一個新的虛擬結點 N代表 LAN(如下圖 )。 1）發現鄰居結點 ABCDEFGHIL A N路 由 器CDEABNFGHI交 換 技 術第 5 章分 組 交 換72 2） 測量鏈路時延或代價 鏈路狀態路由算法需要每個結點知道它到鄰居結點的時延或代價 。 取得時延值的最直接方法就是發送一個要求對方立即響應的特殊的 Echo分組 。 將 測量 的往返時間除以 2， 就可以得到該鏈路的時延估計值 。 3） 構建鏈路狀態分組 一旦用于交換的鏈路 狀態信息 收集完畢 ， 下一步就是構造一個包含所有這些狀態信息的分組 。 該分組以發送者的標志符開頭 ， 緊跟著是順序號 、 壽命和一個鄰居結點表 。 在鄰居結點表中 ， 列出所有的鄰居結點及相應的鏈路時延 。 鏈路狀態路由算法 交 換 技 術第 5 章分 組 交 換73 構造鏈路狀態分組是容易的 ， 難的是何時構建分組 。 一種方式是定期構建；另一種方式是出現一些重要事件時再構建 。 下圖給出了一個包含 6個結點的子網 ， 其時延標在結點連線上 ， 并給出了相應的 6個鏈路狀態分組 。 構造鏈路狀態分組舉例 ABCDE F42518637A序 號壽 命B 4E5B序 號壽 命A 4C2F 6C序 號壽 命B 2D3E 1D序 號壽 命C 3F7E序 號壽 命A 5C1F 8F序 號壽 命B 6D7E 8交 換 技 術第 5 章分 組 交 換74 該算法最具技巧性的部分就是如何 可靠地發布 鏈路狀態分組 ， 避免出現死循環 、 不可達和其它路由問題 。 鏈路狀態分組的基本發布方法是利用洪泛方式 。 為防止結點處理和轉發過時的鏈路狀態分組 ， 每個分組引入一個 順序號 。 當一個鏈路狀態分組到達時 ， 先查看一下該分組是否已收到過 。 如果是新的 ， 就把它轉發到除了輸入鏈路之外的所有鏈路；否則 ， 則丟棄它 。 在分組擴散過程中 ， 壽命 字段每單位時間遞減一次 ， 如果壽命為 0， 則刪除該分組 ， 以保證沒有任何分組可以在網絡中無限長地存活下去 。 4）發布鏈路狀態分組 交 換 技 術第 5 章分 組 交 換75 鏈路狀態路由算法規定對所有的鏈路狀態分組都需要應答 。 由于鏈路狀態分組以洪泛方式擴散 ， 所以每個結點需要構造一個如下圖所示的分組處理數據結構 ， 用于確定需要向哪些鄰結點轉發或應答 。 發送標志位表示該鏈路狀態分組必須發送給哪些鄰結點 ， 應答標志位表示應給哪些鄰結點發送應答消息 。 分組處理數據結構 ABCDE F42518637A FECD2 12 12 12 02 16 06 05 96 05 90 1 1 10 01 1 0 0 0 10 1 0 1 0 11 0 1 0 1 0100 0 1 1源 結 點序 號 壽 命 A C F A C F 數 據 發 送 標 志A C K 標 志( a ) 子 網 絡 結 構（ b ） 結 點 B 的 分 組 緩 沖 區 數 據 結 構交 換 技 術第 5 章分 組 交 換76 每個結點獲得所有的鏈路狀態分組后 ， 便可以構造整個網絡拓撲圖 ， 每一鏈路的兩個方向都將標出時延 (或代價 )值 。 此時每個結點就可以在本地運行Dijkstra算法 ， 從而 確定 到達所有目的結點的最短路徑 (或最小代價路徑 )， 并 形成分組轉發路由表 。 鏈路狀態路由算法在實際網絡中得到了廣泛的應用 ， 如在 Inter中應用廣泛的 OSPF協議使用的就是該算法 。 另一個使用該算法的重要協議是 ISIS協議 ， 該協議應用于多種 Inter骨干網 (包括老的NSFNET骨干網 )， 和一些數字蜂窩系統中 。 5）計算新路由 交 換 技 術第 5 章分 組 交 換77 集中式路由選擇策略的核心是在網絡中設有 網控中心 NCC。 NCC負責全網狀態信息的收集 、 路由計算以及路由選擇的實現 。 集中式路由選擇策略有多種 ，這取決于儲存在 NCC中的網絡信息的類型 、 路由的計算方法以及實現路由選擇的技術 。 集中式路由選擇策略的 好處 是：各個結點不需要進行路由選擇計算 ， 容易得到精確的路由最優化 。 還可對進入網絡的通信流量實施某種控制 。 集中式路由選擇策略的 缺點 是：在離 NCC較近的地方通信流量的開銷較大 。 更嚴重的是可靠性問題 。 一旦 NCC出故障 ， 則整個網絡即失去控制 。 二、集中式路由選擇策略 交 換 技 術第 5 章分 組 交 換78 從原則上講 ， 在一個網絡中可以混合使用不同類型的路由選擇策略 。 這時只要在每一個結點明確定義出：對于何種類型的通信業務 、 負荷以及網絡的連通條件 ，應當采用何種的路由選擇策略 。 出于多種考慮 ， 可行的混合式路由選擇策略只能是集中式和局部分布式結合起來 。 集中式的路由選擇策略用來尋找在穩定狀態下的最佳路由 ， 然后由 NCC將路由表送到每一個結點去 。 而局部的路由選擇策略則用來提供對局部的擁塞和故障的迅速響應 。 這種響應只是暫時的 ， 因而并不要求很精確 。不需要多長時間 NCC就會發現通信流量以及網絡拓撲的變化情況 ， 于是就會對路由表進行更新 。 三、混合式路由選擇策略 分組交換性能分析 ? 衡量分組交換設備性能的主要指標是交換時延 (Delay)和吞吐量 (Throughput).研究的主要數學工具是概率論和排隊論。 一、分組交換節點的分析模型 ? 節點交換機或者路由器，是一種多輸入多輸出的設備，各輸入端口首先接受并暫存到來的分組，識別和分析分組的首部，然后根據其中的目的地址查找路由表，從而得知該分組應該轉發給那一個下一節點。最后將分組轉移到相應的輸出端口。 ? 分組到達是隨機的，在一個輸出端口發送一個分組的時間內可能有兩個或以上的輸入分組同時轉移到哪里，從而引起輸出鏈路占用的競爭。解決這個問題采用分組緩沖器，發生沖突的情況下只發送其中一個分組，其余分組在緩沖器內排隊等待。 上圖為分組輸出排隊的模型，它是一個隨機服務系統，服務對象是分組，分組進入緩沖器排隊，然后逐個的服務，服務完后離開系統，它的特點是輸入不是單一分組流，而是多個分組流疊加的合成分組流這樣的系統分組很困難，為了簡化分析要做一些假設。 1）各個分組統計獨立 2）各輸入端口到達的分組流式泊松過程，服從泊松分布 3）輸入端口到達的分組均勻地轉移到各輸出端口 ? 經過簡化分組排隊模型變成單輸入單輸出排隊模型。這里分組平均到達速率 λ，任一給定時刻分組緩沖器內等待分組數 Q，一個分組需要等待的時間 TQ，服務器對分組服務時間 TS，分組的服務率 (離去率 )μ(輸出鏈路速率 )，系統內逗留的分組數 N，分組在系統內逗留時間 T。 ? λ和 μ分別是分組平均達到速率和平均服務速率有相同的單位 bit/s ? 這些參數都是隨便變量 ? 分組到達過程為泊松過程的條件下來定量分析 假定分組到達過程為泊松過程，對每個分組服務時間TS相互獨立且服從相同的一般分布，供排隊的緩沖器容量無限大，服務規則為先來先服務 (FIFO)，這樣得到 M/G/1排隊模型。 最后我們介紹一下結論： 系統內逗留的平均分組數 (系統平均對長 )： E[N]=ρ+（ λ 2σB2+ ρ 2） /2(1 ρ) σB2是系統服務時間的方差， ρ= λ/ μ是業務量強度 系統平均時延： E[T]=1/ μ+（ λ 2σB2+ ρ 2） /2(1 ρ) 平均排隊隊長： E[Q]=E[N] ρ=（ λ 2σB2+ ρ 2） /2(1 ρ) 平均排隊等待時間： E[TQ]=（ λ 2σB2+ ρ 2） /2μ(1 ρ) 再假設分組服務時間為定長分布則系統排隊模型變成 M/D/1 令 σB2=0帶入相應計算公式： E[N]= ρ/(1 ρ) *(1 ρ/2) E[T]= ρ/μ(1 ρ) *(1 ρ/2) E[Q]= ρ2/2(1 ρ) E[TQ]= ρ/2μ (1 ρ) 如果再假設分組服務時間服從指數分布 ,則系統的排隊模型變成 M/M/1，平均服務時間為 1/μ,服務時間的方差 σB2= (1/μ)2相應的公式變成： E[N]=ρ/(1 ρ) E[T]=1/μ(1 ρ) 二、分組交換的時延 ? 一個分組在交換機或者路由器內逗留的時間主要有三部分：分組處理時間，分組排隊等待時間和分組服務時間，分組的排隊時間和服務時間在前面已經描述。 ? 分組處理時間指的是：接收完整的數據幀，提取與識別分組標頭，查找路由表，將分組轉移到輸出緩沖器等環節所經歷的時間，這個時間主要取決于分組長度，路由表規模，查找算法以及處理器的能力。 ? 現代分組交換機分組處理速度可達到每秒百萬分組，單個分組處理時間在微秒級。一般的情況下被忽略不考慮。 三、吞吐率 ? 在緩沖器容量無限的情況下，排隊系統不會發生丟失，只要業務量強度小于 1，輸出的業務量始終等于出入，即吞吐率 100%，如果業務量強度大于等于 1，則排隊隊上趨于無窮大，對于特定分組在一定的時間內不可能輸出，因此認為吞吐率為 0 ? 實際的緩沖器的容量是有限的。 ? 1） ρ1(λμ) ? 設緩沖器容量為 K分組的丟失概率： ? PL=PK=(1ρ)/1ρK+1 *ρK 吞吐率 η=1PL ? 2） ρ1 (λμ) ? PL=11/ρ 這種情況下丟失率與緩沖器大小無關 謝謝大家 交 換 技 術第 5 章分 組 交 換88 89