《基于BinaryTrie的IP地址查找算法研究与实现》-毕业论文设计（学术).doc

精品 精品 西 安 邮 电 学 院 毕 业 设 计（论 文） 题 目： 基于Binary Trie的IP地址 查找算法研究与实现 院 系： 计算机学院 专 业： 网络工程 班 级： 学生姓名： 导师姓名： 职称： 副教授 起止时间： 2010年 3 月 8 日至 2010 年 6月 11 日 西 安 邮 电 学 院 毕业设计(论文)任务书 学生姓名 指导教师 职称 副教授 院系 计算机学院 专业 网络工程 题目 基于Binary Trie的IP地址查找算法研究与实现 任务与要求 任务： 1.分析基于Binary Trie的IP地址查找算法，形成完整的算法文档； 2.利用C语言在Linux环境下实现该算法； 3.利用测试数据，对该算法的性能进行定性分析和定量的分析。 要求： 1.熟练进行Linux系统下C程序开发的能力 2.熟悉TCP/IP协议 3.较强的外文文献阅读能力 开始日期 2010年3月8日 完成日期 2010年6 月 11日 院长(签字) 2010 年 3 月 12 日 西安邮电学院 毕业设计(论文)开题报告 计算机 学院 网络工程 专业 06 级 06 班 课题名称： 基于Binary Trie的IP地址查找算法 研究与实现 学生姓名： 学号指导教师： 报告日期： 2010年3月14日 1．本课题所涉及的问题及应用现状综述 随着信息技术的高速发展，因特网承载的业务越来越丰富，加之人们对网络的依赖程度不断增加，使得骨干网对带宽的需求越来越大，而在对骨干网的扩展中，最为关键的是核心路由器性能的提升，路由器的性能通常受两个因素的制约，分组的交换速率；路由查找的速率。而随着交换技术的发展使得交换结构可以满足对分组高速交换的要求，最终路由查找算法就成为路由器的发展瓶颈。目前核心路由算法可分为基于线性表的查找算法和基于树型结构的查找算法。前者简单易于实现，但占有的存储器容量很大；后者的实现相对比较复杂，但占有存储容量小。算法的选择实际是实现复杂度和存储容量的折中。 本课题基于Binary Trie的IP地址查找算法是基于树型结构的查找算法，实现起来比较简单，占用存储容量小。可以用来进行快速的路由查找，提高路由查找速率。该算法是基于树型IP查找算法的基础，可以做为其它各种基于树型路由算法性能的参照。 2．本课题需要重点研究的关键问题、解决的思路及实现预期目标的可行性分析 本课题研究的关键问题是用何种数据结构将现有的路由表项表示出来以及如何对算发性能进行评价。解决思路是采用基于二叉树的数据结构，通过前缀中每一位的值来决定树的分支，将整个路由表项表示出来。处于第L层的节点代表了一个地址前L比特均相同的地址空间，这L个比特串就是由从根节点到这个节点路径上的L比特组成。从根节点开始每次一位地查找：当地址中的相应位为0时选择左分支，为1时选择右分支。当遇到那些对应地址前缀的中间节点时，将此地址前缀记录为目前为止找到的最长地址前缀。当不再有分支可以选择时有哪些信誉好的足球投注网站过程结束，此时被记录的最长地址前缀就是查找结果。该查找方法为基于长度的顺序前缀查找，每有哪些信誉好的足球投注网站一步，有哪些信誉好的足球投注网站空间就缩减一半，当缩减为1时有哪些信誉好的足球投注网站结束。 该算法具有查找结构简单，易于实现，更新容易等优点。但也有不足，在最坏的情况下，对IPv4来说，该算法需要查找比较多达32次 ，而对IPv6来说，更需要查找比较128次，大大地影响了查找速率，从而影响路由性能。 预期目标是在Linux环境下，用C语言实现该算法，利用测试数据对该算法的性能进行定性分析和定量分析。 完成本课题的工作方案 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 毕业设计