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

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

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

正確性簡單性健壯性

穩(wěn)定性

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

Dijkstra算法（1959）：通過用邊的權(quán)值作為距離的度量來計(jì)算最短路徑，有最少邊數(shù)的路徑不一定是最短路徑1674329115328635如下圖：5和4之間邊數(shù)最少的路徑是5234但最短路徑是523674采用的數(shù)據(jù)結(jié)構(gòu)集合S：尚未找到最短路徑的節(jié)點(diǎn) 的集合數(shù)組R：R[i]為從指定源點(diǎn)去節(jié)點(diǎn)i 的路徑上，節(jié)點(diǎn)i的前一個(gè) 節(jié)點(diǎn)數(shù)組D：D[i]為從指定源點(diǎn)到節(jié)點(diǎn)i 的最短距離算法的初始化初始化集合S為除源節(jié)點(diǎn)外的所有節(jié)點(diǎn)初始化數(shù)組D：如果從源節(jié)點(diǎn)到節(jié)點(diǎn)v的邊存在，則D(v)為該邊的權(quán)值，否則為無窮大初始化數(shù)組R：如果從源節(jié)點(diǎn)到節(jié)點(diǎn)v的邊存在，則R(v)為源節(jié)點(diǎn)，否則為0算法WHILE（集合S非空） {從S中選一節(jié)點(diǎn)u，使D[u]最??； 如果（D[u]為無窮大） {錯(cuò)誤！無路徑存在，退出} 把u從S中刪去； 對(duì)(u,v)是邊的每個(gè)節(jié)點(diǎn)v {如果（v仍在S中） C=D[u]+weight(u,v); 如果（C<D[v]）/*v找到了一條更短的路徑*/ {R[v]=u;/*替換v的最短路徑及長度*/ D[v]=C; } } }從5出發(fā)到各個(gè)節(jié)點(diǎn)的最短路徑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）擴(kuò)散法（flooding）為路由器配置一張最優(yōu)的路由表擴(kuò)散法（flooding）

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

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

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

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

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

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

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

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

（LinkStateRouting）

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

（LinkStateRouting）

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

（LinkStateRouting）

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

F7

C1

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

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

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

（LinkStateRouting）

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

F2160110001

E2159010101

C2060101010

D2159100011

源節(jié)點(diǎn)E的鏈路狀態(tài)分組經(jīng)A和F到節(jié)點(diǎn)B，節(jié)點(diǎn)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á)如果序號(hào)循環(huán)使用，就會(huì)發(fā)生重復(fù)如果一個(gè)路由器被重起，序號(hào)將從0開始重新計(jì)數(shù)，但這些分組會(huì)被當(dāng)成過時(shí)分組如果序號(hào)發(fā)生錯(cuò)誤（如序號(hào)用32位表示，4被看成65540，第16位的0被誤傳成了1），則很多分組將被看成過時(shí)分組（此時(shí)5~65539均為過時(shí)分組，因?yàn)楫?dāng)前的分組序號(hào)是65540）解決辦法使用一個(gè)32位序號(hào)，即使每秒鐘發(fā)送一個(gè)分組，137年才會(huì)循環(huán)一次在每個(gè)分組中加一年齡字段（如初值為60），每秒鐘將年齡減1，為0后該分組將被丟棄，否則不會(huì)被認(rèn)為是過時(shí)分組鏈路狀態(tài)算法（L-S）

（LinkStateRouting）

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

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

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

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

當(dāng)前節(jié)點(diǎn)ABCDEFGHJKLMNO到I去的下一節(jié)點(diǎn)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é)點(diǎn)F收到一個(gè)從I來的分組，則立即向節(jié)點(diǎn)A和節(jié)點(diǎn)D轉(zhuǎn)發(fā)當(dāng)節(jié)點(diǎn)D收到一個(gè)經(jīng)F來的節(jié)點(diǎn)I的分組，它意識(shí)到如它有分組要送給I的話，是走節(jié)點(diǎn)F的，所以立即向節(jié)點(diǎn)C和G轉(zhuǎn)發(fā)當(dāng)節(jié)點(diǎn)G收到一個(gè)經(jīng)D來的節(jié)點(diǎn)I的分組，它意識(shí)到如它有分組要送給I的話，是走節(jié)點(diǎn)J而不是走節(jié)點(diǎn)D的，所以它不再轉(zhuǎn)發(fā)所以：經(jīng)過5個(gè)站點(diǎn)共24個(gè)分組的轉(zhuǎn)發(fā)后，廣播算法結(jié)束優(yōu)點(diǎn)：算法合理，容易實(shí)現(xiàn)缺點(diǎn)：對(duì)大型網(wǎng)絡(luò)不適用拓?fù)湎嚓P(guān)的路由算法分層路由廣播路由多址傳輸路由選擇Peer-to-Peer網(wǎng)的節(jié)點(diǎn)查找多址傳輸路由選擇

(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地址格式生成樹法組中的每個(gè)成員都必須以自己作為出發(fā)點(diǎn)建立一棵生成樹，根據(jù)自己所在小組對(duì)生成樹進(jìn)行修剪，得到一棵本小組修剪過的生成樹，并告訴同組的其他成員多址傳輸時(shí)僅沿相應(yīng)的生成樹轉(zhuǎn)發(fā)缺點(diǎn)：存儲(chǔ)量大如一個(gè)網(wǎng)絡(luò)有n個(gè)組，每個(gè)組平均有m個(gè)成員，則要存儲(chǔ)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)

