上海交通大學(xué)計算機網(wǎng)絡(luò)課件第5章翁惠玉

第5章網(wǎng)絡(luò)層網(wǎng)絡(luò)層主要解決的問題路由選擇網(wǎng)絡(luò)互連擁塞控制為上層提供服務(wù)第5章網(wǎng)絡(luò)層網(wǎng)絡(luò)層設(shè)計的相關(guān)問題路由算法擁塞控制服務(wù)質(zhì)量網(wǎng)絡(luò)互聯(lián)因特網(wǎng)中的網(wǎng)絡(luò)層網(wǎng)絡(luò)層的設(shè)計存儲轉(zhuǎn)發(fā)的數(shù)據(jù)包交換為傳輸層提供的服務(wù)面向無連接服務(wù)的實現(xiàn)面向連接服務(wù)的實現(xiàn)虛電路子網(wǎng)和數(shù)據(jù)報子網(wǎng)的比較存儲轉(zhuǎn)發(fā)的數(shù)據(jù)包交換數(shù)據(jù)包Packet存儲轉(zhuǎn)發(fā)StoreandForward路由器Router交換Switching通信子網(wǎng)CommunicationSubnet資源子網(wǎng)ResourceSubnet網(wǎng)絡(luò)層協(xié)議環(huán)境A1BCDEFRouterCarrier’sequipmentLANPacketH1H2ProcessP1ProcessP1TnbmP344Fig.5-1網(wǎng)絡(luò)層協(xié)議環(huán)境網(wǎng)絡(luò)層的設(shè)計存儲轉(zhuǎn)發(fā)的數(shù)據(jù)包交換為傳輸層提供的服務(wù)面向無連接服務(wù)的實現(xiàn)面向連接服務(wù)的實現(xiàn)虛電路子網(wǎng)和數(shù)據(jù)報子網(wǎng)的比較為傳輸層提供的服務(wù)服務(wù)應(yīng)與路由器技術(shù)無關(guān)路由器的數(shù)量、類型和拓?fù)浣Y(jié)構(gòu)對于傳輸層來說應(yīng)是不可見的傳輸層所能獲得的網(wǎng)絡(luò)地址應(yīng)采用統(tǒng)一的編址方式，并允許跨越多個LAN和WAN網(wǎng)絡(luò)層提供的服務(wù)類型面向無連接服務(wù)：網(wǎng)絡(luò)是不可靠的，網(wǎng)絡(luò)服務(wù)不應(yīng)面向連接，分組的排序和流控制應(yīng)不屬于網(wǎng)絡(luò)層，每個分組都單獨尋徑，所以必須攜帶完整的目的地址如Internet面向連接的服務(wù)：網(wǎng)絡(luò)應(yīng)該提供可靠的、面向連接的服務(wù)，否則服務(wù)質(zhì)量將無從談起，尤其對于多媒體應(yīng)用如

ATM對于網(wǎng)絡(luò)層提供的服務(wù)有兩種觀點：網(wǎng)絡(luò)層的設(shè)計存儲轉(zhuǎn)發(fā)的數(shù)據(jù)包交換為傳輸層提供的服務(wù)面向無連接服務(wù)的實現(xiàn)面向連接服務(wù)的實現(xiàn)虛電路子網(wǎng)和數(shù)據(jù)報子網(wǎng)的比較面向無連接服務(wù)的實現(xiàn)（數(shù)據(jù)報子網(wǎng)）路由器A按左邊的路由表運行，后來發(fā)現(xiàn)如到E和F應(yīng)該走B才更好，于是更新路由表A3BCDEFRouterCarrier’sequipmentLANPacketH1H2ProcessP1ProcessP1241A-BBCCDBECFCA-BBCCDBEBFBAABAC-DDEEFEACBDCCDDE-FFA的路由表E的路由表C的路由表TnbmP346Fig.5-2數(shù)據(jù)報子網(wǎng)中分組的尋徑網(wǎng)絡(luò)層的設(shè)計存儲轉(zhuǎn)發(fā)的數(shù)據(jù)包交換為傳輸層提供的服務(wù)面向無連接服務(wù)的實現(xiàn)面向連接服務(wù)的實現(xiàn)虛電路子網(wǎng)和數(shù)據(jù)報子網(wǎng)的比較面向連接服務(wù)的實現(xiàn)（虛電路子網(wǎng)）H1和H2已建立了1#連接H3要和H2建立連接只能是2#H11H31入口F1F2出口E1E2出口C1C2出口A的路由表TnbmP348Fig.5-3虛電路子網(wǎng)中分組的尋徑A3BCDEFRouterCarrier’sequipmentLANPacketH1H2ProcessP1ProcessP1241H3ProcessP3A1A2入口C的路由表C1C2入口E的路由表網(wǎng)絡(luò)層的設(shè)計存儲轉(zhuǎn)發(fā)的數(shù)據(jù)包交換為傳輸層提供的服務(wù)面向無連接服務(wù)的實現(xiàn)面向連接服務(wù)的實現(xiàn)虛電路子網(wǎng)和數(shù)據(jù)報子網(wǎng)的比較虛電路子網(wǎng)和數(shù)據(jù)報子網(wǎng)的比較數(shù)據(jù)報子網(wǎng)虛電路子網(wǎng)建立電路連接不需要需要尋址每個分組包含完整的源和目的地址每個分組包含一個很短的虛電路號狀態(tài)信息路由器不保留連接的狀態(tài)信息每條虛電路要求為每個連接提供路由表空間尋徑路由器為每個分組獨立尋徑尋徑在虛電路建立時完成，此后，所以分組按此路徑傳輸路由器故障的影響除路由器崩潰，所以分組丟失，否則無影響所有通過該故障路由器的虛電路全部終止服務(wù)質(zhì)量困難對每條虛電路，沿途的路由器如有足夠的資源可分配，則很容易實現(xiàn)擁塞控制困難對每條虛電路，沿途的路由器如有足夠的資源可分配，則很容易實現(xiàn)TnbmP349Fig.5-4虛電路子網(wǎng)和數(shù)據(jù)報子網(wǎng)的比較虛電路子網(wǎng)/數(shù)據(jù)報子網(wǎng)的比較(續(xù))虛電路子網(wǎng)通過路徑選擇后建立連接分組按序傳輸服務(wù)質(zhì)量能得到保證通信后撤銷連接適合于實時傳輸數(shù)據(jù)報子網(wǎng)每個分組分別選擇最佳路徑，健壯性較好整個網(wǎng)絡(luò)系統(tǒng)的信道利用率高，成本低差錯控制和排序工作由協(xié)議高層（主機）完成適合于非實時傳輸?shù)?章網(wǎng)絡(luò)層網(wǎng)絡(luò)層設(shè)計的相關(guān)問題路由算法擁塞控制服務(wù)質(zhì)量網(wǎng)絡(luò)互聯(lián)因特網(wǎng)中的網(wǎng)絡(luò)層路由算法路由算法是網(wǎng)絡(luò)層軟件的一個重要部分，它決定進(jìn)入的分組應(yīng)從哪一根輸出線傳輸如果是數(shù)據(jù)報子網(wǎng)，將在每一個分組到達(dá)時作此決定如果是虛電路子網(wǎng)，是在虛電路建立時決定，該連接上所有分組都將沿此線路傳輸路由與轉(zhuǎn)發(fā)：路由是尋徑，轉(zhuǎn)發(fā)是當(dāng)一個分組到達(dá)時發(fā)生的動作路由算法（續(xù)）路由算法設(shè)計必須考慮的問題

正確性簡單性健壯性

穩(wěn)定性

公平性最優(yōu)性路由算法中的度量標(biāo)準(zhǔn)路徑長度hop數(shù)延遲時間路由算法的分類靜態(tài)算法自適應(yīng)算法拓?fù)湎嚓P(guān)的路由算法移動節(jié)點的路由Ad-hoc網(wǎng)絡(luò)的路由靜態(tài)算法（staticrouting）最短路徑算法（Dijkstra）擴散法（flooding）為路由器配置一張最優(yōu)的路由表最短路由選擇（Dijkstra）

Dijkstra算法（1959）：通過用邊的權(quán)值作為距離的度量來計算最短路徑，有最少邊數(shù)的路徑不一定是最短路徑1674329115328635如下圖：5和4之間邊數(shù)最少的路徑是5234但最短路徑是523674采用的數(shù)據(jù)結(jié)構(gòu)集合S：尚未找到最短路徑的節(jié)點 的集合數(shù)組R：R[i]為從指定源點去節(jié)點i 的路徑上，節(jié)點i的前一個 節(jié)點數(shù)組D：D[i]為從指定源點到節(jié)點i 的最短距離算法的初始化初始化集合S為除源節(jié)點外的所有節(jié)點初始化數(shù)組D：如果從源節(jié)點到節(jié)點v的邊存在，則D(v)為該邊的權(quán)值，否則為無窮大初始化數(shù)組R：如果從源節(jié)點到節(jié)點v的邊存在，則R(v)為源節(jié)點，否則為0算法WHILE（集合S非空）

