第6章路由算法_第1頁
第6章路由算法_第2頁
第6章路由算法_第3頁
第6章路由算法_第4頁
第6章路由算法_第5頁
已閱讀5頁,還剩45頁未讀 繼續(xù)免費閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)

文檔簡介

1、第第6 6章章 路由算法路由算法uyxwvz2213112535圖: G = (N,E)N = 路由器集合 = u, v, w, x, y, z E = 鏈路集合 = (u,v), (u,x), (v,x), (v,w), (x,w), (x,y), (w,y), (w,z), (y,z) 圖抽象標(biāo)注:圖抽象在其它網(wǎng)絡(luò)上下文中也十分有用例如: P2P, N是peer結(jié)點,E是TCP的連接圖抽象:邊的代價uyxwvz2213112535 c(x,x) = 鏈路的代價 (x,x) - e.g., c(w,z) = 5 代價可能總為, 或者是鏈路帶寬的倒數(shù), 或者是擁塞情況的倒數(shù)Cost of pa

2、th (x1, x2, x3, xp) = c(x1,x2) + c(x2,x3) + + c(xp-1,xp) 問題: 結(jié)點到結(jié)點的最小代價路徑是什么?路由算法:發(fā)現(xiàn)最小代價路徑的算法r路由:按照某種指標(biāo)(傳輸延遲,所經(jīng)過的站點數(shù)目等)找到一條從源結(jié)點到目標(biāo)結(jié)點的較好路徑m較好路徑: 按照某種指標(biāo)較小的路徑r路由算法(routing algorithm):網(wǎng)絡(luò)層軟件的一部分,完成路由功能r路由的時機m虛電路:在建立虛電路時使用(會話路由選擇,session routing)m數(shù)據(jù)報:每個分組獨立路由路由的概念r匯集樹(sink tree)m一個結(jié)點的匯集樹:所有其它結(jié)點到此結(jié)點的最優(yōu)路徑形成

3、的樹m路由算法就是為所有路由器找到并使用匯集樹最優(yōu)化原則(optimality principle)r正確性(correctness):算法必須正確和完整,使分組一站一站接力,正確發(fā)向目的站點r簡單性(simplicity):在計算機上,算法的實現(xiàn)應(yīng)該簡單。最優(yōu)但復(fù)雜的算法,時間延遲很大,不實用,不應(yīng)為了獲取路由信息而增加很多的通信量r健壯性(robustness):算法應(yīng)適應(yīng)通信量和網(wǎng)絡(luò)拓撲的變化,不向很擁擠的鏈路發(fā)送數(shù)據(jù),不向中斷的鏈路發(fā)送數(shù)據(jù)r穩(wěn)定性(stability):產(chǎn)生的路由不應(yīng)該搖擺r公平性(fairness):對每一個站點都公平r最優(yōu)性(optimality):某一個指標(biāo)的最

4、優(yōu)(時間、費用或綜合指標(biāo))。實際上,獲取最優(yōu)的結(jié)果代價較高,可以選擇次優(yōu)的結(jié)果路由算法的原則路由算法的分類自適應(yīng)或者非自適應(yīng)自適應(yīng)或者非自適應(yīng)? ?r非自適應(yīng)算法(non-adaptive algorithm):不能適應(yīng)網(wǎng)絡(luò)拓撲和通信量的變化,路由表是事先計算好的,也叫靜態(tài)路由算法和非自適應(yīng)路由算法r自適應(yīng)算法(adaptive algorithm):能適應(yīng)網(wǎng)絡(luò)拓撲和通信量的變化,也叫動態(tài)路由算法和自適應(yīng)路由算法r固定路由算法(fixed routing algorithm)r洪泛法(flooding)r隨機走動法(random walk)r基于流量的路由算法(flow-based routi

5、ng)非自適應(yīng)路由算法r每個網(wǎng)絡(luò)結(jié)點存儲一張表格,表格的每一項記錄到達某個目的結(jié)點的下一結(jié)點或鏈路,而不是記錄到該目的結(jié)點的所有中間結(jié)點r優(yōu)點:簡單,適合一個負載穩(wěn)定和拓撲變化不大的網(wǎng)絡(luò)r缺點:靈活性較差,無法對網(wǎng)絡(luò)的擁塞和故障作出反應(yīng)固定路由算法r結(jié)點收到不是發(fā)給它的分組時,就將該分組的副本向除輸入鏈路之外的所有與此結(jié)點相連的鏈路轉(zhuǎn)發(fā)出去r當(dāng)網(wǎng)絡(luò)的通信量很小時,該方法使分組的時延為最小,因為在并行發(fā)送的路由中,肯定有一條為最佳r該方法的缺點是網(wǎng)絡(luò)中的分組數(shù)目會迅速增加,導(dǎo)致網(wǎng)絡(luò)出現(xiàn)擁塞現(xiàn)象,應(yīng)用并不廣泛r該方法可用于健壯性要求很高的地方,如軍事網(wǎng)絡(luò)洪泛法r隨即徘徊法r當(dāng)分組到達某個結(jié)點時,隨

