ip路由查找(參考版)
2024-09-05 14:46本頁面
【正文】 任務(wù)切分 ? Contextpipelining的任務(wù)切分： ? ME1和 ME2負責(zé)第一、第二層表的查找 ? ME3和 ME4負責(zé)第三、四、五層表的查找 延遲槽填充帶來的性能改善 線程同步（維持包序）帶來的性能損失 總結(jié) ? 盡量壓縮算法所需的內(nèi)存空間 ? 合理分配任務(wù)和分布數(shù)據(jù) ? 根據(jù)算法特性選擇合適的位操作指令 ? 充分利用各種延遲隱藏技術(shù) ? 在難以平衡各個子任務(wù)的工作負載時使用 multiprocessing編程模式 。 ? DRAM： TrieC無法在最壞情況下支持 OC192線速。 支持 OC192線速需要的最少線程數(shù) 數(shù)據(jù)分配實驗 ? 單 SRAM通道： 3個微引擎就可以支持 OC192線速，但SRAM通道利用率較高。 并行查找時的相對加速比 ? 使用 69字節(jié)的最小 IPv6分組進行實驗。 TrieC算法的平均訪存次數(shù) ? TrieC算法的平均訪存次數(shù)與路由表前綴長度分布有關(guān)，而與規(guī)模無關(guān)。 ? Group B：采用 IPv6路由表生成算法產(chǎn)生，代表理想狀態(tài)的 IPv6路由表。將無依賴關(guān)系的指令安排在分支指令或線程切換指令附近，以便讓 IXP編譯器用它們填充到這些指令產(chǎn)生的延遲槽中。 IXP2800使用一條 I/O指令最多可以訪問 64個字節(jié)（ SRAM），所以 TrieC結(jié)構(gòu)的大小都限制在 64個字節(jié)內(nèi)。 長延遲隱藏 ? TrieC算法是實現(xiàn)需要頻繁進行 I/O操作， I/O操作是典型的長延遲操作，隱藏訪存延遲的手段包括： ? 多線程技術(shù)是隱藏長延遲的主要手段。每個任務(wù)可用的資源較多，但子任務(wù)間通信負載較高，且子任務(wù)間不易平衡負載。 任務(wù)切分 ? IXP2800支持兩種任務(wù)切分模式： ? Multiprocessing：包括微引擎內(nèi)的多線程技術(shù)和基于多個微引擎的多線程技術(shù)，易于實現(xiàn)，易于平衡負載，但每個任務(wù)所用的資源不宜過多。 數(shù)據(jù)分配 ? IXP2800具有 4個可并行訪問的 SRAM控制器和 3個 DRAM控制器，每個 DRAM控制器支持 4個可交錯訪問的存儲器 bank。 ? 分支跳轉(zhuǎn)指令：可以在 1條指令中完成分支跳轉(zhuǎn)操作，而在 RISC體系結(jié)構(gòu)上通常至少需要 3條指令。 ? 每一層節(jié)點的數(shù)據(jù)結(jié)構(gòu)中都有一個標志位用于指示是否需要繼續(xù)查找下一層節(jié)點。 ? 64條前綴壓縮成一個表項，用高 18比特作為新表項的索引，低 6比特用作另一個索引查找位向量。 ? 根據(jù) IPv6地址前綴的分布特點，構(gòu)造查找步寬為 2488816的五層多分支 TrieC樹，限制最壞情況下路由查找的訪存次數(shù)。 TrieC算法設(shè)計思想 ? 采用改進的 Stanford算法 ? 保留 Stanford算法高速查找、易于更新及硬件實現(xiàn)復(fù)雜度低等優(yōu)點，但通過壓縮技術(shù)使得算法對存儲空間的需求量在可接受的范圍內(nèi)。 ? 基于 TCAM的方法不適用于規(guī)模巨大的表。 ? 規(guī)模更大： ? 目前 IPv6尚未廣泛使用， IPv6路由表都很?。ɑ静怀^ 1000個前綴項），但估計的前綴項應(yīng)在 50萬條左右。 ? 容量小，代價高，功耗大，更新復(fù)雜（關(guān)鍵字需要排序）。 ? 查找速度快，實現(xiàn)簡單。 基于 TCAM的硬件查找 ? TCAM中每一個表項以 地址，掩碼 序偶的形式保存。 ? 路由表規(guī)模很大時
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1