計(jì)算機(jī)網(wǎng)絡(luò)：第4章 網(wǎng)絡(luò)層

1、第4章 網(wǎng)絡(luò)層運(yùn)輸層：接受網(wǎng)絡(luò)層提供的主機(jī)到主機(jī)的通信服務(wù)為主機(jī)上的兩個(gè)進(jìn)程之間提供通信服務(wù)。只在網(wǎng)絡(luò)的主機(jī)中出現(xiàn)網(wǎng)絡(luò)層：在網(wǎng)絡(luò)的主機(jī)和路由器中出現(xiàn)。 本章主要討論網(wǎng)絡(luò)層如何實(shí)現(xiàn)主機(jī)到主機(jī)的通信服務(wù)。應(yīng)用層運(yùn)輸層網(wǎng)絡(luò)層鏈路層物理層1主要內(nèi)容網(wǎng)絡(luò)層功能和服務(wù)：虛電路和數(shù)據(jù)報(bào)。路由器結(jié)構(gòu)：工作原理。分組轉(zhuǎn)發(fā)：網(wǎng)絡(luò)層的選路：決定分組從源到目的地所經(jīng)路徑的一些選路算法。2主要章節(jié)4. 1 概述4.2 虛電路和數(shù)據(jù)報(bào)網(wǎng)絡(luò)4.3 路由器工作原理4.4 IP 協(xié)議4.5 選路算法4.6 因特網(wǎng)的選路4.7 廣播和多播小結(jié)34. 1 概述發(fā)送方主機(jī)網(wǎng)絡(luò)層的作用將來(lái)自運(yùn)輸層的每個(gè)報(bào)文段封裝成一個(gè)數(shù)據(jù)報(bào)（網(wǎng)絡(luò)層分

2、組）；將數(shù)據(jù)報(bào)向目的地發(fā)送，即向相鄰的路由器R1發(fā)送networkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysical網(wǎng)絡(luò)層數(shù)據(jù)鏈路層物理層applicationtransportnetworkdata linkphysicalapplicationtransportnetworkdata linkphysicalH1H2R1R

3、24接收方主機(jī)網(wǎng)絡(luò)層的作用接收來(lái)自相鄰的路由器R2的數(shù)據(jù)報(bào)；解封出報(bào)文段，并交付給其運(yùn)輸層。路由器的主要作用：將數(shù)據(jù)報(bào)從輸入鏈路“轉(zhuǎn)發(fā)”到輸出鏈路。 只實(shí)現(xiàn)下三層部分。networkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysical網(wǎng)絡(luò)層數(shù)據(jù)鏈路層物理層applicationtransportnetworkdata linkp

4、hysicalapplicationtransportnetworkdata linkphysicalH1H2R1R24.1.1 轉(zhuǎn)發(fā)和選路4.1.2 網(wǎng)絡(luò)服務(wù)模型 51、網(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)。選路：確定分組從發(fā)送方流向接收方時(shí)所經(jīng)過(guò)的路由或路徑。 通過(guò)選路算法計(jì)算路徑。networkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysical

5、networkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysical網(wǎng)絡(luò)層數(shù)據(jù)鏈路層物理層applicationtransportnetworkdata linkphysicalapplicationtransportnetworkdata linkphysicalH2R1R26兩者區(qū)別轉(zhuǎn)發(fā)：將分組從路由器的一個(gè)輸入鏈路接口轉(zhuǎn)移到一個(gè)合適的輸出鏈路接口的本地動(dòng)作。 只涉及分組在路由器中從入鏈路到出鏈路的傳送。選路：指分組從源到目的地端到端路徑的網(wǎng)絡(luò)范圍動(dòng)作。 涉及網(wǎng)絡(luò)中的所有路由器，集體經(jīng)選路協(xié)議交互，決定分組從源到目

6、的地的路徑。類比汽車旅行:選路：計(jì)劃從起點(diǎn)到目的終點(diǎn)行駛路線的過(guò)程。轉(zhuǎn)發(fā)：通過(guò)單個(gè)立交橋的過(guò)程。72、路由器如何轉(zhuǎn)發(fā)分組轉(zhuǎn)發(fā)表：每臺(tái)路由器有一張。分組首部（目的地址或某個(gè)連接標(biāo)識(shí)）和相應(yīng)輸出鏈路的對(duì)照表。轉(zhuǎn)發(fā)表的內(nèi)容由選路算法決定集中式：選路算法在某個(gè)中心點(diǎn)運(yùn)行。分布式：選路算法分布在多個(gè)路由器運(yùn)行。81230111到達(dá)分組首部的值選路算法本地轉(zhuǎn)發(fā)表首部值輸出鏈路01000101011110013221轉(zhuǎn)發(fā)方法路由器根據(jù)到達(dá)分組的首部值在轉(zhuǎn)發(fā)表中查詢。找到相應(yīng)的輸出鏈路接口，并將分組轉(zhuǎn)發(fā)出去。93、術(shù)語(yǔ)分組交換機(jī)：一臺(tái)通用分組交換設(shè)備，根據(jù)分組首部值，從輸入鏈路接口到輸出鏈路接口傳送分組。鏈路

7、層交換機(jī)：根據(jù)鏈路層字段值作轉(zhuǎn)發(fā)決定的分組交換機(jī)。路由器：根據(jù)網(wǎng)絡(luò)層字段值作轉(zhuǎn)發(fā)決定的分組交換機(jī)。104、連接建立運(yùn)輸層連接： 如TCP協(xié)議，在數(shù)據(jù)實(shí)際傳輸之前，發(fā)送方和接收方經(jīng)過(guò)三次握手建立所需的狀態(tài)信息。網(wǎng)絡(luò)連接： 網(wǎng)絡(luò)層數(shù)據(jù)分組開(kāi)始傳輸前，在所選擇的源到目的地路徑上的各路由器之間相互握手，建立連接狀態(tài)。 如ATM、幀中繼的網(wǎng)絡(luò)層。 因特網(wǎng)網(wǎng)絡(luò)層不執(zhí)行連接建立。使用IP協(xié)議！114.1.2 網(wǎng)絡(luò)服務(wù)模型問(wèn)題：發(fā)送主機(jī)的運(yùn)輸層是否能依靠網(wǎng)絡(luò)層將分組交付到目的地；多個(gè)分組是否能按發(fā)送順序交付給接收主機(jī)的運(yùn)輸層；傳輸兩個(gè)連續(xù)分組的時(shí)間間隔是否與接收到的時(shí)間間隔相同；網(wǎng)絡(luò)層是否能提供網(wǎng)絡(luò)擁塞的反饋

8、信息；連接發(fā)送與接收主機(jī)的運(yùn)輸層通道的抽象視圖（特性）是什么？ 由網(wǎng)絡(luò)層提供的服務(wù)模型來(lái)確定。121、網(wǎng)絡(luò)層可能提供的服務(wù)確保交付：確保分組到達(dá)目的地。具有時(shí)延上界的確保交付：主機(jī)到主機(jī)的時(shí)延。有序分組交付：按發(fā)送順序到達(dá)。確保最小帶寬：發(fā)送主機(jī)以低于特定比特率的速率發(fā)送比特，分組不會(huì)丟失，在一定時(shí)延到達(dá)。確保最大時(shí)延抖動(dòng)：發(fā)送方發(fā)送兩個(gè)連續(xù)分組的時(shí)間間隔與接收到的間隔相同。132、因特網(wǎng)網(wǎng)絡(luò)層提供的服務(wù) 單一的服務(wù)，即盡力而為服務(wù)(best-effort service)，類似于“根本無(wú)服務(wù)”。分組間的定時(shí)不能被保證；分組的接收順序與發(fā)送順序不一定相同；傳送的分組不能保證最終交付，即網(wǎng)絡(luò)可能