{從S中選一節(jié)點u，使D[u]最?。? 如果（D[u]為無窮大）

{錯誤！無路徑存在，退出}

把u從S中刪去； 對(u,v)是邊的每個節(jié)點v {如果（v仍在S中）

C=D[u]+weight(u,v);

如果（C<D[v]）/*v找到了一條更短的路徑*/ {R[v]=u;/*替換v的最短路徑及長度*/ D[v]=C; } } }從5出發(fā)到各個節(jié)點的最短路徑SR1D1R2D2R3D3R4D4R6D6R7D7u{1,2,3,4,6,7}59560∞0∞0∞0∞2{1,3,4,6,7}5956290∞2140∞1{3,4,6,7}5956290∞2140∞3{4,6,7}5956293203110∞6{4,7}5956293203116167{4}5956297193116164靜態(tài)算法（staticrouting）最短路徑算法（Dijkstra）擴散法（flooding）為路由器配置一張最優(yōu)的路由表擴散法（flooding）

不計算路徑，有路就走1567432911532863如從5出發(fā)到4：數(shù)據(jù)包從51,2；23,6；36,4；63,7；74要解決的問題：數(shù)據(jù)包重復(fù)到達(dá)某一節(jié)點，如3，6擴散法（續(xù)）

解決方法在數(shù)據(jù)包頭設(shè)一計數(shù)器初值，每經(jīng)過一個節(jié)點自動減1，計數(shù)值為0時，丟棄該數(shù)據(jù)包在每個節(jié)點上建立登記表，則數(shù)據(jù)包再次經(jīng)過時丟棄缺點：重復(fù)數(shù)據(jù)包多，浪費帶寬優(yōu)點：可靠性高，路徑最短，常用于軍事路由算法的分類靜態(tài)算法自適應(yīng)算法拓?fù)湎嚓P(guān)的路由算法移動節(jié)點的路由Ad-hoc網(wǎng)絡(luò)的路由

自適應(yīng)算法是動態(tài)的、分布式的算法實現(xiàn)分布式算法的三要素：Themeasurementprocess（測量）Theupdateprotocol（更新協(xié)議）Thecalculation（計算）自適應(yīng)算法（adaptivealgorithm）自適應(yīng)算法（adaptivealgorithm）距離矢量算法（D-V）鏈路狀態(tài)算法（L-S）路由器動態(tài)建立和維護一張最優(yōu)的路由表D-V算法的工作原理每個路由器用兩個向量Di和Si來表示該點到網(wǎng)上所有節(jié)點的路徑距離及其下一個節(jié)點相鄰路由器之間交換路徑信息各節(jié)點根據(jù)路徑信息更新路由表

di1：從節(jié)點i到節(jié)點1的時延向量di2：從節(jié)點i到節(jié)點2的時延向量

Di=di1di2di3…dinSi=si1si2si3…sinsi1：從節(jié)點i到節(jié)點1的一條最小時延路徑上的下一個節(jié)點si2：從節(jié)點i到節(jié)點2的一條最小時延路徑上的下一個節(jié)點其中：n—網(wǎng)絡(luò)中的節(jié)點數(shù)Di—節(jié)點i的時延向量dij—節(jié)點i到j(luò)的最小時延的當(dāng)前估計值Si—節(jié)點i的后繼節(jié)點向量sij—從節(jié)點i到j(luò)的最小時延路徑上的下一節(jié)點

路由表的更新dij=min(dix+dxj)(xA)（從i到j(luò)的時延取途經(jīng)每個節(jié)點時的時延的最小值）

Sij=x（從i到j(luò)途經(jīng)的下一個節(jié)點為x）

其中：A—與i相鄰的所有節(jié)點的集合dij—i到j(luò)的最短距離dix—i到x的最短距離dxj—x到j(luò)的最短距離

To通過A通過I通過H通過KA0242021B12363128C25181936D4027824E1473022F23201940G1831631H1720019I2101422J911710K2422220L293399J到A延時為8J到I延時為10J到H延時為12J到K延時為6線路8A20A28I20H17I30I18H12H10I0-6K15K節(jié)點J的新路由表注意：AI為21；IA為24因為：往和返的信道流量不一定相同，節(jié)點A和I也并非在同一時刻測得，且線路狀態(tài)是動態(tài)變化的J重新估計的延時所謂節(jié)點即路由器當(dāng)前節(jié)點為JAEIHGFDCBLKJTnbmP358Fig.5-9D-V算法的路由表更新D-V算法的缺點交換的路徑信息量大路徑信息不一致收斂速度慢（壞消息）不適合大型網(wǎng)絡(luò)無窮計算問題好消息傳播得快，壞消息傳播得慢ABCDE∞∞∞∞初始時1∞∞∞第1次交換后12∞∞第2次交換后123∞第3次交換后1234第4次交換后ABCDE1234初始時3234第1次交換后3434第2次交換后5454第3次交換后5656第4次交換后7676第5次交換后7878第6次交換后…………∞∞∞∞A下網(wǎng)了TnbmP359Fig.5-10無窮計算問題克服收斂速度慢的方法水平分裂同距離矢量法，只是到X的距離并不是真正的距離，對下方點通知真正的距離，對上方點，給出無窮大如上圖中的C點，它向D通知到A的是真正距離，而向B通知到A的距離是無窮大Holddown當(dāng)發(fā)現(xiàn)不通時，不重新選路徑，而是把它設(shè)成無窮大這些方法尚在研究之中自適應(yīng)算法（adaptivealgorithm）距離矢量算法（D-V）鏈路狀態(tài)算法（L-S）路由器動態(tài)建立和維護一張最優(yōu)的路由表鏈路狀態(tài)算法（L-S）

（LinkStateRouting）

基本思想：發(fā)現(xiàn)它的鄰接節(jié)點，并得到其網(wǎng)絡(luò)地址測量它到各鄰接節(jié)點的延遲或開銷組裝一個分組以告知它剛知道的所有信息將這個分組發(fā)給所有其他路由器計算到每個其他路由器的最短路徑發(fā)現(xiàn)鄰接節(jié)點當(dāng)一個路由器啟動后，向每個點到點線路發(fā)送HELLO分組（攜帶自己的網(wǎng)絡(luò)地址），另一端的路由器發(fā)送回來一個應(yīng)答來說明它是誰，即通報其網(wǎng)絡(luò)地址鏈路狀態(tài)算法（L-S）

（LinkStateRouting）

基本思想：發(fā)現(xiàn)它的鄰接節(jié)點，并得到其網(wǎng)絡(luò)地址測量它到各鄰接節(jié)點的延遲或開銷組裝一個分組以告知它剛知道的所有信息將這個分組發(fā)給所有其他路由器計算到每個其他路由器的最短路徑測量線路開銷發(fā)送一個ECHO分組要求對方立即響應(yīng)，通過測量一個來回時間再除以2，發(fā)送方就可以得到一個延遲估計值，想要更精確些，可以重復(fù)這一過程，取其平均值鏈路狀態(tài)算法（L-S）

（LinkStateRouting）

基本思想：發(fā)現(xiàn)它的鄰接節(jié)點，并得到其網(wǎng)絡(luò)地址測量它到各鄰接節(jié)點的延遲或開銷組裝一個分組以告知它剛知道的所有信息將這個分組發(fā)給所有其他路由器計算到每個其他路由器的最短路徑構(gòu)造分組子網(wǎng)及其節(jié)點到其鄰節(jié)點（路由器）的線路開銷測量值（即延時，假設(shè)以ms計）ABCDEF序號序號序號序號序號序號年齡年齡年齡年齡年齡年齡B4A4B2C3A5B6E5C2D3

F7

C1

D7F6E1F8E8AE324FDCB56187子網(wǎng)的鏈路、狀態(tài)及分組情況：

節(jié)點A僅與節(jié)點B和E相鄰AB的時延為4msAE的時延為5ms

TnbmP363Fig.5-13L-S算法的路由表更新鏈路狀態(tài)算法（L-S）

（LinkStateRouting）

基本思想：發(fā)現(xiàn)它的鄰接節(jié)點，并得到其網(wǎng)絡(luò)地址測量它到各鄰接節(jié)點的延遲或開銷組裝一個分組以告知它剛知道的所有信息將這個分組發(fā)給所有其他路由器計算到每個其他路由器的最短路徑發(fā)布鏈路狀態(tài)分組用擴散法（向鄰接的節(jié)點）發(fā)布鏈路狀態(tài)分組（以B為例，B的鄰接點有A、C、F）源序號年齡ACFACF數(shù)據(jù)A2160011100

F2160110001

E2159010101

C2060101010

D2159100011

源節(jié)點E的鏈路狀態(tài)分組經(jīng)A和F到節(jié)點B，節(jié)點B必須再將E的狀態(tài)分組轉(zhuǎn)送到C，并向A和F發(fā)ACK

