【正文】 ，稱 H[i]與 f[i]前綴匹配。 ? 將高維問題轉(zhuǎn)化為二維乃至一維的問題，降低問題的復(fù)雜度。 ? 缺點：空間復(fù)雜度高，不易更新，只適用于靜態(tài)規(guī)則集。 ? 每個哈希表項為一棵 Grid of Tries，哈希表的索引為相應(yīng)的端口地址和協(xié)議號的某種組合（或函數(shù)）。 ? 當(dāng)某節(jié)點包含的規(guī)則數(shù)超過預(yù)先定義的門限時，節(jié)點進一步被劃分為若干子節(jié)點。 ? 易于并行處理 ? 處于同一階段的預(yù)處理表或交叉乘積表可被并行地索引 ? 處于不同階段的表也可被并行地索引 ? 這些表各自獨立，可分布于不同的存儲單元中 ? 缺點： ? 交叉乘積表占用內(nèi)存空間較多，存儲空間 消耗隨規(guī)則集規(guī)模增大而迅速增大。 指令編碼 ? 5種端口范圍： WC（通配）、 HI（高端）、 LO（低端）、 AR（任意范圍）、 EM（精確匹配）。 ? %的情況下，匹配一對地址的候選范圍可以編碼成一個 64字節(jié)的代碼塊（ X86上一個 cache行大小），僅需訪問內(nèi)存一次。 RFC與 TIC的訪存次數(shù) 4階段 RFC TIC TIC與 RFC的比較 ? 內(nèi)存空間?。? ? TIC最多可比 RFC節(jié)省 97%的存儲空間。 TIC的設(shè)計 ? 第一階段采用 RFC算法，找到匹配一對 源 IP地址，目的 IP地址 的規(guī)則集，實際上得到的是對應(yīng)該規(guī)則集的代碼塊的地址。 ? 每一階段映射稱為一次縮減（ reduction），由多階段映射構(gòu)建的數(shù)據(jù)結(jié)構(gòu)稱為縮減樹。 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維空間。 ? 協(xié)議域的處理： ? 協(xié)議只取 TCP、 UDP和通配（ *）三個值； ? 對于取值為通配的規(guī)則，將一條規(guī)則重復(fù) 3次，分別對應(yīng)TCP、 UDP和其它情況（ OTHER）。 ? 分類時，只需查找一遍目的地址 Trie和一遍源地址Trie，就可以完成規(guī)則匹配。 IP分類問題的復(fù)雜度 ? 假設(shè)不同區(qū)域互不相交，對 N條規(guī)則進行 k（ k3）維分類，計算幾何給出的最好結(jié)果是： ? 空間復(fù)雜度為 O(Nk)時，時間復(fù)雜度為 O(logN)； ? 或者，空間復(fù)雜度為 O(N)時，時間復(fù)雜度為O(logk1N)。 ? 過濾規(guī)則 f ：具有 K個域，第 i個域表示為 f[i]。 ? 第五層為基于 CRC的哈希表，存儲長度為 [49, 64]比特的地址前綴。 ? 根據(jù)統(tǒng)計結(jié)果及 IPv6地址分配策略，長度大于 48比特的前綴僅為 5%左右。采用流水線技術(shù)可以進一步提高查找速度。 Stanford算法的硬件實現(xiàn) TBL24 TBLlong （ 5）基于 TCAM的地址查找 ? 內(nèi)容可尋址存儲器（ Content Addressable Memory）是一種支持快速搜索和數(shù)據(jù)存儲的存儲機制，主要用于提高查表速度。 ? 需要額外的數(shù)據(jù)結(jié)構(gòu)保存原始前綴。 （ 3）多分支 Trie ? 查找的每一步檢查地址的多個比特，以減少樹的高度（訪存次數(shù)）。 ? 若查找過程在一個中間節(jié)點終止，將此節(jié)點標記為非前綴節(jié)點，刪除此節(jié)點的轉(zhuǎn)發(fā)信息。 ? 當(dāng)不再有分支可以選擇時搜索過程結(jié)束，此時被記錄的最長地址前綴就是查找結(jié)果。 ? 查找過程如下： ? 根據(jù) IP地址的前幾位得到該地址所屬的地址類別 ? 根據(jù)地址類別提取目的地址中的網(wǎng)絡(luò)地址部分 ? 查找相應(yīng)的哈希表或進行二分查找 最長地址前綴匹配的困難 ? 轉(zhuǎn)發(fā)表中的目的前綴具有任意的長度，并且不再對應(yīng)地址的網(wǎng)絡(luò)部分，因而前綴長度無法從目的地址本身獲得。 總的性能改進 2 IP路由查找 地址前綴與地址聚合 ? IP地址由兩個部分組成：網(wǎng)絡(luò)地址部分（地址前綴）和主機地址部分。 數(shù)據(jù)包輸入 /輸出 ? 在目前的操作系統(tǒng)中， ? 數(shù)據(jù)包的元數(shù)據(jù)存放在 skb中，有一個指針指向數(shù)據(jù)包實際存放的位置。 服務(wù)器架構(gòu) 硬件平臺 輸入流量 ? 服務(wù)器上安裝了兩塊雙端口 10Gbps網(wǎng)卡。 ? 挑戰(zhàn)：單臺服務(wù)器不可能達到 NR的處理和交換速度。 ? 利用網(wǎng)絡(luò)處理器加速時間關(guān)鍵任務(wù)的處理，具有較高程度的可編程性，但編程困難。 ? 通用處理器的計算能力很強大，存儲資源很豐富，能夠承擔(dān)很復(fù)雜的包處理任務(wù)。 ? RSP處理其它重要任務(wù)，如路由協(xié)議、非 IP流量、網(wǎng)絡(luò)管理等。 ? 快路徑的速度直接影響路由器的性能，一般在網(wǎng)絡(luò)接口上實現(xiàn)，且大多用硬件實現(xiàn)。 ? 優(yōu)點：提高了路由器的端口密度。 ? 實踐發(fā)現(xiàn)，路由緩存在因特網(wǎng)邊緣比較有效，在因特網(wǎng)核心并不奏效： ? 核心路由器見到的目的地址數(shù)量巨大，可導(dǎo)致緩存溢出或查找速度變慢。 ? 特殊服務(wù)： 不屬于核心路由的其它功能，包括數(shù)據(jù)包轉(zhuǎn)換、封裝、流量管理、認證、包過濾等。 ? 與地址前綴對應(yīng)的節(jié)點包含了轉(zhuǎn)發(fā)信息。 第二代：基于總線和多處理器的架構(gòu)（ 1） ? 卸載包轉(zhuǎn)發(fā)、路由緩存和包緩存到 NIC上： ? 減少總線拷貝 ? 減輕 CPU負擔(dān) ? 減少查表時間 ? 缺點： ? 吞吐量依賴流量模式 ? 高速時主路由表查找仍是瓶頸。 使用交換結(jié)構(gòu)代替共享總線 Crossbar交換結(jié)構(gòu) ? 使用 N M 個交叉開關(guān)連接輸入與輸出端口 ? 控制器硬件處理端口競爭 ? 多個端口之間可以并行傳輸，集合吞吐率高 使用轉(zhuǎn)發(fā)數(shù)據(jù)庫（ FIB）代替路由緩存 ? 當(dāng)網(wǎng)絡(luò)拓撲頻繁變化、流量模式高度隨機時，網(wǎng)絡(luò)流量主要通過主 CPU而不是路由緩存轉(zhuǎn)發(fā)。 快路徑 or 慢路徑？ 分布式路由器結(jié)構(gòu)中的功能劃分 Cisco路由器架構(gòu)的演變 ? RSP執(zhí)行以下任務(wù)： ? 基本包交換，使用FIB代替路由緩存。 ? FP：用網(wǎng)絡(luò)處理器實現(xiàn)的轉(zhuǎn)發(fā)路徑。 ? 每一顆 NehalemEX 芯片都與其他 3 顆芯通過QuickPath 點對點相聯(lián)。 ? 性能差距大：軟件路由器的速率只能達到 15Gbps。 ? 路由器中不使用任何集中式組件，任一組件的運行速率不高于 cR（ c為 2或 3）。 服務(wù)器架構(gòu) 軟件環(huán)境 ? Click/Linux ， Click是一個模塊化的軟件路由器。 優(yōu)化措施（ 3） 批處理 ? [3]通過處理來減少包的收發(fā)開銷： ? 網(wǎng)卡驅(qū)動的批處理：驅(qū)動程序每次傳輸 kn個包描述符，減少在 PCIe及 I/O總線上產(chǎn)生的事務(wù)。 ? 核心路由器的轉(zhuǎn)發(fā)表規(guī)模急劇擴大，導(dǎo)致查表時間及內(nèi)存需求增加。 地址查找算法的評價指標 ? 查找速度 ? 存儲空間 ? 預(yù)處理和更新速度 ? 算法實現(xiàn)的靈活性（同時具有硬件和軟件實現(xiàn)方式） ? 算法的可擴展性（路由表規(guī)模， IPv6） （ 1）二元查找樹 Trie ? 采用二叉樹結(jié)構(gòu)，通過前綴中每一位的值決定樹的分支。 ? 若查找過程在一個中間節(jié)點終止，將此節(jié)點標記為前綴節(jié)點，并在此中間節(jié)點中加入前綴轉(zhuǎn)發(fā)信息。例如