第4章網(wǎng)絡(luò)層運(yùn)輸層：·接受網(wǎng)絡(luò)層提供的主機(jī)到主機(jī)的通信服務(wù)?！橹鳈C(jī)上的兩個(gè)進(jìn)程之間提供通信服務(wù)。本章主要討論網(wǎng)絡(luò)層如何實(shí)現(xiàn)主機(jī)到主機(jī)的通信服務(wù)。網(wǎng)絡(luò)層與運(yùn)輸層區(qū)別·運(yùn)輸層只在網(wǎng)絡(luò)的主機(jī)中出現(xiàn)；·網(wǎng)絡(luò)層在網(wǎng)絡(luò)的主機(jī)和路由器中出現(xiàn)。主要內(nèi)容·網(wǎng)絡(luò)層功能和服務(wù)：虛電路和數(shù)據(jù)報(bào)；·路由器結(jié)構(gòu)和分組轉(zhuǎn)發(fā)功能；·網(wǎng)絡(luò)層的選路：決定分組從源到目的地所經(jīng)路徑的一些選路算法。4.1概述圖4-1簡(jiǎn)單網(wǎng)絡(luò)：·兩臺(tái)主機(jī)通信：H1H2；·主機(jī)之間的路徑經(jīng)過幾臺(tái)路由器發(fā)送方主機(jī)（H1）中網(wǎng)絡(luò)層的作用：·將來自運(yùn)輸層的每個(gè)報(bào)文段封裝成一個(gè)數(shù)據(jù)報(bào)（網(wǎng)絡(luò)層分組）；·將數(shù)據(jù)報(bào)向目的地發(fā)送，即向相鄰的路由器R1發(fā)送。接收方主機(jī)（H2）中網(wǎng)絡(luò)層的作用：·接收來自相鄰的路由器R2的數(shù)據(jù)報(bào)；·解封出報(bào)文段，并交付給其運(yùn)輸層。路由器的主要作用：將數(shù)據(jù)報(bào)從輸入鏈路“轉(zhuǎn)發(fā)”到輸出鏈路。通常路由器只實(shí)現(xiàn)下三層部分。4.1.1轉(zhuǎn)發(fā)和選路1、網(wǎng)絡(luò)層功能將分組從發(fā)送主機(jī)移動(dòng)到接收主機(jī)。主要包括：·轉(zhuǎn)發(fā)：當(dāng)一個(gè)分組到達(dá)某個(gè)路由器的輸入鏈路時(shí)，該路由器必須將其移動(dòng)到合適的輸出鏈路。與路由器的內(nèi)部結(jié)構(gòu)有關(guān)?！みx路：確定分組從發(fā)送方流向接收方時(shí)所經(jīng)過的路由或路徑。通過選路算法(routingalgorithm)計(jì)算路徑。兩者區(qū)別：·轉(zhuǎn)發(fā)：將分組從路由器的一個(gè)輸入鏈路接口轉(zhuǎn)移到一個(gè)合適的輸出鏈路接口的本地動(dòng)作。只涉及分組在路由器中從入鏈路到出鏈路的傳送。·選路：指分組從源到目的地的端到端路徑的網(wǎng)絡(luò)范圍動(dòng)作。涉及網(wǎng)絡(luò)中的所有路由器，集體經(jīng)選路協(xié)議交互，決定分組從源到目的地的路徑。2、路由器轉(zhuǎn)發(fā)分組轉(zhuǎn)發(fā)表：每臺(tái)路由器有一張。分組首部（目的地址或某個(gè)連接標(biāo)識(shí)）和相應(yīng)輸出鏈路的對(duì)照表。轉(zhuǎn)發(fā)表的內(nèi)容由選路算法（集中式或分布式）決定。轉(zhuǎn)發(fā)方法：路由器根據(jù)到達(dá)分組的首部值在轉(zhuǎn)發(fā)表中查詢，找到相應(yīng)的輸出鏈路接口，并將分組轉(zhuǎn)發(fā)出去。如圖4-2例。3、術(shù)語分組交換機(jī)：一臺(tái)通用分組交換設(shè)備，根據(jù)分組首部值，從輸入鏈路接口到輸出鏈路接口傳送分組?！ゆ溌穼咏粨Q機(jī)：根據(jù)鏈路層字段值作轉(zhuǎn)發(fā)決定的分組交換機(jī)。·路由器：根據(jù)網(wǎng)絡(luò)層字段值作轉(zhuǎn)發(fā)決定的分組交換機(jī)。4、連接建立如運(yùn)輸層TCP協(xié)議，在數(shù)據(jù)實(shí)際傳輸之前，需要發(fā)送方和接收方經(jīng)過三次握手建立所需的狀態(tài)信息（運(yùn)輸層連接）。網(wǎng)絡(luò)連接：指網(wǎng)絡(luò)層數(shù)據(jù)分組開始傳輸前，在所選擇的從源到目的地路徑上的各路由器之間相互握手，建立連接狀態(tài)。如ATM、幀中繼的網(wǎng)絡(luò)層。因特網(wǎng)網(wǎng)絡(luò)層不執(zhí)行連接建立。4.1.2問題：·發(fā)送主機(jī)的運(yùn)輸層是否能依靠網(wǎng)絡(luò)層將分組交付到目的地；·多個(gè)分組是否能按發(fā)送順序交付給接收主機(jī)的運(yùn)輸層；·傳輸兩個(gè)連續(xù)分組的時(shí)間間隔是否與接收到的時(shí)間間隔相同；·網(wǎng)絡(luò)層是否能提供網(wǎng)絡(luò)擁塞的反饋信息；·連接發(fā)送與接收主機(jī)的運(yùn)輸層通道的抽象視圖（特性）是什么？由網(wǎng)絡(luò)層提供的服務(wù)模型來確定。網(wǎng)絡(luò)服務(wù)模型(networkservicemodel)：定義在網(wǎng)絡(luò)的一側(cè)“邊緣”到另一側(cè)“邊緣”之間（即在發(fā)送與接收端系統(tǒng)之間）端到端的數(shù)據(jù)運(yùn)輸特性。1、網(wǎng)絡(luò)層可能提供的服務(wù)·確保交付：確保分組到達(dá)目的地。·具有時(shí)延上界的確保交付：主機(jī)到主機(jī)的時(shí)延。·有序分組交付：按發(fā)送順序到達(dá)?！ご_保最小帶寬：當(dāng)發(fā)送主機(jī)以低于特定比特率的速率發(fā)送比特，分組不會(huì)丟失，在一定時(shí)延到達(dá)?！ご_保最大時(shí)延抖動(dòng)：發(fā)送方發(fā)送兩個(gè)連續(xù)分組的時(shí)間間隔與接收到的間隔相同。2、因特網(wǎng)網(wǎng)絡(luò)層提供的服務(wù)單一的服務(wù)，即盡力而為服務(wù)(best-effortservice)，類似于“根本無服務(wù)”?！し纸M間的定時(shí)不能被保證；·分組的接收順序與發(fā)送順序不一定相同；·傳送的分組不能保證最終交付，即網(wǎng)絡(luò)可能未向目的地交付分組。3、ATM服務(wù)模型提供多重的服務(wù)模型，即在同一網(wǎng)絡(luò)中為不同的連接提供不同類別的服務(wù)。恒定比特率CBR(Costantbitrate)服務(wù)：標(biāo)準(zhǔn)的ATM服務(wù)模型。適用于實(shí)時(shí)、恒定比特率的音頻和視頻流。服務(wù)目標(biāo)：·使網(wǎng)絡(luò)連接看起來就像在發(fā)送主機(jī)和接收主機(jī)之間有一條專用的固定帶寬的傳輸鏈路?！TM信元傳輸時(shí)的端到端時(shí)延可變性(時(shí)延抖動(dòng))及丟失、遲交的信元都保證在規(guī)定值以下?？捎帽忍芈蔄BR(Availablebitrate)服務(wù)“比盡力服務(wù)稍好一點(diǎn)”的服務(wù)?！た赡軙?huì)丟失信元，但不能被重排序；·保證最小信元傳輸速率(MCR)，或比MCR更高（有足夠空閑資源）；·能夠?yàn)榘l(fā)送方提供反饋信息。4.2虛電路和數(shù)據(jù)報(bào)網(wǎng)絡(luò)運(yùn)輸層：提供無連接服務(wù)和面向連接服務(wù)。如因特網(wǎng)的UDP、TCP。網(wǎng)絡(luò)層：提供無連接服務(wù)和面向連接服務(wù)。相同：·面向連接服務(wù)：源和目的主機(jī)之間先握手?！o連接服務(wù)：無握手過程。區(qū)別：·網(wǎng)絡(luò)層：向運(yùn)輸層提供的主機(jī)到主機(jī)的服務(wù)。運(yùn)輸層：向應(yīng)用層提供的進(jìn)程到進(jìn)程的服務(wù)?！ぞW(wǎng)絡(luò)層：任何網(wǎng)絡(luò)中的網(wǎng)絡(luò)層只提供兩種服務(wù)之一，不會(huì)同時(shí)提供。虛電路網(wǎng)絡(luò)：提供連接服務(wù)。數(shù)據(jù)報(bào)網(wǎng)絡(luò)：提供無連接服務(wù)?！み\(yùn)輸層：面向連接服務(wù)在網(wǎng)絡(luò)邊緣的端系統(tǒng)中實(shí)現(xiàn)。網(wǎng)絡(luò)層：面向連接服務(wù)在端系統(tǒng)及網(wǎng)絡(luò)核心的路由器中實(shí)現(xiàn)。4.2.1虛電路網(wǎng)絡(luò)如X.25、幀中繼和ATM等。根據(jù)虛電路號(hào)轉(zhuǎn)發(fā)分組。1、虛電路VC組成：·源和目的地之間的一條連接路徑：一系列鏈路和路由器；·VC號(hào)：該路徑上每段鏈路的號(hào)碼，每條鏈路上的VC號(hào)可能不同；·路由器轉(zhuǎn)發(fā)表中的表項(xiàng)：VC路徑上每臺(tái)路由器中都有該表。2、工作原理：·在源和目的之間創(chuàng)建一個(gè)VC；·源向該VC發(fā)送帶有VC號(hào)的分組；·每經(jīng)過一臺(tái)中間路由器，用新的VC號(hào)代替原VC號(hào)：從VC號(hào)轉(zhuǎn)發(fā)表獲得；·分組在每條鏈路上的VC號(hào)不同?！ひ来艘?guī)則，直到目的地。例，圖4-3網(wǎng)絡(luò)。接口號(hào)：路由器連接鏈路的接口號(hào)碼。主機(jī)A與主機(jī)B通信過程：·主機(jī)A與主機(jī)B之間創(chuàng)建一條VC：路徑為AR1R2B，3個(gè)鏈路分配VC號(hào)12、22和32?！鬏敃r(shí)，分組VC號(hào)變化過程：122232AR1R2B3、VC號(hào)轉(zhuǎn)發(fā)表結(jié)構(gòu)例，R1中的VC號(hào)轉(zhuǎn)發(fā)表。入接口入VC#出接口出VC#11222226311837217197387…………VC1VC2VC3VC4·只要通過該路由器創(chuàng)建新的VC，其轉(zhuǎn)發(fā)表中就增加一項(xiàng)；·終止一個(gè)VC，其轉(zhuǎn)發(fā)表中就刪除對(duì)應(yīng)項(xiàng)?！ぢ酚善鞅仨殲檎谶M(jìn)行的連接維護(hù)連接狀態(tài)信息，直到該連接釋放。每條鏈路采用不同VC號(hào)的優(yōu)點(diǎn)：·減少分組首部VC字段的長(zhǎng)度；·簡(jiǎn)化虛電路的建立過程。虛電路的三個(gè)階段：虛電路建立在發(fā)送方與接收方之間建立一條虛電路，即決定所有分組要通過的一系列鏈路與路由器，并為每條鏈路確定一個(gè)VC號(hào)?！ぐl(fā)送方與網(wǎng)絡(luò)層聯(lián)系，指定接收方地址，由網(wǎng)絡(luò)建立虛電路(VC)。如圖4-4（1～4步）?！ど婕暗铰窂缴厦總€(gè)路由器轉(zhuǎn)發(fā)表的更新、資源的預(yù)留等。數(shù)據(jù)傳送：沿該虛電路傳輸數(shù)據(jù)分組（5～6步）。虛電路拆除：·由其中一方通知其網(wǎng)絡(luò)層終止該虛電路；·通知網(wǎng)絡(luò)另一側(cè)的端系統(tǒng)呼叫結(jié)束，并更新路徑上每臺(tái)路由器中的轉(zhuǎn)發(fā)表。網(wǎng)絡(luò)層與運(yùn)輸層連接建立區(qū)別：·運(yùn)輸層的連接建立：只涉及兩個(gè)端系統(tǒng)，相互協(xié)商通信并共同確定連接的參數(shù)。網(wǎng)絡(luò)中的路由器并不知道該運(yùn)輸層連接?！ぞW(wǎng)絡(luò)層虛電路建立：發(fā)送方接收方沿兩個(gè)端系統(tǒng)之間路徑上的路由器都要參與虛電路的建立，且每個(gè)路由器都完全知道所經(jīng)過的所有虛電路發(fā)送方接收方信令報(bào)文：端系統(tǒng)向網(wǎng)絡(luò)發(fā)送的指示虛電路的啟動(dòng)與終止的報(bào)文、以紀(jì)錄由器之間傳遞的用于建立虛電路的報(bào)文。信令協(xié)議：用來交換信令報(bào)文的協(xié)議。4.2.2數(shù)據(jù)報(bào)如，因特網(wǎng)。分組傳送，不需在發(fā)送方與接收方之間建立虛電路。路由器根據(jù)主機(jī)目的地址轉(zhuǎn)發(fā)分組。傳輸過程：發(fā)送方給要發(fā)送的分組加上目的端系統(tǒng)地址，并送入網(wǎng)絡(luò)，經(jīng)過若干中間路由器轉(zhuǎn)發(fā)分組，直到目的地。如圖4-5所示。路由器轉(zhuǎn)發(fā)方法：根據(jù)到達(dá)分組的目的地址在轉(zhuǎn)發(fā)表中查詢，找到相應(yīng)的輸出鏈路接口，并將分組轉(zhuǎn)發(fā)出去。轉(zhuǎn)發(fā)表：每臺(tái)路由器有一張。目的地址與鏈路接口的映射表。轉(zhuǎn)發(fā)表中的表項(xiàng)數(shù)與地址位數(shù)有關(guān)，每個(gè)可能的地址對(duì)應(yīng)一項(xiàng)。例，設(shè)目的地址32位，某個(gè)路由器有4條鏈路（0～3），地址與鏈路接口關(guān)系：目的地址范圍鏈路接口11001000000101110001000000000000～11001000000101110001011111111111011001000000101110001100000000000～11001000000101110001100011111111111001000000101110001100100000000～110010000001011100011111111111112其他3對(duì)應(yīng)轉(zhuǎn)發(fā)表：前綴匹配鏈路接口110010000001011100010011001000000101110001100011100100000010111000112其他3路由器查表方法：用目的地址前綴與轉(zhuǎn)發(fā)表的前綴匹配：·存在匹配：向?qū)?yīng)鏈路轉(zhuǎn)發(fā)。如，目的地址110010000001011100010110101000010#·不存在匹配：選擇“其他”項(xiàng)對(duì)應(yīng)的鏈路轉(zhuǎn)發(fā)?！ご嬖诙鄠€(gè)匹配：使用最長(zhǎng)前綴匹配規(guī)則，即向與最長(zhǎng)前綴匹配的鏈路接口轉(zhuǎn)發(fā)分組。如，目的地址110010000001011100011000101010101#說明：·路由器轉(zhuǎn)發(fā)表只維持轉(zhuǎn)發(fā)狀態(tài)信息；·轉(zhuǎn)發(fā)表由選路算法修改（1～5分鐘更新）；虛電路網(wǎng)絡(luò)轉(zhuǎn)發(fā)表隨虛電路的建立和拆除更新。·一個(gè)端系統(tǒng)發(fā)送給另一個(gè)端系統(tǒng)的一批分組可能在網(wǎng)絡(luò)中選擇不同的路徑，到達(dá)的順序可能不一致。4.2虛電路服務(wù)：源于電話產(chǎn)業(yè)界（采用“真正”電路）。呼叫建立及每次呼叫的狀態(tài)要在網(wǎng)絡(luò)中的路由器上維持，比面向數(shù)據(jù)報(bào)的網(wǎng)絡(luò)要復(fù)雜。網(wǎng)絡(luò)功能復(fù)雜，端系統(tǒng)設(shè)備簡(jiǎn)單。數(shù)據(jù)報(bào)服務(wù)：由互連計(jì)算機(jī)的需求發(fā)展而來。與電話網(wǎng)相反。·網(wǎng)絡(luò)層服務(wù)模型簡(jiǎn)單?！ざ讼到y(tǒng)功能復(fù)雜：高層實(shí)現(xiàn)許多功能，如按序傳送、可靠數(shù)據(jù)傳輸、擁塞控制與DNS名字解析等；帶來的結(jié)果：·因特網(wǎng)服務(wù)模型提供的服務(wù)保證最少（可能沒有?。?，對(duì)網(wǎng)絡(luò)層的需求最小，使得互連使用各種不同鏈路層技術(shù)的網(wǎng)絡(luò)變得更加容易。·許多應(yīng)用都在位于網(wǎng)絡(luò)邊緣的主機(jī)（服務(wù)器）上實(shí)現(xiàn)。4.3路由器工作原理網(wǎng)絡(luò)層轉(zhuǎn)發(fā)功能：將分組從路由器的輸入鏈路傳送到適當(dāng)?shù)妮敵鲦溌?。路由器的體系結(jié)構(gòu)：圖4-6。物理層數(shù)據(jù)查找物理層數(shù)據(jù)查找鏈路層轉(zhuǎn)發(fā)排隊(duì)數(shù)據(jù)物理層緩存鏈路層輸入端口：·將一條物理鏈路端接到路由器的物理層；·實(shí)現(xiàn)路由器的數(shù)據(jù)鏈路層功能；·實(shí)現(xiàn)查找與轉(zhuǎn)發(fā)功能，以便分組通過路由器交換結(jié)構(gòu)轉(zhuǎn)發(fā)到適當(dāng)?shù)妮敵龆丝?；·用于控制的分組從輸入端口轉(zhuǎn)發(fā)到選路處理器。通常，路由器中的多個(gè)端口被集中到一塊線路卡（linecard）上。交換結(jié)構(gòu)：將路由器的輸入端口連接到它的輸出端口。完全包含在路由器中。輸出端口：·存儲(chǔ)經(jīng)過交換結(jié)構(gòu)轉(zhuǎn)發(fā)給它的分組，并將分組發(fā)送到輸出鏈路?！ね瓿膳c輸入端口順序相反的數(shù)據(jù)鏈路層和物理層功能。對(duì)雙向鏈路，輸出端口與其輸入端口通常在同一線路卡上成對(duì)出現(xiàn)。選路處理器：執(zhí)行選路協(xié)議、維護(hù)選路信息和轉(zhuǎn)發(fā)表以及執(zhí)行路由器中的網(wǎng)絡(luò)管理功能。目前，Cisco公司主宰因特網(wǎng)路由器市場(chǎng)。4.3.1輸入端口功能：如圖4-7?！ぞ€路端接與數(shù)據(jù)鏈路處理：實(shí)現(xiàn)與輸入鏈路相關(guān)的物理層和數(shù)據(jù)鏈路層功能?！げ檎?轉(zhuǎn)發(fā)：確定將一個(gè)到達(dá)的分組通過交換結(jié)構(gòu)轉(zhuǎn)發(fā)給哪個(gè)輸出端口。通過查找轉(zhuǎn)發(fā)表實(shí)現(xiàn)。轉(zhuǎn)發(fā)表由選路處理器計(jì)算出來，給每個(gè)輸入端口存放一份拷貝，能隨選路更新。分散式轉(zhuǎn)發(fā)：在每個(gè)輸入端口本地做出交換決策，無須激活中央選路處理器?？杀苊庠诼酚善髦心硞€(gè)單點(diǎn)產(chǎn)生轉(zhuǎn)發(fā)處理瓶頸。集中式轉(zhuǎn)發(fā)：若路由器的輸入端口處理能力有限，可直接將分組轉(zhuǎn)發(fā)給中央選路處理器，查找轉(zhuǎn)發(fā)表并將分組轉(zhuǎn)發(fā)到適當(dāng)?shù)妮敵龆丝凇Ｈ?，將工作站或服?wù)器用作路由器時(shí)，采用此法。選路處理器就是CPU，輸入端口是一塊網(wǎng)絡(luò)接口卡。查表速度：搜索轉(zhuǎn)發(fā)表，查找最長(zhǎng)匹配的表項(xiàng)，或無相應(yīng)表項(xiàng)時(shí)找出默認(rèn)選路表項(xiàng)。查找速度受許多因素影響，如路由器速度、鏈路速率、查找算法等。通常，輸入端口的處理速度要超過線路速度。即完成一次查找的時(shí)間應(yīng)少于從輸入端口接收一個(gè)分組所需的時(shí)間（對(duì)收到的分組的輸入處理在下一個(gè)接收操作結(jié)束之前完成）。如，對(duì)運(yùn)行速率為2.5Gbit/s的OC48鏈路，若分組長(zhǎng)256B，查找速度大約為每秒一百萬次。查找方法：線性查找：對(duì)龐大的轉(zhuǎn)發(fā)表不合適；二分查找：將轉(zhuǎn)發(fā)表表項(xiàng)存放在一個(gè)樹形數(shù)據(jù)結(jié)構(gòu)中。樹的每一層對(duì)應(yīng)目的地址的一個(gè)比特，查找某個(gè)地址時(shí)，從樹的根節(jié)點(diǎn)開始，依次查地址的每一位?！さ谝槐忍兀?：左子樹包含與該目的地址對(duì)應(yīng)的轉(zhuǎn)發(fā)表表項(xiàng)；1：表項(xiàng)在右子樹中。·下一比特：0，選擇初始子樹的左子樹；1，選擇初始子樹的右子樹?！璑步之內(nèi)可找到相應(yīng)的轉(zhuǎn)發(fā)表表項(xiàng)（N是地址的位數(shù)，地址空間為2N）。如，因特網(wǎng)32bitIP地址需32步。內(nèi)容可尋址內(nèi)存(CAM)：將一個(gè)32bitIP地址提交給CAM，由它以常數(shù)時(shí)間返回該地址對(duì)應(yīng)的轉(zhuǎn)發(fā)表表項(xiàng)內(nèi)容。如，Cisco8500系列。將最近被訪問的表項(xiàng)保存在高速緩存(cache)中：分組阻塞(blocked)：來自其他輸入端口的分組當(dāng)前正在使用該交換結(jié)構(gòu)。被阻塞的分組必須在輸入端口處排隊(duì)，等待以后調(diào)度通過交換結(jié)構(gòu)。4.3將分組從輸入端口交換（轉(zhuǎn)發(fā)）到輸出端口中。交換方式：三種，如圖4-8所示。經(jīng)內(nèi)存交換早期用計(jì)算機(jī)作為路由器·輸入端口與輸出端口之間的交換由CPU(選路處理器)控制完成；·輸入端口與輸出端口類似I/O設(shè)備：當(dāng)分組到達(dá)輸入端口時(shí)，通過中斷向選路處理器發(fā)出信號(hào)，將分組拷貝到處理器內(nèi)存中；選路處理器根據(jù)分組中的目的地址查表找出適當(dāng)?shù)妮敵龆丝冢瑢⒃摲纸M拷貝到輸出端口的緩存中。若內(nèi)存帶寬為每秒寫入或讀出B個(gè)分組，則總的轉(zhuǎn)發(fā)吞吐量(分組從輸入端口被傳送到輸出端口的總速率)小于B/2。現(xiàn)代路由器目的地址的查找和將分組存儲(chǔ)(交換)進(jìn)適當(dāng)?shù)拇鎯?chǔ)位置是由輸入線路上的處理器來執(zhí)行的。類似共享內(nèi)存的多處理機(jī)，用一個(gè)線路卡上的處理器將分組存儲(chǔ)進(jìn)適當(dāng)輸出端口的內(nèi)存中。2、經(jīng)一根總線交換輸入端口通過一條共享總線將分組直接傳送到輸出端口，不需要選路處理器的干預(yù)。每次只能有一個(gè)分組通過總線傳送。分組到達(dá)一個(gè)輸入端口時(shí)，若總線正忙，會(huì)被暫時(shí)阻塞，在輸入端口排隊(duì)。路由器交換帶寬受總線速率限制。3、經(jīng)一個(gè)互聯(lián)網(wǎng)絡(luò)交換使用一個(gè)互聯(lián)網(wǎng)絡(luò)結(jié)構(gòu)。如縱橫式交換機(jī)：由2n條總線組成，n個(gè)輸入端口與n個(gè)輸出端口連接。到達(dá)輸入端口的分組沿水平總線穿行，直至與所希望的輸出端口的垂直總線交叉點(diǎn)：·若該條垂直總線空閑，則分組被傳送到輸出端口；·否則，該到達(dá)的分組被阻塞，必須在輸入端口排隊(duì)。4.3取出存放在輸出端口內(nèi)存中的分組，并將其傳輸?shù)捷敵鲦溌飞稀Ｊ疽鈭D，4-9。當(dāng)交換結(jié)構(gòu)將分組交付給輸出端口的速率超過輸出鏈路速率，就需要排隊(duì)與緩存管理功能。4.3輸入端口和輸出端口都會(huì)形成分組隊(duì)列。當(dāng)隊(duì)列逐步增長(zhǎng)，路由器緩存空間滿，會(huì)出現(xiàn)分組丟失(packetloss)，在輸入端口隊(duì)列或輸出端口隊(duì)列。丟失具體位置，取決于流量負(fù)載、交換結(jié)構(gòu)的相對(duì)速度、線路速度等因素。假定：輸入線路速率與輸出線路速率相同，有n個(gè)輸入端口和n個(gè)輸出端口。交換結(jié)構(gòu)速率：將分組從輸入端口移動(dòng)到輸出端口的速率。1、輸入端口不排隊(duì)：若交換結(jié)構(gòu)的速率至少是輸入線路速率的n倍，在輸入端口處不會(huì)出現(xiàn)排隊(duì)。最壞情況，有n條輸入線路同時(shí)接收分組。交換結(jié)構(gòu)可以在每個(gè)輸入端口(同時(shí))接收一個(gè)分組的時(shí)間內(nèi)將n個(gè)分組從輸入端口傳送到輸出端口。2、輸出端口排隊(duì)：設(shè)交換結(jié)構(gòu)的速率至少是線路速率的n倍。最壞情況，到達(dá)每個(gè)輸入端口的分組都被發(fā)往同一個(gè)輸出端口?！ぴ谝粋€(gè)單位時(shí)間（接收或發(fā)送一個(gè)分組）內(nèi)，將有n個(gè)分組到達(dá)該輸出端口，排隊(duì)(等待)發(fā)送到輸出鏈路上；·在發(fā)出隊(duì)列中一個(gè)分組的時(shí)間內(nèi)，又有n個(gè)分組到達(dá)。依此類推，最終排隊(duì)的分組快速增長(zhǎng)，很快占滿輸出端口的存儲(chǔ)空間，使后續(xù)分組被丟棄。圖4-10說明輸出端口的排隊(duì)過程。t時(shí)刻：每個(gè)輸入端口都到達(dá)一個(gè)分組，都發(fā)往最上側(cè)的輸出端口。假定：線路速度相同，交換結(jié)構(gòu)處理速度是線路速度的三倍?！ひ粋€(gè)單位時(shí)間后（接收或發(fā)送一個(gè)分組的時(shí)間）：三個(gè)原始分組都被傳送到輸出端口，并排隊(duì)等待發(fā)送。又有兩個(gè)新分組到達(dá)交換結(jié)構(gòu)的輸入端，其中的一個(gè)分組要發(fā)往最上側(cè)的輸出端口?！は乱粋€(gè)單位時(shí)間：三個(gè)分組中的一個(gè)通過輸出鏈路發(fā)送出去。分組調(diào)度程序：在輸出端口排隊(duì)的分組中選出一個(gè)發(fā)送。原則：·先來先服務(wù)FCFS(first-come-first-service)：簡(jiǎn)單?！ぜ訖?quán)公平排隊(duì)WFQ(weightedfairqueuing)：在具有排隊(duì)分組的不同端到端連接之間公平地共享輸出鏈路。分組丟棄方法：若緩存已滿，丟棄分組?！G棄后到的分組（棄尾）；·刪除一個(gè)或多個(gè)已排隊(duì)的分組；·活動(dòng)隊(duì)列管理AQM算法：在緩存填滿前丟棄分組或首部加標(biāo)記，向發(fā)送方提供擁塞信號(hào)。如，隨機(jī)早期檢測(cè)RED算法：輸出隊(duì)列長(zhǎng)度維護(hù)一個(gè)加權(quán)平均值：平均隊(duì)列長(zhǎng)度小于最小閾值minth，到達(dá)分組被納入隊(duì)列；隊(duì)列滿或平均隊(duì)列長(zhǎng)度大于最大閾值minmax，到達(dá)分組被標(biāo)記或丟棄；平均隊(duì)列長(zhǎng)度在[minth，minmax]之間，到達(dá)分組以某種概率被標(biāo)記或丟棄。3、輸入端口分組排隊(duì)：交換結(jié)構(gòu)不夠快，即相對(duì)于輸入線路速度不能快得使所有到達(dá)的分組無延遲地通過它傳送，則在輸入端口出現(xiàn)分組排隊(duì)，以等待通過交換結(jié)構(gòu)傳送到輸出端口。如采用縱橫式交換結(jié)構(gòu)，假定：所有鏈路速度相同；分組從輸入端口傳送到給定輸出端口的時(shí)間與從輸入鏈路接收一個(gè)分組的時(shí)間相同；分組按FCFS方式從輸入隊(duì)列移動(dòng)到輸出隊(duì)列中。結(jié)果：·如果分組輸出端口不同，多個(gè)分組可以被并行傳送?！と绻煌斎腙?duì)列中前端的分組是發(fā)往同一輸出隊(duì)列，其中的一些分組被阻塞，在輸入隊(duì)列中等待（交換結(jié)構(gòu)一次傳一個(gè)分組到端口）。例圖4-11。·不同輸入隊(duì)列前端的兩個(gè)分組要發(fā)往右上角的同一輸出端口?！と粝劝l(fā)送左上角隊(duì)列前端的分組，左下角隊(duì)列中的分組要等待，左下角隊(duì)列中排在該分組后面的分組也要等待（雖然不是同一個(gè)輸出端口）。線頭HOL(head-of-the-line)阻塞：輸入隊(duì)列中后面的分組被位于線頭的一個(gè)分組阻塞(即使輸出端口空閑的)，等待通過交換結(jié)構(gòu)發(fā)送。4.5選路算法分組通過路由器轉(zhuǎn)發(fā)，每個(gè)路由器都有一張轉(zhuǎn)發(fā)表，選路算法決定轉(zhuǎn)發(fā)表內(nèi)容。選路：確定分組從發(fā)送方傳送到接收方所要通過的路徑（路由）。·數(shù)據(jù)報(bào)服務(wù)：在給定源和目的地之間傳輸不同分組可能采用不同的路由?！ぬ撾娐贩?wù)：在給定源和目的地之間的所有分組采用同一路徑。默認(rèn)路由器(defaultrouter)：與主機(jī)直接相連的一臺(tái)路由器，又叫第一跳路由器(first-hoprouter)。每當(dāng)主機(jī)發(fā)送一個(gè)分組時(shí)，都先傳送給它的默認(rèn)路由器?！ぴ绰酚善鳎涸粗鳈C(jī)的默認(rèn)路由器?！つ康穆酚善鳎耗康闹鳈C(jī)的默認(rèn)路由器。從源主機(jī)到目的主機(jī)的選路歸結(jié)為從源路由器到目的路由器的選路。選路算法：確定一個(gè)分組從源路由器到目的路由器所經(jīng)路徑的算法。即在給定的一組路由器以及連接路由器的鏈路中，找到一條從源路由器到目的路由器的“好”路徑?！昂谩甭窂剑壕哂小白畹唾M(fèi)用”的路徑。費(fèi)用由許多因素決定，如鏈路長(zhǎng)度、傳播時(shí)延、價(jià)格等。網(wǎng)絡(luò)的抽象圖模型：用“節(jié)點(diǎn)圖”表示網(wǎng)絡(luò)的結(jié)構(gòu)。圖論中，圖G=(N，E)表示N個(gè)節(jié)點(diǎn)和E條邊的集合，每條邊是來自N的一對(duì)節(jié)點(diǎn)。如圖4-25：·節(jié)點(diǎn)：表示路由器(做出分組轉(zhuǎn)發(fā)判決的點(diǎn))。如u，v，w，x，y，z?！み叄哼B接節(jié)點(diǎn)的線段，表示路由器之間的物理鏈路。如(u，v)、(u，x)、(u，w)、…·邊的值（費(fèi)用）：反映對(duì)應(yīng)鏈路的物理長(zhǎng)度、或鏈路速度、或與鏈路相關(guān)的費(fèi)用。約定：c(x，y)表示節(jié)點(diǎn)x和節(jié)點(diǎn)y之間邊的費(fèi)用（從節(jié)點(diǎn)x到節(jié)點(diǎn)y的鏈路費(fèi)用）?！と?x，y)是E中的某條邊（節(jié)點(diǎn)x與節(jié)點(diǎn)y直接相連）：則c(x，y)=鏈路費(fèi)用，節(jié)點(diǎn)x與節(jié)點(diǎn)y互為鄰居。如c(u，v)=2，節(jié)點(diǎn)u與節(jié)點(diǎn)v互為鄰居c(u，x)=1，節(jié)點(diǎn)u與節(jié)點(diǎn)x互為鄰居·若(x，y)不是E中的某條邊（節(jié)點(diǎn)x與節(jié)點(diǎn)y不直接相連）：則c(x，y)=∞。如c(u，y)=∞，c(u，z)=∞·c(x，y)=c(y，x)如c(u，v)=c(v，u)=2選路算法：根據(jù)給定的網(wǎng)絡(luò)抽象圖，找出從源節(jié)點(diǎn)到目的節(jié)點(diǎn)間的最低費(fèi)用路徑。路徑表示：用路徑上的節(jié)點(diǎn)來描述。如圖G=(N，E)中的一條路徑，是一個(gè)節(jié)點(diǎn)序列(x1,x2,…,xp)，其中每一對(duì)(x1,x2)，(x2,x3)，…，(xp-1,xp)是E中的邊，即x1,x2,…,xp依次連成的邊。路徑(x1,x2,…,xp)費(fèi)用：沿途所有邊的費(fèi)用之和。即c(x1,x2)+c(x2,x3)+…+c(xp-1,xp)通常，任意兩個(gè)節(jié)點(diǎn)x和y之間有多條路徑，費(fèi)用不一定相同。最低費(fèi)用路徑(least-costpath)：該路徑上鏈路費(fèi)用之和最小。若所有鏈路費(fèi)用相同，則最低費(fèi)用路徑就是最短路徑(shortestpath)，即在源和目的地之間經(jīng)過鏈路最少的路徑。如圖4-25，源節(jié)點(diǎn)u和目的節(jié)點(diǎn)w之間的最低費(fèi)用路徑：(u,x,y,w)，費(fèi)用為3。選路算法分類：根據(jù)算法是全局性還是分散性劃分全局選路算法(globalroutingalgorithm)：用完整的、全局性的網(wǎng)絡(luò)信息來計(jì)算最低費(fèi)用路徑。即以所有節(jié)點(diǎn)之間的連通性及所有鏈路的費(fèi)用為條件?！ぴ陂_始計(jì)算前，以某種方式獲得這些信息。·可在單個(gè)位置計(jì)算，也可在多個(gè)位置上復(fù)制?！碛羞B通性和鏈路費(fèi)用的完整信息。鏈路狀態(tài)算法LS：必須知道網(wǎng)絡(luò)中每條鏈路的費(fèi)用。分散式選路算法(decentralizedroutingalgorithm)：以迭代的、分布式的方式計(jì)算最低費(fèi)用路徑?！す?jié)點(diǎn)只有與其直接相連鏈路的費(fèi)用信息：不需擁有所有網(wǎng)絡(luò)鏈路費(fèi)用的完整信息。·通過迭代計(jì)算過程并與相鄰節(jié)點(diǎn)(鄰居節(jié)點(diǎn))交換信息；·逐步計(jì)算出到達(dá)某目的節(jié)點(diǎn)或一組目的節(jié)點(diǎn)的最低費(fèi)用路徑。距離向量算法DV：每個(gè)節(jié)點(diǎn)維護(hù)到網(wǎng)絡(luò)中所有其他節(jié)點(diǎn)的費(fèi)用（距離）的估計(jì)向量。根據(jù)算法是靜態(tài)還是動(dòng)態(tài)劃分·靜態(tài)選路算法：路由確定后基本不再變化。當(dāng)人工干預(yù)調(diào)整時(shí)，可能有一些變化?！?dòng)態(tài)選路算法：當(dāng)網(wǎng)絡(luò)的流量負(fù)載或拓?fù)浒l(fā)生變化時(shí)，改變路徑?？梢灾芷谛缘鼗蛑苯拥仨憫?yīng)拓?fù)浠蜴溌焚M(fèi)用的變化。易受選路循環(huán)、路由振蕩之類問題的影響。根據(jù)對(duì)負(fù)載是否敏感劃分·負(fù)載敏感算法：鏈路費(fèi)用會(huì)動(dòng)態(tài)地變化，反映出底層鏈路的當(dāng)前擁塞水平。如果當(dāng)前擁塞的一條鏈路被賦以高費(fèi)用，則選路算法應(yīng)繞開該擁塞鏈路來選擇路由。如早期的ARPAnet選路算法?！へ?fù)載遲鈍算法：某條鏈路的費(fèi)用一般不反映其當(dāng)前的(或最近的)擁塞級(jí)別。如因特網(wǎng)的選路算法。因特網(wǎng)常用的兩種選路算法：動(dòng)態(tài)全局鏈路狀態(tài)算法與動(dòng)態(tài)分散式距離向量算法。4.前提條件：已知網(wǎng)絡(luò)拓?fù)浜退墟溌返馁M(fèi)用，作為算法的輸入。獲取方法：每個(gè)節(jié)點(diǎn)向網(wǎng)絡(luò)中所有其他路由器廣播鏈路狀態(tài)分組（含有它所連接的鏈路的費(fèi)用）。由鏈路狀態(tài)廣播（linkstatebroadcast）算法實(shí)現(xiàn)。最終使所有節(jié)點(diǎn)都有一個(gè)相同且完整的網(wǎng)絡(luò)視圖。每個(gè)節(jié)點(diǎn)都可以運(yùn)行鏈路狀態(tài)算法并計(jì)算出最低費(fèi)用路徑集。Dijkstra最低費(fèi)用路徑算法（最短通路算法）：計(jì)算從某節(jié)點(diǎn)（源節(jié)點(diǎn)，如u）到網(wǎng)絡(luò)中所有其他節(jié)點(diǎn)的最低費(fèi)用路徑。是一種迭代算法，即：經(jīng)第k次迭代后，可知道到k個(gè)目的節(jié)點(diǎn)的最低費(fèi)用路徑?；舅枷耄阂栽垂?jié)點(diǎn)為起點(diǎn)，每次找出一個(gè)到源節(jié)點(diǎn)的費(fèi)用最低的節(jié)點(diǎn)，直到把所有的目的節(jié)點(diǎn)都找到為止。符號(hào)定義：·D(v)：從源節(jié)點(diǎn)到目的節(jié)點(diǎn)v的當(dāng)前最低費(fèi)用路徑的費(fèi)用；·p(v)：從源節(jié)點(diǎn)到節(jié)點(diǎn)v的當(dāng)前最低費(fèi)用路徑上的前一節(jié)點(diǎn)(節(jié)點(diǎn)v的鄰居)；·N'：節(jié)點(diǎn)集合，從源節(jié)點(diǎn)到這些節(jié)點(diǎn)的最低費(fèi)用路徑已被求出。鏈路狀態(tài)(LS)算法：·由一個(gè)初始化步驟和其后的循環(huán)組成。循環(huán)執(zhí)行的次數(shù)與網(wǎng)絡(luò)中的節(jié)點(diǎn)個(gè)數(shù)（除源節(jié)點(diǎn)）相同?！そY(jié)束時(shí)，算出從源節(jié)點(diǎn)到網(wǎng)絡(luò)中所有其他節(jié)點(diǎn)的最短路徑。算法描述：（1）初始化（1#～6#）N'={源節(jié)點(diǎn)u}；對(duì)所有不在N'中的節(jié)點(diǎn)v，寫出其D(v)值：·節(jié)點(diǎn)v與源節(jié)點(diǎn)u直接相連，D(v)=c(u，v)·節(jié)點(diǎn)v與源節(jié)點(diǎn)u不直接相連，D(v)=∞（2）找出一個(gè)到源節(jié)點(diǎn)的費(fèi)用最低的節(jié)點(diǎn)w，并更新其它點(diǎn)D(v)值從不在N'中的節(jié)點(diǎn)中找出一個(gè)D(w)值最小的節(jié)點(diǎn)w，并將w加入到N'中。(9#～#10)對(duì)不在N'中，但與節(jié)點(diǎn)w是鄰居的節(jié)點(diǎn)v，用新的值更新(11#～#14)D(v)=min[D(v)，D(w)+c(w,v)]將節(jié)點(diǎn)v原值與節(jié)點(diǎn)v現(xiàn)經(jīng)節(jié)點(diǎn)w到源節(jié)點(diǎn)的值比較，取小值。（3）重復(fù)步驟(2)直到所有的網(wǎng)絡(luò)節(jié)點(diǎn)都在N'中為止。例，圖4-25網(wǎng)絡(luò)，計(jì)算從u到所有可能目的節(jié)點(diǎn)的最低費(fèi)用路徑。計(jì)算過程如表4-25，表中的每一行表示一次迭代結(jié)束時(shí)的算法變量值。步驟N'D(v),p(v)D(w),p(w)D(x),p(x)D(y),p(y)D(z),p(z)0u2，u5，u1，u∞∞1ux2，u4，x2，x∞2uxy2，u3，y4，y3uxyv3，y4，y4uxyvw4，y5uxyvwz·初始化：與u直接相連的鄰居有v、x、w，而y、z不直接與u連接?！さ谝淮蔚簭牟辉诩螻'中的節(jié)點(diǎn)，找出最低費(fèi)用的節(jié)點(diǎn)為x，其費(fèi)用是1，并加到集合N'中。更新不在集合N'中的節(jié)點(diǎn)v、w、y、z的費(fèi)用D(v)：min(2，1+2)=2；不變D(w)：min(5，1+3)=4；p(w)：xD(y)：min(∞，1+1)=2；p(y)：xD(z)：z不與x直接相連，D(z)不變·第二次迭代：節(jié)點(diǎn)v與y都具有最低費(fèi)用路徑。先選擇y并加到集合N'中。更新不在N'中的其余節(jié)點(diǎn)v、w和z的費(fèi)用D(v)：v不與y直接相連，D(v)不變D(w)：min(4，2+1)=3；p(w)：yD(z)：min(∞，2+2)=4；p(z)：y……構(gòu)建從源節(jié)點(diǎn)到所有目的節(jié)點(diǎn)的完整路徑：LS算法結(jié)束后·對(duì)于每個(gè)節(jié)點(diǎn)，都得到從源節(jié)點(diǎn)沿著它的最低費(fèi)用路徑的前一節(jié)點(diǎn)；·每個(gè)前一節(jié)點(diǎn)，又可得到它的前一節(jié)點(diǎn)；·以此方式繼續(xù)，可以得到到所有目的節(jié)點(diǎn)的完整路徑。如節(jié)點(diǎn)z的前一節(jié)點(diǎn)依次為：zyxu得出從源節(jié)點(diǎn)u到節(jié)點(diǎn)z的最低費(fèi)用路徑為：uxyz，費(fèi)用為4。21211根據(jù)21211根據(jù)得到的所有目的節(jié)點(diǎn)的完整路徑，或最低費(fèi)用路徑樹，可以生成源節(jié)點(diǎn)的轉(zhuǎn)發(fā)表。轉(zhuǎn)發(fā)表：存放從源節(jié)點(diǎn)到每個(gè)目的節(jié)點(diǎn)的最低費(fèi)用路徑上的下一跳節(jié)點(diǎn)。即指出對(duì)于發(fā)往某個(gè)目的節(jié)點(diǎn)的分組，從該節(jié)點(diǎn)發(fā)出后的下一個(gè)節(jié)點(diǎn)。節(jié)點(diǎn)節(jié)點(diǎn)u的轉(zhuǎn)發(fā)表目的點(diǎn)下一跳u－vvwxxxyxzx節(jié)點(diǎn)節(jié)點(diǎn)u的轉(zhuǎn)發(fā)表目的點(diǎn)下一跳u－vv*x默認(rèn)路由*：表示所有具有相同“下一跳”的表項(xiàng)。即將“下一跳”相同的項(xiàng)合并為一項(xiàng)，目的節(jié)點(diǎn)用“*”表示。 優(yōu)先級(jí)最低，轉(zhuǎn)發(fā)分組時(shí)，當(dāng)找不到對(duì)應(yīng)表項(xiàng)時(shí)，才使用默認(rèn)路由。將網(wǎng)絡(luò)中每一個(gè)節(jié)點(diǎn)作為源點(diǎn)，分別用上述方法計(jì)算，可以得到每一個(gè)節(jié)點(diǎn)的轉(zhuǎn)發(fā)表。算法的計(jì)算復(fù)雜性：設(shè)n個(gè)節(jié)點(diǎn)(不算源節(jié)點(diǎn))，最壞情況下要經(jīng)多少次計(jì)算才能找到從源節(jié)點(diǎn)到所有目的節(jié)點(diǎn)的最低費(fèi)用路徑?·第一次迭代：搜索所有的n個(gè)節(jié)點(diǎn)以確定出最低費(fèi)用節(jié)點(diǎn)w；·第二次迭代：檢查n-1個(gè)節(jié)點(diǎn)；·第三次：檢查n-2個(gè)節(jié)點(diǎn)；依次類推。所有迭代中需要搜尋的節(jié)點(diǎn)總數(shù)為n(n+1)/2。算法復(fù)雜性為n平方階序O(n2)。LS算法的缺陷：可能產(chǎn)生“振蕩”。例，圖4-26一個(gè)簡(jiǎn)單網(wǎng)絡(luò)拓?fù)洹ＴO(shè)：·鏈路費(fèi)用等于鏈路上的負(fù)載；·鏈路費(fèi)用是非對(duì)稱的：c(u，v)與c(v，u)僅當(dāng)在鏈路(u，v)兩個(gè)方向的負(fù)載相同時(shí)才相等。有三個(gè)同時(shí)發(fā)往w的注入流量：·節(jié)點(diǎn)z：一個(gè)單元；·節(jié)點(diǎn)x：一個(gè)單元；·節(jié)點(diǎn)y：e的流量。節(jié)點(diǎn)選路情況：·初始：如圖4-26(a)，其鏈路費(fèi)用相當(dāng)于承載的流量?！さ谝淮危汗?jié)點(diǎn)x、y都確定順時(shí)針方向到w的路徑費(fèi)用最低，為1。產(chǎn)生圖4-26(b)費(fèi)用?！さ诙危汗?jié)點(diǎn)x、y、z都確定逆時(shí)針方向到w的路徑費(fèi)用最低，為0。產(chǎn)生圖4-26(c)費(fèi)用?！さ谌危汗?jié)點(diǎn)x、y、z都確定順時(shí)針方向到w的路徑費(fèi)用最低，為0。產(chǎn)生圖4-26(d)費(fèi)用。避免振蕩：·使鏈路費(fèi)用不依賴于所承載的流量：不可行；·避免所有的路由器同時(shí)運(yùn)行LS算法：比較合理。既使路由器以相同周期運(yùn)行LS算法，在每個(gè)節(jié)點(diǎn)上算法的執(zhí)行時(shí)刻也不同。因特網(wǎng)的自同步：既使路由器初始時(shí)以同一周期但不同時(shí)刻執(zhí)行算法，算法執(zhí)行時(shí)刻最終會(huì)同步并保持。采用隨機(jī)時(shí)間的方法，即每臺(tái)路由器隨機(jī)發(fā)送鏈路通告。4.5DV算法是一種迭代的、異步的和分布式的算法?！し植际剑好總€(gè)節(jié)點(diǎn)都從其直接相連鄰居接收信息，進(jìn)行計(jì)算，再將計(jì)算結(jié)果分發(fā)給鄰居。·迭代：計(jì)算過程一直持續(xù)到鄰居之間無更多信息交換為止。·自我終結(jié)：算法能自行停止?！ぎ惒剑翰灰笏泄?jié)點(diǎn)相互之間步伐一致地操作。最低費(fèi)用表示：dx(y)：節(jié)點(diǎn)x到節(jié)點(diǎn)y的最低費(fèi)用路徑的費(fèi)用。用Bellman-Ford方程表示dx(y)=minv{c(x,v)+dv(y)}（4-1）·c(x,v)+dv(y)：x與某個(gè)鄰居v之間的直接鏈路費(fèi)用c(x，v)加上鄰居v到y(tǒng)的最小費(fèi)用。即x經(jīng)某個(gè)直接相連鄰居v到節(jié)點(diǎn)y的最小的路徑費(fèi)用?！inv：從所有經(jīng)直接相連鄰居到節(jié)點(diǎn)y的費(fèi)用中選取的最小路徑費(fèi)用。如圖4-25，源節(jié)點(diǎn)u到目的節(jié)點(diǎn)z的最低費(fèi)用路徑。源節(jié)點(diǎn)u有三個(gè)鄰居：鄰居v：dv(z)=5c(u,v)=鄰居w：dw(z)=3c(u,w)=鄰居x：dx(z)=3c(u,x)=du(z)=min{5+2，3+5，3+1}=4即源節(jié)點(diǎn)u經(jīng)相鄰節(jié)點(diǎn)x到目的節(jié)點(diǎn)z的路徑費(fèi)用最低，為4。節(jié)點(diǎn)x的轉(zhuǎn)發(fā)表表項(xiàng)：目的節(jié)點(diǎn)下一跳路由器設(shè)v*是方程（4-1）中，取得最小值的相鄰節(jié)點(diǎn)，則v*是節(jié)點(diǎn)x到節(jié)點(diǎn)y最低費(fèi)用路徑上的下一跳路由器。如4-25，節(jié)點(diǎn)u的轉(zhuǎn)發(fā)表中，到目的節(jié)點(diǎn)z的下一跳路由器是相鄰節(jié)點(diǎn)x。目的節(jié)點(diǎn)下一跳路由器uxDV算法基本思想：每個(gè)節(jié)點(diǎn)有一張選路表（距離表），維持選路數(shù)據(jù)，隨著算法進(jìn)行，不斷更新，直到靜止。每個(gè)節(jié)點(diǎn)x的選路表維持如下選路數(shù)據(jù)·從x到其每個(gè)鄰居v的費(fèi)用，c(x,v)；·節(jié)點(diǎn)x的距離向量，Dx=[Dx(y)：y在N中]，即節(jié)點(diǎn)x到每個(gè)目的節(jié)點(diǎn)y的估計(jì)費(fèi)用；·某個(gè)鄰居的距離向量，對(duì)x的每個(gè)鄰居v，Dv=[Dv(y)：y在N中]更新其距離向量·每個(gè)節(jié)點(diǎn)不斷向鄰居發(fā)送其距離向量拷貝；·當(dāng)節(jié)點(diǎn)收到一個(gè)鄰居v的新距離向量，先保存，并用方程（4-1）更新自己的距離向量：Dx(y)=minv{c(x,v)+Dv(y)}·若距離向量發(fā)生改變，將新的距離向量通知給鄰居。當(dāng)距離向量不再變化，算法靜止：此時(shí)Dx(y)收斂到dx(y)，即得到節(jié)點(diǎn)x到節(jié)點(diǎn)y的最低費(fèi)用路徑。1、距離向量DV算法描述：對(duì)每個(gè)節(jié)點(diǎn)x（源節(jié)點(diǎn)）