發(fā)送標(biāo)志ACK標(biāo)志TnbmP365Fig.5-14鏈路狀態(tài)分組的轉(zhuǎn)發(fā)和確認(rèn)存在的問題狀態(tài)分組的重復(fù)到達(dá)如果序號循環(huán)使用，就會發(fā)生重復(fù)如果一個路由器被重起，序號將從0開始重新計數(shù)，但這些分組會被當(dāng)成過時分組如果序號發(fā)生錯誤（如序號用32位表示，4被看成65540，第16位的0被誤傳成了1），則很多分組將被看成過時分組（此時5~65539均為過時分組，因為當(dāng)前的分組序號是65540）解決辦法使用一個32位序號，即使每秒鐘發(fā)送一個分組，137年才會循環(huán)一次在每個分組中加一年齡字段（如初值為60），每秒鐘將年齡減1，為0后該分組將被丟棄，否則不會被認(rèn)為是過時分組鏈路狀態(tài)算法（L-S）

（LinkStateRouting）

基本思想：發(fā)現(xiàn)它的鄰接節(jié)點，并得到其網(wǎng)絡(luò)地址測量它到各鄰接節(jié)點的延遲或開銷組裝一個分組以告知它剛知道的所有信息將這個分組發(fā)給所有其他路由器計算到每個其他路由器的最短路徑計算新路由用Dijkstra算法計算到每個節(jié)點的路由得到該節(jié)點到每個節(jié)點的最短路徑L-S路由算法的優(yōu)缺點LSR的優(yōu)點路由信息的一致性好，壞消息也一樣傳播得快狀態(tài)分組的長度較短，僅包含到鄰接點的距離、序號和年齡等，與網(wǎng)絡(luò)規(guī)模關(guān)系不大，傳輸所耗用的網(wǎng)絡(luò)帶寬不大，此外，狀態(tài)分組的擴散，由于年齡參數(shù)的設(shè)定，不會無限制擴散，所以可適用于大型網(wǎng)絡(luò)LSR的缺點每個路由器需要有較大的存儲空間，用以存儲所收到的每一個節(jié)點的鏈路狀態(tài)分組計算工作量大，每次都必須計算最短路徑路由算法的分類靜態(tài)算法自適應(yīng)算法拓?fù)湎嚓P(guān)的路由算法移動節(jié)點的路由Ad-hoc網(wǎng)絡(luò)的路由拓?fù)湎嚓P(guān)的路由算法分層路由廣播路由多址傳輸路由選擇Peer-to-Peer網(wǎng)的節(jié)點查找分層路由隨著網(wǎng)絡(luò)規(guī)模的增長，存儲和處理路由表所需的資源也急劇增長，從拓?fù)渖戏謱邮墙鉀Q問題的一個方法分層的概念：將路由器分成組，每一路由器知道到組內(nèi)任何一臺路由器的路由，以及到其他組的路由，因此可把其他組中所有的路由器抽象成一個，以減少路由表的長度分層實例不分層時1A的路由表目的地下一跳跳數(shù)1A----1B1B11C1C12A1B22B1B32C1B32D1B43A1C33B1C24A1C34B1C44C1C45A1C45B1C55C1B55D1C65E1C5分層時1A的路由表目的地下一跳跳數(shù)1A----1B1B11C1C121B231C241C351C4TnbmP367Fig.5-15分層路由5D5A5B5C5E4A4B4C3A3B1A1B1C2A2B2C2D區(qū)域1區(qū)域5區(qū)域3區(qū)域2區(qū)域4分層的層數(shù)Kamoun和Kleinrock發(fā)現(xiàn)：N個路由器的最優(yōu)層次數(shù)是lnN，每個路由器需要elnN個路由表項拓?fù)湎嚓P(guān)的路由算法分層路由廣播路由多址傳輸路由選擇Peer-to-Peer網(wǎng)的節(jié)點查找廣播路由逐個向所有節(jié)點分別發(fā)送報文缺點：發(fā)送量大 需知道網(wǎng)上所有節(jié)點的地址擴散法缺點：流量大，消耗大量帶寬 某些節(jié)點還可能收到重復(fù)的報文廣播路由算法多目的地路由生成樹算法逆向路徑傳送多目的地路由

分組中包含需到達(dá)的多個目的地的地址表到一個節(jié)點時，路由器檢查所有的目的地址表，確定輸出線路集合，路由器為每一條輸出線路復(fù)制一個新的分組，每個分組中僅含有要用此線路的目的地址表優(yōu)點：流量小，節(jié)約帶寬缺點：費用承擔(dān)不公平廣播路由算法多目的地路由生成樹算法逆向路徑傳送生成樹算法

路由器將分組沿生成樹發(fā)送（除進(jìn)入線路之外）優(yōu)點：帶寬得到最佳利用缺點：每個路由器必須知道其可用生成樹如鏈路狀態(tài)路由算法可得到生成樹，距離矢量路由算法卻不能得到廣播路由算法多目的地路由生成樹算法逆向路徑傳送逆向路徑傳送基本原理：當(dāng)某一廣播分組到達(dá)路由器時，路由器對它進(jìn)行檢查，如該分組來自通常向廣播源發(fā)送分組的線路，則將該分組轉(zhuǎn)發(fā)到除進(jìn)線以外的其它線路，否則丟棄

(a)一個子網(wǎng)ABCDEHFGIJKLMNOABCDEHFGIJKLMNO(b)一棵匯集樹TnbmP369Fig.5-16逆向路徑傳送逆向路徑傳送說明在(a)的子網(wǎng)中，每個節(jié)點都已生成了一張路由表，假設(shè)當(dāng)前每個節(jié)點的路由表中到節(jié)點I去的路徑中的下一跳分別為：

當(dāng)前節(jié)點ABCDEFGHJKLMNO到I去的下一節(jié)點FCDFAIJIIMKNIJ逆向路徑傳送說明（續(xù)1）根據(jù)上述逆向路徑轉(zhuǎn)發(fā)的原則，可構(gòu)造如下一棵樹(c)由逆向路徑轉(zhuǎn)發(fā)構(gòu)造的樹MHKJIHGFEDCBAONOKEGLLDNBTnbmP369Fig.5-16逆向路徑傳送HMHKJIHGFEDCBAONOKEGLLDNBTnbmP369Fig.5-16逆向路徑傳送H逆向路徑傳送說明（續(xù)2）如節(jié)點F收到一個從I來的分組，則立即向節(jié)點A和節(jié)點D轉(zhuǎn)發(fā)當(dāng)節(jié)點D收到一個經(jīng)F來的節(jié)點I的分組，它意識到如它有分組要送給I的話，是走節(jié)點F的，所以立即向節(jié)點C和G轉(zhuǎn)發(fā)當(dāng)節(jié)點G收到一個經(jīng)D來的節(jié)點I的分組，它意識到如它有分組要送給I的話，是走節(jié)點J而不是走節(jié)點D的，所以它不再轉(zhuǎn)發(fā)所以：經(jīng)過5個站點共24個分組的轉(zhuǎn)發(fā)后，廣播算法結(jié)束優(yōu)點：算法合理，容易實現(xiàn)缺點：對大型網(wǎng)絡(luò)不適用拓?fù)湎嚓P(guān)的路由算法分層路由廣播路由多址傳輸路由選擇Peer-to-Peer網(wǎng)的節(jié)點查找多址傳輸路由選擇

(MulticastRouting)

多址傳輸路由選擇使用IP的D類地址生成樹法核心樹(core-basedtree)0前綴后綴816311111保留將來使用1110多址傳送地址110前綴后綴10前綴后綴A類B類C類D類E類大規(guī)模網(wǎng)絡(luò)中規(guī)模網(wǎng)絡(luò)小規(guī)模網(wǎng)絡(luò)TnbmP437Fig.5-55IP地址格式生成樹法組中的每個成員都必須以自己作為出發(fā)點建立一棵生成樹，根據(jù)自己所在小組對生成樹進(jìn)行修剪，得到一棵本小組修剪過的生成樹，并告訴同組的其他成員多址傳輸時僅沿相應(yīng)的生成樹轉(zhuǎn)發(fā)缺點：存儲量大如一個網(wǎng)絡(luò)有n個組，每個組平均有m個成員，則要存儲m*n棵生成樹多址傳輸路由選擇

(MulticastRouting)

多址傳輸路由選擇使用IP的D類地址生成樹法核心樹(core-basedtree)0前綴后綴8163110前綴后綴1111保留將來使用1110多址傳送地址110前綴后綴A類B類C類D類E類大規(guī)模網(wǎng)絡(luò)中規(guī)模網(wǎng)絡(luò)小規(guī)模網(wǎng)絡(luò)TnbmP437Fig.5-55IP地址格式核心樹(core-basedtree)