9、未向目的地交付分組。143、ATM服務(wù)模型 提供多重的服務(wù)模型，即在同一網(wǎng)絡(luò)中為不同的連接提供不同類別的服務(wù)。恒定比特率CBR (Costant bit rate)服務(wù)：可用比特率ABR (Available bit rate)服務(wù)：15恒定比特率CBR服務(wù) 標(biāo)準(zhǔn)的ATM服務(wù)模型。適用于實(shí)時(shí)、恒定比特率的音頻和視頻流。服務(wù)目標(biāo)：使網(wǎng)絡(luò)連接看起來(lái)就像在發(fā)送主機(jī)和接收主機(jī)之間有一條專用的固定帶寬的傳輸鏈路。ATM信元傳輸時(shí)的端到端時(shí)延可變性(時(shí)延抖動(dòng))及丟失、遲交的信元都保證在規(guī)定值以下。16可用比特率ABR “比盡力服務(wù)稍好一點(diǎn)”的服務(wù)?？赡軙?huì)丟失信元；保證最小信元傳輸速率 (MCR)，或比MC

10、R更高（有足夠空閑資源）；能夠?yàn)榘l(fā)送方提供反饋信息。17網(wǎng)絡(luò)層服務(wù)模型網(wǎng)絡(luò)體系結(jié)構(gòu)服務(wù)模型帶寬保證無(wú)丟失保證排序定時(shí)擁塞指示因特網(wǎng)盡力而為 無(wú) 無(wú)任何可能順序不維持 無(wú)ATMCBR保證恒定速率 是有序維持擁塞不出現(xiàn)ATMABR保證最小速率 無(wú)有序不維持提供擁塞指示184.2 虛電路和數(shù)據(jù)報(bào)網(wǎng)絡(luò)運(yùn)輸層：提供無(wú)連接服務(wù)和面向連接服務(wù)。 如因特網(wǎng)的UDP、TCP 。網(wǎng)絡(luò)層：提供無(wú)連接服務(wù)和面向連接服務(wù)。面向連接服務(wù)：源和目的主機(jī)之間先握手。無(wú)連接服務(wù)：無(wú)握手過(guò)程。19區(qū)別網(wǎng)絡(luò)層：向運(yùn)輸層提供主機(jī)到主機(jī)的服務(wù)。 運(yùn)輸層：向應(yīng)用層提供進(jìn)程到進(jìn)程的服務(wù)。網(wǎng)絡(luò)層：任何網(wǎng)絡(luò)中的網(wǎng)絡(luò)層只提供兩種服務(wù)之一，不會(huì)同

11、時(shí)提供。虛電路網(wǎng)絡(luò)：提供連接服務(wù)。數(shù)據(jù)報(bào)網(wǎng)絡(luò)：提供無(wú)連接服務(wù)。運(yùn)輸層：面向連接服務(wù)在網(wǎng)絡(luò)邊緣的端系統(tǒng)中實(shí)現(xiàn) 網(wǎng)絡(luò)層：面向連接服務(wù)在端系統(tǒng)及網(wǎng)絡(luò)核心的路由器中實(shí)現(xiàn)。20本節(jié)內(nèi)容4.2.1 虛電路網(wǎng)絡(luò)4.2.2 數(shù)據(jù)報(bào)網(wǎng)絡(luò)4.2.3 數(shù)據(jù)報(bào)和虛電路服務(wù)的由來(lái)214.2.1 虛電路網(wǎng)絡(luò) 如X.25、幀中繼和ATM等。 根據(jù)虛電路號(hào)轉(zhuǎn)發(fā)分組。221、虛電路VC 組成源和目的地之間的一條邏輯連接路徑：一系列鏈路和路由器。VC號(hào)：該路徑上每段鏈路的號(hào)碼，每條鏈路上的VC號(hào)可能不同。轉(zhuǎn)發(fā)表：VC路徑上每臺(tái)路由器中都有該表。根據(jù)轉(zhuǎn)發(fā)表進(jìn)行轉(zhuǎn)發(fā)?？梢酝瑫r(shí)創(chuàng)建多條虛電路。232、VC號(hào)轉(zhuǎn)發(fā)表結(jié)構(gòu) 入接口 入VC

12、# 出接口 出VC #1 12 2 222 63 1 18 3 7 2 171 97 3 87 例，R1中的VC號(hào)轉(zhuǎn)發(fā)表。路由器維護(hù)連接狀態(tài)信息!122232132VC號(hào)BR1R2R3R4AVC1VC2VC3VC46318接口號(hào)：路由器連接鏈路的接口號(hào)碼。物理線路未獨(dú)占：可同時(shí)建多條虛電路。服務(wù)可靠：到達(dá)順序與發(fā)送順序一致。24VC號(hào)轉(zhuǎn)發(fā)表維持只要該路由器創(chuàng)建新的VC，其轉(zhuǎn)發(fā)表中就增加一項(xiàng)；終止一個(gè)VC，其轉(zhuǎn)發(fā)表中就刪除對(duì)應(yīng)項(xiàng)。路由器必須為正在進(jìn)行的連接維護(hù)連接狀態(tài)信息，直到該連接釋放。每條鏈路采用不同VC號(hào)的優(yōu)點(diǎn)：減少分組首部VC字段的長(zhǎng)度；簡(jiǎn)化虛電路的建立過(guò)程。253、工作過(guò)程在源和目的之

13、間創(chuàng)建一個(gè)VC；源向該VC發(fā)送帶有VC號(hào)的分組；每經(jīng)過(guò)一臺(tái)中間路由器，用新的VC號(hào)代替原VC號(hào)： 從VC號(hào)轉(zhuǎn)發(fā)表獲得。分組在每條鏈路上的VC號(hào)不同。依此規(guī)則，直到目的地。26主機(jī)A與主機(jī)B通信過(guò)程122232132VC號(hào)接口號(hào):路由器連接鏈路的接口號(hào)碼。 主機(jī)A與主機(jī)B之間創(chuàng)建一條VC： 路徑為A R1 R2 B，3個(gè)鏈路分配VC號(hào)12、22和32。 傳輸時(shí)，分組VC號(hào)變化過(guò)程： 12 22 32 A R1 R2 BABR1R2R3R427虛電路的三個(gè)階段虛電路建立：在發(fā)送方與接收方之間建立一條虛電路，即決定所有分組要通過(guò)的一系列鏈路與路由器，并為每條鏈路確定一個(gè)VC號(hào)。發(fā)送方與網(wǎng)絡(luò)層聯(lián)系，指

14、定接收方地址，由網(wǎng)絡(luò)建立虛電路 (VC)。如圖4-4（14步）。涉及到路徑上每個(gè)路由器轉(zhuǎn)發(fā)表的更新、資源預(yù)留等應(yīng)用運(yùn)輸網(wǎng)絡(luò)數(shù)據(jù)鏈路物理應(yīng)用運(yùn)輸網(wǎng)絡(luò)數(shù)據(jù)鏈路物理1. 發(fā)起呼叫2. 入呼叫3. 接受呼叫4. 呼叫已連接28應(yīng)用運(yùn)輸網(wǎng)絡(luò)數(shù)據(jù)鏈路物理應(yīng)用運(yùn)輸網(wǎng)絡(luò)數(shù)據(jù)鏈路物理1. 發(fā)起呼叫2. 入呼叫3. 接受呼叫4. 呼叫已連接5. 數(shù)據(jù)流開(kāi)始6. 接收數(shù)據(jù)虛電路的三個(gè)階段數(shù)據(jù)傳送： 沿該虛電路傳輸數(shù)據(jù)分組（56步） 虛電路拆除： 由其中一方通知其網(wǎng)絡(luò)層終止該虛電路；通知網(wǎng)絡(luò)另一側(cè)的端系統(tǒng)呼叫結(jié)束，并更新路徑上每臺(tái)路由器中的轉(zhuǎn)發(fā)表。29網(wǎng)絡(luò)層與運(yùn)輸層連接建立區(qū)別運(yùn)輸層的連接建立： 只涉及兩個(gè)端系統(tǒng)，相

