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