【正文】 ? 查找相應(yīng)的哈希表或進行二分查找 最長地址前綴匹配的困難 ? 轉(zhuǎn)發(fā)表中的目的前綴具有任意的長度，并且不再對應(yīng)地址的網(wǎng)絡(luò)部分，因而前綴長度無法從目的地址本身獲得。 ? 處于第 L層的節(jié)點代表了一個地址前 L比特均相同的地址空間，這 L個比特串就是由從根節(jié)點到這個節(jié)點路徑上的L比特組成。 ? 當(dāng)不再有分支可以選擇時搜索過程結(jié)束，此時被記錄的最長地址前綴就是查找結(jié)果。例如，插入前綴 01*。 ? 若查找過程在一個中間節(jié)點終止，將此節(jié)點標(biāo)記為非前綴節(jié)點，刪除此節(jié)點的轉(zhuǎn)發(fā)信息。 （ 2）路徑壓縮 Trie樹 ? 路徑壓縮 Trie樹壓縮單孩子分支 ? 每個節(jié)點需要維護一個變量，指示下一個需要檢查的比特位 ? 前綴節(jié)點需要保存地址前綴的比特串 路徑壓縮 Trie樹（續(xù)） ? 當(dāng)二元 Trie樹中的前綴分布較稀疏時，路徑壓縮算法能夠獲得良好的壓縮效果。 （ 3）多分支 Trie ? 查找的每一步檢查地址的多個比特，以減少樹的高度（訪存次數(shù)）。 多分支 Trie的查找和更新 ? 多分支 Trie的查找過程類似于二分支 Trie。 ? 需要額外的數(shù)據(jù)結(jié)構(gòu)保存原始前綴。 （ 4） Stanford算法 ? 據(jù)統(tǒng)計，因特網(wǎng)中 %的前綴長度分布在 24或小于 24的范圍內(nèi)。 Stanford算法的硬件實現(xiàn) TBL24 TBLlong （ 5）基于 TCAM的地址查找 ? 內(nèi)容可尋址存儲器（ Content Addressable Memory）是一種支持快速搜索和數(shù)據(jù)存儲的存儲機制，主要用于提高查表速度。 ? 掩碼長度等于槽長度，指示哪些比特要和關(guān)鍵字的相應(yīng)比特比較。采用流水線技術(shù)可以進一步提高查找速度。 ? 規(guī)模更大：大規(guī)模應(yīng)用后，前綴項估計在 50萬條左右。 ? 根據(jù)統(tǒng)計結(jié)果及 IPv6地址分配策略，長度大于 48比特的前綴僅為 5%左右。 ? 64條前綴壓縮成一個表項，高 18比特作為表項索引，低 6比特用作位向量索引。 ? 第五層為基于 CRC的哈希表，存儲長度為 [49, 64]比特的地址前綴。 ? 分支跳轉(zhuǎn)指令：可在 1條指令中完成分支跳轉(zhuǎn)操作。 ? 過濾規(guī)則 f ：具有 K個域，第 i個域表示為 f[i]。 ? 規(guī)則 f 與包頭 H匹配，當(dāng)且僅當(dāng)每個 H[i]匹配 f[i]。 IP分類問題的復(fù)雜度 ? 假設(shè)不同區(qū)域互不相交，對 N條規(guī)則進行 k（ k3）維分類，計算幾何給出的最好結(jié)果是： ? 空間復(fù)雜度為 O(Nk)時，時間復(fù)雜度為 O(logN)； ? 或者，空間復(fù)雜度為 O(N)時，時間復(fù)雜度為O(logk1N)。 ? 第一級 Trie中的每個前綴節(jié)點（即規(guī)則集中存在對應(yīng)的項），有指針指向其第二級 Trie。 ? 分類時，只需查找一遍目的地址 Trie和一遍源地址Trie，就可以完成規(guī)則匹配。 ? 查找過程： ? 先對目的地址做最長前綴匹配； ? 在所指向的源地址 Trie上，根據(jù)包頭的源地址沿著 0、1指針（或者轉(zhuǎn)發(fā)指針）盡可能地前進。 ? 協(xié)議域的處理： ? 協(xié)議只取 TCP、 UDP和通配（ *）三個值； ? 對于取值為通配的規(guī)則，將一條規(guī)則重復(fù) 3次，分別對應(yīng)TCP、 UDP和其它情況（ OTHER）。 ? 根據(jù) Grid of Tries的查找方法找到最小代價規(guī)則 ? 取所有哈希表中的最好結(jié)果，即為最佳匹配的規(guī)則。 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é)點包含整個 d維空間。 ? 缺點： ? 預(yù)處理時間長，比一些快速包分類算法慢。 ? 每一階段映射稱為一次縮減（ reduction），由多階段映射構(gòu)建的數(shù)據(jù)結(jié)構(gòu)稱為縮減樹。 ? 前綴查找是訪存密集的操作，范圍查找是計算密集的操作，將兩者分開處理有助于提高查找的效率。 TIC的設(shè)計 ? 第一階段采用 RFC算法，找到匹配一對 源 IP地址，目的 IP地址 的規(guī)則集，實際上得到的是對應(yīng)該規(guī)則集的代碼塊的地址。 ? 采用 CISC風(fēng)格的指令，總共需要約 5 5 2=50種操作符。 RFC與 TIC的訪存次數(shù) 4階段 RFC TIC TIC與 RFC的比較 ? 內(nèi)存空間?。? ? TIC最多可比 RFC節(jié)省 97%的存儲空間。 主要參考文獻 [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。 ? %的情況下，匹配一對地址的候選范圍可以編碼成一個 64字節(jié)的代碼塊（ X86上一個 cache行大?。瑑H需訪問內(nèi)存一次。 源端口和目的端口的分布 ? 12字節(jié)的指令非常少見。 指令編碼 ? 5種端口范圍： WC（通配）、 HI（高端）、 LO（低端）、 AR（任意范圍）、 EM（精確匹配）。 TIC算法 ? 算法要點： ? 將匹配一對 源 IP地址，目的 IP地址 的過程與匹配其余 3個域的過程分開，前者使用適合前綴查找的算法，后者使用適合范圍查找的算法。 ? 易于并行處理 ? 處于同一階段的預(yù)處理表或交叉乘積表可被并行地索引 ? 處于不同階段的表也可被并行地索引 ? 這些表各自獨立，可分布于不同的存儲單元中 ? 缺點： ? 交叉乘積表占用內(nèi)存空間較多，存儲空間 消耗隨規(guī)則集規(guī)模增大而迅速增大。 ? 從 S位比特串直接映射到 eqID需要消耗巨大的內(nèi)存空間。 ? 當(dāng)某節(jié)點包含的規(guī)則數(shù)超過預(yù)先定義的門限時，節(jié)點進一步被劃分為若干子節(jié)點。 ? 算法復(fù)雜度分析： ? N位與操作的時間復(fù)雜度為 O(N)，若一個字長為 W比特，最壞情況下與操作需要（ N*d） /W次內(nèi)存訪問。 ? 每個哈希表項為一棵 Grid of Tries，哈希表的索引為相應(yīng)的端口地址和協(xié)議號的某種組合（或函數(shù)）。 ? 特點：不需回溯， 內(nèi)存空間小，但更新困難。 ? 缺點：空間復(fù)雜度高，不易更新，只適用于靜態(tài)規(guī)則集。 ? 對這個節(jié)點及其父節(jié)點所指向的所有第二級 Trie進行匹配查找，得到優(yōu)先級最高的規(guī)則。 ? 將高維問題轉(zhuǎn)化為二維乃至一維的問題，降低問題的復(fù)雜度。 IP分類與多維空間的點定位 ? 多維空間的點定位問題： ? 給定多維空間中一些互不相交的區(qū)域，找出包含指定點的區(qū)域。 ? 前綴匹配： f[i]通過一個前綴指定，若 H[i]與 f[i]表示的前綴匹配，稱 H[i]與 f[i]前