15、互協(xié)商通信并共同確定連接的參數(shù)。網(wǎng)絡(luò)中的路由器并不知道該運(yùn)輸層連接。網(wǎng)絡(luò)層虛電路建立： 沿兩個(gè)端系統(tǒng)之間路徑上的路由器都要參與虛電路的建立，且每個(gè)路由器都完全知道所經(jīng)過(guò)的所有虛電路。30相關(guān)術(shù)語(yǔ)信令報(bào)文： 端系統(tǒng)向網(wǎng)絡(luò)發(fā)送的指示虛電路的啟動(dòng)與終止的報(bào)文、以及路由器之間傳遞的用于建立虛電路的報(bào)文。信令協(xié)議：用來(lái)交換信令報(bào)文的協(xié)議。314.2.2 數(shù)據(jù)報(bào)網(wǎng)絡(luò) 如，因特網(wǎng)。網(wǎng)絡(luò)層無(wú)呼叫建立路由器沒(méi)有端到端連接的狀態(tài)無(wú)網(wǎng)絡(luò)級(jí)“連接”的概念分組使用目的主機(jī)地址轉(zhuǎn)發(fā)相同源和目的地的分組可能采用不同的路徑32傳輸過(guò)程發(fā)送方給要發(fā)送的分組加上目的端系統(tǒng)地址，并送入網(wǎng)絡(luò)；經(jīng)過(guò)若干中間路由器轉(zhuǎn)發(fā)分組，直到目的地。

16、 應(yīng)用運(yùn)輸網(wǎng)絡(luò)數(shù)據(jù)鏈路物理應(yīng)用運(yùn)輸網(wǎng)絡(luò)數(shù)據(jù)鏈路物理1. 發(fā)送數(shù)據(jù)2. 接收數(shù)據(jù)33 根據(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位， 40億可能的項(xiàng)。 路由器轉(zhuǎn)發(fā)方法34轉(zhuǎn)發(fā)表結(jié)構(gòu) 目的地址范圍 鏈路接口 11001000 00010111 00010000 00000000 到 0 11001000 00010111 00010111 11111111 11001000 00010111 00011000 00000000 到

17、1 11001000 00010111 00011000 11111111 11001000 00010111 00011001 00000000 到 2 11001000 00010111 00011111 11111111 其他 3例，某個(gè)路由器有4條鏈路（03），地址與鏈路接口關(guān)系：是否可簡(jiǎn)化？將前綴相同的合并為一項(xiàng)35最長(zhǎng)前綴匹配轉(zhuǎn)發(fā)表 前綴匹配 鏈路接口 11001000 00010111 00010 0 11001000 00010111 00011000 1 11001000 00010111 00011 2 其他 336路由器查表方法用目的地址前綴與轉(zhuǎn)發(fā)表的前綴比較匹配：存在匹

18、配：向?qū)?yīng)鏈路轉(zhuǎn)發(fā)。 如，目的地址 11001000 00010111 00010110 10100001 不存在匹配：選擇“其他”項(xiàng)對(duì)應(yīng)的鏈路轉(zhuǎn)發(fā)。存在多個(gè)匹配：使用最長(zhǎng)前綴匹配規(guī)則，即向與最長(zhǎng)前綴匹配的鏈路接口轉(zhuǎn)發(fā)分組。 如，目的地址 11001000 00010111 00011000 10101010 0#1#前綴匹配 鏈路接口11001000 00010111 00010 0 11001000 00010111 00011000 111001000 00010111 00011 2 其他 337說(shuō)明數(shù)據(jù)報(bào)網(wǎng)絡(luò)：路由器轉(zhuǎn)發(fā)表只維持轉(zhuǎn)發(fā)狀態(tài)信息。 由選路算法修改（15分鐘更新）。一個(gè)端系

19、統(tǒng)發(fā)送給另一個(gè)端系統(tǒng)的一批分組可能在網(wǎng)絡(luò)中選擇不同的路徑，到達(dá)的順序可能不一致。虛電路網(wǎng)絡(luò)：轉(zhuǎn)發(fā)表隨虛電路的建立和拆除更新。38虛電路服務(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)單。 39數(shù)據(jù)報(bào)服務(wù)由互連計(jì)算機(jī)的需求發(fā)展而來(lái)。與電話網(wǎng)相反。網(wǎng)絡(luò)層服務(wù)模型簡(jiǎn)單。端系統(tǒng)功能復(fù)雜：高層實(shí)現(xiàn)許多功能，如按序傳送、可靠數(shù)據(jù)傳輸、擁塞控制與DNS名字解析等帶來(lái)的結(jié)果：因特網(wǎng)服務(wù)模型提供的服務(wù)保證最少（可能沒(méi)有?。?duì)網(wǎng)絡(luò)層的需求最小，使得互連使用各種不同鏈路層技術(shù)的網(wǎng)絡(luò)變得更加容易。許多應(yīng)用都在位于網(wǎng)絡(luò)邊緣的主

20、機(jī)（服務(wù)器）上實(shí)現(xiàn)404.3 路由器工作原理網(wǎng)絡(luò)層轉(zhuǎn)發(fā)功能：將分組從路由器的輸入鏈路傳送到適當(dāng)?shù)妮敵鲦溌贰Ｂ酚善鞯捏w系結(jié)構(gòu)：輸入端口選路處理器交換結(jié)構(gòu)輸出端口物理層數(shù)據(jù)鏈路層排隊(duì)查找轉(zhuǎn)發(fā)排隊(duì)緩存數(shù)據(jù)鏈路層物理層41輸入端口將輸入物理鏈路端接到路由器的物理層；實(shí)現(xiàn)路由器的數(shù)據(jù)鏈路層功能；實(shí)現(xiàn)查找與轉(zhuǎn)發(fā)功能，以便分組通過(guò)路由器交換結(jié)構(gòu)轉(zhuǎn)發(fā)到適當(dāng)?shù)妮敵龆丝?；將控制性分組從輸入端口轉(zhuǎn)發(fā)到選路處理器。 通常，路由器中的多個(gè)端口被集中到一塊線路卡（line card）上。42交換結(jié)構(gòu) 將路由器的輸入端口連接到它的輸出端口。完全包含在路由器中。43輸出端口存儲(chǔ)經(jīng)過(guò)交換結(jié)構(gòu)轉(zhuǎn)發(fā)給它的分組，并將分組發(fā)送到輸出鏈

21、路。完成與輸入端口順序相反的數(shù)據(jù)鏈路層和物理層功能。 對(duì)雙向鏈路，輸出端口與其輸入端口通常在同一線路卡上成對(duì)出現(xiàn)。44選路處理器 執(zhí)行選路協(xié)議、維護(hù)選路信息和轉(zhuǎn)發(fā)表以及執(zhí)行路由器中的網(wǎng)絡(luò)管理功能。 因特網(wǎng)路由器市場(chǎng)，Cisco公司主導(dǎo)產(chǎn)品。4.3.1 輸入端口4.3.2 交換結(jié)構(gòu)4.3.3 輸出端口4.3.4 何時(shí)出現(xiàn)排隊(duì)454.3.1 輸入端口線路端接與數(shù)據(jù)鏈路處理： 實(shí)現(xiàn)與輸入鏈路相關(guān)的物理層和數(shù)據(jù)鏈路層功能。查找、轉(zhuǎn)發(fā)、排隊(duì)。輸入鏈路線路端接數(shù)據(jù)鏈路處理（協(xié)議、拆封）查表、轉(zhuǎn)發(fā)排隊(duì)交換結(jié)構(gòu)46查找/轉(zhuǎn)發(fā) 確定將一個(gè)到達(dá)的分組通過(guò)交換結(jié)構(gòu)轉(zhuǎn)發(fā)給哪個(gè)輸出端口。 通過(guò)查找轉(zhuǎn)發(fā)表實(shí)現(xiàn)。分散式轉(zhuǎn)發(fā)