每個(gè)組只有一棵生成樹，它的樹根靠近組的中心部位，要發(fā)送一個(gè)分組給這個(gè)組成員，則發(fā)給樹根，由樹根將該分組沿核心樹發(fā)往各成員，這樣，每組只有一棵核心樹，節(jié)約了存儲(chǔ)空間拓?fù)湎嚓P(guān)的路由算法分層路由廣播路由多址傳輸路由選擇Peer-to-Peer網(wǎng)的節(jié)點(diǎn)查找Peer-to-Peer網(wǎng)中節(jié)點(diǎn)的查找對(duì)等網(wǎng)：一組織中大量用戶通過固定線路 接入Internet，共享資源對(duì)等網(wǎng)的特點(diǎn)：全分布：所有節(jié)點(diǎn)都是對(duì)稱的，沒有控制中心或分層的概念每個(gè)節(jié)點(diǎn)都有一些其他用戶感興趣的信息對(duì)等網(wǎng)的路由：沒有一個(gè)中心數(shù)據(jù)庫，如 何發(fā)現(xiàn)要尋找的信息Chord算法假設(shè)：系統(tǒng)中有n個(gè)用戶每個(gè)用戶都有可提供的信息資源，并且都已作了索引供其他用戶使用每個(gè)用戶都有一個(gè)IP地址，并可被散列成m位的一個(gè)數(shù)字，稱為節(jié)點(diǎn)標(biāo)識(shí)符（Chord用SHA-1算法來散列），節(jié)點(diǎn)標(biāo)識(shí)符為0~2m-1所有2m個(gè)標(biāo)識(shí)符按遞增次序鏈接成一個(gè)環(huán)，而不管節(jié)點(diǎn)是否存在定義函數(shù)successor(k)：找出節(jié)點(diǎn)k后面的第一個(gè)存在節(jié)點(diǎn)Chord算法（續(xù)）信息資源名稱(name)同樣被散列為一個(gè)m位的數(shù)字，稱為鍵值key（key=hash(name)）信息索引的存儲(chǔ)：信息的索引在所有節(jié)點(diǎn)上是隨機(jī)分布的，當(dāng)一個(gè)節(jié)點(diǎn)要提供信息name時(shí)，它首先構(gòu)造一個(gè)二元組（name,IP地址），然后調(diào)用successor(hash(name))去存儲(chǔ)該二元組，不同節(jié)點(diǎn)上的同名信息，其索引將被存在同一節(jié)點(diǎn)信息的查找：當(dāng)某個(gè)用戶需要查找名稱為name的信息時(shí)，向successor(key)發(fā)一個(gè)請(qǐng)求，要求返回?fù)碛行畔ame的節(jié)點(diǎn)的IP地址Chord算法優(yōu)化每個(gè)節(jié)點(diǎn)保存其直接前趨和直接后繼，那么請(qǐng)求可以順時(shí)針傳遞，也可以逆時(shí)針傳遞，可以在兩者之間選擇一條較短的路徑每個(gè)節(jié)點(diǎn)保存一張表，稱為fingertable，該表有m個(gè)表項(xiàng)，編號(hào)從0到m-1Chord算法優(yōu)化（續(xù)1）fingertable表的內(nèi)容每個(gè)表項(xiàng)指向一個(gè)實(shí)際存在的節(jié)點(diǎn)，每個(gè)表項(xiàng)有兩個(gè)字段：start和successor(start)的IP地址，節(jié)點(diǎn)k中第i個(gè)表項(xiàng)的值為： Start[i]=[k+2i]mod(2m)[i=0…m-1] Successor(start[i])的IP地址Chord算法優(yōu)化（續(xù)2）在節(jié)點(diǎn)k上查找鍵值key的過程：如果k<key<successor(k)之間，那么包含key信息的節(jié)點(diǎn)是successor(k)，查找結(jié)束否則，查找finger表，找出小于key但最接近key的start值，并直接發(fā)一請(qǐng)求給successor(start)的IP地址，請(qǐng)求它繼續(xù)查找Chord算法實(shí)例2434579121720節(jié)點(diǎn)1TnbmP382Fig.5-24Chord算法實(shí)例017122027410986532111615141319181721222324262530292831i=44420,12,32,30,10,13當(dāng)前在線的節(jié)點(diǎn)i=01234576781212122020節(jié)點(diǎn)4812912111215152327節(jié)點(diǎn)71315141516202020281節(jié)點(diǎn)121620172019202327311節(jié)點(diǎn)15i=0123421272227242728144節(jié)點(diǎn)20281291311341112節(jié)點(diǎn)27Chord算法實(shí)例（續(xù)）2434579121720節(jié)點(diǎn)1i=01234576781212122020節(jié)點(diǎn)4812912111215152327節(jié)點(diǎn)71315141516202020281節(jié)點(diǎn)121620172019202327311節(jié)點(diǎn)1521272227242728144節(jié)點(diǎn)20281291311341112節(jié)點(diǎn)27例1：在節(jié)點(diǎn)1上查找key=3（key=hash(name)=3） 對(duì)于節(jié)點(diǎn)1，successor(1)=4，key在(1,4)中，返回4，即資源名為name的索引在節(jié)點(diǎn)4上例2：在節(jié)點(diǎn)1上查找key=14 由于key不在(1,4)中，于是查節(jié)點(diǎn)1的fingertable，小于14并最接近14的節(jié)點(diǎn)是9，successor(9)=12；于是到節(jié)點(diǎn)12查找，successor(12)=15，key在(12,15)中，于是返回15例3：在節(jié)點(diǎn)1上查找key=16 key不在(1,4)中，于是查節(jié)點(diǎn)1的fingertable，小于16并最接近16的節(jié)點(diǎn)是9，successor(9)=12，于是到節(jié)點(diǎn)12查找，successor(12)=15，key不在(12,15)中，于是查節(jié)點(diǎn)12的fingertable，小于16并最接近16的節(jié)點(diǎn)是14，successor(14)=15，于是到節(jié)點(diǎn)15查找，successor(15)=20，key在(15,20)中，于是返回20，即所查找的資源的索引在節(jié)點(diǎn)20上節(jié)點(diǎn)的動(dòng)態(tài)添加和刪除初始化：假設(shè)開始時(shí)節(jié)點(diǎn)很少，因此通過節(jié)點(diǎn)之間直接交換信息建立初始的環(huán)和finger表添加節(jié)點(diǎn)r：向任一節(jié)點(diǎn)詢問successor(r)的地址s向s詢問它的直接前趨p向s和p申請(qǐng)加入環(huán)節(jié)點(diǎn)s將p+1到r的信息轉(zhuǎn)儲(chǔ)到r上，添加即告結(jié)束其他finger表中的問題由定時(shí)執(zhí)行一個(gè)后臺(tái)進(jìn)程完成刪除節(jié)點(diǎn)r將r的信息轉(zhuǎn)儲(chǔ)到后繼s通知前趨p，它的后繼變?yōu)閟節(jié)點(diǎn)的動(dòng)態(tài)添加舉例2434579121720節(jié)點(diǎn)1Chord算法實(shí)例中添加節(jié)點(diǎn)24017122027410986532111615141319181721222324262530292831i=44420,12,32,30,10,13當(dāng)前在線的節(jié)點(diǎn)i=01234576781212122020節(jié)點(diǎn)4812912111215152324節(jié)點(diǎn)71315141516202020281節(jié)點(diǎn)121620172019202324311節(jié)點(diǎn)15i=0123421242224242428144節(jié)點(diǎn)202527262728101812節(jié)點(diǎn)24281291311341112節(jié)點(diǎn)27路由算法的分類靜態(tài)算法自適應(yīng)算法拓?fù)湎嚓P(guān)的路由算法移動(dòng)節(jié)點(diǎn)的路由Ad-hoc網(wǎng)絡(luò)的路由移動(dòng)IP（rfc2002）移動(dòng)IP技術(shù)，是移動(dòng)用戶在跨網(wǎng)絡(luò)隨意移動(dòng)和漫游中，不用修改計(jì)算機(jī)配置的IP地址，享有原網(wǎng)絡(luò)中一切權(quán)限。支持主機(jī)移動(dòng)或漫游的協(xié)議是MobileIP協(xié)議MobileIP協(xié)議中定義了三種功能實(shí)體：移動(dòng)節(jié)點(diǎn)：一個(gè)移動(dòng)的計(jì)算機(jī)，它改變位置時(shí)無需更改其IP設(shè)置，仍然可以通過其固定的IP地址進(jìn)行通信。主代理：一個(gè)移動(dòng)節(jié)點(diǎn)本地網(wǎng)絡(luò)的主機(jī)或路由器，它保存有移動(dòng)節(jié)點(diǎn)的位置信息，當(dāng)移動(dòng)節(jié)點(diǎn)離開主網(wǎng)絡(luò)時(shí)能夠?qū)l(fā)往移動(dòng)節(jié)點(diǎn)的數(shù)據(jù)包傳給移動(dòng)節(jié)點(diǎn)。客代理：移動(dòng)節(jié)點(diǎn)當(dāng)前所在的外地網(wǎng)絡(luò)上的一個(gè)主機(jī)，它能夠把由主代理送來的數(shù)據(jù)包轉(zhuǎn)發(fā)給移動(dòng)節(jié)點(diǎn)。移動(dòng)IP的工作機(jī)制代理周期性地發(fā)送廣播，宣告他們與鏈路之間的關(guān)系移動(dòng)節(jié)點(diǎn)收到這些廣播后，判斷自己是在本地網(wǎng)還是在其他網(wǎng)。如在其他網(wǎng)移動(dòng)節(jié)點(diǎn)向客代理注冊(cè)，遞交自己的IP地址，MAC地址和一些安全信息客代理與主代理聯(lián)系，報(bào)告自己的網(wǎng)絡(luò)地址主代理告訴客代理接收此消息可代理保存此移動(dòng)主機(jī)的信息數(shù)據(jù)包的轉(zhuǎn)發(fā)首先，該包會(huì)路由到主網(wǎng)絡(luò)主代理查找到了移動(dòng)主機(jī)的新住址，以及客代理的地址。把此包再封裝在一個(gè)IP包中，發(fā)給客代理告訴發(fā)送者將包直接發(fā)給客代理客代理解封裝數(shù)據(jù)包，把此數(shù)據(jù)包用數(shù)據(jù)鏈路層協(xié)議傳給移動(dòng)主機(jī)當(dāng)有一個(gè)包發(fā)給移動(dòng)主機(jī)時(shí)安全問題采用優(yōu)化路由的主要障礙是安全問題。當(dāng)通信對(duì)端直接通過隧道與移動(dòng)節(jié)點(diǎn)通信時(shí)，對(duì)端必須知道移動(dòng)節(jié)點(diǎn)當(dāng)前的優(yōu)化地址，這個(gè)問題與移動(dòng)IP注冊(cè)相似。移動(dòng)IP注冊(cè)的目的就是通知家鄉(xiāng)代理移動(dòng)節(jié)點(diǎn)當(dāng)前的轉(zhuǎn)交地址。一個(gè)“壞家伙”只需送一個(gè)偽造的注冊(cè)給通信對(duì)端就可以中斷移動(dòng)節(jié)點(diǎn)和對(duì)端的通信，這對(duì)移動(dòng)IP中任何試圖優(yōu)化路由的努力來說都是一個(gè)挑戰(zhàn)。移動(dòng)IPv6無客代理同時(shí)支持隧道和源路由技術(shù)主要內(nèi)容移動(dòng)主機(jī)在外地網(wǎng)上獲取一個(gè)轉(zhuǎn)交地址將轉(zhuǎn)交地址通知主代理和他的通信伙伴知道轉(zhuǎn)交地址的伙伴和直接發(fā)送信息不知道轉(zhuǎn)交地址的伙伴可發(fā)送給主代理，由主代理在發(fā)送到轉(zhuǎn)交地址路由算法的分類靜態(tài)算法自適應(yīng)算法拓?fù)湎嚓P(guān)的路由算法移動(dòng)節(jié)點(diǎn)的路由Ad-hoc網(wǎng)絡(luò)的路由Ad-Hoc模式早期的Ad-Hoc模式用于多個(gè)移動(dòng)主機(jī)（無線站點(diǎn)）之間的直接通信，毋需接到有線網(wǎng)絡(luò)，每個(gè)站點(diǎn)必須“看”到其它所有站點(diǎn)現(xiàn)在的Ad-Hoc，移動(dòng)主機(jī)并不要求相互都能“看”到，但，源主機(jī)到目的主機(jī)之間至少存在一條通路，途中的站點(diǎn)（移動(dòng)主機(jī)）同時(shí)也將兼作路由器用，也可以與有線網(wǎng)絡(luò)連接Ad-Hoc的路由主動(dòng)路由（表驅(qū)動(dòng)）：每個(gè)節(jié)點(diǎn)都周期性廣播路由信息，主動(dòng)地發(fā)現(xiàn)并維護(hù)路由表DSDV（DestinationSequencedDistanceVector）按需路由（事件驅(qū)動(dòng)）：只有在需要發(fā)送數(shù)據(jù)時(shí)，源站點(diǎn)才尋找路由AODV（AdHocOn-demandDistanceVector）DSR（DynamicSourceRouting）主動(dòng)路由DSDVDSDV（DestinationSequencedDistanceVector）是一種采用距離矢量算法的路由協(xié)議網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)都維護(hù)一張路由表，路由表包含所有可能的目的節(jié)點(diǎn)、距離信息以及下一跳等每個(gè)節(jié)點(diǎn)都周期地廣播其全部的路由信息（對(duì)于拓?fù)渥兓鄬?duì)較慢的網(wǎng)絡(luò)只需廣播其更新的路由信息），每個(gè)節(jié)點(diǎn)都依據(jù)所收到的信息來維護(hù)它們的路由表DSDV算法依賴于每個(gè)節(jié)點(diǎn)路由信息周期性的廣播，在Ad-Hoc網(wǎng)絡(luò)中，由于其網(wǎng)絡(luò)拓?fù)涫莿?dòng)態(tài)變化的，維護(hù)一張路由表意味著耗用大量的帶寬和CPU資源Ad-Hoc的路由主動(dòng)路由（表驅(qū)動(dòng)）：每個(gè)節(jié)點(diǎn)都周期性廣播路由信息，主動(dòng)地發(fā)現(xiàn)并維護(hù)路由表DSDV（DestinationSequencedDistanceVector）按需路由（事件驅(qū)動(dòng)）：只有在需要發(fā)送數(shù)據(jù)時(shí)，源站點(diǎn)才尋找路由AODV（AdHocOn-demandDistanceVector）DSR（DynamicSourceRouting）按需路由AODV說明AODV（AdHocOn-demandDistanceVector）AODV是DSDV算法的改進(jìn)，與DSDV的區(qū)別在于只是在需要時(shí)（on-demand）才尋找路由，而不必如DSDV一樣需隨時(shí)維護(hù)一張包含全部節(jié)點(diǎn)的路由表當(dāng)源節(jié)點(diǎn)想發(fā)送信息給某個(gè)目的節(jié)點(diǎn)時(shí)，如當(dāng)前沒有路徑，則啟動(dòng)PathDiscovery過程，廣播一個(gè)RouteRequest（RREQ）路徑請(qǐng)求分組給相鄰節(jié)點(diǎn)，收到此請(qǐng)求分組的鄰節(jié)點(diǎn)再轉(zhuǎn)發(fā)給它的相鄰節(jié)點(diǎn)并建立到源節(jié)點(diǎn)的反向路徑，直到一個(gè)知道目的節(jié)點(diǎn)路由信息的中間節(jié)點(diǎn)或目的節(jié)點(diǎn)本身，然后回復(fù)RouteReply（RREP）路徑應(yīng)答包給源節(jié)點(diǎn)AODV假設(shè)每一條鏈路都是雙向?qū)ΨQ的（Symmetric）按需路由AODV算法AODV的請(qǐng)求分組和應(yīng)答分組AODV的PathDiscovery過程AODV的路徑維護(hù)AODV中的請(qǐng)求分組和應(yīng)答分組AODV中的請(qǐng)求分組AODV中的應(yīng)答分組SourceAddRequestIDDestinationAddSourceSeq.#DestinationSeq.#HopCountSourceAddDestinationAddDestinationSeq.#HopCountLifeTimeTnbmP378Fig.5-22RouteReply分組的格式TnbmP377Fig.5-21RouteRequest分組的格式按需路由AODV算法AODV的請(qǐng)求分組和應(yīng)答分組AODV的PathDiscovery過程AODV的路徑維護(hù)AODV算法舉例—環(huán)境TnbmP376Fig.5-20(a)A的廣播范圍A的廣播范圍FEGHIDCBA圖中每個(gè)節(jié)點(diǎn)都是一臺(tái)具有路由功能的移動(dòng)主機(jī)圖為A~I九個(gè)節(jié)點(diǎn)當(dāng)前的位置及其相互的連接狀態(tài)節(jié)點(diǎn)A的廣播范圍覆蓋了節(jié)點(diǎn)B和節(jié)點(diǎn)D，所以A和B以及A和D之間有連接，其它節(jié)點(diǎn)間的連接關(guān)系如圖，并假設(shè)連接是雙向的當(dāng)前A準(zhǔn)備向I發(fā)送分組，并且當(dāng)前沒有到達(dá)I的表項(xiàng)于是A發(fā)送一個(gè)RREQ廣播分組，分組中包含源和目的地址（A和I的IP地址）路徑發(fā)現(xiàn)過程—RouteRequest1TnbmP376Fig.5-20(b)B和C接收到A的廣播信息之后當(dāng)B和D接收到A的RREQ廣播分組，于是查各自的路由表，首先判斷是否重復(fù)，然后查找是否有較新的到達(dá)目的端的路徑信息如果有，則向源節(jié)點(diǎn)回送一個(gè)RREP分組如果沒有，則繼續(xù)廣播該RREQ分組，并建立一逆向路由的表項(xiàng)，以備返回的RREP分組途經(jīng)本節(jié)點(diǎn)時(shí)使用，同時(shí)啟動(dòng)一個(gè)定時(shí)器（屆時(shí)如果不是逆向路徑的途經(jīng)節(jié)點(diǎn)，則丟棄）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分組，并建立一逆向路由的表項(xiàng)，同時(shí)啟動(dòng)一個(gè)定時(shí)器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é)點(diǎn)類似，即也繼續(xù)廣播，并建立一逆向路由的表項(xiàng)，同時(shí)啟動(dòng)一個(gè)定時(shí)器等I在收到后，由于它是目的節(jié)點(diǎn)，所以立即創(chuàng)建一個(gè)RREP分組作為應(yīng)答，其中源、目的地址從RREQ分組中copy，此外根據(jù)當(dāng)前的計(jì)數(shù)值填寫Dest.Seq#、清Hopcount為0，并對(duì)Lifetime置一適當(dāng)?shù)某踔翟揜REP分組是一單播分組FEGHIDCBA可能的逆向路徑路徑發(fā)現(xiàn)過程—RouteReplyI所創(chuàng)建的RREP分組是一個(gè)單播的分組，將按逆向路徑傳送給源節(jié)點(diǎn)A沿途的節(jié)點(diǎn)（本例中的G、D）都將免費(fèi)得到一條到達(dá)I的路徑（如果原來沒有到達(dá)I的路徑則添加，如果有則替代或更新）非沿途的中間節(jié)點(diǎn)（本例中的B、C、E、F和H），在定時(shí)器TimeOut后，原暫時(shí)保留的逆向路徑將丟棄路徑發(fā)現(xiàn)過程的優(yōu)化AODV算法中的RREQ分組采用的是廣播方式，所以會(huì)產(chǎn)生大量的廣播分組如果將RREQ分組的TTL（TimetoLife）限定在一個(gè)有限的網(wǎng)絡(luò)半徑之內(nèi)，將是有效的如果發(fā)送方在生成RREQ分組時(shí)，先把TTL設(shè)為1，如在合理的時(shí)間內(nèi)沒有RREP分組返回，則再生成下一個(gè)RREQ分組，并把TTL逐次設(shè)為2、3、4……，將有效地限制廣播分組的傳輸范圍按需路由AODV算法AODV的請(qǐng)求分組和應(yīng)答分組AODV的PathDiscovery過程AODV的路徑維護(hù)AODV的路徑維護(hù)每個(gè)節(jié)點(diǎn)都定期廣播一個(gè)HELLO消息，并期待其鄰居節(jié)點(diǎn)的應(yīng)答，如果沒有應(yīng)答，則說明該鄰居節(jié)點(diǎn)已經(jīng)不再有效如果某個(gè)鄰居節(jié)點(diǎn)無效，必須及時(shí)更新自己的路由表如果無效的鄰居節(jié)點(diǎn)是活動(dòng)鄰居節(jié)點(diǎn)，那么還必須檢查路由表中與活動(dòng)鄰居節(jié)點(diǎn)相關(guān)的路徑，并通知相關(guān)節(jié)點(diǎn)（遞歸）活動(dòng)鄰居：在最近的ΔT時(shí)間內(nèi)曾經(jīng)給它發(fā)送過到達(dá)該目的節(jié)點(diǎn)的分組AODV的路徑維護(hù)以節(jié)點(diǎn)D的路由表為例Dest.NexthopDistanceActiveNeighborsOtherfieldsAA1F、GBB1F、GCB2FEG2FF1A、BGG1A、BHF2A、BIG2A、BTnbmP379Fig.5-23(a)在G停機(jī)之前D的路由表FEGHIDCBAAODV的路徑維護(hù)D發(fā)現(xiàn)其鄰居節(jié)點(diǎn)G已不復(fù)存在根據(jù)路由表得知，到目的節(jié)點(diǎn)E、G、I的下一跳是節(jié)點(diǎn)G，所以在D的路由表中刪除目的地址為E、G、I的表項(xiàng)同時(shí)，D知道節(jié)點(diǎn)A和B的某些路徑依賴節(jié)點(diǎn)G，所以立即通知節(jié)點(diǎn)A和BTnbmP379Fig.5-23(b)在G停機(jī)之后的拓?fù)鋱DFEGHIDCBAAd-Hoc的路由主動(dòng)路由（表驅(qū)動(dòng)）：每個(gè)節(jié)點(diǎn)都周期性廣播路由信息，主動(dòng)地發(fā)現(xiàn)并維護(hù)路由表DSDV（DestinationSequencedDistanceVector）按需路由（事件驅(qū)動(dòng)）：只有在需要發(fā)送數(shù)據(jù)時(shí)，源站點(diǎn)才尋找路由AODV（AdHocOn-demandDistanceVector）DSR（DynamicSourceRouting）按需路由DSR算法DSR（DynamicSourceRouting）DSR也是一種按需（on-demand）的路由協(xié)議，是一種基于源路由的按需路由協(xié)議，它使用源路由算法，每個(gè)節(jié)點(diǎn)都有一個(gè)RouteCache，記錄路由的路徑軌跡當(dāng)某源節(jié)點(diǎn)要發(fā)送數(shù)據(jù)給某一目的節(jié)點(diǎn)時(shí)，首先查看自己的RouteCache中是否存在現(xiàn)成的路徑可以使用（有時(shí)甚至保存有多條），如果不存在，則啟動(dòng)RouteDiscovery過程，即廣播一個(gè)RREQ請(qǐng)求分組，其中包含目的節(jié)點(diǎn)地址、源節(jié)點(diǎn)地址、RequestID和一個(gè)RouteRecord（用于按順序逐個(gè)記錄此RREQ所途經(jīng)的節(jié)點(diǎn)地址）DSR的RouteDiscovery過程1RouteDiscovery過程中的RouteRequest目的節(jié)點(diǎn)源節(jié)點(diǎn)N1-N3-N4-N7N1-N3-N4N1-N3-N4N1-N3-N4-N6N1-N2-N5N1-N2N1-N3N1N1N1-N3-N4N1N2N5N8N7N6N4N3RouteRecord中的路徑記錄當(dāng)節(jié)點(diǎn)收到RouteRequest時(shí)如果在此之前已收到過同一源節(jié)點(diǎn)、同一ID的RREQ（表示這是重復(fù)的），則該請(qǐng)求分組丟棄如果在RouteCache中發(fā)現(xiàn)已經(jīng)有到目的節(jié)點(diǎn)的路徑（表示自己可提供到達(dá)目的節(jié)點(diǎn)的路徑），則把此路徑加入RouteRecord并創(chuàng)建RREP應(yīng)答分組，回復(fù)源節(jié)點(diǎn)并丟棄該請(qǐng)求分組如果自己是目的節(jié)點(diǎn)，此時(shí)RouteRecord中記錄的就是從源節(jié)點(diǎn)到目的節(jié)點(diǎn)的路徑信息，把此路徑加入RREP應(yīng)答分組，回復(fù)給源節(jié)點(diǎn)，并丟棄該請(qǐng)求分組否則，代表自己是中間節(jié)點(diǎn)，把自己的地址附加在RouteRecord中，然后再繼續(xù)廣播DSR的RouteDiscovery過程2RouteDiscovery過程中的RouteReply過程N(yùn)1-N2-N5-N8源節(jié)點(diǎn)目的節(jié)點(diǎn)N1-N2-N5-N8N1-N2-N5-N8N1N2N5N8N7N6N4N3目的節(jié)點(diǎn)N8選擇的返回源節(jié)點(diǎn)N1的一條路徑AODV和DSR算法的比較1AODV假設(shè)鏈路是雙向的；而DSR支持單向鏈路，并且DSR是基于源路由的AODV和DSR都有類似的RouteDiscovery過程，都有著按需建立路徑的特性，都強(qiáng)調(diào)是在源節(jié)點(diǎn)需要的時(shí)候才會(huì)去建立到目的地節(jié)點(diǎn)的路徑，但是兩者仍然有相當(dāng)?shù)牟顒e在AODV中，目的節(jié)點(diǎn)生成的RREP分組是按原路徑返回，所以鏈路必須是雙向的，但未必所有的鏈路都是雙向的；在DSR中，目的節(jié)點(diǎn)所創(chuàng)建的RREP分組是單播的，如果鏈路是雙向的，可以按原路徑返回，也可以再啟動(dòng)一個(gè)RouteDiscovery過程，將先前所得到的路徑附在新的RREQ分組中，所以DSR支持單向鏈路AODV和DSR算法的比較2在AODV的路由表中，每個(gè)目的節(jié)點(diǎn)只有一條路徑記錄，而在DSR中，采用的是RouteCache，所以對(duì)每個(gè)目的節(jié)點(diǎn)都可能保留有多條路徑記錄在AODV中，在處理源節(jié)點(diǎn)的RREQ分組時(shí)，只處理一筆路徑信息，所以目的節(jié)點(diǎn)也只回應(yīng)最先到的RREQ，其余的一律丟棄；在DSR中，因?yàn)槭鞘褂肦outeCache，目的節(jié)點(diǎn)會(huì)回應(yīng)所有的RREQ分組，即使是重復(fù)的，這就使源節(jié)點(diǎn)可以在RouteCache中保留多條到同一目的地的路徑，所以當(dāng)最短路徑失效時(shí)，可能還有另一個(gè)選擇，這種機(jī)制減少了啟動(dòng)RouteDiscovery過程的機(jī)會(huì)，但是回應(yīng)每一個(gè)RREP卻也增加了網(wǎng)路流量AODV和DSR算法的比較3在一次RouteDiscovery過程中，與AODV相比較，DSR所得到的路徑信息更多DSR是基于源路由的，在RREQ請(qǐng)求分組中，除包含目的節(jié)點(diǎn)地址、源節(jié)點(diǎn)地址等以外，還包括一個(gè)RouteRecord域，用于按順序逐個(gè)記錄所途經(jīng)的節(jié)點(diǎn)地址，所以在完成一次RouteDiscovery后，源節(jié)點(diǎn)可以獲得目的節(jié)點(diǎn)和所有中間節(jié)點(diǎn)的路徑信息，每一個(gè)中間節(jié)點(diǎn)也可以獲得到達(dá)其他中間節(jié)點(diǎn)的路徑信息；而AODV得到的路徑信息則是有限的，只可得到相鄰節(jié)點(diǎn)的路徑信息，所以可能會(huì)造成節(jié)點(diǎn)常常啟動(dòng)RouteDiscovery過程，而使得網(wǎng)路流量增大AODV和DSR算法的比較4路徑信息的更新，和由于某個(gè)節(jié)點(diǎn)失效而導(dǎo)致的路由信息的維護(hù)，兩者所采用的機(jī)制和策略有所不同在AODV中，路徑的時(shí)效是由SequenceNumber來決定，并根據(jù)所得到的消息隨時(shí)更新，如果過一段時(shí)間后此路徑?jīng)]被用過，則將從RoutingTable中刪除，此外，一旦發(fā)現(xiàn)某鄰節(jié)點(diǎn)失效，發(fā)現(xiàn)節(jié)點(diǎn)將維護(hù)自己的路由表，并根據(jù)路由表查看并通知與失效節(jié)點(diǎn)相關(guān)的路徑中所涉及到的節(jié)點(diǎn)；在DSR中，則無法判斷現(xiàn)有的路徑信息是否有效，只有等到RouteError分組返回時(shí)，才會(huì)把RouteCache中無效的路徑信息刪除，如果發(fā)現(xiàn)某鄰節(jié)點(diǎn)失效，因?yàn)槭腔谠绰酚傻?，所以也只?huì)通知唯一的上游節(jié)點(diǎn)，直到源節(jié)點(diǎn)為止，而不會(huì)通知不在此路徑上的其它節(jié)點(diǎn)第5章網(wǎng)絡(luò)層網(wǎng)絡(luò)層設(shè)計(jì)的相關(guān)問題路由算法擁塞控制服務(wù)質(zhì)量網(wǎng)絡(luò)互聯(lián)因特網(wǎng)中的網(wǎng)絡(luò)層擁塞控制當(dāng)通信子網(wǎng)中有太多的分組，導(dǎo)致其性能降低，這種情況叫擁塞擁塞控制和流量控制的區(qū)別全局性問題和局部性問題造成擁塞的原因節(jié)點(diǎn)存儲(chǔ)容量（緩沖區(qū)）不夠處理機(jī)速度太低線路容量（帶寬）不夠

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

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

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

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

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

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

