計(jì)算機(jī)網(wǎng)絡(luò),路由原理

1、路由原理1第六章 路由原理概述路由原理2Internet是一個(gè)巨型復(fù)雜系統(tǒng)。過(guò)去認(rèn)為它的拓?fù)浣Y(jié)構(gòu)是一個(gè)隨機(jī)網(wǎng)絡(luò)。后來(lái)測(cè)試結(jié)果發(fā)現(xiàn)與隨機(jī)網(wǎng)絡(luò)預(yù)測(cè)不符，而是一個(gè)無(wú)尺度網(wǎng)絡(luò)。隨機(jī)網(wǎng)絡(luò)隨機(jī)網(wǎng)絡(luò)節(jié)點(diǎn)的連接數(shù)是隨機(jī)分布的無(wú)尺度網(wǎng)絡(luò)無(wú)尺度網(wǎng)絡(luò)(Scale free)少數(shù)節(jié)點(diǎn)具有很高連接數(shù)(集散節(jié)點(diǎn))連接分布遵循“冪次定律” 任何節(jié)點(diǎn)與其它k個(gè)節(jié)點(diǎn)連接概率，與1/k成正比(無(wú)尺度特性) 可承受意外故障，無(wú)法抗拒協(xié)同式攻擊 事例 萬(wàn)維網(wǎng)、細(xì)胞代謝、語(yǔ)言、人際關(guān)系路由原理36.1 概述 在網(wǎng)絡(luò)上選擇一條從源到目的節(jié)點(diǎn)的通路 若干中繼節(jié)點(diǎn)和鏈路組成的一條路：路徑 L2、L3的中繼都有選路要求 L2中繼選路：依據(jù)鏈路

2、連接 L3中繼選路：依據(jù)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)RouteRoutingRouted如何選路如何中繼路由原理4L2選路 站點(diǎn)在鏈路上 鏈路在中繼可以產(chǎn)生多條支路 每個(gè)站點(diǎn)只能連接到一個(gè)鏈路上 選路的依據(jù)是站點(diǎn)在鏈路上的位置 鏈路的拓?fù)涫呛?jiǎn)單的或樹(shù)狀結(jié)構(gòu) 到任一站點(diǎn)只有唯一的一條路 L2的選路方式是簡(jiǎn)單的 根據(jù)鏈路的方向選路路由原理5L3選路 站點(diǎn)在某個(gè)網(wǎng)關(guān)處 多個(gè)網(wǎng)關(guān)構(gòu)成的網(wǎng)狀拓?fù)浣Y(jié)構(gòu) 站點(diǎn)連接到某個(gè)網(wǎng)關(guān)上（通過(guò)鏈路連接） 選路的依據(jù)是站點(diǎn)所處的網(wǎng)關(guān)位置 拓?fù)浣Y(jié)構(gòu)是復(fù)雜的網(wǎng)狀拓?fù)浣Y(jié)構(gòu) 到某個(gè)站點(diǎn)有多條路存在 L3的選路是復(fù)雜的 按照一定準(zhǔn)則，從多條路中選出一條最佳路由路由原理6選路的有關(guān)問(wèn)題選路與路由 網(wǎng)

3、狀拓?fù)浣Y(jié)構(gòu)中的選路問(wèn)題 以網(wǎng)關(guān)為節(jié)點(diǎn)、鏈路為線條的網(wǎng)狀拓?fù)?確定網(wǎng)狀結(jié)構(gòu)中所有節(jié)點(diǎn)對(duì)間的路徑 不是確定某個(gè)特定的通信路徑【選路】 而是確定所有可能的通信路徑【路由】 在所有節(jié)點(diǎn)對(duì)的多條路徑中選擇合理的路徑 路由：全局性的選路方法路由原理7多條路由 節(jié)點(diǎn)對(duì)（i，j）間存在多條路徑 i，j1,6 ij （i，j）的路徑與（j，i）的路徑不一定相同 （i，j）看成一對(duì)序偶 N個(gè)節(jié)點(diǎn)，就得考慮N（N1）條路由213456(1,6)的可能路徑：1-2-4-61-3-5-61-3-4-61-4-61-2-3-4-6需從所有可能的路徑中確定： 6530條路徑路由原理8選路的有關(guān)問(wèn)題算法與協(xié)議 每對(duì)節(jié)點(diǎn)間可能

