1、第8講 分組交換與路由選擇 課時(shí)授課計(jì)劃 課 程 內(nèi) 容1內(nèi)容： 電路交換和分組交換 虛電路和數(shù)據(jù)報(bào) 路由選擇策略 目的與要求： 掌握電路交換和分組交換的基本工作原理； 掌握網(wǎng)絡(luò)提供的服務(wù)方式：虛電路和數(shù)據(jù)報(bào)服務(wù)； 理解路由選擇算法； 重點(diǎn)與難點(diǎn)： 重點(diǎn)：分組交換的工作原理、路由選擇算法； 難點(diǎn)：路由選擇算法。2課堂討論：分組交換的工作原理？ 網(wǎng)絡(luò)層提供的基本服務(wù)之一：路由選擇？ 現(xiàn)代教學(xué)方法與手段： 投影 PowerPoint幻燈課件復(fù)習(xí)（提問）： IEEE 體系結(jié)構(gòu)？ CSMA/CD和Token ring？3第5章 網(wǎng)絡(luò)層5.1 電路交換和分組交換5.2 虛電路和數(shù)據(jù)報(bào)5.3 路由選擇4網(wǎng)

2、絡(luò)層討論：為什么需要網(wǎng)絡(luò)層？網(wǎng)絡(luò)層提供哪些服務(wù)? 為什么網(wǎng)絡(luò)互連中需要路由器等路由設(shè)備？5OSI/RM Application protocolRepresentation protocol Session protocol Transport protocolAPDUPPDUFrameBitsPacketSPDUSegment6為什么需要網(wǎng)絡(luò)層主機(jī)A主機(jī)B結(jié)點(diǎn) 1結(jié)點(diǎn) 2結(jié)點(diǎn) 3網(wǎng)絡(luò)連接數(shù)據(jù)鏈路連接數(shù)據(jù)鏈路連接 傳輸層數(shù)據(jù)鏈路層網(wǎng)絡(luò)層網(wǎng)絡(luò)層是通信子網(wǎng)的最高層，對(duì)上層用戶屏蔽了子網(wǎng)通信的細(xì)節(jié)，如子網(wǎng)類型、拓?fù)浣Y(jié)構(gòu)、子網(wǎng)數(shù)目，向上層提供一致的服務(wù)、統(tǒng)一的地址7交換通信網(wǎng)的數(shù)據(jù)交換方式電路交換（c

3、ircuit switching ）分組交換（packet switching）8電路交換電路交換的數(shù)據(jù)傳輸過程電路的建立數(shù)據(jù)傳輸電路釋放電路交換的特點(diǎn)：時(shí)延小，適合于實(shí)時(shí)性強(qiáng)的交互式通信；對(duì)突發(fā)性通信不適應(yīng)，信道利用率低；不具備存儲(chǔ)數(shù)據(jù)或差錯(cuò)控制能力9電路交換12345DTEDCEDCEDTEDCEDCEDCEDCEDTEDTEDTE6ABCDE返回10分組交換分組交換的數(shù)據(jù)傳輸過程仍基于存儲(chǔ)轉(zhuǎn)發(fā)原理，但對(duì)數(shù)據(jù)傳輸單位的作了劃分：將長報(bào)文或大的數(shù)據(jù)塊分割成小段，為每小段附上地址、分組編號(hào)、校驗(yàn)等信息構(gòu)成一個(gè)數(shù)據(jù)分組（數(shù)據(jù)包），作為存儲(chǔ)轉(zhuǎn)發(fā)的邏輯數(shù)據(jù)單元。電路交換的特點(diǎn)：固定大小的分組單位較小

4、，可充分利用線路空閑，從而減少了傳輸延時(shí)；出錯(cuò)重傳的數(shù)據(jù)量也大大減少11分組交換虛電路（Virtual Circuit）數(shù)據(jù)報(bào)（ Datagram ）ACBDEACDH1H2H4H3H5H6ACBDEACDH1H2H4H3H5H6(a) 數(shù)據(jù)報(bào)服務(wù)(b) 虛電路服務(wù)12虛電路含義： 通信子網(wǎng)借以實(shí)現(xiàn)面向連接服務(wù)的工作方式，需要源與目標(biāo)之間建立一條邏輯上的通信鏈路。 涉及虛電路邏輯連接的三個(gè)階段： 虛電路對(duì)立數(shù)據(jù)傳輸虛電路拆除 在建立連接時(shí)，將從源端機(jī)器到目標(biāo)機(jī)器的路由作為連接建立的一部分加以保存。在虛電路上傳送的分組總是取相同的路徑（路由）通過通信子網(wǎng)。13虛電路AEDCBH2H3H1H4H5

