第二部分第二代網(wǎng)絡(luò)系統(tǒng)

1、第二部分 第二代網(wǎng)絡(luò)系統(tǒng)主要內(nèi)容p用于協(xié)議處理的硬件體系結(jié)構(gòu)p分類和轉(zhuǎn)發(fā)p交換結(jié)構(gòu)1. 傳統(tǒng)的軟件路由器p第一個網(wǎng)絡(luò)設(shè)備是分組交換機(jī)，使用的是小型機(jī)。p第一個商用的IP路由器是軟件路由器，使用常規(guī)的計算機(jī)硬件：n由通用處理器、共享內(nèi)存、共享總線、若干個網(wǎng)卡組成n通用處理器執(zhí)行大部分的協(xié)議處理任務(wù)，網(wǎng)卡完成組幀及地址識別n適用于低速系統(tǒng)，成本低。2. 路由器的速度p路由器的處理速度決定了：n可以連接到路由器上的網(wǎng)絡(luò)的最大速率n路由器能夠支持的最大網(wǎng)絡(luò)接口數(shù)p集合速率和端口速率：n集合速率：數(shù)據(jù)進(jìn)入或離開一個網(wǎng)絡(luò)系統(tǒng)的總速率，是系統(tǒng)處理能力的測度。n端口速率：在一個網(wǎng)絡(luò)接口上數(shù)據(jù)進(jìn)入或離開的速度。

2、p數(shù)據(jù)速率和包速率：n數(shù)據(jù)速率：單位為比特/秒。n包速率：單位為包/秒（pps），取決于網(wǎng)絡(luò)的吞吐量和包的長度。不同網(wǎng)絡(luò)中的包速 注：灰色條塊代表大數(shù)據(jù)包的速率一個包的最大處理時間注：以上僅是一個網(wǎng)絡(luò)接口的數(shù)據(jù)，如果有N個端口，則每個包的處理 時間還要除以N。一個軟件系統(tǒng)能夠支持多大的包速？p處理一個數(shù)據(jù)包的時間包括：n中斷處理n將包拷入內(nèi)存n包的協(xié)議處理：取決于包的內(nèi)容（如使用的協(xié)議）p一個典型的運(yùn)行Linux內(nèi)核的PC機(jī)，每秒最多可以處理50000個IP包（每個數(shù)據(jù)報只做最少的處理）。p若數(shù)據(jù)包要經(jīng)過防火墻軟件處理，則每秒種最多處理8000個包。軟件路由器的能力p考慮兩個10Base-T的

3、以太網(wǎng)。每個網(wǎng)絡(luò)的最大包速是19500pps，每個包的處理時間不超過25.6微秒，處理每個包的指令數(shù)一般在500010000條之內(nèi)。因此，CPU的執(zhí)行速度必須在195Mips390Mips之間。p許多商用的CPU可以有超過400Mips的執(zhí)行速度，因此軟件路由器可以連接大約兩個10Mbps以太網(wǎng)。p考慮一個10Gbps的網(wǎng)絡(luò)，每微秒產(chǎn)生大約20個數(shù)據(jù)包，CPU每秒鐘必須執(zhí)行21011 條指令。p結(jié)論：運(yùn)行在通用處理器上的軟件無法應(yīng)對高速網(wǎng)絡(luò)。3. 克服單CPU瓶頸p細(xì)粒度并行（指令級并行）p對稱粗粒度并行（對稱多處理器）p非對稱粗粒度并行（非對稱多處理器）p專用協(xié)處理器p智能NICp數(shù)據(jù)流水線

4、3.1 細(xì)粒度并行（指令級并行）p目前幾乎所有的處理器均采用了指令流水線來重疊指令的執(zhí)行，但數(shù)據(jù)包處理程序中可以利用的指令重疊很少。p利用程序中的循環(huán)級并行，如采用向量指令。向量指令可以同時操作在一組數(shù)據(jù)單元上，比如進(jìn)行檢查和計算時，對內(nèi)存中連續(xù)8個位置的數(shù)值同時相加。但數(shù)據(jù)包處理程序中可以利用的循環(huán)級并行很少。p細(xì)粒度并行對包處理來說優(yōu)勢不明顯n包處理功能很少能被細(xì)粒度優(yōu)化的n程序必須花時間建立并行指令n細(xì)粒度并行僅能改善CPU性能，而多數(shù)情況下訪存或I/O是瓶頸3.2 對稱粗粒度并行（SMP）p在一個計算機(jī)上匯集一組相同的CPU，系統(tǒng)資源被所有CPU共享，工作負(fù)載被均勻分配到所有可用的CP

