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

西 安 邮 电 学 院 毕 业 设 计（论 文）题 目： 基于Binary Trie的IP地址 查找算法研究与实现 院 系： 计算机学院 专 业： 网络工程 班 级： 0606 学生姓名： 导师姓名： 职称： 副教授 起止时间： 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日西 安 邮 电 学 院毕 业 设 计 (论文) 工 作 计 划 学生姓名 余立宁 指导教师 王亚刚 职称 副教授 院系 计算机学院 专业 网络工程 题目 基于Binary Trie的IP地址查找算法研究与实现 _ 工作进程起 止 时 间工 作 内 容2010.03.08 2010.03.14 毕业设计整体安排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毕业论文修改并毕业答辩.主要参考书目(资料)1 M Sanchez, E W Biersack, W Dabbous. Survey 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, Missouri (May 1999).4 毛曙福，LINUX C高级程序员指南M. 北京:清华大学出版社，2001.主要仪器设备及材料1 PC机一台2 Linux开发环境论文(设计)过程中教师的指导安排每周 周五集中答疑，平时使用电子邮件联系：lazy_linux对计划的说明西安邮电学院毕业设计(论文)开题报告 计算机 学院 网络工程 专业 06 级 06 班课题名称： 基于Binary Trie的IP地址查找算法 研究与实现 学生姓名： 余立宁 学号：04063188指导教师： 王亚刚 报告日期： 2010年3月14日 1本课题所涉及的问题及应用现状综述随着信息技术的高速发展，因特网承载的业务越来越丰富，加之人们对网络的依赖程度不断增加，使得骨干网对带宽的需求越来越大，而在对骨干网的扩展中，最为关键的是核心路由器性能的提升，路由器的性能通常受两个因素的制约，分组的交换速率；路由查找的速率。而随着交换技术的发展使得交换结构可以满足对分组高速交换的要求，最终路由查找算法就成为路由器的发展瓶颈。目前核心路由算法可分为基于线性表的查找算法和基于树型结构的查找算法。前者简单易于实现，但占有的存储器容量很大；后者的实现相对比较复杂，但占有存储容量小。算法的选择实际是实现复杂度和存储容量的折中。本课题基于Binary Trie的IP地址查找算法是基于树型结构的查找算法，实现起来比较简单，占用存储容量小。可以用来进行快速的路由查找，提高路由查找速率。该算法是基于树型IP查找算法的基础，可以做为其它各种基于树型路由算法性能的参照。2本课题需要重点研究的关键问题、解决的思路及实现预期目标的可行性分析本课题研究的关键问题是用何种数据结构将现有的路由表项表示出来以及如何对算发性能进行评价。解决思路是采用基于二叉树的数据结构，通过前缀中每一位的值来决定树的分支，将整个路由表项表示出来。处于第L层的节点代表了一个地址前L比特均相同的地址空间，这L个比特串就是由从根节点到这个节点路径上的L比特组成。从根节点开始每次一位地查找：当地址中的相应位为0时选择左分支，为1时选择右分支。当遇到那些对应地址前缀的中间节点时，将此地址前缀记录为目前为止找到的最长地址前缀。当不再有分支可以选择时搜索过程结束，此时被记录的最长地址前缀就是查找结果。该查找方法为基于长度的顺序前缀查找，每搜索一步，搜索空间就缩减一半，当缩减为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.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周周五之前独立撰写完成，并交指导教师审阅。西安邮电学院毕业设计 (论文)成绩评定表学生姓名余立宁性别男学号04063188专 业班 级网络0606课题名称基于Binary Trie的IP地址查找算法研究与实现课题类型软件开发难度适中毕业设计（论文）时间2010 年3 月8 日6 月11 日指导教师王亚刚(职称：副教授)课题任务完成情况论文 (千字)； 设计、计算说明书 (千字)； 图纸 (张)；其它(含附件)：指导教师意见分项得分：开题调研论证 分； 课题质量（论文内容） 分； 创新 分；论文撰写（规范） 分； 学习态度 分； 外文翻译 分指导教师审阅成绩：指导教师(签字)： 年 月 日评阅教师意见分项得分：选题 分； 开题调研论证 分； 课题质量（论文内容） 分； 创新 分；论文撰写（规范） 分； 外文翻译 分评阅成绩： 评阅教师(签字)： 年 月 日验收小组意见分项得分：准备情况 分； 毕业设计（论文）质量 分； （操作）回答问题 分验收成绩：验收教师(组长)(签字)： 年 月 日答辩小组意见分项得分：准备情况 分； 陈述情况 分； 回答问题 分； 仪表 分答辩成绩： 答辩小组组长(签字)： 年 月 日成绩计算方法(填写本系实用比例)指导教师成绩 () 评阅成绩 () 验收成绩 () 答辩成绩 ()学生实得成绩(百分制)指导教师成绩 评阅成绩 验收成绩 答辩成绩 总评 答辩委员会意见 毕业论文(设计)总评成绩(等级)： 院答辩委员会主任(签字)： 院(签章) 年 月 日备注西安邮电学院毕业论文(设计)成绩评定表(续表)目 录摘要IAbstractII1引言11.1 背景介绍11.2 路由查找现状31.3 基于Trie结构的路由算法的介绍41.4 论文结构92 基于Binary Trie的算法分析102.1 Binary Trie算法概述102.2 算法涉及的主要操作112.3 Binary Trie算法性能123 算法的详细设计与实现133.1 算法逻辑结构的实现133.2 主要函数的实现和作用133.3 部分函数流程图144 算法测试及性能评价174.1 测试环境174.2 测试结果174.3 算法的可扩展性评价195 结论205.1 全文总结205.2 改进方案20致谢21参考文献2221摘 要随着信息技术的高速发展，因特网承载的业务越来越丰富，加之人们对网络的依赖程度不断增加，使得骨干网对带宽的需求越来越大，而在对骨干网的扩展中，最为关键的是核心路由器性能的提升。这就要求核心路由器每秒能转发几百万甚至更多的分组，快速路由查找技术成为路由器报文转发的瓶颈。因此如何实现路由表的高速查找和更新就成为研究的难点。同时随着IPv6技术的逐步成熟和推广，也进一步要求提升路由查找的性能。本文简要介绍了目前因特网的使用情况及发展趋势以及当下路由查找算法的现状，并简要介绍了几种常用的基于Trie结构的IP路由算法。重点研究了基于Trie结构的基础算法基于Binary Trie的IP地址查找算法，本文完成了该算法的实现并根据实验数据对其进行了定性及定量的性能分析。关键词：IP路由查找 最长前缀匹配 Trie树AbstractWith the rapid development of information technology, the Internet is carrying more and more applications, and the number of web users is fast increasing, which lead to the demand for bandwidth increase on its backbone network, so to improve and upgrade the core router becomes the key to expand the backbone network . It orders the core router to be able to forward ten million of packets per second. Fast routing lookup has become the bottleneck of high speed packet forwarding. Thus how to improve search and update performance is the key. Besides, IPv6 technology has been more and more mature, and is being applied into many domains. And it also order to improve the performance of routing lookup. This paper describes the Internet usage situation and trends and summarizes the route lookup algorithm existed, then briefly introduces some IP routing lookup algorithms based on trie structure. This paper emphatic describes the binary trie IP routing lookup algorithm, and implements the algorithm, in the same time , we carry out qualitative and quantitative analysis according to the experimental data.Key Words: IP Route Lookup Longest Prefix Match Trie tree基于Binary Trie的IP地址查找算法研究与实现1引言互联网已经走进千家万户，成为人们生活中不可缺少的组成部分，它不仅为人们提供了各种各样的简单且快捷的通信与信息检索手段，更重要的是为人们提供了巨大的信息资源和服务资源。随着越来越多的人认识并使用互联网，使得在互联网中起互联作用的路由器或路由交换机不堪重负。路由器或路由交换机完成的核心功能就是在路由表中为来自不同链路、去往不同目的地的IP分组找到最佳的传送路由，并以接力的方式把分组送到下一跳的路由器，如此反复，直到分组到达最终目的地。而为每个IP分组根据各自的目的地，在路由表里找到最佳匹配路由的算法，就是路由查找算法。1.1 背景介绍1.1.1 因特网应用需求及发展趋势截至2009年底，中国网民规模达到3.84亿人，较2008年增长28.9%，在总人口中的比重从22.6%提升到28.9%，互联网普及率在稳步上升。随着中国网民规模的不断增加，意味着IP地址资源的不足将会表现的更加突出，更加迫切的要求互联网技术快速的更新和发展。图1-1 中国网民规模与增长率表1-1：世界范围使用Internet的人口分布情况（200912）地区总人口网民数互联网普及率占世界网民数量比率2000-2009 年增长率非洲991,002,342 86,217,9008.7 % 4.8 %1,809.8 % 亚洲3,808,070,503 764,435,900 20.1 % 42.4% 568.8 %欧洲803,850,858 425,773,571 53.0 % 23.6 %305.1 % 中东202,687,00558,309,546 28.8 % 3.2 % 1,675.1 %北美 340,831,831 259,561,000 76.2 %14.4 %140.1 % 拉美586,662,468 186,922,050 31.9 % 10.4 % 934.5 % 大洋洲 34,700,20121,110,49060.8 % 1.2 % 177.0 % 总计6,767,805,208 1,802,330,457 26.6 % 100.00%399.3 %从表1-1中可以看出，世界范围内使用互联网的速度呈现快速增长的的趋势，我们可以相信，互联网的使用在世界范围内的迅速扩展，将对网络容量和互连设备性能提出更高的要求。1.1.2 核心路由表（BGP）的增长趋势图1-2 Internet核心网BGP路由表规模增长趋势如图1-2所示，路由表的规模的迅猛增加是不可避免的，路由表的规模和前缀的潜在数量直接影响路由查找和分组分类算法的时间和空间复杂度，这将使路由查找技术面临严峻的考验。路由表的日益膨胀和IP地址的短缺，都预示着新一代网络协议IPv6必然在不久的将来被实施，因为IPv6协议不仅可提供充足的地址空间，还能对路由前缀实施更好的聚合，以减小路由表规模。但是，IPv6协议的应用也将给路由查找带来很大的挑战，因为IPv6的实施意味着IP地址将从32位迅速增加到128位，而目前大多数成熟的算法都和IP地址长度密切相关，有些算法根本无法适用于IPv6。1.2 路由查找现状路由查找是寻找最长前缀匹配的问题，其难点在于不仅需要考虑与地址前缀相匹配，而且还需要考虑地址前缀的长度。可以用基于硬件和软件两种方法来实现路由查找。1.2.1 基于硬件的查找算法分析基于RAM的路由查找方案是最简单的基于硬件的查找算法，该方案是在RAM中为所有的IP地址都建立一个对应的转发表项。进行路由查找时，仅需要根据目的IP地址进行检索，一次访存就可以找到对应的路由信息。但这将造成转发表空间的极大浪费，因此，这种方案在实际中并不可行。目前使用最多的硬件实现方式是在基于RAM技术的改进：内容寻址存储器 (ContentAddressableMemory，简记CAM)来进行快速的路由查找。CAM能够在一个硬件时钟周期内完成关键字的精确匹配查找。常用的随机存储器通过输入地址来返回该地址所对应的数据信息，而CAM的访问方式不同，只需输入关键字的内容，CAM就会将此关键字与C胡中所有的表项同时进行匹配比较，最后返回匹配表项在CAM中所对应的地址。这种方法有一个明显的缺点，即在对地址前缀长度具体分布没有准确了解之前，为了保证能够存储N个前缀表项，每个CAM都需要有N个表项的空间，因此，预留方案使得CAM存储空间的利用率大大降低了，而且成本昂贵。为了能够克服CAM方法的缺点，又有一种CAM实现机制-三态CAM(TernaryContent一 AddressableMemory，简记TCAM)提出来。TCAM一个特殊的CAM硬件设备，是CAM实现机制的改进。结构同CAM一样，由一个二维阵列组成，阵列中的每一行对应存储器的一个槽，槽的大小依照不同的应用设置成64bits、72bits或128bits及更高的比特位大小。它能起到和完全相关联存储器一样的功用。TCAM的优点是它保存的表项在长度要求上非常灵活，可以在同一个TCAM芯片中保存任意长度的关键字表项。TCAM具有实现简单、查找速度快的优点，它使用并行技术，查找复杂度仅为O(1)，但TCAM最大的不足之处在于其造价昂贵、集成度低和高功耗。1.2.2 基于软件的查找算法分析基于软件的路由查找算法有很多种，现按照算法实现的数学模型，对一些经典的路由查找算法做简要介绍。基于线性查找：路由表内的表项按照简单的线性排列方式组织，查找将待查找的IP地址和数据库内的前缀逐一进行比较，直到匹配为止。这种算法实现非常简单，而且存储代价也并不高，适用于低速要求下非常小规模的路由表实例。然而，此算法不可能被广泛采用，特别是对于速度要求严苛的环境，因为其时间复杂度和路由表的规模成正比，其期望值是N/2；其空间复杂度为O(NW)(其中W为最长前缀长度)。 基于Trie结构的查找：根据前缀的二进制比特值，构建二叉树或二的次叉树，根据前缀的二进制比特值将其关联的存储在分叉树上。检索将待查找的IP地址的二进制比特值作为索引，在Trie树数据结构上索得到相应的前缀以及对应的下一跳路由信息。二分/多分查找：根据前缀的一些特性，例如前缀长度、前缀区间等，先将前缀进行预分割处理，并构造相应的决策树，将前缀存储在决策的不同分支。查找时，利用待匹配目的IP地址对应的属性值，在决策上进行搜索，得到与之匹配的最佳表项。基于哈希表结构的查找：根据前缀某个指定属性的哈希函数值，构造希表对前缀进行存储组织。查找时根据待匹配目的IP地址的哈希值进哈希索引，进而得到匹配结果。由于哈希冲突的存在，基于哈希表的法通常需结合其它的算法思想，或常被融入到众多算法的思想精髓里。 规避查找技术：通过利用查找任务的某些局部性特征，或者对查找任进行特定的转化和重新分配，使得某些查找任务可以被简化或规避，而减小路由查找的压力，以满足高性能的需求。1.3 基于Trie结构的路由算法的介绍下面对基于Trie结构的基于Binary Trie的路由算法（在第二章重点介绍）、路径压缩（Path-Compressed）Trie算法、多比特Trie算法、级压缩Trie（LC-Trie）算法、位图压缩（Bitmap-Compressed）Trie算法进行简要介绍。1.3.1 Binary Trie的路由算法 图1-3路由前缀集用例以及对应的二进制Trie算法数据结构 基本的二进制Trie数据结构早在20世纪70年代就被提出，这种Trie的每个结点最多包含2个指针，分别指向他的左右孩子结点，代表前缀的某个比特位为0和1时两种情况的搜索分支。在Trie树中，处于第L层的结点实际上代表了一类地址前L-1比特均相同的地址空间，如图1-3所示。查找搜索时，根据待查找IP地址的比特位，从Trie树的根结点开始依次向其子孙结点进行，直到再无分支可搜索为止，其间记录的最后一个前缀结点对应的路由信息就是查找结果。基本的二进制Trie数据结构构造的Trie最多有W+1层，因此每次搜索的次数最多为W次，所以查找时间复杂度是O(W)；存储一个前缀，最多可能产生W个Trie结点，因而该算法的存储复杂度为O(WN)。1.3.2 路径压缩Trie算法要提高查找速度、减少存储器访问操作的次数，必须降低Trie树的高度。降低Trie树高度的一种方法是使用路径压缩技术。路径压缩是K.Sklower在1968年D.R.Morrison提出的一种叫做PATRICIA的算术编码算法基础上，提出的一种称为路径压缩Trie的最长前缀路由查找算法。很明显，在二进制trie树中存在着许多不含转发信息的中间结点。从地址前缀分布的特点可知，到目前为止还没有长度小于8比特的地址前缀，即便是长度介于9-15比特之间的前缀也并不多，这就使得二进制Trie树的前若干层主要是由那些不含转发信息的中间结点组成。路径压缩的Trie树是对树的层次进行压缩，来减小树的深度。由于某些结点被删除，查找过程中不是逐位对比，而是维护一个位变量指示下一个需要检查的比特位。为了恢复原有信息，路径压缩Trie树需要保存地址前缀的比特串。图1-4路径压缩Trie算法数据结构 当二进制Trie树稀疏时，有许多内部结点具有单个的分支，当访问这样的结点时，没有分支决策，仅有的操作是当这个结点对应路由表中的一个前缀时记录下一跳信息，使得Trie有一个高的空间复杂度和大的查找时间。为了降低存储需求，缩短Trie树的深度（查找时间），路径压缩Trie中去掉了所有具有单个分支的内部结点（不包括含有前缀的结点）。图1-4给出了路径压缩Trie算法的一个示例（采用与图1-3中相同的前缀集）。前缀结点b和e都处于一个“单分支并且内部不包含前缀结点的子Trie结构”的末端，因而对应的单分支Trie结构被压缩掉。为了保证查找正确，在结点中增加两个域：Bitposition，表示下一个要比较的字符位；Bitstring，表示从根到该结点位置的路径对应的位串。路径压缩Trie的每一个叶子结点含有一个路由前缀和一个下一跳信息指针。当遍历一个路径压缩时间Trie查找一个地址时，将结点中的位串与待查找的地址比较。如果该位串是地址的一个前缀，则存储下一跳信息指针(如果存在)并且转向下一个结点。当比较失败或者到达叶子结点时，查找终止。此时，最近记录的下一跳信息指针作为结果被返回。事实上，对于非前缀内部结点，路径压缩Trie中的位串并不是必需的，增加这样的信息有助于尽早终止查找，从而提高平均查找性能。路径压缩Trie减少了对Trie结构查找的平均次数，但最坏情况下，路径中可能不存在单分支结构，因此查找时间复杂度仍为O(W)；最坏情况下，没有分支被压缩，因而存储复杂度还是O(NW)。事实上，路径压缩Trie仅当二进制Trie树稀疏时其性能较优。随着前缀个数的增加以及二进制Trie树变得稠密，使用路径压缩Trie的改进性能降低。1.3.3 多比特Trie算法 基本二进制Trie算法在查找时每次仅检查IP地址的一个比特，查找速度较慢。多比特Trie算法在查找过程的每一步检查多个比特，加速查找的进程，其中每步检查的比特数定义为搜索步长。如图1-5所示，该多比特Trie的第一层上有8个分支，对应的搜索步长为3；而在第二层，每个结点有4个分支，对应的搜索步长为2。我们看到，整个Trie树仅有2层，即最多仅需2次多分支Trie搜索就可以得到最终匹配结果，相比基本二进制Trie在性能上有了较大的改进。一般的，k比特（即每层都有2k个分支的）Trie的查找时间复杂度是O(W/k)。另一方面，我们注意到，多比特Trie不能支持任意长度的地址前缀，如图1-5的例子，该多比特Trie仅支持长度为3和5的前缀，为了能够用多比特Trie来进行前缀查找，路由表中的地址前缀需要被扩展成这两种长度。这种扩展带来了存储的冗余度，增加了存储复杂度。最坏情况下，存储复杂度为O(N 2kW/k)。图1-5多分支Trie的数据结构示意针对常规的多比特Trie浪费存储空间的问题，S.Nilsson等人提出了一种叫做层压缩Trie（Level-Compressed Trie）的算法。该算法的主要思想是：灵活的为Trie的各个层、各个分支按照前缀集分布特点自适应选定不同的搜索步长：当子Trie结构分支是满2L叉树时，才使用步长L。这样既能发挥多比特Trie的优势，同时由于子Trie结构本来就是满2L叉树，不会产生结点复制。但我们也注意到，层压缩Trie仅在Trie结点分布较为密集时才较为有效。1.3.4 级压缩Trie（LC-Trie）算法如上所述，路径压缩Trie适合于结点稀疏的情况。Nilsson ET AL提出了一种级压缩技术用于结点稠密的情况。这种技术被称为级压缩Trie，简称LC一Trie。LC一Trie结合路径压缩和多位Trie的特点进一步优化基本Trie结构。LC压缩树中每个内部结点的孩子结点都是连续存放的，父结点只存放左孩子指针，每个父结点还存放分支(branch)信息，如果父结点有8个孩子结点，分支记录将是3，孩子结点的个数刚好是分支记录的2的幂次方。另外每个父结点还记录跳步(skip)信息，跳步是指查找到当前结点所跨越的比特数。查找时，从树的根部开始查找，根据分支信息、跳步信息和左孩子指针就可以搜索到对应的下一个孩子结点，最终能找到叶结点，从叶结点就可以知道路由信息。LC层压缩算法的关键是构建层压缩树。构建LC树时，首先对前缀(称为基矢量，base vector)进行排序，对已经排好序的基矢量，采用由上至下的方法来构建LC树。它将基矢量划分成许多子间隔(subinterval)，子间隔的划分是按照基矢量的第一个成员，基矢量的个数和它们相同的前缀部分进行的。如果子间隔只有一个基矢量，就生成一个叶结点，否则计算跳步数和分支个数，并创建一个内部结点。对每个结点都采用以上的方法，以此递归下去就可以构建LC压缩树。以上构建LC树是一种比较严格的方法。这样构建的LC树可能会使树的深度很大，因为它要求每一层必须是完全二叉树才能对结点作压缩，否则就不能进行压缩处理。为了减小树的深度，对以上的构建方法作一定的处理，其方法是并不要求是完全二叉树才能作压缩，只要孩子结点的数目达到一定的量就对结点进行压缩，使用一个填充因子 (finfactor)来决定是否压缩，这样势必带来一些空结点，但是这样带来的好处是用空间换时间，从而减少树的搜索深度。考虑到根结点的分支数目对整个查找的影响比较大，所以将根结点的分支数固定，在实现算法时通常将根结点的分支值设置为16，这样共有2到6个分支。树的深度受填充子的影响，对一个比较理想的填充因子，LC树的最大深度达到5，平均深度小于2。可以看到，采用这种方法有些不确定因索，压缩树的深度受填充因子的影响比较明显，如果前缀比较分散，可能会使树的搜索深度加大。构建LC压缩树的操作比较复杂，因为它要对基矢量进行排序，并需要对基矢量进行子间隔内的处理，这种采用递归方法来构建压缩树的过程显得比较复杂。而且，插入和删除路由将可能会导致树的变动比较大，这种变动可能会要求子结点合并，这带来了插入和删除的复杂性。1.3.5 位图压缩（Bitmap-Compressed）Trie算法路径压缩Trie、层压缩Trie等所谓的压缩都是从提高查找性能的角度考虑的，主要是将搜索的步骤进行压缩。而位图压缩Trie技术则是针对多比特Trie造成的大量前缀扩展问题而提出的。它实际上是一种数据压缩技术，试图对多比特Trie的数据结构进行无损数据压缩减少系统的内存使用量。位图压缩的思想首先由M.Degermark等人提出，N.Huang和D.E.Taylor等人也分别将它采用到他们的路由查找算法里面，其原理如图1-6所示。对于多比特Trie的某一个分支子Trie，假设其搜索步长为k，则子Trie包含2k个分支，对应一个含有2k个元素的结点信息阵列；而实际上，这个阵列中的元素很多可能是由于多比特Trie的结点复制产生的，对应同一个路由前缀，含有完全一致的路由信息。如图1-6所示，“结点信息阵列”包含多个长串的相同元素的“数据串”。位图压缩算法引入一个叫做“压缩位图”的数据结构来表示这些数据串在阵列中的起点位置，位图的对应比特被标志为“1”，否则为0；而每个数据串相同的数据仅需要保存一份，即其它相同的元素可以被“压缩”掉。压缩后的阵列叫做“压缩的结点信息阵列”。不难验证压缩前后的数据等价。查找时，首先定位对应元素在“结点信息阵列”中的位置，计算对应的“压缩位图”中该位置之前有多少个“1”，然后再根据这个计算的数值，索引“压缩的结点信息阵列”相应的元素，得到结果。图1-6位图压缩技术的原理示意多比特Trie结点阵列中相同元素组成“数据串”的个数是和路由前缀的规模N成正比的，因此“压缩的结点信息阵列”是O(NW)的规模。原来O(N 2kW/k)量级的“结点信息阵列”被同样数量的位图阵列取代。假设原来一个结点需要4Bytes来存储，现在仅需1bit，这部分缩小了32倍。1.4 论文结构本文的组织结构如下：第2章 介绍了基于Binary Trie的IP地址查找算法的概述。文中对该算法涉及的主要操作做了重点介绍，并对其算法性能进行了定性的评价。第3章 对该算法的实现和逻辑结构做了介绍。文中对算法所用的存储结构作了介绍，以及对主要函数的功能进行了说明并画出主要函数的流程图。第4章 根据实验数据对该算法进行定性定量的性能分析。经过多组数据实验，对该算法的性能做统计分析并用图表的形式表示。第5章 是论文的总结及对该算法提出进一步的改进方案。2 基于Binary Trie的算法分析2.1 Binary Trie算法概述 这是IP查找中使用的基本Trie结构，也就是我们常提到的二叉树。在这种结构中，每次进行结点相关操作时，都是以一个比特作为比较对象的，其下属分支最多包含左右两个结点:0(左结点)和1(右结点)。如图2-1所示。这样的一棵树包含了所有的可能的网络前缀，但并非每一个结点都被使用。使用的结点将会存有转发信息。如图2-2示，一个位于树的第n层上的结点k表示所有具有同样的头n位的路由前缀的集合。结点k的每一个分支按照下一位是0或1分别指向对应子树的根结点，该子树根结点代表了所有具有同样的头h+l位的路由前缀。由于采用最长前缀匹配原则，每一次结点访问过程中，要从Trie的根结点开始，按包中目标地址的每一位是O或l决定下一个要访问的结点，搜索到叶子结点后搜索过程才结束。在Trie的遍历过程中，记录目前匹配的最长地址前缀从而获取下一跳信息。结点的增加或删除通过路由协议来实现。使用的结点并不需要保存前缀信息，因此它的路径就决定了它所要存储的数据。这种Trie的每个结点最多包含2个指针，分别指向他的左右孩子结点，代表前缀的某个比特位为0和1时两种情况的搜索分支。在Trie树中，处于第L层的结点实际上代表了一类地址前L-1比特均相同的地址空间。 采用二叉Trie树进行IP地址最长匹配的最有名的例子是BSD内核.它的算法称为 Radixtrie。首先把整个转发表构造成二叉树的结构。结点代表转发表中的一条记录。在搜索时，沿着匹配的路径逐渐从树根出发走向树叶。同时，记住最新经过的结点，直到路径走不下去为止。从根到最新的结点就是最长的地址前缀。图2-1Binary Trie结构图2-2 Binary Trie树代表的地址空间结构2.2 算法涉及的主要操作2.2.1 路由表的构建路由表的构建就是根据每个IP前缀构造二叉树结点。结点的插入是在已有的Trie树中按IP比特位比较，寻找合适的插入位置的过程。过程中除了为新的路由项生成新结点外，可能会插入辅助结点来平衡树结构，这将导致附加结点的内存申请。对于路由表，其初始状态为空，需要逐条加入。2.2.2 删除路由表项删除路由表项是删除二叉树中不用的IP前缀信息，实际上就是删除无用的结点。无用结点的删除可以理解为结点查询动作的扩展对查找到的结点进行删除操作，该操作可能引起连锁反应，即递归删除上层的中间结点。当实际路由删除时可能会涉及更复杂的更新动作，比如对其他关心路由变化的协议的通知等，由于其根实际环境的相关性较大，所以在本文不做讨论。2.2.3 路由表的更新路由表的更新操作实际上是新路由的插入和无用路由的删除过程。因为结点本身只包含了基本的比特信息，不存在更新问题，只存在插入、删除两个操作。对于包含的结点中具体路由信息的修改，可以通过查询到相应的结点，然后修改或者分解为先删除后增加两个操作来完成。2.2.4 路由查询路由查询是指根据待查的IP地址在所建的二叉树中寻找最差匹配前缀的操作。路由查询的效率是决定数据转发速度的重要因素之一。另外路由的删除、更新操作实质上也是查询的一个操作，所以他们的效率也将受到查询算法效率的影响，当然其他的根世纪路由条目相关的操作不再考虑之列。2.3 Binary Trie算法性能 Binary Trie树的优点在于其实现的简单性，它只用根据IP地址比特逐个比较，直到找到一最长的前缀匹配。其不足之处在于树的深度较大，比较搜索的次数较多，查找速度不是很快。基于树型结构的路由查找容易受到前缀长度的影响。如果Trie中存储的最长前缀的位数是W，则查找的时间复杂度是O(W)，如果有N个前缀，其存储需要是O(Nw)(N表示路由表中的项数)，更新的过程基于结点的查找，更新时间是O(W)。虽然这种结构简单，但是他的最坏时间复杂度是O(W)，而W可能很大，如果32比特的IP地址用一棵二叉trie树存储，那么树的深度为32，在最坏情况下树的深度为32，即需要32次的存储器访问。这对128位地址的IPv6来说，无疑是一个极大的挑战。为了减少查询的时间，必须减小树的深度。由于低档路由器要求的查找速率不是很高，该查找算法在低档路由器中可以得到应用。3 算法的详细设计与实现3.1 算法逻辑结构的实现该算法采取链式存储结构，如图3-1所示含有两个指针域，左孩子指针和右孩子指针，当比特位为0时指向左孩子，当比特位为1时指向右孩子。还有一个int型数据域，用来记录下一跳端口信息，当该节点为有效节点时数据域记录下一跳端口信息，否则数据域记为-1。 图3-1 Binary Trie的存储结构3.2 主要函数的实现和作用3.2.1 ReadIProute（）函数该函数是从路由表中读取路由信息，路由表以文本文件的方式存储，在该函数中以只读的方式读取路由信息，当该文本文件非空时，以“前缀长度 IP地址 下一跳端口”的形式读取路由信息，再根据所读取的信息构造二叉树。3.2.2 CreatBitree（）函数该函数是根据从路由表中读取的路由信息创建二叉树，根据IP地址前缀值确定分支方向，0指向左分支；1指向右分支。如果当前分之存在时就利用当前结点，如果不存在就申请空间，并对该结点进行初始化。当树深度小于该IP地址前缀长度时，结点的数据域记为-1，否则该结点数据域记录下一跳端口信息。3.2.3 SearchIP（）函数该函数是以所要查找的IP地址为关键字，在所创建的二叉树中进行搜索，从Trie的根结点开始，按目标IP地址的每一位是0或l决定下一个要访问的结点，搜索到叶子结点后搜索过程才结束。在Trie的遍历过程中，记录目前匹配的最长地址前缀从而获取下一跳信息。3.2.4 SaveMessage（）函数该函数是将查找结果以只写的方式存入名为“BinaryTrie”的文本文件之中，存储格式是“待查IP地址 匹配的前缀值 下一跳端口号 查找次数”。3.3 部分函数流程图3.3.1 该算法流程图图3-2 该算法流程图3.3.2 CreatBitree（）函数流程图图3-3CreatBitree（）函数流程图3.3.3 SearchIP（）函数流程图图3-4 SearchIP（）函数流程图4 算法测试及性能评价4.1 测试环境主频1.67Ghz，512MB内存，英特尔奔腾处理器，Ubuntu 7.10操作系统，标准gcc编译器。4.2 测试结果测试结果如表4-1所示。表4-1 实验测试结果路由表项待查表项存储容量平均查找次数506991331613616622.81506991179313616624.21506661271011949022.79506661319611949023.29506021204712549324.02506021179712549322.95506331202812912224.38506331281612912224.01506081279213350623.51506081356213350623.77如图4-2所示，横轴表示的是不同的路由表文本文件，竖轴表示的是每个文件中所含路由信息条目的个数。图4-2路由表项图4-3待查路由表项如图4-3所示，横轴表示的是待查的IP文本文件，竖轴表示的是每个待查文本文件中所含待查IP的个数。图4-4路由表构造Binary Trie结构所需存储容量本文用构建相应的二叉树所需结点的个数来表示一个路由表所需的存储容量。如图4-4所示，横轴表示不同的路由表文本文件，竖轴表示每个路由表所需的存储空间。图4-5待查路由表项所需的平均查找次数如图4-5所示，横轴表示不同的待查IP文本文件在所对应的路由表中的查找结果，竖轴表示找到与待查IP相匹配的最长前缀所需的平均查找次数。4.3 算法的可扩展性评价由于新一代IP协议IPv6使用长度为128的地址，所以它给本来己经很复杂的最长匹配前缀查找带来了更大的困难，对于目前的32位计算机系统来说，访问一个128地址就需要进行4次读写操作，查找速度会大大降低。Trie树的查找复杂度为O(W/K)，其中lKW。如果W从32增加到128，在K不发生变化的前提下，算法的查找性能将下降到原来的1/4。为了能够提高查找性能，唯一的做法就是提高K的大小。但是，从算法存储容量的复杂度来看，增加K的大小势必会增加算法的存储空间，从而影响算法在实际系统中的使用。基于Trie结构的查找方案结构简单，易于实现，因此，在IPv6占主导地位的将来，研究基于Trie的IP路由查找方案有不错的发展前景。5 结论5.1 全文总结随着信息技术的高速发展，因特网承载的业务越来越丰富，加之人们对网络的依赖程度不断增加，使得骨干网对带宽的需求越来越大，而在对骨干网的扩展中，最为关键的是核心路由器性能的提升，这就要求核心路由器每秒能转发几百万甚至更多的分组，快速路由查找技术成为路由器报文转发的瓶颈。因此如何实现路由表的高速查找和更新就成为研究的难点。同时随着IPv6技术的逐步成熟和推广，也进一步要求提升路由查找的性能。目前常用的路由查找算法分为软件实现和硬件实现两类，硬件方面主要围绕CAM和TCAM展开;基于软件算法主要包括树形结构为主体的Trie算法及其变种算法：Binary Trie的路由算法、路径压缩Trie算法、多分支Trie算法、级压缩Trie（LC-Trie）、位图压缩（Bitmap-Compressed）Trie算法其他压缩算法和以表结构为主体的基于前缀长度二分查找和地址区间二分查找算法相关研究。这些算法一定程度上解决了路由查找速度的技术问题，但是还存在结构复杂，插入和删除表项的难度较大，难于解决空间复杂度和时间复杂度之间的关系。本论文重点研究了基于Binary Trie的IP路由查找算法，第二章对该算法进行综述，定性的了解了该算法的优缺点；第三章对该算法进行逻辑实现，并对该算法的主要函数做了介绍并附有相应流程图；第四章通过实验数据对该算法做了相应的定性分析。5.2 改进方案该算法不能根据路由表的实时更新插入新的路由信息或删除无用的路由信息，下一步可以在此基础上实现该插入新的路由信息和删除无用路由的工作。因为该算法的存储器访问次数较高，并不非常高效，随着IPv6应用的不断扩大，应该考虑如何实现与硬件结合，实现路由的快速查找。致 谢首先要感谢我的指导老师，在他的正确指导下我顺利的完成了毕业设计的任务。在毕业设计过程中，指导老师帮助我搜集了许多相关资料，帮助我解答了设计中遇到的许多专业问题。他坚持每周五给我们进行相关答疑，启发开拓我们的设计思路，并敦促我们完成相应的工作任务。几个月来，指导老师严谨的工作作风深深地感染着我，在此谨向老师致以崇高的敬意和诚挚的谢意。再次是要感谢和我一起完成毕业设计的同学们，特别是和我是同一个指导老师的同学们还有我亲爱的舍友们，正是有了他们，我才可以解决毕业设计中遇到的种种困难，我们之间的互相帮助，互相探讨最终圆满地完成了毕业设计。最后，衷心地感谢学校给我提供了良好的学习条件，让我在这度过了四年难忘的大学生活，感谢我校图书馆及电子数据库给我们提供了国内外众多的参考文献和良好的学习环境，以及学校提供的固定的毕设实验室网络教研室，使我有良好的条件完成毕业设计。参考文献1 中国互联网络发展状况统计报告 2010年1月 2 nternet World Stats.Internet Usage and Population Statistics Report(Dec 2009).3 Huston G.BGP Route Table Analysis Reports(March 2010). 4 Knuth D.Fundamental Algorithms Vol.3:Sorting and Searching. Addison-wesley 19735 Morrison D R.PATRICIA-Pratical Algorithm to Retrieve Information Coded in Alphanumeric.Journal of ACM,1968,15(4):5145346 Sklower K.A Tree-based Routing Table for Berkeley Unix.Technical report,University of California,Berkeley,USA,19937 Nilsson S and Karlsson G.IP-Address lookup using LC-tries.IEEE Journal on Select Areas of Co