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

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

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

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