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