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

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

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

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