《網(wǎng)絡(luò)實(shí)現(xiàn)模型》ppt課件

《《網(wǎng)絡(luò)實(shí)現(xiàn)模型》ppt課件》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、第二章網(wǎng)絡(luò)實(shí)現(xiàn)模型模型的重要性網(wǎng)絡(luò)算法學(xué)包含以下幾個(gè)不同的領(lǐng)域：協(xié)議，硬件，體系結(jié)構(gòu)，操作系統(tǒng)，算法。不同領(lǐng)域的專家通過(guò)簡(jiǎn)單的模型進(jìn)行對(duì)話：模型描述了問(wèn)題的要點(diǎn)，又不涉及不必要的細(xì)節(jié)最低程度：模型應(yīng)能定義所需要的術(shù)語(yǔ)最好情況：領(lǐng)域外的專家可以根據(jù)模型進(jìn)行設(shè)計(jì)，并可由領(lǐng)域內(nèi)的專家對(duì)設(shè)計(jì)進(jìn)行驗(yàn)證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í)器事件。常見(jiàn)而耗時(shí)的功能與數(shù)據(jù)

2、包收發(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ù)用控制切換重要的性能指標(biāo)網(wǎng)絡(luò)中兩個(gè)最重要的性能指標(biāo)：吞吐量：每秒處理的包數(shù)（pps）或比特?cái)?shù)（bps）。延遲：處理一個(gè)數(shù)據(jù)包的時(shí)間（典型地為最壞情況）。性能測(cè)量分為：全局性能測(cè)量：如端到端延遲和帶寬，使用網(wǎng)絡(luò)管理工具（如OpenView）進(jìn)行測(cè)量。本地性能測(cè)量：如路由器查找速度，使用計(jì)算機(jī)內(nèi)部的性能測(cè)量工具（如Oprofile,Vtune）測(cè)量。本課程關(guān)注本地性能。因特網(wǎng)環(huán)境的特點(diǎn)鏈路速度：骨干

3、鏈路達(dá)到10Gbps和40Gbps，本地鏈路達(dá)到1Gbps。無(wú)線鏈路和家庭網(wǎng)鏈路的速度要低幾個(gè)量級(jí)。TCP和web占主導(dǎo)（目前P2P流量占主導(dǎo)）。小包：路由器收到的包中大約一半為最小長(zhǎng)度（40字節(jié)）的TCP響應(yīng)包。Smalltransfers：訪問(wèn)最多的web文檔都比較小。延遲很長(zhǎng)：實(shí)際來(lái)回延遲遠(yuǎn)遠(yuǎn)超過(guò)光的傳輸延遲。局部性很差：在一個(gè)包上執(zhí)行的計(jì)算在未來(lái)短時(shí)間內(nèi)重用到另一個(gè)包上的可能性很小。2.2存儲(chǔ)器寄存器：由一組有序的觸發(fā)器構(gòu)成，訪問(wèn)同一個(gè)片上寄存器的耗時(shí)大約為0.5-1ns。SRAM：由一組寄存器構(gòu)成。一般情況下，片上SRAM的訪

4、問(wèn)時(shí)間為1-2ns，片外SRAM的訪問(wèn)時(shí)間為5-10ns。DRAM：片上DRAM的訪存延遲大約為30ns，最快的片外DRAM訪存延遲為40-60ns，連續(xù)讀的延遲約為100ns。2021/10/2page-modeDRAM（快頁(yè)內(nèi)存）：以4字節(jié)突發(fā)模式傳送數(shù)據(jù)，有利于局部性好的訪問(wèn)模式。InterleavedDRAM（交錯(cuò)內(nèi)存）：幾個(gè)DRAMbank集成到一個(gè)內(nèi)存芯片中，復(fù)用數(shù)據(jù)線和地址線。SDRAM（2個(gè)bank），RDRAM（16個(gè)bank）2021/10/2舉例：流水化的流ID查找應(yīng)用需求：路由器統(tǒng)計(jì)每個(gè)流發(fā)送的包數(shù)每個(gè)流用五元組

