計算機網(wǎng)絡(luò)第四章

4.3.1輸入端口線路端接和鏈路層處理實現(xiàn)了用于各個輸入鏈路的物理層和鏈路層。查找，轉(zhuǎn)發(fā)，排隊----在這個地方，路由器用轉(zhuǎn)發(fā)表查找輸出端口，使分組能經(jīng)過交換結(jié)構(gòu)轉(zhuǎn)發(fā)到輸出端口。----轉(zhuǎn)發(fā)表的一個影子副本會存放在每個輸入端口，使轉(zhuǎn)發(fā)決策能在輸入端口做出，避免了集中式處理的瓶頸。線路端接數(shù)據(jù)鏈路處理（協(xié)議、拆封）查找、轉(zhuǎn)發(fā)、排隊交換結(jié)構(gòu)輸入端口處理輸入鏈路查找：概念上講查找是簡單的，即我們只是搜索轉(zhuǎn)發(fā)表查找最長前綴匹配。但在吉比特速率下，這種查找必須在納秒級執(zhí)行。我們不僅要用硬件執(zhí)行查找，還要對大型轉(zhuǎn)發(fā)表使用超出簡單線性搜索的技術(shù)。三態(tài)內(nèi)容可尋址存儲器（TCAM）經(jīng)常被用于查找。通過查找確定輸出端口后，分組就能發(fā)送進入交換結(jié)構(gòu)。但若此交換結(jié)構(gòu)正被其他輸入端口的分組占用，則此分組會被阻塞，以致必須在輸入端口處排隊，等待稍后被及時調(diào)度以通過交換結(jié)構(gòu)。除查找外，輸入端口處理還需采取其他動作：1、必須出現(xiàn)物理層和鏈路層處理2、必須檢查分組的版本號、檢驗和以及壽命字段，并重寫后兩個字段3、必須更新用于網(wǎng)絡(luò)管理的計數(shù)器4.3.2交換結(jié)構(gòu)位于路由器的核心，實現(xiàn)了分組從一個輸入端口交換到一個輸出端口。內(nèi)存內(nèi)存總線縱橫式經(jīng)內(nèi)存交換：早期用計算機作為路由器輸入端口與輸出端口之間的交換由CPU(選路處理器)控制完成；輸入端口與輸出端口類似I/O設(shè)備：

當分組到達輸入端口時，通過中斷向選路處理器發(fā)出信號，將分組拷貝到處理器內(nèi)存中；

選路處理器根據(jù)分組首部中的目的地址查表找出適當?shù)妮敵龆丝?，將該分組拷貝到輸出端口的緩存中。此情況下，若內(nèi)存帶寬為每秒寫入或讀出B個分組，則總的轉(zhuǎn)發(fā)吞吐量(分組從輸入端口被傳送到輸出端口的總速率)必然小于B/2。且注意不能同時轉(zhuǎn)發(fā)兩個分組，即使有不同的端口號，因為經(jīng)過共享系統(tǒng)總線一次僅能執(zhí)行一個內(nèi)存讀/寫。

現(xiàn)代路由器與早期路由器的主要差別是：輸入線路上的處理器來執(zhí)行目的地址的查找，并將分組存儲(交換)進適當?shù)拇鎯ξ恢谩?/p>

在某些方面，類似共享內(nèi)存的多處理機，用一個線路卡上的處理器將分組存儲進適當輸出端口的內(nèi)存中。如，Cisco的Catalyst8500系列的交換機。經(jīng)總線交換：輸入端口通過一條共享總線將分組直接傳送到輸出端口，不需要選路處理器的干預(yù)。總線

輸入端口為分組預(yù)先計劃一個內(nèi)部標簽指示本地輸出端口，通過總線傳送到輸出端口，只有與該標簽匹配的輸出端口才能保存該分組。每次只能有一個分組通過總線傳送。分組到達一個輸入端口時，若總線正忙，會被暫時阻塞，在輸入端口排隊因為每個分組必須跨過單一總線，故路由器交換帶寬受總線速率限制。經(jīng)互聯(lián)網(wǎng)絡(luò)交換：縱橫式交換機：由2n條總線組成，n個輸入端口與n個輸出端口連接。每條垂直的總線在交叉點與每條水平的總線交叉，交叉點通過交換結(jié)構(gòu)控制器能在任何時候開啟和閉合。當某分組到達A，需轉(zhuǎn)發(fā)到端口Y，交換機控制器閉合總線A和Y的交叉點，然后A在其總線上發(fā)送分組，分組僅由總線Y安排接收。不同輸入輸出總線上傳輸?shù)姆纸M不會相互阻塞。但若兩個分組是兩個不同輸入端口，同一輸出端口，則一個分組必須在輸入端等待，因為給定總線在某個時刻僅有一個分組能被發(fā)送?？v橫式4.3.3輸出端口用于取出存放在輸出端口內(nèi)存中的分組，并將其發(fā)送到輸出鏈路上。

