《計(jì)算機(jī)網(wǎng)絡(luò)教程》第6章 網(wǎng)絡(luò)層-2

《計(jì)算機(jī)網(wǎng)絡(luò)教程》電子教案第六章網(wǎng)絡(luò)層

路由選擇與路由協(xié)議2主要內(nèi)容路由選擇（6.2）最佳路由算法靜態(tài)路由方式動(dòng)態(tài)路由方式層次路由、策略路由和自治系統(tǒng)路由協(xié)議（6.3）路由器和路由協(xié)議路由信息協(xié)議RIP開放最短路徑優(yōu)先協(xié)議OSPF3路由算法路由算法的目的是找到一條從源到目的地的一條“最好”路徑（通常是指具有最小花費(fèi)的路徑）?；ㄙM(fèi)可能是距離、信道帶寬、平均通信量、通信開銷、隊(duì)列平均長度、測量到的時(shí)延和其它一些因素的綜合。給定一個(gè)代表該網(wǎng)絡(luò)的圖，找到一條由一系列鏈路組成的路徑，其中：路徑中的第一條鏈路連接到源。路徑中的最后一條鏈路連接到目的地。對(duì)應(yīng)所有的i，路徑中的第i和i-1條鏈路連接到同一個(gè)節(jié)點(diǎn)。最小花費(fèi)路徑：源到目的地之間所有可能的路徑的鏈路花費(fèi)總和最小。（若所有的鏈路花費(fèi)相同，則最小花費(fèi)路徑即最短路徑。）Dijkstra最佳路由算法Dijkstra算法網(wǎng)絡(luò)中所有節(jié)點(diǎn)的集合為N，源節(jié)點(diǎn)為SL(i,j)為節(jié)點(diǎn)i與j之間鏈路的權(quán)值；若沒有直接連接則為∞算法求得的當(dāng)前從S到n的最少花費(fèi)路由的花費(fèi)C(n)已由算法歸并的節(jié)點(diǎn)的集合M1.初始化M={S};C(n)=L(S,n)fornS2.從不在M中的相鄰節(jié)點(diǎn)中找出一個(gè)具有和節(jié)點(diǎn)S的最少花費(fèi)路由的節(jié)點(diǎn)，并且把該節(jié)點(diǎn)規(guī)約進(jìn)M中。即： 尋找wM，使得把w加入到M中。3.更新最少花費(fèi)路徑對(duì)所有nM有 C(n)=min[C(n),C(w)+L(w,n)]如果后一項(xiàng)為最小值，則從S到n的路徑更新為從S到w的路徑再加上從w到n的鏈路。4.重復(fù)步驟2和3，直到M=N?；舅枷耄呵跋蛩阉?，經(jīng)過迭代，按照到源節(jié)點(diǎn)的最短距離的遞增的順序，逐步尋找到那些更加接近于源節(jié)點(diǎn)的節(jié)點(diǎn)。5Dijkstra最佳路由算法（例）（所有M中的節(jié)點(diǎn)最佳路徑已確定）D(,-)B(2,A)C(,-)H(,-)D(,-)B(2,A)ABCDEFGHAD(,-)E(,-)F(,-)G(6,A)H(,-)2732232246AB(2,A)C(9,B)E(4,B)F(6,E)G(5,E)AB(2,A)C(9,B)G(5,E)H(8,F)AB(2,A)C(9,B)D(,-)E(4,B)F(6,E)G(5,E)H(9,G)AC(9,B)D(,-)E(4,B)F(,-)G(6,A)H(,-)E(4,B)F(6,E)(a)(b)(c)(d)(e)(f)1已規(guī)約節(jié)點(diǎn)Path(Cost,prev)演繹直到結(jié)束的步驟？6路由方式路由方式靜態(tài)路由（非適應(yīng)路由）擴(kuò)散法固定路由選擇隨機(jī)路由選擇基于流量的路由選擇動(dòng)態(tài)路由（適應(yīng)路由）孤立路由選擇集中路由選擇分布路由選擇分別對(duì)應(yīng)著網(wǎng)絡(luò)狀態(tài)信息的三種來源：本地、所有節(jié)點(diǎn)、相鄰節(jié)點(diǎn)7擴(kuò)散法節(jié)點(diǎn)從某條輸入線路收到一個(gè)分組之后，把該分組從除了分組到來的線路外的所有其他輸出線路上發(fā)出。會(huì)產(chǎn)生大量的重復(fù)分組。用于健壯性要求很高的場合。還可被用來分發(fā)信息、判斷可達(dá)性、找到最短路徑等。靜態(tài)路由：擴(kuò)散法(flooding)站點(diǎn)計(jì)數(shù)器，每到達(dá)一個(gè)節(jié)點(diǎn)減1，為0時(shí)丟棄記錄分組擴(kuò)散的路徑選擇擴(kuò)散：選擇可能向目的節(jié)點(diǎn)的方向8固定路由選擇網(wǎng)絡(luò)節(jié)點(diǎn)存儲(chǔ)固定路由表，路由表記錄到達(dá)某個(gè)目的節(jié)點(diǎn)而選擇的下一節(jié)點(diǎn)或鏈路。當(dāng)分組到達(dá)某節(jié)點(diǎn)時(shí)，節(jié)點(diǎn)根據(jù)分組中的地址信息從固定路由表中找出對(duì)應(yīng)的目的節(jié)點(diǎn)所應(yīng)選擇的下一節(jié)點(diǎn)，將分組轉(zhuǎn)發(fā)給該下一節(jié)點(diǎn)。通常由網(wǎng)絡(luò)控制中心構(gòu)造固定路由表并發(fā)送給所有節(jié)點(diǎn)（網(wǎng)絡(luò)拓?fù)涓淖儠r(shí)，重新構(gòu)造）。優(yōu)點(diǎn)：簡單，適合于在一個(gè)負(fù)載穩(wěn)定、拓?fù)渥兓淮蟮木W(wǎng)絡(luò)中運(yùn)行。缺點(diǎn)：靈活性較差，無法對(duì)網(wǎng)絡(luò)的擁塞和故障作出反應(yīng)。改進(jìn)：在最優(yōu)路由的下一節(jié)點(diǎn)之外提供幾個(gè)替換節(jié)點(diǎn)，并且可以使這些替換節(jié)點(diǎn)的使用符合一定的概率。