22、：選路處理器計(jì)算轉(zhuǎn)發(fā)表，給每個(gè)輸入端口存放一份拷貝，能隨選路更新。在每個(gè)輸入端口本地做出交換決策，無(wú)須激活中央選路處理器。可避免在路由器中某個(gè)單點(diǎn)產(chǎn)生轉(zhuǎn)發(fā)處理瓶頸。47查找/轉(zhuǎn)發(fā)集中式轉(zhuǎn)發(fā)：路由器的輸入端口處理能力有限；直接將分組轉(zhuǎn)發(fā)給中央選路處理器，查找轉(zhuǎn)發(fā)表并將分組轉(zhuǎn)發(fā)到適當(dāng)?shù)妮敵龆丝凇?如，將工作站或服務(wù)器用作路由器時(shí)采用。選路處理器就是CPU，輸入端口是一塊網(wǎng)絡(luò)接口卡。48查表速度查表：搜索轉(zhuǎn)發(fā)表，查找最長(zhǎng)匹配的表項(xiàng)，若無(wú)相應(yīng)表項(xiàng)找出默認(rèn)選路表項(xiàng)。查找速度：受許多因素影響，如路由器速度、鏈路速率、查找算法等。目標(biāo)：輸入端口的處理速度要超過(guò)線路速度。 即完成一次查找的時(shí)間應(yīng)少于從輸入端口

23、接收一個(gè)分組所需的時(shí)間（對(duì)收到的分組的輸入處理在下一個(gè)接收操作結(jié)束之前完成）。 減少排隊(duì)49查找方法線性查找：按順序找。對(duì)龐大的轉(zhuǎn)發(fā)表不合適。二分查找：將轉(zhuǎn)發(fā)表表項(xiàng)存放在一個(gè)樹(shù)形數(shù)據(jù)結(jié)構(gòu)中。 樹(shù)的每一層對(duì)應(yīng)目的地址的一個(gè)比特，查找某個(gè)地址時(shí)，從樹(shù)的根節(jié)點(diǎn)開(kāi)始，依次查地址的每一位。內(nèi)容可尋址內(nèi)存(CAM)：將一個(gè)32bit IP地址提交給CAM，由它以常數(shù)時(shí)間返回該地址對(duì)應(yīng)的轉(zhuǎn)發(fā)表表項(xiàng)內(nèi)容。如，Cisco8500系列。 將最近被訪問(wèn)的表項(xiàng)保存在高速緩存(cache)中50二分查找第一比特： 0：左子樹(shù)包含與該目的地址對(duì)應(yīng)的轉(zhuǎn)發(fā)表表項(xiàng)； 1：表項(xiàng)在右子樹(shù)中。 下一比特： 0：選擇初始子樹(shù)的左子樹(shù)；

24、 1：選擇初始子樹(shù)的右子樹(shù)。 N步之內(nèi)可找到相應(yīng)的轉(zhuǎn)發(fā)表表項(xiàng)（N是地址的位數(shù)，地址空間為2N）。 如，因特網(wǎng)32bit IP地址需32步。00110100 01 10 1151輸入端口可能出現(xiàn)問(wèn)題分組阻塞 (blocked)： 來(lái)自其他輸入端口的分組當(dāng)前正在使用交換結(jié)構(gòu)。 被阻塞的分組必須在輸入端口處排隊(duì)，等待以后調(diào)度通過(guò)交換結(jié)構(gòu)。524.3.2 交換結(jié)構(gòu)內(nèi)存總線縱橫制將分組從輸入端口交換（轉(zhuǎn)發(fā)）到輸出端口。531、經(jīng)內(nèi)存交換早期用計(jì)算機(jī)作為路由器輸入端口與輸出端口之間的交換由CPU(選路處理器)控制完成；輸入端口與輸出端口類似I/O設(shè)備： 當(dāng)分組到達(dá)輸入端口時(shí)，通過(guò)中斷向選路處理器發(fā)出信號(hào)，

25、將分組拷貝到處理器內(nèi)存中； 選路處理器根據(jù)分組中的目的地址查表找出適當(dāng)?shù)妮敵龆丝?，將該分組拷貝到輸出端口的緩存中。 54輸入端口輸出端口內(nèi)存系統(tǒng)總線轉(zhuǎn)發(fā)速度受內(nèi)存帶寬的速度限制 (每個(gè)分組穿過(guò)兩次總線) 若內(nèi)存帶寬為每秒寫(xiě)入或讀出B個(gè)分組，則總的轉(zhuǎn)發(fā)吞吐量 (分組從輸入端口被傳送到輸出端口的總速率)小于B/2。55 改進(jìn)現(xiàn)代路由器改進(jìn)：由輸入線路上的處理器來(lái)執(zhí)行目的地址的查找，并將分組存儲(chǔ)(交換)進(jìn)適當(dāng)?shù)拇鎯?chǔ)位置。類似共享內(nèi)存的多處理機(jī)，用一個(gè)線路卡上的處理器將分組存儲(chǔ)進(jìn)適當(dāng)輸出端口的內(nèi)存中。 如，Cisco 8500。562、經(jīng)總線交換 輸入端口通過(guò)一條共享總線將分組直接傳送到輸出端口，不需

26、要選路處理器的干預(yù)?？偩€每次只能有一個(gè)分組通過(guò)總線傳送。分組到達(dá)一個(gè)輸入端口時(shí)，若總線正忙，會(huì)被暫時(shí)阻塞，在輸入端口排隊(duì)。路由器交換帶寬受總線速率限制。573、經(jīng)交換矩陣交換縱橫式交換機(jī)：由2n條總線組成，n個(gè)輸入端口與n個(gè)輸出端口連接。 到達(dá)輸入端口的分組沿水平總線穿行，直至與所希望的輸出端口的垂直總線交叉點(diǎn)：若該垂直總線空閑，則分組被傳送到輸出端口否則，該分組被阻塞，在輸入端口排隊(duì)。高級(jí)設(shè)計(jì): 數(shù)據(jù)報(bào)分割成固定長(zhǎng)度信元, 通過(guò)交換矩陣來(lái)交換信元。584.3.3 輸出端口 取出存放在輸出端口內(nèi)存中的分組，并將其傳輸?shù)捷敵鲦溌飞稀?當(dāng)交換結(jié)構(gòu)將分組交付給輸出端口的速率超過(guò)輸出鏈路速率，就需要排

27、隊(duì)與緩存管理功能。交換結(jié)構(gòu)排隊(duì)：緩存管理數(shù)據(jù)鏈路處理(協(xié)議、解封)線路端接594.3.4 何時(shí)出現(xiàn)排隊(duì)輸入端口和輸出端口都會(huì)形成分組隊(duì)列。當(dāng)隊(duì)列逐步增長(zhǎng)，路由器緩存空間滿，在輸入端口或輸出端口出現(xiàn)分組丟失 (packet loss)。丟失具體位置，取決于流量負(fù)載、交換結(jié)構(gòu)的相對(duì)速度、線路速度等因素。假定：輸入線路速率與輸出線路速率相同有n個(gè)輸入端口和n個(gè)輸出端口交換結(jié)構(gòu)速率：將分組從輸入端口移動(dòng)到輸出端口的速率。601、輸入端口何時(shí)不排隊(duì) 若交換結(jié)構(gòu)的速率至少是輸入線路速率的n倍，在輸入端口處不會(huì)出現(xiàn)排隊(duì)。 最壞情況：有n條輸入線路同時(shí)接收分組。 交換結(jié)構(gòu)可以在每個(gè)輸入端口(同時(shí))接收一個(gè)分組

28、的時(shí)間內(nèi)將n個(gè)分組從輸入端口傳送到輸出端口。n條n條n倍接收轉(zhuǎn)發(fā)612、輸入端口何時(shí)排隊(duì) 交換結(jié)構(gòu)比輸入端口總和的速度慢時(shí)產(chǎn)生。交換結(jié)構(gòu)不夠快：即相對(duì)于輸入線路速度不能快得使所有到達(dá)的分組無(wú)延遲地通過(guò)它傳送。在輸入端口出現(xiàn)分組排隊(duì)：等待通過(guò)交換結(jié)構(gòu)傳送到輸出端口。623、輸出端口何時(shí)排隊(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ù)分

