二章網(wǎng)絡(luò)實(shí)現(xiàn)模型

1、二章網(wǎng)絡(luò)實(shí)現(xiàn)模型二章網(wǎng)絡(luò)實(shí)現(xiàn)模型模型的重要性網(wǎng)絡(luò)算法學(xué)包含以下幾個(gè)不同的領(lǐng)域：協(xié)議，硬件，體系結(jié)構(gòu)，操作系統(tǒng)，算法。不同領(lǐng)域的專家通過簡單的模型進(jìn)行對(duì)話：模型描述了問題的要點(diǎn)，又不涉及不必要的細(xì)節(jié)最低程度：模型應(yīng)能定義所需要的術(shù)語最好情況：領(lǐng)域外的專家可以根據(jù)模型進(jìn)行設(shè)計(jì)，并可由領(lǐng)域內(nèi)的專家對(duì)設(shè)計(jì)進(jìn)行驗(yàn)證模型的重要性網(wǎng)絡(luò)算法學(xué)包含以下幾個(gè)不同的領(lǐng)域：2.1 協(xié)議抽象模型協(xié)議定義了通信實(shí)體之間交換的報(bào)文的格式和次序，以及在報(bào)文發(fā)送、接收或收到其它事件后采取的動(dòng)作。協(xié)議是一個(gè)加上了接口和報(bào)文格式的狀態(tài)機(jī)。協(xié)議規(guī)范描述狀態(tài)機(jī)如何改變狀態(tài)，以及如何響應(yīng)接口調(diào)用、消息到達(dá)和定時(shí)器事件。2.1 協(xié)議抽象模

2、型協(xié)議定義了通信實(shí)體之間交換的報(bào)文的格式和常見而耗時(shí)的功能與數(shù)據(jù)包收發(fā)有關(guān)的功能：交換，數(shù)據(jù)拷貝，檢查和計(jì)算，內(nèi)存分配等。與協(xié)議處理有關(guān)的功能：重組數(shù)據(jù)包查找及修改狀態(tài)設(shè)置定時(shí)器調(diào)度任務(wù)數(shù)據(jù)包交付給應(yīng)用：解復(fù)用控制切換常見而耗時(shí)的功能與數(shù)據(jù)包收發(fā)有關(guān)的功能：重要的性能指標(biāo)網(wǎng)絡(luò)中兩個(gè)最重要的性能指標(biāo)：吞吐量：每秒處理的包數(shù)（pps）或比特?cái)?shù)（bps）。延遲：處理一個(gè)數(shù)據(jù)包的時(shí)間（典型地為最壞情況）。性能測量分為：全局性能測量：如端到端延遲和帶寬，使用網(wǎng)絡(luò)管理工具（如OpenView）進(jìn)行測量。本地性能測量：如路由器查找速度，使用計(jì)算機(jī)內(nèi)部的性能測量工具（如Oprofile, Vtune）測量。本

3、課程關(guān)注本地性能。重要的性能指標(biāo)網(wǎng)絡(luò)中兩個(gè)最重要的性能指標(biāo)：因特網(wǎng)環(huán)境的特點(diǎn)鏈路速度：骨干鏈路達(dá)到10Gbps和40Gbps，本地鏈路達(dá)到1Gbps無線鏈路和家庭網(wǎng)鏈路的速度要低幾個(gè)量級(jí)TCP流量占主導(dǎo)小包：路由器收到的包中大約一半為最小長度（40字節(jié)）的包延遲很長：實(shí)際來回延遲遠(yuǎn)遠(yuǎn)超過光的傳輸延遲局部性很差：在一個(gè)包上執(zhí)行的計(jì)算在未來短時(shí)間內(nèi)重用到另一個(gè)包上的可能性很小因特網(wǎng)環(huán)境的特點(diǎn)鏈路速度：網(wǎng)絡(luò)系統(tǒng)面臨的挑戰(zhàn)高速鏈路 + 大量小包：包速率很高網(wǎng)絡(luò)系統(tǒng)線速處理難度大高速鏈路 + 大規(guī)模并發(fā)流：數(shù)據(jù)局部性差Cache用不上（命中率低）TCP流占主導(dǎo) + TCP處理開銷大：TCP優(yōu)化很重要網(wǎng)絡(luò)