隨機(jī)路由選擇當(dāng)分組到達(dá)節(jié)點(diǎn)后，隨意選擇一條輸出線路進(jìn)行轉(zhuǎn)發(fā)。和擴(kuò)散法類似。每個(gè)輸出線路的選擇是符合預(yù)定的概率（概率數(shù)的分配考慮網(wǎng)絡(luò)的拓?fù)渑c容量）。若概率相等，則只是簡單地循環(huán)選擇下一節(jié)點(diǎn)。靜態(tài)路由：固定路由和隨機(jī)路由9動(dòng)態(tài)路由：孤立路由選擇動(dòng)態(tài)路由需要考慮的問題網(wǎng)絡(luò)節(jié)點(diǎn)（路由器）的處理負(fù)擔(dān)增加的網(wǎng)絡(luò)負(fù)載算法反應(yīng)太快而引起振蕩，反應(yīng)太慢而起不到作用孤立路由選擇每個(gè)節(jié)點(diǎn)根據(jù)自己的信息獨(dú)立確定路由。如：最短等待法：選擇所有輸出鏈路上具有最短隊(duì)列的那條鏈路。優(yōu)點(diǎn)、缺點(diǎn)、改進(jìn)？逆向?qū)W習(xí)算法（BackwardLearning）：根據(jù)收到的分組了解目的的最短路徑。優(yōu)點(diǎn)、缺點(diǎn)、改進(jìn)？10動(dòng)態(tài)路由：集中路由選擇集中路由算法根據(jù)所有節(jié)點(diǎn)的網(wǎng)絡(luò)信息來選擇路由由一個(gè)集中的路由控制中心RCC（RoutingControlCenter）動(dòng)態(tài)收集網(wǎng)絡(luò)的狀態(tài)信息，使用最短路徑算法計(jì)算出每對(duì)節(jié)點(diǎn)之間的最優(yōu)路徑，構(gòu)造出路由表分發(fā)給對(duì)應(yīng)的每個(gè)節(jié)點(diǎn)。優(yōu)點(diǎn)：類似于固定路由簡單，但具有動(dòng)態(tài)適用性。缺點(diǎn)：節(jié)點(diǎn)與RCC的信息交換產(chǎn)生額外的負(fù)載信息的一致性（同步問題）RCC的脆弱性δ路由選擇把集中路由選擇和孤立路由選擇結(jié)合起來，是一種介于集中路由選擇和孤立路由選擇之間的混合路由選擇算法。通過調(diào)整δ可以在RCC和各節(jié)點(diǎn)之間分配決定權(quán)。11動(dòng)態(tài)路由：分布路由選擇分布路由選擇根據(jù)鄰居節(jié)點(diǎn)的信息計(jì)算路由距離向量路由僅僅了解到鄰居節(jié)點(diǎn)及到鄰居節(jié)點(diǎn)的花費(fèi)鄰居節(jié)點(diǎn)間交換路由表分布式迭代計(jì)算鏈路狀態(tài)路由僅僅了解到鄰居節(jié)點(diǎn)及到鄰居節(jié)點(diǎn)的花費(fèi)鏈路狀態(tài)被擴(kuò)散到所有路由器根據(jù)全局拓?fù)浒凑誅ijkstra算法計(jì)算路由12距離向量路由距離向量路由初始路由表中僅僅包含到直接鄰居的路由分布式：每個(gè)節(jié)點(diǎn)只需要把路由表傳遞給直接鄰居異步：每個(gè)節(jié)點(diǎn)獨(dú)立定期發(fā)送路由表，節(jié)點(diǎn)間路由交換步驟無需同步迭代：每個(gè)節(jié)點(diǎn)收到鄰居節(jié)點(diǎn)來的路由表后重新計(jì)算路由表（尋找通過直接鄰居到達(dá)目的地中的更短路徑）迭代計(jì)算過程中無需額外的信號(hào)來通知結(jié)束，迭代過程在沒有新的信息更新時(shí)自動(dòng)結(jié)束13Bellman算法Bellman（Ford、Fulkerson）算法距離表記錄當(dāng)前節(jié)點(diǎn)通過周圍鄰居到某個(gè)目的地的花費(fèi)，比如節(jié)點(diǎn)X通過鄰居Z到Y(jié)D(Y,Z)XdistancefromXtoY,viaZasnexthopC(X,Z)+min{D(Y,w)}Zw==D(Y,*)XMinimumknowndistancefromXtoY=H(Y)X=NexthopnodefromXtoY14Bellman算法AEDCB781212D()ABCDA1764B148911D5542EcosttodestinationviadestinationD(C,D)EC(E,D)+min{D(C,w)}Dw==2+2=4D(A,D)EC(E,D)+min{D(A,w)}Dw==2+3=5D(A,B)EC(E,B)+min{D(A,w)}Bw==8+6=14loop!loop!H(Y)=X

