第6章路由算法

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é)點(diǎn)，E是TCP的連接圖抽象：邊的代價(jià)uyxwvz2213112535 c(x,x) = 鏈路的代價(jià) (x,x) - e.g., c(w,z) = 5 代價(jià)可能總為, 或者是鏈路帶寬的倒數(shù), 或者是擁塞情況的倒數(shù)Cost of pa

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

18、1到其它每個(gè)結(jié)點(diǎn)的下一站路由表） 最短路徑算法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é)點(diǎn)， E 條鏈路，發(fā)送報(bào)文O(nE)個(gè) rDV: 只和鄰居交換信息收斂時(shí)間收斂時(shí)間rLS: O(n2)， 算法需要O(nE)報(bào)文m有可能震蕩rDV: 收斂時(shí)間變化m可能存在路由環(huán)路mcount-to-infinity 問題健壯性健壯性: 路由器發(fā)生故障會(huì)出現(xiàn)什么?LS: m結(jié)點(diǎn)會(huì)通告不正確的鏈路代價(jià)DV:mDV 結(jié)點(diǎn)可能通告不正確的路徑代價(jià)m每一個(gè)結(jié)點(diǎn)的路由表可能被其它結(jié)點(diǎn)使用LS 和 DV 算法的比較層

20、次性路由規(guī)模:有200M個(gè)目的主機(jī)r不可能在路由表中存儲(chǔ)全部的目的地r路由器的路由表交換會(huì)淹沒鏈路 自治管理rinternet =網(wǎng)間網(wǎng)r每一個(gè)網(wǎng)絡(luò)管理員可能希望控制自己網(wǎng)絡(luò)內(nèi)部的路由我們前面講的路由算法都比較理想化r所有的路由器都是一樣的 r網(wǎng)絡(luò)是平面的 實(shí)際的網(wǎng)絡(luò)不是這樣的r某個(gè)區(qū)域內(nèi)的路由器集合，自治系統(tǒng)“autonomous systems” (AS)r在同一個(gè)AS內(nèi)的路由器運(yùn)行相同的路由協(xié)議m“intra-AS” routing protocol內(nèi)部網(wǎng)關(guān)協(xié)議m不同AS的路由器可能運(yùn)行著不同的內(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 中的路由器收到了一個(gè)目標(biāo)地址是AS1 外部的數(shù)據(jù)報(bào)m路由器應(yīng)該將它轉(zhuǎn)發(fā)到其中的一個(gè)gateway routers中，但是是哪一個(gè)？AS1 需要:r獲知哪一個(gè)目標(biāo)可以通過AS2 到達(dá)，哪一個(gè)可以通過AS3 到達(dá)r將這種可達(dá)性信息傳播到AS1中的每一個(gè)路由器中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