4、系統(tǒng)面臨的挑戰(zhàn)高速鏈路 + 大量小包：2.2 存儲(chǔ)器寄存器：由一組有序的觸發(fā)器構(gòu)成，訪問同一個(gè)片上寄存器的耗時(shí)大約為0.5-1 ns。SRAM：由一組寄存器構(gòu)成。一般情況下，片上SRAM的訪問時(shí)間為1-2ns，片外SRAM的訪問時(shí)間為5-10ns。DRAM：片上DRAM的訪存延遲大約為30ns，最快的片外DRAM訪存延遲為40-60ns，連續(xù)讀的延遲約為100ns。2022/9/232.2 存儲(chǔ)器寄存器：2022/9/21mode DRAM（快頁內(nèi)存）：支持以4字節(jié)突發(fā)模式傳送數(shù)據(jù)，有利于局部性好的數(shù)據(jù)的快速訪問。Interleaved DRAM（交織內(nèi)存）：幾個(gè)DRAM bank集成到一個(gè)內(nèi)

5、存芯片中，復(fù)用數(shù)據(jù)線和地址線SDRAM（2個(gè)bank），RDRAM（16個(gè)bank）2022/9/23mode DRAM（快頁內(nèi)存）：2022/9/2舉例：流水化的流ID查找應(yīng)用需求：路由器統(tǒng)計(jì)每個(gè)流發(fā)送的包數(shù)每個(gè)流用五元組（共96位）進(jìn)行描述線速處理要求：對(duì)于2.5Gbps鏈路和40字節(jié)最小數(shù)據(jù)包，流ID的查找時(shí)間不能超過128ns。（40*8/2.5Gb/s = 128ns）問題規(guī)模：核心路由器中大約有100萬條并發(fā)的流2022/9/23舉例：流水化的流ID查找應(yīng)用需求：2022/9/21設(shè)計(jì)方案考慮需要設(shè)計(jì)一個(gè)數(shù)據(jù)結(jié)構(gòu)：每個(gè)流維護(hù)一個(gè)計(jì)數(shù)器支持插入和查找兩種操作，查找為針對(duì)流ID的精確匹

6、配要求限制最壞情況下的查找時(shí)間 使用平衡二叉樹在SRAM中保存查找樹？維護(hù)100萬條流的狀態(tài)，需要約14MB空間，代價(jià)太高！在普通DRAM中保存查找樹？若實(shí)現(xiàn)分支因子為2的二叉樹，查找一個(gè)流需要20次訪存；按照訪存周期50ns計(jì)算，查找時(shí)間為1微秒！2022/9/23設(shè)計(jì)方案考慮需要設(shè)計(jì)一個(gè)數(shù)據(jù)結(jié)構(gòu)：2022/9/21使用RDRAM實(shí)現(xiàn)二分查找使用具有16個(gè)bank的RDRAM實(shí)現(xiàn)樹高為16的二叉樹，樹中第i層的所有節(jié)點(diǎn)存儲(chǔ)在bank i中。查找芯片同時(shí)對(duì)16個(gè)數(shù)據(jù)包（流ID）進(jìn)行查找，比如：用第1個(gè)包的流ID查找bank 1中的根節(jié)點(diǎn)，得到bank 2（第二層）中要查找的節(jié)點(diǎn)；用第1個(gè)包的流

7、ID查找bank 2時(shí)，用第2個(gè)包的流ID查找bank 1中的根節(jié)點(diǎn)；依次類推流水線充滿后，每60ns完成一個(gè)流ID的查找問題：層次為16的二叉樹只能有216=64K個(gè)流ID，不能滿足問題規(guī)模！ 2022/9/23使用RDRAM實(shí)現(xiàn)二分查找使用具有16個(gè)bank的RDRAM使用RDRAM實(shí)現(xiàn)M=3的B-樹RDRAM允許快頁模式，可一次讀8個(gè)32比特的字（256比特）256比特的字可以存放2個(gè)96比特的流ID，以及3個(gè)20比特的指針構(gòu)造一棵高度為16、M=3的B-樹，可以保存31643,000,000個(gè)流ID2022/9/23使用RDRAM實(shí)現(xiàn)M=3的B-樹RDRAM允許快頁模式，可一網(wǎng)絡(luò)存儲(chǔ)子

