1、第二章第二章 網絡實現模型網絡實現模型模型的重要性網絡算法學的一個難題是它需要多個領域的知識：協議、硬件、體系結構、操作系統、算法等需要不同領域的專家協作設計出高效的網絡計算機系統不同領域的專家通過簡單的模型進行對話：模型描述了問題的要點，又不涉及不必要的細節最低程度：模型應能定義所需要的術語（能夠交流）最好情況：領域外的專家可以根據模型進行設計，并可由領域內的專家對設計進行驗證2.1 協議抽象模型協議定義了對等實體之間通信的規則：定義了對等實體之間交換的報文的格式和次序定義了在發送報文、收到報文或收到其它事件后采取的動作（通常給出一個協議狀態機）定義了調用接口2021-7-22協議抽象模型（

2、續）可將協議看成是加上了調用接口和報文格式定義的狀態機，所有協議都可以抽象為圖中的狀態機模型： 一個上層接口調用使協議狀態機初始化在某個狀態時，可能發送一個報文、收到一個報文或發生一個定時器事件，并進入一個新的狀態常見而耗時的功能（TCP/IP）與數據包收發有關的功能：數據操作：交換、數據拷貝、檢錯等分配資源（如內存、CPU）與協議處理有關的功能：重組數據包查表及修改狀態設置定時器調度任務數據包交付給應用：解復用（確定目標程序）控制切換（喚醒目標程序）重要的性能指標兩個最重要的性能指標：吞吐量：每秒處理的包數（pps）或比特數（bps）延遲：處理一個數據包的時間（通常關注最壞情況延遲）性能測量

3、分為：全局性能測量：如端到端延遲和帶寬，使用網絡管理工具（如OpenView）進行測量本地性能測量：如路由器查找速度，使用計算機內部的性能測量工具（如Oprofile, Vtune）測量本課程關注數據包在本地的處理速度，線速處理是系統優化的重要目標之一因特網環境的特點鏈路速度已達到萬兆量級10Gbps已普及，40Gbps在數據中心很常見，100Gbps已出現TCP流量占主導大量應用使用TCP協議小包很多路由器收到的包中大約一半為最小長度（40字節）的包移動互聯網、即時通訊應用中大量都是小包局部性很差骨干網上，在一個非常短的時間內大約有一百萬個并發流經過一個路由器這意味著，在一個包上執行的計算，

4、在未來短時間內重用到另一個包上的可能性很小網絡計算機系統面臨的挑戰高速鏈路 + 大量小包：包速率很高線速處理難度大：處理一個包的時間必須非常短高速鏈路 + 大規模并發流：數據局部性很差Cache用不上（命中率低），消除訪存瓶頸困難TCP流占主導 + TCP處理開銷大：優化TCP實現很重要2.2 存儲器在現代計算機系統結構中，訪存是最大的性能瓶頸：存儲器訪問時間比指令執行時間長很多處理器速度和訪存速度之間的鴻溝越來越寬，使得訪存瓶項問題更加突出訪存構成了端節點和路由器的主要性能瓶頸：數據包、狀態信息、指令等都保存在內存中許多系統優化工作都是圍繞訪存優化而展開的2021-7-22存儲器的種類寄存器

5、：由一組有序的觸發器構成，訪問同一個片上寄存器的耗時大約為0.5-1 ns。SRAM：由一組寄存器構成。一般情況下，片上SRAM的訪問時間為1-2ns，片外SRAM的訪問時間為5-10ns。DRAM：存儲單元組織成行、列二維結構。片上DRAM的訪存延遲大約為30ns，最快的片外DRAM訪存延遲為40-60ns，連續讀的延遲約為100ns。2021-7-22存儲器的種類（續）page-mode DRAM（快頁內存）利用DRAM的結構特點，優化對相鄰存儲單元的連續訪問：提供行地址時，選中的那一行數據（4字節）進入到row buffer中如果要訪問的4個字節剛好位于同一行（頁），不需要再提供列地址快

6、頁內存有利于快速訪問局部性好的數據：可以一次讀取相鄰的4個字節優化訪存的措施：有意識地組織數據，將那些要被讀取的數據保存在連續位置2021-7-22存儲器的種類（續）Interleaved DRAM（交織內存）將幾個DRAM bank集成到一個內存芯片中，復用數據線和地址線利用單個DRAM bank讀寫周期長的特點，在總線上交替完成對各個DRAM bank的訪問提高內存帶寬典型的產品有：SDRAM：集成了2個bankRDRAM：集成了16個bank2021-7-22舉例：流ID的流水化查找應用需求：路由器統計每個流發送的包數每個流用五元組（共96位）進行描述線速處理要求：對于2.5Gbps鏈路

