【正文】 綴匹配。 ? 硬件 CRC指令： ? 5個時鐘周期完成計算。 網絡處理器中的實現優(yōu)化 ? 位操作指令 ? POP_COUNT指令：可在 3個時鐘周期內計算 32位寄存器中 1的個數。 TrieC樹結構 ? 建立 2488816多分支 TrieC樹： ? 根節(jié)點采用 TrieC15/6數據結構，存儲長度為 [1, 24]比特的地址前綴。 前綴擴展產生許多冗余 （ 2020:4*::/18, A）和（ 2020:5*::/20, B）擴展出來的表項 TrieC的算法思想 ? 具有相同下一跳的前綴項組成一個數據塊，下一跳信息只在表中存儲一次。 ? 基于 TCAM的方法不適用于規(guī)模巨大的表。 T C A M 芯片 NextHop索 引表 NextHop映 射表目的I P 地址下一跳地址和端口（ 6） IPv6地址查找 ? IPv6路由表的特點： ? 前綴更長： IPv6地址長 128比特。 ? TCAM適合于查找?guī)ㄅ浞年P鍵字。 ? 處理器提供一個查找關鍵字，CAM返回匹配該關鍵字的一組槽。 ? 第二層步寬 8比特：少數情況下需要查找這一層。 ? 一種較自然的做法是根據二分支 Trie的 地址前綴分布來選擇合適的步寬。 ? 多分支 Trie的更新過程比二分支 Trie復雜： ? 插入一個前綴時，需要找到相應的 subtrie，對前綴進行擴展，然后插入。 ? 根據同一層中不同子樹的步寬是否相同，分為： ? 固定步寬多分支 Trie ? 可變步寬多分支 Trie 可變步寬與固定步寬的多分支 Trie樹 前綴擴展 ? 前綴表中的地址前綴必須轉換成多分支 Trie查找允許的地址前綴。 ? 研究表明，對于一個具有 47113個前綴表項的典型骨干網路由器，使用 BSD Trie會創(chuàng)建 93304個節(jié)點，樹的最大高度為 26，平均高度為 20。 ? 若查找過程終止于葉子節(jié)點，除了刪除該節(jié)點之外，還需要根據情況刪除其它一些內部節(jié)點 。 例如，插入前綴 00*。 Trie樹的更新（ 1） ? 插入一個地址前綴 ? 以 該前綴為關鍵字在 Trie樹中進行查找。 Trie樹代表的地址空間結構 Trie樹的查找 ? 從根節(jié)點開始每次一位地查找： ? 當地址中的相應位為 0時選擇左分支，為 1時選擇右分支。 ? 地址查找在數值和長度兩個維度上進行。 地址聚合的例子（ 1） 地址聚合的例子（ 2） 路由器的地址查找問題，就是要從轉發(fā)表中查找匹配數據包目的地址的最長的地址前綴。 轉發(fā)表舉例 基于類的編址方案 ? 地址空間利用率低，地址短缺問題日益突顯。性能提升 3倍。 ? 當有數據包到達網卡時，網卡將數據包及元數據通過 DMA存放到指定位置，然后向 CPU發(fā)送中斷，返回包描述符。 優(yōu)化措施（ 1） 充分利用服務器的并行性 ? 用基于點到點連接的 Nehalem 服務器代替基于共享總線結構的 Xeon服務器，性能提高了 23倍。 ? 因此，每塊網卡可獲得 ，服務器最高數據輸入速率為 。 集群路由器架構圖示 設計原則（ 2） ? 僅當單個服務器的性能能夠提高到 cR，集群路由器架構方案才是可行的，但目前的服務器遠不能達到這個速度。 ? 每個服務器承擔傳統(tǒng)路由器中線卡的功能，負責一個或幾個端口的包處理，處理速度為 kR。 ? 路由器的功能主要是包處理和包交換： ? 包處理：典型地發(fā)生在線卡上，每塊線卡處理一個或幾個端口，線卡的處理速度為 kR（ k為端口數）。 ? 擴展性好：數據面和控制面功能可通過軟件升級來修改，免去開發(fā)者設計硬件的負擔。 ? 軟件路由器利用通用平臺上的軟件執(zhí)行包處理任務，易于編程，但只適用于低速環(huán)境。 Intel Nehalem 8核處理器內部結構 ? 8個核，每個核自帶256KB L2 cache ? 8個核共享一個 L3 cache ? 內置內存控制器 ? 微內核與內存控制器之間使用crossbar交叉互聯 ? 內置 QPI接口，允許與其它處理器進行高速點對點連接 多個處理器互聯 ? NehalemEX 的最高配置是 4 芯 32 核。 ? 板卡之間的高速互聯： ? 更高帶寬的互聯結構代替原先的交換結構。 ? PRE（主、備各一塊）： ? RP：運行路由協議，更新路由表，其它控制面功能。 ? 其它維護功能，如網絡管理。 ? 慢路徑一般在 CPU上用軟件實現。 小結 ? 路由器架構基本上是從集中式向分布式演變： ? 將協議棧的處理功能分布到主控制板及各個網絡接口卡上，消除處理和訪存瓶頸 ? 使用交換結構消除內部總線瓶頸 ? 針對路由器結構的各種改進都是要消除處理、訪存、總線三個性能瓶頸。 第三代：基于交換的路由器架構 ? 控制卡、線卡和轉發(fā)引擎卡通過一個高速交換結構連接： ? 每塊線卡包含多個網絡接口 ? 每塊轉發(fā)引擎卡包含路由緩存，負責包頭處理與轉發(fā) ? 控制卡提供基本的管理功能。 ? 轉發(fā)引擎包含自己的路由 cache，只負責解析下一跳和處理包頭。 IP路由器架構的演變 ? 第一代：基于總線和單處理器 的架構（軟件路由器） ? CPU需要完成全部的網絡處理功能 ? 每個包需穿過總線兩次 ? 路由器的性能嚴重依賴于共享總線的吞吐量以及 CPU的處理速度，不具有擴放性。 ? 先用目的地址查找路由 cache，不命中再查找路由表。 ? 查找時使用地址前綴的每一位決定樹的分支。IP路由器 主要內容 ? IP路由器架構 ? 路由查找 ? 數據包分類 1 IP路由器架構 IP路由器的功能 ? IP路由器的基本功能可以分為三類： ? 路由處理： 運行路由協議，建立并維護路由表。 IP路由器的一般結構 路由表查找 — Binary Trie ? 將路由表中的地址前綴組織在一棵二元查找樹中。 路由緩存（ cache） ? 為提高路由查找速度，采用二元查找樹 +路由緩存的方法： ? 路由 cache中存放最近使用過的 目的 IP地址，下一跳 ，用哈希表組織，使用精確匹配查找。 ? 頻繁的路由更新使得 cache中的路由信息很快失效。 帶路由緩存的結構 第二代：基于總線和多處理器的架構（ 2） 使用轉發(fā)引擎的結構 ? 轉發(fā)功能由專門的轉發(fā)引擎完成。 ? 缺點：共享總線仍然是瓶頸。 ? 解決方案： ? 在每個網絡接口上用轉發(fā)數據庫（ Forward Information Base， IP路由表的完整鏡像）取代路由緩存。 ? 慢路徑（非關鍵路徑）： ? 由非時間關鍵的處理任務構成：與包轉發(fā)不直接相關的任務一般 是非時間關鍵任務。 ? 運行路由協議。 Cisco Versatile Interface Processor 1996年引入 VIP接口板 Cisco 10000 ESR（邊緣服務路由器） ? 線卡（ 8塊）：管理自己的接口類型，通過背板向 PRE發(fā)送和接收數據包。 Cisco ASR1000 路由器架構的進一步發(fā)展 ? 更多的包處理功能加到快路徑上： ? 包過濾、深度數據包檢查、流量管理等原先屬于特殊服務的功能，現在也加入到了快路徑上。 ? 設計中已經考慮了適合網