4、存在多條路徑 各條路徑的通信性質(zhì) 信道速率、時(shí)延、費(fèi)用 路徑的優(yōu)選【“最佳”路由算法】 “最佳”的準(zhǔn)則，因應(yīng)用不同而異（或曰“人為因素”） 全局路徑達(dá)到最佳準(zhǔn)則和算法（局部也許不太合理） 最佳路徑隨拓?fù)?、通信狀況改變而動(dòng)態(tài)變化 算法與協(xié)議 所有網(wǎng)關(guān)都參與，把握全局性的選路信息 集中或分布(或其它方式)的選路算法【路由算法】 統(tǒng)一選路規(guī)則、網(wǎng)關(guān)的協(xié)作【路由協(xié)議】路由原理9最優(yōu)路由選擇 路徑的全程傳輸容量 路徑的長(zhǎng)度（距離） 路徑的費(fèi)用213456c1c2c3c4c5c6c7c8c9c10節(jié)點(diǎn)的流量、線路容量直接影響到路徑的容量和時(shí)延線路的故障、節(jié)點(diǎn)的故障可能影響到路徑的可用性費(fèi)用：c1+c2+c

5、8 或 c1+c4+c10路由原理10選路的有關(guān)問(wèn)題路由體系 多種路由算法和協(xié)議客觀存在 不同網(wǎng)絡(luò)的通信需求不同，路由策略和準(zhǔn)則不同 大型網(wǎng)絡(luò)不可能只用一種路由協(xié)議 路由體系結(jié)構(gòu) 小網(wǎng)中的路由、網(wǎng)狀網(wǎng)的路由、大型網(wǎng)的路由 網(wǎng)絡(luò)權(quán)屬機(jī)構(gòu)的管理和路由策略 權(quán)屬網(wǎng)絡(luò)間的路由 多層次的路由路由原理11路由體系 多層次的路由 不同的小網(wǎng)可有不同的路由算法和協(xié)議 不同的網(wǎng)狀網(wǎng)可有不同的路由算法和協(xié)議 多種不同權(quán)屬網(wǎng)絡(luò)的有不同的路由策略域1域2域3域4小網(wǎng)路由網(wǎng)狀網(wǎng)路由大型、不同權(quán)屬網(wǎng)絡(luò)間的路由路由原理12本章內(nèi)容 本章只討論L3選路問(wèn)題 選路基本方法 路由協(xié)議（算法） 路由體系結(jié)構(gòu)路由原理136.2 選路

6、基本方法路由問(wèn)題： 源到目的節(jié)點(diǎn)之間節(jié)點(diǎn)和線路組成的通路 任意一對(duì)節(jié)點(diǎn)間都可能存在多條路經(jīng) 從所有路徑中計(jì)算出每對(duì)節(jié)點(diǎn)間的最佳路由 什么是最佳路由？ 如何計(jì)算？1到6的可能路徑：1-2-4-61-3-5-61-3-4-61-4-61-2-3-4-612354613232211331142856385路由原理146.2.1 最佳路由記：Lx為一條經(jīng)過(guò)節(jié)點(diǎn)ax,0,ax,1,ax,n的路徑， Cx(a,b)為節(jié)點(diǎn)對(duì)(a,b)的“距離” C(Lx)為路徑Lx的總距離，且： C(Lx) = Cx (ax,i,ax,i+1)假定節(jié)點(diǎn)a，b之間存在k條路徑L1, Lk,則最佳路徑為其中的一條，滿足:Lm

