（通信与信息系统专业论文）交换式路由器研究与设计.pdf

中国科学技术大学博士学位论文 摘要 摘要 f 在当今信息社会，因特网的规模迅速扩大，对网络带宽的需求不断上升。w w w 用户的 大量增加使提供信息服务的主机数不断增加；另方面，网络业务种类也在不断扩展，视频 和音频相结合的多媒体技术所占的比重越来越大。这些原因使i n t e m e t 的流量以每年4 倍的 速度递增，人们对网络带宽的需求比以往任何时候都更加迫切。 作为全球化的计算机网络，i n t e r n e t 通过路由器将世界各地的计算机连接起来。传统的 路由器处理分组的能力有限，并且只能提供尽力服务，成为因特网进一步发展的瓶颈。为了 解决这个问题，人们重新审视了传统路由器的结构，提出了交换式路由器的体系结构。 从目前来看，国内的网络设备总体水平还很落后，就交换式路由器来说，国内产品的寻 路转发等核心部件基本上还是依赖于国外厂商。作为网络互联的关键设备，研制具有自主知 识产权的交换式路由器成为当务之急。在这背景下彳席实验室参加了九五攻关8 6 3 - 3l 7 主 题的子课题“实用化综合接入系统”，承担了边缘路由器的研制工作，以掌握边缘路由器的 核心技术，设计出具有自主知识产权的边缘路由器。本论文就是围绕这一课题展开的。 作为路由器的一个核心部件，路由表查询速度对路由器的性能有至关重要的影响。论文 首先给出了查表算法的研究背景，介绍了现有的高速路由表查询算法以及这些算法的优缺 点，在此基础上提出了基于硬件的可扩展高速路由表查询算法，给出了扩展前缀情况下最优 步长的选择公式，并进行了仿真。由于i p v 6 取代i p v 4 是i n t e r n e t 发展的必然趋势，我们给 出了算法在i p v 6 下的应用。l 该算法消除了基于前缀长度的二分法查找中的h a s h 过程；从仿 真性能来看，相对于扩展前缀方法，在相同条件下这一算法减少了表项更新时存储器的修改。 同时，由于算法简单，容易实现，因此有很高的实用价值。 多媒体业务的发展要求路由器能够提供服务质量保证，实现这要求的前提是路由器能 够识别不同的流，这就是分组识别的功能。在这一部分中，论文介绍了分组识别的应用背景， 以及在我们的路由器设计中采用的多维投影算法，并给出了硬件实现。 路由器的队列管理及交换结构的仲裁也是路由器设计的核心内容。缓存方式涉及到交换 结构的选择；队列调度算法关系到路由器能够提供的服务质量保证：交换结构的选择以及采 用的仲裁算法对路由器的性能有重要影响。了捧论文通过讨论包括队列缓存、交换结构仲裁、 队列调度、拥塞控制算法在内的各种算法原理，给出我们在设计时所选用的算法以及选用依 据。由于我们的设计中存在端口复用，如果输出端队列管理不当，很容易造成队头阻塞，影 响输出端的吞吐量。针对这一问题尹论文提出了分组重组算法和基于输出子端口的队列组织 算法，使输出端的吞吐量达到1 0 0 。为提高交换效率，简化交换结构仲裁模块的设计，内 部交换时我们用的是定长信元。定长信元交换必然带来额外开销，如信元头部开销、数据交 换的同步开销等，不同的信元长度会使交换结构的利用效率有所不同。针对这一点，我们推 导出了交换结构平均利用效率的计算公式，对选择最佳信元长度具有一定的指导意义。 在研究与实现路由器关键技术的基础上，论文实现了具有九十年代末先进水平的交换式 边缘路由器。憾路由器用压缩树算法进行路由表查询；用多维投影法对分组分类；用w r e d 算法实现拥塞控制；用i s l i p 算法实现了c r o s s b a r 交换结构的仲裁：用d r r 算法进行输出 端的队列调度。除此之外，该路由器的主要特色有：在输出端填写数据链路帧头，以简化输 入端的处理，有利于提供多种接口类型；由控制与路由处理模块产生a r p 解析报文，以简 化线路卡的设计；采用校验和的累加更新技术更新校验和，减少逻辑开销；利用论文提出的 中国科学技术大学博士学位论文摘要 基于目的子端口的队列组织与管理算法来解决端口复用情况下存在的队头阻塞问题；利用操 作系统提供的虚拟网络设备功能，充分利用操作系统已有的网络处理协议栈，简化软件设计 的工作量：根据i n t e m e t 分组长度分布，利用论文给出的信元长度与交换结构效率的关系公 式，确定最佳的信元长度。在路由器设计中，所有核心模块都由f p g a 编程实现，对掌握 路由器的核一t l , 技术具有重要意义 ， 结合路由器的设计，论文还提出了数字通信系统f p g a 的协同仿真方法，对降低仿真 与调试工作量有一定的指导意义。 关键词：路由器，查表算法，分组识别；队列调度，交换结构，f p g a 仿真 a b s t r a c t n o w a d a y s t h es c a l eo f t h ei n t e m e te n l a r g e sr a p i d l y , a n dt h ed e m a n df o rn e t w o r kw i d t hh a s b e e ns c a l i n gu pt oa nu n b e l i e v a b l ed e g r e e d r a m a t i c a l l yi n c r e a s e da m o u n t o f t h ew o r l dw i d ew e b u s e r sh a v eb r o u g h tm o r ei n f o r m a t i o ns e r v e r so n l i n e f u r t h e r m o r e ，t h et y p e s o ft h en e t w o r k s e r v i c e sh a v eb e e nl a r g e l yi n c r e a s e d ，a n dt h ep r o p o r t i o no f m u l t i m e d i at e c h n o l o g i e si n t e g r a t e db y v i d e oa n da u d i ob e c o m e sl a r g e r , a l lt h e s er e a s o n sh a v em a d et h ei n t e r n e tt r a f f i ci n c r e a s e4t i m e s p e ry e a r , a n d t h ed e m a n df o rn a t w o r kw i d t hb e c o m e sm o r eu r g e n tt h a ne v e r t h ei n t e m e ti t s e l fi sag l o b a lc o m p u t e rn e t w o r k i n gt h a tc o n s i s t so fc o m p u t e r si n t e r c o n n e c t e d b y c o m m u n i c a t i o nl i n k sw i t hi n t e r m e d i a t es w i t c h i n gp o i n t sc a l l e dr e u t e r s t r a d i t i o n a lr e u t e r sh a v e b e c o m et h eb o r l e n e c ko ft h ei n t e m e tf o rt h a tt h ep a c k e tp r o c e s s i n gc a p a b i l i t i e sa r el i m i t e d ，a n d t h e yc o u l do n l yp r o v i d eb e s te f f o r t s e r v i c e s f o rt h i s r e a s o n ，p e o p l eh a v e1 0 0 k e da t t h eb a s i c b o r l e n e c k p o i n t si na t r a d i t i o n a li pr o u t e r , a n dp r o p o s e dt h ea r c h i t e c t u r ee r as w i t c h i n gr o u t e r a saw h o l e ，w ea r eb e h i n dt h ed e v e l o p m e n ti nt h et e c h n o l o g yo fn e t w o r ke q u i p m e n t s t h e k e yc o m p o n e n t se r as w i t c h i n g r o u t e rl i k et h ef o r w a r d i n ge n g i n ea r em o s t l yd e p e n d i n go nf o r e i g n c o u n t r i e s i ti sa nu r g e n ta f f a i rt od e v e l o po u ro w r ls w i t c h i n gr o u t e r , a si t st h ek e ye q u i p m e n tf o r n e t w o r ki n t e r c o u n e c t i o n i nt h e s ec i r c u m s t a n c e s ，o u rl a b o r a t o r yt o o kp a r ti nt h ep r o j e c tn a m e d 。p r a c t i c a li n t e g r a t e da c c e s ss y s t e m w h i c hi sl i s t e di nt h en a t i o n a l8 6 3h i g ht e c h n o l o g yr e s e a r c h & d e v e l o p m e n tp r o j e c t w eu n d e r t o o kt h er e s e a r c ha n dd e s i g nt a s ko fa ne d g er o u t e r , s oa st o g r a s pt h ek e yt e c h n o l o g i e sa n dd e v e l o p o u ro w n e d g er o u t e r t h i st h e s i si so n t h i sp r o j e c t a so b eo ft h ek e yc o m p o n e n t s ，t h es p e e do ft h et a b l el o o k u pm o d u l eh a sm u c he f f e c to nt h e r o u t e r s p e r f o r m a n c e t h i st h e s i s f i r s t s p e c i f i e st h er e s e a r c hb a c k g r o u n d ，i n t r o d u c e s c u l t e n t h i g h s p e e da l g o r i t h m sa n dt h e i rp r o sa n dc o n s a f t e rt h i s ，w ep r e s e n to u rh a r d w a r eb a s e d s c a l a b l e h i g h s p e e dl o o k u pa l g o r i t h m a n dt h es t r i d e s s e l e c t i n gf o r m u l a ，t o g e t h e rw i t h t h e s i m u l m i o nr e s u l t s f o ri ti st h et r e n dt or e p l a c ei p v 4w i t hl p v 6 ，w ea l s os h o wt h ea p p l i c a t i o ni n i p v 6t h i sa l g o r i t h me l i m i n a t e st h eh a s h i n gp r o c e s st h a ti sn e e d e di np r e f i x - l e n g t hb a s e db i n a r y s e a r c h c o m p a r e d w i t ht h ep r e f i x e x p a n s i o nm e t h o d s ，t h i sa l g o r i t h md e c r e a s e st h eu p d a t e d m e m o r ye l e m e n t s a tt h es a m et i m e ，i ti sq u i t ee a s yt oi m p l e m e n tt h i sa l g o r i t h m s oi ti s q u i t e v a i n a b i e r e n t e r sm u s tp r o v i d eg u a r a n t e e ds e r v i c et om e e tt h er e q u i r e m e n t so fm u l t i m e d i as e r v i c e s t h i sr e q u i r e st h a tr e u t e r sc a ni d e n t i f yp a c k e t sb e l o n g i n gt od i f f e r e n ts t r e a m s t h i si st h ef u n c t i o n o fp a c k e tc l a s s i f i c a t i o n i nt h i ss e c t i o n ，t h et h e s i si n t r o d u c e si t s a p p l i c a t i o nb a c k g r o u n d ，a n dt h e m u l t i d i m e n s i o n a lr a n g em a t c h i n g a l g o r i t h mu s e di no u rd e s i g n w ea l s op r e s e n tt h eh a r d w a r e i m p l e m e n t a t i o n t h eq u e u em a n a g e m e n ta n dt h ea r b i t r a t i n go fas w i t c h i n gf a b r i ca r ea l s ot h ek e yc o n t e n t si n t h er o u t e rd e s i g n t h eq u e u i n gm e t h o dc o n c e r n sw i t ht h ec h o i c eo ft h e s w i t c h i n gf a b r i c ；t h e s c h e d u l i n ga l g o r i t h mc o u n t sm u c hf o rt h ep e r f o r m a n c eo f t h er o u t e r o nt h eb a s i so f d i s c u s s i n 2t h e a l g o r i t h m si n c l u d i n gt h eq u e u i n gm e t h o d s ，a r b i t r a t i n go ft h es w i t c h i n gf a b r i c ，q u e u es c h e d u l i n g ， c o n g e s t i o nc o n t r o l l i n g ，e t c ，w ep r e s e n t t h e a l g o r i t h m s u s e di no u rr o u t e r s i n c et h e r e s p o r t - m u l t i p l e x i n gi no u rd e s i g n ，i tm a y c a u s eh e a do fl i n ec o n g e s t i o ni ft h eo u t p u tq u e u ei s n o t t r e a t e dp r o p e r l y t h i st h e s i sp r e s e n t st h e p a c k e t sr e c o m b i n i n ga n dq u e u em a n a g e m e n t a g o r i t h m 一b s t r a c t - _ - _ _ _ _ _ _ - _ _ _ _ _ _ _ _ _ _ _ - _ _ - _ _ _ _ - _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ - _ _ - _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ b a s e do ns u b p o r t st os e t t l et h i sp r o b l e m t h i sa l g o r i t h mc a na c h i e v e1 0 0 t h r o u g h p u t f i x e d l e n g t hc e l l sa r eu s e d t oi m p r o v et h es w i t c h i n ge f f i c i e n c ya n ds i m p l i f yt h ed e s i g no ft h ea r b i t r a t i n g m o d u l ei ta g a i nb r i n g sa d d i t i o n a lc o s t sl i k ec e l lh e a dc o s t s y n c h r o n i z a t i o nc o s t ，e t c d i f f e r e n t l e n g t h sb r i n gd i f f e r e n te f f i c i e n c i a s s ow ep r e s e n t t h ee x p r e s s i o n st oc a l c u l a t et h eu s a g ee f f i c i e n c y o f t h es w i t c h i n gf a b r i c t h i si sq u i t ev a l u a b l ei np r a c t i c e b a s e do nt h er e s e a r c ha n dd e s i g no ft h ek e yt e c h n o l o g i e s w ei m p l e m e n t e das w i t c h i n ge d g e r o u t e r , t h i sr o u t e ri sb a s e do nt h ef o l l o w i n ga l g o r i t h m s ：c o m p r e s s e d - t r i ea l g o r i t h mf o rr o u t i n g t a b l el o o k u p ；m u l t i d i m e n s i o n a lr a n g em a t c h i n gf o rp a c k e tc l a s s i f i c a t i o n ；w r e df o rc o n g e s t i o n c o n t r o l ；i s l i pf o rc r o s s b a ra r b i t r a t i n g ；d r rf o ro u t p u tq u e u es c h e d u l i n g a p a r tf r o mt h e s e ，t h e r o u t e rc o n t a i n st h ef o l l o w i n gc h a r a c t e r i s t i c s ：t h ed a d a 1 i n kl a y e rh e a di sf i l l e di nt h eo u t p u tp o r ts o a st o s i m p l i f yt h ei n p u tp r o c e s s i n g a n dp r o v i d em u l t i p l ei n t e r f a c et y p e s ；a r pp a c k e t sa r e g e n e r a t e db yt h ec o n t r o la n dr o u t ep r o c e s s i n gm o d u l et os i m p l i f yt h ed e s i g no ft h el i n ec a r d ；1 p c h e c k s u ma r eu p d a t e du s i n gt h ei n c r e m e n t a lu p d a t i n gt e c h n i q u e ss oa st or e d u c et h el o g i cc o s t s w eu s et h eq u e u em a n a g e m e n ta l g o r i t h mp r e s e n t e di nt h i st h e s i st h a ti sb a s e do no u t p u ts u b - p o r t t os e t t l et h eh e a do fl i n eb l o c k i n g ；w eu s et h ev i r t u a ln e t w o r kd e v i c ef u n c t i o np r o v i d e db yt h e o p e r a t i n gs y s t e mt ot a k ef u l l u s eo ft h ee x i s t i n gn e t w o r kp r o t o c o ls t a c k ，s oa st o s i m p l i f yt h e s o f t w a r ed e s i g n ；w ec h o o s et h ec e l ll e n g t hb yc a l c u l a t i n gt h ee f f i c i e n c ya c c o r d i n gt ot h ei n t e m e t p a c k e tl e n g t hd i s t r i b u t i o n a l lo f t h ek e ym o d u l e si nt h er o u t e ra r ei m p l e m e n t e di nf p g a s ，s oi ti s v e r yh e l p f u lt og r a s p t h ek e y t e c h n o l o g i e so f a ni pr o u t e r b a s e do nt h ed e s i g no f t h er o u t e r , t h i st h e s i sp r e s e n t st h ef p g ac o s i m u l a t i o na l g o r i t h mu s e d i nad i g i t a lc o m m u n i c a t i o n s y s t e m i ti sh e l p f u lt or e d u c et h es i m u l a t i o na n dd e b u g g i n gw o r k l o a d k e y w o r d s ：r o u t e r , r o u t et a b l el o o k u pa l g o r i t h m ，p a c k e tc l a s s i f i c a t i o n ，q u e u e s c h e d u l i n g ， s w i t c h i n gf a b r i c ，f p o as i m u l a t i o n 主里型兰垫查查兰堡主兰焦堡苎! 已! ! 堡 1 1i n t e r n e t 发展概况 第一章绪论 近年来，随着通信技术与计算机技术的飞速发展，i n t e m e t 规模不断扩大，i n t e r n e t 入网 的主机数、上网的人数都在飞速增长。图1 1 给出的是从1 9 9 1 年到2 0 0 1 年i n t e r n e t 入网主 机数的增长曲线【9 】 4 8 】，预计到2 0 0 5 年间，入网主机总数将达到1 , 0 0 0 ，0 0 0 ，0 0 0 台【5 5 ；表 1 - l 和图1 2 给出了在线用户数统计 1 0 4 9 ，预计到2 0 0 5 年，在线用户总数也可以达到 1 0 0 0 0 0 0 0 0 0 人。在a n 主机数和上网人数增长的同时，i n t e m e t 的网站数量也在上升( 图 l 一3 ) f 4 9 1 ，到2 0 0 1 年3 月，商业网站( 仅t o m ) 已经达到3 6 ，3 5 2 ，2 4 3 个 5 0 1 。主机数、上 网人数以及网站数目的增长使得i n t e m e t 的流量以每年4 倍的速度递增 7 】 8 1 0 ( 图1 4 ) ， 预计到2 0 0 5 年，骨干节点的流量可以达到1 0 0 t b p s 。 图1 11 9 9 1 年l j 2 0 0 1 年i n t e r n e t 主机数增长曲线 9 1 ( 单位：百万) 图卜2i n t e r n e t 全球在线用户数变化趋势 4 9 】 份 日期( 年b ) 2 0 0 1 ，82 0 0 0 8 1 9 9 9 8 1 9 9 8 9 1 9 9 7 11 1 9 9 6 1 21 9 9 5 1 2 【在线人数 5 1 3 4 13 6 8 5 41 9 5 1 91 4 77 63 61 6 ( 百万) 表l - 1 i n t e m e t 全球在线用户数统计 1 0 1 年一 崔喾 熹 如 们船 。 ! 望型兰垫垄奎兰壁主兰堡丝壅 一j 兰生! ! 垒 图卜3i n t e r n e w e b 站点增长趋势 4 9 图1 4 美国i n t e r n e t 流量趋势图 在i n t e r n e t 的规模飞速增长的同时，业务种类也越来越多，由数据通信、e m a i l 、w w w 业务向集音频、视频数据为体的多媒体方向发展。 1 2 路由器的研制背景 路由器工作在o s i 第三层即网络层，是i n t e r n e t 网络互联的主要设备，负责连接不同的 子网，把从输入链路接收到的分组转发到相应的输出链路 1 】。路由器位于i n t e m e t 的各个层 次( 图1 - 5 ) ：接入网中的路由器可以把家庭用户或者小的企业用户接入到i s p ( i n t e m e ts e r v i c e p r o v i d e r ，i n t e m e t 业务供应商) ；边缘路由器位于骨干网的边缘，汇聚校园或者公司中上万 台计算机的业务量：骨干网中的路由器并不直接与终端用户相连，而是通过长距离链路连接 2 ! 里型兰垫查查兰竖主兰垡笙兰 一墨二兰! ! 鱼 1 2 1 路由器的结构 图1 - 5i n t e m e t 层次划分【2 】 图1 - 6 是路由器的结构简图，一般由四个部分组成：输入端口，输出端口，交换结构， 以及路由处理器。输入端口与物理链路相连，是到达分组的入口点：交换结构负责连接输入 和输出端口；输出端口对分组进行发送调度；路由处理器运行路由协议，并产生转发表用丁 分组转发。 输入端口 画 图1 6 路由器结构简图( 【3 】，p 3 3 3 ) 根据输入端口和交换结构的相对速率，路由器可以分为输入缓存和输出缓存两种：如果 交换结构的交换容量大于各输入端口带宽之和，则分组在输出端排队，称为输出缓存方式： 否则，分组在输入端排队，称为输入缓存。 交换结构可以分为三种：共享存储器型；总线型；交叉连接即c r o s s b a r 型。 共享存储器型 共享存储器结构如图1 7 ( a ) 所示。工作过程为：由输入端口把接收到的分组或者拆分后 的信元写入到存储器，然后由相应的输出端口读出。在早期的路由器中，一般是由各线路卡 通过d m a 送给与c p u 相连的存储器，由c p u 对分组寻路，然后再通过d m a 送给相应的 输出端口。一般来说，这种结构受存储器的带宽限制，系统容量很难提高。但是近年来又提 出了一些新的技术，如j u n i p e r 的分布式共享缓存等，使这种技术也可以用在高端路由器中。 中国科学技术大学博士学位论文 第一章绪论 目前采用共享缓存的还有c i s c o 的c a t a l y s t 8 5 0 0 1 8 等。 旧口一 _ 口e e 3 - 一- 佃口p 存储器 咖卿u 画 佃口卿卜 卅圆口d ( a ) 共享存储器型 妇口卿卜忡r 呼 佃口p枷vl 一 妇口圃c p 硼卿口d 总线 ( b ) 总线型 ( c ) 交叉连接型 图1 7 三种交换结构示意图( f 3 】，p 3 3 7 ) 总线型 在这种交换结构中，输入端口通过共享总线到达输出端口( 图l - 7 ( b ) ) 。由于每一个分 组都要经过该总线，系统的整体性能受到一定限制，同时也不利于扩充系统容量。但是近年 来的高速总线技术使传输速率可以达到gb i t 级，再加上实现简单，在目前的中低端路由器 中应用也很广泛，如c i s c o 的c a t a l y s t 5 0 0 0 1 7 1 系列等。 交叉连接( c r o s s b a r ) 型 这种结构由连接n 个输入和n 个输出端口的2 n 条总线构成。如图1 7 ( c ) 所示，如果到 达输入端口a 的分组目的端口为x ，则通过连接a 端口的水平线和x 端口的垂直线，可以 实现a 到x 的数据传输而不影响其它输入输出端口。由多个c r o s s b a r 组成的交叉连接阵列 可以使系统交换容量达到几十g 、几百g 甚至t 级，因此在高端路由器中使用比较普遍， 例如c i s c o 的1 2 0 0 0 系列1 2 0 就采用了这一结构。 4 ! 里型兰垫查查兰堡主兰垡堡苎 笙二兰! ! 鱼 1 2 2 路由器的发展演变 到目前为止，路由器结构的发展经历了三代，由第一代的软件转发发展到第三代的分布 式处理，劳正在向第四代并行交换和光交换方向发展一 ( 1 ) 第一代路由器：单c p u 结构 图1 _ 8 给出了第1 代路由器的结构。它采用通用c p u ，用软件转发分组：一条共享总线 连接了c p u ，存储器和所有的接口卡。接口卡上的输入端 e l 收到分组后，将分组通过共享 总线送至c p u ，通过软件对分组寻路；软件作出转发决定后，该分组再次通过共享总线送 至输出端口。这种结构的主要缺点是：每个分组要经过共享总线两次，系统的性能依赖于共 享总线的传输速率和c p u 的处理能力；c p u 要处理每个到达的数据包，成为系统的瓶颈。 图l 8 第一代路由器结构 2 】 ( 2 ) 第二代路由器：线路卡具有寻路转发能力 第2 代路由器的结构如图1 - 9 所示，主要是对线路卡作了改进。在线路卡上有一定容量 的存储器，以及用来存储路由信息的本地c a c h e 。接收到分组后，首先在本地c a c h e 中查找， 如果没有找到转发项，则送给c p u ，由c p u 对分组寻路。c p u 作出转发决定后，同时在相 应接口卡的本地c a c h e 中加入该转发项，使此后到达的属于该流的分组可以通过查询线路卡 上的本地c a c h e 直接转发1 。如果c a c h e 的命中率较高，大部分的数据包只需要使用一次共 享总线，提高了系统的吞吐能力，也减轻了c p u 的处理负担。但是随着因特网规模的不断 扩大和路由器端口速率的不断增加，路由器每个端口上同时存在的流的数目也在不断增加， 造成c a c h e 命中率的下降【4 ，降低了路由器的性能：另外共享总线方式所能提供的带宽不 能适应网络发展的需要。在这种情况下人们又提出了第三代路由器的结构。 ( 3 ) 第三代路由器：分布式处理和交叉连接型的交换结构 图1 1 0 是第三代路由器的结构示意图。与传统的路由器不同，第三代路由器采用了分布 式处理结构，在各个线路卡上都有自己的处理单元，可以对分组寻路。除此之外，第三代路 由器主要有以下几个特点： l 、数据通道与管理通道分开。路由协议及网管等对实时性要求不是很高，这一部分可 以和数据通道分开。在图中，由控制卡上的c p u 运行路由协议，生成路由转发表， 并且将完整的路由转发表下载到所有的线路接口板：线路接口板在收到分组后，根 据自己的路由转发表对分组进行寻路转发2 。这种寻路可以采用通用c p u ( 大都用 r i s c 处理器) 用软件实现，或者是通过专用集成电路( a s i c ) 实现。 由于线路卡的转发表与接收到的流有关，这种转发方式也称为流驱动的分组转发 2 由于线路卡的路由表中拥有网络连接的完整拓扑结构。这种转发方式也称为拓扑驱动的分组转发。 5 主垦型鲎垫查查兰堕主堂堡笙塞 一一生二童堕坠 2 、用交叉连接型的交换结构代替共享总线，以提高系统的总容量，因此这种路由器也 常称为交换式路由器。 3 、有些路由器提供多层交换功能，即按照i p 分组的多个域( 如源、目的l p 地址，协议类 型，源、目的端口号等) 来划分流，为不同的流提供不同的服务。对第四层头标的 识别能力又称为第4 层交换。 图1 - 9 第_ 二代路由器结构【2 】 图1 - 1 0 第三代路由器的结构【2 】 1 2 3 交换式路由器的研制背景 l t t t e r n e t 流量的增长以及业务的多样化使路由器面临四个关键问题：链路速率、吞吐量、 分组转发速率以及对分组的识别( 即流划分，或称分类) 能力。目前，光纤链路所提供的容 量以大约每年两倍的速度增长( 表1 - 2 ) ；总线型和共享存储器型交换结构由于受总线或者 存储器带宽的限制，很难提供大的交换容量，而由交叉连接型的交换芯片组成的交换阵列可 以实现从几g b s 到t b s 量级的交换。对后两个问题，一方面，i n t e r n e t 路由器在转发i p 分 组时，要采用最长网络前缀匹配方式对i p 分组进行寻路【1 5 】，这比采用定长的标号查询路 由表要困难得多；另一方面，确定分组所属的流涉及到i p 分组的多个域，并且还存在规则 重叠的问题( 这点在后面将有介绍) ，相对于查表来说难度更大。对这两个问题，目前主 要有以下两种解决方案： 1 、标号交换。在网络边缘，仍然采用最长网络前缀匹配对分组寻路转发，并通过分组 的相关域来识别分组所属的流，以提供相应的服务。而在网络的核心，通过定长标 号直接对分组进行识别和寻路，加快分组的寻路转发速度。 6 中国科学技术大学博士学位论文 第一章绪论 2 、分布式处理。用分布式处理取代集中式处理结构，在备线路板上直接进行分组识别 和寻路。这种结构把分组的处理、寻路等放在各线路板，减轻了控制板( 即路由处 理器) 的处理负担，也便于扩充系统容量。近年来在查表和分组的分类算法上面有 很大突破，使这种路由器的端口速率可以达到o c - 1 9 2 ( | 0 g b s ) 甚至更高。 系统描述 光纤容量时间 ( 波长数x 单路容量) 8 x 25 g b s2 0 g b s1 9 9 6 1 6 x 2 5g b s4 0 g b s1 9 9 7 3 2 x 2 5g b s8 0 g b s1 9 9 9 8 0 x 2 5g b l s2 0 0 g b s2 0 0 0 4 0 x l og b s4 0 0 g b sm i d t o l a t e2 0 0 0 1 6 0 x 2 5g b s4 0 0 g b sm i d t 0 1 a t e2 0 0 0 8 0 x 1 0g b s8 0 0 g b sl a t e2 0 0 1 1 6 0 x 1 0g b sl6 t b sl a t e2 0 0 2 4 0 x 4 0g b s1 6 t b sl a t e2 0 0 2 8 0 x 4 0g b s32 t b sl a t e2 0 0 3t oe a r l y2 0 0 4 l 1 0 0 x 4 0g b s4 t b s 2 0 0 5 l1 6 0 x 4 0g b s6 4 t b s 2 0 0 7 表1 - 2 光纤容量发展趋势 1 i 】 同标号交换方式相比，采用分布处理的交换式路由器( 即第三代路由器，简称交换式路 由器，以下同) 不需要对现有的网络作大的改动，不需要增加新的协议，可以逐步替换现有 的路由器，从而升级网络。另外，即使采用标号交换，在网络的边缘仍然需要采用路由器， 随着骨干网链路速率的提高，边缘路由器的端v i 速率也将越来越高。也就是说采用标号交换 仍然需要处理速度更快、性能更高的路由器。 正是由于这些原因，国外许多厂商都在开发交换式路由器，目前也已经有不少这类产品。 从国内的情况来看，虽然也有了一些类似的产品，但寻路转发等核心芯片基本上还是依赖于 国外厂商，或者是直接用通用r i s c 处理器来实现。例如国内电信设备厂商华为公司的骨干 路由器n e 8 0 就采用了i b m 的网络处理芯片。 从目前的发展形式来看，电信网和计算机网的融合是大势所趋，而网络的核心设备就是 路由器。在这一背景下，开发具有我们自主知识产权的交换式路由器、用硬件实现寻路转发 具有非常重要的意义。 1 3 高速路由表查询算法的研究背景 i 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 ，分为 网络号( n e t i d ) 和主机号( h o s t i d ) 两个部分，用( n e t i d , h o s t i d ) 表示，其中h p 删表示一个 网络，h o s t i d 表示该网络中的一个主机：同一个网络中的主机具有相同的”p 耐和不同的 h o s t i d 。在i p 协议最初提出的时候采用的是基于类的地址结构，后来为了解决地址利用效率 低和路由表膨胀太快的问题，i n t e m e t 工作组i e t f 于1 9 9 3 年9 月提出了“无类域问路由” ( c 1 d r ，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 的提出背景以及 i n t e m e t 路由器在c i d r 下的查表操作，在此基础上给出研究高速路由表查询算法的意义。 7 中国科学技术大学博士学位论文 第一章绪论 1 3 1基于类的地址结构与分组寻路 基于类的地址结构把l p 地址划分为5 类：a 、b 、c 类用于单播业务，d 类用于组播业 务，e 类保留给其它应用。地址所属的类别通过i p 地址的最高几位来区分。各类单播地址 的n e t i d 和h o s t i d 比特数都不同，因此不同地址类型的网络能容纳的主机数也不相同，如表 1 3 所示。 类最高( 几) 位 n 吼i dh o s f i d范围 0 0 0 0 aob i t s l 7b i t s8 3 l 1 2 7 2 5 5 2 5 5 2 5 5 1 2 8 0 0 0 一 b1 0b i t2 1 5b i t1 6 3 1 1 9 1 2 5 5 2 5 52 5 5 1 9 2 0 。0 0 c1 1 0b i t3 2 3b i t2 4 - 3 1 2 2 3 2 5 5 2 5 5 2 5 5 2 2 40 00 d ( 组播) 1 1 1 0 2 3 9 2 5 52 5 5 2 5 5 2 4 0 0 0 0 e ( 保留) 1 1 1 l o 2 5 5 2 5 5 2 5 52 5 5 表1 3 基于类的地址划分 在基于类的地址结构下，路由器通常按照地址的不同类型( a ，b ，c 类) 把转发表( 即