6、機選擇一條鏈路作為轉(zhuǎn)發(fā)的路由;當(dāng)某結(jié)點的輸出鏈路有3條時,就以平均概率0.33選擇任一條鏈路作為轉(zhuǎn)發(fā)路由r當(dāng)結(jié)點或鏈路發(fā)生故障時,該方法可使路由算法有較好的穩(wěn)健性隨機走動法r該方法不僅考慮網(wǎng)絡(luò)的拓撲結(jié)構(gòu),還要考慮網(wǎng)絡(luò)的負載因素r對某一給定的線路,如果已知負載量與平均流量,那么可以根據(jù)排隊論的知識計算出該線路上的平均分組延遲r由所有的線路平均延遲,可直接計算出流量的加權(quán)平均值,從而得到整個網(wǎng)絡(luò)的平均分組延遲r這樣找出網(wǎng)絡(luò)的最小平均延遲就可以實現(xiàn)最優(yōu)路由選擇基于流量的路由算法r孤立路由選擇r集中路由選擇r分布式路由選擇自適應(yīng)路由算法r每個結(jié)點并不利用其它結(jié)點來的網(wǎng)絡(luò)信息,僅僅根據(jù)它自己所看到的情況

7、來確定路由m最短等待法m逆向?qū)W習(xí)算法孤立路由選擇r根據(jù)所有結(jié)點的網(wǎng)絡(luò)信息來選擇路由r網(wǎng)絡(luò)中設(shè)置了一個路由控制中心r每隔一段時間,每個結(jié)點向路由控制中心發(fā)送狀態(tài)信息,如鏈路連接情況、流量和隊列長度等r路由控制中心收集所有這些信息,然后根據(jù)它對整個網(wǎng)絡(luò)的全局性了解,利用這些信息使用最短路徑算法計算出每對結(jié)點之間的最佳路徑,構(gòu)造出路由表分發(fā)給對應(yīng)的每個結(jié)點r缺點:計算量大和路由控制中心的脆弱性集中路由選擇r根據(jù)來自于相鄰結(jié)點的信息,通過一個最短花費路由算法計算出到每個目的地的路由r分布式路由算法得到了廣泛使用r目前最流行的兩個分布式路由算法m距離矢量路由算法(distance vector rout

8、ing) 局部:路由器只知道與它有物理連接關(guān)系的鄰居路由器和到該路由器的代價m鏈路狀態(tài)路由算法(link state routing) 全局:所有的路由器擁有完整的拓撲和邊的代價的信息分布式路由選擇r歷史及應(yīng)用情況m由Bellman、Ford和Fulkerson等提出m用于ARPANET, Internet和Novellr基本思想m每個結(jié)點都保存一張到目的地的路由表 到目的地的下一結(jié)點 測量出到目的地的度量值(metric):初始化時,直接連接的目的地置為0(表示無需經(jīng)過別的路由器),其它置為m每個結(jié)點把它的路由表定期向它直接連接的相鄰結(jié)點傳遞距離矢量路由算法m當(dāng)結(jié)點K從結(jié)點J接收一個更新消息