每個組只有一棵生成樹，它的樹根靠近組的中心部位，要發(fā)送一個分組給這個組成員，則發(fā)給樹根，由樹根將該分組沿核心樹發(fā)往各成員，這樣，每組只有一棵核心樹，節(jié)約了存儲空間拓?fù)湎嚓P(guān)的路由算法分層路由廣播路由多址傳輸路由選擇Peer-to-Peer網(wǎng)的節(jié)點查找Peer-to-Peer網(wǎng)中節(jié)點的查找對等網(wǎng)：一組織中大量用戶通過固定線路 接入Internet，共享資源對等網(wǎng)的特點：全分布：所有節(jié)點都是對稱的，沒有控制中心或分層的概念每個節(jié)點都有一些其他用戶感興趣的信息對等網(wǎng)的路由：沒有一個中心數(shù)據(jù)庫，如 何發(fā)現(xiàn)要尋找的信息Chord算法假設(shè)：系統(tǒng)中有n個用戶每個用戶都有可提供的信息資源，并且都已作了索引供其他用戶使用每個用戶都有一個IP地址，并可被散列成m位的一個數(shù)字，稱為節(jié)點標(biāo)識符（Chord用SHA-1算法來散列），節(jié)點標(biāo)識符為0~2m-1所有2m個標(biāo)識符按遞增次序鏈接成一個環(huán)，而不管節(jié)點是否存在定義函數(shù)successor(k)：找出節(jié)點k后面的第一個存在節(jié)點Chord算法（續(xù)）信息資源名稱(name)同樣被散列為一個m位的數(shù)字，稱為鍵值key（key=hash(name)）信息索引的存儲：信息的索引在所有節(jié)點上是隨機分布的，當(dāng)一個節(jié)點要提供信息name時，它首先構(gòu)造一個二元組（name,IP地址），然后調(diào)用successor(hash(name))去存儲該二元組，不同節(jié)點上的同名信息，其索引將被存在同一節(jié)點信息的查找：當(dāng)某個用戶需要查找名稱為name的信息時，向successor(key)發(fā)一個請求，要求返回?fù)碛行畔ame的節(jié)點的IP地址Chord算法優(yōu)化每個節(jié)點保存其直接前趨和直接后繼，那么請求可以順時針傳遞，也可以逆時針傳遞，可以在兩者之間選擇一條較短的路徑每個節(jié)點保存一張表，稱為fingertable，該表有m個表項，編號從0到m-1Chord算法優(yōu)化（續(xù)1）fingertable表的內(nèi)容每個表項指向一個實際存在的節(jié)點，每個表項有兩個字段：start和successor(start)的IP地址，節(jié)點k中第i個表項的值為：

Start[i]=[k+2i]mod(2m)[i=0…m-1] Successor(start[i])的IP地址Chord算法優(yōu)化（續(xù)2）在節(jié)點k上查找鍵值key的過程：如果k<key<successor(k)之間，那么包含key信息的節(jié)點是successor(k)，查找結(jié)束否則，查找finger表，找出小于key但最接近key的start值，并直接發(fā)一請求給successor(start)的IP地址，請求它繼續(xù)查找Chord算法實例2434579121720節(jié)點1TnbmP382Fig.5-24Chord算法實例017122027410986532111615141319181721222324262530292831i=44420,12,32,30,10,13當(dāng)前在線的節(jié)點i=01234576781212122020節(jié)點4812912111215152327節(jié)點71315141516202020281節(jié)點121620172019202327311節(jié)點15i=0123421272227242728144節(jié)點20281291311341112節(jié)點27Chord算法實例（續(xù)）2434579121720節(jié)點1i=01234576781212122020節(jié)點4812912111215152327節(jié)點71315141516202020281節(jié)點121620172019202327311節(jié)點1521272227242728144節(jié)點20281291311341112節(jié)點27例1：在節(jié)點1上查找key=3（key=hash(name)=3）

對于節(jié)點1，successor(1)=4，key在(1,4)中，返回4，即資源名為name的索引在節(jié)點4上例2：在節(jié)點1上查找key=14