交換結(jié)構(gòu)排隊：緩存管理數(shù)據(jù)鏈路處理(協(xié)議、解封)線路端接輸出端口處理4.3.4何處出現(xiàn)排隊輸入端口和輸出端口都會形成分組隊列。排隊的位置和程度，取決于流量負載、交換結(jié)構(gòu)的相對速率、線路速率等因素。當隊列逐步增長，路由器緩存空間終將耗盡，并當無內(nèi)存可用于存儲到達的分組是會出現(xiàn)丟包。假定：輸入線路速率與輸出線路速率相同，均為每秒Rline個分組，有n個輸入端口和n個輸出端口。定義交換結(jié)構(gòu)速率Rswitch為:將分組從輸入端口移動到輸出端口的速率。輸出端口排隊設(shè)交換結(jié)構(gòu)的速率至少是線路速率的n倍。最壞情況：到達每個輸入端口的分組都被發(fā)往同一個輸出端口。因為輸出端口在一個單位時間（分組傳送時間）內(nèi)只能發(fā)送一個分組，有n個到達的分組必須排隊(等待)發(fā)送到輸出鏈路上；在發(fā)出隊列中一個分組的時間內(nèi)，又有n個分組到達。依此類推，最終排隊的分組快速增長，很快占滿輸出端口的存儲空間，使后續(xù)分組被丟棄。例假定：線路速度相同，交換以三倍快的線路速度進行操作。交換結(jié)構(gòu)交換結(jié)構(gòu)在時間t輸出端口競爭一個分組時間以后

在t時刻每個輸入端口都到達一個分組，都發(fā)往最上側(cè)的輸出端口。一個時間單位后（接收或發(fā)送一個分組的時間）：三個原始分組都被傳送到輸出端口，并排隊等待發(fā)送。又有兩個新分組到達交換結(jié)構(gòu)的輸入端，其中的一個分組要發(fā)往最上側(cè)的輸出端口。下一個單位時間：三個分組中的一個通過輸出鏈路發(fā)送出去。輸出端口排隊的后果：

在輸出端口上的一個分組調(diào)度程序必須在排隊的分組中選一個來發(fā)送。

原則有：先來先服務(wù)FCFS：簡單。加權(quán)公平排隊WFQ：在具有排隊分組的不同端到端連接之間公平地共享輸出鏈路。當沒有足夠內(nèi)存來緩存一個入分組，則要么丟棄到達的分組（棄尾策略），要么刪除一個或多個已排隊的分組來為新的分組騰出空間。已經(jīng)提出和分析了許多分組丟棄與標記策略，統(tǒng)稱為主動隊列管理算法（AQM）。隨機早期檢測（RED）算法是一種得到廣泛實現(xiàn)的AQM算法，此算法為輸出隊列長度維護著一個加權(quán)平均值。隨機早期檢測（RED）設(shè)最小閾值minth和最大閾值maxth平均隊列長度小于最小閾值minth，到達分組會被納入隊列；隊列滿或平均隊列長度大于最大閾值maxth

，到達分組則被標記或丟棄；平均隊列長度在[minth，maxth]之間，到達分組則以某種概率被標記或丟棄。輸入端口排隊交換結(jié)構(gòu)比輸入端口總和的速度慢輸入隊列產(chǎn)生排隊

交換結(jié)構(gòu)不夠快，即相對于輸入線路速度而言不能快得使所有到達的分組無延遲地通過它傳送，則在輸入端口出現(xiàn)分組排隊，以等待通過交換結(jié)構(gòu)傳送到輸出端口。為說明這種排隊的重要后果：考慮縱橫式交換結(jié)構(gòu)

假定：1.所有鏈路速度相同；2.一個分組能夠以一條輸入鏈路接收一個分組所用的相同的時間量，從任意一個輸入端口傳送到給定的輸出端口。3.分組按FCFS方式從一指定輸入隊列移動到其要求的輸出隊列中。結(jié)果：1.分組輸出端口不同：多個分組可以被并行傳送。2.發(fā)往相同輸出端口：位于兩個輸入隊列前端的兩個分組是發(fā)往同一輸出隊列的，則其中的一個分組被阻塞，在輸入隊列中等待，因為交換結(jié)構(gòu)一次只能傳一個分組到端口。舉例：不同輸入隊列前端的兩個分組要發(fā)往右上角的同一輸出端口。若先發(fā)送左上角隊列前端的分組，左下角隊列中的分組要等待，左下角隊列中排在該分組后面的分組也要等待，即使右中側(cè)輸出端口中無競爭。這種現(xiàn)象叫做輸入排隊交換機中的線路前部（HOLhead-of-the-line)阻塞：即在一個輸入隊列中排隊的分組必須等待通過交換結(jié)構(gòu)發(fā)送（即使輸出端口使空閑的），因為它被位于線路前部的另一個分組所阻塞。時間t：輸出端口競爭，僅一個紅色分組能被傳輸時間t＋1：綠色分組經(jīng)歷了HOL阻塞交換結(jié)構(gòu)交換結(jié)構(gòu)4.3.5路由選擇控制平面