29、組被丟棄63例假定：線路速度相同，交換結(jié)構(gòu)處理速度是線路速度的3倍。交換結(jié)構(gòu)交換結(jié)構(gòu)在時(shí)間t輸出端口競(jìng)爭(zhēng)一個(gè)分組時(shí)間以后 t時(shí)刻：每個(gè)輸入端口都到達(dá)一個(gè)分組，都發(fā)往最上側(cè)的輸出口 一個(gè)單位時(shí)間后（接收或發(fā)送一個(gè)分組的時(shí)間）： 三個(gè)原始分組都被傳送到輸出端口，并排隊(duì)等待發(fā)送。 又有兩個(gè)新分組到達(dá)交換結(jié)構(gòu)的輸入端，其中的一個(gè)分組要發(fā)往最右上側(cè)的輸出端口。下一個(gè)單位時(shí)間：三個(gè)分組中的一個(gè)通過(guò)輸出鏈路發(fā)送出去。 64分組調(diào)度程序 在輸出端口排隊(duì)的分組中選出一個(gè)發(fā)送。原則：先來(lái)先服務(wù)FCFS：簡(jiǎn)單。加權(quán)公平排隊(duì)WFQ：在具有排隊(duì)分組的不同端到端連接之間公平地共享輸出鏈路。65分組丟棄方法若緩存已滿，丟棄

30、分組。丟棄后到的分組（棄尾）；刪除一個(gè)或多個(gè)已排隊(duì)的分組； 活動(dòng)隊(duì)列管理AQM算法：在緩存填滿前丟棄分組 或 首部加標(biāo)記，向發(fā)送方提供擁塞信號(hào)。 如，隨機(jī)早期檢測(cè)RED算法： 輸出隊(duì)列長(zhǎng)度維護(hù)一個(gè)加權(quán)平均值。66隨機(jī)早期檢測(cè)RED算法設(shè)最小閾值minth和最大閾值maxth平均隊(duì)列長(zhǎng)度小于最小閾值minth，到達(dá)分組被納入隊(duì)列；隊(duì)列滿或平均隊(duì)列長(zhǎng)度大于最大閾值maxth ，到達(dá)分組被標(biāo)記或丟棄；平均隊(duì)列長(zhǎng)度在minth， maxth之間，到達(dá)分組以某種概率被標(biāo)記或丟棄。674. 縱橫式交換結(jié)構(gòu)假定：所有鏈路速度相同；交換結(jié)構(gòu)速率與輸入鏈路速率相同：分組從輸入端口傳送到給定輸出端口的時(shí)間與從輸入

31、鏈路接收一個(gè)分組的時(shí)間相同；分組按FCFS方式從輸入隊(duì)列移動(dòng)到輸出隊(duì)列中。結(jié)果：分組輸出端口不同：多個(gè)分組可以被并行傳送。發(fā)往相同輸出端口：不同輸入隊(duì)列中的分組發(fā)往同一輸出隊(duì)列，其中的一些分組被阻塞，在輸入隊(duì)列中等待（交換結(jié)構(gòu)一次傳一個(gè)分組到端口）68例不同輸入隊(duì)列前端的兩個(gè)分組要發(fā)往右上角的同一輸出端口。若先發(fā)送左上角隊(duì)列前端的分組，左下角隊(duì)列中的分組要等待，左下角隊(duì)列中排在該分組后面的分組也要等待。線頭HOL (head-of-the-line)阻塞： 輸入隊(duì)列中后面的分組被位于線頭的一個(gè)分組阻塞(即使輸出端口空閑的)，等待交換結(jié)構(gòu)發(fā)送。時(shí)間t：輸出端口競(jìng)爭(zhēng)，僅一個(gè)紅色分組能被傳輸時(shí)間t1

32、：綠色分組經(jīng)歷了HOL阻塞交換結(jié)構(gòu)69 4.4 Internet 網(wǎng)絡(luò)層組成轉(zhuǎn)發(fā)表選路協(xié)議路徑選擇RIP, OSPF, BGPIP 網(wǎng)際協(xié)議編址規(guī)則數(shù)據(jù)報(bào)格式分組處理規(guī)則ICMP 網(wǎng)際控制報(bào)文協(xié)議差錯(cuò)報(bào)告路由器“信令”運(yùn)輸層: TCP, UDP鏈路層物理層網(wǎng)絡(luò)層70IP：無(wú)連接交付系統(tǒng)提供不可靠、盡力而為、無(wú)連接分組交付服務(wù)不可靠：分組可能丟失、重復(fù)、延遲或不按序交付等，但服務(wù)不檢測(cè)這些情況，也不提醒發(fā)送方和接收方。盡力而為：并不隨意地丟棄分組；只有當(dāng)資源用完或底層網(wǎng)絡(luò)出現(xiàn)故障時(shí)才可能出現(xiàn)不可靠性。無(wú)連接：每個(gè)分組都是獨(dú)立對(duì)待的。分組序列可能經(jīng)過(guò)不同的傳輸路徑或者有的丟失有的到達(dá)。71IP 數(shù)

33、據(jù)報(bào)格式（IPv4）ver長(zhǎng)度32 bits數(shù)據(jù)(變長(zhǎng),通常是一個(gè)TCP或UDP段)16-bit標(biāo)識(shí)符首部檢查和生存期32 bit源IP地址IP協(xié)議版本號(hào)首部長(zhǎng)度 (以4字節(jié)為單位)剩余跳的最大數(shù)(在每臺(tái)路由器減1)用于分段/重裝總數(shù)據(jù)報(bào)長(zhǎng)度(字節(jié))高層處理的協(xié)議如TCP或UDP首部長(zhǎng)度服務(wù)類型區(qū)分服務(wù)的“類型”(一般不用)標(biāo)志段偏移協(xié)議32 bit目的IP地址選項(xiàng) (如果有的話)例如，時(shí)間戳，記錄所經(jīng)路徑，定義訪問(wèn)的路由器列表20字節(jié)首部長(zhǎng)度：4位。無(wú)選項(xiàng)時(shí)，為20字節(jié)?？傞L(zhǎng)度：16位。包含首部和數(shù)據(jù)。生存期TTL：避免分組無(wú)限循環(huán)傳輸。72IP分片和重新組裝網(wǎng)絡(luò)鏈路幀有最大傳輸單元（MTU

34、）長(zhǎng)度，不同鏈路長(zhǎng)度不同。分段：大IP 數(shù)據(jù)報(bào)被分割成幾個(gè)傳輸。重裝：在目的主機(jī)組裝。 通過(guò)標(biāo)識(shí)、標(biāo)志、偏移表示原屬于哪個(gè)數(shù)據(jù)報(bào)、第幾段。分段: 輸入: 1個(gè)大的數(shù)據(jù)報(bào)輸出: 3個(gè)小的數(shù)據(jù)報(bào)重新組裝MTU：4000字節(jié)MTU：1500字節(jié)73例ID=x偏移=0段標(biāo)志=0長(zhǎng)度=4000數(shù)據(jù)報(bào)：4000字節(jié) 去掉20字節(jié)首部，有效數(shù)據(jù)3980字節(jié) MTU = 1500字節(jié) 去掉20字節(jié)首部，有效數(shù)據(jù)1480字節(jié) 大數(shù)據(jù)報(bào)分為3個(gè)較小的數(shù)據(jù)報(bào)偏移值：片號(hào)偏移數(shù) 偏移數(shù)：為MTU/8 1480/8 =185數(shù)據(jù)報(bào)標(biāo)識(shí)是否最后片（還有分片？）片從原始數(shù)據(jù)報(bào)的第幾個(gè)字節(jié)開(kāi)始： 偏移值80 14791480

