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

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

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

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