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