ip路由查找(存儲版)
【正文】 前提下減少算法的存儲空間。 ? 多分支 Trie的查找過程類似于二進制 Trie。 多分支 Trie的優(yōu)化（ 2） ? 248多分支 trie快速查找算法的硬件實現(xiàn) ? 查找最多只需要兩次訪存；采用硬件流水線技術(shù)，實際上只需要一次訪存的時間。 基于 TCAM的硬件查找 ? TCAM中每一個表項以 地址，掩碼 序偶的形式保存。 ? 基于 TCAM的方法不適用于規(guī)模巨大的表。 ? 每一層節(jié)點的數(shù)據(jù)結(jié)構(gòu)中都有一個標志位用于指示是否需要繼續(xù)查找下一層節(jié)點。每個任務(wù)可用的資源較多，但子任務(wù)間通信負載較高，且子任務(wù)間不易平衡負載。 ? Group B：采用 IPv6路由表生成算法產(chǎn)生，代表理想狀態(tài)的 IPv6路由表。 ? DRAM： TrieC無法在最壞情況下支持 OC192線速。 支持 OC192線速需要的最少線程數(shù) 數(shù)據(jù)分配實驗 ? 單 SRAM通道： 3個微引擎就可以支持 OC192線速，但SRAM通道利用率較高。將無依賴關(guān)系的指令安排在分支指令或線程切換指令附近，以便讓 IXP編譯器用它們填充到這些指令產(chǎn)生的延遲槽中。 任務(wù)切分 ? IXP2800支持兩種任務(wù)切分模式： ? Multiprocessing：包括微引擎內(nèi)的多線程技術(shù)和基于多個微引擎的多線程技術(shù)，易于實現(xiàn)，易于平衡負載，但每個任務(wù)所用的資源不宜過多。 ? 64條前綴壓縮成一個表項，用高 18比特作為新表項的索引，低 6比特用作另一個索引查找位向量。 ? 規(guī)模更大： ? 目前 IPv6尚未廣泛使用， IPv6路由表都很?。ɑ静怀^ 1000個前綴項），但估計的前綴項應(yīng)在 50萬條左右。 ? 路由表規(guī)模很大時，查找效果不好。 ? 一種較自然的做法是根據(jù)實際地址前綴的分布來選擇合適的步寬。 ? 前綴表中的地址前綴必須轉(zhuǎn)換成多分支 Trie查找能夠允許的地址前綴。 ? 例如：前綴 1*的地址范圍可以用前綴 10*和 11*來涵蓋，也可以用前綴 100*、 101*、 110*和 111*來涵蓋。 ? 以上查找方法為基于長度的順序前綴查找，每搜索一步，搜索空間就縮減一半，當縮減為 1時搜索結(jié)束。 ? 轉(zhuǎn)發(fā)表查找要求采用最長前綴匹配查找而不是精確匹配查找。 ? 地址前綴的兩種表示方法： ? 不大于 32比特的比特串跟上一個 *，比如： 1000001001010110* ? 帶點十進制表示加上地址前綴長度，比如： ? 地址聚合（ address aggregation）：連接到同一個網(wǎng)絡(luò)的所有主機，在轉(zhuǎn)發(fā)表中對應(yīng)一個入口，即允許使用前綴來表示一組地址。 無類域間路由（ CIDR）編址方案 ? 摒棄傳統(tǒng)的基于類的地址分配方式，允許使用任意長度的地址前綴，有效提高地址空間的利用率。 ? 處于第 L層的節(jié)點代表了一個地址前 L比特均相同的地址空間，這 L個比特串就是由從根節(jié)點到這個節(jié)點路徑上的 L比特組成。 路徑壓縮 Trie樹 ? 路徑壓縮 Trie樹壓縮單向分支 ? 每個節(jié)點需要維護一個變量，指示下一個需要檢查的比特位 ? 前綴節(jié)點需要保存地址前綴的比特串 路徑壓縮 Trie樹（續(xù)） ? 當二進制 Trie樹中的前綴分布較稀疏時，路徑壓縮算法能夠獲得良好的壓縮效果。 ? 存儲層次設(shè)計 ? 盡量減小查找算法的數(shù)據(jù)結(jié)構(gòu)所占據(jù)的存儲空間，從而可以將數(shù)據(jù)結(jié)構(gòu)
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1