ABCD

A,1D,5D,4D,2Outgoinglinktouse,costdestination15距離向量路由算法Dy(z,*)xyzy’z’C(x,y)C(x,y’)Dy’(z,*)Dx(z,*)如果從鄰居收到路由信息，發(fā)現(xiàn)通過鄰居到某個(gè)目的地的路由更好，則更新相應(yīng)的路由表項(xiàng)：以前無到該目的地的路由，新增:到目的地Z的路由經(jīng)過Y轉(zhuǎn)發(fā)，距離為C(x,y)+Dy(z,*)以前有到目的地的路由，并且下一跳段也正好是該鄰居，則更新路徑花費(fèi)比較是否新的路徑要更短，如果是，則更新表項(xiàng)C(x,y)+Dy(z,*)<Dx(z,*)

16無窮計(jì)數(shù)問題鏈路花費(fèi)改變時(shí)好消息意味著一條更好的路徑，很快被相鄰路由器知道，并且更新相應(yīng)路由表，再通知給其它路由器。XZ1450Y1算法結(jié)束好消息傳播迅速17無窮計(jì)數(shù)問題無窮計(jì)數(shù)問題節(jié)點(diǎn)僅僅根據(jù)通過鄰居到目的地的花費(fèi)來選擇最短路徑，可能出現(xiàn)路由回路壞消息傳播慢（收斂慢）XZ1450Y60orerroralgorithmcontinueson!18Split-horizonandPoisonreverse水平分割（Split-Horizon）不把從某個(gè)接口了解到的路由信息再通過該接口傳遞給其他路由器。