則最大的突發(fā)時(shí)間S為：C+S=MS即S=C/(M-)當(dāng)：令牌桶的容量C=250Kbyte令牌到達(dá)速率=2Mbyte/s最大的輸出速率M=25Mbyte/s時(shí)，=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的時(shí)間保證服務(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í)，沿途的路由器都會(huì)修改這組參數(shù)，當(dāng)?shù)竭_(dá)接收方，就知道是否準(zhǔn)入流說明舉例輸入的特性說明令牌到達(dá)速率（字節(jié)/秒）通信量將被以字節(jié)方式工作的令牌桶算法整形令牌桶大?。ㄗ止?jié)數(shù)）說明了每秒鐘有多少字節(jié)允許輸出及桶的大小，即令牌存儲(chǔ)的最大值最大傳輸速率（字節(jié)/秒）主機(jī)在任何條件下可以產(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)度公平排隊(duì)加權(quán)公平排隊(duì)如何強(qiáng)迫每個(gè)流只得到它自己預(yù)訂的帶寬公平排隊(duì)公平排隊(duì)：強(qiáng)迫各發(fā)送源公平地占用信道ABCDETnbmP409Fig.5-36(a)線路O有5個(gè)分組隊(duì)列的路由器(b)6個(gè)分組的結(jié)束時(shí)間O(a)(b)16111520222712164913181721385101419分組結(jié)束時(shí)間C18B16D18E19C221A22公平排隊(duì)算法其中：

