畢業(yè)設(shè)計(jì)（論文）--基于Binavy Trie 的IP地址查找算法研究與實(shí)現(xiàn)

《畢業(yè)設(shè)計(jì)（論文）--基于Binavy Trie 的IP地址查找算法研究與實(shí)現(xiàn)》由會(huì)員上傳分享，免費(fèi)在線(xiàn)閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫(kù)。

1、西安郵電學(xué)院畢業(yè)設(shè)計(jì)（論文）題目：基于BinaryTrie的IP地址查找算法研究與實(shí)現(xiàn)院系：計(jì)算機(jī)學(xué)院專(zhuān)業(yè)：網(wǎng)絡(luò)工程班級(jí)：0606學(xué)生姓名：余立寧導(dǎo)師姓名：王亞剛職稱(chēng)：副教授起止時(shí)間：2010年3月8日至2010年6月11日21西安郵電學(xué)院畢業(yè)設(shè)計(jì)(論文)任務(wù)書(shū)學(xué)生姓名余立寧指導(dǎo)教師王亞剛職稱(chēng)副教授院系計(jì)算機(jī)學(xué)院專(zhuān)業(yè)網(wǎng)絡(luò)工程題目基于BinaryTrie的IP地址查找算法研究與實(shí)現(xiàn)任務(wù)與要求任務(wù)：1.分析基于BinaryTrie的IP地址查找算法，形成完整的算法文檔；2.利用C語(yǔ)言在Linux環(huán)境下實(shí)現(xiàn)該算法；3.利用測(cè)試數(shù)據(jù)

2、，對(duì)該算法的性能進(jìn)行定性分析和定量的分析。要求：1.熟練進(jìn)行Linux系統(tǒng)下C程序開(kāi)發(fā)的能力2.熟悉TCP/IP協(xié)議3.較強(qiáng)的外文文獻(xiàn)閱讀能力開(kāi)始日期2010年3月8日完成日期2010年6月11日院長(zhǎng)(簽字)2010年3月12日21西安郵電學(xué)院畢業(yè)設(shè)計(jì)(論文)工作計(jì)劃學(xué)生姓名余立寧指導(dǎo)教師王亞剛職稱(chēng)副教授院系計(jì)算機(jī)學(xué)院專(zhuān)業(yè)網(wǎng)絡(luò)工程題目基于BinaryTrie的IP地址查找算法研究與實(shí)現(xiàn)______________________________________________________工作進(jìn)程起止時(shí)間工作內(nèi)容2010.

3、03.08~2010.03.14畢業(yè)設(shè)計(jì)整體安排2010.03.15~2010.03.28撰寫(xiě)開(kāi)題報(bào)告2010.03.29~2010.04.11撰寫(xiě)系統(tǒng)概要分析，進(jìn)行概要設(shè)計(jì)2010.04.12~2010.04.25詳細(xì)設(shè)計(jì)2010.04.26~2010.05.09程序設(shè)計(jì)實(shí)現(xiàn)測(cè)試2010.05.10~2010.05.16畢業(yè)設(shè)計(jì)總結(jié)，撰寫(xiě)相關(guān)技術(shù)文檔2010.05.17~2010.05.30撰寫(xiě)畢業(yè)論文2010.06.01~2010.06.11畢業(yè)論文修改并畢業(yè)答辯.21主要參考書(shū)目(資料)1．MSanchez,EWBie

4、rsack,WDabbous.SurveyandtaxonomyofIPaddresslookupalgorithms[J].IEEENetwork,2001,15(2):8–232．D.Knuth,FundamentalAlgorithmsVol.3:SortingandSearching.Addison-Wesley,Massachusetts,1973.3．W.Eatherton,“Hardware-basedinternetprotocolprefixlookups,”M.S.Thesis,WashingtonUni