7、和40字節最小數據包，流ID的查找時間不能超過128ns。（40*8/2.5Gb/s = 128ns）問題規模：核心路由器中大約有100萬條并發的流2021-7-22設計方案考慮需要設計一個數據結構：每個流維護一個計數器支持插入和查找兩種操作，查找為針對流ID的精確匹配要求限制最壞情況下的查找時間 使用平衡二叉樹使用平衡二叉樹在SRAM中保存查找樹？維護100萬條流的狀態，需要約14MB空間，代價太高！在普通DRAM中保存查找樹？若實現分支因子為2的二叉樹，查找一個流需要20次訪存；按照訪存周期50ns計算，查找時間為1微秒！2021-7-22使用RDRAM實現二分查找使用具有16個bank的

8、RDRAM實現高度為16的二叉樹，樹中第i層的所有節點存儲在bank i中。查找芯片同時對16個數據包（流ID）進行查找，比如：第一個讀周期（60ns）：用第1個包的流ID查找bank 1中的根節點，得到bank 2（第二層）中要查找的節點；第二個讀周期：先用第1個包的流ID查找bank 2，再用第2個包的流ID查找bank 1中的根節點；依次類推流水線充滿后，每60ns完成一個流ID的查找問題：層次為16的二叉樹只能有216=64K個流ID，不能滿足問題規模！ 2021-7-22使用RDRAM實現M=3的B-樹RDRAM允許快頁模式，可一次讀8個32比特的字（256比特）256比特的字可以存

9、放2個96比特的流ID，以及3個20比特的指針構造一棵高度為16、M=3的B-樹，可以保存31643,000,000個流ID2021-7-22網絡芯片的存儲子系統設計技術交織內存和流水線：類似的技術也可用于IP查找、包分類和包調度等多個bank可以用多個外部存儲來實現可并行處理的寬內存字：使用快頁內存，或者 使用內存字較寬的SRAM組合DRAM和SRAM：SRAM快而貴，DRAM便宜卻慢，將這兩種技術組合起來可以得到一個最佳的平衡2021-7-222.3 端節點架構端節點由處理器、存儲器、總線和I/O設備組成處理器是一個狀態機，以一系列指令和數據作為輸入，寫輸出到I/O設備大部分的處理器狀態保

10、存在外部DRAM（主存）中，主存通常用較大的交織內存實現，訪問時間長（如60ns）處理器使用cache來提高速度：Cache為容量相對較小的SRAM，保存最常使用的狀態某些SRAM（如L1、L2 cache）位于處理器芯片中更多的SRAM（如L3 cache）位于處理器芯片外2021-7-22端節點的性能瓶頸網絡應用的吞吐量受限于最慢的總線（通常是I/O總線）協議處理通常涉及多次數據包拷貝，每個數據包都要穿過總線幾次處理器性能的提高消除了計算瓶頸，但無助于消除數據移動瓶頸結論：端節點的性能瓶頸結論：端節點的性能瓶頸不在計算，而在訪存和不在計算，而在訪存和I/O 2021-7-22Cache的使

11、用效果與時空局部性Cache的使用效果與指令/數據的時間局部性和空間局部性有關：時間局部性：一個存儲位置在短時間內被再次訪問空間局部性：一個存儲位置被訪問后，其鄰近位置在短時間內被訪問X86處理器基于空間局部性假設實現預取：每當讀取一個32比特字時，處理器預取連續的128比特到cache中高速數據包流基本不呈現時間局部性：數據包本身通常不會被反復處理同一個流的包往往被大量其它的流隔開對于高速網絡應用，提高算法及數據結構的空間局部性非常重要！對于高速網絡應用，提高算法及數據結構的空間局部性非常重要！2021-7-22提高算法及數據結構的空間局部性設計緊湊的數據結構，使其能夠常駐cache不被換出