由于key不在(1,4)中，于是查節(jié)點1的fingertable，小于14并最接近14的節(jié)點是9，successor(9)=12；于是到節(jié)點12查找，successor(12)=15，key在(12,15)中，于是返回15例3：在節(jié)點1上查找key=16 key不在(1,4)中，于是查節(jié)點1的fingertable，小于16并最接近16的節(jié)點是9，successor(9)=12，于是到節(jié)點12查找，successor(12)=15，key不在(12,15)中，于是查節(jié)點12的fingertable，小于16并最接近16的節(jié)點是14，successor(14)=15，于是到節(jié)點15查找，successor(15)=20，key在(15,20)中，于是返回20，即所查找的資源的索引在節(jié)點20上節(jié)點的動態(tài)添加和刪除初始化：假設(shè)開始時節(jié)點很少，因此通過節(jié)點之間直接交換信息建立初始的環(huán)和finger表添加節(jié)點r：向任一節(jié)點詢問successor(r)的地址s向s詢問它的直接前趨p向s和p申請加入環(huán)節(jié)點s將p+1到r的信息轉(zhuǎn)儲到r上，添加即告結(jié)束其他finger表中的問題由定時執(zhí)行一個后臺進(jìn)程完成刪除節(jié)點r將r的信息轉(zhuǎn)儲到后繼s通知前趨p，它的后繼變?yōu)閟節(jié)點的動態(tài)添加舉例2434579121720節(jié)點1Chord算法實例中添加節(jié)點24017122027410986532111615141319181721222324262530292831i=44420,12,32,30,10,13當(dāng)前在線的節(jié)點i=01234576781212122020節(jié)點4812912111215152324節(jié)點71315141516202020281節(jié)點121620172019202324311節(jié)點15i=0123421242224242428144節(jié)點202527262728101812節(jié)點24281291311341112節(jié)點27路由算法的分類靜態(tài)算法自適應(yīng)算法拓?fù)湎嚓P(guān)的路由算法移動節(jié)點的路由Ad-hoc網(wǎng)絡(luò)的路由移動IP（rfc2002）移動IP技術(shù)，是移動用戶在跨網(wǎng)絡(luò)隨意移動和漫游中，不用修改計算機配置的IP地址，享有原網(wǎng)絡(luò)中一切權(quán)限。支持主機移動或漫游的協(xié)議是MobileIP協(xié)議MobileIP協(xié)議中定義了三種功能實體：移動節(jié)點：一個移動的計算機，它改變位置時無需更改其IP設(shè)置，仍然可以通過其固定的IP地址進(jìn)行通信。主代理：一個移動節(jié)點本地網(wǎng)絡(luò)的主機或路由器，它保存有移動節(jié)點的位置信息，當(dāng)移動節(jié)點離開主網(wǎng)絡(luò)時能夠?qū)l(fā)往移動節(jié)點的數(shù)據(jù)包傳給移動節(jié)點?？痛恚阂苿庸?jié)點當(dāng)前所在的外地網(wǎng)絡(luò)上的一個主機，它能夠把由主代理送來的數(shù)據(jù)包轉(zhuǎn)發(fā)給移動節(jié)點。移動IP的工作機制代理周期性地發(fā)送廣播，宣告他們與鏈路之間的關(guān)系移動節(jié)點收到這些廣播后，判斷自己是在本地網(wǎng)還是在其他網(wǎng)。如在其他網(wǎng)移動節(jié)點向客代理注冊，遞交自己的IP地址，MAC地址和一些安全信息客代理與主代理聯(lián)系，報告自己的網(wǎng)絡(luò)地址主代理告訴客代理接收此消息可代理保存此移動主機的信息數(shù)據(jù)包的轉(zhuǎn)發(fā)首先，該包會路由到主網(wǎng)絡(luò)主代理查找到了移動主機的新住址，以及客代理的地址。把此包再封裝在一個IP包中，發(fā)給客代理告訴發(fā)送者將包直接發(fā)給客代理客代理解封裝數(shù)據(jù)包，把此數(shù)據(jù)包用數(shù)據(jù)鏈路層協(xié)議傳給移動主機當(dāng)有一個包發(fā)給移動主機時安全問題采用優(yōu)化路由的主要障礙是安全問題。當(dāng)通信對端直接通過隧道與移動節(jié)點通信時，對端必須知道移動節(jié)點當(dāng)前的優(yōu)化地址，這個問題與移動IP注冊相似。移動IP注冊的目的就是通知家鄉(xiāng)代理移動節(jié)點當(dāng)前的轉(zhuǎn)交地址。一個“壞家伙”只需送一個偽造的注冊給通信對端就可以中斷移動節(jié)點和對端的通信，這對移動IP中任何試圖優(yōu)化路由的努力來說都是一個挑戰(zhàn)。移動IPv6無客代理同時支持隧道和源路由技術(shù)主要內(nèi)容移動主機在外地網(wǎng)上獲取一個轉(zhuǎn)交地址將轉(zhuǎn)交地址通知主代理和他的通信伙伴知道轉(zhuǎn)交地址的伙伴和直接發(fā)送信息不知道轉(zhuǎn)交地址的伙伴可發(fā)送給主代理，由主代理在發(fā)送到轉(zhuǎn)交地址路由算法的分類靜態(tài)算法自適應(yīng)算法拓?fù)湎嚓P(guān)的路由算法移動節(jié)點的路由Ad-hoc網(wǎng)絡(luò)的路由Ad-Hoc模式早期的Ad-Hoc模式用于多個移動主機（無線站點）之間的直接通信，毋需接到有線網(wǎng)絡(luò)，每個站點必須“看”到其它所有站點現(xiàn)在的Ad-Hoc，移動主機并不要求相互都能“看”到，但，源主機到目的主機之間至少存在一條通路，途中的站點（移動主機）同時也將兼作路由器用，也可以與有線網(wǎng)絡(luò)連接Ad-Hoc的路由主動路由（表驅(qū)動）：每個節(jié)點都周期性廣播路由信息，主動地發(fā)現(xiàn)并維護路由表DSDV（DestinationSequencedDistanceVector）按需路由（事件驅(qū)動）：只有在需要發(fā)送數(shù)據(jù)時，源站點才尋找路由AODV（AdHocOn-demandDistanceVector）DSR（DynamicSourceRouting）主動路由DSDVDSDV（DestinationSequencedDistanceVector）是一種采用距離矢量算法的路由協(xié)議網(wǎng)絡(luò)中每個節(jié)點都維護一張路由表，路由表包含所有可能的目的節(jié)點、距離信息以及下一跳等每個節(jié)點都周期地廣播其全部的路由信息（對于拓?fù)渥兓鄬^慢的網(wǎng)絡(luò)只需廣播其更新的路由信息），每個節(jié)點都依據(jù)所收到的信息來維護它們的路由表DSDV算法依賴于每個節(jié)點路由信息周期性的廣播，在Ad-Hoc網(wǎng)絡(luò)中，由于其網(wǎng)絡(luò)拓?fù)涫莿討B(tài)變化的，維護一張路由表意味著耗用大量的帶寬和CPU資源Ad-Hoc的路由主動路由（表驅(qū)動）：每個節(jié)點都周期性廣播路由信息，主動地發(fā)現(xiàn)并維護路由表DSDV（DestinationSequencedDistanceVector）按需路由（事件驅(qū)動）：只有在需要發(fā)送數(shù)據(jù)時，源站點才尋找路由AODV（AdHocOn-demandDistanceVector）DSR（DynamicSourceRouting）按需路由AODV說明AODV（AdHocOn-demandDistanceVector）AODV是DSDV算法的改進(jìn)，與DSDV的區(qū)別在于只是在需要時（on-demand）才尋找路由，而不必如DSDV一樣需隨時維護一張包含全部節(jié)點的路由表當(dāng)源節(jié)點想發(fā)送信息給某個目的節(jié)點時，如當(dāng)前沒有路徑，則啟動PathDiscovery過程，廣播一個RouteRequest（RREQ）路徑請求分組給相鄰節(jié)點，收到此請求分組的鄰節(jié)點再轉(zhuǎn)發(fā)給它的相鄰節(jié)點并建立到源節(jié)點的反向路徑，直到一個知道目的節(jié)點路由信息的中間節(jié)點或目的節(jié)點本身，然后回復(fù)RouteReply（RREP）路徑應(yīng)答包給源節(jié)點AODV假設(shè)每一條鏈路都是雙向?qū)ΨQ的（Symmetric）按需路由AODV算法AODV的請求分組和應(yīng)答分組AODV的PathDiscovery過程AODV的路徑維護AODV中的請求分組和應(yīng)答分組AODV中的請求分組AODV中的應(yīng)答分組SourceAddRequestIDDestinationAddSourceSeq.#DestinationSeq.#HopCountSourceAddDestinationAddDestinationSeq.#HopCountLifeTimeTnbmP378Fig.5-22RouteReply分組的格式TnbmP377Fig.5-21RouteRequest分組的格式按需路由AODV算法AODV的請求分組和應(yīng)答分組AODV的PathDiscovery過程AODV的路徑維護AODV算法舉例—環(huán)境TnbmP376Fig.5-20(a)A的廣播范圍A的廣播范圍FEGHIDCBA圖中每個節(jié)點都是一臺具有路由功能的移動主機圖為A~I九個節(jié)點當(dāng)前的位置及其相互的連接狀態(tài)節(jié)點A的廣播范圍覆蓋了節(jié)點B和節(jié)點D，所以A和B以及A和D之間有連接，其它節(jié)點間的連接關(guān)系如圖，并假設(shè)連接是雙向的當(dāng)前A準(zhǔn)備向I發(fā)送分組，并且當(dāng)前沒有到達(dá)I的表項于是A發(fā)送一個RREQ廣播分組，分組中包含源和目的地址（A和I的IP地址）路徑發(fā)現(xiàn)過程—RouteRequest1TnbmP376Fig.5-20(b)B和C接收到A的廣播信息之后當(dāng)B和D接收到A的RREQ廣播分組，于是查各自的路由表，首先判斷是否重復(fù)，然后查找是否有較新的到達(dá)目的端的路徑信息如果有，則向源節(jié)點回送一個RREP分組如果沒有，則繼續(xù)廣播該RREQ分組，并建立一逆向路由的表項，以備返回的RREP分組途經(jīng)本節(jié)點時使用，同時啟動一個定時器（屆時如果不是逆向路徑的途經(jīng)節(jié)點，則丟棄）FEGHIDCBA可能的逆向路徑路徑發(fā)現(xiàn)過程—RouteRequest2TnbmP376Fig.5-20(c)C、F和G接收到A的廣播信息之后當(dāng)B收到D繼續(xù)廣播的A的RREQ分組，經(jīng)查是重復(fù)的，丟棄，當(dāng)F、G收到A的RREQ分組，經(jīng)查不是重復(fù)的，然后查自己的路由表，假設(shè)也都沒有較新的到達(dá)I的路徑信息所以，F(xiàn)和G也繼續(xù)廣播該RREQ分組，并建立一逆向路由的表項，同時啟動一個定時器C和D收到B繼續(xù)廣播的分組，D丟棄，C的處理與F、G類似FEGHIDCBA可能的逆向路徑路徑發(fā)現(xiàn)過程—RouteRequest3TnbmP376Fig.5-20(d)E、H和I接收到A的廣播信息之后當(dāng)E和H收到A的RREQ分組，也同樣檢查是否重復(fù)，再查自己的路由表E和H的處理與F和G等節(jié)點類似，即也繼續(xù)廣播，并建立一逆向路由的表項，同時啟動一個定時器等I在收到后，由于它是目的節(jié)點，所以立即創(chuàng)建一個RREP分組作為應(yīng)答，其中源、目的地址從RREQ分組中copy，此外根據(jù)當(dāng)前的計數(shù)值填寫Dest.Seq#、清Hopcount為0，并對Lifetime置一適當(dāng)?shù)某踔翟揜REP分組是一單播分組FEGHIDCBA可能的逆向路徑路徑發(fā)現(xiàn)過程—RouteReplyI所創(chuàng)建的RREP分組是一個單播的分組，將按逆向路徑傳送給源節(jié)點A沿途的節(jié)點（本例中的G、D）都將免費得到一條到達(dá)I的路徑（如果原來沒有到達(dá)I的路徑則添加，如果有則替代或更新）非沿途的中間節(jié)點（本例中的B、C、E、F和H），在定時器TimeOut后，原暫時保留的逆向路徑將丟棄路徑發(fā)現(xiàn)過程的優(yōu)化AODV算法中的RREQ分組采用的是廣播方式，所以會產(chǎn)生大量的廣播分組如果將RREQ分組的TTL（TimetoLife）限定在一個有限的網(wǎng)絡(luò)半徑之內(nèi)，將是有效的如果發(fā)送方在生成RREQ分組時，先把TTL設(shè)為1，如在合理的時間內(nèi)沒有RREP分組返回，則再生成下一個RREQ分組，并把TTL逐次設(shè)為2、3、4……，將有效地限制廣播分組的傳輸范圍按需路由AODV算法AODV的請求分組和應(yīng)答分組AODV的PathDiscovery過程AODV的路徑維護AODV的路徑維護每個節(jié)點都定期廣播一個HELLO消息，并期待其鄰居節(jié)點的應(yīng)答，如果沒有應(yīng)答，則說明該鄰居節(jié)點已經(jīng)不再有效如果某個鄰居節(jié)點無效，必須及時更新自己的路由表如果無效的鄰居節(jié)點是活動鄰居節(jié)點，那么還必須檢查路由表中與活動鄰居節(jié)點相關(guān)的路徑，并通知相關(guān)節(jié)點（遞歸）活動鄰居：在最近的ΔT時間內(nèi)曾經(jīng)給它發(fā)送過到達(dá)該目的節(jié)點的分組AODV的路徑維護以節(jié)點D的路由表為例Dest.NexthopDistanceActiveNeighborsOtherfieldsAA1F、GBB1F、GCB2FEG2FF1A、BGG1A、BHF2A、BIG2A、BTnbmP379Fig.5-23(a)在G停機之前D的路由表FEGHIDCBAAODV的路徑維護D發(fā)現(xiàn)其鄰居節(jié)點G已不復(fù)存在根據(jù)路由表得知，到目的節(jié)點E、G、I的下一跳是節(jié)點G，所以在D的路由表中刪除目的地址為E、G、I的表項同時，D知道節(jié)點A和B的某些路徑依賴節(jié)點G，所以立即通知節(jié)點A和BTnbmP379Fig.5-23(b)在G停機之后的拓?fù)鋱DFEGHIDCBAAd-Hoc的路由主動路由（表驅(qū)動）：每個節(jié)點都周期性廣播路由信息，主動地發(fā)現(xiàn)并維護路由表DSDV（DestinationSequencedDistanceVector）按需路由（事件驅(qū)動）：只有在需要發(fā)送數(shù)據(jù)時，源站點才尋找路由AODV（AdHocOn-demandDistanceVector）DSR（DynamicSourceRouting）按需路由DSR算法DSR（DynamicSourceRouting）DSR也是一種按需（on-demand）的路由協(xié)議，是一種基于源路由的按需路由協(xié)議，它使用源路由算法，每個節(jié)點都有一個RouteCache，記錄路由的路徑軌跡當(dāng)某源節(jié)點要發(fā)送數(shù)據(jù)給某一目的節(jié)點時，首先查看自己的RouteCache中是否存在現(xiàn)成的路徑可以使用（有時甚至保存有多條），如果不存在，則啟動RouteDiscovery過程，即廣播一個RREQ請求分組，其中包含目的節(jié)點地址、源節(jié)點地址、RequestID和一個RouteRecord（用于按順序逐個記錄此RREQ所途經(jīng)的節(jié)點地址）DSR的RouteDiscovery過程1RouteDiscovery過程中的RouteRequest目的節(jié)點源節(jié)點N1-N3-N4-N7N1-N3-N4N1-N3-N4N1-N3-N4-N6N1-N2-N5N1-N2N1-N3N1N1N1-N3-N4N1N2N5N8N7N6N4N3RouteRecord中的路徑記錄當(dāng)節(jié)點收到RouteRequest時如果在此之前已收到過同一源節(jié)點、同一ID的RREQ（表示這是重復(fù)的），則該請求分組丟棄如果在RouteCache中發(fā)現(xiàn)已經(jīng)有到目的節(jié)點的路徑（表示自己可提供到達(dá)目的節(jié)點的路徑），則把此路徑加入RouteRecord并創(chuàng)建RREP應(yīng)答分組，回復(fù)源節(jié)點并丟棄該請求分組如果自己是目的節(jié)點，此時RouteRecord中記錄的就是從源節(jié)點到目的節(jié)點的路徑信息，把此路徑加入RREP應(yīng)答分組，回復(fù)給源節(jié)點，并丟棄該請求分組否則，代表自己是中間節(jié)點，把自己的地址附加在RouteRecord中，然后再繼續(xù)廣播DSR的RouteDiscovery過程2RouteDiscovery過程中的RouteReply過程N1-N2-N5-N8源節(jié)點目的節(jié)點N1-N2-N5-N8N1-N2-N5-N8N1N2N5N8N7N6N4N3目的節(jié)點N8選擇的返回源節(jié)點N1的一條路徑AODV和DSR算法的比較1

