基于路由查找算法的研究與硬件實現(xiàn).pdf

1、近年來，隨著Internet的迅猛發(fā)展和人們對網(wǎng)絡應用的各種需求，現(xiàn)有網(wǎng)絡帶寬的容量逐漸受到日益嚴重的挑戰(zhàn)。由于用于主干網(wǎng)絡互聯(lián)的核心路由器的接口速率已經(jīng)達到了幾十個Gbps，這一速率要求核心路由器每秒能夠轉發(fā)幾百萬乃至上千萬個數(shù)據(jù)包文。 隨著光通信技術的發(fā)展，現(xiàn)有的物理介質能夠保證有足夠的傳輸速度和傳輸質量滿足網(wǎng)絡流量的要求，但另一方面，網(wǎng)絡結點的包處理轉發(fā)能力卻沒有跟上物理層傳輸速度的步伐。因此，網(wǎng)絡結點的較低的數(shù)據(jù)包處理轉

2、發(fā)能力成為了一個很重要的需要克服的瓶頸。在網(wǎng)絡結點對數(shù)據(jù)包的處理過程中，最主要的制約整個處理轉發(fā)速度的步驟就是路由查找。因為基于軟件實現(xiàn)的路由查找算法無法滿足更快的網(wǎng)絡要求，所以本論文的重點就是對路由查找算法進行研究、完成基于硬件實現(xiàn)的查找結構并進行實現(xiàn)。 本文對現(xiàn)有的軟件路由查找算法進行了歸納和總結，重點分析了各種算法查找速度，存儲空間，更新復雜度等方面的優(yōu)缺點，并介紹了CAM和TCAM器件在路由查找方面的應用。 精確

3、匹配是路由查找中的重要內(nèi)容，其查找速度的快慢，關系到網(wǎng)絡結點對數(shù)據(jù)鏈路層報文查找的速度。對于精確匹配，本文對基于Hash的路由查找的性能進行了分析，實現(xiàn)了采用多重Hash進行查找的硬件結構，并對雙重Hash的路由查找算法進行了硬件實現(xiàn)，所實現(xiàn)的硬件結構具有自學習功能，最后對所實現(xiàn)的硬件程序進了仿真。 最大長度匹配是路由查找中的另一個重要內(nèi)容，也是制約網(wǎng)絡層數(shù)據(jù)包轉發(fā)速度的主要因素。對于最大長度匹配，本文采取了并行結構和變步長多分