7、Lx: C(Lx) = min C(L1), C(Lk)經(jīng)典最短距離算法：Dijkstra（1959）路由原理15“距離”的解釋 C(a,b)的意義 若C(a,b)=1，則最佳路徑為經(jīng)過(guò)的節(jié)點(diǎn)數(shù)最少 若C(a,b)=dt (節(jié)點(diǎn)a的中繼時(shí)延傳輸時(shí)延),則最佳路徑為最小傳輸時(shí)延的路徑 若C(a,b)為節(jié)點(diǎn)a,b間鏈路上傳輸?shù)馁M(fèi)用，則最佳路徑為最小費(fèi)用的路徑 若C(a,b)=1/鏈路容量, 則最佳路徑是一條最大傳輸容量的路徑(不嚴(yán)格) 若C(a,b)=鏈路使用率，則最佳路徑是一條最空閑的路徑(不嚴(yán)格)路由原理16路由算法 C(a,b)的不同含義，意味著不同的“最佳”選路 C(a,b)可以是距離、時(shí)

8、延、容量、費(fèi)用等的函數(shù)的加權(quán)組合 實(shí)際中，各種因素的量綱不同，沒(méi)有一種方法能兼顧所有的因素。路由原理17路由算法 跳數(shù) 費(fèi)用 時(shí)延 吞吐量 最短路徑路由算法：路徑上的節(jié)點(diǎn)數(shù)最少 最小費(fèi)用路由算法 最大吞吐量路由算法 最小時(shí)延路由算法12354613232211331142856385路由原理18網(wǎng)絡(luò)流量過(guò)于集中，超過(guò)信道傳輸能力網(wǎng)絡(luò)流量過(guò)于集中，超過(guò)節(jié)點(diǎn)處理能力6.2.2 路由相關(guān)問(wèn)題 網(wǎng)絡(luò)擁塞 路由過(guò)分集中到網(wǎng)絡(luò)中的某些局部區(qū)域 后果：擁塞逐漸蔓延到全網(wǎng)，網(wǎng)絡(luò)吞吐能力下降流量吞吐量理想路由原理19拓?fù)浣Y(jié)構(gòu)變化引起網(wǎng)絡(luò)中多條路徑發(fā)生改變，需要及時(shí)根據(jù)變化，進(jìn)行路由調(diào)整X信道故障節(jié)點(diǎn)故障新節(jié)點(diǎn)加

9、入路由原理20 路由環(huán)路 節(jié)點(diǎn)間路由配合不當(dāng)，可能出現(xiàn)路由環(huán)路 PDU進(jìn)入環(huán)路后，再也出不來(lái)了路由原理21路由不一致性 時(shí)延會(huì)造成路由的不一致問(wèn)題 要求所有節(jié)點(diǎn)同時(shí)掌握各種情況是不現(xiàn)實(shí)的故障正常路由鏈路故障后的一段時(shí)間內(nèi)路由原理22路由協(xié)議 需要節(jié)點(diǎn)間交換與路由相關(guān)的信息，以便形成全網(wǎng)一致的路由【路由協(xié)議】，解決： 路由的不一致性 網(wǎng)絡(luò)擁塞 路由環(huán)路 拓?fù)渥兓?路由原理236.2.3 路由的基本要求 路由不僅僅是計(jì)算最佳路由的算法 實(shí)際上，網(wǎng)絡(luò)擁塞、拓?fù)浣Y(jié)構(gòu)變化、路由環(huán)路問(wèn)題遠(yuǎn)比最佳路由的影響大 路由協(xié)議的要求 正確性：一致且無(wú)環(huán)路的路由 公平性：對(duì)所有方向的通信等同對(duì)待 簡(jiǎn)潔性：路由算法簡(jiǎn)單

