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