【文章內(nèi)容簡(jiǎn)介】 需要維護(hù)一個(gè)變量，指示下一個(gè)需要檢查的比特位 ? 前綴節(jié)點(diǎn)需要保存地址前綴的比特串 路徑壓縮 Trie樹（續(xù)） ? 當(dāng)二元 Trie樹中的前綴分布較稀疏時(shí)，路徑壓縮算法能夠獲得良好的壓縮效果。 ? 二元 Trie樹和路徑壓縮 Trie樹的不足是查找過(guò)程需要大量的存儲(chǔ)器訪問(wèn)操作。 ? 研究表明，對(duì)于一個(gè)具有 47113個(gè)前綴表項(xiàng)的典型骨干網(wǎng)路由器，使用 BSD Trie會(huì)創(chuàng)建 93304個(gè)節(jié)點(diǎn)，樹的最大高度為 26，平均高度為 20。而對(duì)于同樣的前綴表，二元 Trie樹的最大高度為 30，平均高度為 22。 （ 3）多分支 Trie ? 查找的每一步檢查地址的多個(gè)比特，以減少樹的高度（訪存次數(shù)）。 ? 查找步寬：每次檢查的比特?cái)?shù)稱為查找步寬。 ? 根據(jù)同一層中不同子樹的步寬是否相同，分為： ? 固定步寬多分支 Trie ? 可變步寬多分支 Trie 可變步寬與固定步寬的多分支 Trie樹 前綴擴(kuò)展 ? 前綴表中的地址前綴必須轉(zhuǎn)換成多分支 Trie查找允許的地址前綴。 前綴擴(kuò)展例 2 在前綴擴(kuò)展過(guò)程中，如果擴(kuò)展的地址前綴與原來(lái)的地址前綴沖突，應(yīng)保留原來(lái)的地址前綴。 多分支 Trie的查找和更新 ? 多分支 Trie的查找過(guò)程類似于二分支 Trie。 ? 多分支 Trie可以看成是由單層 subtrie構(gòu)成的樹，在每個(gè) subtrie所做的前綴擴(kuò)展是局部的。 ? 多分支 Trie的更新過(guò)程比二分支 Trie復(fù)雜： ? 插入一個(gè)前綴時(shí)，需要找到相應(yīng)的 subtrie，對(duì)前綴進(jìn)行擴(kuò)展，然后插入。 ? 刪除一個(gè)前綴時(shí)，需要?jiǎng)h除所有擴(kuò)展的前綴。 ? 需要額外的數(shù)據(jù)結(jié)構(gòu)保存原始前綴。 多分支 Trie的優(yōu)化 ? 步寬的選擇 ? 步寬的選擇是在算法查找速度、存儲(chǔ)空間和更新復(fù)雜度之間的折衷。 ? 一種較自然的做法是根據(jù)二分支 Trie的 地址前綴分布來(lái)選擇合適的步寬。 ? 使用某種優(yōu)化策略，使在搜索深度固定的情況下整個(gè)樹的存儲(chǔ)空間最小。 （ 4） Stanford算法 ? 據(jù)統(tǒng)計(jì)，因特網(wǎng)中 %的前綴長(zhǎng)度分布在 24或小于 24的范圍內(nèi)。 ? 提出一種 248的多分支 Trie快速查找算法： ? 第一層步寬 24比特：絕大多數(shù)情況下訪問(wèn)這一層就可以找到最佳匹配前綴。 ? 第二層步寬 8比特：少數(shù)情況下需要查找這一層。 ? 查找速度快，要求較大的存儲(chǔ)空間。 Stanford算法的硬件實(shí)現(xiàn) TBL24 TBLlong （ 5）基于 TCAM的地址查找 ? 內(nèi)容可尋址存儲(chǔ)器（ Content Addressable Memory）是一種支持快速搜索和數(shù)據(jù)存儲(chǔ)的存儲(chǔ)機(jī)制，主要用于提高查表速度。 ? CAM被組織成一個(gè)二維陣列，每一行長(zhǎng)度固定，稱為一個(gè)槽。 ? 處理器提供一個(gè)查找關(guān)鍵字，CAM返回匹配該關(guān)鍵字的一組槽。 CAM的組織 TCAM（三態(tài) CAM） ? 每個(gè) TCAM條目存儲(chǔ)一個(gè)二進(jìn)制數(shù)和一個(gè)掩碼。 ? 掩碼長(zhǎng)度等于槽長(zhǎng)度，指示哪些比特要和關(guān)鍵字的相應(yīng)比特比較。 ? 若有多個(gè)條目匹配，選擇地址最低的條目。 ? TCAM適合于查找?guī)ㄅ浞年P(guān)鍵字。 （ 5）基于 TCAM的地址查找 ? 優(yōu)點(diǎn)：查找速度快，實(shí)現(xiàn)簡(jiǎn)單。采用流水線技術(shù)可以進(jìn)一步提高查找速度。 ? 缺點(diǎn)： TCAM容量小、代價(jià)高、功耗大、更新復(fù)雜（關(guān)鍵字需要排序）。 T C A M 芯片 NextHop索 引表 NextHop映 射表目的I P 地址下一跳地址和端口（ 6） IPv6地址查找 ? IPv6路由表的特點(diǎn)： ? 前綴更長(zhǎng)： IPv6地址長(zhǎng) 128比特。 ? 由路由器轉(zhuǎn)發(fā)的一類地址（可聚合的全局單播地址），前 3比特（格式前綴）總是 001，最后 64比特用于標(biāo)識(shí)網(wǎng)絡(luò)接口。 ? 規(guī)模更大：大規(guī)模應(yīng)用后，前綴項(xiàng)估計(jì)在 50萬(wàn)條左右。 ? IPv4地址查找算法不能直接應(yīng)用于 IPv6： ? 基于 Trie的算法訪存次數(shù)很多，或內(nèi)存需求很大。 ? 基于 TCAM的方法不適用于規(guī)模巨大的表。 采用多分支 Trie樹構(gòu)造查找表 [5] ? 采用改進(jìn)的 Stanford算法，保留其查找快速、易于更新及硬件實(shí)現(xiàn)容易等優(yōu)點(diǎn)，并壓縮算法所需的存儲(chǔ)空間。 ? 根據(jù)統(tǒng)計(jì)結(jié)果及 IPv6地址分配策略，長(zhǎng)度大于 48比特的前綴僅為 5%左右。 ? 構(gòu)造查找步寬為 2488816的五層多分支 Trie樹，限制最壞情況下路由查找的訪存次數(shù)。 前綴擴(kuò)展產(chǎn)生許多冗余 （ 2020:4*::/18, A）和（ 2020:5*::/20, B）擴(kuò)展出來(lái)的表項(xiàng) TrieC的算法思想 ? 具有相同下一跳的前綴項(xiàng)組成一個(gè)數(shù)據(jù)塊，下一跳信息只在表中存儲(chǔ)一次。 ? 采用一個(gè)位向量記錄每個(gè)數(shù)據(jù)塊的起始位置。 ? 64條前綴壓縮成一個(gè)表項(xiàng)，高 18比特作為表項(xiàng)索引，低 6比特用作位向量索引。 ? 統(tǒng)計(jì)位向量中從起始位置到當(dāng)前位置 “ 1”的個(gè)數(shù)，作為數(shù)組下標(biāo)。 TrieC樹結(jié)構(gòu) ? 建立 2488816多分支 TrieC樹： ? 根節(jié)點(diǎn)采用 TrieC15/6數(shù)據(jù)結(jié)構(gòu)，存儲(chǔ)長(zhǎng)度為 [1, 24]比特的地址前綴。 ? 第二層至第四層均采用 TrieC4/4數(shù)據(jù)結(jié)構(gòu)，分別存儲(chǔ)長(zhǎng)度為 [25, 32]、 [33, 40]、 [41, 48]比特的地址前綴。 ? 第五層為基于 CRC的哈希表，存儲(chǔ)長(zhǎng)度為 [49, 64]比特的地址前綴。 ? 每一層節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)中都有一個(gè)標(biāo)志位用于指示是否需要繼續(xù)查找下一層節(jié)點(diǎn)。 網(wǎng)絡(luò)處理器中的實(shí)現(xiàn)優(yōu)化 ? 位操作指令 ? POP_COUNT指令：可在 3個(gè)時(shí)鐘周期內(nèi)計(jì)算 32位寄存器中 1的個(gè)數(shù)。在 RISC結(jié)構(gòu)上通常需要 100多條指令。 ? 分支跳轉(zhuǎn)指令：可在 1條指令中完成分支跳轉(zhuǎn)操作。在RISC體系結(jié)構(gòu)上通常至少需要 3條指令。 ? 硬件 CRC指令： ? 5個(gè)時(shí)鐘周期完成計(jì)算。 ? 數(shù)據(jù)分布 ? TrieC表按照 TrieC樹的層次存儲(chǔ)在四個(gè) SRAM控制器中 3 數(shù)據(jù)包分類 包分類的術(shù)語(yǔ) ? 包頭 H：有 K個(gè)域的實(shí)體，第 i個(gè)域表示為一個(gè)比特串 H[i]。 ? 過(guò)濾規(guī)則 f ：具有 K個(gè)域，第 i個(gè)域表示為 f[i]。 ? 與每個(gè) f[i]相關(guān)聯(lián)有一個(gè)匹配方式，可以是： ? 精確匹配： f[i]用一個(gè)值表示，若 H[i]=f[i]，稱 H[i]與 f[i]精確匹配。 ? 前綴匹配： f[i]通過(guò)一個(gè)前綴指定，若 H[i]與 f[i]表示的前綴匹配，稱 H[i]與 f[i]前綴匹配。 ? 范圍匹配： f[i]通過(guò)一個(gè)范圍 [val1, val2]指定，若滿足val1≤ H[i] ≤ val2，稱 H[i]與 f[i]范圍匹配。 ? 規(guī)則 f 與包頭 H匹配，當(dāng)且僅當(dāng)每個(gè) H[i]匹配 f[i]。 IP分類問(wèn)題的定義 ? 給定一個(gè)具有 N條規(guī)則的規(guī)則集 F，與每條規(guī)則 f 相聯(lián)系有一個(gè)代價(jià)函數(shù) cost(f)，給定一個(gè)包頭 H，最佳規(guī)則匹配問(wèn)題為在 F 中查找滿足下列條件的規(guī)則 fbest： ? Fbest 匹配 H ? 在 F 中不存在其它的規(guī)則 f ，使得 f 匹配 H且滿足 cost(f)cost(fbest)。 IP分類與多維空間的點(diǎn)定位 ? 多維空間的點(diǎn)定位問(wèn)題： ? 給定多維空間中一些互不相交的區(qū)域，找出包含指定點(diǎn)的區(qū)域。 ? IP分類問(wèn)題與多維空間中的點(diǎn)定位問(wèn)題相似： ? 每條規(guī)則對(duì)應(yīng)多維空間中的一個(gè)