為流f的第j個(gè)數(shù)據(jù)報(bào)

為流f的第j個(gè)數(shù)據(jù)報(bào)的長度

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

r為線路帶寬

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

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

如每個(gè)流都已分配了不同的輸出信道帶寬，則排隊(duì)中必須體現(xiàn)信道帶寬的權(quán)值，即加權(quán)公平排隊(duì)服務(wù)質(zhì)量保證服務(wù)質(zhì)量的技術(shù)集成服務(wù)區(qū)分服務(wù)標(biāo)簽交換和MPLS集成服務(wù)（IntegratedService）提供兩類服務(wù)保證服務(wù)負(fù)載可控服務(wù)實(shí)現(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ù)中，一組路由器形成一個(gè)管理域每個(gè)域中定義一組服務(wù)級(jí)別，即一組轉(zhuǎn)發(fā)規(guī)則當(dāng)一客戶登錄到某一域時(shí)，它的數(shù)據(jù)包必須攜帶一服務(wù)類型子段，用來表示所需的服務(wù)級(jí)別不需要為每一流進(jìn)行端到端的協(xié)商和資源預(yù)留QBONE：Internet上的區(qū)分服務(wù)的測(cè)試床集成服務(wù)要在沿途的每個(gè)路由器上保存每個(gè)流的狀態(tài)，因而可擴(kuò)展性較差，區(qū)分服務(wù)就是針對(duì)此問題提出已定義的服務(wù)類別加速轉(zhuǎn)發(fā)（expeditedforwarding）：專線模擬：定義兩個(gè)隊(duì)列（快速、常規(guī)）保證轉(zhuǎn)發(fā)（assuredforwarding）：分為四個(gè)優(yōu)先級(jí)，每個(gè)優(yōu)先級(jí)有它自己的資源，每個(gè)數(shù)據(jù)包定義一個(gè)丟棄概率：高、中、低，組合起來，一共有12種類別數(shù)據(jù)包的處理：TnbmP414Fig.5-40保證轉(zhuǎn)發(fā)數(shù)據(jù)流的一種可能的實(shí)現(xiàn)分類標(biāo)記整形/丟棄分組4種優(yōu)先級(jí)1234路由器入口4種優(yōu)先級(jí)4個(gè)隊(duì)列隊(duì)列中分組服務(wù)質(zhì)量保證服務(wù)質(zhì)量的技術(shù)集成服務(wù)區(qū)分服務(wù)標(biāo)簽交換和MPLS標(biāo)簽交換（LabelSwitching）類似于虛電路方式：在數(shù)據(jù)包頭上加一個(gè)標(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頭前增加一個(gè)MPLS頭轉(zhuǎn)發(fā)表的建立：采用數(shù)據(jù)驅(qū)動(dòng)的方式，即當(dāng)?shù)谝粋€(gè)數(shù)據(jù)包經(jīng)過時(shí)，建立轉(zhuǎn)發(fā)表項(xiàng)TnbmP416Fig.5-41用IP、MPLS和PPP傳輸一個(gè)TCP數(shù)據(jù)報(bào)PPPMPLSIPTCP數(shù)據(jù)CRC標(biāo)簽QoSSTTL第5章網(wǎng)絡(luò)層網(wǎng)絡(luò)層設(shè)計(jì)的相關(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é)議IP、IPX、SNA、ATM等編址平面編址還是層次編址多址傳輸支持還是不支持分組大小每個(gè)網(wǎng)絡(luò)有它自己的最大值服務(wù)質(zhì)量支持還是不支持，支持幾種差錯(cuò)處理可靠的有序傳送還是無序傳送流量控制滑動(dòng)窗口、速率控制等，還是沒有控制擁塞控制漏桶、令牌桶、RED、抑制分組等安全加密方法等參數(shù)不同的超時(shí)設(shè)置，流量說明等計(jì)費(fèi)按連接時(shí)間、數(shù)據(jù)包數(shù)、字節(jié)數(shù)或不計(jì)費(fèi)TnbmP420Fig.5-43不同網(wǎng)絡(luò)的部分區(qū)別互聯(lián)網(wǎng)絡(luò)的相關(guān)技術(shù)互聯(lián)設(shè)備與方式互聯(lián)網(wǎng)絡(luò)的路由Packet的分段與重組互聯(lián)方式級(jí)聯(lián)虛電路

