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