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