即如果A到某個(gè)目的地D的路由要經(jīng)過鄰居B，則A向B發(fā)送的更新消息不會(huì)包含到D的路由毒性反轉(zhuǎn)水平分割（Poisonreverse）如果A到某個(gè)目的地D的路由要經(jīng)過鄰居B：A向B發(fā)送的更新消息中到目的地D的距離為無窮大。XZ1450Y60algorithmterminates19TriggeredUpdate水平分割解決了兩個(gè)節(jié)點(diǎn)間的路由回路，但是考慮三個(gè)或者更多節(jié)點(diǎn)間的路由回路，仍然失敗：C-D鏈路斷開A認(rèn)為經(jīng)B可以到達(dá)DC收到該消息，認(rèn)為經(jīng)A可到DC告訴B經(jīng)A可到D無窮計(jì)數(shù)問題的出現(xiàn)主要是新的消息剛傳播出去又收到來自于其他節(jié)點(diǎn)的老的信息：異步帶來的問題，且收斂太慢觸發(fā)更新當(dāng)路由器了解到到某個(gè)目的地的路由有變化時(shí)，馬上（等待一段隨機(jī)時(shí)間）發(fā)送更新消息，從而加快收斂過程Hold-Down一旦路由器了解到某個(gè)網(wǎng)絡(luò)不可達(dá)，在一段時(shí)間內(nèi)忽略所有有關(guān)那個(gè)網(wǎng)絡(luò)的路由信息缺省為60秒，要求所有路由器采用相同的Hold-down間隔ABCD20鏈路狀態(tài)路由鏈路狀態(tài)路由鄰居發(fā)現(xiàn)過程路由器定期在鏈路上發(fā)送報(bào)文，通過從鏈路上收到的來自于鄰居節(jié)點(diǎn)的報(bào)文來發(fā)現(xiàn)鄰居到鄰居節(jié)點(diǎn)的花費(fèi)可以通過手工配置或者通過測量延遲的方法來獲得每個(gè)節(jié)點(diǎn)根據(jù)其所有鄰居列表和到鄰居的花費(fèi)組建鏈路狀態(tài)分組，然后通過擴(kuò)散的方法傳播給所有路由器每個(gè)節(jié)點(diǎn)根據(jù)了解到的當(dāng)前全局拓?fù)溆?jì)算路由（Dijkstra算法）21鏈路狀態(tài)路由：鄰居發(fā)現(xiàn)鄰居可達(dá)性：HELLO協(xié)議：回應(yīng)RouterID定期在鏈路上發(fā)送包括RouterID和聽到的鄰居RouterIDk-out-of-n方法：為了測試某種狀態(tài)，如果n次測試中有k次滿足，則認(rèn)為該狀態(tài)滿足鏈路花費(fèi)：發(fā)一個(gè)分組，鄰居節(jié)點(diǎn)響應(yīng)，分組來回的時(shí)間/2為鏈路延遲測量延遲時(shí)是否考慮負(fù)載因素：排隊(duì)還是隊(duì)頭？考慮負(fù)載因素：負(fù)載均衡可能產(chǎn)生不穩(wěn)定路由22鏈路狀態(tài)路由：信息的分發(fā)鏈路狀態(tài)信息的分發(fā)：擴(kuò)散法：路由分組包括順序號(hào)，節(jié)點(diǎn)記錄最新收到的來自于各個(gè)節(jié)點(diǎn)的最大順序號(hào)過時(shí)、重復(fù)的信息丟棄，新的信息被擴(kuò)散順序號(hào)重復(fù)使用，并且路由器可能崩潰解決方法：順序號(hào)足夠大（32比特）增加一個(gè)計(jì)時(shí)字段：丟棄過時(shí)的路由器信息僅僅這樣還不夠假設(shè)一個(gè)路由器出現(xiàn)故障，發(fā)送三個(gè)更新消息，順序號(hào)分別為a,b,c,并且滿足a<b,c<a解決方法：硬件順序號(hào)發(fā)生器，有限時(shí)間內(nèi)順序號(hào)永遠(yuǎn)不回繞nn+1abb’

