【正文】 一個任務(wù)就是要知道誰是它的 鄰居 ， 這是通過向每條點到點鏈路發(fā)送特殊的 Hello分組來實現(xiàn)的 。 該分組以發(fā)送者的標(biāo)志符開頭 ， 緊跟著是順序號 、 壽命和一個鄰居結(jié)點表 。 當(dāng)一個鏈路狀態(tài)分組到達時 ， 先查看一下該分組是否已收到過 。 鏈路狀態(tài)路由算法在實際網(wǎng)絡(luò)中得到了廣泛的應(yīng)用 ， 如在 Inter中應(yīng)用廣泛的 OSPF協(xié)議使用的就是該算法 。 更嚴重的是可靠性問題 。不需要多長時間 NCC就會發(fā)現(xiàn)通信流量以及網(wǎng)絡(luò)拓撲的變化情況 ， 于是就會對路由表進行更新 。這里分組平均到達速率 λ，任一給定時刻分組緩沖器內(nèi)等待分組數(shù) Q，一個分組需要等待的時間 TQ，服務(wù)器對分組服務(wù)時間 TS，分組的服務(wù)率 (離去率 )μ(輸出鏈路速率 )，系統(tǒng)內(nèi)逗留的分組數(shù) N，分組在系統(tǒng)內(nèi)逗留時間 T。 三、吞吐率 ? 在緩沖器容量無限的情況下，排隊系統(tǒng)不會發(fā)生丟失，只要業(yè)務(wù)量強度小于 1，輸出的業(yè)務(wù)量始終等于出入，即吞吐率 100%，如果業(yè)務(wù)量強度大于等于 1，則排隊隊上趨于無窮大，對于特定分組在一定的時間內(nèi)不可能輸出，因此認為吞吐率為 0 ? 實際的緩沖器的容量是有限的。 上圖為分組輸出排隊的模型，它是一個隨機服務(wù)系統(tǒng)，服務(wù)對象是分組，分組進入緩沖器排隊，然后逐個的服務(wù)，服務(wù)完后離開系統(tǒng)，它的特點是輸入不是單一分組流，而是多個分組流疊加的合成分組流這樣的系統(tǒng)分組很困難，為了簡化分析要做一些假設(shè)。 而局部的路由選擇策略則用來提供對局部的擁塞和故障的迅速響應(yīng) 。 還可對進入網(wǎng)絡(luò)的通信流量實施某種控制 。 分組處理數(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é) 點序 號 壽 命 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é) 點 B 的 分 組 緩 沖 區(qū) 數(shù) 據(jù) 結(jié) 構(gòu)交 換 技 術(shù)第 5 章分 組 交 換76 每個結(jié)點獲得所有的鏈路狀態(tài)分組后 ， 便可以構(gòu)造整個網(wǎng)絡(luò)拓撲圖 ， 每一鏈路的兩個方向都將標(biāo)出時延 (或代價 )值 。 鏈路狀態(tài)分組的基本發(fā)布方法是利用洪泛方式 。 將 測量 的往返時間除以 2， 就可以得到該鏈路的時延估計值 。 事實上 ， 完整的拓撲結(jié)構(gòu)和所有的鏈路時延都通過試驗測量并發(fā)布到網(wǎng)絡(luò)中每一個結(jié)點 。 這就是所謂的 “ 無窮計算問題 ” 。 這里的 “ 距離 ” ，可以用結(jié)點間路徑的跳數(shù) 、 時延和排隊隊長等度量 。 三、洪泛法（ flooding） 交 換 技 術(shù)第 5 章分 組 交 換66 自適應(yīng)路由就是網(wǎng)絡(luò)結(jié)點定期或不定期地根據(jù)當(dāng)時的網(wǎng)絡(luò)狀態(tài) 調(diào)整路由 。 這種方法可使通信流量平衡 ,平均時延小 。 再令l(i,j)為結(jié)點 i至結(jié)點 j之間的距離 。 路由表是在整個系統(tǒng)進行 配置 時生成的 ， 并且在此后的一段相當(dāng)時間內(nèi)保持固定不變 。 6）算法應(yīng)是 最佳 的。 二、路由選擇算法 交 換 技 術(shù)第 5 章分 組 交 換55 路由表的簡化 考慮下圖所示的網(wǎng)絡(luò) ， 網(wǎng)絡(luò)圖 G=(V,E)， 其中 ，V={A,B,C,D,E,F} ， E={l1,l2,… l10}。 默認路由比其它項目的優(yōu)先級低 。 本節(jié)的主要內(nèi)容 交 換 技 術(shù)第 5 章分 組 交 換51 (1) 標(biāo)頭指示法 標(biāo)頭指示法是由源結(jié)點將路由信息標(biāo)識在每個分組的標(biāo)頭中 ， 故又稱為 源路由法 。 DG方式提供無連接服務(wù) ， 適用于詢問 /響應(yīng)型數(shù)據(jù)業(yè)務(wù) 。因此虛電路對通信的服務(wù)質(zhì)量 QoS有比較好的保證 。 在虛電路方式下 ， 屬于同一呼叫的各個數(shù)據(jù)分組均沿著同一虛電路流動 (路由相同 )， 分組的路由選擇是以呼叫為單位的 ， 而不是以單個分組為單位進行的 。 優(yōu)點 數(shù)據(jù)報方式路由靈活 ， 便于繞過過于繁忙或發(fā)生故障的結(jié)點或鏈路 ， 并且比較適合于短報文的傳送 。 一個分組交換網(wǎng)可以容許很多主機同時進行通信 ， 而一個主機中的多個進程也可以各自和不同主機中的不同進程進行通信 。 分組交換繼承了存儲轉(zhuǎn)發(fā)這一交換機制 ， 但存儲轉(zhuǎn)發(fā)的基本數(shù)據(jù)單元是分組 （ 又稱為包 ） 。可以充分利用空閑時隙傳輸數(shù)據(jù)。 由此可見，必須尋找出新的適合于計算機通信的交換技術(shù)，這就要求改變傳統(tǒng)的交換方式。 但實際上這兩個層次還是很重要的 。 ISO認識到了網(wǎng)際協(xié)議 IP的重要性后 ， 只好在網(wǎng)絡(luò)層中劃分出一個子層來完成類似TCP/IP中 IP的作用 。 另一種是無連接的用戶數(shù)據(jù)報協(xié)議 UDP。 OSI的 7層體系結(jié)構(gòu)中 ， 下面的四層 ， 即物理層， 數(shù)據(jù)鏈路層 ， 網(wǎng)絡(luò)層 ， 傳輸層與前面介紹的完全相同 。 這 3個層次從上到下的名稱是：應(yīng)用層 、 表示層和會話層 。 上層使用下層所提供的服務(wù)必須通過層間交換的命令來實現(xiàn) ， 這些命令稱為 服務(wù)原語 。 而要實現(xiàn)本層協(xié)議 ， 還需要使用下一層所提供的服務(wù) 。 這就是所謂的“ 對等層 ” （ Peer Layers） 之間的通信 。 計算機 1AP4321AP 254321物 理 傳 輸 媒 質(zhì)計算機 2應(yīng)用程序數(shù)據(jù)H 5H4H 3H 2 2T數(shù) 據(jù) 部 分數(shù) 據(jù) 部 分數(shù) 據(jù) 部 分數(shù) 據(jù) 部 分1010011 ? 比 特 流 ? 010111010首部尾部51交 換 技 術(shù)第 5 章分 組 交 換16 數(shù)據(jù)在各層之間的傳遞過程 假定兩個主機是直接相連的 ， 計算機 1的應(yīng)用進程AP1向計算機 2的應(yīng)用進程 AP2傳送 數(shù)據(jù) 。 運輸層根據(jù)通信子網(wǎng)的特性最佳地利用網(wǎng)絡(luò)資源 ，并以可靠和經(jīng)濟的方式 ， 透明地傳送報文 。 交 換 技 術(shù)第 5 章分 組 交 換12 (2) 數(shù)據(jù)鏈路層 (Data Link Layer) 網(wǎng)絡(luò)層的 基本任務(wù) 是將數(shù)據(jù)從源 (結(jié) )點傳送到目的 (結(jié) )點 。 物理層要規(guī)定與 信道 （ 傳輸媒質(zhì) ） 的接口 ， 包括接口的電氣特性 、 機械特性 、 功能特性和工作時序 。 應(yīng)用層 運輸層 網(wǎng)絡(luò)層 數(shù)據(jù)鏈路層 物理層 交 換 技 術(shù)第 5 章分 組 交 換10 根據(jù)計算機網(wǎng)絡(luò) ， 特別是互聯(lián)網(wǎng)( Inter ) 的建設(shè) 、 發(fā)展和運行的經(jīng)驗 ， 將復(fù)雜的計算機網(wǎng)絡(luò)的功能分為如右圖所示的五層是比較適當(dāng)?shù)?。兩個模塊之間的虛線表示兩個計算機系統(tǒng)文件交換的一些命令等 ? 第二類工作設(shè)立一個通信模塊，用來保證文件和文件傳送命令能可靠地在兩端系統(tǒng)之間交換。 網(wǎng)絡(luò)協(xié)議主要由以下三個要素組成： (1) 語法 ， 即數(shù)據(jù)和控制信息的格式和編碼； (2) 語義 ， 即各種控制信息的含義及相應(yīng)的控制操作； (3) 同步 ， 即速率適配 、 事件出現(xiàn)順序的控制等 。 交 換 技 術(shù)第 5 章分 組 交 換2 分組交換 (Packet Switching)也稱為包交換 ， 它是現(xiàn)代計算機網(wǎng)絡(luò)的技術(shù)基礎(chǔ) 。交 換 技 術(shù)第 5 章分 組 交 換第 5 章 分組交換 教學(xué)大綱要求： （ 1） 掌握計算機網(wǎng)絡(luò)的組成和 OSI協(xié)議體系結(jié)構(gòu) 。 本章主要涉及傳統(tǒng)的分組交換 ， 而新型分組交換將在后續(xù)的章節(jié)中討論 。 對不同系統(tǒng)的實體之間的信息交流進行控制的一組規(guī)則或約定 ， 稱為 網(wǎng)絡(luò)協(xié)議或規(guī)約 。 ? 可以將通過網(wǎng)絡(luò)傳送文件的工作分為三類： ? 第一類工作與傳送文件直接相關(guān)，例如確信對方做好接受準(zhǔn)備，文件格式轉(zhuǎn)換等。 交 換 技 術(shù)第 5 章分 組 交 換9 計算機網(wǎng)絡(luò)體系結(jié)構(gòu) 一 、 分層 分層就是將一個復(fù)雜的系統(tǒng)功能劃分為若干相對獨立的子功能；每層完成一個子功能；下層為上層服務(wù) ， 上層是下層的用戶 。物理層就是要盡可能地減小這些損傷 ， 達到 “ 透明 ” 傳輸 。 鏈路連接控制只在有連接方式下采用 。 當(dāng)報文較長時 ， 先要把它分割成若干段 ，然后再交給下一層 （ 網(wǎng)絡(luò)層 ） 進行傳送 。 主機或端系統(tǒng)要完成所有各層的功能；而通信子網(wǎng)的各個結(jié)點和子網(wǎng)之間的路由器中只需完成低層功能 。 同理 ， 任何兩個同樣的層次 （ 圖中的水平虛線所示 ） 之間 ， 也好像將數(shù)據(jù)通過水平虛線直接傳遞給對方 。 在協(xié)議的控制下 ， 兩個對等實體間的通信使得本層能夠向上一層提供 服務(wù) 。 只有那些能夠被高一層看得見的功能才能稱之為 “ 服務(wù) ” 。 開放系統(tǒng)互連參考模型 國際標(biāo)準(zhǔn)化組織 （ ISO, International Standard Organization ） 制 定的 開放 系統(tǒng) 互連 （ OSI, Open System Interconnection） 參考模型采用 7個層次的網(wǎng)絡(luò)體系結(jié)構(gòu) ， 也就是將前面所講的原理性體系結(jié)構(gòu)中的應(yīng)用層再劃分為 3個層次 ， 其余 4層保持不變 。 交 換 技 術(shù)第 5 章分 組 交 換25 （ 2） 表示層 （ Presentation Layer） 應(yīng)用層負責(zé)為用戶提供接入 OSI環(huán)境的方法 ， 支持各種應(yīng)用 ， 如網(wǎng)絡(luò)虛擬終端 、 文件傳送 、 電子郵件 、 多媒體 、 WWW等 。 運輸層 這層可使用兩種不同的協(xié)議 ， 一種是面向連接的傳輸控制協(xié)議 TCP。 但 ISO和CCITT最初只考慮到使用一種標(biāo)準(zhǔn)的公用數(shù)據(jù)網(wǎng)將各種不同的系統(tǒng)互連在一起 。 TCP/IP的網(wǎng)絡(luò)接口層嚴格來說并不是一個層次而僅僅是一個接口 ， 而在網(wǎng)絡(luò)層下面的數(shù)據(jù)鏈路層和物理層則根本沒有 。 另外，由于計算機和各種終端的傳送 速率不一樣，采用電路交換不同類型，不同規(guī)格，不同速率的終端很難相互通信，而電路交換所分配的帶寬是固定的或量化的，因此缺乏 靈活性， 而且電路交換通話雙方建立的通路中的任何一個點出了故障就必須重新?lián)芴柦㈡溄印Ｈ绻捎猛綍r分復(fù)用，每一幀都有 4個時隙第一到第四個時隙分別分配給 ABCD當(dāng)某個數(shù)據(jù)源無數(shù)據(jù)發(fā)送相應(yīng)的時隙就空閑，不能被其他用戶使用，但是如果采用異步時分復(fù)用用時隙標(biāo)題區(qū)分各路數(shù)據(jù)。 分組交換是報文交換的繼承和發(fā)展 。 分組交換網(wǎng) BACED H1HHHHH32456 （ a ） 通 信 子 網(wǎng) 和 主 機 通 信 子 網(wǎng)H1H2H4H6H5H3結(jié) 點交 換 機ABDEC1 2 3 4123441 2 31 2 341234 （ b ） 結(jié) 點 交 換 機 的 兩 組 端 口 結(jié) 點交 換 機結(jié) 點交 換 機結(jié) 點交 換 機結(jié) 點交 換 機高 速 鏈 路交 換 技 術(shù)第 5 章分 組 交 換40 結(jié)點交換機處理分組的過程是：將收到的分組先放入緩沖區(qū) ， 再查找 路由表 ， 然后確定將該分組交給某個端口轉(zhuǎn)發(fā)出去 。 交 換 技 術(shù)第 5 章分 組 交 換42 分組交換方式 數(shù)據(jù)報分組交換在傳送數(shù)據(jù)之前 ， 不需要預(yù)先建立任何連接 ， 而是直接按照每個分組首部中的目的地址獨立選擇轉(zhuǎn)發(fā)路徑 。 這種連接通路稱為虛通路或虛電路 (VC)。 此外 ， 還可以采取連接接納控制等措施進行流量控制 。 (5) 提供的 服務(wù) 和 應(yīng)用 VC方式支持面向連接的服務(wù) ， 適用于連續(xù)的數(shù)據(jù)流傳送 。 那么路由應(yīng)該如何表示 ？ 網(wǎng)絡(luò)依據(jù)什么信息來進行路由選擇 ？ 路由選擇應(yīng)該采取哪些策略和算法 ？ 這些就是本節(jié)要討論的問題 。 12