5、versity,St.Louis,Missouri(May1999).4．毛曙福，LINUXC高級(jí)程序員指南[M].北京:清華大學(xué)出版社，2001.主要儀器設(shè)備及材料1．PC機(jī)一臺(tái)2．Linux開(kāi)發(fā)環(huán)境論文(設(shè)計(jì))過(guò)程中教師的指導(dǎo)安排每周周五集中答疑，平時(shí)使用電子郵件聯(lián)系：lazy_linux@126.com對(duì)計(jì)劃的說(shuō)明21西安郵電學(xué)院畢業(yè)設(shè)計(jì)(論文)開(kāi)題報(bào)告計(jì)算機(jī)學(xué)院網(wǎng)絡(luò)工程專(zhuān)業(yè)06級(jí)06班課題名稱(chēng)：基于BinaryTrie的IP地址查找算法研究與實(shí)現(xiàn)學(xué)生姓名：余立寧學(xué)號(hào)：04063188指導(dǎo)教師：王亞剛報(bào)告日期：2010

6、年3月14日211．本課題所涉及的問(wèn)題及應(yīng)用現(xiàn)狀綜述隨著信息技術(shù)的高速發(fā)展，因特網(wǎng)承載的業(yè)務(wù)越來(lái)越豐富，加之人們對(duì)網(wǎng)絡(luò)的依賴(lài)程度不斷增加，使得骨干網(wǎng)對(duì)帶寬的需求越來(lái)越大，而在對(duì)骨干網(wǎng)的擴(kuò)展中，最為關(guān)鍵的是核心路由器性能的提升，路由器的性能通常受兩個(gè)因素的制約，分組的交換速率；路由查找的速率。而隨著交換技術(shù)的發(fā)展使得交換結(jié)構(gòu)可以滿(mǎn)足對(duì)分組高速交換的要求，最終路由查找算法就成為路由器的發(fā)展瓶頸。目前核心路由算法可分為基于線(xiàn)性表的查找算法和基于樹(shù)型結(jié)構(gòu)的查找算法。前者簡(jiǎn)單易于實(shí)現(xiàn)，但占有的存儲(chǔ)器容量很大；后者的實(shí)現(xiàn)相對(duì)比較復(fù)雜，但

7、占有存儲(chǔ)容量小。算法的選擇實(shí)際是實(shí)現(xiàn)復(fù)雜度和存儲(chǔ)容量的折中。本課題基于BinaryTrie的IP地址查找算法是基于樹(shù)型結(jié)構(gòu)的查找算法，實(shí)現(xiàn)起來(lái)比較簡(jiǎn)單，占用存儲(chǔ)容量小?？梢杂脕?lái)進(jìn)行快速的路由查找，提高路由查找速率。該算法是基于樹(shù)型IP查找算法的基礎(chǔ)，可以做為其它各種基于樹(shù)型路由算法性能的參照。2．本課題需要重點(diǎn)研究的關(guān)鍵問(wèn)題、解決的思路及實(shí)現(xiàn)預(yù)期目標(biāo)的可行性分析本課題研究的關(guān)鍵問(wèn)題是用何種數(shù)據(jù)結(jié)構(gòu)將現(xiàn)有的路由表項(xiàng)表示出來(lái)以及如何對(duì)算發(fā)性能進(jìn)行評(píng)價(jià)。解決思路是采用基于二叉樹(shù)的數(shù)據(jù)結(jié)構(gòu)，通過(guò)前綴中每一位的值來(lái)決定樹(shù)的分支，將整個(gè)

8、路由表項(xiàng)表示出來(lái)。處于第L層的節(jié)點(diǎn)代表了一個(gè)地址前L比特均相同的地址空間，這L個(gè)比特串就是由從根節(jié)點(diǎn)到這個(gè)節(jié)點(diǎn)路徑上的L比特組成。從根節(jié)點(diǎn)開(kāi)始每次一位地查找：當(dāng)?shù)刂分械南鄳?yīng)位為0時(shí)選擇左分支，為1時(shí)選擇右分支。當(dāng)遇到那些對(duì)應(yīng)地址前綴的中間節(jié)點(diǎn)時(shí)，將此地址前綴記錄為目前為止找到的最長(zhǎng)地址前綴