要求沿途的網(wǎng)絡(luò)都能提供可靠傳輸?shù)谋ＷC無連接的網(wǎng)絡(luò)互聯(lián)每個(gè)分組獨(dú)立地選擇路由不同網(wǎng)絡(luò)的

分組格式可能不盡相同不同網(wǎng)絡(luò)可能采用不同的地址編制方法此外，不能保證分組按順序到達(dá)

必須設(shè)計(jì)一個(gè)通用的互聯(lián)網(wǎng)分組格式和編址方法

隧道隧道隧道作用網(wǎng)絡(luò)互聯(lián)的一種較簡單的方式VPN—在公用網(wǎng)上建立自己的專用網(wǎng)隧道協(xié)議第二層隧道協(xié)議 PPTP—pointtopointtunnelingprotocol L2TP—layer2tunnelingprotocol第三層隧道協(xié)議：IPSec(IPSecurity)互聯(lián)網(wǎng)絡(luò)的相關(guān)技術(shù)互聯(lián)設(shè)備與方式互聯(lián)網(wǎng)絡(luò)的路由Packet的分段與重組互聯(lián)網(wǎng)絡(luò)的路由將網(wǎng)絡(luò)分成一個(gè)個(gè)的AS（autonomoussystem自治系統(tǒng)），AS之間由路由器連接每個(gè)自治系統(tǒng)受單一管理機(jī)構(gòu)控制，由一組網(wǎng)絡(luò)構(gòu)成（如校園網(wǎng)就是一個(gè)AS）AS中由內(nèi)部網(wǎng)關(guān)協(xié)議IGP（InteriorGatewayprotocol）處理AS間由外部網(wǎng)關(guān)協(xié)議EGP（ExteriorGatewayprotocol）進(jìn)行處理互聯(lián)網(wǎng)絡(luò)的相關(guān)技術(shù)互聯(lián)設(shè)備與方式互聯(lián)網(wǎng)絡(luò)的路由Packet的分段與重組簡單的網(wǎng)絡(luò)互聯(lián)數(shù)據(jù)包數(shù)據(jù)包數(shù)據(jù)包數(shù)據(jù)包數(shù)據(jù)包幀頭1數(shù)據(jù)包幀頭3數(shù)據(jù)包幀頭2網(wǎng)絡(luò)1網(wǎng)絡(luò)3網(wǎng)絡(luò)2源主機(jī)路由器1路由器2目的主機(jī)分段每個(gè)報(bào)頭都包含三個(gè)字段：分組號(hào)、偏移量和分組結(jié)束標(biāo)志2701ABCDEFGHIJ2700ABCDEFGH2781IJ2700ABCDE2750FGH2781IJTnbmP430Fig.5-51一個(gè)分段的例子重組透明分段——在入口網(wǎng)關(guān)分段，由出口 網(wǎng)關(guān)重組出口網(wǎng)關(guān)必須知道什么時(shí)候本分組的所有分段都已收到，并必須對(duì)每個(gè)分段進(jìn)行存儲(chǔ)，此外所有分段必須匯集到出口網(wǎng)關(guān)

非透明分段——由目的主機(jī)重組要求每一主機(jī)都有重組功能，由于每個(gè)分段都必須增加一個(gè)頭部，所以增加了每一分組的開銷第5章網(wǎng)絡(luò)層網(wǎng)絡(luò)層設(shè)計(jì)的相關(guān)問題路由算法擁塞控制服務(wù)質(zhì)量網(wǎng)絡(luò)互聯(lián)因特網(wǎng)中的網(wǎng)絡(luò)層