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

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

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

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