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

第二章 網(wǎng)絡(luò)實現(xiàn)模型,模型的重要性,網(wǎng)絡(luò)算法學(xué)包含以下幾個不同的領(lǐng)域： 協(xié)議，硬件，體系結(jié)構(gòu)，操作系統(tǒng)，算法。 不同領(lǐng)域的專家通過簡單的模型進行對話： 模型描述了問題的要點，又不涉及不必要的細節(jié) 最低程度：模型應(yīng)能定義所需要的術(shù)語 最好情況：領(lǐng)域外的專家可以根據(jù)模型進行設(shè)計，并可由領(lǐng)域內(nèi)的專家對設(shè)計進行驗證,2.1 協(xié)議抽象模型,協(xié)議定義了通信實體之間交換的報文的格式和次序，以及在報文發(fā)送、接收或收到其它事件后采取的動作。 協(xié)議是一個加上了接口和報文格式的狀態(tài)機。 協(xié)議規(guī)范描述狀態(tài)機如何改變狀態(tài)，以及如何響應(yīng)接口調(diào)用、消息到達和定時器事件。,常見而耗時的功能,與數(shù)據(jù)包收發(fā)有關(guān)的功能： 交換，數(shù)據(jù)拷貝，檢查和計算，內(nèi)存分配等。 與協(xié)議處理有關(guān)的功能： 重組數(shù)據(jù)包 查找及修改狀態(tài) 設(shè)置定時器 調(diào)度任務(wù) 數(shù)據(jù)包交付給應(yīng)用： 解復(fù)用 控制切換,重要的性能指標,網(wǎng)絡(luò)中兩個最重要的性能指標： 吞吐量：每秒處理的包數(shù)（pps）或比特數(shù)（bps）。 延遲：處理一個數(shù)據(jù)包的時間（典型地為最壞情況）。 性能測量分為： 全局性能測量：如端到端延遲和帶寬，使用網(wǎng)絡(luò)管理工具（如OpenView）進行測量。 本地性能測量：如路由器查找速度，使用計算機內(nèi)部的性能測量工具（如Oprofile, Vtune）測量。 本課程關(guān)注本地性能。,因特網(wǎng)環(huán)境的特點,鏈路速度： 骨干鏈路達到10Gbps和40Gbps，本地鏈路達到1Gbps。 無線鏈路和家庭網(wǎng)鏈路的速度要低幾個量級。 TCP和web占主導(dǎo)（目前P2P流量占主導(dǎo)）。 小包：路由器收到的包中大約一半為最小長度（40字節(jié)）的TCP響應(yīng)包。 Small transfers：訪問最多的web文檔都比較小。 延遲很長：實際來回延遲遠遠超過光的傳輸延遲。 局部性很差：在一個包上執(zhí)行的計算在未來短時間內(nèi)重用到另一個包上的可能性很小。,2.2 存儲器,寄存器： 由一組有序的觸發(fā)器構(gòu)成，訪問同一個片上寄存器的耗時大約為0.5-1 ns。 SRAM： 由一組寄存器構(gòu)成。一般情況下，片上SRAM的訪問時間為1-2ns，片外SRAM的訪問時間為5-10ns。 DRAM： 片上DRAM的訪存延遲大約為30ns，最快的片外DRAM訪存延遲為40-60ns，連續(xù)讀的延遲約為100ns。,2019/7/3,page-mode DRAM（快頁內(nèi)存）： 以4字節(jié)突發(fā)模式傳送數(shù)據(jù)，有利于局部性好的訪問模式。 Interleaved DRAM（交錯內(nèi)存）： 幾個DRAM bank集成到一個內(nèi)存芯片中，復(fù)用數(shù)據(jù)線和地址線。 SDRAM（2個bank），RDRAM（16個bank）,2019/7/3,舉例：流水化的流ID查找,應(yīng)用需求： 路由器統(tǒng)計每個流發(fā)送的包數(shù) 每個流用五元組（共96位）進行描述。 線速處理要求： 對于2.5Gbps鏈路和40字節(jié)最小數(shù)據(jù)包，流ID的查找時間不能超過128ns。（40*8/2.5Gb/s = 128ns） 問題規(guī)模： 核心路由器中大約有100萬條并發(fā)的流。,2019/7/3,設(shè)計方案考慮,需要設(shè)計一個數(shù)據(jù)結(jié)構(gòu)： 每個流維護一個計數(shù)器 支持插入和查找兩種操作，查找為針對流ID的精確匹配 要求限制最壞情況下的查找時間（考慮使用平衡二叉樹） 使用SRAM實現(xiàn)？ 維護100萬條流的狀態(tài)，代價太高。 使用普通DRAM實現(xiàn)？ 若實現(xiàn)分支因子為2的二叉樹，查找一個流需要20次訪存；按照訪存周期50ns計算，查找時間為1微秒。,2019/7/3,使用具有16個bank的RDRAM實現(xiàn)樹高為16的二叉樹，樹中第i層的所有節(jié)點存儲在bank i中。 查找芯片同時對16個數(shù)據(jù)包（流ID）進行查找，比如： 用第1個包的流ID查找bank 1中的根節(jié)點，然后查找bank 2中的第二層節(jié)點； 稍后用第2個包的流ID查找bank 1中的根節(jié)點； 依次類推； 當數(shù)據(jù)包1的查找“線程”正在訪問bank 16時，數(shù)據(jù)包16的查找線程在訪問bank 1。 總的查找性能為每個流ID一次查找時間，約為60ns。,2019/7/3,使用RDRAM實現(xiàn)M=3的B-樹,RDRAM允許快頁模式，可一次性讀8個32比特的字（256比特）。 256比特的字可以存放2個96比特的流ID，以及3個20比特的指針。 構(gòu)造一棵高度為16、M=3的B-樹，可以保存31643,000,000個流ID。,2019/7/3,M=3的B-樹示例,2019/7/3,網(wǎng)絡(luò)存儲子系統(tǒng)設(shè)計的主要技術(shù),內(nèi)存交錯和流水線： 類似的技術(shù)也可用于IP查找、包分類和包調(diào)度等。 多個bank可以用多個外部存儲來實現(xiàn)。 寬字并行： 使用DRAM，并利用其快頁模式； 或者使用SRAM，并使得每個內(nèi)存字更寬。 組合DRAM和SRAM： SRAM快而貴，DRAM便宜卻慢，將這兩種技術(shù)組合起來可以得到一個最佳的平衡。,2019/7/3,2.3 端節(jié)點架構(gòu),端節(jié)點是通用計算機，由處理器、存儲器、總線和I/O設(shè)備組成。 處理器是一個狀態(tài)機，以一系列指令和數(shù)據(jù)作為輸入，寫輸出到I/O設(shè)備。 大部分的處理器狀態(tài)保存在外部DRAM（主存）中。主存通常用1GB或更大的交錯內(nèi)存實現(xiàn)，訪問時間長（如60ns）。 處理器使用cache來提高速度： Cache為容量相對較小的SRAM，保存最常使用的狀態(tài)。 某些SRAM（如L1、L2 cache）位于處理器芯片中。 更多的SRAM（如L3 cache）位于處理器芯片外。,2019/7/3,Cache的使用效果與時空局部性,當指令和數(shù)據(jù)呈現(xiàn)時間局部性和空間局部性時，cache的使用效果非常好： 時間局部性：一個存儲位置在短時間內(nèi)被頻繁訪問。 空間局部性：一個存儲位置被訪問后，其鄰近位置在短時間內(nèi)被訪問。 X86處理器利用DRAM的訪存特點實現(xiàn)預(yù)?。好慨斪x取一個32比特字時，處理器預(yù)取連續(xù)的128比特到cache中。 高速數(shù)據(jù)包流基本不呈現(xiàn)時間局部性，因此，協(xié)議實現(xiàn)時注意提高算法及數(shù)據(jù)結(jié)構(gòu)的空間局部性非常重要。,2019/7/3,端節(jié)點的架構(gòu)模型,網(wǎng)絡(luò)應(yīng)用的吞吐量受限于最慢的總線（通常是I/O總線）。 協(xié)議處理通常涉及多次數(shù)據(jù)包拷貝，每個數(shù)據(jù)包都要穿過總線幾次。 處理器性能的提高消除了計算瓶頸，但無助于消除數(shù)據(jù)移動瓶頸。,2019/7/3,2.4 路由器架構(gòu)模型,路由器是具有一組輸入鏈路和一組輸出鏈路的設(shè)備，其任務(wù)是將數(shù)據(jù)包從輸入鏈路交換到輸出鏈路。 路由器的三個主要性能瓶頸： 查找 交換（數(shù)據(jù)包移動） 輸出排隊,2019/7/3,查找,IP地址查找（chapter 11）： 按照最長前綴匹配原則，查找FIB（Forwarding Information Base），確定數(shù)據(jù)包的下一跳。 早期的路由器由主CPU完成地址查找，當今最高端的路由器使用專用芯片完成查找，一些要求實現(xiàn)新功能（如web 負載均衡）的路由器使用網(wǎng)絡(luò)處理器進行查找。 數(shù)據(jù)包分類（chapter 12）： 按照五元組將數(shù)據(jù)包劃分到某一個流中。,2019/7/3,交換,路由器內(nèi)部的交換機制將數(shù)據(jù)包從輸入鏈路 i 傳送到輸出鏈路 j。 早期的路由器使用總線作為交換機制： 假設(shè)存在N條輸入鏈路，每條鏈路的速率為B，則總線上的負載達到BN，成為系統(tǒng)瓶頸。 今天的路由器采用并行交換機制，如crossbar交換機： 每條輸入和輸出鏈路使用各自的總線，通過交換機內(nèi)部的交叉開關(guān)實現(xiàn)連通。 交換機調(diào)度是瓶頸，其問題規(guī)模也是BN。,2019/7/3,排隊,當數(shù)據(jù)包被交換到輸出鏈路后，需要排隊等候發(fā)送。 許多早期的路由器使用一個FIFO隊列。 更復(fù)雜的調(diào)度策略可實現(xiàn)帶寬公平分配或延遲保證： 每條輸出鏈路設(shè)置多條隊列 數(shù)據(jù)包按照一定的原則（優(yōu)先級、業(yè)務(wù)類型、流ID等）放入某個隊列 隊列調(diào)度器每次從一個隊列中取出數(shù)據(jù)包發(fā)送 隊列調(diào)度器是瓶頸。,2019/7/3,其它任務(wù),包頭檢查和修改：一般由硬件完成 選路（RIP，OSPF，BGP）：由主處理器完成。 協(xié)議處理（TCP，UDP，ICMP）：由主處理器完成。 分片、重定向、ARP：在快路徑還是慢路徑上完成，有不同的做法。 基于內(nèi)容的交換：快速URL匹配 流量測量：快速流匹配 ,2019/7/3,2.5 操作系統(tǒng),操作系統(tǒng)是為解決在裸機上編程困難而設(shè)計的。 與裸機打交道的三個最主要難題是：處理中斷，管理內(nèi)存，控制I/O設(shè)備。 為處理這些困難，操作系統(tǒng)提供了不間斷計算、無限存儲和簡單I/O的抽象。 抽象在提高程序員生產(chǎn)效率的同時，帶來了兩個代價： 實現(xiàn)抽象的機制是有代價的 抽象阻礙了程序員對資源的充分利用,2019/7/3,（1） 依靠進程實現(xiàn)不間斷計算的抽象,操作系統(tǒng)通過進程提供給程序員不間斷、順序計算的抽象。 進程抽象通過三個機制實現(xiàn)：上下文切換，調(diào)度，保護。,2019/7/3,進程的三種類型,中斷處理程序： 僅用于處理緊急請求的短小程序。 只使用少量的狀態(tài)（如幾個寄存器），開銷最小。 線程： 輕量級的進程，只需要較少的狀態(tài)。 同一個進程中的線程切換比進程切換開銷小。 用戶進程： 使用計算機的全部狀態(tài)，比如內(nèi)存和寄存器。 用戶進程之間切換的代價很高。,2019/7/3,舉例：接收端活鎖（Receiver Livelock）,計算機將所有的時間用來處理數(shù)據(jù)包中斷，卻因為沒有時間運行應(yīng)用程序，而最終將數(shù)據(jù)包丟棄。,2019/7/3,進程啟動時間,在Pentiem IV計算機上，一個空的中斷調(diào)用，中斷延遲大約為2微秒。 在一個具有兩個進程的Linux機器上，進程上下文切換約用時10微秒；Windows和Solaris用時更多。 在1Gbps鏈路上，10微秒時間內(nèi)可能會有30個最小長度（40字節(jié)）的包到來。 端節(jié)點上網(wǎng)絡(luò)程序的延遲和吞吐量和進程啟動時間有關(guān)。,2019/7/3,（2）依靠虛擬內(nèi)存實現(xiàn)無限存儲的抽象,在虛擬內(nèi)存系統(tǒng)中，程序員使用的內(nèi)存抽象是一個線性存儲空間，編譯器在該空間內(nèi)指定變量的地址。 現(xiàn)代計算機系統(tǒng)使用基于頁的映射方法： 一個虛擬頁為4KB，用虛擬地址的高20位構(gòu)成頁號，低12位構(gòu)成頁內(nèi)偏移量。 物理內(nèi)存劃分為物理頁，每個物理頁的大小為4KB。 虛擬頁到物理頁的映射關(guān)系被保存到一個頁表中，以虛擬頁號作為索引。 （頁表映射） 虛擬頁也可以不在內(nèi)存中，當需要時從磁盤讀入到內(nèi)存的一個物理頁中。（請求調(diào)頁）,2019/7/3,基于頁的內(nèi)存映射,2019/7/3,虛擬內(nèi)存抽象帶來的開銷,到虛擬地址X的一個讀操作可能需要訪問主存兩次： 第一次訪問頁表，將X轉(zhuǎn)換成物理地址P； 第二次訪問地址P。 現(xiàn)代處理器將最近使用過的地址映射緩存在TLB中，實際的地址轉(zhuǎn)換由MMU完成。 極其影響內(nèi)存訪問速度的兩個因素： TLB miss 調(diào)頁,2019/7/3,（3）通過系統(tǒng)調(diào)用實現(xiàn)簡單I/O的抽象,操作系統(tǒng)提供給程序員的設(shè)備抽象是可以進行讀寫的一塊內(nèi)