9、后,它對到每個目的地的路由和距離度量進行檢查 如果J知道一條到目的地的更短的路徑,結(jié)點K更新該目的地對應(yīng)的下一結(jié)點標(biāo)識和距離度量 如果J列出了一個K還沒有記錄的某個目的地的路徑,結(jié)點K會向表中增加一項 如果K記錄的下一結(jié)點標(biāo)識為J,并且J所報告的到目的地的距離改變了,也會更新路由表中的距離度量距離矢量路由算法r算法表示m初始化。對于每個結(jié)點G,對所有它直接連接的目的地N,路由表中的表項用三元組(N,G,0)來表示,即從結(jié)點G到目的地N無需經(jīng)過轉(zhuǎn)發(fā)m結(jié)點G定期發(fā)送它的路由表給相鄰結(jié)點。更新信息中對應(yīng)著每一個目的地N用一個三元組來表示(N,V,D),即到目的地N的路由上的下一結(jié)點為V,G到N的距離

10、為D距離矢量路由算法m結(jié)點G收到G送來的路由信息,對于更新信息中給出的每個目的地,在G的路由表中查找相對應(yīng)的表項,設(shè)它為(N,V,D),而更新信息中的三元組為(N,V,D),C為結(jié)點G和G之間的距離 如果找不到相應(yīng)的表項,在G的路由表中增加一項:(N,G,D+C) 如果V=G,G中路由表對應(yīng)的表項根據(jù)D+C和D的比較獲得如果D+CD,G中表項更新為(N,G,D+C)否則G中表項保持原狀,仍為(N,V,D)距離矢量路由算法正確的算法r如果找不到相應(yīng)的表項,在G的路由表中增加一項:(N,G,D+C) r 如果V=G,G中路由表對應(yīng)的表項根據(jù)D+C和D的比較獲得r如果D+CD,G中表項更新為(N,G

11、,D+C)r否則G中表項保持原狀,仍為(N,V,D)r 改為:r 如果找不到相應(yīng)的表項,在G的路由表中增加一項:(N,G,D+C) r 如果V=G,那么無條件的把G中的項目更新為G中的(N,G,D+C)。r 如果VG,G中路由表對應(yīng)的表項根據(jù)D+C和D的比較獲得r如果D+CD,G中表項更新為(N,G,D+C)r否則G中表項保持原狀,仍為(N,V,D)r該改為:如果V=G,那么無條件的把G中的項目更新為G。理由是:要以最新消息為準(zhǔn)。見謝希仁第五版計算機網(wǎng)絡(luò)148頁距離矢量路由算法距離矢量路由算法路由器1的更新前的路由表路由器2發(fā)給路由器1的報文路由器1的更新后的路由表rDV的無窮計算問題mDV的

12、特點 好消息傳的快 壞消息傳的慢m好消息的傳播以每一個交換周期前進一個路由器的速度進行 好消息:某個路由器接入或有更短的路徑 舉例距離矢量路由算法rDV的無窮計算問題m壞消息的傳播速度非常慢(無窮計算問題)m例子 第一次交換之后, B從C處獲得信息,C可以到達A(C-A,要經(jīng)過B本身),但是路徑是2,因此B變成3,從C處走 第二次交換,C從B處獲得消息, B可以到達A,路徑為3。 因此,C到A從B走,代價為4 無限此之后, 到A的距離變成INF,不可達距離矢量路由算法rLS的背景mDV的問題 代價沒有考慮線路帶寬因素,認為所有線路帶寬一樣 慢速收斂問題(無窮計算問題)m1979年后ARPANE

