ip路由查找-資料下載頁
2025-08-23 14:46本頁面
【導(dǎo)讀】路由查找問題的產(chǎn)生背景?；贗XP2800的高速IPv6路由查找算法及實現(xiàn)。IP編址方案最初使用一個簡單的二層結(jié)構(gòu)：上層為網(wǎng)絡(luò)，這個分層結(jié)構(gòu)反映在IP地址上，就是IP地址由兩個部分組。地址前綴的兩種表示方法：。核心路由器的轉(zhuǎn)發(fā)表規(guī)模急劇擴(kuò)大，導(dǎo)致查表時。間及內(nèi)存需求增加。摒棄傳統(tǒng)的基于類的地址分配方式，允許使用任。意長度的地址前綴，有效提高地址空間的利用率。允許任意地、遞歸地進(jìn)行地址聚合，減少轉(zhuǎn)發(fā)表。中的入口數(shù)目，有效解決路由表爆炸的問題。根據(jù)IP地址的前幾位得到該地址所屬的地址類別。查找相應(yīng)的哈希表或進(jìn)行二分查找。轉(zhuǎn)發(fā)表查找要求采用最長前綴匹配查找而不是精。處于第L層的節(jié)點代表。以該前綴項為關(guān)鍵字在Trie樹中進(jìn)行查找；度為26，平均高度為20。Trie樹的最大高度為30，平均高度為22。前綴擴(kuò)展的目的是為了獲得一組長度差異較小的前。查找步寬為k的多分支Trie樹，每個節(jié)點的最大分支數(shù)為2k。需要額外的數(shù)據(jù)結(jié)構(gòu)保存原始前綴。
【正文】 式： ? Multiprocessing：包括微引擎內(nèi)的多線程技術(shù)和基于多個微引擎的多線程技術(shù)，易于實現(xiàn)，易于平衡負(fù)載，但每個任務(wù)所用的資源不宜過多。 ? Contextpipelining：將一個任務(wù)切分成若干個子任務(wù)分配到多個微引擎上執(zhí)行，子任務(wù)之間通過鄰居環(huán)或 Scratch ring連接形成流水線。每個任務(wù)可用的資源較多，但子任務(wù)間通信負(fù)載較高，且子任務(wù)間不易平衡負(fù)載。 ? 實驗了 multiprocessing、 Contextpipelining和混合三種模式，發(fā)現(xiàn) multiprocessing模式更適合 TrieC算法的實現(xiàn)。 長延遲隱藏 ? TrieC算法是實現(xiàn)需要頻繁進(jìn)行 I/O操作， I/O操作是典型的長延遲操作，隱藏訪存延遲的手段包括： ? 多線程技術(shù)是隱藏長延遲的主要手段。 ? I/O向量化：訪問存儲器中連續(xù)存儲的內(nèi)容可以通過一條 I/O指令來完成。 IXP2800使用一條 I/O指令最多可以訪問 64個字節(jié)（ SRAM），所以 TrieC結(jié)構(gòu)的大小都限制在 64個字節(jié)內(nèi)。 ? I/O交錯（延遲槽填充）：在 IXP2800上，分支指令和線程切換指令都會導(dǎo)致 1個或者多個延遲槽。將無依賴關(guān)系的指令安排在分支指令或線程切換指令附近，以便讓 IXP編譯器用它們填充到這些指令產(chǎn)生的延遲槽中。 TrieC算法對表空間的壓縮性能 ? Group A：參考 CERNET、 6Bone、 6Net和 Telstra的 IPv6路由表前綴長度分布而生成，代表了目前為止實際的 IPv6路由表。 ? Group B：采用 IPv6路由表生成算法產(chǎn)生，代表理想狀態(tài)的 IPv6路由表。 ? Group C：由 Group A和 Group B的算術(shù)平均生成。 TrieC算法的平均訪存次數(shù) ? TrieC算法的平均訪存次數(shù)與路由表前綴長度分布有關(guān)，而與規(guī)模無關(guān)。 ? Group B中超過 70%的前綴的長度位于 4148比特之間，匹配這部分前綴的 IPv6地址必須搜索到 TrieC的第四級。 并行查找時的相對加速比 ? 使用 69字節(jié)的最小 IPv6分組進(jìn)行實驗。 ? OC192線速意味著轉(zhuǎn)發(fā)速度至少要達(dá)到 。 支持 OC192線速需要的最少線程數(shù) 數(shù)據(jù)分配實驗 ? 單 SRAM通道： 3個微引擎就可以支持 OC192線速，但SRAM通道利用率較高。 ? 4 SRAM通道： 2個微引擎可獲得 OC192線速，且 SRAM通道利用率只有 15%左右。 ? DRAM： TrieC無法在最壞情況下支持 OC192線速。 ? 混合 SRAM/DRAM：第一級節(jié)點存儲在 SRAM中，其它節(jié)點存儲在 DRAM中，最壞情況下 4個微引擎可以達(dá)到 OC192線速，但 DRAM 通道利用率非常高，實際情況下無法使用。 任務(wù)切分 ? Contextpipelining的任務(wù)切分： ? ME1和 ME2負(fù)責(zé)第一、第二層表的查找 ? ME3和 ME4負(fù)責(zé)第三、四、五層表的查找 延遲槽填充帶來的性能改善 線程同步（維持包序）帶來的性能損失 總結(jié) ? 盡量壓縮算法所需的內(nèi)存空間 ? 合理分配任務(wù)和分布數(shù)據(jù) ? 根據(jù)算法特性選擇合適的位操作指令 ? 充分利用各種延遲隱藏技術(shù) ? 在難以平衡各個子任務(wù)的工作負(fù)載時使用 multiprocessing編程模式
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1