基于Bloom濾波器的緩存路由表快速查找算法.pdf

1、路由器是網(wǎng)絡(luò)互連的關(guān)鍵設(shè)備.隨著因特網(wǎng)的快速發(fā)展和業(yè)務(wù)量的迅猛增長(zhǎng),對(duì)路由器的吞吐性能提出了更高的要求,尤其是對(duì)骨干網(wǎng)核心路由器.在當(dāng)前的路由機(jī)制(包括IPv4和IPv6)中,路由表查找是實(shí)現(xiàn)高性能路由器(吞吐能力達(dá)100Mpps)的主要瓶頸之一.近年來(lái),為提高IP路由表的查找速度,人們已提出了許多解決方案.影響路由表查找速度的因素很多,如基礎(chǔ)軟硬件的處理速度、路由表的大小、最長(zhǎng)前綴匹配、路由更新頻率等,其中最長(zhǎng)前綴匹配是關(guān)鍵因素.傳統(tǒng)

2、路由表查找算法可大致分為兩類(lèi):基于CAM(內(nèi)容可尋址存儲(chǔ)器)和基于RAM(隨機(jī)尋址存儲(chǔ)器)的路由表查找.這兩類(lèi)算法各有優(yōu)劣,CAM算法的主要缺點(diǎn)是內(nèi)存訪問(wèn)速度慢,而RAM算法的平均內(nèi)存訪問(wèn)次數(shù)過(guò)多.2003年,D.Sarang等人首次把Bloom濾波器應(yīng)用于路由表查找.Bloom濾波器是一種隨機(jī)化的數(shù)據(jù)結(jié)構(gòu),可為信息檢索提供高效的計(jì)算算法,并具有實(shí)現(xiàn)簡(jiǎn)單和節(jié)約存儲(chǔ)空間等優(yōu)點(diǎn).但是Bloom濾波器存在一定的正向誤檢(false posit

3、ive)概率.盡管Bloom濾波器在70年代就已經(jīng)被發(fā)明,然而只在近幾年才得到重視和應(yīng)用.Sarang等人的方案,通過(guò)擴(kuò)展前綴的方式,利用了2個(gè)并行Bloom濾波器計(jì)算匹配前綴位長(zhǎng),并結(jié)合Hash查找技術(shù),可使平均RAM內(nèi)存訪問(wèn)次數(shù)接近于1.該文在Sarang方案的基礎(chǔ)上,進(jìn)一步考慮了因特網(wǎng)實(shí)際業(yè)務(wù)流所具有的臨時(shí)集中性特點(diǎn),引入了緩存機(jī)制.通過(guò)在Hash表中添加補(bǔ)充前綴的手段,消除同一前綴查找重復(fù)出現(xiàn)誤檢的缺點(diǎn),以期更大地提高路由表查找