AODV假設(shè)鏈路是雙向的；而DSR支持單向鏈路，并且DSR是基于源路由的AODV和DSR都有類似的RouteDiscovery過程，都有著按需建立路徑的特性，都強調(diào)是在源節(jié)點需要的時候才會去建立到目的地節(jié)點的路徑，但是兩者仍然有相當(dāng)?shù)牟顒e在AODV中，目的節(jié)點生成的RREP分組是按原路徑返回，所以鏈路必須是雙向的，但未必所有的鏈路都是雙向的；在DSR中，目的節(jié)點所創(chuàng)建的RREP分組是單播的，如果鏈路是雙向的，可以按原路徑返回，也可以再啟動一個RouteDiscovery過程，將先前所得到的路徑附在新的RREQ分組中，所以DSR支持單向鏈路AODV和DSR算法的比較2在AODV的路由表中，每個目的節(jié)點只有一條路徑記錄，而在DSR中，采用的是RouteCache，所以對每個目的節(jié)點都可能保留有多條路徑記錄在AODV中，在處理源節(jié)點的RREQ分組時，只處理一筆路徑信息，所以目的節(jié)點也只回應(yīng)最先到的RREQ，其余的一律丟棄；在DSR中，因為是使用RouteCache，目的節(jié)點會回應(yīng)所有的RREQ分組，即使是重復(fù)的，這就使源節(jié)點可以在RouteCache中保留多條到同一目的地的路徑，所以當(dāng)最短路徑失效時，可能還有另一個選擇，這種機制減少了啟動RouteDiscovery過程的機會，但是回應(yīng)每一個RREP卻也增加了網(wǎng)路流量AODV和DSR算法的比較3在一次RouteDiscovery過程中，與AODV相比較，DSR所得到的路徑信息更多DSR是基于源路由的，在RREQ請求分組中，除包含目的節(jié)點地址、源節(jié)點地址等以外，還包括一個RouteRecord域，用于按順序逐個記錄所途經(jīng)的節(jié)點地址，所以在完成一次RouteDiscovery后，源節(jié)點可以獲得目的節(jié)點和所有中間節(jié)點的路徑信息，每一個中間節(jié)點也可以獲得到達(dá)其他中間節(jié)點的路徑信息；而AODV得到的路徑信息則是有限的，只可得到相鄰節(jié)點的路徑信息，所以可能會造成節(jié)點常常啟動RouteDiscovery過程，而使得網(wǎng)路流量增大AODV和DSR算法的比較4路徑信息的更新，和由于某個節(jié)點失效而導(dǎo)致的路由信息的維護，兩者所采用的機制和策略有所不同在AODV中，路徑的時效是由SequenceNumber來決定，并根據(jù)所得到的消息隨時更新，如果過一段時間后此路徑?jīng)]被用過，則將從RoutingTable中刪除，此外，一旦發(fā)現(xiàn)某鄰節(jié)點失效，發(fā)現(xiàn)節(jié)點將維護自己的路由表，并根據(jù)路由表查看并通知與失效節(jié)點相關(guān)的路徑中所涉及到的節(jié)點；在DSR中，則無法判斷現(xiàn)有的路徑信息是否有效，只有等到RouteError分組返回時，才會把RouteCache中無效的路徑信息刪除，如果發(fā)現(xiàn)某鄰節(jié)點失效，因為是基于源路由的，所以也只會通知唯一的上游節(jié)點，直到源節(jié)點為止，而不會通知不在此路徑上的其它節(jié)點第5章網(wǎng)絡(luò)層網(wǎng)絡(luò)層設(shè)計的相關(guān)問題路由算法擁塞控制服務(wù)質(zhì)量網(wǎng)絡(luò)互聯(lián)因特網(wǎng)中的網(wǎng)絡(luò)層擁塞控制當(dāng)通信子網(wǎng)中有太多的分組，導(dǎo)致其性能降低，這種情況叫擁塞擁塞控制和流量控制的區(qū)別全局性問題和局部性問題造成擁塞的原因節(jié)點存儲容量（緩沖區(qū)）不夠處理機速度太低線路容量（帶寬）不夠

