北京大學(xué)計(jì)算機(jī)網(wǎng)絡(luò)路由選擇及算法

1、 第十講計(jì)算機(jī)網(wǎng)絡(luò)路由選擇及算法 路由選擇算法Array主要內(nèi)容路由基本概念靜態(tài)路由算法距離矢量算法鏈路狀態(tài)算法閱讀 路由選擇概述 路由器的內(nèi)部結(jié)構(gòu) 路由選擇算法 路由算法的分類 非自適應(yīng)算法 不根據(jù)實(shí)測或估計(jì)的網(wǎng)絡(luò)的當(dāng)前通信量和拓?fù)浣Y(jié)構(gòu)來作路由選擇。 自適應(yīng)算法根據(jù)拓?fù)浣Y(jié)構(gòu)、通信量的變化來改變其路由選擇。 9可提高網(wǎng)絡(luò)性能 有助于擁塞控制路由決策復(fù)雜依賴于狀態(tài)信息 不能太快和太慢路由算法的設(shè)計(jì)目標(biāo)對隨時出現(xiàn)的局部網(wǎng)絡(luò)故障和負(fù)載變化迅速作出反映,理想情況下不丟失包和中斷虛電路。 不管運(yùn)行多長時間始終穩(wěn)定; 在路由變化期間包可能循環(huán)通過網(wǎng)絡(luò),要解決; 路由處理和傳輸?shù)拈_銷應(yīng)小于基于某種度量獲得的

