網(wǎng)絡(luò)層知識點

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

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