《网络工程毕业设计（论文）基于Binary Trie的IP地址查找算法研究与实现》由会员分享，可在线阅读，更多相关《网络工程毕业设计（论文）基于Binary Trie的IP地址查找算法研究与实现（34页珍藏版）》请在金锄头文库上搜索。
1、西 安 邮 电 学 院 毕 业 设 计（论 文）题 目： 基于Binary Trie的IP地址 查找算法研究与实现 院 系： 计算机学院 专 业： 网络工程 班 级： 0606 学生姓名： 导师姓名： 职称： 副教授 起止时间： 2010年 3 月 8 日至 2010 年 6月 11 日 西 安 邮 电 学 院毕业设计(论文)任务书学生姓名指导教师职称副教授院系计算机学院专业网络工程题目基于Binary Trie的IP地址查找算法研究与实现 任务与要求任务：1.分析基于Binary Trie的IP地址查找算法，形成完整的算法文档；2.利用C语言在Linux环境下实现该算法；3.利用测试数据，对
2、该算法的性能进行定性分析和定量的分析。要求：1.熟练进行Linux系统下C程序开发的能力 2.熟悉TCP/IP协议 3.较强的外文文献阅读能力开始日期2010年3月8日完成日期2010年6 月 11日院长(签字)2010年3月12日西 安 邮 电 学 院毕 业 设 计 (论文) 工 作 计 划 学生姓名 余立宁 指导教师 王亚刚 职称 副教授 院系 计算机学院 专业 网络工程 题目 基于Binary Trie的IP地址查找算法研究与实现 _ 工作进程起 止 时 间工 作 内 容2010.03.08 2010.03.14 毕业设计整体安排2010.03.15 2010.03.28撰写开题报告20
3、10.03.29 2010.04.11撰写系统概要分析，进行概要设计2010.04.12 2010.04.25详细设计2010.04.26 2010.05.09程序设计实现测试2010.05.10 2010.05.16毕业设计总结，撰写相关技术文档2010.05.17 2010.05.30撰写毕业论文2010.06.01 2010.06.11毕业论文修改并毕业答辩.主要参考书目(资料)1 M Sanchez, E W Biersack, W Dabbous. Survey and taxonomy of IP address lookup algorithms J. IEEE Network,
4、 2001, 15(2): 8232 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 毛曙福，LINUX C高级程序员指南M. 北京:清华大学出版社，2001.主要仪器设备及材
5、料1 PC机一台2 Linux开发环境论文(设计)过程中教师的指导安排每周 周五集中答疑，平时使用电子邮件联系：lazy_对计划的说明西安邮电学院毕业设计(论文)开题报告 计算机 学院 网络工程 专业 06 级 06 班课题名称： 基于Binary Trie的IP地址查找算法 研究与实现 学生姓名： 余立宁 学号：04063188指导教师： 王亚刚 报告日期： 2010年3月14日 1本课题所涉及的问题及应用现状综述随着信息技术的高速发展，因特网承载的业务越来越丰富，加之人们对网络的依赖程度不断增加，使得骨干网对带宽的需求越来越大，而在对骨干网的扩展中，最为关键的是核心路由器性能的提升，路由器
6、的性能通常受两个因素的制约，分组的交换速率；路由查找的速率。而随着交换技术的发展使得交换结构可以满足对分组高速交换的要求，最终路由查找算法就成为路由器的发展瓶颈。目前核心路由算法可分为基于线性表的查找算法和基于树型结构的查找算法。前者简单易于实现，但占有的存储器容量很大；后者的实现相对比较复杂，但占有存储容量小。算法的选择实际是实现复杂度和存储容量的折中。本课题基于Binary Trie的IP地址查找算法是基于树型结构的查找算法，实现起来比较简单，占用存储容量小。可以用来进行快速的路由查找，提高路由查找速率。该算法是基于树型IP查找算法的基础，可以做为其它各种基于树型路由算法性能的参照。2本课
7、题需要重点研究的关键问题、解决的思路及实现预期目标的可行性分析本课题研究的关键问题是用何种数据结构将现有的路由表项表示出来以及如何对算发性能进行评价。解决思路是采用基于二叉树的数据结构，通过前缀中每一位的值来决定树的分支，将整个路由表项表示出来。处于第L层的节点代表了一个地址前L比特均相同的地址空间，这L个比特串就是由从根节点到这个节点路径上的L比特组成。从根节点开始每次一位地查找：当地址中的相应位为0时选择左分支，为1时选择右分支。当遇到那些对应地址前缀的中间节点时，将此地址前缀记录为目前为止找到的最长地址前缀。当不再有分支可以选择时搜索过程结束，此时被记录的最长地址前缀就是查找结果。该查找
8、方法为基于长度的顺序前缀查找，每搜索一步，搜索空间就缩减一半，当缩减为1时搜索结束。该算法具有查找结构简单，易于实现，更新容易等优点。但也有不足，在最坏的情况下，对IPv4来说，该算法需要查找比较多达32次 ，而对IPv6来说，更需要查找比较128次，大大地影响了查找速率，从而影响路由性能。预期目标是在Linux环境下，用C语言实现该算法，利用测试数据对该算法的性能进行定性分析和定量分析。3 完成本课题的工作方案2010.03.08 2010.03.14 复习Linux，数据结构等相关知识2010.03.15 2010.03.28查找该课题相关知识，撰写开题报告2010.03.29 2010.
9、04.11撰写系统概要分析，进行概要设计2010.04.12 2010.04.25详细设计2010.04.26 2010.05.09程序设计实现并进行测试2010.05.10 2010.05.16毕业设计总结，撰写相关技术文档2010.05.17 2010.05.30撰写毕业论文2010.06.01 2010.06.11修改完善毕业论文并毕业答辩4指导教师审阅意见指导教师(签字)： 年 月 日说明：本报告必须由承担毕业论文(设计)课题任务的学生在毕业论文(设计) 正式开始的第1周周五之前独立撰写完成，并交指导教师审阅。西安邮电学院毕业设计 (论文)成绩评定表学生姓名余立宁性别男学号040631
10、88专 业班 级网络0606课题名称基于Binary Trie的IP地址查找算法研究与实现课题类型软件开发难度适中毕业设计（论文）时间2010 年3 月8 日6 月11 日指导教师王亚刚(职称：副教授)课题任务完成情况论文 (千字)； 设计、计算说明书 (千字)； 图纸 (张)；其它(含附件)：指导教师意见分项得分：开题调研论证 分； 课题质量（论文内容） 分； 创新 分；论文撰写（规范） 分； 学习态度 分； 外文翻译 分指导教师审阅成绩：指导教师(签字)： 年 月 日评阅教师意见分项得分：选题 分； 开题调研论证 分； 课题质量（论文内容） 分； 创新 分；论文撰写（规范） 分； 外文翻译
11、 分评阅成绩： 评阅教师(签字)： 年 月 日验收小组意见分项得分：准备情况 分； 毕业设计（论文）质量 分； （操作）回答问题 分验收成绩：验收教师(组长)(签字)： 年 月 日答辩小组意见分项得分：准备情况 分； 陈述情况 分； 回答问题 分； 仪表 分答辩成绩： 答辩小组组长(签字)： 年 月 日成绩计算方法(填写本系实用比例)指导教师成绩 () 评阅成绩 () 验收成绩 () 答辩成绩 ()学生实得成绩(百分制)指导教师成绩 评阅成绩 验收成绩 答辩成绩 总评 答辩委员会意见 毕业论文(设计)总评成绩(等级)： 院答辩委员会主任(签字)： 院(签章) 年 月 日备注西安邮电学院毕业论文(设计)成绩评定表(续表)目 录摘要IAbstractII1引言11.1 背景介绍11.2 路由查找现状31.3 基于Trie结构的路由算法的介绍41.4 论文结构92 基于Binary Trie的算法分析102.1 Bi