35、 29592960 3979片0片1片2偏移值： 1185=185原始位置：1858=1480偏移值： 2185=370原始位置：3708=296074例ID=x偏移=0段標(biāo)志=0長(zhǎng)度=4000ID=x偏移=0段標(biāo)志=1長(zhǎng)度=1500ID=x偏移=185段標(biāo)志=1長(zhǎng)度=1500ID=x偏移=370段標(biāo)志=0長(zhǎng)度=1040一個(gè)大數(shù)據(jù)報(bào)分為3個(gè)較小的數(shù)據(jù)報(bào)數(shù)據(jù)字段1480 字節(jié)數(shù)據(jù)報(bào)標(biāo)識(shí)是否最后片片從原始數(shù)據(jù)報(bào)的第幾個(gè)字節(jié)開(kāi)始： 偏移值81852從1858=1480開(kāi)始從3708=2960開(kāi)始75IP地址網(wǎng)絡(luò)層地址：互連網(wǎng)中主機(jī)分配的一個(gè)唯一地址。IPv4長(zhǎng)度為32比特，IPv6擴(kuò)展到128位。路

36、由器通常有多個(gè)IP地址。用于把分組送到目的IP網(wǎng)絡(luò)。223.1.1.1223.1.1.2223.1.1.3223.1.1.4223.1.2.9223.1.2.2223.1.2.1223.1.3.2223.1.3.1223.1.3.2776 IP地址格式及分類 網(wǎng)絡(luò)號(hào)：指明主機(jī)所在物理網(wǎng)絡(luò)的編號(hào)。 主機(jī)號(hào)：主機(jī)在物理網(wǎng)絡(luò)中的編號(hào)。大型網(wǎng)絡(luò)中型網(wǎng)絡(luò)小型網(wǎng)絡(luò)77IP地址表示方法 點(diǎn)分十進(jìn)制表示：將4個(gè)字節(jié)中的每一個(gè)字節(jié)分別用十進(jìn)制數(shù)來(lái)表示，十進(jìn)制數(shù)之間用 “.” 分隔例： 點(diǎn)分十進(jìn)制 二進(jìn)制 129 81625 10000001 00001000 00010000 00011001 10 . 2.

37、0. 52 00001010 00000010 00000000 00110100 126. 0. 0. 0 01111110 00000000 00000000 00000000 192.255. 255. 255 11000000 11111111 11111111 11111111 784.5 選路算法 分組通過(guò)路由器轉(zhuǎn)發(fā)，每個(gè)路由器都有一張轉(zhuǎn)發(fā)表，選路算法決定轉(zhuǎn)發(fā)表內(nèi)容。選路：確定分組從發(fā)送方傳送到接收方所要通過(guò)的路徑（路由）。數(shù)據(jù)報(bào)服務(wù)：在給定源和目的地之間傳輸不同分組可能采用不同的路由。虛電路服務(wù)：在給定源和目的地之間的所有分組采用同一路徑。79概念默認(rèn)路由器 ：與主機(jī)直接相連的一

38、臺(tái)路由器，又叫第一跳路由器 主機(jī)發(fā)送一個(gè)分組時(shí)，都先傳送給它的默認(rèn)路由器。源路由器：源主機(jī)的默認(rèn)路由器目的路由器：目的主機(jī)默認(rèn)路由器 networkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysical網(wǎng)絡(luò)層數(shù)據(jù)鏈路層物理層applicationtransportnetworkdata linkphysicalapplicatio

39、ntransportnetworkdata linkphysicalH2R1R2默認(rèn)路由器從源主機(jī)到目的主機(jī)的選路：從源路由器到目的路由器的選路。80選路算法 確定一個(gè)分組從源路由器到目的路由器所經(jīng)路徑的算法。 即在給定的一組路由器以及連接路由器的鏈路中，找到一條從源路由器到目的路由器的“好”路徑?！昂谩甭窂剑壕哂小白畹唾M(fèi)用”的路徑。 由許多因素決定，如鏈路長(zhǎng)度、傳播時(shí)延、價(jià)格等。81網(wǎng)絡(luò)的抽象圖模型用“節(jié)點(diǎn)圖”表示網(wǎng)絡(luò)的結(jié)構(gòu)。圖G = (N，E)：表示N個(gè)節(jié)點(diǎn)和E條邊的集合，每條邊是來(lái)自N的一對(duì)節(jié)點(diǎn)。節(jié)點(diǎn)：表示路由器(做出分組轉(zhuǎn)發(fā)判決的點(diǎn))。 如u，v，w，x，y，z。 邊：連接節(jié)點(diǎn)的線段，

40、表示路由器之間的物理鏈路。 如(u，v)、 (u，x) 、(u，w)、uyxwvz221311253582邊的值（費(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直接相連（x與y是鄰居） 則c(x，y )= 鏈路費(fèi)用 如c(u，v) = 2，節(jié)點(diǎn)u與節(jié)點(diǎn)v互為鄰居 若節(jié)點(diǎn)x與節(jié)點(diǎn)y不直接相連（x與y不是鄰居） 則c(x，y) = 如c(u，y) = ，c(u，z) = c(x，y)= c(y，x) 如c(u，v) = c(v，u) =2uyxwvz2213112535選路算法：根據(jù)給定的網(wǎng)絡(luò)抽象圖，找

41、出從源節(jié)點(diǎn)到目的節(jié)點(diǎn)間的最低費(fèi)用路徑。83路徑 路徑表示：路徑所經(jīng)過(guò)的節(jié)點(diǎn)序列。 如路徑(x1,x2,xp)，相鄰節(jié)點(diǎn)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)用路徑 ：該路徑上鏈路費(fèi)用之和最小。 最短路徑：所有鏈路的費(fèi)用都相同的情況。即在源和目的地之間經(jīng)過(guò)鏈路最少的路徑。84例如圖，源節(jié)點(diǎn)u和目的節(jié)點(diǎn)w之間的最低費(fèi)用路徑： uyxwvz2213112535(u,x,y,w) ，費(fèi)用為3。85選路算法分類根據(jù)算法是全局性還是

42、分散性劃分根據(jù)算法是靜態(tài)還是動(dòng)態(tài)劃分根據(jù)對(duì)負(fù)載是否敏感劃分因特網(wǎng)常用的兩種選路算法： 動(dòng)態(tài)全局鏈路狀態(tài)算法 動(dòng)態(tài)分散式距離向量算法4.5.1 鏈路狀態(tài)選路算法4.5.2 距離向量選路DV算法4.5.3 層次選路86全局選路算法用完整的、全局性的網(wǎng)絡(luò)信息來(lái)計(jì)算最低費(fèi)用路徑 即以所有節(jié)點(diǎn)之間的連通性及所有鏈路的費(fèi)用已知為條件。 在開(kāi)始計(jì)算前，以某種方式獲得這些信息。 可在單個(gè)位置計(jì)算，也可在多個(gè)位置上復(fù)制。 擁有連通性和鏈路費(fèi)用的完整信息。鏈路狀態(tài)算法LS：必須知道網(wǎng)絡(luò)中每條鏈路的費(fèi)用87分散式選路算法以迭代的、分布式的方式計(jì)算最低費(fèi)用路徑。節(jié)點(diǎn)只有與其直接相連鏈路的費(fèi)用信息：不需擁有所有網(wǎng)絡(luò)鏈路

43、費(fèi)用的完整信息。 通過(guò)迭代計(jì)算過(guò)程并與相鄰節(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ì)向量。88靜態(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)、路由振蕩之類問(wèn)題的影響。89負(fù)載敏感和遲鈍算法負(fù)載敏感算法： 鏈路費(fèi)用會(huì)動(dòng)態(tài)地變化，反映出底層鏈路的當(dāng)前擁塞水平。如果當(dāng)前擁塞的一條鏈路被賦以高費(fèi)用，則選路算法應(yīng)繞開(kāi)該擁塞鏈路來(lái)選擇路