8、系統(tǒng)設(shè)計(jì)的主要技術(shù)內(nèi)存交錯(cuò)和流水線：類似的技術(shù)也可用于IP查找、包分類和包調(diào)度等多個(gè)bank可以用多個(gè)外部存儲(chǔ)來實(shí)現(xiàn)寬字并行：使用DRAM，并利用其快頁模式或者使用SRAM，并使得每個(gè)內(nèi)存字更寬組合DRAM和SRAM：SRAM快而貴，DRAM便宜卻慢，將這兩種技術(shù)組合起來可以得到一個(gè)最佳的平衡2022/9/23網(wǎng)絡(luò)存儲(chǔ)子系統(tǒng)設(shè)計(jì)的主要技術(shù)內(nèi)存交錯(cuò)和流水線：2022/9/2.3 端節(jié)點(diǎn)架構(gòu)端節(jié)點(diǎn)是通用計(jì)算機(jī)，由處理器、存儲(chǔ)器、總線和I/O設(shè)備組成處理器是一個(gè)狀態(tài)機(jī)，以一系列指令和數(shù)據(jù)作為輸入，寫輸出到I/O設(shè)備大部分的處理器狀態(tài)保存在外部DRAM（主存）中，主存通常用1GB或更大的交織內(nèi)存實(shí)現(xiàn)，

9、訪問時(shí)間長（如60ns）處理器使用cache來提高速度：Cache為容量相對(duì)較小的SRAM，保存最常使用的狀態(tài)某些SRAM（如L1、L2 cache）位于處理器芯片中更多的SRAM（如L3 cache）位于處理器芯片外2022/9/232.3 端節(jié)點(diǎn)架構(gòu)端節(jié)點(diǎn)是通用計(jì)算機(jī)，由處理器、存儲(chǔ)器、總線Cache的使用效果與時(shí)空局部性當(dāng)指令和數(shù)據(jù)呈現(xiàn)時(shí)間局部性和空間局部性時(shí)，cache的使用效果非常好：時(shí)間局部性：一個(gè)存儲(chǔ)位置在短時(shí)間內(nèi)被頻繁訪問。空間局部性：一個(gè)存儲(chǔ)位置被訪問后，其鄰近位置在短時(shí)間內(nèi)被訪問。X86處理器利用DRAM的訪存特點(diǎn)實(shí)現(xiàn)預(yù)?。好慨?dāng)讀取一個(gè)32比特字時(shí)，處理器預(yù)取連續(xù)的128比

10、特到cache中。高速數(shù)據(jù)包流基本不呈現(xiàn)時(shí)間局部性，因此，協(xié)議實(shí)現(xiàn)時(shí)注意提高算法及數(shù)據(jù)結(jié)構(gòu)的空間局部性非常重要2022/9/23Cache的使用效果與時(shí)空局部性當(dāng)指令和數(shù)據(jù)呈現(xiàn)時(shí)間局部性和提高算法及數(shù)據(jù)結(jié)構(gòu)的空間局部性設(shè)計(jì)緊湊的數(shù)據(jù)結(jié)構(gòu)，使其能夠常駐cache不被換出將隨機(jī)訪問（如鏈表）變?yōu)轫樞蛟L問（如數(shù)組）對(duì)相同位置的數(shù)據(jù)進(jìn)行的操作盡可能放在一起將經(jīng)常要被一起訪問的數(shù)據(jù)放在連續(xù)位置，且與cache行對(duì)齊提高算法及數(shù)據(jù)結(jié)構(gòu)的空間局部性設(shè)計(jì)緊湊的數(shù)據(jù)結(jié)構(gòu)，使其能夠常端節(jié)點(diǎn)的架構(gòu)模型網(wǎng)絡(luò)應(yīng)用的吞吐量受限于最慢的總線（通常是I/O總線）。協(xié)議處理通常涉及多次數(shù)據(jù)包拷貝，每個(gè)數(shù)據(jù)包都要穿過總線幾次。處

11、理器性能的提高消除了計(jì)算瓶頸，但無助于消除數(shù)據(jù)移動(dòng)瓶頸。結(jié)論：端節(jié)點(diǎn)的瓶頸不在計(jì)算，而在訪存和I/O。 2022/9/23端節(jié)點(diǎn)的架構(gòu)模型網(wǎng)絡(luò)應(yīng)用的吞吐量受限于最慢的總線（通常是I/2.4 路由器架構(gòu)模型路由器是具有一組輸入鏈路和一組輸出鏈路的設(shè)備，其任務(wù)是將數(shù)據(jù)包從輸入鏈路交換到輸出鏈路路由器的三個(gè)主要性能瓶頸：查找交換（數(shù)據(jù)包移動(dòng)）隊(duì)列調(diào)度2022/9/232.4 路由器架構(gòu)模型路由器是具有一組輸入鏈路和一組輸出鏈路查找IP地址查找（chapter 11）：FIB（Forwarding Information Base）是路由表的鏡像，但其數(shù)據(jù)結(jié)構(gòu)專門針對(duì)快速查找而設(shè)計(jì)早期的路由器由主CP

