基于trie軟轉(zhuǎn)發(fā)路由查找模塊設(shè)計實現(xiàn)

《基于trie軟轉(zhuǎn)發(fā)路由查找模塊設(shè)計實現(xiàn)》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。

1、南京郵電大學(xué)碩士學(xué)位論文基于TRIE的軟轉(zhuǎn)發(fā)路由查找模塊的設(shè)計實現(xiàn)姓名：郭文文申請學(xué)位級別：碩士專業(yè)：信號與信息處理指導(dǎo)教師：曹雪虹2011-03學(xué)科門類：工學(xué)分類號：TN911單位代碼：10293密級：碩士學(xué)位論文論文題目：基于TRIE的軟轉(zhuǎn)發(fā)路由查找模塊的設(shè)計實現(xiàn)學(xué)生姓名郭文文學(xué)號碩080717指導(dǎo)教師曹雪虹教授學(xué)科專業(yè)信號與信息處理研究方向現(xiàn)代通信中的智能信號處理技術(shù)論文提交日期二〇一一年三月南京郵電大學(xué)學(xué)位論文原創(chuàng)性聲明本人聲明所呈交的學(xué)位論文是我個人在導(dǎo)師指導(dǎo)下進(jìn)行的研究工作及取得的研究成果。盡我所知，除了文中特別加以標(biāo)注和致謝的地方外，論文中不包含其他人已經(jīng)發(fā)表

2、或撰寫過的研究成果，也不包含為獲得南京郵電大學(xué)或其它教育機構(gòu)的學(xué)位或證書而使用過的材料。與我一同工作的同志對本研究所做的任何貢獻(xiàn)均已在論文中作了明確的說明并表示了謝意。研究生簽名：_____________日期：____________南京郵電大學(xué)學(xué)位論文使用授權(quán)聲明南京郵電大學(xué)、中國科學(xué)技術(shù)信息研究所、國家圖書館有權(quán)保留本人所送交學(xué)位論文的復(fù)印件和電子文檔，可以采用影印、縮印或其它復(fù)制手段保存論文。本文電子文檔的內(nèi)容和紙質(zhì)論文的內(nèi)容相一致。除在保密期內(nèi)的保密論文外，允許論文被查閱和借閱，可以公布（包括刊登）論文的全部或部分內(nèi)容。論文的公布（包括刊登）授權(quán)南京郵電大學(xué)研究生

3、院（籌）辦理。研究生簽名：____________導(dǎo)師簽名：____________日期：_____________南京郵電大學(xué)碩士學(xué)位論文摘要學(xué)科、專業(yè)：工學(xué)信號與信息處理研究方向：現(xiàn)代通信中的智能信號處理技術(shù)作者：郭文文指導(dǎo)教師：曹雪虹題目：基于TRIE的軟轉(zhuǎn)發(fā)路由查找模塊的設(shè)計實現(xiàn)英文題目：DesignonTRIE-BasedSoft-forwordRoutelookupmodule主題詞：路由查找，TRIE樹，軟轉(zhuǎn)發(fā)，最長前綴匹配Keywords:Routelookup,Trie-tree,Soft-forword,LongestPrefixMatching南京郵電

4、大學(xué)碩士研究生學(xué)位論文摘要摘要隨著Internet的迅猛發(fā)展，其規(guī)模、鏈路速度、帶寬、流量等都呈指數(shù)級增長，這對路由器的轉(zhuǎn)發(fā)性能提出了更高的要求，而轉(zhuǎn)發(fā)的重要一步就是查找路由表，故快速的路由查找算法是實現(xiàn)高速數(shù)據(jù)轉(zhuǎn)發(fā)的關(guān)鍵。在常用的路由查找算法中，基于Trie樹的算法不僅具有較好的查找速度、空間復(fù)雜度和時間復(fù)雜度，而且能適應(yīng)不斷提高的路由器性能要求，新穎的現(xiàn)代快速路由查找算法均是在Trie樹的基礎(chǔ)上通過優(yōu)化算法實現(xiàn)的。Trie樹是實現(xiàn)高速路由查找的關(guān)鍵，是實現(xiàn)各種路由查找優(yōu)化策略的基礎(chǔ)，故基于Trie樹的路由查找算法的實現(xiàn)成為軟轉(zhuǎn)發(fā)路由表查找的一種趨勢。本文將圍繞如何設(shè)計實

5、現(xiàn)高效實用的基于Trie的軟轉(zhuǎn)發(fā)路由表查找算法這一核心，結(jié)合實際路由器的自身配置，在已有算法的基礎(chǔ)上提出綜合改進(jìn)的方案，提高路由查找速度，實現(xiàn)對報文高速轉(zhuǎn)發(fā)。本文的主要內(nèi)容如下：1）研究了路由器的基本功能和IP路由選擇的流程，分析了Trie結(jié)構(gòu)在IP路由查找算法中的應(yīng)用，介紹了路由與轉(zhuǎn)發(fā)的相關(guān)概念，路由表的生成與路由選擇的基本原理。2）詳細(xì)分析了轉(zhuǎn)發(fā)模塊的框架與流程，研究了轉(zhuǎn)發(fā)查詢表項的基本結(jié)構(gòu)，詳細(xì)介紹了轉(zhuǎn)發(fā)模塊中上下行子模塊的設(shè)計方案原理和具體流程。3）研究了軟轉(zhuǎn)發(fā)路由表查找模塊對數(shù)據(jù)轉(zhuǎn)發(fā)的重要性，分析了路由表查找算法的研究現(xiàn)狀，結(jié)合新穎的算法思想設(shè)計高效實用的基于TR

6、IE的路由表查找算法。4）根據(jù)設(shè)計的路由查找算法的實現(xiàn)方法，整合源碼實現(xiàn)符合規(guī)范要求的路由表查找算法。確定整個路由器軟轉(zhuǎn)發(fā)模塊的解決方案，優(yōu)化整個模塊，最后編譯版本上機調(diào)試。5）在路由器上實現(xiàn)基于TRIE的軟轉(zhuǎn)發(fā)路由表查找算法，用測試儀配合路由器來驗證軟轉(zhuǎn)發(fā)功能的實現(xiàn)。根據(jù)實驗測試結(jié)果來分析是否滿足用戶需求，總結(jié)現(xiàn)有方案的利弊，提出改進(jìn)的方法和后期的展望。關(guān)鍵詞：路由查找，TRIE樹，軟轉(zhuǎn)發(fā)，最長前綴匹配I南京郵電大學(xué)碩士研究生學(xué)位論文ABSTRACTABSTRACTWiththerapiddevelopmentofInternet,itssize,linkspeed,ba

7、ndwidth,traffic,etc.showexponentialgrowth,whichneedahigherrouteforwardingperformance,andanimportantstepofforwardingistolooktheroutingtableup,sofastroutelookupalgorithmisthekeytohigh-speeddataforwarding.Amongthecommonlyusedroutelookupalgorithms,Trie-basedalgori