5、依次建立5條VC：VC1：A-B-EVC2：A-B-DVC3：B-D-EVC4：C-E-DVC5：A-B-C-D 入口出口H1H1H1125012B012BB 入口出口AAH2 3010E001DD 入口出口BBE010H4001EH4 入口出口H3B4000E002D 入口出口BDC000H5010D A B C D EA2C0H5CH4虛電路路由表建立過程示例14虛電路特點(diǎn)：包傳輸路徑相同，不需要源地址與目標(biāo)地址信息 。 除了建立連接時(shí)需要路由，在數(shù)據(jù)傳送過程中不需要作路由，無路由信息，只有虛電路連接信息。包的傳輸不會(huì)出現(xiàn)丟失、重復(fù)和亂序現(xiàn)象。分類：永久虛電路（PVC）呼叫虛電路（SVC）

6、15數(shù)據(jù)報(bào)通信子網(wǎng)借以實(shí)現(xiàn)面向無連接服務(wù)的工作方式 。為每個(gè)分組選擇獨(dú)立的路由，即不同的分組可以走不同的路由。16數(shù)據(jù)報(bào)AEDCBH2H3H1H4H512目的站輸出線BCDE1212結(jié)點(diǎn)A的路由表數(shù)據(jù)報(bào)的路由表每個(gè)分組都需要攜帶完整的目的地址。每個(gè)結(jié)點(diǎn)保存一個(gè)到網(wǎng)內(nèi)其他結(jié)點(diǎn)的輸出線選擇表17虛電路與數(shù)據(jù)報(bào)的比較數(shù)據(jù)報(bào)子網(wǎng)虛電路子網(wǎng)延時(shí)分組傳播延時(shí)電路建立，分組傳輸延時(shí)路由選擇每個(gè)分組單獨(dú)選擇路由建立虛電路時(shí)選擇路由，以后所有分組都是用該路由狀態(tài)信息子網(wǎng)無需保存狀態(tài)信息每個(gè)節(jié)點(diǎn)要保存一張路由表地址每個(gè)分組包括源端和目的端的完整地址每個(gè)分組含有一個(gè)短的虛電路號(hào)節(jié)點(diǎn)失敗的影響除了在崩潰時(shí)正在由該節(jié)點(diǎn)

7、處理的分組都丟失外，無其它影響所有經(jīng)過失敗節(jié)點(diǎn)的虛電路都要被終止擁塞控制難如果有足夠的緩沖區(qū)分配給已經(jīng)建立的虛電路，則容易控制18路由選擇理想路由算法的基本特性正確性（Correctness）簡單性（Simplicity）健壯性（robustness）穩(wěn)定性（stability）公平性（fairness）優(yōu)越性（optimality）高效性（efficiency）19路由選擇靜態(tài)路由策略擴(kuò)散法固定路由選擇隨機(jī)路由選擇基于流量的路由選擇動(dòng)態(tài)路由策略在網(wǎng)絡(luò)互聯(lián)中講解20擴(kuò)散法(洪泛)基本思想把收到的每一個(gè)包，向除了該包到來的線路外的所有輸出線路發(fā)送。主要問題洪泛要產(chǎn)生大量重復(fù)包。解決措施每個(gè)包頭包

8、含站點(diǎn)計(jì)數(shù)器， 每經(jīng)過一站計(jì)數(shù)器減1， 為0時(shí)則丟棄該包；記錄包經(jīng)過的路徑AKLPEMNDCB圖 洪泛算法示意圖信源21擴(kuò)散法(洪泛)選擇性洪泛算法（selective flooding）洪泛法的一種改進(jìn)。將進(jìn)來的每個(gè)包僅發(fā)送到與正確方向接近的線路上。應(yīng)用情況路由器和線路的資源過于浪費(fèi)，實(shí)際很少直接采用；具有極好的健壯性，可用于軍事應(yīng)用；作為衡量標(biāo)準(zhǔn)評(píng)價(jià)其它路由算法。22固定路由選擇固定路由選擇 在每個(gè)節(jié)點(diǎn)上保持一張路由表,表上標(biāo)明對(duì)每一個(gè)目的地址應(yīng)走哪條鏈路進(jìn)行轉(zhuǎn)發(fā).路由表是在整個(gè)系統(tǒng)進(jìn)行配置時(shí)生成的.配置時(shí)根據(jù)事先計(jì)算好的“網(wǎng)絡(luò)中任意兩個(gè)節(jié)點(diǎn)之間最短路徑”,將這些最短通路制成路由表,存放在