10、 最優(yōu)性：一定策略下的最優(yōu)路由 穩(wěn)健性：對(duì)偶發(fā)事件做出正確反應(yīng) 高效性：路由協(xié)議引入的附加通信少 穩(wěn)定性：路由算法是穩(wěn)定性、收斂的路由原理246.3 基本路由算法與協(xié)議 基本方法 事先計(jì)算所有最優(yōu)路由，形成路由表(轉(zhuǎn)發(fā)表） 各節(jié)點(diǎn)根據(jù)路由表進(jìn)行PDU的轉(zhuǎn)發(fā)213456目的節(jié)點(diǎn) 出口 下一節(jié)點(diǎn)路由原理25路由方式路由協(xié)議靜態(tài)路由動(dòng)態(tài)路由局部最優(yōu)路由 全局最優(yōu)路由路由原理26 靜態(tài)路由與動(dòng)態(tài)路由 依據(jù)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)建立路由表 路由表的內(nèi)容保持不變（網(wǎng)絡(luò)變化小的網(wǎng)絡(luò)） 路由表的內(nèi)容隨網(wǎng)絡(luò)的變化而更新 靜態(tài)路由簡(jiǎn)單可靠、但靈活性較差 動(dòng)態(tài)路由隨網(wǎng)絡(luò)變化而自動(dòng)變化，可靠性較差 動(dòng)態(tài)路由需在節(jié)點(diǎn)間交換路由信

11、息-路由協(xié)議 全局最優(yōu)路由與局部最優(yōu)路由 全局最優(yōu)路由-小型網(wǎng)絡(luò) 局部最優(yōu)路由-大型網(wǎng)絡(luò)路由原理276.3.1 靜態(tài)路由 靜態(tài)路由在網(wǎng)絡(luò)發(fā)生變化時(shí)，由人工修改路由基本方法： 1）計(jì)算所有節(jié)點(diǎn)間的最優(yōu)路徑，形成中心路由選擇表12453613232211331142856385123 4561-15 14522-2 245343-5354445 -455445 5-56445 56-源節(jié)點(diǎn)目的節(jié)點(diǎn)下一節(jié)點(diǎn)路由原理282）為每個(gè)節(jié)點(diǎn)形成路由轉(zhuǎn)發(fā)表節(jié)點(diǎn)1目的節(jié)點(diǎn) 下一節(jié)點(diǎn)2234445464節(jié)點(diǎn)2目的節(jié)點(diǎn)下一節(jié)點(diǎn)1133445464節(jié)點(diǎn)3目的節(jié)點(diǎn) 下一節(jié)點(diǎn)1522455565節(jié)點(diǎn)4目的節(jié)點(diǎn) 下一節(jié)點(diǎn)1

12、122355565節(jié)點(diǎn)5目的節(jié)點(diǎn) 下一節(jié)點(diǎn)1424334466節(jié)點(diǎn)6目的節(jié)點(diǎn) 下一節(jié)點(diǎn)1525354555路由原理296.3.2 動(dòng)態(tài)路由 網(wǎng)絡(luò)的變化較頻繁 網(wǎng)絡(luò)的規(guī)模較大 網(wǎng)絡(luò)的拓?fù)鋸?fù)雜根據(jù)網(wǎng)絡(luò)運(yùn)行的情況，動(dòng)態(tài)更新網(wǎng)絡(luò)的路由表根據(jù)網(wǎng)絡(luò)運(yùn)行的情況，動(dòng)態(tài)更新網(wǎng)絡(luò)的路由表路由原理306.3.2.1 洪泛路由工作方式：某個(gè)接口進(jìn)的PDU，轉(zhuǎn)發(fā)到其余所有接口；目的節(jié)點(diǎn)會(huì)收到多個(gè)重復(fù)報(bào)文。特點(diǎn)： 不需要網(wǎng)絡(luò)拓?fù)湫畔?網(wǎng)絡(luò)結(jié)構(gòu)無(wú)關(guān)性 總能夠送到目的地-高度穩(wěn)健性 所有節(jié)點(diǎn)都能收到-可用于廣播 無(wú)休止地轉(zhuǎn)發(fā)PDU-PDU生命期（Time To Live, TTL) 網(wǎng)絡(luò)上PDU幾何級(jí)數(shù)膨脹-網(wǎng)絡(luò)負(fù)擔(dān)重，小網(wǎng)