2、好處。 10正確性(correctness 簡單性(simplicity 健壯性穩(wěn)定性最優(yōu)性(optimality 公平性(fairness 有效性(efficiency路由技術(shù)元素 11 路由性能標(biāo)準(zhǔn) 12 目標(biāo)端13 節(jié)點(diǎn)1到節(jié)點(diǎn)6的最短路經(jīng)是1-3-6,路徑長為10;節(jié)點(diǎn)1到節(jié)點(diǎn)6的最小成本路徑是1-4-5-6,路徑成本4;14 路由決策時間與地點(diǎn)決策時間內(nèi)部數(shù)據(jù)報:為每個包單獨(dú)作路由決策內(nèi)部虛電路:當(dāng)建立虛電路時作路由決策決策地點(diǎn)分布式路由每個節(jié)點(diǎn)都負(fù)責(zé)為到達(dá)的包選擇一條輸出鏈路集中式路由15 由某些指定節(jié)點(diǎn)(如網(wǎng)絡(luò)控制中心負(fù)責(zé)決策源路由路由決策由源站點(diǎn)而非網(wǎng)絡(luò)作出16網(wǎng)絡(luò)信息源和更新

3、時間 路由信息需求 無信息(擴(kuò)散法 局部信息其他信息源(鄰接節(jié)點(diǎn),全部節(jié)點(diǎn) 從不更新信息 固定策略不時更新信息自適應(yīng)策略靜態(tài)路由算法最短路徑選擇測量路徑長度的方法 最小跳計(jì)數(shù) 最短距離 信道帶寬 傳輸延遲 平均通信量 Dijkstra子網(wǎng)圖節(jié)點(diǎn)代表路由器 弧線代表兩個路由器之間的一條鏈路 初試化測量每一條鏈路的長度 選擇當(dāng)前工作節(jié)點(diǎn)A(, -標(biāo)值其他節(jié)點(diǎn)到源的距離Dijkstra 算法迭代(1/3 選擇當(dāng)前工作節(jié)點(diǎn)E(, - 標(biāo)值其他節(jié)點(diǎn)到 選擇當(dāng)前工作節(jié)點(diǎn) B標(biāo)值其他節(jié)點(diǎn)到 源的距離 Dijkstra算法迭代(2/3 (, - 標(biāo)值其他節(jié)點(diǎn)到源的距離 選擇當(dāng)前工作節(jié)點(diǎn) G標(biāo)值其他節(jié)點(diǎn)到源的距

4、離 選擇當(dāng)前工作節(jié)點(diǎn) F( , - Dijkstra算法迭代(3/3選擇當(dāng)前工作節(jié)點(diǎn)H 標(biāo)值其他節(jié)點(diǎn)到源的距離選擇當(dāng)前工作節(jié)點(diǎn)C 標(biāo)值其他節(jié)點(diǎn)到源的距離 (10, H 從目標(biāo)節(jié)點(diǎn)倒著往前推即可獲得從源節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的一條最短路徑。 (10 , H 擴(kuò)散法(flooding 擴(kuò)散法的特性優(yōu)點(diǎn)嘗試所有可能路由至少有一個包通過最小跳路由到達(dá)所有與源節(jié)點(diǎn)連接的節(jié)點(diǎn)都被訪問健壯性 建立虛電路廣播重要信息 每個節(jié)點(diǎn)接收來自與其直接鄰接節(jié)點(diǎn)的路由信息執(zhí)行路由計(jì)算 將計(jì)算結(jié)果回傳給直接鄰接的節(jié)點(diǎn)迭代的(iterative計(jì)算過程循環(huán)進(jìn)行直到相鄰節(jié)點(diǎn)沒有可交換的路由信息為止異步的(asynchronous 并不

5、要求所有節(jié)點(diǎn)相互鎖步操作距離矢量算法距離 其中w 為Z 的所有直接鄰居(包括X考慮X 經(jīng)直接鄰居Z 到達(dá)Y 距離矢量算法距離矩陣 D E ( A ,D = c(E,D +D D ( A , w = 2+3 = 5 距離矢量算法的數(shù)據(jù)結(jié)構(gòu)主要數(shù)據(jù)結(jié)構(gòu)每個節(jié)點(diǎn)維護(hù)的距離表(distance table。一個節(jié)點(diǎn)能得到的信息與其直接相連鏈路的成本Array來自鄰接節(jié)點(diǎn)的路由信息DV算法用估算延遲作為性能指標(biāo)基于Bellman-Ford算法 2 for all adjacentnodes v:3 D X(*, v = 4 D X(v, v = c(X, v5 for all destinations,

6、y 表中到鄰居的距離設(shè)置成鏈路成本; 把距離表中到非鄰居的距離設(shè)置成無窮大; 把到所有目的地的距離信息發(fā)給每個鄰居6 send min w D(y, w to each neighbor/* w over all X's neighbors */78 loop9 wait (until I see a link cost change to neighbor v10 or until I receive update from neighbor v 11 12 if (c(X,v changesby d X到鄰居v的距離發(fā)生變化d13 /* change cost to all des

7、t's vianeighbor v by d */14 /* note:d could be positiveor negative */15 for all destinations y: D X(y,v = D X(y, v + d16 17 else if (update received fromv wrt destination y35 18 /* shortest path fromv to some y haschanged */19 /* v has sent a new value forits min w D V(y,w */ 20 /* callthis rece

8、ived new value is"newval" */21 for the single destination y:D X(y, v = c(X, v + newval22 23 if we have a new min w D X(y, wfor any destination y24 send new value of min wD X(y,w to all neighbors36 25 26 forever 最左列為x, y, z初始化后的距離表37 X收到來自y, z的更新信息后,重新計(jì)算距離表收到Z的消息后 收到y(tǒng)的消息后 X計(jì)算出D x(z,y=3需要通知鄰

9、居 38 39 鏈路成本變化對算法的影響 X YXD Z 550 X ZX DY4 6X ZX DY1 6X ZXDY31 假設(shè) x y 鏈路的成 本由 4 下降為 1 無窮計(jì)算問題 假設(shè) x y 鏈路的成 本由 4 上升為 60 C(X, Ychangedtime t0 t1t2 t3 t4Y的距離表Y 的距離表 X Z X DY 4 X Y X DZ50 5C(X, Ychanged timet0t1t2 t3 t4 50 Z的距離表 X Z X DY 4 -X YX D Z 550 染毒反向法的局限 A 通知C 到D 的距離為;B 通知C 到D 的距離為; 當(dāng)C-D 鏈路失效后,C 到D

10、 不可達(dá); A 選擇經(jīng)過B 到D 且距離為3 C C 選擇經(jīng)過A到D且距離為4 B B選擇經(jīng)過C到D且距離為5 A鏈路狀態(tài)路由算法(LS LS算法特性每個節(jié)點(diǎn)都有網(wǎng)絡(luò)的完整拓?fù)?每個節(jié)點(diǎn)維護(hù)到每個鄰居的連通性與鏈路成本;例如:節(jié)點(diǎn)每10秒計(jì)算每條出境鏈路的平均延遲節(jié)點(diǎn)向網(wǎng)絡(luò)中所有其他節(jié)點(diǎn)廣播自己和鄰居的連接信息;每當(dāng)接收到來自其他節(jié)點(diǎn)的信息時用Dijkstra算法重新計(jì)算路由表;通常采用延遲作為性能標(biāo)準(zhǔn);能消除慢速收斂的問題; LS路由算法方法延遲計(jì)算方法(在每個節(jié)點(diǎn)發(fā)出去的包被蓋上時間戳,記錄其離開時間;收到返回的肯定確認(rèn)時,計(jì)算該包的延遲;收到返回的否定確認(rèn)時,更新包的離開時間; Dijk

11、stra 算法計(jì)算從一個節(jié)點(diǎn)(源,假設(shè)為A到網(wǎng)絡(luò)中所有其他節(jié)點(diǎn)的最小成本路徑。算法迭代進(jìn)行;經(jīng)第k次迭代后,就能找到到k個目標(biāo)節(jié)點(diǎn)的最小成本路徑。 1 Initialization:2 N = A3 for all nodes v4 if v adjacent to A5 then D(v = c(A,v6 else D(v = 78 Loop :將到A的鄰居的距離標(biāo)記為鏈路成本;9 find w not in N such that D(w is a minimum10 add w to N選擇距離值最小的w,更11 update D(v for all v not in N:新所有w鄰居的距離值。 12 D(v = min( D(v, D(w + c(w,v 13 /* new cost to v is either old cost to v or known14 shortest path cost to w plus cost from w to v */15 until all nodes in NLS算法初始化假設(shè)C(i,j:從節(jié)點(diǎn)i到j(luò)的成本D(v:從源節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)v的當(dāng)前最小成本48 P(