【正文】 主要參考文獻(xiàn) [1] IP Router Architectures: An Overview. [2] Study of Inter Router Architectures. [3] RouteBricks: Exploiting Parallelism to Scale Software Routers. [4] Survey and Taxonomy of IP Address Lookup Algorithms. [5] Highperformance IPv6 Forwarding Algorithm for Multicore and Multithreaded Network Processor. [6] Survey amp。 ? %的情況下，匹配一對(duì)地址的候選范圍可以編碼成一個(gè) 64字節(jié)的代碼塊（ X86上一個(gè) cache行大?。瑑H需訪問內(nèi)存一次。 RFC與 TIC的訪存次數(shù) 4階段 RFC TIC TIC與 RFC的比較 ? 內(nèi)存空間?。? ? TIC最多可比 RFC節(jié)省 97%的存儲(chǔ)空間。 源端口和目的端口的分布 ? 12字節(jié)的指令非常少見。 ? 采用 CISC風(fēng)格的指令，總共需要約 5 5 2=50種操作符。 指令編碼 ? 5種端口范圍： WC（通配）、 HI（高端）、 LO（低端）、 AR（任意范圍）、 EM（精確匹配）。 TIC的設(shè)計(jì) ? 第一階段采用 RFC算法，找到匹配一對(duì) 源 IP地址，目的 IP地址 的規(guī)則集，實(shí)際上得到的是對(duì)應(yīng)該規(guī)則集的代碼塊的地址。 TIC算法 ? 算法要點(diǎn)： ? 將匹配一對(duì) 源 IP地址，目的 IP地址 的過程與匹配其余 3個(gè)域的過程分開，前者使用適合前綴查找的算法，后者使用適合范圍查找的算法。 ? 前綴查找是訪存密集的操作，范圍查找是計(jì)算密集的操作，將兩者分開處理有助于提高查找的效率。 ? 易于并行處理 ? 處于同一階段的預(yù)處理表或交叉乘積表可被并行地索引 ? 處于不同階段的表也可被并行地索引 ? 這些表各自獨(dú)立，可分布于不同的存儲(chǔ)單元中 ? 缺點(diǎn)： ? 交叉乘積表占用內(nèi)存空間較多，存儲(chǔ)空間 消耗隨規(guī)則集規(guī)模增大而迅速增大。 ? 每一階段映射稱為一次縮減（ reduction），由多階段映射構(gòu)建的數(shù)據(jù)結(jié)構(gòu)稱為縮減樹。 ? 從 S位比特串直接映射到 eqID需要消耗巨大的內(nèi)存空間。 ? 缺點(diǎn)： ? 預(yù)處理時(shí)間長(zhǎng)，比一些快速包分類算法慢。 ? 當(dāng)某節(jié)點(diǎn)包含的規(guī)則數(shù)超過預(yù)先定義的門限時(shí)，節(jié)點(diǎn)進(jìn)一步被劃分為若干子節(jié)點(diǎn)。 001F 1F 20 1 0 0 1 11 1 0 1 1 10 0 1 0 0 10010 0 1 1 0 01 0 1 1 0 00 0 0 0 1 10 1 1 1 0 0規(guī)則 F 1 （目的地址） F 2 （源地址）R1R2R3R4R5R600*0*1*00*0**00*01*0*0*1*1*（ 5） HiCuts ? 算法思想： ? 采用一棵基于規(guī)則的決策樹，根節(jié)點(diǎn)包含整個(gè) d維空間。 ? 算法復(fù)雜度分析： ? N位與操作的時(shí)間復(fù)雜度為 O(N)，若一個(gè)字長(zhǎng)為 W比特，最壞情況下與操作需要（ N*d） /W次內(nèi)存訪問。 ? 根據(jù) Grid of Tries的查找方法找到最小代價(jià)規(guī)則 ? 取所有哈希表中的最好結(jié)果，即為最佳匹配的規(guī)則。 ? 每個(gè)哈希表項(xiàng)為一棵 Grid of Tries，哈希表的索引為相應(yīng)的端口地址和協(xié)議號(hào)的某種組合（或函數(shù)）。 ? 協(xié)議域的處理： ? 協(xié)議只取 TCP、 UDP和通配（ *）三個(gè)值； ? 對(duì)于取值為通配的規(guī)則，將一條規(guī)則重復(fù) 3次，分別對(duì)應(yīng)TCP、 UDP和其它情況（ OTHER）。 ? 特點(diǎn)：不需回溯， 內(nèi)存空間小，但更新困難。 ? 查找過程： ? 先對(duì)目的地址做最長(zhǎng)前綴匹配； ? 在所指向的源地址 Trie上，根據(jù)包頭的源地址沿著 0、1指針（或者轉(zhuǎn)發(fā)指針）盡可能地前進(jìn)。 ? 缺點(diǎn)：空間復(fù)雜度高，不易更新，只適用于靜態(tài)規(guī)則集。 ? 分類時(shí)，只需查找一遍目的地址 Trie和一遍源地址Trie，就可以完成規(guī)則匹配。 ? 對(duì)這個(gè)節(jié)點(diǎn)及其父節(jié)點(diǎn)所指向的所有第二級(jí) Trie進(jìn)行匹配查找，得到優(yōu)先級(jí)最高的規(guī)則。 ? 第一級(jí) Trie中的每個(gè)前綴節(jié)點(diǎn)（即規(guī)則集中存在對(duì)應(yīng)的項(xiàng)），有指針指向其第二級(jí) Trie。 ? 將高維問題轉(zhuǎn)化為二維乃至一維的問題，降低問題的復(fù)雜度。 IP分類問題的復(fù)雜度 ? 假設(shè)不同區(qū)域互不相交，對(duì) N條規(guī)則進(jìn)行 k（ k3）維分類，計(jì)算幾何給出的最好結(jié)果是： ? 空間復(fù)雜度為 O(Nk)時(shí)，時(shí)間復(fù)雜度為 O(logN)； ? 或者，空間復(fù)雜度為 O(N)時(shí)，時(shí)間復(fù)雜度為O(logk1N)。 IP分類與多維空間的點(diǎn)定位 ? 多維空間的點(diǎn)定位問題： ? 給定多維空間中一些互不相交的區(qū)域，找出包含指定點(diǎn)的區(qū)域。 ? 規(guī)則 f 與包頭 H匹配，當(dāng)且僅當(dāng)每個(gè) H[i]匹配 f[i]。 ? 前綴匹配： f[i]通過一個(gè)前綴指定，若 H[i]與 f[i]表示的前綴匹配，稱 H[i]與 f[i]前綴匹配。 ? 過濾規(guī)則 f ：具有 K個(gè)域，第 i個(gè)域表示為 f[i]。 ? 硬件 CRC指令： ? 5個(gè)時(shí)鐘周期完成計(jì)算。 ? 分支跳轉(zhuǎn)指令：可在 1條指令中完成分支跳轉(zhuǎn)操作。 網(wǎng)絡(luò)處理器中的實(shí)現(xiàn)優(yōu)化 ? 位操作指令 ? POP_COUNT指令：可在 3個(gè)時(shí)鐘周期內(nèi)計(jì)算 32位寄存器中 1的個(gè)數(shù)。 ? 第五層為基于 CRC的哈希表，存儲(chǔ)長(zhǎng)度為 [49, 64]比特的地址前綴。 TrieC樹結(jié)構(gòu) ? 建立 2488816多分支 TrieC樹： ? 根節(jié)點(diǎn)采用 TrieC15/6數(shù)據(jù)結(jié)構(gòu)，存儲(chǔ)長(zhǎng)度為 [1, 24]比特的地址前綴。 ? 64條前綴壓縮成一個(gè)表項(xiàng)，高 18比特作為表項(xiàng)索引，低 6比特用作位向量索引。 前綴擴(kuò)展產(chǎn)生許多冗余 （ 2020:4*::/18, A）和（ 2020:5*::/20, B）擴(kuò)展出來(lái)的表項(xiàng) TrieC的算法思想 ? 具有相同下一跳的前綴項(xiàng)組成一個(gè)數(shù)據(jù)塊，下一跳信息只在表中存儲(chǔ)一次。 ? 根據(jù)統(tǒng)計(jì)結(jié)果及 IPv6地址分配策略，長(zhǎng)度大于 48比特的前綴僅為 5%左右。 ? 基于 TCAM的方法不適用于規(guī)模巨大的表。 ? 規(guī)模更大：大規(guī)模應(yīng)用后，前綴項(xiàng)估計(jì)在 50萬(wàn)條左右。 T C A M 芯片 NextHop索 引表 NextHop映 射表目的I P 地址下一跳地址和端口（ 6） IPv6地址查找 ? IPv6路由表的特點(diǎn)： ? 前綴更長(zhǎng)： IPv6地址長(zhǎng) 128比特。采用流水線技術(shù)可以進(jìn)一步提高查找速度。 ? TCAM適合于查找?guī)ㄅ浞年P(guān)鍵字。 ? 掩碼長(zhǎng)度等于槽長(zhǎng)度，指示哪些比特要和關(guān)鍵字的相應(yīng)比特比較。 ? 處理器提供一個(gè)查找關(guān)鍵字，CAM返回匹配該關(guān)鍵字的一組槽。 Stanford算法的硬件實(shí)現(xiàn) TBL24 TBLlong （ 5）基于 TCAM的地址查找 ? 內(nèi)容可尋址存儲(chǔ)器（ Content Addressable Memory）是一種支持快速搜索和數(shù)據(jù)存儲(chǔ)的存儲(chǔ)機(jī)制，主要用于提高查表速度。 ? 第二層步寬 8比特：少數(shù)情況下需要查找這一層。 （ 4） Stanford算法 ? 據(jù)統(tǒng)計(jì)，因特網(wǎng)中 %的前綴長(zhǎng)度分布在 24或小于 24的范圍內(nèi)。