5、U上。p典型的設(shè)計：每個CPU處理一個包，或者每個CPU執(zhí)行一個協(xié)議。p使用N個處理器的網(wǎng)絡(luò)系統(tǒng)獲得的性能增益不是單處理器系統(tǒng)的N倍：n大多數(shù)多處理器系統(tǒng)使用一個共享內(nèi)存n包處理軟件必須協(xié)調(diào)對共享數(shù)據(jù)結(jié)構(gòu)（如隊列）的訪問n只能增加處理能力，不能自動增加I/O帶寬。3.3 非對稱粗粒度并行p使用多個可并行執(zhí)行的異構(gòu)處理器，每個處理器針對一種任務(wù)而優(yōu)化，使用特殊的指令集。p非對稱多處理器的缺點(diǎn)：n每一個處理器都要有自己的指令n比對稱系統(tǒng)難以編程n需要協(xié)調(diào)對共享數(shù)據(jù)結(jié)構(gòu)的訪問n通用性差，不適用于其它任務(wù)或協(xié)議n成本很高3.4 專用協(xié)處理器p使用一個通用CPU加上一個或多個專用協(xié)處理器構(gòu)成網(wǎng)絡(luò)系統(tǒng)。p

6、協(xié)處理器是在CPU控制下運(yùn)行的一個硬件：n靈活的設(shè)計自由度：協(xié)處理器可以設(shè)計得很復(fù)雜，也可以設(shè)計得很簡單n不要求獨(dú)立運(yùn)行，沒有通用指令，也沒有取指令-執(zhí)行周期n可以像軟件例程一樣被調(diào)用n可以被異步調(diào)用，從而允許系統(tǒng)同時處理多個包或?qū)ν粋€包執(zhí)行多個獨(dú)立的操作 p一般將消耗CPU時間最多或最頻繁執(zhí)行的操作（如檢查和計算，加/解密等）用專用協(xié)處理器實(shí)現(xiàn)。p協(xié)處理器通常采用ASIC技術(shù)實(shí)現(xiàn)，ASIC（Application Specific Integrated Circuit）是指為某種特殊需要而定制的集成電路。3.5 智能NICp可以將一部分處理轉(zhuǎn)移到網(wǎng)卡上：n地址識別和過濾，包緩存，DMA，操

7、作鏈n驗證IP頭校驗，從IP頭中抽取某些域，執(zhí)行加密或壓縮等 p在網(wǎng)卡上增加處理的優(yōu)點(diǎn)：n減輕CPU的負(fù)擔(dān)n不要求NIC有很高的處理速度p使用ASIC硬件實(shí)現(xiàn)智能NIC：n設(shè)計專用芯片，集成到網(wǎng)卡上，如鏈路層芯片組、第3層ASIC芯片等n速度快p使用嵌入式RISC硬件實(shí)現(xiàn)智能NIC：n使用標(biāo)準(zhǔn)的RISC處理器代替定制硬件n代價低，易于修改，允許將更多的處理功能轉(zhuǎn)移到NIC上TCP Offload Engine（TOE） pTOE將處理TCP/IP的許多開銷從主機(jī)轉(zhuǎn)移到網(wǎng)卡，只將TCP/IP控制保留在主機(jī)上。 3.6 數(shù)據(jù)流水線p由一系列硬件stage組成的硬件體系結(jié)構(gòu)，數(shù)據(jù)包經(jīng)過每一級時被執(zhí)行