(1)初始化：·對(duì)所有目的點(diǎn)y，若是節(jié)點(diǎn)x的鄰居，則距離向量Dx(y)=c(x,y)；否則，Dx(y)=∞（2#～3#）·節(jié)點(diǎn)x的每一個(gè)鄰居w到所有目的點(diǎn)y的距離向量為Dw(y)=∞（4#～5#）·把節(jié)點(diǎn)x的距離向量Dx=[Dx(y)：y在N中]（節(jié)點(diǎn)x到每個(gè)目的節(jié)點(diǎn)y的估計(jì)費(fèi)用）發(fā)給每一個(gè)鄰居w。（6#～7#）（2）若節(jié)點(diǎn)x看到某個(gè)直接相連的鏈路費(fèi)用變化，或收到鄰居的新距離向量，更新自己的距離向量（10#～11#）·用收到的鄰居的新距離向量更新自己到所有目的點(diǎn)y的距離向量（13#～14#）Dx(y)=minv{c(x,v)+Dv(y)}在經(jīng)每個(gè)鄰居v到目的點(diǎn)y的距離向量中，選擇一個(gè)最小值作為當(dāng)前新距離向量，并將所經(jīng)過的鄰居v作為節(jié)點(diǎn)x轉(zhuǎn)發(fā)表中到目的節(jié)點(diǎn)y的下一跳路由器v*(y)?！と艟嚯x向量發(fā)生改變，向其鄰居發(fā)送新距離向量。（16#～17#）（3）重復(fù)執(zhí)行（2），直到?jīng)]有更新的距離向量發(fā)出為止。圖4-27例。每個(gè)節(jié)點(diǎn)維護(hù)一張選路表（距離表），隨著算法進(jìn)行不斷變化。行：一個(gè)距離向量，每行分別表示該節(jié)點(diǎn)的距離向量和其鄰居的距離向量，即該節(jié)點(diǎn)和鄰居到所有目的節(jié)點(diǎn)的估計(jì)費(fèi)用。列：所有目的節(jié)點(diǎn)。初始化初始化鄰居鄰居鄰居初始化：（第一列）·節(jié)點(diǎn)x選路表：第一行：Dx=[Dx(x),Dx(y),Dx(z)]=[0，2，7]第二行：鄰居y到目的節(jié)點(diǎn)的距離向量，為無窮大∞。第三行：鄰居z到目的節(jié)點(diǎn)的距離向量，為無窮大∞。·節(jié)點(diǎn)y、z選路表同樣方法得到：·每個(gè)節(jié)點(diǎn)分別向鄰居發(fā)送其距離向量。第一次迭代：（第二列）·節(jié)點(diǎn)x選路表：第二行：收到的y的新距離向量。第三行：收到的z的新距離向量。第一行：Dx=[Dx(x),Dx(y),Dx(z)]Dx(x)=0Dx(y)=min{c(x,y)+Dy(y),c(x,z)+Dz(y)}=min{2+0,7+1}=2Dx(z)=min{c(x,y)+Dy(z),c(x,z)+Dz(z)}=min{2+1,7+0}=3經(jīng)過節(jié)點(diǎn)y到目的節(jié)點(diǎn)費(fèi)用最小，此時(shí)節(jié)點(diǎn)x的轉(zhuǎn)發(fā)表中，到節(jié)點(diǎn)y和節(jié)點(diǎn)z的下一跳路由器均是y，即v*(y)=y和v*(z)=y?！す?jié)點(diǎn)y、z的選路表用相同方法計(jì)算其中節(jié)點(diǎn)y的距離向量未變化，不向鄰居發(fā)送更新。節(jié)點(diǎn)x、z分別向鄰居發(fā)送其距離向量?！啻沃貜?fù)從鄰居接收更新距離向量、重新計(jì)算選路表項(xiàng)、并向鄰居發(fā)送更新通知的過程，一直持續(xù)到?jīng)]有更新報(bào)文發(fā)出為止。算法進(jìn)入靜止?fàn)顟B(tài)，直到某個(gè)鏈路費(fèi)用發(fā)生改變?yōu)橹埂?、鏈路費(fèi)用改變與鏈路故障當(dāng)一個(gè)節(jié)點(diǎn)檢測(cè)到從它到鄰居的鏈路費(fèi)用發(fā)生變化時(shí)，就更新其距離向量，如果最低費(fèi)用路徑的費(fèi)用發(fā)生變化，通知其鄰居。（1）某鏈路費(fèi)用減少時(shí)情況例圖4-28。當(dāng)y到x的鏈路費(fèi)用從4變?yōu)?的情況?？紤]y與z到目的節(jié)點(diǎn)x的距離表變化。t0：y檢測(cè)到x的鏈路費(fèi)用從4變?yōu)?，更新其距離向量，并通知其鄰居z；t1：z收到來自y的更新報(bào)文，并更新自己的距離表，此時(shí)到節(jié)點(diǎn)x的最低費(fèi)用減為2，并通知其鄰居y；t2：y收到來自z的更新報(bào)文，并更新自己的距離表，此時(shí)到節(jié)點(diǎn)x的最低費(fèi)用不變?nèi)詾?。不發(fā)送更新報(bào)文，算法靜止。當(dāng)x與y之間費(fèi)用減少，DV算法只需兩次迭代到達(dá)靜止?fàn)顟B(tài)。說明：節(jié)點(diǎn)之間鏈路費(fèi)用減少的“好消息”在網(wǎng)絡(luò)中能迅速傳播。（2）某鏈路費(fèi)用增加時(shí)情況例圖4-28b，設(shè)x與y之間的鏈路費(fèi)用從4增加到60。1）鏈路費(fèi)用變化前Dy(x)=4，Dy(z)=1，Dz(y)=1，Dz(x)=5t0時(shí)刻：y檢測(cè)到鏈路費(fèi)用從4變?yōu)?0。并計(jì)算其到x的新的最低路徑費(fèi)用Dy(x)=min{c(y,x)+Dx(x),c(y,z)+Dz(x)}=min{60+0,1+5}=6經(jīng)節(jié)點(diǎn)z到x費(fèi)用最低，此新費(fèi)用錯(cuò)誤，發(fā)給節(jié)點(diǎn)z。t1時(shí)刻：z收到新費(fèi)用，計(jì)算其到x的新的最低路徑費(fèi)用Dz(x)=min{c(z,x)+Dx(x),c(z,y)+Dy(x)}=min{50+0,1+6}=7經(jīng)節(jié)點(diǎn)y到x費(fèi)用最低，發(fā)給節(jié)點(diǎn)y。t2時(shí)刻：y收到新費(fèi)用，計(jì)算其到x的新的最低路徑費(fèi)用Dy(x)=min{c(y,x)+Dx(x),c(y,z)+Dz(x)}=min{60+0,1+7}=8經(jīng)節(jié)點(diǎn)z到x費(fèi)用最低，發(fā)給節(jié)點(diǎn)z。……節(jié)點(diǎn)y或z的最低費(fèi)用不斷更新。選路回環(huán)(routingloop)：為到達(dá)x，y通過z選路，z又通過y選路。即目的地為x的分組到達(dá)y或z后，將在這兩個(gè)節(jié)點(diǎn)之間不停地來回反復(fù)，直到轉(zhuǎn)發(fā)表發(fā)生改變?yōu)橹埂Ｉ鲜鲅h(huán)將持續(xù)44次迭代(y與z之間的報(bào)文交換)，直到z最終算出它經(jīng)由y的路徑費(fèi)用大于50為止。并確定：·z到x的最低費(fèi)用路徑：zx·y到x的最低費(fèi)用路徑：yzx。說明：鏈路費(fèi)用增加的“壞消息”傳播很慢！當(dāng)鏈路費(fèi)用增加很大，會(huì)出現(xiàn)“計(jì)數(shù)到無窮(count-to-infinity)”問題。如鏈路費(fèi)用c(y，x)變?yōu)?0000，c(z，x)變?yōu)?999時(shí)。3、增加“毒性逆轉(zhuǎn)(PoisonedReverse)”避免出現(xiàn)“選路回環(huán)”現(xiàn)象?；舅枷耄喝绻鹺通過y選路到達(dá)目的地x，則z將告訴y，它到x的距離是無窮大（即z將告訴y，Dz(x)=∞）；y認(rèn)為z沒有到x的路徑，就不會(huì)試圖經(jīng)由z選路到x。例，“毒性逆轉(zhuǎn)”用來解決圖4-28b中的特定環(huán)路。設(shè)使用“毒性逆轉(zhuǎn)”后，y距離表顯示Dz(x)=∞?！0時(shí)刻：(x,y)鏈路費(fèi)用從4變?yōu)?0。y更新其到x的最低費(fèi)用Dy(x)=min{c(y,x)+Dx(x),c(y,z)+Dz(x)}=min{60+0,1+∞}=60直接選路到x，將新費(fèi)用Dy(x)=60，通知z?！1時(shí)刻：z收到新費(fèi)用，計(jì)算其到x的新的最低路徑費(fèi)用Dz(x)=min{c(z,x)+Dx(x),c(z,y)+Dy(x)}=min{50+0,1+60}=50直接選路到x，將新費(fèi)用Dz(x)=50，通知y?！2時(shí)刻：y收到新費(fèi)用，計(jì)算其到x的新的最低路徑費(fèi)用Dy(x)=min{c(y,x)+Dx(x),c(y,z)+Dz(x)}=min{60+0,1+50}=51y經(jīng)z到x費(fèi)用最低，使用“毒性逆轉(zhuǎn)”抑制從y到x方向的路徑?！3時(shí)刻：y通知z，y到x費(fèi)用無窮大，Dy(x)=∞。算法靜止。毒性逆轉(zhuǎn)局限：未解決“不可計(jì)數(shù)問題”。當(dāng)涉及到三個(gè)或更多節(jié)點(diǎn)的回路將不能被毒性逆轉(zhuǎn)技術(shù)檢測(cè)到。4、LS算法與DV算法比較DV算法：每個(gè)節(jié)點(diǎn)只與鄰居互相交流，得到鄰居的新費(fèi)用，并告知鄰居自己的當(dāng)前最低費(fèi)用。LS算法：每個(gè)節(jié)點(diǎn)與所有其他節(jié)點(diǎn)廣播交流，只告知與其直接相連鏈路的費(fèi)用。報(bào)文復(fù)雜性：·LS算法：知道網(wǎng)絡(luò)每條鏈路的費(fèi)用，需發(fā)送O(NE)個(gè)報(bào)文；當(dāng)一條鏈路的費(fèi)用變化時(shí)，必須通知所有節(jié)點(diǎn)?！V算法：迭代時(shí)，在兩個(gè)直接相連鄰居之間交換報(bào)文；收斂時(shí)間受許多因素影響；當(dāng)鏈路費(fèi)用改變時(shí)，只有該鏈路相連的節(jié)點(diǎn)的最低費(fèi)用路徑發(fā)生改變時(shí)，才傳播已改變的鏈路費(fèi)用。收斂速度：·LS算法：需要O(NE)個(gè)報(bào)文和O(N2)的搜尋?！V算法：收斂較慢。可能會(huì)遇到選路回環(huán)，或計(jì)數(shù)到無窮的問題。健壯性：當(dāng)一臺(tái)路由器發(fā)生故障、操作錯(cuò)誤或受到破壞時(shí)，會(huì)產(chǎn)生什么情況?·LS算法：路由器向其連接的一條鏈路廣播不正確費(fèi)用。路由計(jì)算基本獨(dú)立（僅計(jì)算自己的轉(zhuǎn)發(fā)表），有一定健壯性。·DV算法：一個(gè)節(jié)點(diǎn)可向任意或所有目的節(jié)點(diǎn)發(fā)布其不正確的最低費(fèi)用