《計算機(jī)通信網(wǎng) 》第5章 網(wǎng)絡(luò)層1

第五章

網(wǎng)絡(luò)層1背景與相關(guān)問題2路由算法概述3路由算法4擁塞控制5網(wǎng)絡(luò)互聯(lián)11背景與相關(guān)問題1.1背景1.2網(wǎng)絡(luò)層提供的服務(wù)1.3網(wǎng)絡(luò)層的功能1.4網(wǎng)絡(luò)層基礎(chǔ)21.1背景鏈路層僅實(shí)現(xiàn)了數(shù)據(jù)單元(DU)在信道上的傳輸物理層鏈路層物理層鏈路層物理層MAC物理層MAC物理層MAC物理層MAC鏈路層將DU向某個/某些相連的站點(diǎn)傳輸物理層鏈路層物理層鏈路層形成網(wǎng)絡(luò)的基礎(chǔ)在上層，將DU再次傳送出去，擴(kuò)大DU的傳輸范圍DU在一個設(shè)備內(nèi)部實(shí)現(xiàn)鏈路層將DU向?qū)Ψ秸军c(diǎn)傳輸31.1背景由任意多個局域網(wǎng)和點(diǎn)對點(diǎn)鏈路的連接結(jié)構(gòu)網(wǎng)絡(luò)基本元素L1L2L1L2L1L2L1L2L3=點(diǎn)對點(diǎn)局域網(wǎng)(總線、環(huán)形、…)路由器在L3中繼DU任意連接結(jié)構(gòu)41.1背景簡化模型“鏈路層”“物理層”“信道”簡化成鏈路(線條)，DU從源站點(diǎn)的L3出發(fā)，經(jīng)過中間多個L3的轉(zhuǎn)發(fā)，最終到達(dá)目的站網(wǎng)絡(luò)層的核心任務(wù)將分組從源端傳送到目的端分組將如何穿越網(wǎng)絡(luò)從源端到達(dá)目的端？相連端到端中間節(jié)點(diǎn)：如何知道目的地在何處？多條路徑該選哪條路？選好的路故障怎么辦？網(wǎng)絡(luò)擁塞怎么辦？★51.2網(wǎng)絡(luò)層提供的功能★尋址標(biāo)識節(jié)點(diǎn)，節(jié)點(diǎn)定位路由選擇傳播路徑信息、形成路徑選擇路徑存儲轉(zhuǎn)發(fā)接收數(shù)據(jù)并存儲，并按選擇的路由轉(zhuǎn)發(fā)（逐段轉(zhuǎn)發(fā)）擁塞控制網(wǎng)際互聯(lián)穿越多個同構(gòu)或異構(gòu)網(wǎng)絡(luò)可能涉及分段與重組記帳61.3網(wǎng)絡(luò)層提供的服務(wù)★向傳送層提供穿越網(wǎng)絡(luò)的、端到端的服務(wù)，并屏蔽網(wǎng)絡(luò)的具體細(xì)節(jié)向傳送層提供的服務(wù)與具體的網(wǎng)絡(luò)環(huán)境和技術(shù)無關(guān)傳送層不必也不需要了解具體的網(wǎng)絡(luò)情況對傳送層而言，對等實(shí)體的通信就像直接通信一樣服務(wù)類別面向連接的服務(wù)通常由面向連接的協(xié)議實(shí)現(xiàn)無連接的服務(wù)通常由無連接的協(xié)議實(shí)現(xiàn)71.3網(wǎng)絡(luò)層提供的服務(wù)針對網(wǎng)絡(luò)層究竟應(yīng)該提供何種服務(wù)，兩大陣營產(chǎn)生了激烈的沖突爭論的焦點(diǎn)：通信子網(wǎng)應(yīng)承擔(dān)什么樣的任務(wù)？面向連接還是面向無連接的服務(wù)和技術(shù)？以電信公司為代表認(rèn)為網(wǎng)絡(luò)層應(yīng)提供面向連接的服務(wù)以IETF（Internet工程任務(wù)組）為代表認(rèn)為網(wǎng)絡(luò)層應(yīng)提供無連接的服務(wù)81.3網(wǎng)絡(luò)層提供的服務(wù)以電信公司為代表的理由100年來電信系統(tǒng)的成功經(jīng)驗(yàn)就是典范，認(rèn)為：通信子網(wǎng)應(yīng)采用面向連接的服務(wù)與技術(shù)網(wǎng)絡(luò)層應(yīng)該提供可靠的服務(wù)盡量簡單的終端建立連接后，通信更容易受到控制,可在連接上限制用戶流量以IETF為代表的理由通信子網(wǎng)應(yīng)采用無連接的服務(wù)與技術(shù)，因?yàn)椋和ㄐ抛⒍ú豢煽啃枰K端自行解決差錯等問題－－復(fù)雜終端終端的復(fù)雜性與終端的成本不一定成比例上升用戶不必支付過時的、高額的通信費(fèi)用網(wǎng)絡(luò)的適應(yīng)性更強(qiáng)、帶寬利用率更高更自由91.3網(wǎng)絡(luò)層提供的服務(wù)兩種不同的觀念形成了兩種不同的通信子網(wǎng)構(gòu)成方式面向連接的通信子網(wǎng)——虛電路無連接的通信子網(wǎng)——數(shù)據(jù)報典型的面向連接的網(wǎng)絡(luò)層ATM的網(wǎng)絡(luò)層X.25網(wǎng)的網(wǎng)絡(luò)層典型的無連接的網(wǎng)絡(luò)層Internet的網(wǎng)絡(luò)層★10數(shù)據(jù)報與虛電路虛電路方式節(jié)點(diǎn)尋徑速度快數(shù)據(jù)報方式健壯性強(qiáng)重新建立連接，重新開始11數(shù)據(jù)報與虛電路項(xiàng)目類型數(shù)據(jù)報子網(wǎng)虛電路子網(wǎng)都是以分組為單位，存儲轉(zhuǎn)發(fā)、逐站尋徑建鏈與拆鏈NOYES地址源、目地址虛電路號保存狀態(tài)信息NOYES（虛電路映射表）路由選擇每個分組獨(dú)立選路所有分組沿已建好的路徑轉(zhuǎn)發(fā)節(jié)點(diǎn)或線路損毀的影響影響不大，可立即重新選路所有經(jīng)過的虛電路被終止，須重新建立連接擁塞控制較難較易服務(wù)質(zhì)量較難較易靈活性更好稍差★121.4網(wǎng)絡(luò)層基礎(chǔ)網(wǎng)絡(luò)地址：編址與尋址路由表（FIT）：記錄到達(dá)目的地的路徑信息Routed：查表方法及轉(zhuǎn)發(fā)策略Routing：計算到目的節(jié)點(diǎn)的最佳路徑，生成并維護(hù)路由表網(wǎng)絡(luò)層分組格式（PDU）網(wǎng)絡(luò)層協(xié)議進(jìn)一步分析無連接模式、連接模式★131.4.1網(wǎng)絡(luò)地址網(wǎng)絡(luò)地址的編址需求全網(wǎng)唯一地址：每個站點(diǎn)至少有一個唯一網(wǎng)絡(luò)地址來標(biāo)識網(wǎng)絡(luò)地址結(jié)構(gòu)有規(guī)律，有助于站點(diǎn)位置的查找（尋址）全網(wǎng)統(tǒng)一編址兩個編址參考實(shí)例郵政編碼6100xx6102xx6117xx郫縣成都雙流清水河校區(qū)沙河校區(qū)61830000832000008320111483201120832011198320345661830114618301196183012061834321電話號碼特點(diǎn)：區(qū)域編址內(nèi)部子區(qū)域編碼任意編排特點(diǎn)：中心編址按中心接口位置編排141.4.1網(wǎng)絡(luò)地址電話網(wǎng)（中心編址）國家號+城市號+局號+終端號Internet（區(qū)域編址）網(wǎng)絡(luò)號+子網(wǎng)號+主機(jī)號對比以太網(wǎng)MAC地址編碼MAC地址：xx-xx-xx-xx-xx-xxIP地址：aaa.bbb.ccc.ddd平面地址，地址與站點(diǎn)位置無關(guān)結(jié)構(gòu)地址，地址與站點(diǎn)位置相關(guān)：位置在某個網(wǎng)絡(luò)(aaa.bbb.ccc.0)區(qū)域內(nèi)結(jié)構(gòu)地址為網(wǎng)絡(luò)協(xié)議提供了尋找站點(diǎn)所在位置的部分線索，但這對于尋找網(wǎng)絡(luò)站點(diǎn)還遠(yuǎn)遠(yuǎn)不夠！151.4.1網(wǎng)絡(luò)地址考慮站點(diǎn)A向站點(diǎn)B傳遞報文ABR1R2R3R4R5傳遞過程可以分解為：1、A將報文傳遞到R1上2、R1設(shè)法找到B所在的區(qū)域位置(R5),并尋找到R5的路徑，沿路徑傳遞報文3、R5將報文傳遞到B上尋址的關(guān)鍵點(diǎn)：是各個R如何找出目的R在何處、及確定傳輸路徑的問題，與源網(wǎng)絡(luò)或目的網(wǎng)絡(luò)關(guān)系不大。(中心編址方案亦如此)161.4.1網(wǎng)絡(luò)編址和尋址區(qū)域編址與中心編址方案的尋址差異區(qū)域編址可能有多個目的R帶來尋址靈活性的同時，也帶來了尋址計算的復(fù)雜性中心編址只僅有一個目的R尋址方式簡便、單一171.4.2路由表與轉(zhuǎn)發(fā)策略★路由表（RoutingTable）通過路由協(xié)議計算出某個節(jié)點(diǎn)到目的節(jié)點(diǎn)的最佳路由，形成的路徑信息有時也與轉(zhuǎn)發(fā)表同義（ForwardingTable-FIT）注意：有時分為路由信息表和轉(zhuǎn)發(fā)表兩種表，而轉(zhuǎn)發(fā)表由路由信息表得到路由表的組成ABCED121122A節(jié)點(diǎn)的路由表目的下一站出口度量B直連21DC13……181.4.2路由表與轉(zhuǎn)發(fā)策略轉(zhuǎn)發(fā)策略查路由表（轉(zhuǎn)發(fā)表），根據(jù)轉(zhuǎn)發(fā)路徑進(jìn)行轉(zhuǎn)發(fā)轉(zhuǎn)發(fā)之前如何查表？最短適配：從高地址部分開始適配即從最大的范圍開始例：8602861830328最長適配：從低地址部分開始適配即從最接近主機(jī)的路由開始例：202.115.12.0高地址－－網(wǎng)絡(luò)號低地址－－主機(jī)號其它查找算法：順序、折半、Hash……不考慮地址的結(jié)構(gòu)性，可提高查找效率與以上兩種方法配合以提高效率完整適配：要求路由表規(guī)模太大，一般不用191.4.2路由表與轉(zhuǎn)發(fā)策略主要技術(shù)問題(按地址尋址方式)地址空間太大，每個節(jié)點(diǎn)都裝不下IP地址：32bit（232個地址）IPv6地址：128bit（2128個地址）只能記錄已知部分查表運(yùn)算量太大如上萬個站點(diǎn)的表IP協(xié)議的處理方法僅考慮網(wǎng)絡(luò)號部分，忽略主機(jī)號部分可以大大減小轉(zhuǎn)發(fā)表項(xiàng)數(shù)目但仍然還有很大的運(yùn)算量目的子網(wǎng)下一節(jié)點(diǎn)出口鏈路子網(wǎng)號主機(jī)號IP地址32比特201.4.3路由選擇（Routing）尋找各處站點(diǎn)，在本地建立路徑的方向轉(zhuǎn)發(fā)表(FIT）Routing協(xié)議設(shè)置路由信息211.4.3路由選擇（Routing）每個站點(diǎn)的FIT表內(nèi)容表示從自己出發(fā)達(dá)到任意目的地址的“最短路徑”。(不同站點(diǎn)FIT內(nèi)容不同)Routing協(xié)議站點(diǎn)間路由信息交互計算到任意站點(diǎn)的最短路由，生成FIT表的內(nèi)容221.4.4網(wǎng)絡(luò)層分組格式L3轉(zhuǎn)發(fā)DU—微觀問題需要在DU中攜帶轉(zhuǎn)發(fā)信息，L3才能處理L3接收DU、尋找路徑、轉(zhuǎn)發(fā)DU功能構(gòu)成L3協(xié)議定義協(xié)議數(shù)據(jù)格式(分組，Packet)DU=網(wǎng)絡(luò)層Packet=[協(xié)議首部+Data_Block]協(xié)議首部={類型、狀態(tài)、方向等信息}Data-Block=攜帶的數(shù)據(jù)塊(若干字節(jié)數(shù)據(jù))HDataDU網(wǎng)絡(luò)層分組鏈路層DU鏈路層HData根據(jù)首部信息選擇轉(zhuǎn)發(fā)出口鏈路L3231.4.4網(wǎng)絡(luò)層分組格式無連接模式分組標(biāo)志：首部包含源地址和目的地址連接模式分組標(biāo)志：首部包含流ID號(可能名稱不同)VerHLenTOSTotalLengthIdentifierFlagsFragOffsetTTLProtocolHCSSourceIPAddressDestinationIPAddressDataBlockIP分組格式GPILGNLCN分組類型DataBlockX.25分組格式(源地址、目的地址)(邏輯信道號=流ID)241.4.5網(wǎng)絡(luò)層協(xié)議—進(jìn)一步分析兩種典型的網(wǎng)絡(luò)通信體制比較無連接模式(ConnectionlessMode)通信體制數(shù)據(jù)報(Datagram)通信連接模式(ConnectionMode)通信體制虛電路(VirtualCircuit)通信S1D1D2S2考察S1D1、S2D2兩對通信25無連接模式典型特征PDU首部包含有源地址S和目的地址D中間節(jié)點(diǎn)用目的地址D尋找PDU轉(zhuǎn)發(fā)方向S1D1D2S2HDataSD……報文常規(guī)傳輸路徑報文即使走錯，地址D也會指出正確方向特性：1、不需要為通信預(yù)先建立完整傳輸路徑2、報文沒有固定的傳輸路徑(數(shù)據(jù)報通信體制)3、各個報文獨(dú)立穿越網(wǎng)絡(luò)4、網(wǎng)狀結(jié)構(gòu)下，部分節(jié)點(diǎn)或鏈路故障不會造成通信中斷5、節(jié)點(diǎn)難以估計通信自己的通信流量26連接模式典型特征PDU首部用連接id標(biāo)明中繼方向需要事先建立連接id的中繼關(guān)系S1D1D2S2報文常規(guī)傳輸路徑報文走錯，連接id將把報文送到錯誤方位HDataid……11①②①②①②①②①②⑤①②③②⑤①27連接模式連接id標(biāo)識的傳輸路徑邏輯上等效于一條傳輸電路(VirtualCircuit)S1D1D2S211①②n連接id的編號空間大小等同于該鏈路的虛電路數(shù)目特性：1、需要預(yù)先建立id轉(zhuǎn)發(fā)的完整傳輸路徑2、報文沿id標(biāo)識的固定路徑傳輸(虛電路傳輸體制)3、同源、同id的各個報文沿路徑順序傳輸4、傳輸路徑上節(jié)點(diǎn)或鏈路故障將造成通信中斷5、節(jié)點(diǎn)可估計通過自己的通信流量12n28網(wǎng)絡(luò)層協(xié)議—進(jìn)一步分析DU傳輸路徑問題HData轉(zhuǎn)發(fā)信息=目的地址根據(jù)地址選擇出口鏈路到X，走AA到X，走C到X，走QQX123njkm12knjkm12injkmHData原始轉(zhuǎn)發(fā)信息13HDataHDataHDatamk根據(jù)首部的不同ID，從同一源站點(diǎn)發(fā)出的分組將走不同的路徑，同時，分組首部ID也隨之改變根據(jù)首部不同目的地址，從同一源站點(diǎn)發(fā)出的分組將走不同的路徑，分組首部不發(fā)生改變HDataC29網(wǎng)絡(luò)層協(xié)議—進(jìn)一步分析無連接vs連接

FITConnectionless網(wǎng)絡(luò)協(xié)議利用FIT表直接轉(zhuǎn)發(fā)PDU盡量發(fā)揮FIT直接轉(zhuǎn)發(fā)的優(yōu)勢：1、用于網(wǎng)狀拓?fù)浣Y(jié)構(gòu)的網(wǎng)絡(luò)中2、動態(tài)修改FIT，形成動態(tài)路由，以適應(yīng)網(wǎng)絡(luò)動態(tài)變化3、地址空間巨大，每個報文都需經(jīng)FIT查表，CPU計算負(fù)擔(dān)重FITConnection網(wǎng)絡(luò)協(xié)議FIT表僅用于建立id之間的轉(zhuǎn)發(fā)關(guān)系FIT和id雙重處理，盡量降低FIT處理負(fù)擔(dān)：1、采用簡單拓?fù)浣Y(jié)構(gòu)(如樹形結(jié)構(gòu))2、不考慮網(wǎng)絡(luò)動態(tài)變化，固定FIT3、優(yōu)化數(shù)據(jù)轉(zhuǎn)發(fā)：連接報文數(shù)目<<數(shù)據(jù)報文數(shù)目4、id轉(zhuǎn)發(fā)關(guān)系動態(tài)建立，一次建立多次使用5、鏈路id空間小，查表負(fù)擔(dān)輕30查表算法目的子網(wǎng)下一中繼出接口FIT表路由器有一個FIT表供路由查詢FIT可能達(dá)到幾千上萬條表項(xiàng)，假設(shè)有10000條表項(xiàng)，對每個PDU的目的地址平均需要查詢5000次表項(xiàng)假設(shè)路由器每秒可轉(zhuǎn)發(fā)M個報文，表項(xiàng)查詢速率將達(dá)到5000*M