8、一種操作。p優(yōu)點(diǎn)：n適合于多種協(xié)議處理任務(wù)n每一級可以做得很簡單，運(yùn)行得很快n所有級可以同時運(yùn)行4. 總結(jié)p傳統(tǒng)的基于軟件的網(wǎng)絡(luò)系統(tǒng)已經(jīng)不能適應(yīng)高速網(wǎng)絡(luò)的需要p高速網(wǎng)絡(luò)系統(tǒng)需要特殊的硬件支持p可能的硬件體系結(jié)構(gòu)包括：n多處理器系統(tǒng)nASIC協(xié)處理器n智能NICn數(shù)據(jù)流水線主要內(nèi)容p用于協(xié)議處理的硬件體系結(jié)構(gòu)p分類和轉(zhuǎn)發(fā)p交換結(jié)構(gòu)1. 解多路復(fù)用的局限性p解多路復(fù)用：n與分層協(xié)議一起使用，數(shù)據(jù)包穿過協(xié)議棧時每次前進(jìn)一層。n在輸出端，包頭中的類型域指明封裝的格式。n在輸入端，每一層上的軟件選擇高一層上的一個協(xié)議模塊。p特點(diǎn)：n使用全局類型系統(tǒng)，發(fā)送方參與，逐層執(zhí)行。p優(yōu)點(diǎn)：n傳輸效率高：每一種協(xié)議

9、的包頭只需要包含本協(xié)議需要的域n靈活定義新的協(xié)議類型：每個協(xié)議獨(dú)立地定義它的協(xié)議頭，不同協(xié)議頭中的域不共享 p缺點(diǎn)：n逐層順序執(zhí)行使得實(shí)現(xiàn)上很低效2. 包分類p基本思想：一次性檢查所有層次上的相關(guān)域，將包劃分到相應(yīng)的類（也稱流）中。p舉例：n從輸入的以太幀流中分離出去往Web服務(wù)器的流量n描述該流量的規(guī)則集：p以太幀的type域為0 x0800（IP）pIP頭中的protocol域為6（TCP）pTCP段中的destination port域為80（HTTP）n從概念上說，分類器需要計算以上三個條件的邏輯“與”3. 用軟件實(shí)現(xiàn)分類p比較各級包頭中的相關(guān)域，進(jìn)行邏輯“與”運(yùn)算p比如：If(typ

10、e=0 x0800)&(protocol=6)&(destination port=80) Declare the packet matches the classification;Else Declare the packet does not match; 優(yōu)化軟件實(shí)現(xiàn)方法p重新排列條件測試的順序，將能夠過濾掉較多流量的測試排在前面；p比如，若已知95%的幀攜帶了IP包，92%的IP包攜帶了TCP段，85%的TCP段的目的端口號為80，則：If(destination port=80) &(protocol=6) &(type=0 x0800) Declare the packet ma

11、tches the classification;Else Declare the packet does not match the classification; 4. 用硬件實(shí)現(xiàn)分類p建立專用的并行硬件，避免頭域的順序測試。p步驟n抽取多層報頭中的相關(guān)域n將這些域連接成一個多字節(jié)的值n與分類規(guī)則中給出的常數(shù)進(jìn)行比較p在前面的例子中，分類器將type、protocol和destination port三個域中的值連接成一個5字節(jié)的值，然后與08 00 06 00 50進(jìn)行比較。一個硬件分類器的例子包頭長度不固定的解決方法p方法一：在并行測試中增加對長度域的檢查，針對每一種可能的包頭長度設(shè)計

12、一組分類規(guī)則。如在前面的例子中，假設(shè)IP頭長度有20字節(jié)和24字節(jié)兩種，則設(shè)計兩組規(guī)則： Set 1Set2 以太幀的type域為0 x0800 以太幀的type域為0 x0800 IP頭中的頭兩個字節(jié)為0 x45 IP頭中的頭兩個字節(jié)為0 x46 IP頭中的protocol域為6 IP頭中的protocol域為6 距IP頭22個字節(jié)處的域為80 距IP頭24個字節(jié)處的域為80 p方法二：建立一個能夠順序計算報頭偏移量的硬件，抽取當(dāng)前協(xié)議頭長度，并移動相應(yīng)的距離到下一個協(xié)議頭。5. 混合硬件/軟件實(shí)現(xiàn)方法p硬件分類方法：代價高昂，靈活性差p軟件分類方法：靈活性好，速度不高p混合硬件/軟件方法：

