前缀一种新的IP路由表快速搜索技术

一种新的!"路由表快速搜索技术

曾 斌% ! 邢继峰! 李之棠%

% 华中科技大学计算机科学与技术系武汉 5#""75

!海军工程大学!"5教研室武汉5#""##

89: ;</ =>?@<A@BC?D/<A$EF$FD$AG

摘 要 随着因特网的飞速发展以及%!&位地址的’(46的出现路由表变得日益庞大这给’(目标地址的查找速度提

出了更高的要求。另外最长前缀匹配技术的出现使过去传统哈希搜索技术不再适用。为此论文针对现有’(查找技术的

缺点和不足提出了一种新的二叉搜索算法。文中还对新的路由表数据结构进行了详细描述并给出了该算法的一种软

件实现方案。这种算法具有良好的可扩展性不需要对现有协议进行改动在实践中证明其具有良好的报文转发性能。

关键词 最长前缀匹配 路由 二叉搜索 哈希搜索

文章编号%""!9&##%9 !""#%&9"%579"# 文献标识码) 中图分类号H(#I#

#$%&#’()*+,-. /)* 012, 3)4,+5( 6))7482

9%5( : +5; < =+5( >+/%5(< 6+ 9-+, 15(;

% 3@C;>= :@G= 0J +0 :C?=@> 2A<@GA@ K H@AFG0/01LM?;NF0G1 OG<4@>P<=L 0J 2A<@GA@

;GQ H@AFG0/01 LR?F;G 5#""75

! S;4;/ 8G1 <G@@><G1 OG<4@>P<=LR?F;G 5#""##

#?2,*1@,  ’( >0?=<G1 /00T?C <P ; AF;//@G1<G1 C>0D/@: D@A;?P@ =F@ /0G1@P= : ;=AF<G1 C>@J<U >@V?<>@Q J<GQ<G1 =F@ >0?=<G1

@G=>L F;P D@@G Q<JJ<A?/= J0> =F@ A0G4@G=<0G;/ P0/?=<0GP /<T@ F;PF<G1 =0 Q@;/ E<=F$’G =F<P C;C@> =F@ ;?=F0>P Q<PA?PP =F;=

@U<P=<G1 PAF@:@P F;4@ C>0D/@: P 0J @<=F@> C@>J0> : ;GA@ PA;/ ;D</<=L 1@G@> ;/<=L 0> A0P=$)GQ =F@L Q@PA><D@ ;G 0C=< : ;/ P@;>AF

;/10><=F: D;P@Q 0G C>@A0:C?= ;=<0G =F;= F;P 100Q C@>J0> : ;GA@@UA@//@G= PA;/ ;D</<=L ;GQ Q0@P G0= >@V?<>@ C>0=0A0/

AF;G1@P$HF@ ;?=F0>P ;/P0 C>@P@G= =F@<> G@E >0?=<G1 = ;D/@ Q;= ; P=>?A=?>@ Q@P< 1G@Q J0> V?<AT >0?=<G1 /00T?CP$W;P=/L =F@L

PF0E ; AF@;C J ;P= P0J=E;>@ < :C/@:@G= ;=<0G <GA/?Q<G1 ;/10><=F: =0 D?</Q =F@ Q;= ; P=>?A=?>@$

A%B&)*C2 W0G1@P=X;=AF<G1 (>@J<UY0?=<G1 *<G;>L 2@;>AFM;PF 2@;>AF

% 引言 址与(%最长匹配而头%!位为"%"%%"%"%%"%的地址与(!最

为了保证日益增长的因特网能继续提供快速高效的服务 长匹配。传统的哈希算法对这种最长前缀匹配方式一直没有较有三个关键技术必须跟上发展传输链路的带宽、路由器的数 好的解决办法所以文章描述了一种新的算法在哈希表基础据吞吐率以及报文转发速率。光纤技术和交换技术对前二者已 上通过改进二叉搜索树从而较好地提高了最长前缀匹配的速经起了巨大的推动作用。论文主要解决的问题是如何改进现有 度这种算法最坏情况下的复杂度为" /01 ! !  !为以比特为技术从而提高报文的转发速率。 单位的地址长度 与现有的一些算法相比有较大的优势。

报文转发的关键步骤是读取到达报文的目标地址在路由

表中查找与之匹配的表项最后根据该表项所指向的出口链路 !相关研究

取代,% 这就导致了路由表查找方式由过去的精确匹配发展到 %基于精确匹配的改进方案这种方案一般效率不高详

项其前缀与报文目标地址相应部分匹配而且其长度最长。例 !层次方案这是普遍采用的一种查找方案在*23内

基金项目部委预研项目

作者简介曾斌%I7"9男在读博士研究生海军工程大学计算机技术教研室讲师主要研究领域为计算机移动网络、交互分布仿真。邢继峰

硬件实现’()这种方法需要昂贵的内容寻址存储器而且扩 时间才能找到最佳结果。例如在图!中如果要搜索%%"前缀展性不好。 在中间的哈希表命中 有%%标记项但在第三个哈希表中却

基于协议的解决方案现在的*+交换’ ,)和标记交换技术’-) 搜索失败二叉搜索过程不得不回退到树的上半部分开始在

插入哈希表时可以预计算出该标记项在路由表中的最佳匹配# 二叉搜索的基础方案

基础算法基于以下三个关键方法。一、针对某一地址采用 不必回退了 而是可以直接取2的最佳匹配前缀作为结果即哈希算法检索与之匹配的前缀二、采用二叉树搜索技术降低 可。 如图!中+#前缀在表中的最佳匹配为+%可以把它预先搜索的复杂性三、为了避免搜索失败时引起回退使用了预计 作为+#的结构变量存储当%%"在+#查找失败后可以直接算技术。 把+%的值"作为结果返回。

局

图!基于哈希表的二叉搜索 为根进行搜索。如果在树中找到一个匹配的标记项则从该标

记项指向的优化树开始向下搜索如果找到的匹配项为单纯的

为简便起见 图!中每一个哈希表只有一项分别为" 前缀则搜索结束如果没有找到匹配则向上搜索。"" %%%。假设要搜索%%%二叉搜索从前缀长度的中间开始既 如果对一个*+5(地址进行基本的二叉搜索假设其最佳从长度为!的哈希表开始搜索由于+!不匹配这就需要预先 匹配长度为!%需要检查的步骤为前缀长度%- 命中 !( 未加入一个标记项图中为%% 用它来引导下一步的搜索过程 命中 !" 命中 ! ! 未命中最后到达!%每次命中则向下即当搜索时发现当前哈希表有一个匹配项且其为标记项则 未命中向上。

往树的下半部分继续 否则往树的上半部分搜索。 作者在一开 使用裁剪后的二叉搜索则不同。为简化起见把图中的前始构造二叉树结构的路由表时先对每一个加入的前缀在表中 缀项和标记项记为6 7 8 9 :每一项都以6为前缀 6的前进行一次二叉搜索在成功匹配的路径上依次加入相应的标记 缀简化为 7则记为%%%即以6为前缀%%%为后缀其它

左边的标准树开始检查长度为%’的前缀找到(。以(开始的 8@ 896: ;B" =<:9 C5 :DE >?到达结尾?>

前缀只有)项 长度为%* %& %+ !" !% 所以(中包含的优 设置长度7为896: ;指向的长度 把前

化树树!对搜索范围进行了缩小。在树!中找到, 它包含一 缀1简短为7长度

个新树只有一个长度指向-这样最初为#!位长度的二叉树 8@ 896: ;表中已经包含一项其前缀值为1 =<:9到第二级被裁剪为)个长度第三级则只包含一个长度。 把该项标为标记符 返回

总之该算法不再是仅依赖一个单一的二叉树而是搜索 (968@

一个由各级树组成的互连网。分支决策不再仅仅依靠当前的前 (96@45

缀长度和上次匹配是否成功这两个条件而是借鉴了整个最佳 (96@45

匹配的搜索过程的提示信息。这就意味着在每一个分支处不 )$ ! 改进算法

是仅仅选择下一步搜索方向 而是切换到下一个最优搜索树 构造改进算法的数据结构更为复杂每一个可能的二叉搜上缩小搜索范围。可以通过对当前路由表的前缀分布中预计 索路径都需要优化需要二次遍历来完成这个工作算出最优树。 第一次遍历先建立一个常规的层次树每一个层次树的

为了节省存储空间并提高算法执行效率可以把图#中的 节点9都包含了它的所有子节点 所有以9为前缀的节点 的二叉树进一步简化见图0。只需标出失败时需要搜索的前缀 前缀长度。

长度即可命中时路径已经在树的层次中反映出来了况且作 第二次遍历 把所有的前缀插入到相应长度的哈希表中者只关心下一步的搜索节点没必要存储整个搜索树。 从最短的前缀开始 。对于每一个前缀都计算出它的优化树路

图与现在

当路由表中增加新的前缀项时节点插入过程比过去复杂了。 下一步的工作是改进算法的适应性在不同的网络流量下然而由于在实际运行时指向目标前缀的路由经常变化而加 提供不同的相适应的搜索提示函数以进一步提高算法性能并入新前缀的情况却很少出现所以作者认为在 插入时付出代价 且开发出更快的插入算法。 收稿日期 !""#年% 月而提高整个搜索速度是值得的。

)$% 基础算法 参考文献

为基础算法建立数据结构的过程如下。为了说明方便假 %$389P: ,QFF: 5 := DF$2FDGGF:GG I9= :5RL4SD89 T4Q=89U 2ILTD9 D665 :GG设前缀列表事先按前缀长度的升序排列排序算法可见数据结 DGG8U9S:9= D96 DUU5 :UD=849 G=5D= :UV T,2%)%+  WKX$@=H  > >构的相关书籍 。 6G$89= :598P$9:= > 5@P>5@P%)%+$=;= %++#