44、由。如早期的ARPAnet選路算法。負(fù)載遲鈍算法： 某條鏈路的費(fèi)用一般不馬上反映其當(dāng)前的(或最近的)擁塞級(jí)別。 如因特網(wǎng)的選路算法。904.5.1 鏈路狀態(tài)選路算法前提條件：已知網(wǎng)絡(luò)拓?fù)浜退墟溌返馁M(fèi)用，作為算法的輸入。獲取方法：每個(gè)節(jié)點(diǎn)向網(wǎng)絡(luò)中廣播鏈路狀態(tài)分組（含有它所連接的鏈路的費(fèi)用）。 由鏈路狀態(tài)廣播算法實(shí)現(xiàn)。最終使所有節(jié)點(diǎn)都有一個(gè)相同且完整的網(wǎng)絡(luò)視圖。每個(gè)節(jié)點(diǎn)都可以運(yùn)行鏈路狀態(tài)算法并計(jì)算出最低費(fèi)用路徑集。91Dijkstra最低費(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)用路徑?；舅枷耄?以源

45、節(jié)點(diǎn)為起點(diǎn)，每次找出一個(gè)到源節(jié)點(diǎn)的費(fèi)用最低的節(jié)點(diǎn)，直到把所有的目的節(jié)點(diǎn)都找到為止。 92符號(hào)定義c(x,y): 從節(jié)點(diǎn)x到y(tǒng)的鏈路費(fèi)用; = 如果不是直接鄰居D(v) ：從源節(jié)點(diǎn)到目的節(jié)點(diǎn)v的當(dāng)前費(fèi)用 ；p(v)： 從源節(jié)點(diǎn)到節(jié)點(diǎn)v的路徑上的前一節(jié)點(diǎn)(節(jié)點(diǎn)v的鄰居)；N： 節(jié)點(diǎn)子集，從源節(jié)點(diǎn)到這些節(jié)點(diǎn)的最低費(fèi)用路徑已被求出。u 源mnef如： c(m,n)=1 c(m,e)= D(n) =2 p(n)=m 1193 Dijkstra算法組成由一個(gè)初始化步驟和其后的循環(huán)組成。循環(huán)執(zhí)行的次數(shù)與網(wǎng)絡(luò)中的節(jié)點(diǎn)個(gè)數(shù)（除源節(jié)點(diǎn)）相同。結(jié)束時(shí)，算出從源節(jié)點(diǎn)到網(wǎng)絡(luò)中所有其他節(jié)點(diǎn)的最短路徑。演示94算法1 初始

46、化: 2 N = u 3 對(duì)所有節(jié)點(diǎn)v 4 if v 臨近 u 5 then D(v) = c(u,v) 6 else D(v) = 78 Loop 9 找出不在N中而D(w)最小的節(jié)點(diǎn)w10 將w加入N 11 對(duì)于所有v臨近w并不在N中，更新D(v): 12 D(v) = min( D(v), D(w) + c(w,v) ) 13 /* 到v的新費(fèi)用或是到v的老費(fèi)用或到w加上從w到v的已知最短路費(fèi)用*/ 15 until 所有節(jié)點(diǎn)在 N 中 95算法描述（1）初始化（1#6#） N =源節(jié)點(diǎn)u； 對(duì)所有不在N 中的節(jié)點(diǎn)v，標(biāo)出其D(v)值：節(jié)點(diǎn)v與源節(jié)點(diǎn)u直接相連，D(v) = c(u，v)

47、 節(jié)點(diǎn)v與源節(jié)點(diǎn)u不直接相連 ，D(v) = 1 初始化: 2 N = u 3 對(duì)所有節(jié)點(diǎn)v 4 if v 臨近 u 5 then D(v) = c(u,v) 6 else D(v) = aefcbd2213112535N =a D(b)=2 D(c)=5 D(f)=1D(e)= D(d)= 96（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，用新的值更新 D(v)=minD(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)的值比

48、較，取小值。（3）重復(fù)步驟(2) 直到所有的網(wǎng)絡(luò)節(jié)點(diǎn)都在N 中為止。8 Loop 9 找出w不在N中使得D(w)最小 10 將w加入N 11 對(duì)于所有v臨近w并不在N中，更新D(v): 12 D(v) = min( D(v), D(w) + c(w,v) ) 13 /* 到v的新費(fèi)用或是到v的老費(fèi)用或到w加上從w到v的已知最短路費(fèi)用*/ 15 until 所有節(jié)點(diǎn)在 N中 aefcbd2213112535N =a D(b)=2 D(c)=5 D(f)=1D(e)= D(d)= N =af D(b)=2 D(c)=4 D(e)=2 D(d)= 97例計(jì)算從u到所有可能目的節(jié)點(diǎn)的最低費(fèi)用路徑計(jì)算過(guò)

49、程如表4-3，表中的每一行表示一次迭代結(jié)束時(shí)的算法變量值。uyxwvz221311253598步驟0NuD(v),p(v)2,uD(w),p(w)5,uD(x),p(x)1,uD(y),p(y)D(z),p(z) 4,yuyxwvz2213112535D(w)：min(5，1+3)=4 D(y)：min(，1+1)=2 2,u 4,x 2,x 2,u 3,y 4,y3,y 4,y1 ux2 uxy 3 uxyv 4 uxyvw 5 uxyvwz依次查找每個(gè)節(jié)點(diǎn)的前一節(jié)點(diǎn)， 直到源節(jié)點(diǎn)。 如節(jié)點(diǎn)z： zyxu 如節(jié)點(diǎn)w：wyxu得出從源節(jié)點(diǎn)u到節(jié)點(diǎn)z的最低費(fèi)用路徑為：uxyz，uxyw，費(fèi)用為4

50、 , 3991002,u 4,x 2,x 1w1yu2v2z1xuyxwvz2213112535根據(jù)目的節(jié)點(diǎn)的找出順序、費(fèi)用、前一節(jié)點(diǎn)，畫(huà)出源節(jié)點(diǎn)u到所有目的節(jié)點(diǎn)的最低費(fèi)用路徑樹(shù)。步驟0NuD(v),p(v)2,uD(w),p(w)5,uD(x),p(x)1,uD(y),p(y)D(z),p(z) 4,y2,u 3,y 4,y3,y 4,y1 ux2 uxy3 uxyv 4 uxyvw 5 uxyvwz最低費(fèi)用路徑樹(shù)5個(gè)箭頭顯示連接關(guān)系注：此處是起始節(jié)點(diǎn)u的最低費(fèi)用路徑樹(shù)，即保證從u出發(fā)到其他點(diǎn)費(fèi)用最低； 不能保證除節(jié)點(diǎn)u外的其他任意兩個(gè)節(jié)點(diǎn)經(jīng)此路徑樹(shù)費(fèi)用最低。101u1w1y2v2z1x轉(zhuǎn)發(fā)

51、表：存放從源節(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)。生成方法：根據(jù)得到的所有目的節(jié)點(diǎn)的完整路徑，或最低費(fèi)用路徑樹(shù)，生成源節(jié)點(diǎn)的轉(zhuǎn)發(fā)表。轉(zhuǎn)發(fā)表目的點(diǎn) 下一跳 u v v w x x x y x z x節(jié)點(diǎn)u的轉(zhuǎn)發(fā)表：將網(wǎng)絡(luò)中每一個(gè)節(jié)點(diǎn)作為源點(diǎn)，分別用Dijkstra方法計(jì)算，可以得到每一個(gè)節(jié)點(diǎn)的轉(zhuǎn)發(fā)表。102表示所有具有相同“下一跳”的表項(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)路由。默認(rèn)路由 u1w1y2v2z1x目的點(diǎn) 下一跳 u v v w x x

52、x y x z x節(jié)點(diǎn)u的轉(zhuǎn)發(fā)表：目的點(diǎn) 下一跳 u v v * x 103算法的計(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)；第二次迭代：檢查n-1個(gè)節(jié)點(diǎn)；第三次：檢查n-2個(gè)節(jié)點(diǎn)； 依次類推。所有迭代中需要搜尋的節(jié)點(diǎn)總數(shù)為n(n+1)/2。算法復(fù)雜性為n平方階序O(n2)。104LS算法的缺陷可能產(chǎn)生“振蕩”。例圖4-26,一個(gè)簡(jiǎn)單網(wǎng)絡(luò)拓?fù)?。設(shè)：鏈路費(fèi)用等于鏈路上的負(fù)載；鏈路費(fèi)用是非對(duì)稱的： c(u，v)與c(v，u)僅當(dāng)在鏈路(u，v)兩個(gè)方向的負(fù)載相同時(shí)才相等。有三個(gè)同時(shí)發(fā)往w的

