基于Bloomier Filter的IPv6路由算法.pdf

1、Internet骨干鏈路速度的不斷提高，要求Internet核心路由器必須以OC-768(40Gbps)甚至更高的鏈路速度處理IP最長前綴匹配(LongestPrefixMatch，LPM)，這一問題已成為Internet核心路由器的主要性能瓶頸之一。IPv6地址的出現(xiàn)要求最長前綴匹配的查找長度從IPv4的32比特增加到128比特，更大的前綴寬度給LPM帶來了巨大的挑戰(zhàn)。而路由器的轉發(fā)速率通常受限于路由選擇的速度，因此，路由查找和更新的

2、方法是路由器進行包轉發(fā)的基礎和提高其性能的關鍵性技術，在路由器設計中至關重要。 傳統(tǒng)的LPM機制并不能很好地滿足IPv6的查找要求，基于TCAM的算法能耗高，花費大；基于Trie的算法占用內(nèi)存多，延時大?；趆ash的算法由于其低能耗，高效的存儲以及O(1)的時間復雜度，是IPv6下LPM的一個很好的選擇。 本文在詳細分析多種現(xiàn)有LPM算法的基礎上，對基于hash的LPM查找機制Chisel進行改進。Chisel利用了B

3、loomierFilter這一數(shù)據(jù)結構，實現(xiàn)無沖突的hash機制；并通過前綴縮減，把比特向量引進hash機制，大大節(jié)省了存儲空間。然而，Chisel的高速路由查找，是以復雜的路由更新為代價的，最壞情況下，一個前綴的更新，將影響到2l個前綴項。本文在Chisel的基礎上，通過對IPv6地址分布現(xiàn)狀和分配政策的研究，充分利用Amdahl定律，提出了1-Chisel機制，以每個前綴增加一個比特的很小的存儲代價，使更新復雜度有了極大的提高。同時