5、<源IP地址，目的IP地址，源端口號(hào)，目的端口號(hào)，協(xié)議>（共96位）進(jìn)行描述。線速處理要求：對(duì)于2.5Gbps鏈路和40字節(jié)最小數(shù)據(jù)包，流ID的查找時(shí)間不能超過(guò)128ns。（40*8/2.5Gb/s=128ns）問(wèn)題規(guī)模：核心路由器中大約有100萬(wàn)條并發(fā)的流。2021/10/2設(shè)計(jì)方案考慮需要設(shè)計(jì)一個(gè)數(shù)據(jù)結(jié)構(gòu)：每個(gè)流維護(hù)一個(gè)計(jì)數(shù)器支持插入和查找兩種操作，查找為針對(duì)流ID的精確匹配要求限制最壞情況下的查找時(shí)間（考慮使用平衡二叉樹(shù)）使用SRAM實(shí)現(xiàn)？維護(hù)100萬(wàn)條流的狀態(tài)，代價(jià)太高。使用普通DRAM實(shí)現(xiàn)？若實(shí)現(xiàn)分支因子為2的二叉樹(shù)，查找一個(gè)

6、流需要20次訪存；按照訪存周期50ns計(jì)算，查找時(shí)間為1微秒。2021/10/2使用RDRAM實(shí)現(xiàn)二分查找使用具有16個(gè)bank的RDRAM實(shí)現(xiàn)樹(shù)高為16的二叉樹(shù)，樹(shù)中第i層的所有節(jié)點(diǎn)存儲(chǔ)在banki中。查找芯片同時(shí)對(duì)16個(gè)數(shù)據(jù)包（流ID）進(jìn)行查找，比如：用第1個(gè)包的流ID查找bank1中的根節(jié)點(diǎn)，然后查找bank2中的第二層節(jié)點(diǎn)；稍后用第2個(gè)包的流ID查找bank1中的根節(jié)點(diǎn)；依次類推；當(dāng)數(shù)據(jù)包1的查找“線程”正在訪問(wèn)bank16時(shí)，數(shù)據(jù)包16的查找線程在訪問(wèn)bank1?？偟牟檎倚阅転槊總€(gè)流ID一次查找時(shí)間，約為60ns。2021/1

7、0/2使用RDRAM實(shí)現(xiàn)M=3的B-樹(shù)RDRAM允許快頁(yè)模式，可一次性讀8個(gè)32比特的字（256比特）。256比特的字可以存放2個(gè)96比特的流ID，以及3個(gè)20比特的指針。構(gòu)造一棵高度為16、M=3的B-樹(shù)，可以保存316≈43,000,000個(gè)流ID。2021/10/2M=3的B-樹(shù)示例2021/10/2網(wǎng)絡(luò)存儲(chǔ)子系統(tǒng)設(shè)計(jì)的主要技術(shù)內(nèi)存交錯(cuò)和流水線：類似的技術(shù)也可用于IP查找、包分類和包調(diào)度等。多個(gè)bank可以用多個(gè)外部存儲(chǔ)來(lái)實(shí)現(xiàn)。寬字并行：使用DRAM，并利用其快頁(yè)模式；或者使用SRAM，并使得每個(gè)內(nèi)存字更寬。組合DRAM和SRAM

8、：SRAM快而貴，DRAM便宜卻慢，將這兩種技術(shù)組合起來(lái)可以得到一個(gè)最佳的平衡。2021/10/22.3端節(jié)點(diǎn)架構(gòu)端節(jié)點(diǎn)是通用計(jì)算機(jī)，由處理器、存儲(chǔ)器、總線和I/O設(shè)備組成。處理器是一個(gè)狀態(tài)機(jī)，以一系列指令