12、將隨機訪問（如鏈表）變為順序訪問（如數組）對相同/相近位置進行的操作盡可能放在一起將經常要被一起訪問的數據放在連續位置，且與cache行對齊2.4 操作系統操作系統是為解決在裸機上編程困難而設計的與裸機打交道最主要的三個難題是：處理中斷，管理內存，控制I/O設備為處理這些困難，操作系統提供了三種抽象：不間斷計算，無限存儲，簡單I/O抽象在提高程序員生產效率的同時，帶來了兩個代價：實現抽象的機制是有代價的抽象阻礙了程序員對資源的充分利用2021-7-22（1） 依靠進程實現不間斷計算的抽象操作系統通過進程提供給程序員不間斷、順序計算的抽象進程抽象通過三個機制實現：上下文切換，調度，保護進程抽象帶

13、來的開銷：上下文切換（狀態保存及恢復），調度器運行，API2021-7-22進程的三種類型中斷處理程序：僅用于處理緊急請求的短小程序只使用少量的狀態（如幾個寄存器），開銷（上下文）最小線程：輕量級的進程，只需要較少的狀態（較小的上下文）同一個進程中的線程切換比進程切換開銷?。▋却娌恍枰匦掠成洌┯脩暨M程：使用計算機的全部狀態，比如內存和寄存器（上下文最大）用戶進程之間切換的代價很高（重新映射內存）2021-7-22舉例：接收端活鎖（Receiver Livelock）正常過程：數據包到來產生一個硬件中斷CPU執行中斷處理程序，將數據包描述符拷貝到內核IP隊列，調用一個軟中斷后返回調度器調度CP

14、U執行軟中斷（協議處理），將包放入socket隊列調度器調度相應的應用進程執行接收端活鎖：當包大量到來時，計算機將全部時間用來執行較高優先級的任務，卻因為沒有時間運行低優先級的應用程序而導致數據包最終被丟棄，系統吞吐量為零。2021-7-22進程啟動時間在Pentiem IV計算機上，一個空的中斷調用，中斷延遲大約為2微秒。在一個具有兩個進程的Linux機器上，進程上下文切換約用時10微秒；Windows和Solaris用時更多。在10Gbps以太網鏈路上，10微秒時間內可能會有接近200個最小長度的包到來。在端節點上，應盡可能減少中斷和進程切換的發生。在端節點上，應盡可能減少中斷和進程切換的

15、發生。2021-7-22（2）依靠虛擬內存實現無限存儲的抽象在虛擬內存系統中，程序員使用的內存抽象是一個線性存儲空間，存儲空間大小只受指令地址長度的限制任何一個對虛擬地址的訪問必須映射到一個物理地址上現代計算機系統使用頁表映射和請求調頁兩個機制實現虛擬內存抽象：一個虛擬頁為4KB，用虛擬地址的高20位構成頁號，低12位構成頁內偏移量物理內存劃分為物理頁，每個物理頁的大小為4KB虛擬頁到物理頁的映射關系被保存到一個頁表中，以虛擬頁號作為索引 （頁表映射）虛擬頁也可以不在內存中，當需要時從磁盤讀入到內存的一個物理頁中（請求調頁）2021-7-22虛擬內存抽象帶來的開銷到虛擬地址X的一個讀操作可能需

16、要訪問主存兩次：第一次訪問頁表，將虛擬地址X轉換成物理地址P第二次訪問物理地址P現代處理器將最近使用過的地址映射緩存在TLB中，實際的地址轉換由MMU硬件完成極其影響內存訪問速度的兩個因素：TLB miss請求調頁2021-7-22（3）通過系統調用實現簡單I/O的抽象操作系統提供給程序員的設備抽象是可以進行讀寫的一塊內存，不管是磁盤還是網卡，在程序員看來都是讀寫一個文件描述符2021-7-22設備訪問和系統調用設備驅動程序：將一個I/O接口調用映射到對設備進行實際操作的代碼為安全考慮，設備驅動程序運行在內核空間，提供一組不能被應用程序直接執行的基本服務應用程序必須通過系統調用來訪問設備系統調用：函數調用的一種保護形式，它使處理器進入內核模式執行I/O操作， I/O結束后處理器返回用戶模式系統調用比函數調用的開銷大，涉及用戶代碼/內核代碼切換、參數檢查一個簡單的系統調用可能需要幾個微秒2021-7-222.5 小結本章介紹了影響系統性能的四個抽象等級，以及各個抽象等級的主要開銷來源：協議：如包重組、查表、定時器管理等硬件：如存儲器訪問體系結構：如總線速度、cache容量操作系統：如進程切換、虛擬內存、系統調用等理解這些抽象等級，對于改進系統性能有很大的幫助2021-7-22文獻閱讀作業1 PacketShader: a GPU-Accele