网络工程毕业设计（论文）-基于Binary Trie的IP地址查找算法研究与实现.doc

西安邮电学院
毕业设计(论文)
题目: 基于Binary Trie的IP地址
查找算法研究与实现
院系: 计算机学院
专业: 网络工程
班级: 0606
学生姓名:
导师姓名: 职称: 副教授
起止时间: 2010年 3 月 8 日至 2010 年 6月 11 日
西安邮电学院
毕业设计(论文)任务书
学生姓名
指导教师
职称
副教授
院系
计算机学院
专业
网络工程
题目
基于Binary Trie的IP地址查找算法研究与实现
任务与要求
任务:
Trie的IP地址查找算法,形成完整的算法文档;
;
,对该算法的性能进行定性分析和定量的分析。
要求:



开始日期
2010年3月8日
完成日期
2010年6 月 11日
院长(签字)
2010
年
3
月
12
日
西安邮电学院
毕业设计(论文) 工作计划


学生姓名余立宁指导教师王亚刚职称副教授
院系计算机学院专业网络工程
题目基于Binary Trie的IP地址查找算法研究与实现
______________________________________________________
工作进程
起止时间
工作内容
~ 毕业设计整体安排
~ 撰写开题报告
~ 撰写系统概要分析,进行概要设计
~ 详细设计
~ 程序设计实现测试
~ 毕业设计总结,撰写相关技术文档
~ 撰写毕业论文
~ 毕业论文修改并毕业答辩.
主要参考书目(资料)
M Sanchez, E W Biersack, W Dabbous. Survey and taxonomy of IP address lookup algorithms [J]. work, 2001, 15(2): 8–23
D. Knuth, Fundamental Algorithms Vol. 3: Sorting and Searching. Addison-Wesley,Massachusetts, 1973.
W. Eatherton, “Hardware-based protocol prefix lookups,” M. S. Thesis, Washington University, St. Louis, Missouri (May 1999).
毛曙福,LINUX C高级程序员指南[M]. 北京:清华大学出版社,2001.
主要仪器设备及材料
PC机一台
Linux开发环境
论文(设计)过程中教师的指导安排
每周周五集中答疑,平时使用电子邮件联系:lazy_linux@
对计划的说明
西安邮电学院
毕业设计(论文)开题报告
计算机学院网络工程专业 06 级 06 班
课题名称: 基于Binary Trie的IP地址查找算法
研究与实现

学生姓名: 余立宁学号:04063188
指导教师: 王亚刚
报告日期: 2010年3月14日

随着信息技术的高速发展,因特网承载的业务越来越丰富,加之人们对网络的依赖程度不断增加,使得骨干网对带宽的需求越来越大,而在对骨干网的扩展中,最为关键的是核心路由器性能的提升,路由器的性能通常受两个因素的制约,分组的交换速率;路由查找的速率。而随着交换技术的发展使得交换结构可以满足对分组高速交换的要求,最终路由查找算法就成为路由器的发展瓶颈。目前核心路由算法可分为基于线性表的查找算法和基于树型结构的查找算法。前者简单易于实现,但占有的存储器容量很大;后者的实现相对比较复杂,但占有存储容量小。算法的选择实际是实现复杂度和存储容量的折中。
本课题基于Binary Trie的IP地址查找算法是基于树型结构的查找算法,实现起来比较简单,占用存储容量小。可以用来进行快速的路由查找,提高路由查找速率。该算法是基于树型IP查找算法的基础,可以做为其它各种基于树型路由算法性能的参照。
、解决的思路及实现预期目标的可行性分析