53、注入流量：節(jié)點(diǎn)z：1個(gè)單元；節(jié)點(diǎn)x：1個(gè)單元；節(jié)點(diǎn)y：e的流量。wzyxe11105初始： 圖(a)，其鏈路費(fèi)用相當(dāng)于承載的流量第一次： 根據(jù)LS算法計(jì)算后，節(jié)點(diǎn)x、y都確定順時(shí)針?lè)较虻絯的路徑費(fèi)用最低，為1。產(chǎn)生圖(b)費(fèi)用。第二次： 根據(jù)LS算法計(jì)算后，節(jié)點(diǎn)x、y、z都確定逆時(shí)針?lè)较虻絯的路徑費(fèi)用最低，為0。產(chǎn)生圖(c)費(fèi)用。第三次： 根據(jù)LS算法計(jì)算后，節(jié)點(diǎn)x、y、z都確定順時(shí)針?lè)较虻絯的路徑費(fèi)用最低，為0。產(chǎn)生圖(d)費(fèi)用。wzyx11+ee0e1100(a)wzyx2+e0001+e1e11(b)(c)ewzyx02+e1+e10011(d)wzyx2+e0001+e111e106避

54、免振蕩使鏈路費(fèi)用不依賴于所承載的流量：不可行；避免所有的路由器同時(shí)運(yùn)行LS算法：比較合理。 既使路由器以相同周期運(yùn)行LS算法，但在每個(gè)節(jié)點(diǎn)上算法的執(zhí)行時(shí)刻不同。因特網(wǎng)的自同步問(wèn)題： 既使路由器初始時(shí)以同一周期但不同時(shí)刻執(zhí)行算法，但最終會(huì)變?yōu)橥讲⒈３帧?1074.5.2 距離向量選路DV算法 是一種迭代的、異步的和分布式的算法。分布式：每個(gè)節(jié)點(diǎn)都從其直接相連鄰居接收信息，進(jìn)行計(jì)算，再將計(jì)算結(jié)果分發(fā)給鄰居。迭代：計(jì)算過(guò)程一直持續(xù)到鄰居之間無(wú)更多信息交換為止。自我終結(jié)：算法能自行停止。異步：不要求所有節(jié)點(diǎn)相互之間步伐一致地操作。108最低費(fèi)用表示dx(y)：節(jié)點(diǎn)x到節(jié)點(diǎn)y的最低費(fèi)用路徑的費(fèi)用。 用

55、Bellman-Ford方程表示 dx(y) = minvc(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)用dv(y) 。即x經(jīng)v到節(jié)點(diǎn)y的最小的路徑費(fèi)用。 minv ：從所有經(jīng)直接與x相連鄰居到節(jié)點(diǎn)y的費(fèi)用中選取的最小路徑費(fèi)用。109dx(y)示例如：要求源節(jié)點(diǎn)u到目的節(jié)點(diǎn)z的最低費(fèi)用路徑du(z) 。源節(jié)點(diǎn)u有三個(gè)鄰居：鄰居v：dv(z) = 5 、c(u,v) = 2鄰居w：dw(z) = 3 、c(u,w) = 5鄰居x：dx(z) = 3 、c(u,x) = 1 du(z) = min c(u,v)

56、 + dv(z), c(u,w) + dw(z) , c(u,x) + dx(z) = min2+5， 5+3，1+3 = 4 uyxwvz2213112535得到節(jié)點(diǎn)u的轉(zhuǎn)發(fā)表中到目的節(jié)點(diǎn)z的下一跳是節(jié)點(diǎn)x。節(jié)點(diǎn)u經(jīng)鄰節(jié)點(diǎn)x到目的節(jié)點(diǎn)z的路徑費(fèi)用最低，為4。110DV算法基本思想基本思想： 每個(gè)節(jié)點(diǎn)有一張選路表（距離表），維持選路數(shù)據(jù)，隨著算法進(jìn)行，不斷更新，直到靜止。演示節(jié)點(diǎn)x選路表更新選路表的距離向量當(dāng)距離向量不再變化，算法靜止設(shè):Dx(y)：節(jié)點(diǎn)x到節(jié)點(diǎn)集N中某個(gè)節(jié)點(diǎn)y的估計(jì)費(fèi)用Dx：節(jié)點(diǎn)x的距離向量。Dx = Dx(y)：y在N中，即節(jié)點(diǎn)x到N中所有其他節(jié)點(diǎn)y的估計(jì)費(fèi)用。 111節(jié)點(diǎn)

57、x選路表節(jié)點(diǎn)x選路表（距離表）:列：所有目的節(jié)點(diǎn)。行：該節(jié)點(diǎn)的距離向量Dx和其鄰居的距離向量Dv節(jié)點(diǎn)x的距離向量Dx ，即節(jié)點(diǎn)x到每個(gè)目的節(jié)點(diǎn)y的估計(jì)費(fèi)用； Dx = Dx(y)：y在N中節(jié)點(diǎn)x每個(gè)鄰居的距離向量Dv ，即x的鄰居v到每個(gè)目的節(jié)點(diǎn)y的估計(jì)費(fèi)用，Dv = Dv(y)：y在N中xz127yx y zxyz0 2 7 DxDyDzDx(x) Dx(y) Dx(z) x y zxyzDy(x) Dy(y) Dy(z) Dz(x) Dz(y) Dz(z) 鄰居初始化112更新表中距離向量每個(gè)節(jié)點(diǎn)不斷向鄰居發(fā)送其距離向量拷貝；當(dāng)節(jié)點(diǎn)x收到一個(gè)鄰居v的新距離向量，先保存，并用公式（4-1）更

58、新自己的距離向量： Dx(y) = minvc(x,v)+ Dv(y) 從所有經(jīng)鄰居v到節(jié)點(diǎn)y的費(fèi)用中選取最小路徑費(fèi)用。若距離向量發(fā)生改變，將新的距離向量通知給鄰居。113當(dāng)距離向量不再變化，算法靜止 此時(shí)Dx(y)收斂到dx(y)，即得到節(jié)點(diǎn)x到節(jié)點(diǎn)y的最低費(fèi)用路徑。114距離向量選路DV算法1、距離向量DV算法描述2、鏈路費(fèi)用改變與鏈路故障3、增加“毒性逆轉(zhuǎn) 4、LS算法與DV算法比較5、其他選路算法1151、距離向量DV算法描述對(duì)每個(gè)節(jié)點(diǎn)x（1）初始化：（2）更新自己的距離向量 （3）重復(fù)執(zhí)行（2），直到?jīng)]有更新的距離向量發(fā)出。等待 (收到本地鏈路費(fèi)用變化或鄰居來(lái)距離矢量更新)重新計(jì)算距

59、離矢量如果到任何目的節(jié)點(diǎn)的距離矢量發(fā)生變化, 通知鄰居 初始化116距離矢量算法1 Initialization: 2 for all destinations y in N: 3 Dx (y) = c( x, y ) /* if y is not a neighbor then c( x, y )= */ 4 for each neighbor w5 Dw (y) = for all destinations y in N6 for each neighbor w7 send DV Dx = Dx (y) :y in N to w 在所有的節(jié)點(diǎn), X:9 loop 10 wait (unti

60、l I see a link cost change to neighbor w or 11 until I receive update from neighbor w) 13 for each y in N: Dx(y) = minvc(x,v)+ Dv(y) 16 if Dx(y) changed for any destination y 17 Send DV Dx = Dx (y) : y in N to all neighbors 19 forever 初始化117（1）初始化計(jì)算節(jié)點(diǎn)x到所有目的點(diǎn)y的距離向量Dx(y) 若目的點(diǎn)y是節(jié)點(diǎn)x的鄰居，則Dx(y) = c(x,y )