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

m 京s f i t ! 人，f 硕十研究，上位论文 摘要 摘要 随着i n t e r n e t 的发展，路由信息不断增加，路由表不断膨胀，路由查找问题越来越成为 影响网络通信速度的瓶颈。未来i p v 6 的应用将会使这一问题更加明显。而当前已有的算法并 不能够很好地解决i p v 6 的路由查找问题。 本文在详细分析了已有的路由算法的基础上，对当前i p v 6 骨干路由器的路由表的特点进 行分析总结，从而根据i p v 6 路由表的特点设计了一套适合i p v 6 的并行查找框架。该框架由 四路组成，其中三路是由占了路由前缀数量9 0 以上的长度为3 2 ，3 5 ，4 8 的前缀组成，第四 路采用t c a m ，其中存放了除长度为3 2 ，3 5 ，4 8 外的其他前缀，t c a m 为硬件实现，其查洵速 度很快，不会影响并行框架的整体性能。对于3 2 ，3 5 ，4 8 三路，本文设计了段表加偏移量表 的数据结构，并设计了相应的h a s h 函数。由于该二路只要考虑确定长度的路由前缀，避免了 最长前缀【蔓配问题。该二路的路由查找只需要最多两次的存储器访问操作，并且可以在常量 时间内实现路由更新，存储器的需求不到i mb y t e s ，且该需求受路由前缀数量的增加影响较 小。该算法对末来路l 丰j 的发展具柯很好的适应性。 论文对所设计算法的软件部分进行了编程实现，同时实现的还有lb i tt r i e 和4b i tt r i e 算法，并与论文所设计的算法进行性能比较，实验比较结果再次表明，所设计的算法在路由 查找，路由更新，存储器需求和适应性方面具有很好的性能。 最后，总结了本文提出的方案，并明确了未来工作方向。 关键字：i p v 6 ，并行计算，路由查找 a b s t r a c t i n t e r n e ta d d r e s sj o o k u pi sac h a l j e n g i n gp r o b l e mb e c a u s e 。f i n c r e a s i 力gr o u t j n gt ablesizes。i ，n 。c ，r e a s e dt r a f f i c , ，h i g h e r s p e e d1 n k sa n dt h em i g r a t i 。nt 。12 8b i ti p v 6a d d r e s s e s i p r o 。u t i n gi 。： 嘲淄哪“n g 协蚰e s a l c h i n gp 嘲x ，f o rw h i c h 。r i g i n a l s 。i u t i 。n sw e r e b e l i e v e dt 。：i n a p p l i c a b l ef o ri p v 6 。 a p a r a l l e lf r a m e w o r ki sp r 。p 。s e da f t e ra l 。t 。fr e s e a r c hw a sd o n e 。nt h ea c t u a l i p v 6r o一!一一t 。a b l e s t h e p a r a l l e lf r a m e w o r kc o n s i s t s0 ff o u r b 啪c h e si n w h j c ht h 脚。ft h e ma r et h e ：r ：二：u w u i t h n 9 2 = , 3 5 m a n d 4 8l e n g t h , t h e o t h e rl e n g t hp r e x s n t r i b u t e t ot c a m i n t h e 3 2 ，3 5i = 嚣 三渤s 咖砹啪州t hs e 舯e n t t a m e ，。凰e t t a b i e a n dg 。d h a s b 内n c t i o n si sd e s i g n e d t h i sa 乏：淼 ：a 、叶n r e d u c e t h e e r o u t i n g l o o ku p t j m et oa tm 0 s t 咖m e m o r y a c c e s s i n g a n d c 。：s u m e 】e s s 孟焉 b e s m e m o r y f o rc u n n ti p v 6 r o u t i n gt a b l e ，a n d i tc a j lu p d a t ei n c o n s t a n tt i m e 怖竺= m e n o f s o f t w a r ep a r to n h j sa j 9 1 o r i t h mw a sd o n e , a tt h es a m et i m et h e i b i l t 一t ：羔专：! 竺sw e ，r e a l s o i m p l e m e n t e d t 0c o m p a r ew j t ht 1 1 e p r o p o s e d a l g o r i t h m t ui t ：e s t 2 t t l c d = q - o l s h o w sd l ep r o p o s e d 硝g o t h m p e r f o 肋s 风t e r ，q u i c k l yu p d a t e , 妇b l ym e m 面c 。n s u m 二。：二z ：s u p p o r tl a r g ea m o u n to ff u t u r ei p v 6 p r e f i x s 。 。“、7 “1 k e y w 。r d s ：i p v 6 ，p a r a l l e ic 啪p u t e ，r o u t i n g l 。ku p n 南京邮电大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了文中特麦j i j j n 以标注和致谢的 地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包 含为获得南京邮电大学或其它教育机构的学位或证书而使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了 明确的说明并表示了谢意。 研究生签名：墨堑l 五日期：竺壁：生? f 南京邮电大学学位论文使用授权声明 南京邮电大学、中国科学技术信息研究所、国家图书馆有权保留 本人所送交学位论文的复印件和电子文档，可以采用影印、缩印或其 他复制手段保存论文。本人电子文档的内容和纸质论文的内容相一 致。除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布 ( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权 南京邮电大学研究生部办理。 研究生签名： 毕导师签名：古物 日期：逊：丝f 南京邮电大学硕士研究生学位论文 第一章绪论 1 1 课题的目的与意义 第一章绪论 随着i n t e m e t 规模的急剧膨胀，信息量的加大以及i n t e m e t 上新应用的不断涌现，2 0 多年前 提出的i p v 4 网际互连协议有许多方面不适应。首先是地址的限制，其次是日益复杂的应用业 务如流式视频和音频业务等对网络性能提出新的需求，人们对i p 协议的地址空间、性能以及 安全性等方面提出了更高的要求，使i p v 4 的局限性越来越显现出来，迫切需要发展新一代互 联网( n g i - n e x tg e n e r a t i o ni n t e m e t ) 。i p v 6 正是为了满足这些新的需求而提出来的。 另一方面，由于i n t e m e t 规模的膨胀、信息量的加大、应用业务的多元化导致网络流量的 迅速增加，据统计，网络流量每几个月就会翻一番。为了消除网络流量增加带来的影响，保 证i n t e m e t 的服务质量，我们必须消除三个主要因素的影响：链路传输速率、路由器的数据处 理能力和路由查找速率。而前两个因素都已经存在解决方案，例如，光纤的广泛应用可以保 证链路的传输速率；交换技术的应用能够使路由器以g 比特的速率将数据包从输入端口转移 到相应的输出端口。而第三个因素就成为了制约网络速率的瓶颈，而当前的路由查找算法大 部分是针对i p v 4 ，针对i p v 6 的路由查找算法还不够成熟。因此，有必要进行针对于i p v 6 的 高速路由查找算法的研究。 1 2i n t e r n e t 地址结构的发展 在i n t e r n e t 的发展初期，i p v 4 地址采用的是基于类的地址结构整个i p 地址空间一共分为 5 类：为单播地址设计的a ，b ，c 类：为组播地址设计的d 类：为今后使用而保留的e 类地址各个类 之间由地址的前几个比特位来区分在i n t e r n e t 发展的初期，基于类的地址结构由于其简单性 而得到了广泛的应用但是，随着网络的不断发展，使用这种地址结构产生了两个问题一个问 题是地址分配的不灵活导致了地址空间的大量消耗以及路由表规模的不断增大基于类的地 址结构将整个地址空间简单地分成了5 个类别，这就导致了地址的分配不够灵活另一个问题 是，由于路由器需要记录所有已经分配的网络地址，特别是对于c 类地址来说，由于它的地址前 缀特别多，如果记录所有的c 类地址，那么路由表的规模将变得非常大 南京邮电大学硕士研究生学位论文 第一章绪论 为了降低路由表规模的增长速度以及提高地址空间的利用率，i e t f 提出了一种称为无类 n 一1 域问路由( c l a s s l e s si n t e r d o m a i nr o u t i n g ，简称c i d r ) 的地址结构”“c i d r 摒弃了传统上基 于类的地址分配方式，规定可以使用任意长度的网络地址部分，因此产生了路由地址前缀的概 念使用c i d r 的好处是明显的，它提高了地址空间的利用率，例如为3 0 0 台主机分配网络地址只 需使用一个2 3 位网络地址前缀长度的网络地址( 可以支持5 1 2 台主机) 就可以满足要求 为了满足网络规模不断增长的需要，i e t f 设计了新一代的网络协议i p v 6 ，也被称为 i p n g i p v 6 与i p v 4 相比，在地址格式上发生了巨大的改变，地址长度由原来的3 2 位变成了1 2 8 位，相 r 1 1 应地，i p v 6 在整个地址分配上也进行了一定的改进1 尽管i f v 6 的地址结构与i p v 4 相比有很多的 不同之处，但是从根本上来说，整个地址空间仍然是层次性结构，仍然支持类似于i p “c i d r 地址 结构下的路由合并，因此新一代的网络协议并没有改变路由查找的本质特点 1 3i p v 6 简介 1 3 ii p v 6 地址 i p v 6 地址的长度为1 2 8 位，也就是说可以有2 的1 2 8 次方的i p 地址，相当于1 0 的后面有3 8 个零，如此庞大的地址空间，足以保证地球上每个人拥有一个或多个i p 地址。 ( 1 ) i p v 6 地址表示 对于1 2 8 位的i p v 6 地址，考虑至1 i p v 6 地址的长度是原来的四倍，r f c l 8 8 4 规定的标准语法 建议把i p v 6 地址的1 2 8 位( 1 6 个字节) 写成8 个1 6 位的无符号整数，每个整数用四个十六进制 位表示，这些数之间用冒号分开，例如：3 f f e ：3 2 0 1 ：1 4 0 1 ：l ：2 8 0 ：c 8 f f ：f e 4 d ：d b 3 9 某些i p v 6 地址中可能包含一长串的o 。当出现这种情况时，标准中允许用“空隙”来表示 这一长串的0 。换句话说，地址2 0 0 0 ：o ：0 ：0 ：o ：o ：0 ：1 9 以被表示为：2 0 0 0 ：l 这两个冒号表示 该地址, - i p a 扩展到一个完整的1 2 8 位地址。在这种方法中，只有当1 6 位组全部为0 时才会被两 个冒号取代，且两个冒号在地址中只能出现一次。 由于i p v 6 地址被分成两个部分一子网前缀和接口标识符，因此人们期待一个i p 节点地址 可以按照类似c i d r 地址的方式被表示为一个携带额外数值的地址，其中指出了地址中有多少 位是掩码。即i p v 6 节点地址中指出了前缀长度，该长度与i p v 6 地址间以斜杠区分，例如： 1 0 3 0 ：0 ：0 ：0 ：c 9 8 4 ：f f l 2 ：4 8 a a ：1 a 2 b 6 0 ：i 塞_ 个地址中用于选路的前缀长度为6 0 位。 2 童塞堕皇奎兰堡主堕茎尘兰堡垒奎一 一墅二! 兰j ! 坚l ( 2 ) i p v 6 地址空间 图1 1 显示了地址空间的分配方法。地址分配的不同类型，前缀( 地址分配中前面的位值) 和作为整个地址空间的一部分的地址分配的长度。 在r f c l 8 8 4 中指出了三种类型的i p v 6 地址，他们分别占用不同的地址空间： 木单点传送：这种类型的地址是单个接口的地址。发送到一个单点传送地址的信息包只 会送到地址为这个地址的接口。 宰任意点传送：这种类型的地址是一组接口的地址，发送到一个任意点传送地址的信息 包只会发送到这组地址中的一个( 根据路由距离的远近来选择) 宰多点传送：这种类型的地址是一组接口的地址，发送到一个多点传送地址的信息包会 发送到属于这个组的全部接口。 妻室坚皇奎堂堡塑窒尘堂堡堡奎 一墨二兰二堕! l ( 4 ) i p v 6 地址分配 r f c l 8 8 l 规定，i p v 6 地址空间的管理必须符合i n t e m e t 团体的利益，必须是通过一个中心 权威机构来分配。目前这个权威机构就是i a n a ( i n t e m e ta s s i g n e dn u m b e r sa u t h o r i t y ，i n t e r n e t 分配号码权威机构) 。i a n a 会根据i a b ( i n t e r n e t a r c h i t e c t u r eb o a r d ) 和l e g s 的建议来进 行i p v 6 地址的分配。如图1 2 所示。 1 3 2i p v 6 的寻址方式 图1 2i p v 6 分配的用户和地址总量 i p v 6 的地址型态可分为三种： ( 1 ) u n i c a s ta d d r e s s ：单播地址。此种地址是用来识别单一网络接n ( i n t e r f a c e ) 。其字段 可分为前后两段，前段作为路径搜寻用，后一段做为网络接口识别之用。在所有的u n i c a s t a d d r e s s e s 中，除了以0 0 0 开头的地址之外，其i n t e r f a c ei d 都必须是6 4 b i t s 长，n t e r f a c ei d 具有 唯一性，以识别每一个网络接口，在u n i c a s ta d d r e s s 中又可分为三种：g l o b a lu n i c a s ta d d r e s s 、 l i n k 一l o c a lu n i c a s ta d d r e s s 、s i t e - l o c a lu n i c a s ta d d r e s s ，新的g l o b a lu n i c a s ta d d r e s s 的格式如 图1 3 所示，l i n k l o c a lu n i c a s t 地址及s i t e l o c a lu n i c a s t 地址在定义上是提供给局域网络 使用的地址，因此路由器是不会传送来源或目的地地址为此种格式的地址，这两种格式的地 4 南京邮电大学硕士研究生学位论文 第一章绪论 址将只会出现在l o c a l 端，不会出现在骨干网络上，所以会出现在骨干网络上的u n i c a s t a d d r e s s 为g l o b a lu n i c a s ta d d r e s s ，因此路由器在对封包做路径搜寻时，只需针对此种类 型的地址做处理。 3b i t s4 5b i t s 1 6 b i t s6 4b i t s 0 0 1 g l o b a lr o u t i n gp r e f i xs u b n e ti di n t e r f a c ei d g l o b a lu n i c a s ta d d r e s s 1 0b i t s5 4b i t s6 4b i t s 1 1 1 1 1 1 1 0 1 0oi n t e r f a c ei d l i n k l o c a lu n i c a s ta d d r e s s 1 0b i t s5 4b i t s6 4 b i t s 1 1 1 1 1 1 1 0 l ls u b n e tl di n t e r f a c ei d s i t e l o c a iu n i c a s ta d d r e s s 图1 3u n i c a s ta d d r e s s 地址格式 ( 2 ) m u l t i c a s ta d d r e s s - 组播地址。此种地址是用来识别一群网络接口，当一个封包送 往此地址时，会把此封包送往属于这个群网络接口中所有的网络接口。 ( 3 ) a n y c a s ta d d r e s s ：泛播地址。此种地址是用来识别一群网络接口，当封包送往此地 址时，会把此封包送往这群网络接口中最近的一个网络接口，如何定义最近的网络接口，是 藉由路由协议计算出来的距离决定。与i p v 4 比较，i p v 6 多了a n y c a s ta d d r e s s 少了b r o a d c a s t a d d r e s s ，这是因为b r o a d c a s ta d d r e s s 会影响网络的效能，当网络中存在太多广播( b r o a d c a s t ) 讯息时，所有的网络节点都必须对此讯息做处理，这种b o r a d c a s t 的讯息不仅影响网络的效 能更会造成路由器的负担。 由上述内容可知i p v 6 的地址类型，可分为u n i c a s t 、m u l t i c a s t 、a n y c a s ta d d r e s s 三 种，其中a n y c a s ta d d r e s s 的格式事实上是跟u n i c a s t 相同，所以我们可以把这两种地址合并 起来处理。由于l i n k l o c a l 、s i t e l o c a lu n i c a s ta d d r e s s 这两类u n i c a s ta d d r e s s 只会 在l o c a l 端使用，不会被路由器传送到骨干上，因此对于u n i c a s ta d d r e s s 而言，我们只 需处理g l o b a lu n i c a s t 就可以了。在m u l t i c a s ta d d r e s s d p ，因为只用到最后的3 2 位，所以 在对m u l t i c a s ta d d r e s s 做最长前缀匹配时，只需处理这3 2 位就可以了。 南京邮电大学硕士研究生学位论文第一章绪论 总结上面所述，在整个路由查找的过程中我们只需处理g l o b a lu n i c a s t 及m u l t i c a s ta d d r e s s ， 我们可以依目的地地址的前3 位来判断此a d d r e s s 是属- 于g l o b a lu n i c a s ta d d r e s s ( 0 0 1 ) j 丕是m u l t i c a s t a d d r e s s ( 1l1 ) ，再来对它做个别的处理。本文内容只涉及对g l o b a lu n i c a s ta d d r e s s ( 0 0 1 ) l 撇。 1 3 3i p v 6 与i p v 4 的比较 在r f c 2 4 6 0 中提到i p v 6 与i p v 4 的不同可分为五大部分： ( 1 ) 延伸寻址的能力： i p v 6 的地址空间由i p v 4 的3 2 位长延伸到1 2 8 位长。 ( 2 ) 简化标头格式： i p v 6 的字段将某些包头( h e a d e r ) 字段删除或改为可选择性，在i p v 4 中h e a d e r 的长度是 不固定的，而i p v 6h e a d e r 在简化后h e a d e r 的长度变为固定的，对于路径搜寻而言，固定的 h e a d e r 与较少的字段可以有效的改善路由器的效能。在i p v 6 中封包的切割方法也与i p v 4 不 同，封包只在起始点作切割，中途的路由器不做切割的动作，这也减少了路由器对封包的处 理动作。i p v 4 和i p v 6 的包头字段如下图1 4 和图1 5 所示。 图i 4i p v 4 包头 图1 5i p v 6 包头 6 塑室坚皇奎兰堡墅窒生堂垡堡茎一墅二兰! 耋! l ( 3 ) 将o p t i o n 放到延伸包头( e x t e n s i o nh e a d e r ) 作处理： 将o p t i o n 放在延伸字段，需要此功能时，才去处理这部分的字段，否则就不处理延伸字 段，譬如：f r a g m e n th e a d e r 只有在起始点的时候才需要考虑到，中途经过的节点都不需要 去处理它，这可以使封包的传输效率变好。 ( 4 ) 数据流卷标： 在王p v 6h e a d e r 中可以利用f 】o wl a b e l 这个字段将来源地址与目的地地址相同的封包定 义成同一个f l o w ，藉此拥有相同f l o wl a b e l 的封包就可以走相同的路径，以提升路径搜寻的 速度。 ( 5 ) 增加i p s e c 功能。 1 4i p 路由查找的定义 当i p 分组进入路由器时，路由器根据i p 头中的目的i p 地址，在路由表( r o u t i n gt a b l e ， 又称前缀表p r e f i xt a b l e ) 中查找相应的输出端口和下一跳信息( n e x t h o pi n f o r m a t i o n ) ，以 便将i p 分组从这个输出端口传送到对应的下一跳路由器。在路由表中查找目的i p 地址的下一 跳信息的动作就是i p 路由查找( i pa d d r e s sl o o k u p ) 与精确匹配查找( e x a c tm a t c hs e a r c h ) 不同的是，i p 路由查找必须在前缀表中查找到和目的地址匹配的最长前缀，这种查找是一种 最长匹配查找( l o n g e s tm a t c hs e a r c h ，l m s ) ，而匹配的最长前缀被称为最长匹配前缀( l o n g e s t p r e f i xm a t c h ，l p m ) ，所以i p 路由查找问题有时也被称为l p m 问题。 下面以表1 1 中的样例前缀表为例，给出i p 路由查找的形式化定义。 表1 1 样例前缀表 前缀下一跳信息端口 0 木a1 1 宰c 2 1 0 ：i cb1 1 0 1 木d 3 1 0 1 0 l 木e 2 1 0 1 1 i 0 f 3 1 0 1 1 1 0 1 h g 2 7 南京邮电大学硕士研究生学位论文 一 茎：童! 丝 如果目的i p 地址为0 0 1 0 1 1 0 0 x x x ( 这里x 为通配符) ，则匹配目的i p 地址的只有前缀o , a ， 其输出端口为1 。如果目的i p 地址为，f o l l l 0 1 1 x x x ，贝u i o * b ，10 1 d ，10 1 i i o * f 和 1 0 1 1 1 0 1 1 g 都是匹配的前缀，其前缀长度依次为2 ，3 ，6 和8 ，所以按照l p m 原则，路e h 查找的 结果为1 0 1 11 0 1i * g ，对应的输出端口为2 。 下面我们给出一些名词及术语： 木目的i p 地址d s t l p ：长度为w 的二进制比特串，典型的w 值为3 2 或1 2 8 ： 木路由前缀p r e f i x ：长度介于0 和w 之间( 包括0 和w ) 的二进制比特串，l e n ( p r e f i x ) 表示 组成前缀p r e f i x 的二进制比特串长度： 幸路由前缀表p t a b l e ：由n 个( p r e f i x ，n e x th o p ) 对组成的二维表，这里n 称为p t a b l e 的 规模： 木前缀p r e f i x 匹配目的i p 地址d s t l p ：当且仅当d s t l p 的前l e n ( p r e f i x ) 个二进制比特等 于p r e f i x 的二进制比特串： 据此，i p 路由查找问题可以定义为：寻找d s t l p 的最长匹配前缀p r e f i x t 。删使得 ( 1 ) 前缀p r e f i x 。匹b 己d s t l p ： ( 2 ) p t a b l e 中不存在匹配d s t l p 的前缀p r e f i x j ，使得l e n ( p r e f i x j ) l e n ( p r e f i x i 。) 。 1 5 路由查找的主要困难 根据i p 路由查找的定义，路由查找的主要困难可以分为三类： ( 1 ) l p m 问题本身造成的困难； ( 2 ) 问题规模造成的困难； ( 3 ) 实时性要求造成的困难。 下面逐一进行描述。 1 5 1l p m 问题造成的困难 由路由查找的定义易知，l p m 问题的最大困难在于必须在前缀长度( p r e f i xl e n g t h ) 和前 缀值( p r e f i xv a l u e ) 两个维度查找最佳匹配，这和精确匹配查找e m s 是完全不一样的。由于目 的i p 地址本身并不携带任何关于前缀长度的信息，所以在查找前缀是否匹配的同时，还必须 检查前缀是否是最长的匹配前缀，这使得查找变得异常困难。也就是说，只有查找完整个i p 3 南京邮电大学硕士研究圭兰垡垒奎 一笙：二兰兰i ! l- - - _ _ - _ _ - _ - _ - - _ - i l - i i _ - - _ _ _ _ _ _ - _ - _ 一一一 前缀表空间，才能保证查找结果是最长匹配前缀。 图1 6l p m 问题的主要困难 此外，不同前缀值之间可以互相交错重叠，这也使得l p m 变得非常困难。如图1 6 所示， 前缀1 2 8 9 1 6 0 21 ，1 2 8 9 0 0 1 6 ，1 2 8 9 1 7 2 0 2 1 和1 2 8 9 1 7 6 0 2 4 彼此交错，对于目的 i p 地址1 2 8 9 1 6 1 4 来说，从前缀值来看1 2 8 9 1 6 0 2 1 和1 2 8 9 0 0 1 6 都是匹配前缀，从前 缀长度来看1 2 8 9 1 6 0 2 1 大于1 2 8 9 0 0 1 6 ，所以查找结果为1 2 8 9 ，1 6 o 2 1 1 5 2 问题规模造成的困难 问题规模造成的困难主要分为两个方面，一个是路由前缀表的规模非常大且增长速度很 快，另一个是i p v 6 地址使得需要查找的二进制比特串宽度翻了两番，从3 2 比特增加到1 2 8 比特。 以目前路由前缀表的规模计算，典型的i n t e r n e t 核心路由器的i p v 4 路由表包含约1 0 0 k 至t j 2 5 0 k 左右的前缀项，虽然由于i p v 6 未大规模使用使得目前i p v 6 路由表大约只包含不n i k 左右 的前缀项目，但估计的i p v 6 路由表前缀项应在5 0 0 k 左右。由于l p m 必须处理前缀表中所有的前 缀，如此大规模的前缀表使l p m 变得更加困难，这就要求路由查找算法在前缀表的规模快速增 9 南京邮电大学硕士婴窒竺堂垡堡奎 茎二雯堕! l - - _ - _ _ - _ _ _ - _ _ _ _ _ _ - - - - - - - - _ - 。- _ - - _ - _ _ - _ - _ _ - 1 一一一 长时具有良好的可扩展性。 、图1 7 中的统计数据来源于g e o f fh u s t o n 的i p v 4b g p ( b o r d e rg a t e w a yp r o t o c 0 1 ) 路由表 分析报告【4 】，包括了自 黼a s 6 4 4 7t e l s t r a 和0 r e g o n 大学r o u t ev i e w s i 员目监控所得的数据。 可以看出，i p v 4 前缀表的规模成近似线性增长，目前的平均前缀数量在2 4 0 k 个左右。 图1 71 9 9 4 年至今i n t e r n e tb g p 路由表的增长 另外一个规模是从查找宽度来看，i p v 4 路由查找需要处理的目的地址宽度为3 2 位，而i p v 6 地址的宽度增加到了1 2 8 位，这必然对i p v 6 路由查找造成困难和挑战。 1 5 3 实时性要求造成的困难 目前己经出现t 4 0 g b p s 数量级的高速网络，1 6 0 g b p s 数量级的更高速网络己处在研究阶 段，网络的性能瓶颈己从原先的传输媒体带宽逐渐转移到主机和以交换机、路由器等网络设 备为代表的传输设备上，尤其是路由设备。高速数据传输链路的出现，使得路由器进行线速 转发( 即按照数据包达到的速率进行转发) 的条件越来越苛刻。 通常来说，典型的路由器对每个分组的处理操作包括接收分组、协议识别及分类、分组 过滤、分段、前缀查找、服务质量控制、分组调度和分组发送等，表1 2 中列出的“每分组处 理时间”实际上包括了部分或所有这些操作。很明显，路由查找操作的时间只能占t t 每分组 1 0 南京邮电大学硕士研究生学位论文 第一4 章绪论 处理时间 的一部分，这对路由查找算法的性能提出了很高的要求。与此同时，线路速率和 c p u 计算能力、内存系统带宽之间的差距还在不断扩大。在过去的1 0 年中，由于通信技术的高 速发展，物理层传输速度呈指数级增长，而且将继续以每年4 倍的速度增长，这一增长速度远 远超过了处理器性能的增长速度，从而导致处理器速度和传输媒体带宽之间的差距越来越大。 以1 0 g b p s 的i o g e 线路和6 4 字节i p 数据分组( 假设为以太网的情况) 为例，路由器必须在5 1 2 n s 内处理完分组并将分组传送到相应的网络接口上。根据相关的统计数据，对于r i s c 处理器来 说，处理这样的一个i p 数据分组至少需要1 6 0 0 条r i s c 指令。若采用一个1 5 g h z 频率的r i s c 处 理器，假设一个时钟周期可以执行一条指令，则总共需要1 0 6 7 n s 才能处理完成，而这还只考 虑了最关键的协议通路处理，诸女n o o s 等其它特性均未考虑。显然，这已经远远超出了5 1 2 n s 的性能预算时间，是不可能达到i o g e 线路的速度要求的。即使是i g b p s 的线路，目前最快的r i s c 处理器所需要的处理时间也大于线速转发允许的时间。 此外，由于i n t e r n e tb g p 路由表的不稳定性，其前缀表更新具有突发性和频繁性，可能 需要路由器每秒处理数百个前缀项的插入、删除或更新，这也对路由查找算法提出了更高的 性能要求。一般来说，i n t e r n e t 核，l 1 , 路由器至少需要具备1 k u p s ( u p d a t ep e rs e c o n d ) 的更新 能力，而实际的实现中一般认为5 k u p s 到l o k u p s 的更新速度才是安全的。 1 6 论文的主要贡献 本论文i p v 6 高速并行路由查找算法的研究，主要贡献如下： ( 1 ) 给出了i p v 6 路由查找的定义，分析了当前路由查找的主要困难。 ( 2 ) 对现有的路由查找算法进行了分析总结。 ( 3 ) 提出一种并行路由查找框架，设计了实现该并行框架的详细算法，包括路由的存储 组织形式和路由查找的h a s h 函数。 ( 4 ) 对所提出的算法进行编码实现和性能分析，并与现有经典算法进行性能比较。 ( 5 ) 对所做工作进行了总结并对算法的进一步完善和改进进行了展望。 南京邮电大学硕士研究生学位论文 第二章路由查找算法分析 第二章路由查找算法分析 伴随着i n t e r n e t 的迅速发展，传统的i p v 4 网络地址将消耗殆尽，现行的解决方案的c i d r 以及网络地址转换，而未来的解决方案是i p v 6 。i p v 6 也被称为i p n g i p v 6 与i p v 4 相比，在地 址格式上发生了巨大的改变，地址长度由原来的3 2 位变成了1 2 8 位，相应地，i p v 6 在整个地址 分配上也进行了一定的改进。 i p v 6 的地址结构与i p v 4 相比有很多的不同之处，但是从根本上来说，整个地址空间仍然 是层次性结构，仍然支持类似于i p v 4c i d r 地址结构下的路由合并，因此新一代的网络协议并 没有改变路由查找的本质特点。相对于i p v 4 来说，1 2 8 位的i p v 6 地址长度，要使用最长地址 前缀匹配查找难度更大，而最长地址前缀匹配查找的难点在于，在查找过程中不仅需要与地址 前缀的比特值进行匹配查找，而且还需要考虑地址前缀的长度，因此各种路由查找算法都可以 归结为这两个方面的匹配查找过程。 基于地址前缀值路由查找算法的特点是通过对整个地址前缀空间进行地址关键字穷举来 消除地址前缀长度对查找的影响。第2 1 1 节中介绍的线性匹配查找算法是基于地址前缀值查 找中最为简单、直观的地址前缀查找方法。第2 2 4 节介绍的地址区域二分法也是基于地址前 缀值的查找算法，但由于它采用了二分查找，所以在算法性能上有很大的提高。第2 2 5 节介绍 的t s b 算法也是基于前缀值的查找算法，但它结合了二分查找，h a s h 表和桶等多种数据结构， 因此在查找性能少得到了很大的提高。第2 2 6 节介绍的c a m 硬件实现方法从本质上来说也属 于地址前缀值的查找算法。 基于地址前缀长度的路由查找算法的出发点是在前缀长度空间内进行查找，与基于地址 前缀值查找算法类似，查找过程可以使用线性遍历法，也可以使用二分法遍历法。第2 1 3 节 介绍的二进制t r i e 树查找算法就是基于地址前缀长度的线性遍历法，因为对于查找的第i 步 来说，匹配的是长度为i 的地址前缀。第2 1 4 节的路径压缩t r i e 树是二进制t r i e 树的变形。 同理，第2 2 2 节介绍的多分支t r i e 查找算法也是基于在地址前缀长度空间内的线性遍历法， 但由于它采用大于l 的步宽，所遍历的地址长度数目变少了，查找性能得到了提高。第2 2 3 节介绍的算法能够在前缀长度空间内进行二分查找，所以从算法的复杂度来看，它的性能更 好。 1 3 南京邮电大学硕士研究生学位论文 第二章路由查找算法分析 徐恪等【5 1 对已有的路由算法进行了一定的研究，我们以此为基础对现有的路由算法特别是 i p v 6 路由查找算法进行分析，并对现有的并行查找的算法进行总结。 2 1 传统的路由查找算法 在下面的算法介绍中，我们用表2 1 作为算法分析的实例 表2 1 地址前缀实例 p r e f i x n e x t h o p p lo 乖a p 20 1 0 0 0 b p 30 n 霉c p 41 木矗 p 51 0 0 e p 611 0 0 f p 71 1 0 1 宰 g p 8 l l10h p 911 母 i 2 1 1 线性查找 线性表结构是最简单的查找数据结构，因此可以把所有的路由地址前缀用线性链表的方 式组织起来。每一次查找需要遍历线性表中的所有表项，在遍历过程中记录最长的路由前缀项， 直到遍历完整个线性链表为止。对于 个路由前缀表项，查找过程的算法复杂度为口( 肋，存储空 间复杂度为p ( 朋，插入删除路由表项的算法复杂度为口( 1 ) ( 假设表项插入和删除均在线性表的 末尾进行) 。 2 1 2 缓存策略 在路由查找中可以使用缓存策略，把最近查找过的i f l 的地址路由存放在高速的路由缓存 ( r o u t ec a c h e ) 中，只有当在路由缓存表中查找失败的时候，我们才需要进行真正完整的前缀 查找匹配过程。 为了能够在查找性能上获得较大的提高，缓存的命中率就需要有一定的保证，假设缓存查 找速度是路由前缀查找速度的2 0 倍，经过计算可以得出，为了能够使平均查找性能达到原来的 1 4 南京邮电大学硕士研究生学位论文 第：二章辇各由查找算法分析 l o 倍，缓存的命中率需要达至j j 9 5 左右。随着i n t e r n e t 的不断发展、网络用户的不断增加以及 业务数据量的多样化，数据的时间局部性变得越来越不明显，从而大大地降低了缓存的命中 率。因此，文献 6 建议缓存的大小应该能够随着网络用户或者网络数据业务量的增加而相应 地呈线性增加。 2 1 3 二进制t r i e 树( b i n a r yt r i e ) 用二进f 若1 t r i e 结构来表示地址前缀是一个常用的方法。t r i e 采用一种基于树的数据结构， 通过前缀中每一位比特的值来决定树的分支。图2 1 就是用二进带l j t r i e 结构( 树中每一个内部 结点最多包含两个子结点) 来表示的地址前缀表。 在t r i e 树中，处于第层的结点代表了一类地址前个比特均相同的地址空间，并且这前 个比特串就是由从根结点到这个结点路径上的l 个比特组成。例如，图1 中处于第3 层的结点c 就代表了所有前3 个比特为0 1 1 的地址族，而且比特串o l l 就是根结点到结点c 路径上的比特按 照遍历顺序所构成的。图2 1 中用字母标识的结点表示该结点对应着一个地址前缀，因此这些 结点中包含了与该地址前缀相关的转发信息。图2 1 中的字母标识结点既可以是叶予结点( 如 结点b ) 。也可以是中间结点( 如结点a ) 。 p r e f i x e s a0 b0 c0 d1 e1 f1 g 1 h1 l1 图2 1 二进爿i r t r i e 树结构 2 1 4 路径压缩t r ie 树( p a t h c o m p r e s s e dt r ie ) 图2 1 中的t r i e 树经过路径压缩之后得到的t r i e 树如图2 2 所示。比较图2 1 和图2 2 可以 南京邮电大学硕士研究生学位论文第二章路由查找算递乏逝 看到，结点b 的前两个父结点已经被删除，结点a 从原来单分支结点处移动到了二分支结点处， 原来的单分支结点被删除。由于删除的单分支纬点可能包含多个地址前缀信息，所以路径压缩 t r i e 树结点中可能包含多个地址前缀。t r i e 树搜索过程由于某些结点被删除，所以可忽略目的 地址中某些比特位的匹配操作，因此结点处需要维护一个变量指示下一个需要检查的比特位。 另外，与二进带r j t r i e 树相比，路径压缩t r i e 树前缀结点处需要保存地址前缀的比特串。查找过 程与二进镱l l t r i e 树类似，但是在结点选取分支时考虑的是比特位变量所指示的比特位。当查找 过程遇到前缀结点时，需要进行前缀匹配操作。当到达叶子结点或者是前缀匹配操作失败时， 查找过程终止，查找结果是查找过程中已被记录的最长匹配前缀。 p r e f i x e s1 a0 睾 b0 10 0 0 c0 11 粤 d1 事 e1 0 0 膏 f1 10 0 卑 91 10 1 奉 h1 11 0 i1 11 1 牛 图2 2 路径压缩t r i e 树结构 路径压缩的思想最初在被称为p a t r i c i a 的算法中提出，但该算法不支持最长前缀的查 找s k l o w e r 对该算法进行改进，使之能够适应最长前缀的查找，并且在b s d ( b e r k e l e y s o f t w a r ed i s t r i b u t i o n ) u n i x 中加以实现。 简单二迸制t r i e 树和路径压缩t r i e 树的不足之处在于查找过程需要大量的存储器访问操 作，对于i p v 4 地址来说，最差的情况需要3 2 次存储器操作。实验表明，使用b s d 路径压缩t r i e 树 来表示典型路由器中4 7 1 1 3 表项数目的前缀表p 1 ，最大搜索深度为2 6 ，平均搜索深度也达到了2 0 使用简单二进制t r i e 树来表示同样的地址前缀表，其最大搜索深度为3 0 ，平均搜索深度为2 2 。 2 2 路由查找新算法的研究 近几年来，随着对路由器研究的逐步深入以及对路由器性能要求的不断提高，研究人员提 1 6 南京邮电大学硕士研究生学位论文第二章路由查找算法! 堕 出了很多较为新颖的地址前缀查找算法。与二进制t r i e 树、缓存目的地址法等传统的地址前 缀查找方法相比，这些算法在性能方面有了很大的提高。 2 2 1 查找算法使用的辅助策略 为了提高算法的效率，最近提出的算法中都使用了一些辅助策略。 ( 1 ) 前缀扩展( p r e f i xe