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

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

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

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

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

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

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

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

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

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

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

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

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

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