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