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

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

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

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