基于快速搜索樹的路由查表算法

摘 要：根據(jù)路由表中前綴的分布特點(diǎn)，將路由集合分割成幾個(gè)子集，然后分別針對(duì)每個(gè)子集建立搜索樹來實(shí)現(xiàn)路由查表。借助哈希壓縮索引表使搜索樹的深度降低到3，加快了搜索樹的查找速度。而Bloom Fmcrs的應(yīng)用，使幾乎平均一次搜索樹的查找就可以完成一次路由查表。該算法可以滿足OC—768鏈路的處理速度要求，支持達(dá)10⁶數(shù)量級(jí)的路由表項(xiàng)，適于硬件流水線方式實(shí)現(xiàn)，具有很高的實(shí)用價(jià)值。這種方法用到IPv6同樣可以收到很好的效果。

關(guān)鍵詞：IP路由查找；最長(zhǎng)前綴匹配；搜索樹；BloomFilters；哈希

中圖法分類號(hào)：TP393

文獻(xiàn)標(biāo)識(shí)5馬：A

文章編號(hào)：1001—3695(2005)07—0226-03