b’<a<b23鏈路狀態(tài)路由：擴(kuò)散LSP節(jié)點(diǎn)間的路由信息交換采用確認(rèn)機(jī)制:擴(kuò)散LSP時(shí)要求ACK收到路由分組后不是馬上擴(kuò)散，而是等待一段時(shí)間，丟棄這段時(shí)間來的重復(fù)和過時(shí)的分組，減少負(fù)載開銷路由器從X收到S的LSP時(shí)如果順序號(hào)更新，則接受，增加S的狀態(tài)，設(shè)置ACKX，設(shè)置Send給其它路由器如果更老，則忽略如果相等，則設(shè)置ACKX，清除SendX輪流掃描ACK和Send標(biāo)志，發(fā)送實(shí)際的報(bào)文24層次路由網(wǎng)絡(luò)規(guī)模很大時(shí)，將網(wǎng)絡(luò)分成若干個(gè)區(qū)域，各個(gè)區(qū)域內(nèi)的節(jié)點(diǎn)只考慮本區(qū)域內(nèi)的路由，而區(qū)域間的路由選擇由各個(gè)區(qū)域中某幾個(gè)節(jié)點(diǎn)負(fù)責(zé)完成。100個(gè)節(jié)點(diǎn)分成10個(gè)區(qū)域，每個(gè)區(qū)域內(nèi)有10個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)路由表項(xiàng)為10＋9＝19，而不是100。Kamoun和Kleinrock結(jié)論：理論上將N個(gè)節(jié)點(diǎn)分成m個(gè)層次，每個(gè)節(jié)點(diǎn)存放的信息：當(dāng)m=lnN時(shí)，f(m)最小，表項(xiàng)總數(shù)f=elnN。25層次路由表項(xiàng)對(duì)比26策略路由在實(shí)際實(shí)施路由選擇時(shí)，往往還需要從策略上進(jìn)行考慮，即所謂策略路由，有時(shí)更多地稱為基于策略（policies-based）的路由。法律限制、利益考慮計(jì)費(fèi)策略、服務(wù)質(zhì)量考慮27自治系統(tǒng)自治系統(tǒng)（AutonomousSystem，AS）AS由一個(gè)獨(dú)立的管理實(shí)體控制的一組網(wǎng)絡(luò)和路由器組成。

一般一個(gè)互連網(wǎng)是由許多個(gè)AS組成的，AS內(nèi)部可以選擇任何路由協(xié)議，來進(jìn)行AS內(nèi)部的路由。為使AS中的網(wǎng)絡(luò)能夠被互連網(wǎng)中別的AS訪問到，它必須把AS內(nèi)網(wǎng)絡(luò)的可達(dá)性信息傳遞給其他AS，實(shí)現(xiàn)AS間的路由。每個(gè)AS都被分配了一個(gè)AS編號(hào)，該AS編號(hào)由一個(gè)中央權(quán)威機(jī)構(gòu)進(jìn)行分配，它唯一地標(biāo)識(shí)了對(duì)應(yīng)的AS。AS1AS2EGPIGPR1R2EGP：ExteriorGatewayProtocolIGP：InteriorGatewayProtocol

