ip路由查找-全文預(yù)覽
【正文】 000hash tables with marker前綴范圍查找 任何地址區(qū)域所對應(yīng)的最長前綴應(yīng)該是包含此區(qū)域的前綴中范圍最窄的那一項(xiàng)。 多分支 Trie的優(yōu)化（ 2） ? 248多分支 trie快速查找算法的硬件實(shí)現(xiàn) ? 查找最多只需要兩次訪存；采用硬件流水線技術(shù)，實(shí)際上只需要一次訪存的時(shí)間。 可變步寬與固定步寬的多分支 Trie樹 多分支 Trie例 1 多分支 Trie例 2 在地址擴(kuò)展過程中，如果擴(kuò)展的地址前綴與原來的地址前綴沖突，應(yīng)保留原來的地址前綴。 ? 多分支 Trie的查找過程類似于二進(jìn)制 Trie。 ? 同一層中不同子樹的步寬可以相同（固定步寬多分支 Trie），也可以不同（可變步寬多分支 Trie）。 查找算法使用的輔助策略（ 2） ? 獨(dú)立前綴轉(zhuǎn)化 ? 將地址前綴集轉(zhuǎn)化為一組不相交的前綴集 ? 所有的前綴節(jié)點(diǎn)都出現(xiàn)在葉子節(jié)點(diǎn) 查找算法使用的輔助策略（ 3） ? 壓縮技術(shù) ? 壓縮前綴擴(kuò)展造成的信息冗余 ? 從壓縮數(shù)據(jù)中恢復(fù)原有信息不應(yīng)過于復(fù)雜 ? 優(yōu)化技術(shù)的應(yīng)用 ? 在滿足一定約束條件的前提下找到最佳的前綴集，比如在滿足查找速度的前提下減少算法的存儲空間。而對于同樣的前綴表，二進(jìn)制Trie樹的最大高度為 30，平均高度為 22。 ? 刪除一個(gè)地址前綴 ? 以 該前綴項(xiàng)為關(guān)鍵字在 Trie樹中進(jìn)行查找； ? 若查找過程在一個(gè)中間節(jié)點(diǎn)終止，將此節(jié)點(diǎn)標(biāo)記為非前綴節(jié)點(diǎn)，刪除此節(jié)點(diǎn)的轉(zhuǎn)發(fā)信息； ? 若查找過程終止于葉子節(jié)點(diǎn)，除了刪除該節(jié)點(diǎn)之外，還需要根據(jù)情況刪除其它一些內(nèi)部節(jié)點(diǎn) 。 ? 當(dāng)遇到那些對應(yīng)地址前綴的中間節(jié)點(diǎn)時(shí)，將此地址前綴記錄為目前為止找到的最長地址前綴。 地址查找算法的評價(jià)標(biāo)準(zhǔn) ? 查找速度 ? 存儲空間 ? 預(yù)處理和更新速度 ? 算法實(shí)現(xiàn)的靈活性（同時(shí)具有硬件和軟件實(shí)現(xiàn)方式） ? 算法的可擴(kuò)展性（路由表規(guī)模， IPv6） 經(jīng)典的 IP地址查找算法 ? 線性表查找 ? 二進(jìn)制 Trie樹（ Binary Trie） ? 路徑壓縮 Trie樹（ pathpressed Trie） 二進(jìn)制 Trie樹 ? 采用基于樹的數(shù)據(jù)結(jié)構(gòu)，通過前綴中每一位的值來決定樹的分支。 基于類的地址查找 ? 轉(zhuǎn)發(fā)表中的前綴被組織成三張表（分別對應(yīng) A、 B、 C三類地址前綴），地址查找就是在對應(yīng)的轉(zhuǎn)發(fā)表中進(jìn)行精確匹配查找。 ? 核心路由器的轉(zhuǎn)發(fā)表規(guī)模急劇擴(kuò)大，導(dǎo)致查表時(shí)間及內(nèi)存需求增加。IP路由查找 主要內(nèi)容 ? 路由查找問題的產(chǎn)生背景 ? 典型的 IPv4路由查找算法 ? 基于 IXP2800的高速 IPv6路由查找算法及實(shí)現(xiàn) 參考文獻(xiàn) ? Survey and Taxonomy of IP Address Lookup Algorithms. IEEE Network, 2020. ? Highperformance IPv6 Forwarding Algorithm for Multicore and Multithreaded Network Processors. In Proceedings of PPoPP’06, 2020. 地址前綴與地址聚合 ? IP編址方案最初使用一個(gè)簡單的二層結(jié)構(gòu)：上層為網(wǎng)絡(luò)，下層為主機(jī)。 轉(zhuǎn)發(fā)表舉例 基于類的編址方案 基于
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1