12、U完成地址查找，當(dāng)今最高端的路由器使用專用芯片完成查找，一些要求實(shí)現(xiàn)新功能（如web 負(fù)載均衡）的路由器使用網(wǎng)絡(luò)處理器進(jìn)行查找。數(shù)據(jù)包分類（chapter 12）：數(shù)據(jù)包分類是區(qū)別化服務(wù)的基礎(chǔ)，按照五元組將數(shù)據(jù)包劃分到不同的流中數(shù)據(jù)包分類是比IP地址查找困難得多的問題2022/9/23查找IP地址查找（chapter 11）：2022/9/21交換（switching）路由器內(nèi)部的交換機(jī)制將數(shù)據(jù)包從輸入鏈路 i 傳送到輸出鏈路 j。早期的路由器使用總線作為交換機(jī)制：假設(shè)存在N條輸入鏈路，每條鏈路的速率為B，則總線上的負(fù)載達(dá)到BN，成為系統(tǒng)瓶頸。今天的路由器采用并行交換機(jī)制，如crossbar交

13、換機(jī)：每條輸入和輸出鏈路使用各自的總線，通過交換機(jī)內(nèi)部的交叉開關(guān)實(shí)現(xiàn)連通。交換機(jī)調(diào)度是瓶頸，其問題規(guī)模也是BN。任何問題，如果其規(guī)模與N成正比，就有擴(kuò)放性問題。 2022/9/23交換（switching）路由器內(nèi)部的交換機(jī)制將數(shù)據(jù)包從輸入隊(duì)列調(diào)度當(dāng)數(shù)據(jù)包被交換到輸出鏈路后，需要排隊(duì)等候發(fā)送許多早期的路由器使用一個(gè)FIFO隊(duì)列更復(fù)雜的調(diào)度策略可實(shí)現(xiàn)帶寬公平分配或延遲保證：每條輸出鏈路設(shè)置多條隊(duì)列數(shù)據(jù)包按照一定的原則（優(yōu)先級(jí)、業(yè)務(wù)類型、流ID等）放入某個(gè)隊(duì)列隊(duì)列調(diào)度器每次從一個(gè)隊(duì)列中取出數(shù)據(jù)包發(fā)送隊(duì)列調(diào)度器是瓶頸（最壞情況下問題規(guī)模也是BN）2022/9/23隊(duì)列調(diào)度當(dāng)數(shù)據(jù)包被交換到輸出鏈路后，

14、需要排隊(duì)等候發(fā)送2022其它任務(wù)包頭檢查和修改：一般由硬件完成選路（RIP，OSPF，BGP）：由主處理器完成協(xié)議處理（TCP，UDP，ICMP）：由主處理器完成分片、重定向、ARP：在快路徑還是慢路徑上完成，有不同的做法快路徑：每個(gè)包都要執(zhí)行的處理，在接口卡上完成慢路徑：不是每個(gè)包都要執(zhí)行的處理，可以由主CPU完成基于內(nèi)容的交換：快速URL匹配流量測量：快速流ID匹配2022/9/23其它任務(wù)包頭檢查和修改：一般由硬件完成2022/9/212.5 操作系統(tǒng)操作系統(tǒng)是為解決在裸機(jī)上編程困難而設(shè)計(jì)的與裸機(jī)打交道的三個(gè)最主要難題是：處理中斷，管理內(nèi)存，控制I/O設(shè)備為處理這些困難，操作系統(tǒng)提供了不

15、間斷計(jì)算、無限存儲(chǔ)和簡單I/O的抽象抽象在提高程序員生產(chǎn)效率的同時(shí)，帶來了兩個(gè)代價(jià)：實(shí)現(xiàn)抽象的機(jī)制是有代價(jià)的抽象阻礙了程序員對(duì)資源的充分利用2022/9/232.5 操作系統(tǒng)操作系統(tǒng)是為解決在裸機(jī)上編程困難而設(shè)計(jì)的20（1） 依靠進(jìn)程實(shí)現(xiàn)不間斷計(jì)算的抽象操作系統(tǒng)通過進(jìn)程提供給程序員不間斷、順序計(jì)算的抽象進(jìn)程抽象通過三個(gè)機(jī)制實(shí)現(xiàn)：上下文切換，調(diào)度，保護(hù)進(jìn)程抽象帶來的開銷：上下文切換（狀態(tài)保存及恢復(fù)），調(diào)度器運(yùn)行2022/9/23（1） 依靠進(jìn)程實(shí)現(xiàn)不間斷計(jì)算的抽象操作系統(tǒng)通過進(jìn)程提供給程進(jìn)程的三種類型中斷處理程序：僅用于處理緊急請求的短小程序只使用少量的狀態(tài)（如幾個(gè)寄存器），開銷（上下文）最小線