（表項(xiàng)/秒）連接id對接表連接id出id出接口每個接口有一個連接id對接表，其表項(xiàng)只有幾千個接口收到PDU，根據(jù)PDU的id號(=a)查表轉(zhuǎn)發(fā)時，直接采取表索引找到出id和出接口。id=連接id對接表[a].出id

接口=連接id對接表[a].出接口31通信體制：小結(jié)無連接方式A-B的通信可隨時切換傳輸路徑具備抗鏈路或中繼站點(diǎn)故障能力分組到達(dá)B的順序可能發(fā)生與A發(fā)出的順序不一致易于實(shí)現(xiàn)廣播通信中繼轉(zhuǎn)發(fā)性能較弱(地址空間大，F(xiàn)IT表龐大)每個分組平均需要M/2次查表(M為表項(xiàng)數(shù))面向連接方式A-B的通信沿固定路徑傳輸不具備抗鏈路或中繼站點(diǎn)故障能力分組按順序傳輸難以實(shí)現(xiàn)廣播通信中繼轉(zhuǎn)發(fā)能力強(qiáng)(只關(guān)注流經(jīng)本站的ID，F(xiàn)IT表小巧)優(yōu)化情況下，每個分組只需一次查表32★2路由算法概述★2.1路由的基本概念2.2路由算法的要求2.3路由最優(yōu)化原則2.4路由算法分類332.1路由的概念路由的基本概念源到目的節(jié)點(diǎn)之間，由節(jié)點(diǎn)和線路組成的一條通路路由選擇面臨的問題存在多條路徑選擇一條最優(yōu)路徑：如何選擇？節(jié)點(diǎn)需掌握所有的路徑：表項(xiàng)規(guī)模？最優(yōu)路徑隨網(wǎng)絡(luò)拓?fù)渥兓兓酚尚枰皶r更新，但要避免路由振蕩避免出現(xiàn)路由環(huán)路.避免網(wǎng)絡(luò)阻塞負(fù)載均擔(dān)？★34路由相關(guān)問題拓?fù)浣Y(jié)構(gòu)變化引起網(wǎng)絡(luò)中多條路徑發(fā)生改變，需要及時根據(jù)變化，進(jìn)行路由調(diào)整X信道故障節(jié)點(diǎn)故障新節(jié)點(diǎn)加入35路由相關(guān)問題路由環(huán)路節(jié)點(diǎn)間路由配合不當(dāng)，可能出現(xiàn)路由環(huán)路PDU進(jìn)入環(huán)路后，再也出不來了36路由不一致性路由信息分發(fā)時延會造成路由的不一致問題要求所有節(jié)點(diǎn)同時掌握各種情況是不現(xiàn)實(shí)的故障正常路由鏈路故障后的一段時間內(nèi)37網(wǎng)絡(luò)流量過于集中，超過信道傳輸能力網(wǎng)絡(luò)流量過于集中，超過節(jié)點(diǎn)處理能力路由相關(guān)問題網(wǎng)絡(luò)擁塞路由過分集中到網(wǎng)絡(luò)中的某些局部區(qū)域后果：擁塞逐漸蔓延到全網(wǎng)，網(wǎng)絡(luò)吞吐能力下降流量吞吐量理想382.2路由選擇算法的要求正確性：目的地存在且可達(dá)簡單性：計算簡單，實(shí)現(xiàn)容易健壯性：路由算法能適應(yīng)節(jié)點(diǎn)故障、增減造成的拓?fù)浣Y(jié)構(gòu)的變化，及時調(diào)整路由，并不影響全網(wǎng)工作穩(wěn)定性：路由更新后會有過渡期，路由算法應(yīng)使過渡期盡量短，具有快的收斂性（避免路由震蕩）公平性：節(jié)點(diǎn)地位平等最優(yōu)化：一定策略下的最優(yōu)（有時也稱策略性）低開銷：路由控制信息盡可能少，開銷盡可能低。★392.3最佳路由什么是最優(yōu)路徑？源、目節(jié)點(diǎn)間存在多條路徑1到5的路徑有多條：1-2-5，1-3-5，1-4-5，1-2-3-5……尋求一條最優(yōu)路徑，需求不同會有不同的最優(yōu)路徑最優(yōu)定義以距離為度量：最短距離以跳數(shù)為度量：最少節(jié)點(diǎn)數(shù)以時延為度量：最小延時以投遞率為度量：最大成功率以帶寬為度量：最大吞吐量……實(shí)際網(wǎng)絡(luò)中，可能考慮一項(xiàng)，也可能需要考慮多項(xiàng)參數(shù)，進(jìn)行選擇通常稱這些度量參數(shù)為Cost或Metric★25314402.3最佳路由最佳路徑節(jié)點(diǎn)si到節(jié)點(diǎn)sj的所有路徑P={1,2,…}中，若則稱為si到sj的最佳路徑，其距離為即：所有路徑中最短的一條為最佳路徑SD2323431311找出S到D的最佳路徑R1R2R3R4R541最佳路徑—例從A到E的多種最佳路徑ABCDE若考慮經(jīng)過最少中間節(jié)點(diǎn)，則最佳路徑為A-D-E10Mbps10Mbps10Mbps100Mbps100Mbps100Mbps結(jié)合信道速率若考慮選擇路徑傳輸容量，則最佳路徑為A-B-C-E信道占用率40%80%30%10%15%12%若考慮路徑可用速率，則最佳路徑仍為A-B-C-E若考慮路徑有較小傳輸延遲，則最佳路徑為A-B-D-E(80%占用率會大大增加傳輸延遲)42路由選擇的最優(yōu)化原則最優(yōu)化原理若I到K的最佳路徑經(jīng)過J，則lm這條路徑也是J到K的最優(yōu)路徑證明(反證法)若J到K的最佳路徑是另一條，假設(shè)經(jīng)過l1和l2，而不經(jīng)過lm則必有D(l1)+D(l2)<D(lm)可以得到：D(ln)+D(l1)+D(l2)<D(ln)+D(lm)與{ln，lm}為I到K的最佳路徑矛盾IJKl1l2lmln43路由選擇的最優(yōu)化原則用途當(dāng)I計算最優(yōu)路由后將分組交給J，J所選擇的最優(yōu)路由與I選擇的是一致的！是存儲轉(zhuǎn)發(fā)、逐站尋徑的基礎(chǔ)，是分布式路由算法的基礎(chǔ)推論1某站點(diǎn)到目的節(jié)點(diǎn)K的最優(yōu)路徑，只需知道該節(jié)點(diǎn)到鄰居節(jié)點(diǎn)的“距離”和鄰居節(jié)點(diǎn)到K的最優(yōu)路徑。K哪條最優(yōu)？d1d2d3abca+d1b+d2c+d344匯集樹（SinkTree）推論2從所有的源到一個指定目標(biāo)的最優(yōu)路徑的集合構(gòu)成了一顆以目標(biāo)節(jié)點(diǎn)為根的樹。從一個源到所有目標(biāo)的最優(yōu)路徑的集合構(gòu)成了一顆以源節(jié)點(diǎn)為根的樹路由算法為所有路由器找到并使用匯集樹452.4路由算法的類型及特點(diǎn)靜態(tài)路由算法（非自適應(yīng)算法）路由表內(nèi)容不隨網(wǎng)絡(luò)的變化而變化算法簡單，可靠性高，但不靈活，適用于小型網(wǎng)絡(luò)動態(tài)路由算法（自適應(yīng)算法）根據(jù)網(wǎng)絡(luò)的變化計算路由路由表內(nèi)容隨網(wǎng)絡(luò)的變化自動更新動態(tài)路由需在節(jié)點(diǎn)間交換信息算法較復(fù)雜，但更能反映網(wǎng)絡(luò)實(shí)際情況適用于網(wǎng)絡(luò)拓?fù)渥兓⒋笮途W(wǎng)絡(luò)46★2.4.1幾種靜態(tài)路由算法固定路由算法事先計算所有節(jié)點(diǎn)的最佳路徑，形成中心路由表。各節(jié)點(diǎn)根據(jù)中心路由表，形成自己的路由轉(zhuǎn)發(fā)表洪泛法（擴(kuò)散法）節(jié)點(diǎn)將收到的分組沿本節(jié)點(diǎn)各出線（收分組的線除外）轉(zhuǎn)發(fā)出去，總有一條路徑最優(yōu)隨機(jī)路由節(jié)點(diǎn)將收到的分組根據(jù)概率隨機(jī)選取一個出口將分組轉(zhuǎn)發(fā)出去燙土豆法節(jié)點(diǎn)將收到的分組盡快出手，選擇隊(duì)列最短的出口轉(zhuǎn)發(fā)472.4.2幾種動態(tài)路由算法涉及的問題節(jié)點(diǎn)之間交換路由信息快速適應(yīng)拓?fù)渥兓兄負(fù)渥兓焖賯鬟f變化信息快速形成新的穩(wěn)定的路由（無環(huán)路、不震蕩，快速收斂）中心路由算法逆向?qū)W習(xí)法分布式路由算法（重點(diǎn)）距離矢量法、鏈路狀態(tài)法48中心路由算法（集中路由）原理各個節(jié)點(diǎn)定期將本節(jié)點(diǎn)及其與相鄰節(jié)點(diǎn)的信息報告給中心路由計算機(jī)由中心路由計算機(jī)計算出各節(jié)點(diǎn)到其它節(jié)點(diǎn)的最佳路由，然后分配到各個節(jié)點(diǎn)特點(diǎn)理論上可得到全網(wǎng)最優(yōu)路由（考慮了流量等全網(wǎng)信息）但實(shí)現(xiàn)困難，很難在大網(wǎng)中使用，適應(yīng)于小網(wǎng)，原因：信息上傳困難同步困難路由更新過時21345中心路由計算機(jī)★49逆向（反向）學(xué)習(xí)法原理根據(jù)接收分組中的源地址和接收端口號，形成轉(zhuǎn)發(fā)表，以便下次作為目的節(jié)點(diǎn)時的轉(zhuǎn)發(fā)路徑特點(diǎn)能動態(tài)適應(yīng)新節(jié)點(diǎn)的加入對線路故障、節(jié)點(diǎn)損壞反應(yīng)遲鈍適應(yīng)拓?fù)浣Y(jié)構(gòu)相對穩(wěn)定、小網(wǎng)CA收到從A送來的分組路由表中記錄從該接口可以到達(dá)A★目標(biāo)節(jié)點(diǎn)端口距離………………AnDn50分布式動態(tài)路由算法基本原理節(jié)點(diǎn)之間需相互交換路由信息節(jié)點(diǎn)單獨(dú)計算路由基本特點(diǎn)局部最優(yōu)，全局不一定最優(yōu)相互交換信息越具體、越頻繁，路由優(yōu)化越好，但造成的額外開銷也越大。需要在額外開銷和路由更新的頻率之間進(jìn)行折中優(yōu)點(diǎn)動態(tài)反映網(wǎng)絡(luò)變化，路由表自動形成與更新（不需人工干預(yù)）局部最優(yōu)，路由開銷少缺點(diǎn)局部最優(yōu)路由，不是全局最優(yōu)路由可能出現(xiàn)不一致（矛盾）的路由可能出現(xiàn)路由震蕩（路由表變化太快）可能出現(xiàn)路由發(fā)散（不能收斂）★51分布式路由算法要點(diǎn)交換路由信息：分布式計算：節(jié)點(diǎn)根據(jù)交換的路由信息，采用最優(yōu)路由計算方法計算最佳路由哪些信息？與誰交換？邊交換信息邊計算可達(dá)、距離、費(fèi)用、負(fù)載、延時……與鄰居、與所有節(jié)點(diǎn)何時交換？定時、拓?fù)渥兓瘯r★523路由算法3.1洪泛路由（擴(kuò)散法）3.2距離矢量路由3.3鏈路狀態(tài)路由3.4分級路由3.5一些特殊的路由533路由算法2312R0R1R2R3R4路由信息：鏈路或路徑距離、節(jié)點(diǎn)間連接關(guān)系等信息信息交互：節(jié)點(diǎn)間交換路由信息的方法路由算法：計算到其余節(jié)點(diǎn)的路徑的算法計算到所有已知路由節(jié)點(diǎn)的最佳路徑通過交換，積累關(guān)于網(wǎng)絡(luò)的更全面的路由信息關(guān)于路徑計算所需的參數(shù)節(jié)點(diǎn)初始條件1、掌握到各鄰居節(jié)點(diǎn)的鏈路及距離2、能感知鏈路的狀態(tài)(正常、故障)路由算法1、若節(jié)點(diǎn)什么都不知道，洪泛路由算法2、若知道鄰居節(jié)點(diǎn)到各處的最佳路由—距離矢量路由算法3、若知道各節(jié)點(diǎn)的鏈路連接狀態(tài)—鏈路狀態(tài)路由算法543路由算法R0R1R2R3R4洪泛路由：入報文向所有方向轉(zhuǎn)發(fā)出去，總有報文到達(dá)目的地R0R1R2R3R4距離矢量路由：如果所有鄰居都已形成到其余節(jié)點(diǎn)的最佳路徑，則R0匯集整理，就可形成自己到各處的最佳路徑匯集路由信息R0鏈路狀態(tài)路由：如果收集到所有節(jié)點(diǎn)的鏈路連接狀態(tài)，R0就能形成網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，并能計算出到各處的路由Ri的鏈路連接狀態(tài)RjRkR0最佳路徑結(jié)果=FIT表內(nèi)容目的1:下一跳為Ri，距離為x目的2：下一跳為Rx，距離為y最佳路徑中只取了下一跳553.1洪泛路由(FloodingRoute)★節(jié)點(diǎn)將收到的分組向所有方向擴(kuò)散（接收鏈路除外）S發(fā)送兩份拷貝R1、R2分別發(fā)送兩份拷貝R3發(fā)送3分拷貝特點(diǎn)無需掌握網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)節(jié)點(diǎn)無需建立FIT表分組肯定能到達(dá)目的節(jié)點(diǎn)高度穩(wěn)健性目的節(jié)點(diǎn)會收到多個重復(fù)分組所有節(jié)點(diǎn)都能收到信息特別適用于廣播SDR1R2R356洪泛路由—分組泛濫問題如果網(wǎng)絡(luò)拓?fù)浯嬖诃h(huán)路，且沒有分組抑制措施分組將會在網(wǎng)絡(luò)上無限循環(huán)轉(zhuǎn)發(fā)可能會出現(xiàn)擴(kuò)散風(fēng)暴，造成網(wǎng)絡(luò)的過載而癱瘓T0時刻T1時刻T2時刻T3時刻T4時刻假設(shè)：源節(jié)點(diǎn)不擴(kuò)散自己發(fā)送的分組目的節(jié)點(diǎn)不擴(kuò)散自己接收的分組上一時刻分組當(dāng)前時刻分組57洪泛路由—分組抑制抑制約束條件節(jié)點(diǎn)不可能根據(jù)分組內(nèi)容判斷兩個分組是否相同節(jié)點(diǎn)不能用地址判斷兩個分組是否相同抑制方法1：跳數(shù)抑制法(限制分組轉(zhuǎn)發(fā)次數(shù))在分組中，設(shè)置跳數(shù)計數(shù)值設(shè)置生命周期（TimeToLive，TTL）初始值為目的站點(diǎn)最大估計跳數(shù)值節(jié)點(diǎn)轉(zhuǎn)發(fā)分組前，將跳數(shù)計數(shù)減一，不為零繼續(xù)轉(zhuǎn)發(fā)，為零則停止轉(zhuǎn)發(fā)，并丟棄。T0時刻,TTL=4T4時刻，該分組消失58洪泛路由—分組抑制抑制方法2：唯一分組標(biāo)識法(轉(zhuǎn)發(fā)過的不再轉(zhuǎn)發(fā))源站點(diǎn)為所有發(fā)送的報文統(tǒng)一編排序號分組標(biāo)識：<源地址，序號>在全網(wǎng)范圍內(nèi)是唯一的節(jié)點(diǎn)記錄已經(jīng)轉(zhuǎn)發(fā)過分組的標(biāo)識：<源地址,序號>需定期清除記錄，以免占用大量存儲空間轉(zhuǎn)發(fā)前，節(jié)點(diǎn)識別分組標(biāo)識，抑制轉(zhuǎn)發(fā)過的分組T1時刻T0時刻T2時刻,中間節(jié)點(diǎn)只轉(zhuǎn)發(fā)1次59洪泛路由—小結(jié)不需要掌握網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)、不需要FIT表分組總能到達(dá)目的節(jié)點(diǎn)(除非脫離了網(wǎng)絡(luò))目的節(jié)點(diǎn)可能收到多個相同分組若不抑制分組擴(kuò)散，網(wǎng)絡(luò)將癱瘓樹形拓?fù)涑馓鴶?shù)抑制法比唯一分組標(biāo)識法占用更多網(wǎng)絡(luò)資源跳數(shù)法是無狀態(tài)的唯一分組標(biāo)識法是有狀態(tài)的(與轉(zhuǎn)發(fā)歷史有關(guān))節(jié)點(diǎn)需記錄：轉(zhuǎn)發(fā)過的節(jié)點(diǎn)地址、最新序號60洪泛路由的應(yīng)用軍用網(wǎng)節(jié)點(diǎn)隨時都有被毀的可能，此路由算法可最大限度地將信息傳輸?shù)侥康牡豈ANET節(jié)點(diǎn)可自由移動，網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)隨時都在發(fā)生變化。按需路由（如AODV）用洪泛路由找到目的節(jié)點(diǎn)后，再建立傳輸路徑MobileAdhocNETwork613.2距離矢量路由★原理：考察如圖網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)及各條鏈路的距離R1到D的最短距離為4R2到D的最短距離為3R3到D的最短距離為5S根據(jù)R1、R2、R3的信息推算到D的最短距離S到D的距離=S到鄰居i的距離+鄰居i到D的距離(距離矢量)算法思想S獲知各鄰居到D的最短距離找出S到D的最短距離和下一跳中繼節(jié)點(diǎn)SD2323431311R1R2R3R4R5DR55DR53DR24D4D3D5R1：R2：R3：+132=567DR1562距離矢量路由—DV協(xié)議初始階段每個節(jié)點(diǎn)形成從自己到鄰居節(jié)點(diǎn)的矢量路由信息矢量路由信息={[目的,下一跳，距離],[…]}SD2323431311R1R2R3R4R5R1R11R2R23R3R32SS1R2R21R4R43SS2R5R53SS3R1R11R4R44R5R51………………………63距離矢量路由—DV協(xié)議路由信息擴(kuò)散每個節(jié)點(diǎn)把自己的路由信息形成分組向鄰居擴(kuò)散擴(kuò)散內(nèi)容為{[目的,距離],[目的,距離],[…]}SD2323431311R1R2R3R4R5S1R21R43S2R53S3R11R44R51………………………S1R21R43R1S3R11R44R51R2S2R53R3R1R11R2R23R3R32SR12R2R12R4R141+(R1)SR26R1R24R4R27R5R243+(R2)S原有SR34R5R352+(R3)………64距離矢量路由—DV協(xié)議用收到的信息更新自己的路由信息S收到Ri的路由信息后，更新路由信息的過程出現(xiàn)新的目的地址，S增加一條路由有相同路由，比較已有的短，還是經(jīng)Ri的短，選擇更短的D(S,Rx)>D(S,Ri)+D(Ri,Rx)?例：用R1的路由信息更新時D(S,R2)=3經(jīng)R1到R2的距離為D(S,R1)+D(R1,R2)=1+1=2R1R11R2R23R3R32S原有的路由信息S1R21R43R1R1R11R2R12R3R32R4R14S更新后路由信息S3R11R44R51R1R11R2R12R3R32R4R14R5R24R2S更新后路由信息S2R53R3更新到R2的路由增加到R4的路由增加到R5的路由R1R11R2R12R3R32R4R14R5R24無更新65距離矢量路由目的節(jié)點(diǎn)下一節(jié)點(diǎn)距離221331信息發(fā)布者2目的節(jié)點(diǎn)距離113141節(jié)點(diǎn)1路由表初始值收到節(jié)點(diǎn)3路由信息目的節(jié)點(diǎn)下一節(jié)點(diǎn)距離221331更新后發(fā)布者3目的節(jié)點(diǎn)距離11214151收到節(jié)點(diǎn)2路由信息目的節(jié)點(diǎn)下一節(jié)點(diǎn)距離221331422距離更新=到鄰居節(jié)點(diǎn)的距離+鄰居節(jié)點(diǎn)到目的節(jié)點(diǎn)的距離更新后213456112111111422532關(guān)66距離矢量路由213456112111111目的節(jié)點(diǎn)下一節(jié)點(diǎn)距離221331422532節(jié)點(diǎn)1當(dāng)前的路由表節(jié)點(diǎn)1向節(jié)點(diǎn)2發(fā)布的路由信息信息發(fā)布者1目的節(jié)點(diǎn)距離21314252節(jié)點(diǎn)1向節(jié)點(diǎn)3發(fā)布的路由信息信息發(fā)布者1目的節(jié)點(diǎn)距離21314252關(guān)67距離矢量路由213456112111111目的節(jié)點(diǎn)下一節(jié)點(diǎn)距離221331422532節(jié)點(diǎn)1路由表更新距離更新=到鄰居節(jié)點(diǎn)的距離+鄰居節(jié)點(diǎn)到目的節(jié)點(diǎn)的距離收到節(jié)點(diǎn)2路由信息發(fā)布者2目的節(jié)點(diǎn)距離1131415263目的節(jié)點(diǎn)下一節(jié)點(diǎn)距離221331422532更新后624發(fā)布者3目的節(jié)點(diǎn)距離1121415162目的節(jié)點(diǎn)下一節(jié)點(diǎn)距離221331422532更新后62433關(guān)68距離矢量路由路由信息周期性地逐跳擴(kuò)散，周期性更新經(jīng)過若干周期后，每個節(jié)點(diǎn)都掌握到任意節(jié)點(diǎn)的最短路由R1R11R2R12R3R32R4R14R5R24周期i擴(kuò)散更新R1R11R2R12R3R32R4R14R5R24………周期i+1擴(kuò)散第0周期：掌握到1跳節(jié)點(diǎn)的路由第1周期：掌握到2跳節(jié)點(diǎn)的路由第2周期：掌握到3跳節(jié)點(diǎn)的路由…69距離矢量路由路由信息的維護(hù)如果新的路由與舊的路由距離相同，選擇哪一條？維持原有路由不變(穩(wěn)定傳輸路徑考慮)若某條路由長時間沒有刷新，將被刪除重復(fù)的路由信息(距離相同、源于周期性擴(kuò)散)用于刷新路由表項(xiàng)的生命期70DV協(xié)議的改進(jìn)DV協(xié)議的主要問題：無窮計算問題沒有讓某條不存在的路由從所有節(jié)點(diǎn)中消失的機(jī)制！設(shè)計最大路徑長度（跳數(shù)），以減輕環(huán)路出現(xiàn)時帶來的損害R1R2R3R4111到R1的距離123R1到R2鏈路中斷后323消失消失4消失5消失6消失5到R1的距離變化71無窮計數(shù)問題算法的缺陷：對好消息反應(yīng)迅速，對壞消息反應(yīng)遲鈍72DV協(xié)議的改進(jìn)改進(jìn)1：水平分割不處理回傳的路由信息（或者節(jié)點(diǎn)不將從某節(jié)點(diǎn)收到的信息再傳回給該節(jié)點(diǎn)）例：R1處理從S傳來的路由信息時回到剛才的例子R1R11R2R12R3R32R4R14R5R24R1根據(jù)路由信息形成的方式，下一跳為R1的表項(xiàng)顯然是從R1產(chǎn)生的，因此：R1不處理表項(xiàng)中下一跳為R1的內(nèi)容，從而杜絕信息的回傳R1R2R3R4111到R1的距離123R1到R2鏈路中斷后消失消失(不處理)3消失消失消失(不處理)R1R2R3R41111水平分割失效的情形73ACBD當(dāng)B到D的鏈路斷掉后，一種可能的情形：B告訴A、C：D不可達(dá)A重新選路，正好收到C告知D有兩跳（C還沒收到B的更新信息）A選擇到D經(jīng)過C，距離為三跳A告知B：D有三跳B選擇到D經(jīng)過A，距離為四跳C收到B先前的D不可達(dá)更新，重新選路B告知C：D有四跳C選擇到D經(jīng)過B，距離為五跳出現(xiàn)路由環(huán)路，并計數(shù)到無窮大網(wǎng)絡(luò)拓?fù)浯嬖诃h(huán)路時，水平分割失效74DV協(xié)議的改進(jìn)改進(jìn)2：毒性逆轉(zhuǎn)發(fā)現(xiàn)鏈路斷開(路由消失),由原來的悄然刪除，改為向外擴(kuò)散“距離無窮大”的路由(通知路由消失)節(jié)點(diǎn)將從某節(jié)點(diǎn)收到的信息再傳回給該節(jié)點(diǎn)時，距離置為無窮大，告訴對方不能從我這過改進(jìn)3：觸發(fā)更新收到路由信息有距離無窮大路由項(xiàng)，直接更新對應(yīng)的路由表項(xiàng)(不再用距離判定是否更新)改進(jìn)4：更新抑制當(dāng)路由項(xiàng)的距離更新為無窮時，不是刪除它，而是保留一段時間不更新，直到該信息傳遍整個網(wǎng)絡(luò)75距離矢量路由—小節(jié)特點(diǎn)：只與鄰節(jié)點(diǎn)交換路由信息各節(jié)點(diǎn)獨(dú)立計算最優(yōu)路徑（但依賴鄰居的計算結(jié)果）能適應(yīng)網(wǎng)絡(luò)拓?fù)涞淖兓?，穩(wěn)定后，形成最短路徑算法簡單缺點(diǎn)：交換路由信息分組長度分組長度與路由表項(xiàng)數(shù)量成正比網(wǎng)絡(luò)變化擴(kuò)散到全網(wǎng)速度慢擴(kuò)散速度：所有節(jié)點(diǎn)都發(fā)現(xiàn)變化的速度路由收斂慢收斂速度：大家分別計算，結(jié)果達(dá)到統(tǒng)一的速度當(dāng)拓?fù)浣Y(jié)構(gòu)、距離參數(shù)變化頻繁時，算法可能不收斂存在路由環(huán)－－在網(wǎng)絡(luò)變化未擴(kuò)散完全時。實(shí)用協(xié)議：RIP適合于變化較慢的小網(wǎng)★76DV協(xié)議—實(shí)驗(yàn)實(shí)驗(yàn)者工作在網(wǎng)絡(luò)的某個節(jié)點(diǎn)上直連節(jié)點(diǎn)為該節(jié)點(diǎn)的鄰居節(jié)點(diǎn)實(shí)驗(yàn)內(nèi)容1、根據(jù)鄰居節(jié)點(diǎn)信息形成路由表2、形成路由信息向各鄰居擴(kuò)散3、根據(jù)接收路由信息更新路由表4、重復(fù)(2、3)，直到路由表穩(wěn)定不變EBCDF本節(jié)點(diǎn)收到路由信息形成路由表發(fā)送路由信息定期考查點(diǎn)：如何更新路由表考查點(diǎn)：如何形成路由信息應(yīng)該向誰發(fā)送初始狀態(tài)考查點(diǎn)：如何形成路由表773.3鏈路狀態(tài)路由★回顧：DV協(xié)議路由算法累積型最佳路由計算D(S,D)=min(D(S,R(i))+D(R(i),D))R(i)∈{S的鄰居節(jié)點(diǎn)}從鄰居的最佳路由累積而成路由狀態(tài)變化時，需要很長時間才能(收斂)穩(wěn)定DV協(xié)議收斂慢的原因分析累積型路由計算等待鄰居計算出最佳路由之后，才能計算出自己的最佳路由協(xié)議算法實(shí)現(xiàn)鄰居間相互依賴和相互等待結(jié)果，導(dǎo)致周期性更新動作78鏈路狀態(tài)路由如何避免等待鄰居的計算結(jié)果？掌握其它節(jié)點(diǎn)(不限于鄰居)的鏈路狀態(tài)信息不依賴其它節(jié)點(diǎn)的計算結(jié)果鏈路狀態(tài)路由算法思想若節(jié)點(diǎn)能收集到網(wǎng)絡(luò)上所有鏈路的狀態(tài)信息鏈路狀態(tài)：鏈路兩端的節(jié)點(diǎn)、鏈路的距離可重構(gòu)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)進(jìn)而可獨(dú)立計算到任意節(jié)點(diǎn)的最佳路由最短路徑優(yōu)先(SPF，ShortestPathFirst)鏈路狀態(tài)路由協(xié)議（LS或SPF）：收集所有鏈路狀態(tài)信息重構(gòu)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)計算自己到任意節(jié)點(diǎn)最佳路由形成到下一跳的FIT表鏈路狀態(tài)改變鏈路狀態(tài)路由節(jié)點(diǎn)間信息交互79重構(gòu)網(wǎng)絡(luò)拓?fù)渚W(wǎng)絡(luò)鏈路連接矩陣FAHK242B4D3G2E3O5L2從F節(jié)點(diǎn)重構(gòu)網(wǎng)絡(luò)原網(wǎng)絡(luò)2ABCDEIHGLFKNOMJ552245322321224232311252180Dijkstra最短路徑算法對任意網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，從任意一點(diǎn)出發(fā)到其余所有點(diǎn)最短路徑的計算方法便于計算機(jī)處理的經(jīng)典算法已找到最短路徑的節(jié)點(diǎn)正處理的節(jié)點(diǎn)未處理的節(jié)點(diǎn)出發(fā)節(jié)點(diǎn)S到S距離最短的節(jié)點(diǎn)K第i步KK的鄰居S0S1S2重復(fù)第i步，直到S2為空、S1為空81Dijkstra算法步驟設(shè)：源節(jié)點(diǎn)為F第一步：以F為起始，向所有可能路徑前進(jìn)一步FHK242AABCDEIHGLFKNOMJ5522453223212242323112521S0={F}S1={A,H,K}S2={…}82Dijkstra最短路徑算法第二步：在已有路徑中選擇最短的繼續(xù)前進(jìn)圖中的A和KFHK242B4D3G2L2AABCDEIHGLFKNOMJ5522453223212242323112521S0={F,A,K}S1={H,B,D,G,L}S0={F}S1={A,H,K}A,KA(B,D,G)K(L)83Dijkstra最短路徑算法重復(fù)第二步在已有路徑中選擇最短的繼續(xù)前進(jìn)路徑出現(xiàn)閉合點(diǎn)D、G、H處理：刪除閉合點(diǎn)到F的距離長的一條(圖中虛線)FHK242B4D3G2L2AABCDEIHGLFKNOMJ55224532232122423231125211M22E3O5S0={F,A,K,H,G,L}S1={B,D,E,O,M}84Dijkstra最短路徑算法重復(fù)第二步在已有路徑中選擇最短的繼續(xù)前進(jìn)注意：G已沒有后續(xù)路徑可用(不在考慮之列)同樣，刪除閉合點(diǎn)的一條長路徑FHK242B4D3G2L2AM2E3O5I22ABCDEIHGLFKNOMJ552245322321224232311252185Dijkstra最短路徑算法重復(fù)第二步在已有路徑中選擇最短的繼續(xù)前進(jìn)同樣，刪除閉合點(diǎn)的一條長路徑FHK242B4D3G2L2AM2E3O5I2C155N4ABCDEIHGLFKNOMJ552245322321224232311252186Dijkstra最短路徑算法重復(fù)第二步在已有路徑中選擇最短的繼續(xù)前進(jìn)同樣，刪除閉合點(diǎn)的一條長路徑(注意B-C)FHK242B4D3G2L2AM2E3O5I2C5N42J23ABCDEIHGLFKNOMJ552245322321224232311252187Dijkstra最短路徑算法重復(fù)第二步在已有路徑中選擇最短的一條繼續(xù)前進(jìn)同樣，刪除閉合點(diǎn)的長路徑FHK242B4D3G2L2AM2E3O5I2CN42J2ABCDEIHGLFKNOMJ55224532232122423231125213188Dijkstra最短路徑算法到達(dá)最后一個節(jié)點(diǎn)，無鏈路可前行—完成計算形成從F到所有節(jié)點(diǎn)的最短路徑FHK242B4D3G2L2AM2E3O5I2CN42J2ABCDEIHGLFKNOMJ5522453223212242323112521Dijkstra算法總結(jié)：讓短路徑傳輸?shù)摹案h(yuǎn)”89Dijkstra最短路徑算法AtoD最短路徑發(fā)現(xiàn)過程臨時性標(biāo)注永久性標(biāo)注90形成FIT表F的FIT表F計算出全部最短到所有節(jié)點(diǎn)，最終以A、H、K之一作為下一跳ABCDEIHGLFKNOMJ5522453223212242323112521AABACADAEHGAHHIAJAKKLKMKNKOH目的下一跳91鏈路狀態(tài)路由協(xié)議目標(biāo)節(jié)點(diǎn)間信息交互，獲得全網(wǎng)所有鏈路信息協(xié)議操作內(nèi)容鏈路狀態(tài)維護(hù)(感知“通”或“斷”)定時的Hello報文溝通測量鏈路“距離”延時、排隊(duì)長度、信道速率、節(jié)點(diǎn)負(fù)載等參數(shù)“距離”

=1個或多個參數(shù)的組