擁塞示例當(dāng)通信量太大時，發(fā)生擁塞，性能顯著降低子網(wǎng)最大傳輸容量完美的理想的擁塞的發(fā)送的分組吞吐量無擁塞輕度擁塞嚴(yán)重?fù)砣泳W(wǎng)最大傳輸容量完美的理想的擁塞的發(fā)送的分組吞吐量無擁塞輕度擁塞嚴(yán)重?fù)砣麚砣芾頁砣乇軗砣謴?fù)TnbmP385Fig.5-25吞吐量增大將發(fā)生擁塞擁塞對延遲的影響發(fā)送的分組無擁塞輕度擁塞嚴(yán)重?fù)砣麜r延擁塞控制原理和一般方法擁塞控制的基本原理擁塞預(yù)防策略虛電路子網(wǎng)中的擁塞控制數(shù)據(jù)報子網(wǎng)的擁塞控制載荷脫落抖動控制擁塞控制的基本原理開環(huán)控制閉環(huán)控制開環(huán)控制通過良好的設(shè)計來避免問題的出現(xiàn)，確保問題在一開始就不會出現(xiàn)開環(huán)控制的方法：什么時候接受新的數(shù)據(jù)報什么時候開始丟棄分組，丟棄哪些分組制定網(wǎng)絡(luò)中各個節(jié)點的調(diào)度策略所有這些決定與網(wǎng)絡(luò)中的當(dāng)前狀態(tài)無關(guān)擁塞控制的基本原理開環(huán)控制閉環(huán)控制閉環(huán)控制建立在反饋的基礎(chǔ)上，由三部分組成：監(jiān)視系統(tǒng)，檢測何時何地發(fā)生了擁塞檢測的指標(biāo)可以是包丟失率、平均隊列長度、由于超時引起的重發(fā)包數(shù)和數(shù)據(jù)包延遲抖動等將此信息傳送到可能采取行動的地方直接發(fā)包給相關(guān)節(jié)點利用包中的某一bit將擁塞通知鄰居節(jié)點每個節(jié)點周期性地發(fā)出探測報文調(diào)整系統(tǒng)操作以更正系統(tǒng)閉環(huán)控制方式顯式反饋：當(dāng)某一節(jié)點發(fā)現(xiàn)擁塞時，它發(fā)一個回答幀給相關(guān)節(jié)點，通知它們網(wǎng)絡(luò)擁塞了隱式反饋：通過定時器方法，發(fā)送端每發(fā)一個幀，就啟動一個定時器，如在規(guī)定的時間內(nèi)沒有收到相應(yīng)的ACK，則認(rèn)為該幀丟失，如丟失率相當(dāng)高，則認(rèn)為網(wǎng)絡(luò)發(fā)生了擁塞閉環(huán)控制一般不適合于高速網(wǎng)因為等反饋的控制信號到達(dá)，早已時過境遷擁塞控制原理和一般方法擁塞控制的基本原理擁塞預(yù)防策略虛電路子網(wǎng)中的擁塞控制數(shù)據(jù)報子網(wǎng)的擁塞控制載荷脫落抖動控制擁塞預(yù)防策略層次策略傳輸層重傳策略錯序保存策略應(yīng)答策略、流量控制策略超時決定網(wǎng)絡(luò)層子網(wǎng)是虛電路子網(wǎng)還是數(shù)據(jù)報子網(wǎng)數(shù)據(jù)包排隊和服務(wù)策略數(shù)據(jù)包丟棄策略路由算法數(shù)據(jù)包生存時間管理數(shù)據(jù)鏈路層重傳策略錯序保存策略應(yīng)答策略流量控制策略傳輸層、網(wǎng)絡(luò)層和數(shù)據(jù)鏈路層的傳輸策略都會對擁塞產(chǎn)生影響擁塞控制原理和一般方法擁塞控制的基本原理擁塞預(yù)防策略虛電路子網(wǎng)中的擁塞控制數(shù)據(jù)報子網(wǎng)的擁塞控制載荷脫落抖動控制虛電路子網(wǎng)中的擁塞控制通過準(zhǔn)入控制：一旦擁塞出現(xiàn)，不允許建立新的虛電路如果允許建立新的虛電路，則在路由選擇時要非常小心地繞過擁塞地段當(dāng)虛電路建立時，在主機和子網(wǎng)之間協(xié)商一個協(xié)議，該協(xié)議指出了新建流的量、特征、服務(wù)質(zhì)量和其他參數(shù)，子網(wǎng)將為該數(shù)據(jù)流預(yù)留資源擁塞控制原理和一般方法擁塞控制的基本原理擁塞預(yù)防策略虛電路子網(wǎng)中的擁塞控制數(shù)據(jù)報子網(wǎng)的擁塞控制載荷脫落抖動控制數(shù)據(jù)報子網(wǎng)的擁塞控制警告位方法這是DECnet和幀中繼網(wǎng)絡(luò)上采用的方法，當(dāng)發(fā)生擁塞時，在分組的頭部設(shè)置一位警告位，當(dāng)該分組到達(dá)目的主機時，傳輸實體將警告位拷貝到ACK上，源主機能得知擁塞的發(fā)生，以調(diào)整它的發(fā)送速率抑制分組擁塞的路由器直接發(fā)一個抑制分組給源主機Hop-by-Hop阻塞包直接發(fā)抑制分組給源主機可能反應(yīng)太慢，取而代之的是發(fā)給它的前一站路由器，通知它放慢速率，前一站再發(fā)給它的前一站，一直到源主機在路由器上監(jiān)視每條輸出線的利用率，當(dāng)利用率超過某一閾值時，采取某些行動擁塞控制原理和一般方法擁塞控制的基本原理擁塞預(yù)防策略虛電路子網(wǎng)中的擁塞控制數(shù)據(jù)報子網(wǎng)的擁塞控制載荷脫落抖動控制載荷脫落RED（RandomEarlyDetection）隨機早期檢測

在情況還不太糟糕時就采取動作隨時觀察數(shù)據(jù)包隊列的長度，一旦長度超過閾值，表示擁塞即將發(fā)生，立即開始在隊列中隨機選取一個分組丟棄，并繼續(xù)觀察擁塞發(fā)生的信息反饋顯式反饋：在丟包的同時，發(fā)送一個抑制分組隱式反饋：丟包時不發(fā)送抑制分組，當(dāng)源主機沒有收到ACK，則表示分組丟失，可能已發(fā)生擁塞當(dāng)路由器來不及處理數(shù)據(jù)包時，就把數(shù)據(jù)包給扔掉擁塞控制原理和一般方法擁塞控制的基本原理擁塞預(yù)防策略虛電路子網(wǎng)中的擁塞控制數(shù)據(jù)報子網(wǎng)的擁塞控制載荷脫落抖動控制抖動控制在音頻和視頻應(yīng)用中應(yīng)考慮抖動（jitter）控制在每個節(jié)點上控制預(yù)期的時間，當(dāng)?shù)竭_(dá)得太早，則在此節(jié)點上多留一會兒，如到達(dá)得太晚，則加快處理速度在接收方設(shè)置一緩沖區(qū)，將收到的數(shù)據(jù)包放入緩沖區(qū)，然后按一定的速率回放第5章網(wǎng)絡(luò)層網(wǎng)絡(luò)層設(shè)計的相關(guān)問題路由算法擁塞控制服務(wù)質(zhì)量網(wǎng)絡(luò)互聯(lián)因特網(wǎng)中的網(wǎng)絡(luò)層服務(wù)質(zhì)量的指標(biāo)從同一源到同一目的地的一串分組流（stream）稱為流（flow）流的服務(wù)質(zhì)量有四個指標(biāo)可靠性延遲抖動所需帶寬不同的服務(wù)需要不同的質(zhì)量服務(wù)可靠性延遲抖動所需帶寬E-mail高低低低ftp高低低中Web高中低中rlogin高中中低音頻點播低低高中視頻點播低低高高電話低高高低電視會議低高高高TnbmP397Fig.5-30不同的服務(wù)需要不同的質(zhì)量服務(wù)質(zhì)量保證服務(wù)質(zhì)量的技術(shù)集成服務(wù)區(qū)分服務(wù)標(biāo)簽交換和MPLS所謂服務(wù)質(zhì)量提供充足的資源包括：路由器的處理能力、緩沖區(qū)和帶寬 在接收端提供緩沖能力，消除抖動提供均衡路由當(dāng)源站點到目的站點有多條路徑時，通常的做法是選一條最佳路徑，均衡路由是把流量分散到多條路徑上，效果可能更好保證服務(wù)質(zhì)量的技術(shù)流量整形漏桶令牌桶資源預(yù)留準(zhǔn)入控制數(shù)據(jù)包調(diào)度通常保證服務(wù)質(zhì)量的技術(shù)包括：漏桶算法（LeakeyBucketAlgorithm）

平滑輸入流量，控制進(jìn)入網(wǎng)絡(luò)的流量：每單位時間泄漏一定量的字節(jié)數(shù)TnbmP401Fig.5-32(a)漏桶漏桶算法中的主機與網(wǎng)絡(luò)在主機上生成的發(fā)送數(shù)據(jù)具有突發(fā)性和間歇性通過漏桶算法，將使進(jìn)入網(wǎng)絡(luò)的數(shù)據(jù)通信量變得平穩(wěn)主機網(wǎng)絡(luò)漏桶深如C=1Mbyte即緩沖區(qū)的容量路由器的最佳工作速率是=2Mbyte/s輸出速率恒定如1M的漏桶需傳輸500ms數(shù)據(jù)生成速率為25Mbyte/s約40ms就能把漏桶灌滿，否則漏桶將溢出TnbmP401Fig.5-32(b)數(shù)據(jù)包漏桶漏桶算法突發(fā)長度的計算設(shè)C為漏桶容量（Byte,cell數(shù)）為漏桶的輸出速率（Byte/s）則突發(fā)速率r與允許突發(fā)時間的長度S的關(guān)系為：上例中突發(fā)長度的計算漏桶深C=1MbyteC=1M路由器的最佳工作速率是

=2Mbyte/s

=2M

數(shù)據(jù)生成速率為25Mbyte/sr=25M/s允許有43.5ms的突發(fā)數(shù)據(jù)允許突發(fā)時間的長度S=C/(r-)=1/(25-2)=43.5(ms)漏桶算法的不足之處漏桶滿時，造成數(shù)據(jù)丟失漏桶算法強迫輸出保持一個固定的平均速率，不能體現(xiàn)通信量的突發(fā)漏桶方法的改進(jìn)增加排隊緩沖區(qū)，提高系統(tǒng)的吞吐量許可證控制（令牌桶）跳躍式窗口通過反饋通知主機縮小發(fā)送窗口的大小信元標(biāo)注法將違約信元加標(biāo)識，進(jìn)入網(wǎng)絡(luò)，如網(wǎng)絡(luò)較空，則通過，否則丟棄信元按優(yōu)先級劃分若網(wǎng)絡(luò)擁擠，先丟掉優(yōu)先級低的信元保證服務(wù)質(zhì)量的技術(shù)流量整形漏桶令牌桶資源預(yù)留準(zhǔn)入控制數(shù)據(jù)包調(diào)度通常保證服務(wù)質(zhì)量的技術(shù)包括：令牌桶算法(TokenbucketAlgorithm)