16、程：輕量級(jí)的進(jìn)程，只需要較少的狀態(tài)（較小的上下文）同一個(gè)進(jìn)程中的線程切換比進(jìn)程切換開銷?。▋?nèi)存不需要重新映射）用戶進(jìn)程：使用計(jì)算機(jī)的全部狀態(tài)，比如內(nèi)存和寄存器（上下文最大）用戶進(jìn)程之間切換的代價(jià)很高（重新映射內(nèi)存）2022/9/23進(jìn)程的三種類型中斷處理程序：2022/9/21舉例：接收端活鎖（Receiver Livelock）計(jì)算機(jī)將所有的時(shí)間用來處理數(shù)據(jù)包中斷，卻因?yàn)闆]有時(shí)間運(yùn)行應(yīng)用程序，而最終將數(shù)據(jù)包丟棄。2022/9/23舉例：接收端活鎖（Receiver Livelock）計(jì)算機(jī)進(jìn)程啟動(dòng)時(shí)間在Pentiem IV計(jì)算機(jī)上，一個(gè)空的中斷調(diào)用，中斷延遲大約為2微秒。在一個(gè)具有兩個(gè)進(jìn)程的

17、Linux機(jī)器上，進(jìn)程上下文切換約用時(shí)10微秒；Windows和Solaris用時(shí)更多。在1Gbps以太網(wǎng)鏈路上，10微秒時(shí)間內(nèi)可能會(huì)有約20個(gè)最小長度的包到來。端節(jié)點(diǎn)上網(wǎng)絡(luò)程序的延遲和吞吐量和進(jìn)程啟動(dòng)時(shí)間有關(guān)。2022/9/23進(jìn)程啟動(dòng)時(shí)間在Pentiem IV計(jì)算機(jī)上，一個(gè)空的中斷調(diào)用（2）依靠虛擬內(nèi)存實(shí)現(xiàn)無限存儲(chǔ)的抽象在虛擬內(nèi)存系統(tǒng)中，程序員使用的內(nèi)存抽象是一個(gè)線性存儲(chǔ)空間，編譯器在該空間內(nèi)指定變量的地址?，F(xiàn)代計(jì)算機(jī)系統(tǒng)使用頁表映射和請求調(diào)頁兩個(gè)機(jī)制實(shí)現(xiàn)虛擬內(nèi)存抽象：一個(gè)虛擬頁為4KB，用虛擬地址的高20位構(gòu)成頁號(hào)，低12位構(gòu)成頁內(nèi)偏移量。物理內(nèi)存劃分為物理頁，每個(gè)物理頁的大小為4KB。

18、虛擬頁到物理頁的映射關(guān)系被保存到一個(gè)頁表中，以虛擬頁號(hào)作為索引。 （頁表映射）虛擬頁也可以不在內(nèi)存中，當(dāng)需要時(shí)從磁盤讀入到內(nèi)存的一個(gè)物理頁中。（請求調(diào)頁）2022/9/23（2）依靠虛擬內(nèi)存實(shí)現(xiàn)無限存儲(chǔ)的抽象在虛擬內(nèi)存系統(tǒng)中，程序員基于頁的內(nèi)存映射2022/9/23基于頁的內(nèi)存映射2022/9/21虛擬內(nèi)存抽象帶來的開銷到虛擬地址X的一個(gè)讀操作可能需要訪問主存兩次：第一次訪問頁表，將虛擬地址X轉(zhuǎn)換成物理地址P第二次訪問物理地址P現(xiàn)代處理器將最近使用過的地址映射緩存在TLB中，實(shí)際的地址轉(zhuǎn)換由MMU硬件完成。極其影響內(nèi)存訪問速度的兩個(gè)因素：TLB miss調(diào)頁2022/9/23虛擬內(nèi)存抽象帶來的開銷到虛擬地址X的一個(gè)讀操作可能需要訪問主（3）通過系統(tǒng)調(diào)用實(shí)現(xiàn)簡單I/O的抽象操作系統(tǒng)提供給程序員的設(shè)備抽象是可以進(jìn)行讀寫的一塊內(nèi)存2022/9/23（3）通過系統(tǒng)調(diào)用實(shí)現(xiàn)簡單I/O的抽象操作系統(tǒng)提供給程