資源描述：
《網(wǎng)絡(luò)工程畢業(yè)設(shè)計(jì)（論文）-基于binary trie的ip地址查找算法研究與實(shí)現(xiàn)》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。
1、西安郵電學(xué)院畢業(yè)設(shè)計(jì)（論文）題目：基于BinaryTrie的IP地址查找算法研究與實(shí)現(xiàn)院系：計(jì)算機(jī)學(xué)院專業(yè)：網(wǎng)絡(luò)工程班級：0606學(xué)生姓名：導(dǎo)師姓名：職稱：副教授起止時(shí)間：2010年3月8日至2010年6月11日22西安郵電學(xué)院畢業(yè)設(shè)計(jì)(論文)任務(wù)書學(xué)生姓名指導(dǎo)教師職稱副教授院系計(jì)算機(jī)學(xué)院專業(yè)網(wǎng)絡(luò)工程題目基于BinaryTrie的IP地址查找算法研究與實(shí)現(xiàn)任務(wù)與要求任務(wù)：1.分析基于BinaryTrie的IP地址查找算法，形成完整的算法文檔；2.利用C語言在Linux環(huán)境下實(shí)現(xiàn)該算法；3.利用測試數(shù)據(jù)，對該算法的性能進(jìn)行定性分析和定量的分析。要求：1.熟練進(jìn)行Linux系統(tǒng)下C程序開發(fā)的能
2、力2.熟悉TCP/IP協(xié)議3.較強(qiáng)的外文文獻(xiàn)閱讀能力開始日期2010年3月8日完成日期2010年6月11日院長(簽字)2010年3月12日22西安郵電學(xué)院畢業(yè)設(shè)計(jì)(論文)工作計(jì)劃學(xué)生姓名余立寧指導(dǎo)教師王亞剛職稱副教授院系計(jì)算機(jī)學(xué)院專業(yè)網(wǎng)絡(luò)工程題目基于BinaryTrie的IP地址查找算法研究與實(shí)現(xiàn)______________________________________________________工作進(jìn)程起止時(shí)間工作內(nèi)容2010.03.08~2010.03.14畢業(yè)設(shè)計(jì)整體安排2010.03.15~2010.03.28撰寫開題報(bào)告2010.03.29~2010.04.11撰寫系統(tǒng)概要
3、分析，進(jìn)行概要設(shè)計(jì)2010.04.12~2010.04.25詳細(xì)設(shè)計(jì)2010.04.26~2010.05.09程序設(shè)計(jì)實(shí)現(xiàn)測試2010.05.10~2010.05.16畢業(yè)設(shè)計(jì)總結(jié)，撰寫相關(guān)技術(shù)文檔2010.05.17~2010.05.30撰寫畢業(yè)論文2010.06.01~2010.06.11畢業(yè)論文修改并畢業(yè)答辯.22主要參考書目(資料)1．MSanchez,EWBiersack,WDabbous.SurveyandtaxonomyofIPaddresslookupalgorithms[J].IEEENetwork,2001,15(2):8–232．D.Knuth,Fundamental
4、AlgorithmsVol.3:SortingandSearching.Addison-Wesley,Massachusetts,1973.3．W.Eatherton,“Hardware-basedinternetprotocolprefixlookups,”M.S.Thesis,WashingtonUniversity,St.Louis,Missouri(May1999).4．毛曙福，LINUXC高級程序員指南[M].北京:清華大學(xué)出版社，2001.主要儀器設(shè)備及材料1．PC機(jī)一臺2．Linux開發(fā)環(huán)境論文(設(shè)計(jì))過程中教師的指導(dǎo)安排每周周五集中答疑，平時(shí)使用電子郵件聯(lián)系：lazy_li
5、nux@126.com對計(jì)劃的說明22西安郵電學(xué)院畢業(yè)設(shè)計(jì)(論文)開題報(bào)告計(jì)算機(jī)學(xué)院網(wǎng)絡(luò)工程專業(yè)06級06班課題名稱：基于BinaryTrie的IP地址查找算法研究與實(shí)現(xiàn)學(xué)生姓名：余立寧學(xué)號：04063188指導(dǎo)教師：王亞剛報(bào)告日期：2010年3月14日221．本課題所涉及的問題及應(yīng)用現(xiàn)狀綜述隨著信息技術(shù)的高速發(fā)展，因特網(wǎng)承載的業(yè)務(wù)越來越豐富，加之人們對網(wǎng)絡(luò)的依賴程度不斷增加，使得骨干網(wǎng)對帶寬的需求越來越大，而在對骨干網(wǎng)的擴(kuò)展中，最為關(guān)鍵的是核心路由器性能的提升，路由器的性能通常受兩個(gè)因素的制約，分組的交換速率；路由查找的速率。而隨著交換技術(shù)的發(fā)展使得交換結(jié)構(gòu)可以滿足對分組高速交換的要求，
6、最終路由查找算法就成為路由器的發(fā)展瓶頸。目前核心路由算法可分為基于線性表的查找算法和基于樹型結(jié)構(gòu)的查找算法。前者簡單易于實(shí)現(xiàn)，但占有的存儲器容量很大；后者的實(shí)現(xiàn)相對比較復(fù)雜，但占有存儲容量小。算法的選擇實(shí)際是實(shí)現(xiàn)復(fù)雜度和存儲容量的折中。本課題基于BinaryTrie的IP地址查找算法是基于樹型結(jié)構(gòu)的查找算法，實(shí)現(xiàn)起來比較簡單，占用存儲容量小?？梢杂脕磉M(jìn)行快速的路由查找，提高路由查找速率。該算法是基于樹型IP查找算法的基礎(chǔ)，可以做為其它各種基于樹型路由算法性能的參照。2．本課題需要重點(diǎn)研究的關(guān)鍵問題、解決的思路及實(shí)現(xiàn)預(yù)期目標(biāo)的可行性分析本課題研究的關(guān)鍵問題是用何種數(shù)據(jù)結(jié)構(gòu)將現(xiàn)有的路由表項(xiàng)表示
7、出來以及如何對算發(fā)性能進(jìn)行評價(jià)。解決思路是采用基于二叉樹的數(shù)據(jù)結(jié)構(gòu)，通過前綴中每一位的值來決定樹的分支，將整個(gè)路由表項(xiàng)表示出來。處于第L層的節(jié)點(diǎn)代表了一個(gè)地址前L比特均相同的地址空間，這L個(gè)比特串就是由從根節(jié)點(diǎn)到這個(gè)節(jié)點(diǎn)路徑上的L比特組成。從根節(jié)點(diǎn)開始每次一位地查找：當(dāng)?shù)刂分械南鄳?yīng)位為0時(shí)選擇左分支，為1時(shí)選擇右分支。當(dāng)遇到那些對應(yīng)地址前綴的中間節(jié)點(diǎn)時(shí)，將此地址前綴記錄為目前為止找到的最長地址前綴。當(dāng)不再有分支可以選擇時(shí)