13、n結(jié)合硬件分類的高速度與軟件分類的靈活性n包含硬件分類與軟件分類兩個階段，硬件分類處理標(biāo)準(zhǔn)格式的包，軟件分類處理異常的包一個混合分類器系統(tǒng) 注意：軟件分類器可以運(yùn)行在較低的速率6. 多規(guī)則集分類與查找引擎p系統(tǒng)中通常定義了很多個流，分類器要將每個包分配到一個對應(yīng)的流，為此需要查找所有的規(guī)則集。p一般做法：n分類器從包中抽取出相關(guān)域的值n通過一個查找引擎去查找分類規(guī)則表p查找引擎的實(shí)現(xiàn)：n算法：已經(jīng)提出了很多種優(yōu)化的包分類算法，可以并行地檢查所有的規(guī)則集。n內(nèi)容可尋址存儲器CAM：目前絕大多數(shù)的查找引擎是基于CAM實(shí)現(xiàn)的。Content Addressable Memoryp一種支持快速查找的特

14、殊存儲器，與普通存儲器的實(shí)現(xiàn)機(jī)制完全不同。p查找操作：n在CAM中輸入查找關(guān)鍵字nCAM將查找關(guān)鍵字與其存儲的所有表項匹配n返回匹配表項的地址p有兩種類型的CAM：nBCAM（Binary CAM）：存儲位有0、1兩種狀態(tài)，精確匹配查找，一般用于低層應(yīng)用。nTCAM（Ternary CAM）：存儲位有0、1和不確定三種狀態(tài)，支持通配符查找，常用于協(xié)議棧的高層，使用最為廣泛。CAM（續(xù)）p優(yōu)點(diǎn)：n查找速度快，最快在一個時鐘周期內(nèi)完成查找關(guān)鍵字的匹配n可以通過級聯(lián)多個CAM增加容量n具有自動更新能力，能夠更新查找表p缺點(diǎn)：n價格昂貴，封裝面積大，功耗太大，容量有限p一般來說，以下應(yīng)用適合采用CAM

15、：n識別大比特模式n處理小規(guī)模的查找表n對查找延時有嚴(yán)格要求7. 靜態(tài)分類與動態(tài)分類p靜態(tài)分類n流的集合及每個流的分類規(guī)則事先已知n主要用于根據(jù)服務(wù)類型或應(yīng)用來隔離不同的流p動態(tài)分類n流的集合隨時間而變，允許創(chuàng)建和改變流n動態(tài)分類通常使用地址和包類型來區(qū)分流n靈活性好，允許細(xì)粒度的流控制n開銷大，需要保存狀態(tài)信息p動態(tài)分類器應(yīng)能自動建立和維護(hù)流描述表，并進(jìn)行分類查找。通常用軟件實(shí)現(xiàn)，狀態(tài)信息保存在內(nèi)存中。8. 分類與轉(zhuǎn)發(fā)p轉(zhuǎn)發(fā)的任務(wù)是根據(jù)接收到的數(shù)據(jù)包確定包的處理方法，比如根據(jù)數(shù)據(jù)包的目的地址將包轉(zhuǎn)發(fā)到合適的下一跳節(jié)點(diǎn)。 p可以將以上任務(wù)分成兩步來做：n分類：將輸入數(shù)據(jù)包映射到一個流（包-流）

16、n轉(zhuǎn)發(fā)：根據(jù)流確定包的處理方法（流-包的處理）用分類優(yōu)化無連接網(wǎng)絡(luò)中的轉(zhuǎn)發(fā)p將無連接轉(zhuǎn)發(fā)劃分成兩個過程：n分類：destination address-flow IDn轉(zhuǎn)發(fā)：flow ID-(next_hop, interface)p引入分類的好處：n可以將轉(zhuǎn)發(fā)信息放在一個路由cache中，用流標(biāo)識進(jìn)行查找。n可用0, N中的整數(shù)作為流標(biāo)識F，并用F作為路由cache的索引。n路由cache比路由表小很多，而且采用索引查找，查找速度快。p高速轉(zhuǎn)發(fā)的過程：n分類器將數(shù)據(jù)包映射為一個流標(biāo)識Fn轉(zhuǎn)發(fā)器使用F作為索引查找路由cache。p分類和索引的全過程比傳統(tǒng)的解多路復(fù)用和查表快得多。9. 第二代網(wǎng)

