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