13、適用 樹(shù)形，星形網(wǎng)絡(luò)路由原理316.3.2.2 隨機(jī)路由工作方式： 從多個(gè)（能到達(dá)目的地的）出口中隨機(jī)選中一個(gè)來(lái)轉(zhuǎn)發(fā)PDU。 不需要網(wǎng)絡(luò)拓?fù)湫畔?網(wǎng)絡(luò)結(jié)構(gòu)無(wú)關(guān)性 每次路徑是隨機(jī)變化的路由原理326.3.2.3 反向?qū)W習(xí)路由法CA收到從A送來(lái)的報(bào)文路由表中記錄下從該接口可以到達(dá)A 在PDU中增加距離記錄，每經(jīng)過(guò)一個(gè)節(jié)點(diǎn)，距離加1，供反向?qū)W習(xí)選擇最佳路由。特點(diǎn)： 自適應(yīng)路由算法，能逐漸形成最佳路由 動(dòng)態(tài)適應(yīng)新節(jié)點(diǎn)的加入 對(duì)節(jié)點(diǎn)、鏈路故障反應(yīng)遲鈍 對(duì)拓?fù)浞€(wěn)定、小型網(wǎng)絡(luò)適用目的節(jié)點(diǎn)接口距離A An ndndn路由原理336.3.2.4 中心路由（集中路由）213456中心路由計(jì)算機(jī)工作方式： 各個(gè)節(jié)點(diǎn)

14、定期把自己的信道、相鄰節(jié)點(diǎn)情況報(bào)告中心路由計(jì)算機(jī)，由計(jì)算機(jī)計(jì)算出各節(jié)點(diǎn)到其余節(jié)點(diǎn)的最佳路由，然后把路由表分發(fā)到各個(gè)節(jié)點(diǎn)上。特點(diǎn)：最佳路由-理想路由信息上報(bào)、更新同步困難（特別是大網(wǎng)）路由原理346.3.2.5 分布式路由 主動(dòng)與其他節(jié)點(diǎn)交換路由信息-路由協(xié)議路由協(xié)議 節(jié)點(diǎn)獨(dú)立計(jì)算最優(yōu)路由 放棄全局最優(yōu)、尋求局部最優(yōu)化 交換的信息越詳細(xì)、交換的頻率越快，路由優(yōu)化越好，對(duì)網(wǎng)絡(luò)帶來(lái)的額外開(kāi)銷也越大。 尋求在額外開(kāi)銷和反應(yīng)速度間的平衡路由原理35分布式路由的不利之處不利之處： 利用部分路由信息，無(wú)法得到全局最優(yōu)路由 可能出現(xiàn)相互矛盾的路由 反應(yīng)快會(huì)造成路由震蕩，反應(yīng)慢則好處不大有利方面： 局部范圍，網(wǎng)

15、絡(luò)額外開(kāi)銷少 可在局部獲得最佳路由路由原理36（距離、信道費(fèi)用、信道負(fù)載、信道延時(shí)）常見(jiàn)的分布式路由： 基于網(wǎng)絡(luò)距離的分布式路由算法-矢量距離法 基于信道狀態(tài)的分布式路由算法-線路狀態(tài)法路由原理37矢量距離法(VD算法)以中繼節(jié)點(diǎn)個(gè)數(shù)為距離度量21345611111111工作方式： 每個(gè)節(jié)點(diǎn)自動(dòng)找出相鄰節(jié)點(diǎn)，形成初始路由表，距離為1 每個(gè)節(jié)點(diǎn)定期和相鄰節(jié)點(diǎn)交換路由信息 根據(jù)收到的路由信息，更新到其他節(jié)點(diǎn)的路徑（最短距離） 通過(guò)不斷擴(kuò)散，逐漸形成到所有節(jié)點(diǎn)的路由交換路由信息1目的節(jié)點(diǎn)下一節(jié)點(diǎn)距離3路由原理38目的節(jié)點(diǎn)下一節(jié)點(diǎn)距離221331443目的節(jié)點(diǎn)距離113141節(jié)點(diǎn)1路由表更新初始值收到

