基于多分支trie的快速路由查找算法.pdf

1、隨著Internet的不斷發(fā)展,路由查找速度已經(jīng)成為制約核心路由器性能的主要瓶頸。減少訪問存儲器的次數(shù)是提高路由查找速度的有效途徑之一。由于片外存儲器價格較片內存儲器低很多,本文利用多片片外存儲器,采用基于并行流水線的查找方式對IP地址進行最長前綴匹配,以達到訪問一次存儲器的時間完成一次路由查找。
　　 本文首先介紹了國內外現(xiàn)有的部分研究成果,并在剖析多分支trie算法的基礎上,采用分段查找及前綴擴展技術,給出了一種適合FPGA

2、實現(xiàn)的路由查找算法。算法采用多表結構,將查找過程分為了四級,然后根據(jù)四塊存儲器獨立工作的特性,采用流水線的方式進行了并行化設計,從而可以保證訪問一次存儲器完成一次數(shù)據(jù)包的查找。設計表的結構時,為了保證占用的空間小,本文給出了一個動態(tài)規(guī)劃算法用于求解四個目標層的值。
　　 本文提出的設計結構支持動態(tài)更新,并且更新單元數(shù)少。測試結果表明,在同等規(guī)模的前綴集下,相比DIR-24-8-BASIC方法在空間上具有顯著優(yōu)勢。最后,給出了算法