資源描述：
《基于路由查找算法的研究與硬件實(shí)現(xiàn)》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。
1、東南大學(xué)碩士學(xué)位論文基于路由查找算法的研究與硬件實(shí)現(xiàn)姓名：林彥竹申請學(xué)位級別：碩士專業(yè)：通信與信息系統(tǒng)指導(dǎo)教師：衡偉20080101摘要近年來，隨著Intcrnct的迅猛發(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é)點(diǎn)的包處理轉(zhuǎn)發(fā)能力卻沒有跟上物理層傳輸速度的步伐。因此，網(wǎng)絡(luò)結(jié)點(diǎn)的較低的數(shù)據(jù)包處理轉(zhuǎn)發(fā)能
2、力成為了一個很重要的需要克服的瓶頸。在網(wǎng)絡(luò)結(jié)點(diǎn)對數(shù)據(jù)包的處理過程中，最主要的制約整個處理轉(zhuǎn)發(fā)速度的步驟就是路由查找。因?yàn)榛谲浖?shí)現(xiàn)的路由查找算法無法滿足更快的網(wǎng)絡(luò)要求，所以本論文的重點(diǎn)就是對路由查找算法進(jìn)行研究、完成基于硬件實(shí)現(xiàn)的查找結(jié)構(gòu)并進(jìn)行實(shí)現(xiàn)。本文對現(xiàn)有的軟件路由查找算法進(jìn)行了歸納和總結(jié)，重點(diǎn)分析了各種算法查找速度，存儲空間，更新復(fù)雜度等方面的優(yōu)缺點(diǎn)。并介紹了CAM和TCAM器件在路由查找方面的應(yīng)用．精確匹配是路由查找中的重要內(nèi)容，其查找速度的快慢，關(guān)系到網(wǎng)絡(luò)結(jié)點(diǎn)對數(shù)據(jù)鏈路層報文查找的速度。對于精確匹配，本文對基于Hash的路由查找的性能進(jìn)行了分析，實(shí)現(xiàn)了
3、采用多重Hash進(jìn)行查找的硬件結(jié)構(gòu)，并對雙重Hash的路由查找算法進(jìn)行了硬件實(shí)現(xiàn)，所實(shí)現(xiàn)的硬件結(jié)構(gòu)具有自學(xué)習(xí)功能，最后對所實(shí)現(xiàn)的硬件程序進(jìn)了仿真。最大長度匹配是路由查找中的另一個重要內(nèi)容。也是制約網(wǎng)絡(luò)層數(shù)據(jù)包轉(zhuǎn)發(fā)速度的主要因素。對于最大長度匹配，本文采取了并行結(jié)構(gòu)和變步長多分支壓縮樹相結(jié)合的算法，對算法性能進(jìn)行了分析，井對所設(shè)計的硬件結(jié)構(gòu)進(jìn)行了硬件實(shí)現(xiàn)和仿真。最后將程序下載到Xinlinx公司的V／rtex-Ⅱ系列FPGA器件中，搭建相應(yīng)的測試平臺，對查找性能進(jìn)行了驗(yàn)證。，關(guān)鍵詞：路由查找、精確匹配、最大長度匹配、Hash算法、并行結(jié)構(gòu)、變長多分支壓縮樹東南大學(xué)碩
4、士論文AbstractNowdays．withtherapiddevelopmentofImemetandpeople’Sallkindsofrequirementfornetwork,theexistingnetworkbandwidthisbeingchallenged，F(xiàn)orcorerouterswhichareusedinbackbonenetworkalreadyhaveaboutseveralGbpsinterfacevelocity,theyshouldhavethecapacityofdealingwithmillionsofdatapacket．
5、Withtheimprovementoffibertechnology,theexistingphysicalmediumhasenoughtransmitingspePxIandtransmitingqualitytOkeepupwiththenetworkbandwidth’Srequirement．Ontheotherhand，theabilityofnetworknodedealingwiththedatapacketisbehind．So，itbecomesthebottleneckofenhancingthenetworkbandwidth．Whent
6、henetworknodedealswithdatapackeb，themainreasonofrestrictingthespeedistheroutelookup．Becausethesoftware-basedroutingalgorithmcan’tmcetlargernetworkbandwidth，thisthesiswillfocusonhardware-basedroutingalgorithmanditsrealization．Thisthesiswillconcludtheexistingsoftware-basedroutingalgorit
7、hms，analyzethealgorithms’searchingspeed，storagerequirementandcomplicationofupaate．AlsothisthesiswillintroducetheCAMandTCAM’sapplicationinroutelookup．Theexact-prefixmatchingisanimportantcontentofroutelookup，foritssearchingspeedisrelatedwiththenetworknode’Sdealingwithdatapacketoflayer2．
8、Thist