13、T的路由算法都轉(zhuǎn)為LSrLS的基本工作過程m發(fā)現(xiàn)相鄰結(jié)點,獲知對方網(wǎng)絡(luò)地址m測量到相鄰結(jié)點的的代價(延遲或開銷)m組裝一個LS分組,描述它到相鄰結(jié)點的代價情況m將分組通過擴散的方法發(fā)到所有其它路由器1.通過Dijkstra算法找出最短路徑鏈路狀態(tài)路由算法q發(fā)現(xiàn)相鄰結(jié)點,獲知對方網(wǎng)絡(luò)地址m一個路由器加電之后,向所有線路發(fā)送HELLO分組m其它路由器收到HELLO分組,回送應(yīng)答,在應(yīng)答分組中告知自己的全局唯一的名字m在LAN中,通過廣播HELLO分組,獲得其它路由器的信息鏈路狀態(tài)路由算法q測量到相鄰結(jié)點的代價(延遲或開銷)m實測法,發(fā)送一個分組要求對方立即響應(yīng)m回送一個ECHO分組m通過測量時間可

14、以估算出延遲情況q組裝一個分組,描述相鄰結(jié)點的情況m發(fā)送者名稱m序號,年齡m列表: 給出它相鄰結(jié)點,和它到相鄰結(jié)點的延遲鏈路狀態(tài)路由算法q將分組通過擴展的方法發(fā)到所有其它路由器m順序號:用于控制無窮的擴散,每個路由器都記錄(源路由器,順序號),發(fā)現(xiàn)重復(fù)的或老的就不擴散 具體問題1: 循環(huán)使用問題 具體問題2: 路由器崩潰之后序號從0開始 具體問題3:序號出現(xiàn)錯誤m解決問題的辦法:年齡字段(age) 生成一個分組時,年齡字段不為0 每過一個時間段,AGE字段減1 AGE字段為0的分組將被拋棄鏈路狀態(tài)路由算法q通過Dijkstra算法找出最短路徑m路由器獲得各站點LS分組和整個網(wǎng)絡(luò)的拓撲m通過Di

15、jkstra算法計算出到其它各路由器的最短路徑(匯集樹)m將計算結(jié)果記錄到路由表中rLS的應(yīng)用情況mOSPF協(xié)議,用于Internet上鏈路狀態(tài)路由算法r計算路由時,一般使用Dijkstra(迪杰斯特拉)算法rDijkstra算法為每條邊賦予一個非負的權(quán)值,以兩結(jié)點間路徑權(quán)值的和作為該路徑的距離r在網(wǎng)絡(luò)中,每個結(jié)點都要用Dijkstra算法計算出到其它各結(jié)點的最短路徑,從而構(gòu)造出該結(jié)點的路由表 最短路徑算法1543262213112535rDijkstra算法首先建立一個除源點外的所有結(jié)點的集合S,集合S保存尚未被刪除的結(jié)點rDijkstra算法使用兩個數(shù)組D和R,每個結(jié)點在這兩個數(shù)組中都各有