9、各個(gè)節(jié)點(diǎn)中.每一個(gè)分組都可在所到達(dá)的節(jié)點(diǎn)中查找下一步應(yīng)轉(zhuǎn)發(fā)到哪一個(gè)節(jié)點(diǎn)(下一站節(jié)點(diǎn)或后繼節(jié)點(diǎn)). 經(jīng)典的求最短路徑算法是Dijkstra算法.它的條件是已知網(wǎng)絡(luò)的拓?fù)浜透麈溌烽L度, 主要是通過計(jì)算任意兩節(jié)點(diǎn)間的最小鏈路長度,求得從源節(jié)點(diǎn)到目的節(jié)點(diǎn)間最短通路.23固定路由選擇Dijkstra算法 對(duì)于一個(gè)無向圖G=(V，E),其中V表示網(wǎng)絡(luò)中所有節(jié)點(diǎn)的集合,E表示網(wǎng)絡(luò)中所有鏈路的集合,D(v)為源節(jié)點(diǎn)到節(jié)點(diǎn)v的距離,l(i, j)為節(jié)點(diǎn)i至節(jié)點(diǎn)j之間的距離.(1)初始化 任選一個(gè)節(jié)點(diǎn)作為源節(jié)點(diǎn),不妨令 V=1,對(duì)所有不在V中的節(jié)點(diǎn)v,寫出:1456232221113355圖 求最短路徑算法的網(wǎng)絡(luò)

10、拓?fù)鋵?shí)際編程時(shí)一般取D(v)=1000代替.源節(jié)點(diǎn)24固定路由選擇(2)尋找一個(gè)不在V中的節(jié)點(diǎn)w,其D(w)值為最小.把w加入到V中.然后對(duì)所有不在V中的節(jié)點(diǎn),用D(v),D(w)+l(w, v)中較小的值去更新原有的D(v)值,即: D(v) MinD(v),D(w)+l(w, v)(3)重復(fù)步驟(2),直到所有的網(wǎng)絡(luò)節(jié)點(diǎn)都在V中為止. 由Dijkstra算法可知,若將已知的各鏈路長度改為鏈路時(shí)延,跳數(shù),帶寬或費(fèi)用,就相當(dāng)于求任意兩節(jié)點(diǎn)之間具有最小時(shí)延,最少跳數(shù),最大帶寬或最小費(fèi)用的通路.所以, 求最短路徑算法具有普遍的應(yīng)用價(jià)值.25固定路由選擇基于左圖的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu),采用Dijkstra算

11、法,計(jì)算以節(jié)點(diǎn)1為源節(jié)點(diǎn)的最短通路的過程.表中帶圓圈的數(shù)字表示的是: 在每一次執(zhí)行步驟(2)時(shí), 所尋找到的具有最小值的D(w)值.步驟 V D(2) D(3) D(4) D(5) D(6)初始化 1 2 5 1 1 1,4 2 4 2 2 1,4,5 2 3 1 4 3 1,2,4,5 3 1 2 4 4 1,2,3,4,5 2 1 2 4 5 1,2,3,4,5,6 2 3 1 2 145623222111335526固定路由選擇 上述路由表僅是以節(jié)點(diǎn)1為源節(jié)點(diǎn),由Dijkstra算法計(jì)算得到節(jié)點(diǎn)1為根的通路樹,然后生成節(jié)點(diǎn)1內(nèi)存中的路由表這樣的路由表每個(gè)節(jié)點(diǎn)都有一個(gè),只需分別以這些節(jié)點(diǎn)為

12、源點(diǎn),重新執(zhí)行算法即可0)(1)(2)(3)(4)(5)圖 基于Dijkstra算法生成的最短通路樹圖 依據(jù)最短通路樹生成節(jié)點(diǎn)1的路由表目的節(jié)點(diǎn) 下一站123456-24444目的節(jié)點(diǎn) 下一站12*-2427隨機(jī)路由選擇當(dāng)分組到達(dá)某個(gè)節(jié)點(diǎn)時(shí)就隨機(jī)地選擇一條鏈路作為轉(zhuǎn)發(fā)的路由.當(dāng)網(wǎng)絡(luò)中的節(jié)點(diǎn)或鏈路發(fā)生故障時(shí),采用隨機(jī)走動(dòng)法是最有效的,它使得路由算法具有較好的穩(wěn)健性.AKLPEMNDCB信源信宿0.50.50.20.20.30.30.30.3圖 隨機(jī)走動(dòng)算法示意圖0.20.20.20.30.30.30.30.30.30.30.328基于流量的路由選擇基本思想既考慮拓?fù)浣Y(jié)構(gòu)，又兼顧網(wǎng)絡(luò)負(fù)荷；前提：每對(duì)結(jié)點(diǎn)間平均數(shù)據(jù)流是相對(duì)穩(wěn)定和可預(yù)測(cè)的；根據(jù)網(wǎng)絡(luò)帶寬和平均流量，可得出平均包延遲，因此路由選擇問題歸結(jié)為找產(chǎn)生網(wǎng)絡(luò)最小延遲的路