ip路由查找(編輯修改稿)
2024-10-07 14:46 本頁面
【文章內(nèi)容簡介】 rie查找能夠允許的地址前綴。 圖 ? 多分支 Trie樹的深度有很大縮減，因而提高了查找效率。 ? 多分支 Trie的查找過程類似于二進制 Trie。 ? 多分支 Trie的更新過程比二進制 Trie復(fù)雜： ? 插入一個前綴時，需要找到相應(yīng)的 subtrie，對前綴進行擴展，然后插入。 ? 刪除一個前綴時，需要刪除所有擴展的前綴。 ? 需要額外的數(shù)據(jù)結(jié)構(gòu)保存原始前綴。 可變步寬與固定步寬的多分支 Trie樹 多分支 Trie例 1 多分支 Trie例 2 在地址擴展過程中，如果擴展的地址前綴與原來的地址前綴沖突，應(yīng)保留原來的地址前綴。 多分支 Trie的優(yōu)化（ 1） ? 步寬的選擇 ? 步寬的選擇是在算法查找速度、存儲空間和更新復(fù)雜度之間的折衷。 ? 一種較自然的做法是根據(jù)實際地址前綴的分布來選擇合適的步寬。 ? 使用某種優(yōu)化策略，使在搜索深度固定的情況下整個樹的存儲空間最小。 多分支 Trie的優(yōu)化（ 2） ? 248多分支 trie快速查找算法的硬件實現(xiàn) ? 查找最多只需要兩次訪存；采用硬件流水線技術(shù)，實際上只需要一次訪存的時間。 ? 算法要求的內(nèi)存空間比較大。 TBL24 TBLlong 多分支 Trie的優(yōu)化（ 3） ? 壓縮 ? 在前綴擴展的過程中，前綴的轉(zhuǎn)發(fā)信息被擴展到了 trie樹的多個連續(xù)節(jié)點中，造成大量的信息冗余。 ? 壓縮因前綴擴展造成的大量冗余信息，減少算法占用的內(nèi)存空間。 基于前綴長度的二分查找 01011100110011011110111101000hash tables01011100110 marker111 marker010 marker11001101111011110100 marker01000hash tables with marker前綴范圍查找 任何地址區(qū)域所對應(yīng)的最長前綴應(yīng)該是包含此區(qū)域的前綴中范圍最窄的那一項。 地址區(qū)間的二分查找樹 ? 最長前綴匹配查找變成在左端點集合中尋找離目的地址最近的左端點。 ? 路由表規(guī)模很大時，查找效果不好。 ? 更新性能較差。 基于 TCAM的硬件查找 ? TCAM中每一個表項以 地址，掩碼 序偶的形式保存。 ? TCAM在所有匹配的表項中選取地址最低的表項作為最后的結(jié)果，所以必須將前綴較長的關(guān)鍵字表項存儲在低地址。 ? 查找速度快，實現(xiàn)簡單。完成一次查找只需三步操作，采用流水線技術(shù)可以進一步提高查找速度。 ? 容量小，代價高，功耗大，更新復(fù)雜（關(guān)鍵字需要排序）。 T C A M 芯片 NextHop索 引表 NextHop映 射表目的I P 地址下一跳地址和端口IPv6地址查找的困難 ? 前綴更長： ? IPv6地址長度為 128比特，路由器只轉(zhuǎn)發(fā) Aggregatable Global Unicast Address，這類地址的前 3個比特總為 001，且最后 64比特用于標識網(wǎng)絡(luò)接口。 ? 規(guī)模更大： ? 目前 IPv6尚未廣泛使用， IPv6路由表都很?。ɑ静怀^ 1000個前綴項），但估計的前綴項應(yīng)在 50萬條左右。 ? IPv4路由查找算法不能直接應(yīng)用于 IPv6： ? 基于 trie的算法訪存次數(shù)很多，或內(nèi)存需求很大，像 Sta
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1