16、一項m數(shù)組D的第i項存儲從源點到結(jié)點i的最短距離m數(shù)組R的第i項存儲從源點到結(jié)點i路徑上的下一站r用Weight(i,j)作為從結(jié)點i到結(jié)點j的權(quán)值,如果從結(jié)點i到結(jié)點j沒有邊,則權(quán)值為無窮大() 最短路徑算法r隨后,開始循環(huán)m每次都從S中刪除一個與源點之間有最短路徑的結(jié)點u,然后檢查從源點到仍然在S中并與u相鄰的每個結(jié)點的距離m如果從源點通過u到某結(jié)點的權(quán)值之和,比此前源點到該結(jié)點的最短距離小,則更新該值r當(dāng)所有結(jié)點都從S中刪除后,就能計算出到每個結(jié)點的最短距離,同時也構(gòu)造出路由表 最短路徑算法具體算法具體算法初始化集合S,為除源點外的所有結(jié)點。初始化數(shù)組D,如果從源點到v有邊存在,則D(v

17、)為該邊的權(quán)值,否則為無窮大。初始化數(shù)組R,如果從源點到v有邊存在,則R(v)=v,否則為0。While(集合S非空) 從S中選一結(jié)點u,使D(u)最??; 如果 D(u)無窮大錯誤,S中無路徑存在,退出 把u從S中刪除; 最短路徑算法 對(u,v)為邊的每個結(jié)點v 如果(v仍在S中) C= D(u)+ Weight(u,v); 如果(C D(u) R(v)=R(u); D(v)=C+1; 最短路徑算法r用Dijkstra算法,計算從源點1到其它每個結(jié)點的最短距離和下一站路由表 最短路徑算法1543262213112535初始化:S=2,3,4,5,6數(shù)組D(1到其它每個結(jié)點的最短距離)數(shù)組R(

18、1到其它每個結(jié)點的下一站路由表) 最短路徑算法1543262213112535123456-251123456-23400 最短路徑算法 最短路徑算法 最短路徑算法鏈路狀態(tài)路由算法OSPF Development History1987198919911993199519971999OSPF Group formedOSPFv1 published RFC 1131OSPFv2 published RFC 1247Becomes recommendedCryptographic authenticationPoint-to-multipoint interfacesMOSPFOSPFv2 up

19、date RFC 1583CIDROSPFv2 update RFC 2178OSPFv2 update RFC 2328OSPFv3 RFC 2740消息復(fù)雜度消息復(fù)雜度rLS: 有 n 結(jié)點, E 條鏈路,發(fā)送報文O(nE)個 rDV: 只和鄰居交換信息收斂時間收斂時間rLS: O(n2), 算法需要O(nE)報文m有可能震蕩rDV: 收斂時間變化m可能存在路由環(huán)路mcount-to-infinity 問題健壯性健壯性: 路由器發(fā)生故障會出現(xiàn)什么?LS: m結(jié)點會通告不正確的鏈路代價DV:mDV 結(jié)點可能通告不正確的路徑代價m每一個結(jié)點的路由表可能被其它結(jié)點使用LS 和 DV 算法的比較層

20、次性路由規(guī)模:有200M個目的主機r不可能在路由表中存儲全部的目的地r路由器的路由表交換會淹沒鏈路 自治管理rinternet =網(wǎng)間網(wǎng)r每一個網(wǎng)絡(luò)管理員可能希望控制自己網(wǎng)絡(luò)內(nèi)部的路由我們前面講的路由算法都比較理想化r所有的路由器都是一樣的 r網(wǎng)絡(luò)是平面的 實際的網(wǎng)絡(luò)不是這樣的r某個區(qū)域內(nèi)的路由器集合,自治系統(tǒng)“autonomous systems” (AS)r在同一個AS內(nèi)的路由器運行相同的路由協(xié)議m“intra-AS” routing protocol內(nèi)部網(wǎng)關(guān)協(xié)議m不同AS的路由器可能運行著不同的內(nèi)部網(wǎng)關(guān)協(xié)議網(wǎng)關(guān)路由器r直接和其它AS的路由器有直接的鏈路相連層次性路由3b1d3a1c2aA

21、S3AS1AS21a2c2b1bIntra-ASRouting algorithmInter-ASRouting algorithmForwardingtable3cr轉(zhuǎn)發(fā)表由AS內(nèi)部和AS間路由算法配置mIntra-AS 設(shè)置AS內(nèi)部的目標(biāo)網(wǎng)絡(luò)mInter-AS & Intra-As 設(shè)置AS外部目標(biāo)網(wǎng)絡(luò)層次性路由3b1d3a1c2aAS3AS1AS21a2c2b1b3cInter-AS 任務(wù)r假設(shè)AS1 中的路由器收到了一個目標(biāo)地址是AS1 外部的數(shù)據(jù)報m路由器應(yīng)該將它轉(zhuǎn)發(fā)到其中的一個gateway routers中,但是是哪一個?AS1 需要:r獲知哪一個目標(biāo)可以通過AS2 到達,哪一個可以通過AS3 到達r將這種可達性信息傳播到AS1中的每一個路由器中inter-AS路由的工作!Intra-AS and Inter-AS routingGateways:perform inter-AS routing amongst themselvesperform intra-AS routers with other routers in their ASinter-AS, intra-AS routing in gateway A.cn

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論