28主要內(nèi)容路由選擇（6.2）最佳路由算法靜態(tài)路由方式動(dòng)態(tài)路由方式層次路由、策略路由和自治系統(tǒng)路由協(xié)議（6.3）路由器和路由協(xié)議路由信息協(xié)議RIP開放最短路徑優(yōu)先協(xié)議OSPF29路由器網(wǎng)絡(luò)層互連設(shè)備主機(jī)H3R2H4H5H6R3R1R4R6R5R7H2H1路由器IP分組的傳遞過程？分組哪些字段會(huì)變化？30路由器三個(gè)層次的功能接口級(jí)（物理層和數(shù)據(jù)鏈路層）執(zhí)行整套與幀傳輸相關(guān)的物理層和數(shù)據(jù)鏈路層功能，包括物理接口、物理信號(hào)處理、幀處理等，以及在校驗(yàn)和正確時(shí)傳遞幀數(shù)據(jù)（網(wǎng)絡(luò)層分組）給上層（網(wǎng)絡(luò)層）。網(wǎng)絡(luò)層協(xié)議檢查分組的網(wǎng)絡(luò)層頭部并且更新頭部的一些內(nèi)容根據(jù)路由表進(jìn)行分組轉(zhuǎn)發(fā)（路由）為上層過濾分組路由協(xié)議層根據(jù)實(shí)現(xiàn)的路由協(xié)議（算法）構(gòu)建和維護(hù)用于分組轉(zhuǎn)發(fā)的路由表分為主干路由器（BackboneRouter，構(gòu)建骨干通訊載體或大型AS的核心網(wǎng)絡(luò)）：側(cè)重轉(zhuǎn)發(fā)邊界路由器（EdgeRouter，連接骨干和周圍網(wǎng)絡(luò)）：側(cè)重過濾載體路由器、企業(yè)路由器、部門路由器、遠(yuǎn)程辦公路由器、軟件路由器等31路由協(xié)議路由協(xié)議使路由器能夠采集和交換路由信息，路由器然后根據(jù)所掌握的路由信息，使用相應(yīng)的路由方式或路由算法，一直努力地構(gòu)建和維護(hù)其用于分組轉(zhuǎn)發(fā)的路由表。典型的IGP路由協(xié)議：RIP、OSPF等典型的EGP路由協(xié)議：EGP、BGP等32RIP路由協(xié)議RIP（RoutingInformationProtocol，路由信息協(xié)議）是一個(gè)簡單的距離向量路由協(xié)議?？梢栽谥鳈C(jī)或路由器中實(shí)現(xiàn)，分為兩種不同的類型的操作方式：被動(dòng)（Passive）方式和主動(dòng)（Active）方式。距離度量為跳段數(shù)（站點(diǎn)計(jì)數(shù)度量），無窮大為16跳段。每隔30秒發(fā)送路由表給鄰居節(jié)點(diǎn)，通過UDP分組發(fā)送。180秒（6*30）沒有收到鄰居節(jié)點(diǎn)來的路由表表示該鄰居節(jié)點(diǎn)不可達(dá)?？梢园l(fā)送Request消息請(qǐng)求鄰居的路由表。每次收到鄰居的路由表信息，就使用前述的Bellman算法更新自己的路由表。處理無窮計(jì)數(shù)問題毒性反轉(zhuǎn)的水平分割抑制觸發(fā)更新33RIP消息格式命令版本必須為0（routedomain）網(wǎng)絡(luò)1的地址家族必須為0（routetag）網(wǎng)絡(luò)1的IP地址必須為0（netmask）必須為0（nexthop）到網(wǎng)絡(luò)1的距離網(wǎng)絡(luò)2的地址家族必須為0網(wǎng)絡(luò)2的IP地址必須為0必須為0到網(wǎng)絡(luò)2的距離…081631UDP520端口每個(gè)消息最長512字節(jié)，可攜帶25個(gè)距離向量RIPv2支持CIDR、認(rèn)證、外部路由和組播紅顏色為RIPv2的消息格式34OSPF路由協(xié)議鏈路狀態(tài)路由協(xié)議OSPF（OpenShortestPathFirst，開放最短路徑優(yōu)先協(xié)議，RFC2328）運(yùn)行在IP之上，協(xié)議號(hào)89支持多種Metric，而不是RIP的HopCount支持變長子網(wǎng)支持多條最短路由間的負(fù)載均衡支持各種路由，允許交換通過其他途徑了解到的路由信息，比如到外部的路由路由消息認(rèn)證支持區(qū)域，引入了層次路由采用組播來傳遞消息244.0.0.5=AllSPFRouters(formDRtoallrouters)244.0.0.6=AllDRouters(fromaroutertoDRandBDR)35OSPF路由協(xié)議支持區(qū)域主干區(qū)域（AreaID=0）和本地區(qū)域區(qū)域間的路由必須通過主干區(qū)域0區(qū)域內(nèi)/區(qū)域間/自治系統(tǒng)