17、絡(luò)系統(tǒng)p使用專門的協(xié)議處理硬件，為更高速度的網(wǎng)絡(luò)而設(shè)計的網(wǎng)絡(luò)系統(tǒng)。p第二代網(wǎng)絡(luò)系統(tǒng)具有以下三個顯著的特點(diǎn)：n使用分類代替解多路復(fù)用處理大部分的包n將包處理功能分散到各個網(wǎng)絡(luò)接口，每個NIC都有分類和轉(zhuǎn)發(fā)的能力n提供高速內(nèi)部互連機(jī)制，在各個網(wǎng)絡(luò)接口間提供快速數(shù)據(jù)通道p以上三個特點(diǎn)都允許系統(tǒng)擴(kuò)展，即允許提高每個端口的數(shù)據(jù)速率，允許系統(tǒng)支持更多的網(wǎng)絡(luò)連接。第二代網(wǎng)絡(luò)系統(tǒng)的概念組織p使用一個常規(guī)CPU，用于管理和控制系統(tǒng)、向系統(tǒng)管理員提供管理接口、運(yùn)行路由協(xié)議和更新路由表、處理異常和錯誤。p網(wǎng)絡(luò)接口使用路由表轉(zhuǎn)發(fā)包p快速數(shù)據(jù)通道連接各個網(wǎng)絡(luò)接口一個典型的NIC的組成p物理芯片組：組幀p嵌入式RISC處

18、理器：實(shí)現(xiàn)分類和轉(zhuǎn)發(fā)pROM：存放軟件、分類規(guī)則集等pRAM：卡上包緩存p總線接口主要內(nèi)容p用于協(xié)議處理的硬件體系結(jié)構(gòu)p分類和轉(zhuǎn)發(fā)p交換結(jié)構(gòu)1. 內(nèi)部數(shù)據(jù)通路p常規(guī)計算機(jī)中的總線不能提供足夠的帶寬處理高速網(wǎng)絡(luò)之間的包轉(zhuǎn)發(fā)。p數(shù)據(jù)通路的速度通常用集合數(shù)據(jù)速率和集合包速來衡量。p系統(tǒng)的集合數(shù)據(jù)速率及集合包速對內(nèi)部互連機(jī)制（也稱背板）的要求：必須有足夠的帶寬傳輸進(jìn)入系統(tǒng)的所有包。2. 交換結(jié)構(gòu)的概念p從概念上說，交換結(jié)構(gòu)是一種承擔(dān)背板任務(wù)的硬件機(jī)制，它在一組輸入端口、輸出端口和CPU之間提供數(shù)據(jù)通路。 交換結(jié)構(gòu)的概念（續(xù)）p用于網(wǎng)絡(luò)系統(tǒng)的交換結(jié)構(gòu)需要優(yōu)化以下特性：n可提供在CPU和智能I/O端口之間

19、的連接n支持單播、多播和廣播包的傳輸n可擴(kuò)展支持任意的數(shù)據(jù)速率n可擴(kuò)展支持任意的包速率n可擴(kuò)展支持任意數(shù)目的輸入或輸出端口n低開銷n低代價p實(shí)際的交換結(jié)構(gòu)是對以上各種特性的權(quán)衡3. 交換結(jié)構(gòu)的分類p同步結(jié)構(gòu)與異步結(jié)構(gòu)n同步結(jié)構(gòu)：交換結(jié)構(gòu)按固定的時間間隔傳輸固定長度的數(shù)據(jù)塊，最早用于電話交換機(jī)中。n異步結(jié)構(gòu)：交換結(jié)構(gòu)可以在任何時刻傳輸數(shù)據(jù)，最早用于通用多處理器系統(tǒng)中。p大多數(shù)網(wǎng)絡(luò)交換結(jié)構(gòu)是同步的，每個包被劃分成固定大小的塊，按固定的時間間隔傳輸。 p空分結(jié)構(gòu)與時分結(jié)構(gòu)n空分結(jié)構(gòu)：交換結(jié)構(gòu)中使用許多通路以減小延遲，集合吞吐量高，代價高。n時分結(jié)構(gòu)：許多端口共享一條或者很少幾條內(nèi)部通路，集合吞吐量低