16、節(jié)點(diǎn)3路由信息目的節(jié)點(diǎn)下一節(jié)點(diǎn)距離221331422更新后目的節(jié)點(diǎn)距離11214151收到節(jié)點(diǎn)2路由信息目的節(jié)點(diǎn)下一節(jié)點(diǎn)距離221331422532距離更新=到中繼節(jié)點(diǎn)的距離+中繼節(jié)點(diǎn)到目的節(jié)點(diǎn)的距離更新后路由原理39特點(diǎn)：特點(diǎn)： 只與鄰節(jié)點(diǎn)交換路由信息 各節(jié)點(diǎn)獨(dú)立計(jì)算最優(yōu)路徑 能適應(yīng)網(wǎng)絡(luò)拓?fù)涞淖兓?穩(wěn)定后，形成最短路徑 路由PDU長(zhǎng)度與節(jié)點(diǎn)數(shù)成正比缺點(diǎn)：缺點(diǎn)： 網(wǎng)絡(luò)變化擴(kuò)散到全網(wǎng)速度慢（收斂慢）-限制在小網(wǎng)使用 存在路由環(huán)-PDU用最大跳數(shù)限制轉(zhuǎn)發(fā)次數(shù)路由原理40線路狀態(tài)法（SPF算法）Shortest Path First以鏈路的某些特征作為距離度量 信道速率、信道負(fù)載、發(fā)送隊(duì)列長(zhǎng)度、通信

17、費(fèi)用等，都可作為度量距離的因素 每個(gè)節(jié)點(diǎn)定期向所有鄰居發(fā)送自己鏈路的距離值 每個(gè)節(jié)點(diǎn)需掌握全網(wǎng)的拓?fù)浣Y(jié)構(gòu)和所有鏈路的距離值，用Dijkstra算法計(jì)算出到所有目的地的最佳路由（僅供自己使用） 路由PDU長(zhǎng)度與節(jié)點(diǎn)的鏈路數(shù)成正比，與網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)無(wú)關(guān)路由原理41SPF的特點(diǎn) 算法收斂較快 距離度量方式靈活，適應(yīng)多種路由策略，如： 鏈路容量、當(dāng)前鏈路流量 通信費(fèi)用、鏈路容量 接近全局最佳路由 由全網(wǎng)拓?fù)浣Y(jié)構(gòu)得到的路由 路由環(huán)的可能性較小路由原理426.4 路由體系結(jié)構(gòu) 路由協(xié)議總是在一定范圍來(lái)考慮的 各個(gè)小網(wǎng)不一定使用相同的路由協(xié)議 網(wǎng)狀網(wǎng)上用另一種協(xié)議(如SPF)來(lái)通信 不同權(quán)屬組織的網(wǎng)絡(luò)間的路由則還需另外的路由協(xié)議域1域2域3域4小網(wǎng)路由路由原理43 路由存在一種層次結(jié)構(gòu)的概念 IGP： Interior Gateway Protocol EGP：Exterior Gateway Protocol小網(wǎng)路由小網(wǎng)路由小網(wǎng)路由網(wǎng)間路由小網(wǎng)路由小網(wǎng)路由小網(wǎng)路由網(wǎng)間路由外部路由IGPEGP路由原理446.4.1 IGP IGP：內(nèi)部網(wǎng)關(guān)協(xié)議 在內(nèi)部網(wǎng)絡(luò)上形成最佳路由 所有節(jié)點(diǎn)為了同一個(gè)目的：最佳路由 節(jié)點(diǎn)間無(wú)保留地交換路由信息 6.3節(jié)的路由都是IGP IGP是內(nèi)部