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