Internet核心原理與應(yīng)用技術(shù) 第6章 Internet路由算法

《Internet核心原理與應(yīng)用技術(shù) 第6章 Internet路由算法》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、第6章Internet路由算法6.26.36.4基本概念6.1距離向量路由算法6.2鏈路狀態(tài)路路選擇算法6.3其他路由選擇算法6.46.1基本概念6.1.1網(wǎng)際互連的基本概念圖6.1Internet的物理網(wǎng)絡(luò)互連示意圖1．同構(gòu)網(wǎng)絡(luò)的網(wǎng)際互連2．相似網(wǎng)絡(luò)的網(wǎng)際互連3．異構(gòu)網(wǎng)絡(luò)的網(wǎng)際互連圖6.2基于轉(zhuǎn)發(fā)器的同構(gòu)網(wǎng)絡(luò)網(wǎng)際互連圖6.3基于網(wǎng)橋/交換機(jī)的相似網(wǎng)絡(luò)網(wǎng)際互連圖6.4基于路由器/3層交換機(jī)的異構(gòu)網(wǎng)絡(luò)網(wǎng)際互連6.1.2路由選擇的基本概念1．路由選擇的通信設(shè)備2．路由選擇的原理路由選擇包括兩項(xiàng)基本內(nèi)容：選擇最優(yōu)路徑和轉(zhuǎn)發(fā)IP分組。選擇最優(yōu)路徑就是判定到達(dá)目標(biāo)端的最佳路徑的下一站，由路由

2、選擇算法來實(shí)現(xiàn)。轉(zhuǎn)發(fā)IP分組就是按照選擇好的最佳路徑傳送信息分組。3．路由選擇考慮的問題（1）路由選擇由誰完成（2）路由選擇什么時(shí)間完成（3）“最佳路徑”的標(biāo)準(zhǔn)是什么4．路由選擇的方式典型的路由選擇方式有兩種：靜態(tài)路由和動(dòng)態(tài)路由。（1）路由表中在計(jì)算和設(shè)置后不再改變，稱為靜態(tài)路由。圖6.55個(gè)路由器組成的網(wǎng)絡(luò)的圖示（2）當(dāng)網(wǎng)絡(luò)變化時(shí)路由表的信息要隨時(shí)進(jìn)行更新，稱為動(dòng)態(tài)路由。6.2距離向量路由算法6.2.1距離向量路由算法描述距離向量路由算法（DistanceVectorRouting）是最早采用的一種路由選擇算法。變量定義：源節(jié)點(diǎn)i的距離向量Di，后繼節(jié)點(diǎn)向量Si表示為，其中，Di

3、j表示從節(jié)點(diǎn)到節(jié)點(diǎn)的最小距離；Sij表示從節(jié)點(diǎn)到節(jié)點(diǎn)的最短路徑的下一站；n表示網(wǎng)絡(luò)中的路由節(jié)點(diǎn)數(shù)。初始值：Dii=0，Sii=?若i與j為相鄰節(jié)點(diǎn)，則Dij的初值為i與j之間的距離，而Sij的初始值為j；若i與j不相鄰，則Dij的初值為∞，而Sij的初始值待定（空值）。算法：節(jié)點(diǎn)i收到各相鄰節(jié)點(diǎn)k的距離向量Dk和后繼節(jié)點(diǎn)向量Sk后,把DkSk更換為　　和對(duì)于j從1到n，{選取相鄰節(jié)點(diǎn)　　，滿足[Div+Dvj=(Dik+Dkj)]，則{}}6.2.2距離向量路由算法舉例圖6.66個(gè)路由節(jié)點(diǎn)的網(wǎng)絡(luò)拓?fù)鋱D6.3鏈路狀態(tài)路由選擇算法6.3.1鏈路狀態(tài)路由算法描述鏈路狀態(tài)路由算法的基本思想

4、是：每個(gè)路由節(jié)點(diǎn)維持一個(gè)網(wǎng)絡(luò)拓?fù)湫畔?shù)據(jù)庫，這個(gè)數(shù)據(jù)庫也稱為鏈路狀態(tài)庫，它包含各個(gè)節(jié)點(diǎn)的鏈路狀態(tài)包。典型的鏈路狀態(tài)包包括包的序號(hào)、該節(jié)點(diǎn)的標(biāo)識(shí)、該節(jié)點(diǎn)的相鄰節(jié)點(diǎn)和該節(jié)點(diǎn)到相鄰節(jié)點(diǎn)的距離。6.3.2鏈路狀態(tài)路由算法實(shí)例圖6.7鏈路狀態(tài)路由算法構(gòu)建的最短路徑節(jié)點(diǎn)樹6.4其他路由選擇算法1．單路徑與多路徑路由選擇算法單路徑路由選擇算法，是通過路由器中的路由表選擇一條最優(yōu)路徑來轉(zhuǎn)發(fā)數(shù)據(jù)包。2．平面結(jié)構(gòu)與分層結(jié)構(gòu)路由選擇算法平面結(jié)構(gòu)路由選擇算法應(yīng)用于單層次的路由系統(tǒng)，單層次的路由系統(tǒng)中所有的路由器都是對(duì)等的，沒有主次之分。3．主機(jī)智能與路由器智能路由選擇算法主機(jī)智能算法就是指由數(shù)據(jù)包的發(fā)送方

5、決定整個(gè)傳輸過程中的完整路由，通常也被稱為源路由。4．域間與域內(nèi)路由選擇算法