1、 毕毕 业业 设设 计（论计（论 文）文） 题 目： 基于 Binary Trie 的 IP 地址 查找算法研究与实现 院 系： 计算机学院 专 业： 网络工程 班 级： 学生姓名： 导师姓名： 职称： 副教授 起止时间： 2010 年 3 月 8 日至 2010 年 6 月 11 日 II 毕业设计毕业设计( (论文论文) )任务书任务书 学生姓名学生姓名 指导教师指导教师 职称职称 副教授 院系院系 计算机学院 专业专业 网络工程 题目题目 基于 Binary Trie 的 IP 地址查找算法研究与实现 任务与要求任务与要求 任务：任务： 1.分析基于 Binary Trie的 IP 地址
2、查找算法， 形成完整的算法文档； 2.利用 C 语言在 Linux 环境下实现该算法； 3.利用测试数据，对该算法的性能进行定性分析和定量的分析。 要求：要求： 1.熟练进行 Linux 系统下 C 程序开发的能力 2.熟悉 TCP/IP 协议 3.较强的外文文献阅读能力 开始日开始日 2010 年年 3 月月 8 日日 完成日期完成日期 2010 年年 6 月月 11 日日 院 长院 长 ( 签签 2010 年年 3 月月 12 日日 III 主要参考书目(资料) 1 M Sanchez, E W Biersack, W Dabbous. Survey and taxonomy of IP
3、address lookup algorithms J. IEEE Network, 2001, 15(2): 823 2 D. Knuth, Fundamental Algorithms Vol. 3: Sorting and Searching. Addison-Wesley,Massachusetts, 1973. 3 W. Eatherton, “Hardware-based internet protocol prefix lookups,” M. S. Thesis, Washington University, St. Louis, Missouri (May 1999). 4
4、毛曙福，LINUX C 高级程序员指南M. 北京:清华大学出版社，2001. 主要仪器设备及材料 1 PC 机一台 2 Linux 开发环境 论文(设计)过程中教师的指导安排 每周 周五集中答疑，平时使用电子邮件联系：lazy_ 对计划的说明 IV 毕业设计(论文)开题报告 计算机 学院 网络工程 专业 06 级 06 班 课题名称： 基于基于 Binary Trie 的的 IP 地址查找算法地址查找算法 研究与实现研究与实现 学生姓名： 学号：04063188 指导教师： 报告日期： 2010 年 3 月 14 日 V 1 1本课题所涉及的问题及应用现状综述本课题所涉及的问题及应用现状综述
5、随着信息技术的高速发展，因特网承载的业务越来越丰富，加之人们对网络的依赖 程度不断增加，使得骨干网对带宽的需求越来越大，而在对骨干网的扩展中，最为关键 的是核心路由器性能的提升，路由器的性能通常受两个因素的制约，分组的交换速率； 路由查找的速率。 而随着交换技术的发展使得交换结构可以满足对分组高速交换的要求， 最终路由查找算法就成为路由器的发展瓶颈。目前核心路由算法可分为基于线性表的查 找算法和基于树型结构的查找算法。前者简单易于实现，但占有的存储器容量很大；后 者的实现相对比较复杂，但占有存储容量小。算法的选择实际是实现复杂度和存储容量 的折中。 本课题基于 Binary Trie 的 IP
6、 地址查找算法是基于树型结构的查找算法， 实现起来比 较简单，占用存储容量小。可以用来进行快速的路由查找，提高路由查找速率。该算法 是基于树型 IP 查找算法的基础，可以做为其它各种基于树型路由算法性能的参照。 VI 2本课题需要重点研究的关键问题、解决的思路及实现预期目标的可行性本课题需要重点研究的关键问题、解决的思路及实现预期目标的可行性 分析分析 本课题研究的关键问题是用何种数据结构将现有的路由表项表示出来以及如何对算 发性能进行评价。解决思路是采用基于二叉树的数据结构，通过前缀中每一位的值来决 定树的分支，将整个路由表项表示出来。处于第 L 层的节点代表了一个地址前 L 比特均 相同的地址空间，这 L 个比特串就是由从根节点到这个节点路径上的 L 比特组
