基于快速搜索樹的路由查表算法
2005-04-29 00:00:00譚興曄張勇雷振明
計算機(jī)應(yīng)用研究 2005年7期
摘 要：根據(jù)路由表中前綴的分布特點，將路由集合分割成幾個子集，然后分別針對每個子集建立搜索樹來實現(xiàn)路由查表。借助哈希壓縮索引表使搜索樹的深度降低到3，加快了搜索樹的查找速度。而Bloom Fmcrs的應(yīng)用，使幾乎平均一次搜索樹的查找就可以完成一次路由查表。該算法可以滿足OC—768鏈路的處理速度要求，支持達(dá)106數(shù)量級的路由表項，適于硬件流水線方式實現(xiàn)，具有很高的實用價值。這種方法用到IPv6同樣可以收到很好的效果。
關(guān)鍵詞：IP路由查找；最長前綴匹配；搜索樹；BloomFilters；哈希
中圖法分類號：TP393
文獻(xiàn)標(biāo)識5馬：A
文章編號：1001—3695(2005)07—0226-03