希望當(dāng)大的突發(fā)流量到來時，輸出也能有適當(dāng)響應(yīng)數(shù)據(jù)的輸出必須持有令牌令牌的產(chǎn)生是定時的，每隔Δt，產(chǎn)生一個令牌，如令牌沒有被及時使用，可以存在令牌桶內(nèi)，令牌桶滿則將被丟棄當(dāng)突發(fā)數(shù)據(jù)到達(dá)時，如令牌桶內(nèi)有多個令牌，則突發(fā)數(shù)據(jù)可按令牌數(shù)輸出

輸出S輸入輸入隊列（K）令牌桶（M）令牌生成令牌桶突發(fā)時間長度的計算如：C：為令牌桶的容量：為令牌到達(dá)速率M：為最大的輸出速率（數(shù)據(jù)到達(dá)速率>M）

則最大的突發(fā)時間S為：C+S=MS即S=C/(M-)當(dāng)：令牌桶的容量C=250Kbyte令牌到達(dá)速率

=2Mbyte/s最大的輸出速率M=25Mbyte/s時，=250/23(ms)約為11ms如令牌桶已滿，則S=250K/(25M-2M)(ms)保證服務(wù)質(zhì)量的技術(shù)流量整形漏桶令牌桶資源預(yù)留準(zhǔn)入控制數(shù)據(jù)包調(diào)度通常保證服務(wù)質(zhì)量的技術(shù)包括：資源預(yù)留流量整形是保證服務(wù)質(zhì)量的良好的開端，然而這些信息的使用隱含著所有的數(shù)據(jù)包必須沿著同一路徑一旦路徑定下來，必須為該數(shù)據(jù)流在沿途預(yù)留一定的資源，包括帶寬、緩沖區(qū)和CPU的時間保證服務(wù)質(zhì)量的技術(shù)流量整形漏桶令牌桶資源預(yù)留準(zhǔn)入控制數(shù)據(jù)包調(diào)度通常保證服務(wù)質(zhì)量的技術(shù)包括：準(zhǔn)入控制網(wǎng)絡(luò)根據(jù)流量特征及所需的資源決定是否接受該數(shù)據(jù)流流說明：一組參數(shù)，用來描述流的特征，網(wǎng)絡(luò)根據(jù)這些特征確定所需的資源當(dāng)這組參數(shù)沿著路徑傳播時，沿途的路由器都會修改這組參數(shù)，當(dāng)?shù)竭_(dá)接收方，就知道是否準(zhǔn)入流說明舉例輸入的特性說明令牌到達(dá)速率（字節(jié)/秒）通信量將被以字節(jié)方式工作的令牌桶算法整形令牌桶大?。ㄗ止?jié)數(shù)）說明了每秒鐘有多少字節(jié)允許輸出及桶的大小，即令牌存儲的最大值最大傳輸速率（字節(jié)/秒）主機在任何條件下可以產(chǎn)生的最高速率最小分組大?。ㄗ止?jié)數(shù)）最小分組的字節(jié)數(shù)最大分組大?。ㄗ止?jié)數(shù)）最大分組的字節(jié)數(shù)TnbmP407Fig.5-35流說明舉例保證服務(wù)質(zhì)量的技術(shù)流量整形漏桶令牌桶資源預(yù)留準(zhǔn)入控制數(shù)據(jù)包調(diào)度通常保證服務(wù)質(zhì)量的技術(shù)包括：數(shù)據(jù)包調(diào)度公平排隊加權(quán)公平排隊如何強迫每個流只得到它自己預(yù)訂的帶寬公平排隊公平排隊：強迫各發(fā)送源公平地占用信道ABCDETnbmP409Fig.5-36(a)線路O有5個分組隊列的路由器(b)6個分組的結(jié)束時間O(a)(b)16111520222712164913181721385101419分組結(jié)束時間C18B16D18E19C221A22公平排隊算法其中：

為流f的第j個數(shù)據(jù)報

為流f的第j個數(shù)據(jù)報的長度

為數(shù)據(jù)報到達(dá)的系統(tǒng)虛擬時間為數(shù)據(jù)報的離開時間

r為線路帶寬

主要目的是無論數(shù)據(jù)流到達(dá)時的速率怎樣，都必須按傳輸信道的速率，每個流一個數(shù)據(jù)塊地輸出

數(shù)據(jù)包調(diào)度公平排隊加權(quán)公平排隊如何強迫每個流只得到它自己預(yù)留的帶寬加權(quán)公平排隊每個發(fā)送源有不同的優(yōu)先級，即不同的流有不同的帶寬其中：為分配給流f的線路帶寬

如每個流都已分配了不同的輸出信道帶寬，則排隊中必須體現(xiàn)信道帶寬的權(quán)值，即加權(quán)公平排隊服務(wù)質(zhì)量保證服務(wù)質(zhì)量的技術(shù)集成服務(wù)區(qū)分服務(wù)標(biāo)簽交換和MPLS集成服務(wù)（IntegratedService）提供兩類服務(wù)保證服務(wù)負(fù)載可控服務(wù)實現(xiàn)手段：通過資源預(yù)留資源預(yù)留協(xié)議RSVP最常用的資源預(yù)留協(xié)議是RSVP（ResourcereSerVationprotocol）協(xié)議將在沿途的路由器上預(yù)留一定的資源，包括帶寬、緩沖區(qū)、表空間等RSVP是一種基于接收端，并由接收端發(fā)起的資源預(yù)留協(xié)議RSVP的工作過程發(fā)送者PATHR1接收者R2R3PATHPATHPATHRESVRESVRESVRESVPATH狀態(tài)RESV狀態(tài)服務(wù)質(zhì)量保證服務(wù)質(zhì)量的技術(shù)集成服務(wù)區(qū)分服務(wù)標(biāo)簽交換和MPLS區(qū)分服務(wù)區(qū)分服務(wù)中，一組路由器形成一個管理域每個域中定義一組服務(wù)級別，即一組轉(zhuǎn)發(fā)規(guī)則當(dāng)一客戶登錄到某一域時，它的數(shù)據(jù)包必須攜帶一服務(wù)類型子段，用來表示所需的服務(wù)級別不需要為每一流進(jìn)行端到端的協(xié)商和資源預(yù)留QBONE：Internet上的區(qū)分服務(wù)的測試床集成服務(wù)要在沿途的每個路由器上保存每個流的狀態(tài)，因而可擴展性較差，區(qū)分服務(wù)就是針對此問題提出已定義的服務(wù)類別加速轉(zhuǎn)發(fā)（expeditedforwarding）：專線模擬：定義兩個隊列（快速、常規(guī)）保證轉(zhuǎn)發(fā)（assuredforwarding）：分為四個優(yōu)先級，每個優(yōu)先級有它自己的資源，每個數(shù)據(jù)包定義一個丟棄概率：高、中、低，組合起來，一共有12種類別數(shù)據(jù)包的處理：TnbmP414Fig.5-40保證轉(zhuǎn)發(fā)數(shù)據(jù)流的一種可能的實現(xiàn)分類標(biāo)記整形/丟棄分組4種優(yōu)先級1234路由器入口4種優(yōu)先級4個隊列隊列中分組服務(wù)質(zhì)量保證服務(wù)質(zhì)量的技術(shù)集成服務(wù)區(qū)分服務(wù)標(biāo)簽交換和MPLS標(biāo)簽交換（LabelSwitching）類似于虛電路方式：在數(shù)據(jù)包頭上加一個標(biāo)簽，一般為轉(zhuǎn)發(fā)表中的索引，在中間路由器上根據(jù)標(biāo)簽而不是根據(jù)目的地址作路由，這樣可加速轉(zhuǎn)發(fā)速度LabelSwitching也被稱為TagSwitchingMPLS

(MultiProtocolLabelSwitching)IETF提出了標(biāo)簽交換的標(biāo)準(zhǔn)標(biāo)簽交換的格式：在IP頭前增加一個MPLS頭轉(zhuǎn)發(fā)表的建立：采用數(shù)據(jù)驅(qū)動的方式，即當(dāng)?shù)谝粋€數(shù)據(jù)包經(jīng)過時，建立轉(zhuǎn)發(fā)表項TnbmP416Fig.5-41用IP、MPLS和PPP傳輸一個TCP數(shù)據(jù)報PPPMPLSIPTCP數(shù)據(jù)CRC標(biāo)簽QoSSTTL第5章網(wǎng)絡(luò)層網(wǎng)絡(luò)層設(shè)計的相關(guān)問題路由算法擁塞控制服務(wù)質(zhì)量網(wǎng)絡(luò)互聯(lián)因特網(wǎng)中的網(wǎng)絡(luò)層網(wǎng)絡(luò)互聯(lián)網(wǎng)絡(luò)互聯(lián)（internet）的背景不同類型的局域網(wǎng)的發(fā)展EthernetFDDI802.11ATMTCP/IPSNANCP/IPXAppleTalk

網(wǎng)絡(luò)互聯(lián)的類型LAN-LANLAN-WANWAN-WANLAN-WAN-LAN所謂網(wǎng)絡(luò)的不同提供的服務(wù)面向連接還是面向非連接協(xié)