【正文】 ? 訪問內(nèi)存次數(shù)少： ? 查找一個數(shù)據(jù)包， RFC需要 13次訪存， TIC大約需要 7+1=8次訪存。（由端口號和協(xié)議組成的范圍表達(dá)式列表被預(yù)先編碼成一系列的 ALU指令） ? 一個解釋器從外部存儲器裝載代碼塊到內(nèi)部存儲器，然后解碼并順序執(zhí)行指令，以找到一個匹配。 一個三維規(guī)則集例子 r u l e F 1 F 2R 1R 2R 3R 40 0 10 0 10 1 ** * *0 1 01 0 01 0 0* * *F 30 1 10 1 1* * ** * *A C T I O Np e r m i td e n yp e r m i tp e r m i tRFC的特點(diǎn) ? RFC是目前除硬件方案之外較快的多維包分類算法。 ? 每個節(jié)點(diǎn)的所有子節(jié)點(diǎn)將父節(jié)點(diǎn)包含的 d維空間按某一維平均劃分，每個節(jié)點(diǎn)保存與其 d維空間相交的規(guī)則的集合。 ? 根據(jù)目的端口和源端口的不同組合建立 4個哈希表，分別對應(yīng)（ DstPort， *）、（ DetPort， SrcPort）、（ *，SrcPort）和（ *， *）的情況。 ? 優(yōu)點(diǎn)： 不需回溯，減少了查找時間。 ? IP分類問題比多維空間的點(diǎn)定位問題復(fù)雜： ? 規(guī)則的數(shù)量可能很大 ? 區(qū)域之間可能有重疊 IP分類問題的解決思路 ? 一般性地求解 IP分類問題很困難，需根據(jù)數(shù)據(jù)流的分布特點(diǎn)以及規(guī)則集中規(guī)則的分布特點(diǎn)設(shè)計(jì)高效的分類算法（啟發(fā)式算法）。 ? 與每個 f[i]相關(guān)聯(lián)有一個匹配方式，可以是： ? 精確匹配： f[i]用一個值表示，若 H[i]=f[i]，稱 H[i]與 f[i]精確匹配。 ? 每一層節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)中都有一個標(biāo)志位用于指示是否需要繼續(xù)查找下一層節(jié)點(diǎn)。 ? 構(gòu)造查找步寬為 2488816的五層多分支 Trie樹，限制最壞情況下路由查找的訪存次數(shù)。 ? 缺點(diǎn)： TCAM容量小、代價高、功耗大、更新復(fù)雜（關(guān)鍵字需要排序）。 ? CAM被組織成一個二維陣列，每一行長度固定，稱為一個槽。 多分支 Trie的優(yōu)化 ? 步寬的選擇 ? 步寬的選擇是在算法查找速度、存儲空間和更新復(fù)雜度之間的折衷。 ? 查找步寬：每次檢查的比特?cái)?shù)稱為查找步寬。例如，刪除前綴 1*。 ? 以上查找方法為基于長度的順序前綴查找，每搜索一步，搜索空間就縮減一半。 ? 轉(zhuǎn)發(fā)表查找要求采用最長前綴匹配查找而不是精確匹配查找。 ? 地址前綴的兩種表示方法： ? 不大于 32比特的比特串跟上一個 *，比如：1000001001010110* ? 帶點(diǎn)十進(jìn)制表示加上地址前綴長度，比如： ? 地址聚合：連接到同一個網(wǎng)絡(luò)的所有主機(jī)在轉(zhuǎn)發(fā)表中對應(yīng)一個入口，即允許使用前綴表示一組地址。 ? CPU預(yù)先在內(nèi)存中分配好以上數(shù)據(jù)結(jié)構(gòu)，并將一個 skb地址（包描述符）通知給網(wǎng)卡。 ? 同一塊網(wǎng)卡上的兩個端口共享一個 x8 PCIe ， 8條數(shù)據(jù)線能夠獲得的最大載荷數(shù)據(jù)速率為 。 設(shè)計(jì)原則（ 1） 構(gòu)建集群路由器 ? 設(shè)計(jì)原則一： ? 將路由器的功能并行化到多個服務(wù)器上，降低對單個服務(wù)器的性能要求，即設(shè)計(jì)一個集群路由器架構(gòu)。 構(gòu)建可擴(kuò)展高速路由器的方法（ 2） ? 從軟件路由器著手，提高其包處理速度： ? 開發(fā)容易：可使用熟悉的計(jì)算機(jī)硬件平臺、操作系統(tǒng)和開發(fā)工具來開發(fā)網(wǎng)絡(luò)設(shè)備。 ? 設(shè)計(jì)中已經(jīng)考慮了適合網(wǎng)絡(luò)處理的有用特性。 Cisco Versatile Interface Processor 1996年引入 VIP接口板 Cisco 10000 ESR（邊緣服務(wù)路由器） ? 線卡（ 8塊）：管理自己的接口類型，通過背板向 PRE發(fā)送和接收數(shù)據(jù)包。 ? 慢路徑（非關(guān)鍵路徑）： ? 由非時間關(guān)鍵的處理任務(wù)構(gòu)成：與包轉(zhuǎn)發(fā)不直接相關(guān)的任務(wù)一般 是非時間關(guān)鍵任務(wù)。 ? 缺點(diǎn)：共享總線仍然是瓶頸。 ? 頻繁的路由更新使得 cache中的路由信息很快失效。 IP路由器的一般結(jié)構(gòu) 路由表查找 — Binary Trie ? 將路由表中的地址前綴組織在一棵二元查找樹中。 ? 查找時使用地址前綴的每一位決定樹的分支。 IP路由器架構(gòu)的演變 ? 第一代：基于總線和單處理器 的架構(gòu)（軟件路由器） ? CPU需要完成全部的網(wǎng)絡(luò)處理功能 ? 每個包需穿過總線兩次 ? 路由器的性能嚴(yán)重依賴于共享總線的吞吐量以及 CPU的處理速度，不具有擴(kuò)放性。 第三代：基于交換的路由器架構(gòu) ? 控制卡、線卡和轉(zhuǎn)發(fā)引擎卡通過一個高速交換結(jié)構(gòu)連接： ? 每塊線卡包含多個網(wǎng)絡(luò)接口 ? 每塊轉(zhuǎn)發(fā)引擎卡包含路由緩存，負(fù)責(zé)包頭處理與轉(zhuǎn)發(fā) ? 控制卡提供基本的管理功能。 ? 慢路徑一般在 CPU上用軟件實(shí)現(xiàn)。 ? PRE（主、備各一塊）： ? RP：運(yùn)行路由協(xié)議，更新路由表，其它控制面功能。 Intel Nehalem 8核處理器內(nèi)部結(jié)構(gòu) ? 8個核，每個核自帶256KB L2 cache ? 8個核共享一個 L3 cache ? 內(nèi)置內(nèi)存控制器 ? 微內(nèi)核與內(nèi)存控制器之間使用crossbar交叉互聯(lián) ? 內(nèi)置 QPI接口，允許與其它處理器進(jìn)行高速點(diǎn)對點(diǎn)連接 多個處理器互聯(lián) ? NehalemEX 的最高配置是 4 芯 32 核。 ? 擴(kuò)展性好：數(shù)據(jù)面和控制面功能可通過軟件升級來修改，免去開發(fā)者設(shè)計(jì)硬件的負(fù)擔(dān)。 ? 每個服務(wù)器承擔(dān)傳統(tǒng)路由器中線卡的功能，負(fù)責(zé)一個或幾個端口的包處理，處理速度為 kR。 ? 因此，每塊網(wǎng)卡可獲得 ，服務(wù)器最高數(shù)據(jù)輸入速率為 。 ? 當(dāng)有數(shù)據(jù)包到達(dá)網(wǎng)卡時，網(wǎng)卡將數(shù)據(jù)包及元數(shù)據(jù)通過 DMA存放到指定位置，然后向 CPU發(fā)送中斷，返回包描述符。 轉(zhuǎn)發(fā)表舉例 基于類的編址方案 ? 地址空間利用率低，地址短缺問題日益突顯。 ? 地址查找在數(shù)值和長度兩個維度上進(jìn)行。 Trie樹的更新（ 1） ? 插入一個地址前綴 ? 以 該前綴為關(guān)鍵字在 Trie樹中進(jìn)行查找。 ? 若查找過程終止于葉子節(jié)點(diǎn)，除了刪除該節(jié)點(diǎn)之外，還需要根據(jù)情況刪除其它一些內(nèi)部節(jié)點(diǎn) 。 ? 根據(jù)同一層中不同子樹的步寬是否相同，分為： ? 固定步寬多分支 Trie ? 可變步寬多分支 Trie 可變步寬與固定步寬的多分支 Trie樹 前綴擴(kuò)展 ? 前綴表中的地址前綴必須轉(zhuǎn)換成多分支 Trie查找允許的地址前綴。 ? 一種較自然的做法是根據(jù)二分支 Trie的 地址前綴分布來選擇合適的步寬。 ? 處理器提供一個查找關(guān)鍵字，CAM返回匹配該關(guān)鍵字的一組槽。 T C A M 芯片 NextHop索 引表 NextHop映 射表目的I P 地址下一跳地址和端口（ 6） IPv6地址查找 ? IPv6路由表的特點(diǎn)： ? 前綴更長： IPv6地址長 128比特。 前綴擴(kuò)展產(chǎn)生許多冗余 （ 2020:4*::/18, A）和（ 2020:5*::/20, B）擴(kuò)展出來的表項(xiàng) TrieC的算法思想 ? 具有相同下一跳的前綴項(xiàng)組成一個數(shù)據(jù)塊，下一跳信息只在表中存儲一次。 網(wǎng)絡(luò)處理器中的實(shí)現(xiàn)優(yōu)化 ? 位操作指令 ? POP_COUNT指令：可在 3個時鐘周期內(nèi)計(jì)算 32位寄存器中 1的個數(shù)。 ? 前綴匹配： f[i]通過一個前綴指定，若 H[i]與 f[i]表示的前綴匹配