20、，代價低。空分交換結(jié)構(gòu)專用內(nèi)部通路p每一對輸入、輸出端口之間有一條專用硬件通路p每個輸出接口都包含了附加的電路用于處理端口競爭 空分交換結(jié)構(gòu)- Crossbar結(jié)構(gòu)p使用NM 個交叉開關(guān)連接輸入與輸出端口p控制器硬件處理端口競爭p控制器允許多個端口之間并行傳輸p優(yōu)點(diǎn)：n允許同時建立多條路徑，集合吞吐率高n路徑上的硬件只需要容納一條數(shù)據(jù)傳輸，易于支持更高的端口速度。 n比全連接結(jié)構(gòu)經(jīng)濟(jì) p缺點(diǎn)：n要求NM個部件，代價要比其它的一些設(shè)計高。 空分交換結(jié)構(gòu)基本隊列p輸入隊列n設(shè)置在輸入端口與交換結(jié)構(gòu)之間n隊頭阻塞問題p將輸入隊列改為隨機(jī)訪問列表，或者p為每個輸出端口設(shè)置一個隊列p通常在每個輸入端口上

21、設(shè)置兩個隊列，分別存放單播包和多播包p輸出隊列n設(shè)置在交換結(jié)構(gòu)與輸出端口之間p只使用輸入隊列n隊頭阻塞p只使用輸出隊列n輸出隊列及交換結(jié)構(gòu)必須運(yùn)行在集合速率上，或者n針對每個輸入端口設(shè)置一個隊列有輸入輸出隊列的Crossbar結(jié)構(gòu)時分交換結(jié)構(gòu)共享總線結(jié)構(gòu)p交換結(jié)構(gòu)總線包括地址線、數(shù)據(jù)線和控制線p每個輸入和輸出端口都有一個接口硬件，每個端口被分配一個唯一的地址。p端口使用總線硬件將數(shù)據(jù)包傳輸?shù)搅硪粋€端口p總線協(xié)議防止多個端口同時傳輸總線操作的粒度p包粒度：n端口一次發(fā)送一個完整的包n操作和硬件均簡單，但增加了包的延遲 p數(shù)據(jù)塊粒度：n包被劃分成較小的數(shù)據(jù)塊，每個發(fā)送端每次發(fā)送一個數(shù)據(jù)塊；n避免了

22、長延遲，多個傳輸可以并行進(jìn)行；但增加了從一個發(fā)送者切換到另一個發(fā)送者的開銷 p信元粒度：n傳輸長度等于網(wǎng)絡(luò)數(shù)據(jù)單元的長度；n類似于數(shù)據(jù)塊粒度，但特別針對特殊協(xié)議而優(yōu)化了總線協(xié)議p一般采用時分多路復(fù)用的方法，將使用總線的時間片分配給各個輸入端口。p各個輸入端口在總線上輪流廣播收到的包；每個輸出端口的地址過濾器檢查包中攜帶的內(nèi)部路由標(biāo)簽，將發(fā)往本端口的包存放到相應(yīng)的緩沖區(qū)中。共享總線結(jié)構(gòu)的可擴(kuò)展性p總線及接口硬件必須操作在集合速率上。p受底層硬件技術(shù)的制約，該結(jié)構(gòu)一般不能簡單地擴(kuò)展以適應(yīng)任意數(shù)目的端口。時分交換結(jié)構(gòu)共享存儲結(jié)構(gòu)p使用內(nèi)存作為共享媒體連接輸入和輸出端口。p每個端口需要一個內(nèi)存接口硬件，將端口連接到存儲系統(tǒng)。p使用一個控制器硬件在端口之間傳輸控制信息。傳輸控制p一個控制器提供一條單獨(dú)的高速總線，各個端口使用總線來協(xié)調(diào)各自的行為。p輸入端口將一個包放入內(nèi)存后，接口硬件通過控制器發(fā)送一個消息，通知輸出端口數(shù)據(jù)準(zhǔn)備好，消息中給出包在內(nèi)存中的存放地址。p輸出端口從控制器收到消息后，從內(nèi)存的指定位置讀取包，然后發(fā)回響應(yīng)消息。p控制器只是用來傳輸短的控制消息，不用于傳輸大量的數(shù)據(jù)包。共享存儲結(jié)構(gòu)的可擴(kuò)展性p由于內(nèi)存接口硬件非常昂貴，通常讓許多端口共享一個內(nèi)存接口。共享存儲接口在降低代價的同時也降低了吞吐