（电路与系统专业论文）基于TCAM和多核处理器的高速路由查找转发引擎设计[电路与系统专业优秀论文].pdf

山东大学硕士学位论文 目鼍葺置皇詈詈暑詈詈詈曼鼻詈鼍! 鼍詈暑量詈詈置| 量一ii 量毫量皇一 符号说明 t c a m t e 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三态内容可寻址存储器 c i d rc l a s s l e s si n t e r - d o m a i nr o u t i n g 无类域间路由 l p m l o n g e s t p r e f i xm a t c h i n g 最长前缀匹配 n g nn e x tg e n e r a t i o nn e t w o r k 下一代互联网 n a tn e t w o r ka d d r e s st r a n s l a t i o n 网络地址转换 m p l sm u l t i p r o t o c o ll a b e ls w i t c h i n g 多协议标签交换 a s i c a p p l i c a t i o ns p e c i f i ci n t e g r a t e dc i r c u i t 专用集成电路 v p nv l r t u a lp r i v a t en e t w o r k 虚拟专用网络 r i p r o u t i n gi n f o r m a t i o np r o t o c o l路由信息协议 o s p f o p e ns h o r t e s tp a t hf i r s t 开放式最短路优先 b g pb o r d e rg a t e w a yp r o t o c o l 边界网关协议 ma d d r e s sr e s o l u t i o np r o t o c o l 地址解析协议 s o c s y s t e mo dac h i p 片上系统 s m s w i t c hm a n a g e m e n t 信元交换篱理模块 t mt r a f f i cm a n a g e m e n t 流量管理模块 p c i p e r i p h e r a lc o m p o n e n ti n t e r c o n n e c t i o n外设组件互连标准 q o s q u a l i t yo fs e r v i c e 服务质量 s e r d e s s e r i a li z e s d e s e r i a li z e s 串化器并化器 3 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不 包含任何其他个人或集体己经发表或撰写过的科研成果。对本文的研 究作出重要贡献的个人和集体，均己在文中以明确方式标明。本声明 的法律责任由本人承担。 论文作者签名：堑壑：筮 日期：丝兰：篁堑 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学 校保留或向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅：本人授权山东大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段 保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：銎塑! 是导师签名：日期：兰! 兰：三：乡 山东大学硕士学位论文 中文摘要 近年来，随着i n t e m e t 的迅速普及，使用i n t e m e t 的人数、连接到i n t e m e t 上的 主机数量和数据流量呈现指数式的增长。另一方面，各种新的多媒体业务也不断 涌现。因此i n t e r n e t 的容量正在成为一种稀缺资源。为了适应i n t e r n e t 应用的迅速 发展，提供更好的服务质量，必须提高网络的容量。随着光纤技术的发展和t 比 特级交换技术的发展有效的解决了链路带宽、路由器的吞吐量问题，而路由器的 转发效率就成为制约网络性能提高的丰要瓶颈。如何提高路由器的查找转发效率 已经成为众多专家学者和公司研发工作人员研究的重点。而提高转发效率的关键 又在于如何提高路由查找速度和采用更先进的、更合理的路由架构。本论文在综 合了国内外近年来在路由查找算法及实现和路由器发展架构的基础上，提出了第 六代路由器架构的概念，并利用t c a m 和多核处理器实现了一种高效的路由查表 转发引擎。 本文所做的主要工作如下： 总结了i p 地址结构的变化历程，介绍了现有的一些常用的高速路由表查询算 法，对它们进行了详细的研究和比较。 分析了路由架构的发展历程，在第五代基于n p 实现的高速路由器基础上提出 了第六代，即基于多核处理器来实现的更高性能的高端路由器的体系架构。 应用t c a m 和多核处理器实现了一种高性能的路由转发引擎架构。介绍了一 种基于t c a m 和f p g a 实现的路由查表结构。从功耗、成本、性能方面综合考虑， 实现了一种高性能路由查表结构。 关键词：查找转发引擎；无是类域问路由；多核处理器；最长前缀匹配； 山东大学硕士学位论文 a b s t r a c t r e c e n t l y , i n t e m e ti sp o p u l a ri np e o p l e sl i f e a n dm o r ea n dm o r em a c h i n e sa r e c o n n e c t e dt ot h ei n t e m e t o nt h eo t h e rh a n d , t h en e wm e d i as e r v i c eb a s e do nt h e i n t e r n e te m e r g e d s ot h ei n t e m e tc a p a b i l i t yb e c o m e st h er a r er e s o u r c e i no r d e rt oa d a p t t h er a p i di m p r o v e m e n to fi n t e m e ta p p l i c a t i o na n d p r o v i d em o r ee f f e c t i v es e r v i c eq u a l i t y , t h en e t w o r kc a p a b i l i t ym u s tb ei m p r o v e d w i t ht h ei m p r o v e m e n to ff i b e rt e c h n o l o g y a n dt - b i ts w i t c ht e c h n o l o g y , t h en e t w o r kb a n d w i d t ha n dr o u t e rt h r o u g h p u th a v eb e e n e f f e c t i v er e s o l v e d b u tt h er o u t e r st r a n s m i te f f i c i e n c yb e c o m e st h eb o t t l e n e c kt ol i m i t t h ed e v e l o p m e n to fn e t w o r k m a n yr o u t e rd e v e l o p e r sa n dr e s e a r c h e r sh a v ed o n ea1 0 to f w o r ko nh o wt oi m p r o v et h el o o ku pa n df o r w a r d i n gr a t e i m p r o v i n gt h el o o k 叩r a t e a n di n t r o d u c i n gm o r ea d v a n c e da n dr e a s o n a b l er o u t e rs t r u c t u r ea r et w ok e ye l e m e n t sf o r i m p r o v i n gf o r w a r d i n gr a t e b a s e do nt h ea n a l y z i n gr o u t i n ga l g o r i t h m sa n dr e s e a r c h i n g o nr o u t e rs t r u c t u r e ，t h i sd i s s e r t a t i o np u t sf o r w a r dt h ec o n c e p t i o no ft h es i x t hg e n e r a t i o n o fr o u t e rs t r u c t u r e u s i n gt c a ma n dm u l t i - c o r ep r o c e s s o r , a l le f f e c tr o u t e rf o r w a r d i n g e n g i n ei sd e s i g n e d t h em a i nw o r ko ft h i sd i s s e r t a t i o ni sa sf o l l o w s ： t l l i sd i s s e r t a t i o na n a l y z e st h ed e v e l o p m e n tt r e n do ni pa d d r e s ss t r u c t u r e p r e s e n t sa s u r v e yo fl o o k u pa l g o r i t h m sc o m m o nu s e d ，t h e n , m a k e sac o m p a r i s o ni nd e t a i l s b a s e do nt h ed e e pd i s c u s s i o no nt h er o u t e rs t r u c t u r e ，t h es i x t hg e n e r a t i o nr o u t e r s t r u c t u r ei sp u t t e df o r w a r d t h eg r e a t e s td i f f e r e n to ft h es i x t hg e n e r a t i o nr o u t e rs t r u c t u r e f r o me a r l i e rf i v eg e n e r a t i o n si st h eu s i n go ft h em u l t i - c o r ep r o c e s s o rw h o s ea b i l i t yi s v e r yp o w e r f u l t c a mh a sb e e nan e c e s s a r yr e s o l u t i o nf o rt h eh i g l ls p e e dt r a n s m i te n g i n e ag r e a t d e a lo fr e s e a r c hh a sb e e na c h i e v e do nt c a m t h i sd i s s e r t a t i o nu s e sf p g a ，t c a ma n d d d r i is d r a mt oa c h i e v ear o u t i n gl o o k u pe n g i n e t k sm e t h o di sav e r yg o o do n e t o s u p p o r tlm i l l i o ni p v 4f i ba n d10 gp o s k e yw o r d s ：l o o k u pa n df o r w a r d i n ge n g i n e ；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 ) ； m u l t i - c o r ep r o c e s s o r ；, l p m ( l o n g e s tp r e f i xm a t c h i n g ) 2 山东大学硕士学位论文 第一章绪论 本章首先介绍了课题的研究背景和研究现状。然后针对当前存在的问题，介 绍了课题的主要工作和论文的结构安排。 1 1 课题研究背景 随着互联网络宽带化和高速化步伐的加快，为了适应互联网用户的急剧膨胀 和用户业务多样化需求的日益增长，新一代互联网络的体系结构正从目前的扁平 化平坦结构向新的分层化结构演进。互联网基本模式趋于三层体系结构：用户末端 网、边沿接入网与核心传输网。口骨干网络速度正在从g 比特( g i g a b i t ) 级向t 比 特( t e r a b i t ) 级过渡。由于光纤传输和电子工艺发展速度的不均衡，作为网络核心节 点的核心路由器正在成为网络演进的瓶颈【l 】。 蔷 譬 掌 g 妻 时弼t 图1 1 单光纤传输容景的增长趋势 盛 矗 g 蕾 静 璇 工 寡 。 一 雹 蠢 图1 2 路由器单端口速率的增长趋势 由以上图1 1 、图1 2 可以看出，高速路由器的发展瓶颈主要集中在了路由器 的端口速率上，而提高路由器的端口速率重在提高路由器的查找和转发速度。 1 2 路由查找算法的研究现状 目前路由算法丰要是在无类域问路由( 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 ) 2 】【3 】的地址结构的基础上进行最长前缀匹配查找。无类域间路由地址结构使 4 山东大学硕士学位论文 用 对来表示路由项。路由查找就是根据目的地址在路由项中查找 出长度最长的路由项。由于在到达的数据包中的目的地址的域中，并没有携带有 关此信息，可以帮助判断此目的地址的最长前缀匹配长度，所以就无法使用普通 的h a s h ( 4 5 】方法或二分查找【6 】的方法进行最长前缀匹配。因此，最长前缀查找需要 考虑最长匹配路由项的长度和在路由表中包含此长度的能匹配数据包目的地址的 路由项。 目前，研究丰要有两个方面，一方面是改进己有的软件算法，使之能更快的 实现路由查找。另一方面，是把一些软件算法用硬件电路来实现或者使用新的硬 件结构如三态内容可寻址存储器t c a m 等来实现路由查找。虽然，硬件实现没有 软件灵活，但是使用硬件来实现路由查找要比软件快的多，所以目前主干网络上 的核心路由器的路由查找都是由硬件来实现的，而一些小的局域网的路由设备还 是通过软件来实现。 软件实现的路由查找算法分为两类，一类是以b i n a r y t r i e t 7 【8 】 9 1 【1 0 】结构为基 础的算法，这类算法通过对b i n a r y t r i e 结构作了一些算法时间和空间上的优化来加 快高速的路由。其中l u l e a t 】查找算法通过将第一、二级路由表项进行压缩，放入 a 卯的c a c h e 中实现高速的路由查找。但是这些算法的路由更新需要较长的时间。 还有一类是二分查找算法【1 2 】【1 3 1 属于区间查找算法，通过逐步缩小查找区间的范围 来实现路由的查找。这类算法用硬件实现比较团难。 硬件实现的路由查找方法也主要是通过t c a m 来实现，使用t c a m 来实现路 由查找的优点是只需要一次目的地址匹配就可以得到下一跳的端口号，但是使用 t c a m 实现路由查找的缺点在于t c a m 存储的路由前缀项要按前缀长度排序，而 且t c a m 功耗很大。所以科研人员一直在研究克服t c a m 缺点的方法。 1 3 路由器发展现状和研究中存在的问题 随着光传输技术的飞速发展，无论是单波长载荷速率还是单纤可用波长数量， 每年都以极其惊人的速度在增长，核心传输网和边沿接入网已经进入1 0 g b p s 的 p o s 和1 0 g b p s 的l a n ( l o c a la r e an e t w o r k ，局域网) 厂 a n ( w i d ea r e an e 咖r k ，广 域网) 接e l 时代。因此，高端路由器要求支持1 0 g b p s 的p o s 接口和l a n w a n 接 山东大学硕士学位论文 口。 同时，随着i p v 6 t 1 4 】1 1 5 】和m p l s 1 6 1 1 7 】技术的进步，p 网络需要并正在承载各种 不同的业务。t 比特路由器作为核心传输网的重要组成设备，其对口v 4 ，v 6 ，m p l s 的全面支持显得尤为重要： 一方面，现在i n t o n e t 运行的i p 协议主要是i p v 4 1 8 】协议。随着i p v 4 地址空间 的枯竭和i p v 6 所独有的富裕的地址空间、较好的安全保证和更多的业务支持等优 势的日益突显，面向下一代网络n g n ( n e x tg e n e r a t i o nn e t w o r k ) 的i p v 6 协议必将 得到越来越多地应用。i p v 6 核心标准日臻成熟，协议体系日趋完善。虽然i p v 6 路由查找和流量处理等算法还不够成熟，但是i p v 6 技术体系基本框架己经确定。 i p v 6 作为i p v 4 唯一的替代者，其在下一代网络的地位已经得到国际承认，i p v 4 网络必定向i p v 6 网络过渡的趋势已经非常明朗。作为面向新一代互联网的核心网 络路由器，t 比特路由器必须在i p 协议的支持上实现i p v 4 ，i p v 6 的双协议栈支持。 另一方面m p l s 将第三层路由技术和第二层交换技术相结合，发挥了第三层 路由的灵活性和第二层交换的高速性，是应用前景非常广阔的高速网络技术。采 用m p l s 的动因之一就是避免逐跳的路由决策，减少对数据分组的高层协议分析， 借助标记建立第二层的快速路径，使得数据沿着这条预先建立的路径快速移动。 m p l s 把用户数据流根据需求和流量特性分成转发等价类进行聚集转发，提高了可 扩展性与资源利用率。m p l s 技术在骨干网络的流量工程、v p n 和服务质量等方 面也得到了应用，并显示出强大的技术牛命力。近年来，m p l s 技术规范不断走向 成熟，技术体系逐渐完善，正日益成为一种较为理想的骨干网络构建技术。 因此，基于传统的算法的路由器已经不能满足当前路由器的业务需求，新的 支持i p v 4 、i p v 6 、m i p s 路由查找算法的研究已经迫在眉睫，支持多种业务的高 速路由架构也成了网络的普遍需求。 1 4 本文的主要工作 6 首先总结了网络地址协议的变化历程，并介绍了现在路由查表所面临的 丰要问题 总结了基本的路由查找的软件算法，简要说明了基于t c a m 的硬件查找 山东大学硕士学位论文 算法。 概括了路由器结构的进化历程，总结了路由器查找c p u 的发展过程，提 出了基于多核处理器实现的第六代路由器结构的概念。并介绍了当前应 用较多的一种典型的多核处理器x l r 7 3 2 的架构。 路由查找转发引擎是路由器的关键功能单元，本论文利用t c a m 和多核 处理器开发出一种高效路由查表转发引擎。 创新性的应用f p g a + t c a m 的形式实现了一种性能、成本、功耗等方面 均很有竞争力的路由查表结构。对后续的网络搜索引擎单元的设计有很 好的借鉴意义。 1 5 本文的组织结构及安排 本文的主要内容安排如下： 第二章首先介绍了口地址结构的变化，由此引出地址查找越来越复杂，路由 表项越来越多。接着讲述了现代高速路由查找技术所面临的问题，并介绍了路由 查找一些常用的算法，包括软件算法和硬件t c a m 实现的算法。 第三章讨论了路由器发展的结构的变化，逐一列出了第一代路由器架构到第 五代路由器架构，并在些基础上提出了利用多核处理器实现的第六代路由器架构 的概念，介绍了第六代路由器的平台架构。详细比较说明了路由器c p u 的演进历 程，说明了m u l t i - c o r e 是将来的发展趋势，并介绍现在市场上典型的多核处理器 x l r 7 3 2 的情况。 第四章集中介绍了一个基于t c a m 技术和多核处理器实现的一种高效的支 持多种协议，处理能力达1 0 g 的查找转发引擎的设计。分别从转发层和查找引擎 两个方面进行了讨论实现。并详细介绍本本查找引擎的实现方式。基于t c a m 和 多核处理器及d d r i is d r a m 的实现。从成本，性能，功耗等方面达到尽可能的 优化。 第五章简要总结了本论文的丰要内容和创新点进行了说明，并对下一步的研 究方向提出了作者的观点。 7 山东大学硕士学位论文 第二章路由查找技术 2 1 地址结构的发展变化 l p v 4 为目前i n t e m e t 上广泛使用的i p ( i n t e r n e tp r o t o c 0 1 ) 版本。它的地址为 3 2 b i t s ，分为网络号( n e t i d ) 和_ 丰机号( h o s t i d ) 两个部分，用( n e t i d , h o s t i d ) 表示。其中 n e t i d 表示一个网络，h o s t i d 表示该网络中的一个丰机，同属一个网络中的丰机应 该具有相同的n e t i d 和不同的h o s t i d 。在m 协议最初提出的时候采用的是基于类 的地址结构，后来为了解决地址利用效率低和路由表膨胀太快的问题，i n t e r n e t 工 作组i e t f 于1 9 9 3 年9 月提出了无类域问路f l j ( c l a s s l e s s i n t e r - d o m a i n r o u t i n g ，c i d r l 概念，这一变化解决了地址利用效率低的问题但却增加了查表问题的复杂性。虽 然c i d r 在一定程度上缓解了当时i p v 4 所面临的问题，但是却不能从根本上解决 网络规模的不断增加的趋势。由i e t f 设计的用来替代现行的i p v 4 协议的i p v 6 协议应运而生。 2 1 1 基于类的地址结构 基于类的地址结构把i p 地址划分为5 类：a 、b 、c 类用于单播业务，d 类用 于组播业务，e 类保留给其它应用。地址所属的类别通过口地址的最高几位来区 分。各类单播地址的n e t i d 和h o s t i d 位数都不同，因为不同地址类型的网络能容纳 的丰机数也不相同。如表2 1 所示。 表2 1 基于类的地址划分 一：一 牛： 誊篡憾t i a 叠 蒿菘参蕊蔓舻筹：孤零囊? 曩蓍：争蠹?麓：；奘嚣：j h 最高诅) _ 但： 0 n c t i d ： ：一 一j i ：， ：a 戆： 0b i t s1 7 b i t s8 3 l 0 0 0 0 一i2 7 2 5 5 2 5 5 2 5 5 ；。i b 。簪 i ob i t s2 一1 5 b i t s1 6 3 i 1 2 8 0 0 o - 1 9 1 2 5 5 2 5 5 2 5 5 一：i 奄i i 鼍：；： 1 1 0b i t s3 2 3 b i t s2 4 3 11 9 2 o 0 0 - 2 2 3 2 5 5 2 5 5 2 5 5 j ：墩组插) ： 1 1 1 0 2 2 4 0 o j o 2 3 9 2 5 5 2 5 5 2 5 5 t 【保留 越 1 1 1 1 0 2 4 0 0 0 0 _ 2 5 5 2 5 5 2 5 5 2 5 5 山东大学硕士学位论文 随着i n t e r a c t 的发展，这种地址分配方式存在的问题逐渐暴露出来： 第一个问题是口地址空间消耗太快。造成这一问题的原因在于按照 n e t i d h o s t i d 长度固定来分配网络地址的方法极不灵活，导致m 地址的浪费。例如， 如果一个组织要申请多于2 5 4 个m 地址，该组织就会被分配一个可以容纳6 5 5 3 4 个主机的b 类网络号。到1 9 9 2 年2 月，1 2 6 个a 类地址己经分配了4 6 个，1 6 3 8 2 个b 类地址也分配了5 4 6 7 个；而到1 9 9 3 年1 月，分配的a 类地址己达到5 2 个， b 类地址达到7 1 3 3 个。按照这种速度，当时预计在1 5 个月内，所有的b 类m 地 址将被耗光，尽管实际使用的口地址还不到1 。 第二个问题是路由表的大小呈指数增长。这是由于路由器需要为每一个网络 号保存一个表项，导致了d 路由表的大小增长过快。路由表过大对处理器的处理 能力和存储容量带来很高要求，同时它使得路由表查找速度变慢。 2 1 2 无类域问路由 为减缓骨干路由表的增长速度，提高口地址空间的利用率，i n t e r n e t 工作组提 出了无类域问路由技术。在分配地址时网络号不再限制为7 ，1 4 或者2 1 b i t s ，可以 为任意长度。c i d r 的网络号用i p 前缀( p r e f i x ) 表示，前缀的有效长度可以从0 到 3 2 b i t s ( 实际中最短的前缀长度为8 b i t s t l 9 1 ) 。i p 前缀的表示方法为p r e f i x l e n g t h ，其 中p r e f i x 为主机地址或者网络号，l e n g t h 为前缀的长度。例如，8 8 9 2 1 9 7 8 3 2 为 3 2 b i t s 网络前缀，2 0 2 1 1 3 0 0 1 6 为1 6 b i t s 的网络前缀。采用c i d r 技术后，如果一 个机构需要申请3 0 0 个地址，可以为该机构分配2 3 b i t s 的网络前缀，从而使p 地址的分配更为合理有效。 变长网络前缀的采用使得i p 地址的层次化分配成为可能。i n t e m e t 骨干的i s p 首先申请较短的网络前缀，然后在该地址空间内向更小的i s p 或者机构分配更长 的网络前缀。i p 地址的层次化分配使得i s p 在向更高层发布路由信息时可以对该 信息进行聚合。图2 1 显示的是地址聚合示例。 9 山东大学硕士学位论文 图2 1 地址聚合示例 在图中，s 和t 连接到i s pp 。分配给i s p p 的网络前缀为1 9 2 2 0 0 2 2 ，在这 一区间内，p 向s 分配了前缀1 9 2 2 1 彤2 4 ，向t 分配了前缀1 9 2 2 2 0 2 4 ，这样在 p 的节点r 2 向骨干网发布路由信息时，只需要发布表项1 9 2 2 0 0 2 2 。地址聚合使 得骨干网络上的路由信息大大减少【2 0 1 ，据统计在采用c i d r 之后的1 9 9 4 1 9 9 8 年间， 路由表的增长趋势接近线性，而不是在这之前的指数关系【2 1 1 。有效地减缓了路由 表增长的速度。 采用c i d r 之后，路由转发表的基本形式为 。 如果网络前缀的有效位与目的l p 地址的这几位相等，则称目的i p 地址与该网络前 缀匹配。这样，查表的过程就变成了寻找匹配路由表项的过程。 2 1 3i p v 6 地址结构 i p v 6 被称作下一代互联网协议，它是由i e t f 设计的用来替代现行的i p v 4 协 议的一种新的i p 协议。与i p v 4 的3 2 位地址相比，i p v 6 的地址要长的多，i p v 6 共有1 2 8 位的地址，i p v 6 的提出从根本上解决了网络规模的不断增加的趋势。相 应的，i p v 6 在地址空间分配上也进行了相应的改变。虽然，i p v 6 的结构和空间上 有了很大的变化。但是，其地址空间仍然是层次结构。所以，其路由查找方法和 i p v 4 的路由查找方法没有本质的区别，还是基于c i d r 地址结构的网络聚集。 1 0 山东大学硕士学位论文 2 2 查找技术面临的问题 2 2 1 链路速率飞速发展 物理链路速率的提高要求路由表查找速度也要相应提高。在给定链路速率情 况下，一般考查以下两种查表速度：一种是按照i n t e r a c t 最短分组长度和最坏情况下 的查表速度；另一种是按照平均分组长度的平均查表速度。其中前者一般是对具有 流识别能力、支持实时业务的系统的要求，以保证所要求的分组延时等性能。在 i n t e m e t 的网络流量中，仅t c p 回应报文( 2 0 字节的口头+ 2 0 字节t c p 头，计4 0 字节) 就占4 0 左右，因此对第一种情况要求按分组长度4 0 字节计算陋】，对o c l 9 2 链路接口来说最坏情况下的查询速度需要达到3 1 2 5 m p p s ( p a c k e t sp e rs e c o n d 分组 秒) 。对不提供流识别的系统，由于分组可以在查表之前被适当地缓存，因此可以 按照平均分组长度和平均查表性能来计算。假如平均分组长度为2 4 0 字节，对 o c 1 9 2 接口，平均查表速度只要达到5 2 1 m p p s 即可。表2 2 给出了查表性能与链 路速率和分组长度之间的关系。 表2 2 各种链路下的线带查表速率要求 ：- 链路速率岳o 字节分组弘字节分组2 4 0 字节分组 链路 ；( m p p s )( b l p p m ) “ 【g b p s )：( b l p p s ) ! t l0 o o l 50 0 0 4 6 8o 0 0 2 20 0 0 0 7 8 o c - 3 一，0 1 5 5o 4 8 0 2 ：l0 0 8 ：；o c - 1 2 0 6 2 21 9 曩0 9 20 3 2 3 一：0 1 2 - 4 81 i ：2 5 07 8 l3 。7 2上3 7 ；o c - 1 9 2 。” 1 0 o3 1 21 4 95 2 i ：。o c - 7 胡j 耋o o1 2 5 0s 9 52 0 8 哇 摹千沌以太隔 1 - o1 d 9o 5 2 上表中千兆以太网的接口与其它类型的接口不大相同，丰要原因在于以太网 的最小帧长为6 4 字节，加上2 0 字节的前导码和分组间隙，共计为8 4 字节。因此 对于6 4 字节的千兆以太网分组，实际的传输速率仅为7 6 2 m b p s ，所以要求的查表 速率为1 4 9 m p p s 。 制约路由表查找速度的最大问题是存储器的访问时间。由于路由表越来越大， 山东大学硕士学位论文 静态r a m 的存储容量相对较小，价格偏高，因此目前大多采用d r a m 来存储路 由表。访问一次d r a m 按照5 0 n s 计算，对于o c 1 9 2 接口，即使按照平均分组长 度计算，查表速率也要达到5 2 1 m p p s ，相当于1 9 0 n s 必须完成一次查找动作，这 样最多只能读三次存储器【1 9 】。因此设计查表算法时需要尽量减少存储器的访问次 数，以提高查询速度。 2 2 2 路由表增长迅速 越来越多的网络设备接入i n t e m e t ，维护这些设备间可达性信息的路由表也在 不断增长。为了减轻骨干网络路由表增长的压力，人们使用c i d r 、网络地址转换 ( n e t w o r ka d d r e s st r a n s l a t i o n ，n a t ) 等技术来允许在两个不同的网络地址域间进行 一定的透明交互。然而这并没有停止路由表的增长，因为路由受网络拓扑结构、 自治系统个数以及一个路由表项覆盖的地址数目等综合因素影响。当一个网络向 外部路由域广播路由更新信息时，这个路由项就会在整个i n t e r n e t 的所有外部路由 域间传播。图2 2 为i n t e m e t 骨干网络路由表增长统计曲线【2 3 1 ，截至2 0 0 8 年骨干 网络路由表已经超过2 5 0 ，0 0 0 项，而且还在继续增长。 曼 耋 暑 ： 岔 图2 21 9 8 9 2 0 0 8 骨干网路由表大小增长曲线 山东大学硕士学位论文 2 2 3 最长前缀匹配复杂 在基于类的地址结构下，路由器按照地址的不同类型( a ，b ，c 类) 把路由表 分成三个部分。如图2 3 所示，路由器收到分组后，首先通过目的地址的高位判断 分组所属类别，以决定采用哪个转发表，然后用n e t i d 在相应的转发表中进行精确 匹配。由于同一表项的n e t i d 长度固定( 对a ，b ，c 类地址分别为7 ，1 4 ，2 1 ) ，因 此精确匹配可以通过h a s h 算法或者是其它一些快速查找算法来实现【2 0 】【2 4 1 。但是基 于类的地址结构使得路由表呈指数次方飞速增长，以至于为了降低路由表增长的 速度，人们不得不放弃这种精确匹配结构。 糟譬袭 图2 3 基于类的路由查找结构 c i d r 的使用，使得d 地址的分配层次化。i s p 向更高层发布的是聚合后的路 由信息。聚合以后的路由前缀对应的是一段地址空间，多个目的地址可以与之匹 配。 路由聚合技术延缓了路由表的增长速度，t u 同时又带来新的问题：如果一个 机构更换了i s p ，但它仍然倾向于使用原来的i p 地址，在原来的i s p 中就会造成 地址空间的不连续。在这种情况下，路由器需要为该机构保存一条更详细的路由 信息，并按照该信息来转发分组。这时一个目的地址既匹配聚合后的前缀，同时 它还匹配该机构的更详细的路由信息，经过判断最终选取后者作为路由转发信息。 山东大学硕士学位论文 这种一个目的地址对应多个网络前缀的选取问题就是最长前缀匹配的问题。 所谓最长前缀匹配是指在所有与数据分组目的l p 地址匹配的表项中选取有效前缀 最长的表项。 表2 3 某路由器的路由表 i li -。1 ： ： ；i ：转发螭1 7 i - ，表项编号。 曩尊颦长度：掣” i ：爱：陋踌地址1 0 二螂妒：兰； 1 0 o 0 0 ，81 2 1 3 1 1 2a ：；i j 毫；- ：乏- 。；i ，： i o 2 0 0 1 61 2 1 3 z 5 5b 簿，：3 ：餐等 1 0 2 3 1 i & 仍22 i 4 3 - 2 4 1 llc 冬兰逑一： l 删i 1 9 2 2 61 2 】3 2 5 5 b _ 羔舅毒： 1 0 2 3 1 0 2 41 2 1 3 2 5 5b ：! ：二曩豇一 1 9 8 1 5 3 0 陀41 0 2 1 4 6 3 4 1 3 8d ! - 二7 咖i ? 乏1 0 2 3 l - 1 5 4 脚2 1 4 3 2 4 i llc 例如，某路由器有表2 3 所示的七个表项，此时有一数据分组到来，且该分组 的目的地址为1 0 2 3 1 1 8 3 ，显然该地址与表项l ，2 ，5 ，7 都匹配。根据最长前缀匹配 原则，由于表项7 为最长匹配，因此分组被转发到端口c 。 2 3 路由查找的一些概念和典型算法 数据包进入路由器后，首先进行路由查找，然后在调度器的管理下由输出端 口进入交换结构，到输出端口。因此路由查找是数据转发重要的一步。由于当前 的路由查找需要采用最长前缀匹配算法，使得查找过程变得困难。由于需要路由 器转发的数据流量不断增长，要求不断提高路由查找的效率，所以路由查找技术 受到广泛的重视。 由于路由查找日益成为提高数据转发效率的瓶颈，人们试图避开它，提出了 多协议标签交换m u l t i p r o t o c o ll a b e ls w i t c h i n gm p l s 技术。当一个数据包进入基 于m p l s 建立的网络时，就被分配标记( l a b e l ) 。当该数据包被转发到下一跳路 由器时，标记也随着一起向前传送。此时，不需要进行路由查找，只需要根据标 记来决定转发的端口。由于基于标记选择路由的复杂度远小于基于地址前缀的路 由查找复杂度，所以可以实现很高的效率。但是，在m p l s 中的标记只能在其特 定网络中有意义，不能像i p 地址在整个因特网中是唯一的标识，即只能在建立 1 4 山东大学硕士学位论文 m p l s 的网络内部消除基于地址前缀的路由查找。由于每个数据包进入、离开基 于m p l s 建立的网络时，都必须进行路由查找。因此完全消除路由查找是不现实 的。 由于路由查找无法彻底避开，学术界和路由器开发商开展了多方位的研究， 提出了一系列的路由查找算法。下面介绍路由查找的基本概念和一些典型的算法。 2 3 1 路由表 路由器最基本的功能是转发数据包到达目的地，即依据每个到达数据包的目 的地址，在路由信息库一路由表中，找到转发到下一跳的端口。路由表是路由协 议所收集的路由信息，其中最基本的内容是：到达目的网络p i 的数据包，由编号 为h i 的端口转发，即路由表是在目的网络与路由器端口编号之间建立对应关系： f ：t h 其中t _ p i ，i - l ，2 ，3 ，n ) ，n 为网络( 地址前缀) 数，h = h i ，i - l ，2 ，3 ，m m 为路由器端口数。 当数据包到达时，在t 中搜索数据包目的地址d 所属的网络p i ，然后得到转发 端口为h j = f ( p j ) 。这一过程称为路由查找。 在i p v 4中， i p地址是3 2位长二进制的数字，如 1 0 0 0 0 0 1 0 0 1 0 1 0 1 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 0 。为了便于人们书写常表示为：1 3 0 8 6 1 6 6 6 ， 即将3 2 位分为4 个8 位的二进制数，每个部分用一个十进制数表示。每个3 2 位 i p 地址分为两个部分：最前面的，位用作网络标识，后3 2 ，位用作主机标识。从 d ，- - t l t 2 t 3 t f 0 0 0 0 ( 3 2 位) 到d 2 = t , t 2 t 3 t ，1 1 1 l ( 3 2 位) 连续的口地址都有相 同的前，位p = t t t 2 t 3 t ，( t i = 0 ，l ，为长度) ， 即为该地址范围的网络标识，称为 i p 地址前缀( p r e f i x )记为：p 。常见有两种表示形式：二进制形式 ( 1 0 0 0 0 0 1 0 0 1 0 1 0 11 0 0 0 0 1 2 0 ) 、十进制形式( 1 3 0 8 6 1 6 2 0 ) ，其中2 0 表示地址前 缀的长度。表2 4 是个简单路由表的示例。 山东大学硕士学位论文 表2 4 路由表示例 地址前缀( 网络标识) 只 转发端口厄 二i ：i f 制形式 进制形武下跳的i p 地址端口编号 0 0 0 1l 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 2 0 2 4 4 0 3 2 2 01 9 2 4 1 1 7 7 1 4 82 0 1 0 11 0 1 0 0 1 0 0 11 0 0 1 6 1 3 0 8 6 1 61 9 2 4 1 1 7 7 1 8 1 6 11 0 1 0 0 0 0 0 0 0 0 11 0 0 0 0 0 1 2 0 2 0 8 1 2 1 6 2 01 9 2 4 1 1 7 7 2 4 l4 1 1 0 l o o 0 0 0 0 0 0 l1 0 0 0 0 0 1 0 1 0 1 2 42 0 8 1 2 2 1 2 4 1 9 2 4 1 1 7 7 1 9 61 1 0 1 0 0 1l1 0 0 0 1 1 0 0 0 0 1l o o l l1 2 4 1 6 7 2 4 1 0 3 2 41 9 2 4 1 1 7 7 34 2 3 2 地址前缀匹配 字符串的匹配是一种常见的搜索技术。例如，对于数据集合，需要判别元素 a 是否存在其中。这时，要以a 作为关键码搜索集合a 。根据集合a 的特点，常 常采用不同的匹配方式，如精确匹配( e x a c tm a t c h i n g ) 、 子串匹配( s u b s t r i n g m a t c h i n g ) 、模式匹配( p a t t e mm a t c h i n g ) 等。 这里，需要判别口地址：d = s l s 2 s 3 s 3 2 ，( s i = 0 ，1 )是否属于地址前缀 p - - t l t 2 t 3 t ，所表示的口地址集合。因为地址前缀p 表示从d l = t l t 2 t 3 t ，0 0 0 0 ( 3 2 位) 到d 2 = t i t 2 t 3 - - t ，1 l l l ( 3 2 位) 连续的i p 地址集合，因此d 属于p 的充 要条件是： s i = t i ，i 亍l ，2 ，3 ，。如果d 属于p ，称d 与p 匹配。 2 3 3 传统的路由查找算法 线性查找( l i n e a rs e a r c h ) ：将路由表中的地址前缀用线性链表结构组织起来， 每次查找需要遍历链表中的所有表项( 地址前缀) ，同时纪录最长的地址前缀项，直 到遍历完整个链表为止对于个地址前缀的路由表查找过程的复杂度为o p t ) ， 存储空间复杂度为o p t ) ，插入、删除表项的复杂度为d 。如果链表中数据项按 照地址前缀的长度递减的顺序组织，在查找过成中一旦出现能匹配的地址前缀， 则该地址前缀即为所查找的最长匹配的地址前缀。这样，可以提高查找的平