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

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

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