资源描述：
《路由查找算法研究综述》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、1000-9825/2002/13(01)0042-09©2002JournalofSoftware软件学报Vol.13,No.1路由查找算法研究综述Ã徐恪,徐明伟,吴建平,吴剑(清华大学计算机科学与技术系网络研究所,北京100084)E-mail:xuke@tsinghua.edu.cn;xmw@csnet1.cs.tsinghua.edu.cnhttp://netlab.cs.tsinghua.edu.cn摘要:随着Internet的迅猛发展,用于主干网络互联的核心路由器的接口速率已经达到了2.5Gbps~10Gbps.这一速率要求核心
2、路由器每秒能够转发几百万乃至上千万个以上的分组.分组转发的重要一步就是查找路由表,因此快速的路由查找算法是实现高速分组转发的关键.路由查找需要实现最长前缀匹配.近年来,研究人员提出了多种路由查找算法,以提高查找性能.分析了路由查找问题及其难点,全面综述了各种查找算法,并对它们进行了详细的分析和比较,最后指出了进一步的研究方向.关键词:路由查找;最长前缀匹配;Trie树;哈希;CAM中图法分类号:TP393文献标识码:A路由器的主要功能是按照IP分组中的目的地址转发分组.查找路由表决定将分组发往哪个端口,这是转发分组过程中的重要一步.因此,快
3、速的IP地址查找算法是实现高速分组转发的关键.传统的查找方法(如顺序查找法、二分查找法)只能完成关键字的精确查找,而路由查找需要完成最长匹配地址前缀的查找.为了提高路由查找的性能,研究人员提出了多种路由查找算法.本文首先分析了路由查找问题和实现难点,然后全面综述了各种查找算法,并对它们进行了详细的分析和比较.1Internet地址结构的发展在Internet的发展初期,IPv4地址采用的是基于类的地址结构.整个IP地址空间一共分为5类:为单播地址设计的A,B,C类;为组播地址设计的D类;为今后使用而保留的E类地址.各个类之间由地址的前几个比
4、特位来区分.在Internet发展的初期,基于类的地址结构由于其简单性而得到了广泛的应用.但是,随着网络的不断发展,使用这种地址结构产生了两个问题.一个问题是地址分配的不灵活导致了地址空间的大量消耗以及路由表规模的不断增大.基于类的地址结构将整个地址空间简单地分成了5个类别,这就导致了地址的分配非常不灵活.另一个问题是,由于路由器需要记录所有已经分配的网络地址,特别是对于C类地址来说,由于它的地址前缀特别多,如果记录所有的C类地址,那么路由表的规模将变得非常大.为了降低路由表规模的增长速度以及提高地址空间的利用率,IETF提出了一种称为无类
5、域间路由[1~2](classlessinter-domainrouting,简称CIDR)的地址结构.CIDR摒弃了传统上基于类的地址分配方式,规定可以使用任意长度的网络地址部分,因此产生了路由地址前缀的概念.使用CIDR的好处是明显的,它提高了地址空间的利用率,例如为300台主机分配网络地址只需使用一个23位网络地址前缀长度的网络地址(可以支持Ã收稿日期:2001-05-30;修改日期:2001-09-14基金项目:国家自然科学基金资助项目(90104002);国家863高科技发展计划资助项目(863-306-ZD-07-01)作者简介
6、:徐恪(1974－),男,江苏洪泽人,博士,讲师,主要研究领域为计算机网络体系结构,分布式路由器操作系统,高性能路由器体系结构;徐明伟(1971－),男,辽宁朝阳人,博士,副教授,主要研究领域为计算机网络体系体系结构,高性能路由器体系结构,网络性能测试;吴建平(1953－),男,山西太原人,博士,教授,博士生导师,主要研究领域为计算机网络体系结构,计算机网络协议测试,形式化技术;吴剑(1977－),男,浙江杭州人,硕士,主要研究领域是高速路由查找算法,分布式路由协议.徐恪等:路由查找算法研究综述43512台主机)就可以满足要求.为了满足网络
7、规模不断增长的需要,IETF设计了新一代的网络协议IPv6,也被称为IPng.IPv6与IPv4相比,在地址格式上发生了巨大的改变,地址长度由原来的32位变成了128位,相应地,IPv6在整个地址分配上也进行[3]了一定的改进.尽管IPv6的地址结构与IPv4相比有很多的不同之处,但是从根本上来说,整个地址空间仍然是层次性结构,仍然支持类似于IPv4CIDR地址结构下的路由合并,因此新一代的网络协议并没有改变路由查找的本质特点.2路由查找算法分析2.1路由查找算法的分类最长地址前缀匹配查找的难点在于,在查找过程中不仅需要与地址前缀的比特值进
8、行匹配查找,而且还需要考虑地址前缀的长度,因此各种路由查找算法都可以归结为这两个方面的匹配查找过程.2.1.1基于地址前缀值的路由查找算法基于地址前缀值路由查找算法的特点是通过对
