（计算机科学与技术专业论文）并行路由器体系结构及其关键技术研究.pdf

国防科学技术大学研究生院博士学位论文 摘要 i n t e m e t 网络流量、规模和应用的快速发展对互联网核心路由器设计提出了重 大挑战。随着光纤传输带宽和入网主机数目的日益增长，路由器交换容量及端口 密度难以适应网络流量的增长需求；随着网络规模的急剧扩张尤其是多宿主技术 的广泛应用，路由器转发能力难以适应f i b ( f o r w a r d i n gi n f o r m a t i o nb a s e ) 表容量 的指数级增长；随着i p v 6 、q o s 、组播、安全等应用的发展，路由器报文处理能力 难以解决网络流量增长和报文处理复杂度增长之间的矛盾。在路由器中引入并行 处理技术的并行路由器体系结构为提高路由器转发交换能力提供了有效途径。 采用并行设计给路由器带来了负载均衡和报文乱序两大问题。负载均衡是实 现延迟和吞吐率保证的关键，但负载均衡可能导致报文乱序，进而可能触发t c p 连接不必要的重传和超时，降低t c p 吞吐率，增加报文延迟。如何解决这对矛盾 是并行路由器设计的难点。已有的维序调度算法，要么需要复杂的通信或集中式 的调度，要么依赖简单的分布式调度而缺乏吞吐率保证。针对以上问题，本文通 过深入分析并行路由器体系结构队列模型和信元分布特性，提出了兼顾负载均衡 和报文保序，降低调度复杂性和通信开销，并能提供延迟和吞吐率保证的分布式 负载分配方法和协同调度机制。 现有的路由器包含转发和交换两个连续的处理阶段，它们在硬件实现上是分 离的，报文转发与交换的串行执行不利于路由器并行性的开发。本文原创性地提 出一种同时开发转发与交换平行度的报文处理机制，将f i b 查找功能分解并映射 到交换网络中分布执行，为解决目前骨干路由器设计所面临的f i b 处理极限问题 提供理论、技术和实践支持。 论文针对目前并行路由器设计所面临的负载均衡、报文乱序、延迟和吞吐率 保证、通信复杂性及f i b 极限等问题进行了深入研究，主要研究成果及创新包括 以下几个方面： 1 针对并行路由器设计负载均衡与报文保序之间的矛盾，提出一种基于流映 射的细粒度负载分配算法u f f s k ( u n i f o r mf n e g r a i nf r a m es p r e a d i n g ，k 为聚合粒 度，简称u f f s k ) ，u f f s k 算法分布于各输入端口独立执行，根据本地v o q 队列 信息分派信元，不需要任何通信开销，以o ( 1 ) 时间复杂度实现了1 0 0 的吞吐率并 能保证报文的顺序。模拟结果显示，u f f s k 算法能够有效降低信元延迟并具有较 好的负载均衡特性。 2 针对异构型并行路由器设计受限于通信及调度的复杂性，难以保证报文的 顺序且硬件实现复杂的问题。基于c i o q 交换平面，提出一种具有按序排队特性 第i 页 国防科学技术大学研究生院博+ 学位论文 的i o q ( i n o r d e rq u e u e i n g ) p p s 体系结构，在输入端轮询( r o u n dr o b i n ) 分派 算法和中间级c i o q 交换平面同步调度算法之间设计了一种简单的协同调度机制， 保证同一条流的信元按序从交换平面读出，避免了输出端报文重定序开销。i o q p p s 在多个独立的交换平面间执行报文流级的负载均衡，消除了中间级交换平面的 加速需求。模拟结果表明，i o qp p s 在同类p p s 设计中具有最优延迟性能。 3 针对并行路由器设计所面临的f i b 处理极限问题，提出一种在交换网络中 执行转发操作的新型报文处理机制f i s ( f o r w a r d i n gi ns w i t c h i n g ) 。f i s 将i p 查找 功能进行分解并映射到多个硬件同构的具有独立转发交换功能的f s n ( f o r w a r d i n g a n ds w i t c h i n gn o d e ) 结点分布执行，通过分解f i b 表，构建f i b 表到f s n 结点的 映射，降低了i p 查找复杂度；f i b 表的分布式存储，解决了并行查找机制访存瓶 颈问题，提高了路由器f i b 扩容能力。论文对f i s 实现关键技术转发表的分 解、子树到f s n 结点的映射及面向f i s 的i p 查找机制进行了深入的研究，给出了 相应的解决方案，为f i s 原型验证系统的设计与实现奠定了基础。 4 面向f i s 处理特性，提出了基于前缀范围的i p v 6 二分查找算法p s b b s ( p r e f i xs c o p eb a s e db i n a r ys e a r c h ) ：基于前缀范围的子树表示法消除了对路径信 息的保存，降低了存储开销；基于前缀范围的二分查找策略能有效压缩查找路径， 减少访存次数。通过构造p s b b s 算法二分查找树实现i p v 6 转发表到f s n 结点的 映射，仿真实验结果表明，随前缀数目的增加，每一级f s n 结点的平均查找次数 几乎没什么变化，反映了p s b b s 算法良好的可扩展性。 综上所述，本文针对并行路由器设计的几个关键问题提出了有效的解决方案， 对提高路由器的性能、规模、可扩展性，以及推进路由器并行技术的实用化具有 一定的理论意义和应用价值。 主题词：并行路由器设计、体系结构、负载均衡、报文维序、f i s 、部分转发 国防科学技术大学研究生院博士学位论文 a bs t r a c t c o n t i n u i n gg r o w t hi nt r a f f i c ，t h es i z eo fi n t e r n e ta sw e l la st h ei n t e r a c ta p p l i c a t i o n s p u t sf o r w a r dg r e a tc h a l l e n g et ob a c k b o n er o u t e rd e s i g n f i r s t ，t h ec a p a c i t ya n dp o r t d e n s i t yo ft h es w i t c hc a nh a r d l yk e e pu p 、析mt h eg r o w t ho ft r a f f i cr e s u l t i n gf r o m i n c r e a s i n gl i n ks p e e d sa n dt h en u m b e ro fh o s t so nt h ei n t e r a c t s e c o n d ，i p - l o o k u p p e r f o r m a n c ei nc o r er o u t e r sc a nh a r d l yk e e pu pw i t ht h eg r o w t ho ff i bs i z er e s u l t i n g f r o mw i d e l yu s e dm u l t i h o m e dt e c h n o l o g ya n di n c r e a s e di n t e m e ts i z e t h i r d ，w i t ht h e d e v e l o p m e n to fi n t e m e ta p p l i c a t i o n ss u c ha si p v 6 ，q o s ，m u l t i c a s t ，s e c u r i t y ，e t c p a c k e t p r o c e s sp o w e rc a nh a r d l yf i xt h ec o n t r a d i c t i o nb e t w e e ni n c r e a s i n gp a c k e tr a t ea n d i n c r e a s i n gc o m p l e x i t yo fp a c k e tp r o c e s s i n g r e c e n t l y ，p a r a l l e lr o u t e ra r c h i t e c t u r e s i n t r o d u c i n gp a r a l l e l i s mi n s i d er o u t e r sa p p e a r st ob ea ne f f i c i e n tw a yt os c a l ei n t e m e t r o u t e r st ov e r yh i 曲c a p a c i t i e sa n d f o r w a r d i n gr a t e s p a r a l l e ld e s i g nb r i n g sl o a db a l a n c i n ga n d p a c k e tr e o r d e r i n gp r o b l e m si n s i d er o u t e r s l o a db a l a n c i n gi sp r e r e q u i s i t et oa c h i e v i n gd e l a ya n dt h r o u g h p u tg u a r a n t e e si np a r a l l e l r o u t e ra r c h i t e c t u r e s u n f o r t u n a t e l y ，l o a db a l a n c i n gm a yi n c u ro u t o f - o r d e rp a c k e t s w h i c ht r i g g e ru n n e c e s s a r yr e t r a n s m i s s i o n sa n dt c pt i m e o u t s ，t h u sd e c r e a s i n gt c p t h r o u g h o u ta n di n c r e a s i n gp a c k e td e l a y h o wt od e a lw i t ht h i sc o n t r a d i c t i o ni sac r u c i a l p r o b l e mi np a r a l l e lr o u t e rd e s i g n t h ee x i s t i n gs c h e d u l i n gm e c h a n i s m sm a i n t a i n i n g p a c k e to r d e r i n ge i t h e rr e q u i r ec o m p l e x ，c e n t r a l i z e ds c h e d u l e r s ，o rr e l yo ns i m p l e d i s t r i b u t e ds c h e d u l i n ga l g o r i t h m st h a tl a c kt h r o u g h p u tg u a r a n t e e s a i m i n ga tt h e p r o b l e m sa b o v e ，b yt h o r o u g ha n a l y z i n gq u e u i n gm o d e la n dd i s t r i b u t i o np r o p e r t i e so f c e l l si n p a r a l l e l r o u t e ra r c h i t e c t u r e sw ep r o p o s eal o a d b a l a n c i n gt e c h n i q u ea n da c o o p e r a t i v es c h e d u l i n gm e c h a n i s mw h i c ha r ea l ld i s t r i b u t e da n dc a ne n f o r c ep a c k e t o r d e r i n ga n dl o a d b a l a n c i n g ，r e d u c ec o m p l e x i t yo fs c h e d u l i n ga n dc o m m u n i c a t i o n o v e r h e a da sw e l la sp r o v i d ed e l a ya n dt h r o u g h p u tg u a r a n t e e s ar o u t e rl o g i c a l l yc o n s i s t so ft w oc o n s e c u t i v es t a g e sn a m e l yf o r w a r d i n gs t a g ea n d s w i t c h i n gs t a g e t h e s et w op r o c e s s i n gs t a g e sa r ei m p l e m e n t e di nd i f f e r e n th a r d w a r e c o m p o n e n t sa n dp e r f o r m e di no r d e r ，w h i c hh i n d e r sp a r a l l e l i s md e v e l o p m e n ti n s i d e r o u t e r s w eo r i g i n a l l yp r o p o s ead i s t i n c tp a c k e tp r o c e s s i n gm e c h a n i s mc o n c u r r e n t l y e x p l o i t i n gp a r a l l e l i s mo fs w i t c h i n ga n df o r w a r d i n go p e r a t i o n s t h i sp a c k e tp r o c e s s i n g m e c h a n i s mp a r t i t i o n sf i bl o o k u pf u n c t i o na n dd i s t r i b u t e sf i bl o o k u p st os w i t c hf a b r i c s s oa st od i s t r i b u t e d l yp e r f o r mp a c k e tf o r w a r d i n gi nt h ep r o c e s so fp a c k e ts w i t c h i n g ， w h i c hp r o v i d et h e o r e t i c a l ，t e c h n i c a la n dp r a c t i c a lv a l u ef o r s o l v i n gf i bl i m i t s c o n f r o n t i n gm o d e m r o u t e r s w em a k ec o m p r e h e n s i v er e s e a r c ho nc r u c i a lp r o b l e m so fl o a db a l a n c i n g ，p a c k e t r e o r d e r i n g ，d e l a ya n dt h r o u g h p u tg u a r a n t e e s ，c o m m u n i c a t i o nc o m p l e x i t ya n d f i bl i m i t s f o rp a r a l l e lr o u t e rd e s i g n t h em a j o rc o n t r i b u t i o n so ft h i sd i s s e r t a t i o na r ea sf o l l o w s 第i i i 页 国防科学技术大学研究生院博士学位论文 1 t om a k eab e t t e rt r a d e o f fb e t w e e nl o a db a l a n c i n ga n dp a c k e to r d e r i n gw e p r o p o s eaf i n e g r a i n e df r a m ed i s p a t c h i n ga l g o r i t h mc a l l e du f f s - k ( u n i f o r mf i n e - g r a i n f r a m es p r e a d i n g ( u f f s - k ，w h e r eki st h ea g g r e g a t ef a c t o r ) b a s e do nf l o wm a p p i n g w h i c hi sd i s t r i b u t e da n dc a no p e r a t ei n d e p e n d e n t l yi ne a c hi n p u t u f f s kd i s p a t c h e s c e l l sb a s e do nl o c a lv o q s s t a t ei n f o r m a t i o n ，m o r e o v e r ，w i t h o u ta n yc o m m u n i c a t i o n o v e r h e a di tg u a r a n t e e sp a c k e to r d e r i n ga n da c h i e v e s10 0 t h r o u g h p u tw i t ho ( 1 ) t i m e c o m p l e x i t y a st h es i m u l a t i o nr e s u l t sd e m o n s 仃m e ，u f f s - kr e d u c e sp a c k e td e l a y c o n s i d e r a b l ya n dh a s b e t t e rc a p a c i t yo fl o a db a l a n c i n g 2 d u et oc o m m u n i c m i o na n ds c h e d u l i n gc o m p l e x i t y ，h e t e r o g e n e o u sp a r a l l e lr o u t e r a r c h i t e c t u r e sh a v ed i f f i c u l t i e si nm a i n t a i n i n gp a c k e to r d e r i n ga n di m p l e m e n t i n g 、析t l l l o w - c o s th a r d w a r ec o m p o n e n t s w ep r o p o s ea ni o q ( h a - o r d e rq u e u i n g ) p p s a r c h i t e c t u r eb a s e do nc i o qs w i t c hp l a n e s b yu s i n gas i m p l ec o l l a b o r a t i v es c h e d u l i n g m e c h a n i s mb e t w e e nr o u n d - r o b i nd e m u l t i p l e x i n ga ti n p u t sa n ds y n c h r o n o u ss w i t c h i n ga t c e n t r a ls w i t c hp l a n e s ，o u rs c h e m eg u a r a n t e e saw a yf o rc e l l so faf l o wt ob er e a di n o r d e rf r o md i f f e r e n ts w i t c hp l a n e s ，t h u sa v o i d i n gp a c k e tr e o r d e f i n ga to u t p u tp o a s i o q p p sa c h i e v e sp a c k e t - l e v e ll o a db a l a n c i n go v e rm u l t i p l ei n d e p e n d e n ts w i t c hp l a n e sa n d e l i m i n a t e st h es p e e d u pr e q u i r e m e n tf o rt h ei n t e r n a ls w i t c hp l a n e s a st h ee x p e r i m e n t r e s u l t sd e m o n s t r a t e ，i o qp p so f f e r si m p r o v e dd e l a yp e r f o r m a n c ec o m p a r e dt oe x i s t i n g p p sd e s i g n s 3 t oa d d r e s sf i bl i m i t sc o n f r o n t i n gp a r a l l e lr o u t e rd e s i g n ，w ep r o p o s eap a r a l l e l p a c k e tp r o c e s sm e c h a n i s mp e r f o r m i n gp a c k e tf o r w a r d i n g i ns w i t c hf a b r i c s - - f i s ( f o r w a r d i n gi ns w i t c h i n g ) w h i c hp a r t i t i o n si pl o o k u pf t m c t i o na n d d i s t r i b u t e si pl o o k u p s t om u l t i p l el o w e rs p e e da n dh e t e r o g e n e o u sn o d e sc a l l e df s n ( f o r w a r d i n ga n d s w i t c h i n gn o d e ) w h i c hp e r f o r m sf o r w a r d i n ga n ds w i t c h i n gi n d e p e n d e n t l y b y p a r t i t i o n i n gf i bt a b l ea n db yc o n s t r u c t i n gm a p p i n gr e l a t i o n s h i pb e t w e e nf i b t a b l ea n d f s n s ，i p l o o k u pc o m p l e x i t yi sr e d u c e dc o n s i d e r a b l y f u r t h e r ，t h ed i s t r i b u t e ds t o r i n go f f i bt a b l ea m o n gf s n se l i m i n a t e sm e m o r yb o t t l e n e c ko fp a r a l l e ll o o k u pm e c h a n i s m ， t h u si m p r o v i n gt h ef i bs c a l a b i l i t yo fm o d e mr o u t e r s w em a k ec o m p r e h e n s i v er e s e a r c h o nt h ek e yt e c h n o l o g i e so ff i sm e c h a n i s mi n c l u d i n gt h ep a r t i t i o no fr o u t i n gt a b l e ，t h e l o g i c a lm a p p i n g f r o ms u b t r i e st of s n s ，a sw e l la st h ef i s o r i e n t e d i p l o o k u p m e c h a n i s m o u rw o r ku n d e r l i e st h ed e s i g na n di m p l e m e n t a t i o no ff i sh a r d w a r e p r o t o t y p es y s t e m 4 w ep r o p o s ea ni p v 6b i n a r yl o o k u pa l g o r i t h mb a s e do np r e f i xs c o p ec a l l e d p s b b s ( p r e f i xs c o p eb a s e db i n a r ys e a r c h ) f o rp u t t i n gf i si np r a c t i c e t h ee f f i c i e n c yo f p s b b sa l g o r i t h mc a nb ea t t r i b u t e dt ot w ok e ya s p e c t s f i r s t ，t h es u b t r i ef o r m a tb a s e d o np r e f i xs c o p ee l i m i n a t e st h ep r e s e n t a t i o no fp a t hi n f o r m a t i o nw h i c hc o n t r i b u t e st oa r e d u c t i o ni nt h em e m o r ys p a c eo c c u p i e db yt h es e a r c hs t r u c t u r e s e c o n d ，t h eb i n a r y s e a r c hs c h e m eb a s e do np r e f i xs c o p ec o m p r e s s e st h es e a r c hp a t h ，t h u sr e d u c i n gt h e n u m b e ro fm e m o r ya c c e s s w em a pi p v 6f o r w a r d i n gt a b l et of s n si nf i sb y 第i v 页 国防科学技术大学研究生院博士学位论文 c o n s t r u c t i n g b i n a r y s e a r c ht r i eo fp s b b s a l g o r i t h m t h ee x p e r i m e n tr e s u l t s d e m o n s t r a t et h ea v e r a g es e a r c ht i m eo ff s nv a r i e ss t a b l yw i t ht h ei n c r e a s e dn u m b e ro f p r e f i x e s ，w h i c hr e f l e c tb e t t e rs c a l a b i l i t yo fp s b b sa l g o r i t h m i ns u m m a r y ，o u rw o r kp r e s e n t ss o l u t i o n st os e v e r a lk e yp r o b l e m so f p a r a l l e lr o u t e r d e s i g n ，a n dh a sa c a d e m i ca n dp r a c t i c a lv a l u ef o ri m p r o v i n gt h ep e r f o r m a n c e ，s i z ea n d s c a l a b i l i t yo fm o d e r nr o u t e r sa n da d v a n c i n gt h ep r a c t i c a b i l i t yo fp a r a l l e lt e c h n o l o g i e s f o rr o u t e r s k e yw o r d s ：p a r a l l e lr o u t e rd e s i g n , a r c h i t e c t u r e ，l o a db a l a n c i n g ，g u a r a n t e e i n g p a c k e to r d e r i n g ，f i s ，p a r t i a lf o r w a r d i n g 第v 页 国防科学技术大学研究生院博十学位论文 表目录 表6 1 真实i p v 6 转发表标记开销( 标准二分查找结构) 7 5 表6 2 真实i p v 6 转发表标记开销( 非对称二分查找结构) 7 8 表6 3 真实i p v 6 转发表子树和前缀分布信息7 8 表6 4f i s 在真实i p v 6 转发表下的查找性能( 非对称二分映射) 7 8 表6 5f i s 在真实i p v 6 转发表下的查找性能( 二次二分映射) 7 9 表6 6 真实i p v 6 转发表标记开销( 二次二分映射) 7 9 第1 v 页 国防科学技术大学研究生院博士学位论文 图1 1 图1 2 图2 1 图2 2 图2 3 图2 4 图2 5 图2 6 图2 7 图2 8 图3 1 图3 2 图3 3 图3 4 图3 5 图3 6 图3 7 图3 8 图3 9 图3 1 0 图4 1 图4 2 图4 3 图4 4 图4 5 图4 6 图4 7 图5 1 图5 2 图5 3 图5 4 图5 5 图目录 网络流量、传输容量和路由器性能的发展2 基于三级交换结构的并行路由器模型4 3 x 3c i c q 交换结构1 3 不同的缓冲区尺寸下的交换吞吐率1 4 为获得1o o 吞吐率所需加速比1 4 改进的带缓冲的c r o s s b a r 体系结构( n = 3 ) 1 6 基于两级c r o s s b a r 的负载均衡交换结构1 7 带流分离操作的并发匹配交换结构c m s 1 9 基于( a ) 单级m e s h 网络( b ) a w g r 的负载均衡路由器体系结构2 0 并行报文交换p p s 体系结构2 1 负载均衡路由器中的报文乱序现象2 9 负载均衡交换结构3 l 将同一条流的2 个单位帧发送到不同的区域所产生的信元乱序现象一3 2 流到区域的映射过程3 3 循环映射算法结果( _ 3 2 ，肛8 ) 3 4 u f f s k 算法描述3 6 f o f f 、u f s 、u f f s k 及b l a 算法平均延迟( 贝努利一致流量模型) 。4 0 f o f f 、u f s 、u f f s k 及b l a 算法平均延迟( 突发流量模型) 4 1 u f f s k 算法在不同聚合粒度下的负载均衡度( 贝努利一致流量模型) 4 2 u f f s k 算法在不同聚合粒度下的负载均衡度( 突发流量模型) 4 3 基于c i o q 交换平面的i o qp p s 体系结构一4 7 分流控制器体系结构( k = 3 ，= 2 ，s = 1 ) 4 8 o q 、i s l i p 以及各种p p s 系统平均延迟( 贝努利一致流量模型) 5 4 o q 、i s l i p 以及各种p p s 系统平均延迟( 突发流量模型) 5 5 i o qp p s 加速比实验的延迟性能5 6 i o qp p s 交换平面数目实验的延迟性能( 第一种情况) 一5 7 i o qp p s 交换平面数目实验的延迟性能( 第二种情况) - 5 7 f b s 与f i s 处理流程的比较5 9 基于分布式转发交换的并行路由器模型一6 0 i p 查找树分解后得到的子树结构6 l 子树到f s n 结点的映射6 3 子树的迁移6 3 第v 页 国防科学技术大学研究生院博士学位论文 图5 6 图5 7 图5 8 图6 1 图6 2 图6 3 图6 4 图6 5 图6 6 图6 7 图6 8 图6 9 图6 1 0 图6 1 l 图6 1 2 图6 1 3 图 图 图 图 子树位图表示法6 5 4 级f s n 结点流水转发结构6 6 c a m 块数据结构6 7 f i s 硬件平台结构7 1 i p 查找结构7 2 子树的表示7 2 线性查找7 3 i p v 6 转发表的分解7 3 h a s h 表的二分查找过程7 4 标准二分查找结构。7 5 带回溯的二分查找算法。7 6 二分查找算法7 6 非对称二分查找结构7 7 二次二分查找结构7 9 子树内前缀密度( 真实i p v 6 转发表) 8 0 子树内前缀密度( 随机i p v 6 转发表) 8 1 f i s 中每一级f s n 结点的存储开销8 1 p s b b s 算法与树位图算法的存储开销8 2 f i s 中每一级f s n 结点的平均查找次数8 2 f s n 转发引擎逻辑结构8 6 第v i 页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它 教育机构的学位或证书而使用过的材料与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示谢意。 学位论文题目：差盈整由墨垡筮鳖整丞墓差缝垫盔盈究 学位论文作者签名：7 氢垄 日期：力曙年乡月勿日 学位论文作者签名：戡型 日期：力蟛年乡月勿日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定。本人授权 国防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子 文档，允许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印j 缩印或扫描等复制手段保存、汇编学位论文。 ( 保密学位论文在解密后适用本授权书。) 学位论文题目：差盈整由墨堡丕丝抱丞甚羞缝拉盔珏究 学位论文作者签名：亟垄 作者指导教师签名：二耋耻： 日期：力略年乡肠日 日期：年 月 日 国防科学技术大学研究生院博士学位论文 第一章绪论 路由器作为网络间相互连接的枢纽，构成了基于t c p i p 的国际互连网络的主 体脉络，是i n t e m e t 的骨架。随着i n t e m e t 网络流量、网络规模和上层应用的快速 发展，路由器技术也面i 临着新的变革。将并行处理技术引入路由器是提高路由器 性能的主要途径，并行路由器体系结构及其相关技术成为网络领域的一大研究热 点。然而，这些并行路由器体系结构并没有完全解决集中式路由器所面临的问题， 它们中的大多数要么需要复杂的通信或集中式的调度，要么依赖简单的分布式调 度算法而缺乏吞吐率保证。本文针对目前并行路由器设计所面临的负载均衡、报 文乱序、延迟和吞吐率保证、通信复杂性及f i b ( f o r w a r d i n gi n f o r m a t i o nb a s e ) 困 境等问题进行了深入研究，给出了相应的解决方案，并原创性的提出了同时开发 转发与交换平行度的新型报文处理机制，为研制低成本的，具有线速转发和大容 量交换能力的下一代高性能核心路由器做出贡献。 1 1 课题研究背景 1 1 1 下一代互联网的发展需求 高性能路由器作为构建互联网的核心设备，主要部署在p o p ( p o i n t o f - p r e s e n c e ) 网络中。每个互联网运营商网络一般包括数百甚至上千个 p o p ，它们之间以数以千计的链路进行互连，共同构成互联网的核心网络基础设施。 近年来，随着i n t e m e t 网络流量和规模的持续增长，各种新型服务和协议不断涌现 出来。当p o p 网络的规模和性能难以满足要求，或者需要支持新的网络服务和协 议时，需要增加新的路由器以及互连链路来进行扩展，这使得运营商p o p 接入点 网络中的设备数量不断增长，网络规模逐渐膨胀，网络拓扑变得更加密集，结构 日趋复杂，存在可靠性、可扩展性及可管理性等多方面的问题，无法满足未来新 一代互联网的发展需求。因此必须使用新一代高性能路由器对现有的p o p 结构进 行简化，通过简化p o p 网络结构，建立可扩展性更强、可靠性更高、可管理性更 好的p o p 网络。路由器中大约有5 0 一6 0 的端口用于路由器之间的互连，采用更 少、性能更高的路由器部署p o p 网络将减少用于路由器互连的端口数目，简化p o p 拓扑结构，从而降低管理维护费用，避免路由协议恶化i j j 。p o p 作为构建互联网基 础设施的基本单位，它的简化可以建立起更加灵活的、可用的、可扩展的新一代 互联网基础设施。这些高可扩展、高可靠性、高灵活性的p o p 甚至允许多个地理 上分离的p o p 进一步聚合成更少的、大规模p o p ，从而简化整个网络的复杂性1 2 j 。 第1 页 国防科学技术大学研究生院博士学位论文 1 1 2 高性能路由器设计面临的挑战 文献 3 】统计了过去十年各厂商推出的路由器产品的容量，将不同型号路由器 每个机柜的容量表示为如图1 1 所示的散点。这些散点的分布趋势表明，路由器每 个机柜的容量大约每1 8 个月增长2 2 倍，略高于摩尔定律。随着入网主机数目的 爆炸性增长，使得i n t e m e t 的网络规模迅速扩张，其链路上的信息流量也呈快速增 长趋势。有统计表明，在过去几年里：i n t e m e t 流量每年提高1 倍【4 ，5 1 ，主机数目 每两年增至3 倍l 引。在传输领域，自1 9 9 5 年d w d m 技术逐步进入商用化阶段以 来，光纤传输带宽沿着每7 个月提高1 倍的速度增长【3 j ；到2 0 0 1 年国际光纤通信 学术会议o f c 报道的光纤传输系统容量已达到3 t b s ；2 0 0 1 年以后，光纤容量的 增长又回复到摩尔定律的发展水平【6 】。2 0 0 7 年1 0 月，阿尔卡特朗讯在欧洲光通信 会议( e c o c ) 上宣布创造新的光纤传输纪录，通过单根光纤，以1 2 8 t b i t s ( 1 6 0 木8 0 g b i t s ) 的传输速率，创纪录地实现了2 , 5 5 0 公里的长途信息传输，将过 去所能达到的高速光纤长途传输距离提高了7 倍以上。这一研究成果为将来部署 1 0 0 g 的以太网服务奠定了基础。网络发展的瓶颈逐渐集中到路由器节点上，路由 器性能直接影响网络性能，是网络通信最主要的瓶颈之一。 图1 1 网络流量、传输容量和路由器性能的发