（计算机应用技术专业论文）ipv6路由查找算法研究.pdf

南京邮电大学硕士研究生学位论文 摘要 摘要 随着i n t c m c 吐的发展，路由信息不断增加，路由表急剧膨胀，路由查找问题越来越成 为影响网络通信速度的瓶颈。未来i p v 6 的应用将会使这一问题更加明显，而当前已有的算 法很难满足i p v 6 快速路由查找的要求。 本文在详细分析了已有路由查找算法的基础上，对当前i p v 6 骨干路由器的路由表特点 进行分析总结，从而根据i p v 6 路由表的特点设计了一套适合i p v 6 的分布式并行路由查找 框架。该框架由十七路组成，其中十六路是由占了路由前缀数量9 7 以上的，长度在 3 2 6 4 ( 包括3 2 和6 4 长度) 之间的路由前缀组成；第十七路采用t c a m ( t e m a r yc o n t e n t a d d r e s s a b l em e m o r y ) ，其存放长度小于3 2 和大于6 4 的“其他 前缀，t c a m 为硬件实现， 其查询速度很快，不会影响并行框架的整体性能。十六个分路存储的路由前缀是根据路由 前缀的特征比特划分的，这种机制使得分布式并行框架能够同时对十六个不同的i p v 6 地址 进行路由查找。对于这十六个分路其中任一分路，本文设计了段表，偏移量表和路由桶的 数据结构，这种数据使得路由查找平均只需要l - 2 次的存储器访问操作，实现了快速的路 由查找，满足未来高速链路的转发要求。该算法对未来路由的发展具有很好的适应性。 论文对所提出算法的软件部分进行了编程实现，同时实现的还有经典的r a d i xt r i e ， l c - t r i e 和新的t s b ( t r e e ，s e g m e n tt a b l ea n dr o u t eb u c k e t ) 算法，并与论文所提出的算法进 行性能比较，实验比较结果再次表明，本文所提出的算法在路由查找，路由更新，存储器 需求和适应性方面具有很好的性能。 最后，总结了本文提出的方案，并明确了未来工作方向。 关键字：i p v 6 ，并行算法，分布式计算，路由查找 南京邮电大学硕士研究生学位论文 a b s t r a c t i n t e m e ta d d r e s sl o o k u ph a sb e c o m ea ni n c r e a s i n g l yc h a l l e n g i n gp r o b l e mb e c a u s eo f i n c r e a s i n gr o u t i n gt a b l es i z e s ，i n c r e a s e dt r a f j 6 i c ，h i g h e rs p e e dl i n k sa n dt h em i g r a t i o nt o12 8 - b i t i p v 6a d d r e s s e s i pm u t i n gl o o k u p ss h o u l df i n dt h er o u t i n ge n t r y 、 ，i 也t h el o n g e s tm a t c h i n gp r e f i x ， f o rw h i c ho r i g i n a ls o l u t i o n sw e r eb e l i e v e dt ob ei n a p p l i c a b l e a p a r a l l e lf r a m e w o r ku s i n gd i s t r i b u t e dm e m o r yo r g a n i z a t i o n ( p f d m o ) i sp r o p o s e db a s e d o nas u f f i c i e n ts t u d yo nt h ec h a r a c t e r i s t i c so ft h el p v 6a d d r e s ss t r u c t u r e ，t h ei p v 6a d d r e s s a l l o c a t i o np o l i c i e s ，a n dt h er e a lw o r l dl p v 6b a c k b o n eb g pr o u t i n gt a b l e s t h ep a r a l l e l f r a m e w o r kc o n s i s t so fs e v e n t e e nb r a n c h e s ，s i x t e e no fw h i c hs t o r et h e3 2 - 6 4l e n g t h sp r e f i x s a c c o u t i n gf o rm o r et h a n9 7p e r c e n t , a n dt h er e s i d u a lo n en a m e dt c a m s t o r e st h eo t h e rl e n g t h s p r e f i x s t h et c a mb r a n c hs t o r e so n l yaf e wm u t i n gp r e f i x e s ，s oi t c a na c h i e v eam u c hf a s t e r l o o k u ps p e e x i tm e a l 3 st h a tt h et c a mb r a n c hw o u l dn o tb et h eb o t t l e n e c ko ft h ep a r a l l e l f r a m e w o r k t h ec h a r a c t e r i s t i c so ft h er e a lw o r l di p v 6b a c k b o n eb g pr o u t i n gt a b l e ss h o wt h a t t h ep r e f i x e sf r o m3 2t o6 4l e n g t h sc a nb ec l a s s i f i e di n t os e v e r a lf l o w se v e n l yd e p e n d i n go n c e r t a i nb i t so ft h e m t h i sm e c h a n i s mp r o v i d e sl o o k u pf o ram a x i m u mo f16i p v 6a d d r e s s s i m u l t a n e o u s l y ad a t as t r u c t u r e 谢也s e g m e n tt a b l e ，o f f s e tt a b l ea n dr o u t eb u c k e ti sp r o p o s e d t a k i n go n l ya na v e r a g eo f1 - 2m e m o r ya 雠s s e sf o ri p v 6a d d r e s sl o o k u p b yu s i n gt h ep r o p o s e d p a r a l l e lf r a m e w o r k , ar o u t e rc 趾a c h i e v em u c hh i g h e rt h r o u g h p u tr a t e ，敝：a l eb e t t e r , s u p p o r t i n c r e m e n t a lu p d a t ea n ds a t i s f yt h er e q u i r e m e n t so ff u r t h e rh i g hd a t al i n ks p e e d i m p l e m e n to fs o f h n a r ep a r to ft h i sa l g o r i t h mw a sd o n e a tt h es a mt i m et h ec l a s s i c sr a d i x t r i e ，l c - t r i ea n dt s ba l g o r i t h m sw e r ea l s oi m p l e m e n t e dt ob ec o m p a r e dw i t ht h ep r o p o s e d a l g o r i t h m t h er e s u l t ss h o wt h a tt h ep r o p o s e da l g o r i t h me x c e l si nf o l l o w i n ga s p e c t s ：e x c e l l e n t f a s tl o o k u ps p e e d ，c o m p e c t i v eu p d a t es p e e d ，s t a b l em e m o r yc o n s u m p t i o na n dg o o da d a p t a b i l i t y t og l o b a ld e p l o y m e n to fi p v 6 a tl a s t , t h et h e s i sn o to n l ys u m su pt h ep r o p o s e ds c h e m e s ，b u ta l s op o i n t so u tt h er e s e a c h d i r e c t i o ni nf u t u r e k e y w o r d s ：i p v 6 ，p a r a l l e la l g o r i t h m ，d i s t r i b u t e dc o m p u t i n g ，r o u t i n g l o o k u p 南京邮电大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研 究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致 谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果， 也不包含为获得南京邮电大学或其他教育机构的学位或证书而使 用过的材料。与我一同工作的同志对本研究所做的任何贡献均己在 论文中作了明确的说明并表示了谢意。 研究生签名：名避日期： 南京邮电大学学位论文使用授权声明 ，勺矿阀 南京邮电大学、中国科学技术信息研究所、国家图书馆有权保 留本人所送交学位论文的复印件和电子文档，可以采用影印、缩印 或其他复制手段保存论文。本人电子文档的内容和纸质论文的内容 相一致。除在保密期内的保密论文外，允许论文被查阅和借阅，可 以公布( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊 登) 授权南京邮电大学研究生部办理。 魏坦熟期：学留盆 南京邮电大学硕士研究生学位论文 第一章绪论 1 1 课题的目的与意义 第一章绪论 随着h l t i 跚斌规模的急剧膨胀【l 】，i n t e m e t _ j = 的主机数目成指数方式增长，应用业务的多 元化导致网络流量的迅速增加，电子商务的应用对网络安全提出了更高的要求，2 0 多年前 提出的口v 4 网际互联协议版本在许多方面已不再适应。i p v 6 正是人们对口v 4 协议的地址空 间，性能以及安全性等方面提出更高要求的情况下提出来的。 ， 另一方面，i n t e r n e t 流量平均三个月翻一翻【2 l ，为了消除网络流量增加带来的影响，保 证i n t e m e t 的服务质量，必须让数据包能够及时转发。影响数据包转发速度的主要因素有三 个：链路传输速度，路由器的数据处理能力和路由查找速度。前两个因素都已经存在较好 的解决方案，例如，光纤的广泛应用可以保证链路的传输速度；交换技术( 刚讹h ) 网能够使 路由器以g 比特每秒的速度将数据包从输入端口转移到相应的输出端口。现在，第三个因 素已成为数据包转发速度的瓶颈。 当前已有的p 路由查找算法几乎都是针对m v 4 的，而其中的绝大多数不适合于i p v 6 ， 因此，有必要进行针对i p v 6 的高速路由查找算法的研究，提出适合i p v 6 的高速路由查找算 法。 1 2i n t e r n e t 地址结构的发展 在i n t e m e t 初期，口地址是分类的地址结构，其中a ，b c 类为单播地址，d 类为组播 地址和为将来保留的e 类地址 4 1 。每类地址都是简单两层体系结构，顶层为网络号字段，底 层为主机号字段。网络号标识某个特定的网络，路由表里面的每条前缀就是一个网络号， 主机号标识特定网络里面的一台主机。a 类地址的网络号字段以o 开头，占一个字节；b 类 地址的网络号字段有两个字节，前面两比特( 1 0 ) 已经固定；c 类地址的网络号字段占3 个字 节，最前面3 个比特是1 1 0 。因为这种简单的分类地址结构，所以我们运用传统的h a s h 或t r e 算法就可以很好地实现路由查找算法。但是，随着i n t e m e t 的不断发展，传统的分类地址结 构就越来越凸显两个问题。第一，因为地址以分类网络为单位进行分配，地址最少的c 类 网络也有2 5 6 个主机号，即使一些用户只需要少量的几个地址也得申请一个c 类地址，这样， 地址的使用效率很低第二，以分类网络为单位的地址分配方式，使得主干路由器的路由 南京邮电大学硕士研究生学位论文篁二童! 堕鲨 条目急剧上升，导致路由查找时间增加，所需的存储容量增大。 为了提高m 地址空间的使用效率以及减缓地址前缀在骨干路由内的增长速度，i n t c m c t 工程任务组( i e t f ) 提出一种叫无类别域问路由( c d r ) 【5 羽的地址分配方式。c i d r 摒弃了传 统的地址分配方式，规定可以使用任意长度的网络地址部分，因此产生了路由地址前缀的 概念。使用c i d r 的好处是明显的，它提高了地址空间的利用率，例如为1 7 台主机分配网络 地址只需使用一个2 7 位网络地址前缀长度的网络地址( 可以支持3 2 台主机) 就可以满足要 求，并不是一定需要一个c 类地址，大大节省了地址空间。 为了满足网络规模不断增长，各种业务不断涌现，安全等问题的需要，i e t f 设计了新 一代的网络协议i p v 6 ，也被称为i p n g 。i p v 6 与i m 相比，在地址格式上发生了巨大的改变， 地址长度由原来的3 2 位变成了1 2 8 位，相应地，i p v g 在整个地址空间的分配上也进行了一定 的改进川。尽管i p v 6 的地址结构与m v 4 相比有很多的不同之处，但是从根本上来说，整个 地址空间仍然是层次性结构，仍然支持类似于1 p v 4c i d i 跳址结梅下的路由合并。因此， 新一代的网络协议并没有改变路由查找的本质特点。 1 3i p v 6 地址体系结构 1 3 1ip v 6 地址表示 p v 6 地址1 2 & 位，是l l ： v 4 地址长度的四倍，r f c l 8 8 4 规定的标准语法建议把i p v 6 ：地址的 1 2 8 位( 1 6 个字节) 写成8 个1 6 位的无符号整数，每个整数用四个十六进制位表示，这些数之 间用冒号分开，例如：2 0 0 1 ：2 0 0 2 ：1 内1 ：l ：2 8 0 ：6 7 0 2 ：f e 4 d ：3 e e f 某些脚6 地址中可能包含一长串的0 。当出现这种情况时，标准中允许用“空隙 来表示这一长串的0 。换句话说，地址：2 0 0 1 ：0 ：0 ：0 ：0 ：0 ：0 ：1 可以被表示为：2 0 0 1 ：1 这两 个冒号表示该地址可以扩展到一个完整的1 2 8 位地址。在这种方法中，只有当1 6 位组全部 为o 时才会被两个冒号取代，且两个冒号在地址中只能出现一次。 由于i p v 6 地址被分成两个部分即子网前缀和接口标识符，因此人们希望一个印节点地 址可以按照类似c d r 地址的方式被表示为一个携带额外数值的地址，其中指出了地址中有 多少位是掩码，r i j i p v 6 节点地址中指出了前缀长度，该长度与i p v 6 地址间以斜杠区分，例 如：2 0 0 1 ：2 0 0 ：e 0 0 0 3 5 这个地址中用于选路的前缀长度为3 5 位。 2 南京邮电大学硕士研究生学位论文 第一章绪论 1 3 2ip v 6 地址类型 r f c l 8 8 4 定义了三种类型的m v 6 地址：单播胁i c a 哟、多播( m u l f i c 嬲t ) 和任播( a n y c a s 0 ， 分别占用不同的地址空间。1 1 6 的a n y c a s 抛址是肌4 所没有的，并以多播地址代替了口v 4 中的广播地址。本文介绍的算法主要针对单播路由。 r f c 3 5 8 7 定义了最新i p v 6 可聚集全球单播地址嘲，如图1 1 所示，该地址格式包括了三 个部分：4 5 位的全球路由前缀( 起始3 位总是“0 0 1 一) ，1 6 位的子网标志符，以及6 4 位的接 口标志符。全球路由前缀定义了一个站点，子网标志符定义了某个站点中的一个子网，而 接口标志符特指一个子网中的一个网络接口。通常，只有全球路由前缀和子网标志符是用 于路由的。 3b i t s 4 5b i t s1 6b i t s 6 4b i t s 1 3 3lp v 6 地址分配策略 图1 1 全球单播i p v 6 地址结构 由于i p v 6 采用了按层的地址分配思想，如图1 2 所示，i a n a 分配2 3 给r e g i o n a li n t e m e t r e g i s t r i e s ( r i r ) ，r i r s 以3 2 为单位向l 0 c a li n t e m v tr e g i s t r i e s ( l i r ) 或i n t e m e t s e r v i c e p r 嘶d e 町s p ) 分配，而最终用户则需要向l 承或i s p s 申请4 8 为单位的地址块，有时会更具用 户的需求和规模分配6 4 和1 2 8 为单位的地址。此外亚洲在r i r 和l i r 之间还有n a t i o n a l i n t e m e tr c g i s t r i c s 0 n m ) ，因此d 阳6 路由表也会呈现和m v 4 路由表相似的统计分布特征。 i n t e r n e ta s sig n e dn u m b e r s a u t h o r it y ( i a n a ) r e g i o n a li n t e r n e tr e g i s t r i e s ( r i r ) n a t i o n a li n t e r n e tr e g i s t r i e s ( n i r ) i n t e r n e ts e r v i c ep r o v i d e r ( i s p ) l o c a li n t e r n e tr e g is t r i e s ( l i r ) e n du s e r s ( e u ) 图1 2 脚6 地址分配层次结构 3 南京邮电大学硕士研究生学位论文 第一章绪论 同时，已经有机构建立了相应的规范以指导口v 6 地址的分配，比如i a b i e s g 建议【9 1 和 由对r s 联盟发布的脚6 地址分配和指派政策【埘，这都将使l p v 6 路由表更完美地体现清晰的 层次关系。 1 4i p 路由查找的定义 当p 数据包进入路由器时，路由器根据p 数据包头中的目的m 地址，在路由表( r o u t i n g t a b l e ，又称前缀表p r e f i xt a b l e ) 中查找相应的输出端口( p o r t ) 和下一跳地址眦h o p a d d r e s s ) ，以便将i p 数据包从输出端口送到下一跳路由器或者目的主机。在路由表中查找目 的口地址的下一跳信息的动作就是m 路由查找( ma d d r e s sl o o k u p ) 。在按类划分地址的 i n t e m e t 初期，查找过程是非常简单，且容易实现的。首先通过目的口地址的前几个比特判 断确定其是属于a ，b 还是c 类地址，然后在对应的类别的前缀中查找匹配前缀，这种查找 叫做精确匹配查找( e x a c tm a t c hs e a r c h ) 。当采用c d r 后，前缀长度可以是任意长度，路由 表中就有可能找到多个匹配的前缀，因此需要在所有匹配的前缀中选择长度最大的前缀作 为最终的查找结果，即进行最长前缀匹配( l o n g e s tp r e f i xm a t c h , l p m ) ，而结果前缀被称为 最长匹配前缀( l o n g e s tm a t c h e dp r e f i x , l p m ) 。尽管i p v 6 的地址结构与m v 4 相比有许多不同 之处，但整个地址空间还是层次性结构，仍然存在类似于i p v 4 的c i d r 地址结构下的路由合 并，h v 6 路由查找同样是l p m 闯题。 下面将以i p v 4 为例，给出l p m 形式化的定义。 表1 1 示例路由表 嚣零夏鼯硒滋镒镒隘畿鹱蠲委翟箩罗零鬻黼筇罗戮鬻穹露獬u ti n t e r f a c e ：, 缀缓糍谚茏i 统碰二勰一舻i ! ；爱二鬈：7 z ：撕糌：红而；。篡押：，二 ；：孙女爱谚：，一：i ? 17 一? 州i ； 刹，夤。韬，i ，i 耐* 一；# j ，。；一：j “， 岬躺缆l 童罄蚕 2 3 4 0 3 2 2 01 9 3 4 1 1 7 7 1 4 8 2 1 3 0 8 6 1 61 9 3 4 1 1 7 7 1 8 16 2 0 8 1 2 1 6 2 01 9 3 4 1 1 7 7 2 4 1 3 2 0 8 1 2 2 1 2 31 9 3 4 1 1 7 7 1 9 6l 1 6 7 2 4 1 0 3 2 4 1 9 3 4 1 1 7 7 3 3 当目的地址是2 0 8 1 2 2 0 1 5 7 的i p v 4 数据包进入路由器( 其路由表如表1 1 所示) 时，路由 查找算法将找到与目的m 地址相匹配的前缀有2 0 8 1 2 1 6 2 0 和2 0 8 1 2 2 1 2 3 。但因为路由查找 需要l p m 查找，且后者长度是2 3 比前者2 0 长，所以算法选择2 0 8 1 2 2 1 2 3 作为最终查找结果。 接着，路由器根据前缀2 0 8 1 2 2 1 2 3 所在行信息，把数据包从接口l 发送到下一跳路由 1 9 3 4 1 1 7 7 1 9 6 。当然，转发过程还需要地址转换协议【4 】c a 剐h s sr e s o l u t i o np r o t o c o l ，a r p ) ， 4 南京邮电大学硕士研究生学位论文第一章绪论 1 5 路由查找的主要困难 根据妒路由查找的定义，路由查找的主要困难可以分为三类： ( 1 ) l p m 问题本身造成的困难 ( 2 ) 问题规模造成的困难 ( 3 ) 实时性要求造成的困难 下面逐一进行描述。 1 5 1l p m 问题造成的困难 c i d r 被采用之后，口查找不仅在前缀值( p r e f i xv a l u e ) ，而且还需要在前缀长度( p r e f i x l e n g t h ) 这两个维度上查找，故不能采用基于类别的精确匹配查找算法相同的简便方法，这 使得路由查找变得异常困难，也就是说，由于m 数据包中没有前缀长度信息，所以，只有 查找完整个路由表后才能保证找到最长匹配前缀。 图1 3 所示，前缀2 0 8 1 2 2 l 2 3 ，2 0 8 1 2 1 6 2 0 相互重叠，对于目的l p v 4 地址2 0 8 1 2 2 0 1 5 7 ， 从前缀值来看2 0 8 1 2 2 1 2 3 和2 0 8 1 2 1 6 2 0 都是匹配前缀，从前缀长度来看2 0 8 1 2 2 1 2 3 大于 2 0 8 1 2 1 6 2 0 ，所以查找结果为2 0 8 1 2 2 l 趁3 。 图1 3l p m 问题的主要困难 5 南京邮电大学硕士研究生学位论文第一章绪论 1 5 2 问题规模造成的困难 问题规模主要来源于两个方面，一个是路由表路由条目数量的迅速膨胀，另一个是i p v 6 地址变长，其二进制表示为1 2 8 位，四倍于i p v 4 地址。 以目前路由前缀的规模计算，典型的i n t e r n e t 核心路由器的l p v 4 路由表包含约为l o o k 到 2 s 0 1 d e 右的前缀项，虽然由于l p v 6 未大规模部署使得目前l p v 6 核心路由表大约只包含1 k 左 右的前缀项目，但预计i p v 6 路由表前缀项应在5 0 0 k 左右。由于l p m 必须处理前缀表中所有 的前缀，如此大规模的前缀表使l p m 变得更加困难，这就要求路由查找算法在前缀表的规 模快速增长时具有良好的可扩展性。 图1 4 中的统计数据来源于g e o f fh u s t o n 的i p v 4b o p ( b o r d e rg a t e w a yp r o t o c 0 1 ) 路由表分 析报告【l ，可以看出，聃4 前缀表的规模成近似指数增长，目前i n t e r a c tb g p 路由器前缀数 量一般在2 4 0 i 阶左右。 心卅 i em一 j k f础 ： ： ： ： 曩雏孵戗越帽蝤酊 o 譬 图1 41 9 9 4 年至今i n t e m e tb g p 路由表的增长 另外一个规模是从查找宽度来看，m v 4 路由查找需要处理的目的地址宽度为3 2 位，而 i p v 6 地址的宽度增加到了1 2 8 位，这必然对i p v 6 路由查找造成困难和挑战。 1 5 3 实时性要求造成的困难 目前己经出现了4 0 g b p s ( g i g a b i tp e rs e c 0 n d ) 数量级的高速网络，1 6 0 0 b p s 数量级的更高 速网络己处在研究阶段，网络的性能瓶颈己从原先的传输媒体带宽逐渐转移到主机和以交 换机、路由器等网络设备为代表的传输设备上，尤其是路由设备。高速数据传输链路的出 6 一 一 一 富旨曼童盒羔蔓 南京邮电大学硕士研究生学位论文第一章绪论 现，使得路由器进行线速转发( 即按照数据包达到的速率进行转发) 的条件越来越苛刻。 通常来说，典型的路由器对每个分组的处理操作包括接收分组、协议识别及分类、分 组过滤、分段、前缀查找、服务质量控制、分组调度和分组发送等。路由查找操作的时间 只能占“每分组处理时间 的一部分，这对路由查找算法的性能提出了很高的要求。与此 同时，线路速率和c p u 计算能力、内存系统带宽之间的差距还在不断扩大。在过去的1 0 年 中，由于通信技术的高速发展，物理层传输速度呈指数级增长，而且将继续以每年4 倍的 速度增长，这一增长速度远远超过了处理器性能的增长速度，从而导致处理器速度和传输 媒体带宽之间的差距越来越大。以1 0 g b p s 的1 0 g e 线路和6 4 字节p v 4 数据分组( 假设为以太 网的情况) 为例，路由器必须在5 1 2 n s 内处理完分组并将分组传送到相应的网络接口上。根 据相关的统计数据，对于r i s c 处理器来说，处理这样的一个l p v 4 数据分组至少需要1 6 0 0 条 r i s c 指令。若采用一个1 5 g h z 频率的r i s c 处理器，假设一个时钟周期可以执行一条指令， 则总共需要1 0 6 7 n s 才能处理完成，而这还只考虑了最关键的协议通路处理，诸如q o s 等其 它特性均未考虑。显然，这已经远远超出了5 1 2 n s 的性能预算时间，是不可能达到1 0 g e 线 路的速度要求的即使是1 g b p s 的线路，目前最快的r i s c 处理器所需要的处理时间也大于 线速转发允许的时间。 此外，由于i n t o m e tb g p 路由表的不稳定性【翻，其前缀表更新具有突发性和频繁性，可 能需要路由器每秒处理数百个前缀项的插入、删除或更新，这也对路由查找算法提出了更 高的性能要求。一般来说，i n t e r a c t 核心路由器至少需要具备1 k u p s ( u p d a t ep e rs e c o n d ) 的更 新能力，而实际的实现中一般认为5 k u p s 到1 0 k u p s 的更新速度才是安全的 1 6 论文的主要贡献 本论文l p v 6 高速并行路由查找算法的研究，主要贡献如下： ( 1 ) 给出了口路由查找的定义，分析了当前路由查找的主要困难。 ( 2 ) 对已有的路由查找算法进行了分析总结。 ( 3 ) 提出一种分布式并行m v 6 路由查找框架，设计该并行框架的各路体系结构，包括 路由前缀的存储组织形式和路由查找的h a s h 函数。 ( 4 ) 对所提出的算法进行编码实现和性能分析，并与现有经典算法进行性能比较。 ( 5 ) 对所做工作进行了总结，并对算法的进一步完善和改进进行了展望。 7 南京邮电大学硕士研究生学位论文 第二章相关算法及性能分析 第二章相关算法及性能分析 e l i n t e r a c t n 世以来，针对肌4 路由查找提出了许多路由查找算法【1 3 1 5 1 ，这些算法的研 究包括从原始的逐前缀项比较，到基于r a d i x e 的逐位比较、基于前缀扩展多比特树的多 位比较、基于r a m 的线性表查找、基于前缀区间的二分查找、基于前缀长度的二分查找和 基于t c a m ( t c r n a r yc o n t e n ta d d r e s s a b l em e m o r y ) 的并行查找。近年来，一些学者根据l p v 6 路由前缀的特点对i p v 6 的路由查找也做了些研究，取得了一定的成果。但是，随着i n t e r a c t b g p 路由器的不断膨胀以及下一代网际协议1 v 6 协议的部署，原有的算法已经不能满足高 速链路转发的要求。 下面，我们将相关算法进行分类介绍，并分析性能，以便为后续章节奠定基础，最后 进一步从路由查找速度，表项更新速度，存储容量需求及对i p v 6 的适应性等方面对各算法 进行分析和比较，具有重要的指导作用。 2 1 路由查找算法常用的辅助策略 为了提高算法的效率，最近提出的算法中都使用了一些辅助策略。其中的一些策略将 在本章所介绍的算法当中运用。 2 1 1 前缀扩展( p r e f i xe x p a n s i o n ) 地址前缀是一系列主机地址或者网络地址的合并，因此，地址前缀的信息涵盖了所有 这些主机或者网络地址的转发信息，所以我们可以把一条长度较短的前缀扩展成多条地址 前缀较长的前缀集，前缀集内任一路由前缀的路由信息继承自较短前缀的路由信息【1 6 1 。 下面将举例说明如何对前缀进行扩展，从而减少前缀长度数目。表2 1 显示路由表在进 行可控扩展前有7 种长度的前缀，长度分别是l 至7 。这里希望把把前缀扩展成只有三种长 度( 2 ，5 ，7 ) 的等价前缀集。前缀p 4 长度为1 ，它将扩展成与它的长度最近的被允许的长度的 前缀集，即长度是2 的前缀集。因为p 2 = 1 代表以1 开头的所有地址，所以它扩展成与它等 价的前缀集0 0 ，1 1 ) 。扩展后的等价性是显然的。等价集内前缀的路由信息继承自被扩展 前缀，1 1 奎的路由信息来自p 2 = l 。表中括号中的前缀是扩展后前缀的导出前缀，扩展后 的前缀的下一跳地址信息应该与其导出前缀相同。但是，从表中可知，扩展后的前缀1 0 的路由信息并不来源于p 2 = l ，而是来源于p 3 = 1 0 。由p 2 = 1 导出的前缀1 0 与尚未扩展 8 南京邮电大学硕士研究生学位论文第二章相关纂鲨墨壁堕坌堑 的前缀p 3 重复，称前缀p 3 捕获了扩展出的前缀。这种短前缀在扩展后与长前缀相重叠的情 况称为前缀捕获f i xc a p t u r e ) 。前缀捕获现象发生说明，扩展前前缀在地址空间上存在重 叠现象，按最长前缀匹配的要求，应该选择最长的匹配前缀，即保留尚未扩展的前缀。所 以在表2 1 中扩展后的前缀列的前缀1 0 的路由信息来自p 3 ，而不是p 2 。 表2 1 前缀扩展 原路由前缀 扩展后的前缀 p l = o 木0 0 ( p 1 ) p 2 = 1 木0 1 ( p i ) 长度2 p 3 = 1 0 1 0 ( p 3 ) p 4 = 1 1 1 宰 1 1 , ( p 2 ) 1 p 5 = 1 0 0 0 1 1 1 0 0 * ( p 4 ) p 6 = i1 0 0 1 i i1 0 1 ( p 4 ) p 7 = 1 0 0 0 0 0 1 111 0 * ( p 4 ) p 8 = 1 0 0 0 0 0 0 , i i i i i * ( p 4 )长度5 1 0 0 0 0 ( p 5 ) 1 0 0 0 1 ( p 5 ) 1 1 0 0 1 ( p 6 ) 1 0 0 0 0 0 0 ( p 8 )f 长度7 1 0 0 0 0 01 , ( p 7 ) 2 1 2 独立前缀转化( d i s j o i n tp r e f i xt r a n s f o r m a t i o n ) 最长前缀匹配要求寻找与目的地址相匹配的前缀中的最长的前缀，这个也是路由查找 的难点。一种避免进行最长前缀匹配规则但仍能找到最长匹配前缀的方法就是将地址前缀 集转化为一些独立的前缀集。在独立前缀集内不存在一条前缀是另一条前缀的前缀的情 况，因此只要找到匹配前缀就可以返回，不需要继续查找。在根据独立前缀集构造的t i l e 树中，所有对应的前缀都出现在叶子结点。 2 1 3 压缩技术 压缩技术试图从编码中删除数据的冗余信息，对t r i e 树使用压缩技术主要是考虑到1 m ： 树的扩展转化过程大大增加了信息的冗余度，因此可以使用一定的压缩算法将信息的冗余 度降低。当然，压缩方法应该不仅能缩小整个e 树的存储空间，而且还应保证从压缩数 据中恢复原有信息的操作不能过于复杂。 9 南京邮电大学硕士研究生学位论文 第二章相关算法及性能分析 2 1 4 优化技术 优化方法能够使我们在一些限制条件的前提下找到满足约束条件的最佳前缀集，比如 说在查找速度的约束下尽量减少算法的存储空剐1 7 1 8 】等。 2 1 5 存储器层次设计 目前我们计算机的存储设备是层次结构的，各个层次上的存储介质在访问速度和存储 容量上存在着差异。如，计算机读写片i - l 1 级缓存的时间为不足1n s e g ，读写l 2 级缓存的 时间为3n s e g ，而访问内存的时间大约为6 0 舔e c 【1 9 1 。如果我们能够把尽可能多的查找表内 容放入c a c h e 中【2 0 1 ，就可以获得更快的查找速度，因此在算法设计中应尽量减少查找算法 数据结构所占据的存储容量。 2 2 经典的路由查找算法 2 2 1r a dixt rie 路由查找算法 r a d i xt d e 也称作简单t r i e ，是一种在每一个分支上标注了值的二叉树，通过前缀中的 每一位比特的值来决定树的分支。r a d i xt r i e 算法最早在n e t b s d 中实现的1 2 1 - 2 2 1 。用t r i e 表示 的前缀并不是存储在t r i e 的节点中，而是用节点间的路径表示前缀，一般前缀中的比特0 用结点到其左孩子结点的路径表示，前缀中的比特l ，用结点到其右孩子结点的路径表 示。因为路由前缀都是由0 ，l 组成，所以适合用t r i e 树表示。图2 1 就是用二进制而e 树结构来表示的地址前缀表。 在t r i e 树中，处于l 层的结点代表了一类地址前l 个比特均相同的地址空间，并且这前 l 个比特串由根结点到这个结点路径上的蚧比特组成。例如，处于第3 层的结点e 就代表了 所有以“1 0 0 开头的地址空间，而比特“1 0 0 是根结点到结点e 路径上的比特按照遍历顺 序所构成。图2 1 中用字母标志的结点表示一个地址前缀，结点中包含了与该地址前缀相关 的转发信息。前缀可以用内部结点( 如a 结点) ，也可以用叶子结点( 如b 结点) 表示。 1 0 南京邮电大学硕士研究生学位论文第二章相关算法及性能分析 前缀 a0 宰 b0 1 0 0 0 c0 1 1 宰 d1 宰 e1 0 0 宰 f1 1 0 0 * g1 1 0 1 h1 1 1 0 i1 1 1 l 木 图2 1 二进制e 树表示前缀 查找时，从目的口地址中读出1 个比特，如果为l ，则下一次查找当前结点的右孩 子结点；如果为0 则查找左孩子结点。如果当前结点代表一条前缀，则记下该点所存 储的下一跳信息，作为当前最长匹配路由信息。就这样一直查找，直到到达树的叶子结点 终止 如果地址长度为w ，r a d i xt i l e 最坏情况下需要o ( w ) 次读取存储器，对于i p v 4 ，i p v 6 来说，分别是3 2 ，1 2 8 次。文献【1 8 】中指出采用2 0 0 m h z 的p e n t i u mc p u ，如果路由表包含3 3 0 0 0 个路由表前缀，平均1 5 u s - 2 5 u s 完成一次查找操作，这几乎不能满足当今链路数据包快速 转发的要求。 2 2 2 多比特t rie 树( m uiribi tt rie ) 路由查找算法 制约路由查找速度的主要因素是存储器的访问次数过多。对于r a d i xt r i e 算法，最坏 情况下需要o ( w ) 次读取存储器，其中w 为地址长度，严重影响查找性能。如果能减少t r i o 的深度，就可以减少存储器的访问次数，提高路由查找的性能。 ( 1 ) 基本原理 一种减少t r i e 树深度的方法，就是增加每次查找的比特数。我们把每一次查找所检查 的比特数称为查找步宽( s t r i d e ) 。步宽可以是固定的，也可以是可变的。一般来说，固定步 宽的多比特t i l e 树实现简单，但浪费存储空间：而可变步宽的多比特t i l e 在实现上复杂些， 但可以节省一定的存储空间。r a d i xt r i o 是步宽为l 的t r i e 树。我们把步宽大于l 的t r i o 树称为多比特t r i e 树( m u l t i b i t t r i o ) 。对于查找步宽为k 的多比特t i l e 树来说，每个结点的 最大子结点数为2 k 。 多比特t i l e 树查找过程的每一步需要检查多个比特，所以它不支持任意比特长度的前 南京邮电大学硕士研究生学位论文 第二章相关算法及性能分析 缀查找。为了能使多比特t i l e 树应用于路由查找中，必须用2 1 1 节所介绍的前缀扩展把 前缀转化成适合多比特t r i e 树查找的长度。 多比特t i l e 树的查找过程与r a d i xt i l e 树查找过程类似，是在每次结点访问过程中把 到目前为止已经匹配上的最长地址前缀记录下来，直至到达树的叶子结点，搜索过程结束。 尽管多比特t i l e 树的查找也是基于地址长度的线性遍历法，但是因为多比特t i l e 树采用的 步宽大于l ，所以其搜索效率大大提高了。 ( 2 ) 多比特t h e 树的优化 多比特t i l e 树的设计的关键是步宽的选择问题，也就是如何在算法查找速度和存储空 间两者之间取得平衡。极端情况下，p v 4 路由查找使用3 2 长度的步宽的多比特t i l e 树只 需要一次内存访问，但是，这需要消耗2 弛个表项空间，是很不现实的。 一种比较合适的方案就是根据实际地址前缀的分布来选择合适的步宽，即根据r a d i x t i l e 树结构来构造多比特t r i e 树。例如，在图2 1 中，前缀d 的右分支子树就是一棵满二 叉树，显然，我们可以用一棵1 层4 分支的t i l e 树来代替这棵2 层二分支的t i l e 树。在这 种情况下，进行前缀扩展转化是很直接的想法。但是，在其他情况下我们如何来进行步宽 选择，就需要我们使用一些特殊的优化策略。s r i n i v a s a n 等人【1 6 3 提出了一种多比特t i l e 树 的优化算法，其出发点是在多比特t i l e 树搜索深度固定的情况下，如何选择合适的步宽以 使整个t i l e 树的存储空间达到最小。在算法设计中，他们根据实际地址前缀的特点使用了 动态规划( d y n a m i cp r o g r a m m i n g ) 的思想来达到优化算法存储空间的目的。 ( 3 ) 多比特t r i e 树的压缩算法 多比特t i l e 树需要通过前缀扩展的方法来建立。在扩展后的前缀集中，前缀的转发信 息被扩展到了t i l e 树的多个结点中，一次信息的冗余度非常高。一些研究人员希望通过数 据压缩的方法来降低这种冗余度，从而降低算法占用的存储空间。 r u n - l e n g t h 压缩法【2 3 】是一种很简单的压缩方法，但是它能够很好的应用于地址前缀查 找问题。文献【2 4 】给出了另外一种有效的多比特t i l e 树的压缩方法一一层压缩 ( l e v e l - c o m p r e s s e d ，l c ) 算法，它将被用于我们的试验仿真比较中。 ( 4 ) 多比特t h e 树的硬件实现 文章 2 5