（通信与信息系统专业论文）高性能路由器的交换技术研究.pdf

北京邮电大学博十学位论文中文并羹 中文摘要 近几年来，由于光通信技术的快速进步，网络带宽的增长极为迅速。目前基 于d w d m 技术的光传输系统带宽己达到1 6 t b i “s ，预计3 5 年内能够达到 1 0 t b i f f s 数量级。带宽的迅速增长将对网络的体系结构、核心路由器、服务质量 保证机制和网络应用的发展产生深远影响。一方面，核心路由器的接口速率越来 越快，目前已经达到了1 0 g b i d s ，4 0 g b i “s 的接口也即将面试。而另一方面，随 肴接口速率的提高，传统的路由器已经快贾达到性能的极限，已经远不能适应太 比特的交换，因此水论文书要研究高性能路由器，并且受到教育部博士学科点专 项科研基金( 2 0 0 2 2 0 0 1 3 0 1 1 ) 和华为科技基金项目“t 比特路由器交换结构及调 度算法的研究”的支持。论文的主要工作和研究内容简介如下： 首先回顾了当前交换结构和调度算法的研究状况，对它们进行了较为详细的 分类、比较和分析，指出了它们的优缺点， 在输出队列交换机方面，我提出了两类基于多信道的公平调度算法，分别从 理论和仿真试验两方面埘算法的性能进行了详细评价，为充分利用光纤这种多信 道的系统带宽，打卜j r 一个良好的基础。 在输入队列交换机方而，我重点关注具有快速交换能力的两阶段交换机，共 提出了两类调度算法。一类是公平调度算法在两阶段交换机中的运用，另一类算 法是基0 二流指数调度算法。理论和仿真分析均表明它们都有良好的性能。 在p p s 交换机方面，共提出了3 种结构：第一种是中间单元采用输入队列 交换机，调度算法是基于消息队列的层次化公平队列调度算法，理论分析证明了 该结构的p p s 能够保持包序和提供q o s 保证；第二种是中间单元采用c i c q 交 换机。该结构的解复用器、复用器和中间交换单元部工作在独立的状态，不需要 瓦相通告状态信息，能够降低系统实现的额外通信开销，调度算法复杂度低，利 1 二硬件实现。理沦分析也表明该结构不仪能够保证信元的最大时延上界，还能避 免信元重排序：第三种是中间单元采片j 两阶段交换机，算法采肆j 复杂度极低的 p p sr r 算浊，它的最大特点是：算法复杂度低，对数据流没有苛刻的要求。仿 真分析表明，此结构的p p s 对u b p 和u i b p 数据流有良好的适应能力。 在c i c q 交换机方面，酶先提出_ r 一种基于重端口的c i c q 交换机。理论分 析表明它能侄无需内部加速的情况下，精确地模仿o q 交换机的行为，从而实 蚬o o s 保证。随后，我又提mr 一种基 。交叉一l 缓存状态的调度算法，仿真分 析说明，在突发性很强的数据流输入下，这种结构的c t c q 交换机宵很好的表现。 关键词 缓存c r o s s b a r 交换结构( c l c o )并行分组交换结构( p p s )两阶段交换结构 公平调度算法服务质最( q o s ) 第1 虫 北京邮电大学博士学位论文 a b s l r a c t a b s t r a c t g r o w t hi nc o m m u n i c a t i o nn e t w o r kc a p a c i t yh a sb e e nf u e l e dr a p i da d v a n c e si n f i b e r - o p t i ct r a n s m i s s i o nt e c h n o l o g i e s b a s e do nd w d mt e c h n o l o g y , i t st r a n s m i s s i o n r a t ec a na c h i e v e1 6 t b i t s ，a n dw i l lb e1 0 t b i t s i nf u t u r e3 - 5y e a r s i nc o n t r a s t ， g r o w t hi nt h ec a p a c i t yo fs w i t c h i n ga n dr o u t i n gn o d e sh a sg r o w na tam u c hs l o w e r p a c e ，t ot h ep o i n t w h e r e t h e ya r ec u r r e n t l yt h eb o t t l e n e c k st h a tl i m i tn e t w o r kc a p a c i t y t h em a x i m u m c a p a c i t y ( t h r o u g h p u t ) a n dq o s ap a c k e ts w i t c hc a na c q u i r ea r e l a r g e l y d e t e r m i n e d b y i t s a r c h i t e c t u r ea n d s c h e d u l i n ga l g o r i t h m i t i s w i d e l y r e c o g n i z e d t h a tc o n v e n t i o n a la r c h i t e c t u r e sc a n n o tb es c a l e dt o i m p l e m e n t t h e m u l t i t e r a b i v sf a b r i c st h a tw i l ls o o nb er e q u i r e d t h e r e f o r e ，t h et w op r o b l e m st h i s d i s s e r t a t i o na d d r e s s e sw i l lb ef o c u so n f i r s t l y ，t h ep r e s e n t a t i o na n da n a l y s i so ft h er e s e a r c hb a c k g r o u n dt b rt h ep a p e r w a sd o n e w e g a v et h er e l a t e dr e s e a r c hb a c k g r o u n da n d t h eu p t i m er e s e a r c hs i t u a t i o n o ft h es w i t c hf a b r i cd i dad e t a i l e d c l a s s i f i c a t i o n ，c o m p a r i s o n a n da n a l y s i s ，t h e n ， p o i n t e d o u tt h ee x i s t i n gp r o b l e m st ob er e s o l v e d o nt h es c h e d u l i n go fi qs w i t c h ，w ea r ef o c u so nt w o s t a g ef a b r i ca n dg i v et w o s c h e d u l i n ga l g o r i t h m o n ei s t oa p p l yf a i r l y s c h e d u l i n gi nt w o - s t a g ef a b r i c i nt h i s a l g o r i t h m ，w ep r o o ft h a tt h ea l g o r i t h mc a ng u a r a n t e eq o s f o re v e r yd a t af l o w t h e o t h e ro n ei st h es c h e d u l i n ga l g o r i t h mb a s e do nt h ec o n c e p to ff l o w i n d e x s i m u l a t i o n s h o w st h a tt h et y p eo fs w i t c hc a l lh a v eg o o dp e r f o r m a n c eu n d e ru b pf l o wo ru i b p f l o w o nt h ep p s ，t h r e en e wk i n d so f p p sa n dt h e i rs c h e d u l i n g a l g o r i t h m a r ep r e s e n t e d i nt h ef i r s tf a b r i c i qi su s e d 船m i d d l es w i t c hf a b r i ca n dh i e r a r c h i c a ip a c k e tf a i r q u e u e i n ga l g o r i t h m si ss u g g e s t e d w i t ht h e o r ya n a l y s i s ，w ep r o o fi t c a ng u a r a n t e e q o s f o re v e r yd a t af l o ww i t h o u tc e l lr e o r d e r i nt h es e c o n df a b r i c ，af l a m eb a s e dp p s w a s p r e s e n t e d ，i n w h i c h c i c q sw a s u s e da st h em i d d l es w i t c hf a b r i c si t s d e m u l t i p l e x e r s ，m u l t i p l e x e r s ，m i d d l es w i t c h e sa l lw o r k e dd e p e n d e n t l y t h e yn e e d e d n o tc o m m u n i c a t i o nt h es t a t e i n f o r m a t i o nw i t he a c ho t h e r s o ，t h ea d d i t i o n a l c o m m u n i c a t i o nc o s to ft h e s y s t e mw a sr e d u c e d al o t t h et r a f f i ca l s oc o u l db c g u a r a n t e e dt ob ed i s t r i b u t e dt oa l lc 1 c q se v e n l yb yi t ss c h e d u l i n ga l g o r i t h m st om a k e e f f i c i e n tu s eo ft h ec r o s s p o i n tb u f f e r a n dt h ec o m p l e x i t yo ft h ea l g o r i t h m sw a ss o l o wt ob er e a l i z e d e a s i l y t h et h e o r e t i c a la n a l y s i sa l s os h o w e dt h a tt h i sk i n do fs w i t c h 第【t 1 贞 北京邮电大学博士学位论文a b s t t a c t f a b r i cn o to n l yc o u l dg u a r a n t e et h em a x i m u m d e l a yo f t h ec e l l ，b u ta l s oc o u l da v o i d t h er e s e q u e n c i n go ft h ec e i l s i nt h el a s tk i n do fp p s ，t w o - s t a g es w i t c hi su s e da s m i d d l es w i t c hf a b r i ca n dt h ep p s r ra l g o r i t h mi ss u g g e s t e d ，w i t hs i m u l a t i o n ，t h e r e s u l t ss h o wt h a ti tc a l lh a v eg o o dp e r f o r m a n c eo n a v e r a g ed e l a ya n ds t a b l e a l s oo nt h e c i c qs w i t c hf a b r i c ，t w o k i n d so fc i c qa n dt h e i r s c h e d u l i n g a l g o r i t h ma r ep r e s e n t e d i nt h ef l r s tf a b r i c 。an e wa r c h i t e c t u r ei sg i v e n ，w h i c hc a n m i m i co qs w i t c hw i t h o u ts p e e d u p w i t ht h e o r e t i c a lp r o o f , w es h o wt h a te a c hp o r t w i t had u p l i c a t e dn u m b e ro ft w oi ss u f f i c i e n tt om i m i co qs w i t c h i nt h es e c o n d f a b r i c ，a na l g o r i t h mb a s e do nt h es t a t eo fc r o s s p o i u tb u f f e ri ss u g g e s t e d b yc o m p u t e r s i m u l a t i o n ，w ea n a l y z ei t sa v e r a g ed e l a ya n ds t a b i l i t y t h er e s u l t ss h o wi tc a nh a v e g o o dp e r f o f i n a n c eu n d e ru b p a n du 1 b pf l o w 第1 v 页 北京邮电大学博士学位论文缩略语说明 英文缩写 a t m c 1 0 q c i c q d i f f s e l w d r r m d r r d p f q e d f f i f 0 f e f f f g p s h o l i q i n t s e r v i s l l p i d r r l p f l q f l p f l o o f a m p l s m o q m s m m w m m c m o q o c f p i m 缩略语说明 英文全拼中文 a s y n c h r o n o u s t r a n s f e rm o d e异步转移模式 c o m b i n e d i n p u ta n do u t p u tq u e u e d 输入输出混台排队 c o m b i n e d i n p u ta n dc r o s s p o i n tq u e u e d输入和交叉点缓存排队 d i f f e r e n f i a t e ds e r v i c e s区分业务 d u a lr o u n dr o b i n m a t c h i n g 双轮循匹配 d e f t e rr o u n dr o b i n差额轮询 d i s t r i b u t e dp a c k e tf a i rq u e u e d分布式的公平排队调度算法 e a r l i e s td e a d l i n ef i r s t 最甲底线优先 f i r s t - i nf i r s t o u t先入先出 f o r w a r d i n ge n g i n e 转发引擎 f u l lf r a m ef i r s t全帧优先 g e n e r a l i z e dp r o c e s s o rs h a r i n g通用处理机共享 h e a do f l i n e队首 i n p u tq u e u e d 输入排队 i n t e g r a t e ds e r v i c e s 综合服务 i t e r a t i v es l i p滑动匹配 i t e r a t i v ed e f i c i tr o u n dr o b i n迭代式差分轮循 l o n g e s t p o r tf i r s t最长端口优先 l o n g e s tq u e u e f i r s t最长队列优先 l o n g e s t p o r tf i r s t最长端口优先 l o w e s t o u t p u to c c u p a n c y f i r s ta l g o r i t h m 最低输出占用优先算法 m u l t i p r o t o c o ll a b t es w i t c h 多协议标签交换 m i d d l eo u t p u tq u e u e d中间输出队列 m a x i m t u ns i z em a t c h i n g最大数目匹配 m a x i m u m w e i g h tm a t c h i n g 最大权重匹配 m a x i m u mc r e d i tm a t c h i n g最大信用量匹配 o u t p u tq u e u e d 输出排队 o l d e s tc e l lf i r s t最老信元优先 p a r a l l e li r e r a t i v em a t c h i n g并行迭代匹配 第1 2 7 页 擞塞奎堂堡主堂垒堡奎 堕堕垦塑塑 p p s q o s r r r r m s f i s s f s e f f s f f t d m t c p v o i p v c v o q v c i v p i w f i w d m w f q w r r w f q p a r a l l e lp a c k e ts w i t c h i n g q u a l i t yo f s e r v i c e r o u n dr o b i n r o u n dr o b i n m a t c h i n g s e r v i c ef a i r n e s si n d e x s m a l l e s tv i r t u a ls t a r t e d - t i m ef i r s t s m a l l e s t e l i g i b l ef i n i s h e d - t i m e f i r s t s m a l l e s tv i r t u a lf i n i s h e d - t i m ef i r s t t i m ed i v i s i o n m u l t i t i l e x i n g t r a n s m i s s i o nc o n t r o lp r o t o c o l v o i c eo v e ri p v i r t u a lc l o c k v i r t u a lo u t p u t q u e u e d v i r t u a lc h a n n e li d e n t i f i e r v i r t u a lp a t hi d e n t i f i e r w o r s t c a s ef a i r n e s si n d e x w a v e l e n g t hd i v i s i o nm u l t i p l e x i n g w e i g h t e d f a i rq u e u i n g w e i g h t e dr o u n d r o b i n w o r s t - c a s ef a i rw e i g h t e df a i rq u e u e d 第1 2 8 页 并行分组交换 服务质量 轮询 轮循匹配 服务公平指数 最小开始时间优先 最小合法虚完成时间优先 最小虚完成时间优先 时分复用 传输控制协议 l p 语音 虚时钟 虚拟输出排队 虚通路标志 虚通道标志 最坏公平指数 波分复用 简单加权公平排队 加权轮询 最坏情况公平的w f q 声明 独创性( 或创新性) 声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名： 圣塑盐 日期：塾! 生：圭墨 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即： 研究生在校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借 阅；学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它 复制手段保存、亨 编学位论文。( 保密的学位论文在解密后遵守此规定) 保密论文注释：本学位论文属于保密在年解密后适用本授权书。非保密论 文注释：本学位论文不属于保密范围，适用本授权书。 本人签名：王姓 导师签名 了虫垄 日期：皇! ：i ：苎圣 同期：丝! 星 北京邮电大学博士学位论文第1 章绍论 1 1 引言 第1 章绪论 随着信息社会的到来，以微电子和光电子为基础的计算机技术和数字通信技 术得到了飞速的发展，微电子技术沿着著名的摩尔曲线快速前进，芯片上的晶体 管每1 8 个月翻一倍，解决了信息的大容量存储和快速复杂的处理。光技术的发展 更为神速，光纤通信的传输容量每6 个月就增加一倍，通过运用密集波分复用 ( d w d m ) 和单波长传输比特数的增加，每对光纤可以传输t 比特的数据量。这 些技术极大地推动了社会的信息化。一个以i n t e m e t 为主要组成部分的信息化社 会正在迅速形成。 i n t e m e t 是一个非常庞大的分组交换网络，它由众多的网络云构成，连接这 些网络云和网络云的内部设备核心部件是路由器。路由器丰要完成路由 ( r o u t i n g ) 和转发( f o r w a r d i n g ) 两项重要任务。路由功能负责运行路由协议， 计算路由转发表，运行软件对路由器进行配置和管理，它一般由高性能的c p u 来实现。交换功能丰要完成不同端口之阊的分组交换，由交换结构及其调度算法 配合完成。这也是本文研究的主要内容。此外，因为应用领域的多样性和应用环 境的复杂性，在很多情况下，路由器还要完成一些控制和管理的功能，如：安全、 策略、计费等。不过在骨干网中系统的路由转发能力仍然是核心路由器最重要的 性能指标。 当前，i n t e m e t 是由一些数目相对较少的高速骨干网连接了很多的小网络组 成。骨二r 网的链路速率基本上是以3 0 的增长速率递增，已经从o c 4 8 ( 2 5 g b p s ) 发展到o c 一1 9 2 ( 1 0 g b p s ) 和o c 7 6 8 ( 4 0 g b p s ) 。这就意味着，传输线路已经不 是解决网络拥塞的瓶颈。因此，设计高性能的核心路由器是提高i n t e r n e t 整体性 能的关键所在u - 3 】。这也就对交换结构和调度算法的配合以及路由处理能力提出 了更高的要求。当前的交换结构和调度算法的研究主要集中在提高吞吐率，降低 时延等方而。但是，随着不同的应用的增加，将来的交换结构也必须能够考虑到 对更加丰富的q o s 保证的支持【3 1 4 1 。因此，受教育部博士学科点专项科研基金 ( 2 0 0 2 2 0 0 1 3 0 1 1 ) 和华为科技基金项目“t 比特路由器交换结构及调度算法的研 究”支持，本文将对这些问题展开研究。 1 2 本文的主要贡献 在输出排队交换结构的公平调度方面：1 ) 提出了2 种基于多信道的公 平调度算法。第一种算法是基于单服务器的调度算法，第2 种是采用并 第1 页 j e 京邮电大学博1 学位论文 第1 章绪沦 行机制的基于消息机制的多服务器调度算法。2 ) 从理论上对这两种调 度算法的性能进行了数学上分析，证明了相关的时延性能和公平性能。 3 ) 对第2 类调度算法进行了计算机仿真分析，将它的时延分布与w f 2 q 做r 全面的分析和比较，为实际中的运用提供参考依据和建议。 在输入排队交换结构的公平调度方面：1 ) 提出了3 种交换结构，一种 足基于矩阵分解的b v n 交换机。第2 种是保证q o s 的两阶段交换机， 另外一种是基于流指数概念的两阶段交换机。2 ) 从理论上证明了保证 q o s 的两阶段交换机能够在保证包序的情况下，对数据流提供最大时延 上限和最小缓存需求。3 ) 运用计算机仿真方法对基于矩阵分解的b v n 交换机的时延特性和稳定性进行分析，实验表明，在双漏桶流的输入下， 交换机有很好的时延特性和稳定性。3 ) 运用计算机仿真方法对基于流 指数概念的两阶段交换机进行分析，实验表明，在保持包序的情况下， 它对u b p 、u i b p 和n ou i b p 流具有非常好的适应能力。 在并行分组交换结构方面：1 ) 提出_ ，基于消息队列的p p s 交换结构。 该结构不仅能保证数据流的包序，丽且能对数据流提供公平的服务，为 每个数据流提供时延上限。2 ) 提出了在中间交换单元采用c i c q 结构 的基j p 帧的p p s 交换结构及其调度算法。它的三大部分都工作在独立的 状态，不需要互相通告状态信息，大火降低系统实现的额外通信开销。 其洞度算法也能保证数据流被均匀地解复用到各c i c q 中，使c i c q 的 有限缓存得到充分的利用。并且，算法复杂度较低，利于硬件实现。理 论分析也表明该结构能为信元提供最大时延上限和避免信元重排序。3 ) 最后，运用流指数概念提出了种中间交换单元采用两阶段交换机的结 构，该结构酌p p sr r 算法的复杂度极低，利于硬件实现。另外，这种 结构的p p s 交换机对数据流没有苛刻的要求，适合复杂环境下运用。 在c i c q 交换结构方面：1 ) 提出了基于重端口的c i c q 交换机，并从数 学上证明了该结构的交换机在不需要内部加速的情况下能够模仿o q 交 换机，从而能够解决q o s 问题。2 ) 为了能够进步增强c i c q 交换机 对突发流的适应能力，我提出了一种基于交叉点缓存状态的c i c q 交换 机。仿真分析表明，这种结构的交换机在u b p 和u i b p 等类型的数据流 的输入下，具有优良的表现，这些分析对实际c i c q 交换系统的设计都 有重要的参考价值和指导意义。 1 3 本文的结构和安排 第二章给出了全文的相关技术研究背景。首先，介绍了路由器的体系结构及 第2 负 北京邮电大学博士学位论文 第1 章绪论 其应具备的基本功能。然后，对目前常用的交换结构进行了分析和比较，指出了 它们的研究现状和存在的问题。 第三章主要对基于多信道的公平调度算法做了深入的研究。茸先，对公平调 度算法的研究背景做了详细的介绍，对已经取得的成果做了简要的评价和总结。 在此基础上提出了两种基于多信道的调度算法，从理论上分析了它们的性能，并 且用计算机仿真的方法对第2 类算法信元的时延分布情况做了详细的分析。 第四章集中讨论了基于确定性调度算法的交换结构，提出了3 种交换结构， 一种是基于矩阵分解的b v n 交换机。第2 种是保证q o s 的两阶段交换机，另外 一种是基于流指数概念的两阶段交换机，然后分别运用数学理论和计算机仿真两 种方法对交换机的性能进行了深入分析。 第五章主要对扩展性较好的并行分组交换结构进行了研究。首先，提出了基 于消息队列的p p s 结构及其调度算法，该结构能为数据流提供q o s 保证，理论 分析表明这神交换结构能为数据流提供最大时延上界和最小缓存需求。然后，又 提出了基于帧的p p s 交换结构及其调度算法，该结构的中间交换单元采用c i c q 交换结构，解复用器、复用器和中问交换单元都工作在独立的状态，不需要互相 交换状态信息，降低了系统实现的额外开销。并从理论上证明了该结构不仅能够 保证信元的最大时延，还能够避免信元的重排序。最后，运用流指数概念义提出 了p p sr r 调度算法，该算法具有非常低的实现复杂度，并能将数据包的乱序控 制在一定范围之内，仿真分析也表明此结构的p p s 具有非常好的性能。 第六章集中讨论了c i c q 的调度问题。首先，提出了具有重端口的c i c q 交 换结构，并从理论上证明了它在不需要内部加速的情况下，就能够模仿理想的输 出队列交换机。然后，又提出了一种基于交叉点缓存状态的c i c q 交换机，计算 机仿真也表明这种c i c q 交换机对突发性数据流有很强的适应能力。 最后一章为“结束语”。对本论文所做的研究工作进行全面的总结，并对未来 的研究工作进行了展望，并且提出了几个还有待予解决的问题。 1 4 。本章摘要 1 h j o n a t h a nc h a o n e x tg e n e r a t i o nr o u t e r s p r o c e e d i n go f t h ei e e e ，v 0 1 9 0 ，n o 9 ，s e p2 0 0 2 ， p p ：i5 1 8 - 1 5 5 8 2 】s k e s h a v , r o s e ns h a r m mc o m e l l ，“i s s u e a n dt r e n d si nr o u t e r d e s i g n ”，i e e e c o m m u n i c a t i o n m a g a z i n e ，m a y2 0 0 i ，p p 1 4 4 - 1 5 l 3 w ，d e n z e lw e ，e n g b e b o nt ，h e r k e r s d o r f a ，l u i j t e nr e “t e c h n o l o g i e sa n db u i l d i n gb l o c k s f o rf a s tp a c k e tf o r w a r d i n g ”i e e ec o m m u n i c a t i o n m a g a z i n e ，v 0 1 3 9 ，2 0 0 1 ，p p 7 0 7 7 第3 贞 北京邮电大学博士学位论文第2 章研究背景 第2 章研究背景 2 1 路由器体系结构的发展 随着需求的增长，路由器的性能在不断得到升级和提高，到今天为止，路由 器的体系经历了几次大的变化。变迁的主线1 1 - 2 1 是这样的：由使用通用功能器件 过渡到使用专用器件；由系统的串行操作过渡到并行操作。器件的专用化程度越 高，意味着系统的一些关键运算可以采用独立的物理器件来完成，提高系统性能。 另一方面，进行并行化处理。提高系统的并行化度，在提高系统性能方面一直都 有广泛的应用，在路由器领域的应用当然也是自然的。 我们认为路由器体系结构主要经历了4 次大的变迁： 1 ) 单机集中式总线结构。 2 ) 单机分布式共享总线结构。 3 ) 单机分布式c r o s s b a r 结构。 4 ) 多机互连的集群结构 2 1 1 单机分布式总线结构 在这种结构中，系统包含一个中央处理器( c p u ) 和集中式内存。所有通信 线卡( 或称网卡n i c ) 都通过一条共享的总线和c p u 以及集中式内存相连。 通信线卡完成数据的物理层以及数据 链路层的收发操作，得到的分组通过总线送 交到集中式内存进行存储，同时分组的头部 送到c p u ，进行路由操作，选路成功后，分 组再通过总线送到目的线卡，发送出去。 从分组的收发流程来看，数据流要几次 通过总线，总线在这个系统中是被所有线卡 和中央处理器以及内存所共享。所以，当线 图2 1 单机集中式总线结构 卡数目增多和数据流量很大时，各个设备对总线的争用会导致严重的访问冲突。 另外，中央处理器需要处理来自所有线卡的数据转发操作，因此，当线卡数 目增加时，单一的中央处理器无法完成更高的转发速率要求。同时，c p u 还要 还要完成路由信息交互和路由计算。因此，在这种结构中，c p u 会成为系统域 根本的性能瓶颈。这种结构的交换容量通常小于o 5 g b i t s 。 第5 页 北京邮电大学博士学位论文第2 章研究背景 2 1 2 单机分布式总线结构 单机分布式总线结构的主要目的是提高线卡的处理能力，同时，将用于路由 计算的处理器从路由转发中解放出来，如图2 2 所示。 单机分布式总线结构的“分布式”特性，体现为多个相对独立的线卡可以并 行完成各自的操作。每一线 卡拥有自己的c p u 、内存和 若干网 的独立子系统。到 达块线卡的数据报文，在 本地线卡进行存储和转发判 决，输出端口在本线卡内部 的数据直接由线卡送到目的 端口，只有路由之后的目的 端u 在其它线卡的数据需要 图2 2 单机分布式总线结构 通过总线送到其它线卡上去。这样做有两方面的好处，一是提高了线卡上的数据 处理能力，二是降低了总线的竞争程度。 在这种系统中，通常有一块“主板”，它不参与路由转发操作，而主要负责 整个系统的管理操作和路由计算等任务。它负责运行路由协议和邻居节点进行路 由交换，生成路由袭，并将用于转发判决的转发表发布到各个线卡上去。 单机分布式总线结构将转发功能和路由计算功能分布在不同的处理板上来 完成，大大提高了系统的整体性能。但是这种共享总线的方式仍然会因为线卡对 总线的竞争而产生系统效率下降，这种结构的交换容量一般小于5 g b i t s 。 2 。1 3 单机分布式c r o s s b a r 结构 如图2 3 所示，在单机分布式总线结构中，使用交叉开关来代替共享总线， 就形成了单机分布式c r o s s b a r 结构。c r o s s b a r 结构可以看作是一个交换开关的集 合，每对输入和输出端口之间都有一个交换开关，交换开关的控制是彼此独立的， 这样，只要数据流彼此不相关( 没有公共的输入端口和输出端口) ，就可以通过 交换开关控制，构成并发的数据通路。通过c r o s s b a r 连接，路由器分布式结构的 并发性得到了进一步提高，整体的交换容量得到了大幅度提升。对于这种结构的 路由器，交换网络的拓扑结构，冲突的仲裁机制以及调度算法都是我的论文丰要 研究的内容，基本目标是构造一个“无阻塞”的交换网络。 第6 页 北京邮电大学博七学位论文第2 章研究背景 在这种结构的路由器中，通常应用了可以基于内容进行查找的路由表查询器 件( t c a m ) ，大大加快了查表速度，突破了查表与线速之间的速度匹配障碍， 这种结构的舆型容量是几十 到几百g b i t s 。现在骨干网络 中的核心路由器通常采用这 种结构。 从前面3 代路由器的结 构变迁来看，系统的并行化 是路由器发展的重要方向。 基于c r o s s b a r 的第3 代路由 器的并行处理能力在单机操 作的情况下己经实现得非常 图2 - 3 单机分布式总线结构 彻底了，要想进一步提高系统的交换容量，需要更高层次的体系结构更新。 2 1 4 多机互连的机群结构 新一代核心路由器的体系结构通常都是基于集群设计的，在集群结构中多 个机柜可以通过内部的连接整合成一个新的大型路由器。互联后的集群在管理操 作和实际运行的路由协议实例方面，都是单一映像的方式，也就是说，整个路由 器集群从外界来看如同一台路由器一样工作。在理论上，这种结构可以无限扩展， 支持不断增加的网络流量需求。 在集群结构中，多个机柜通过内联网络连接在一起，内联网络的性能直接影 响路由器集群的整体交换性能。多级互联的的网络拓扑有多种，如c l o s ，b e n e s 和k n o c k o u t 等，但目前研究比较多的是三级c l o s 结构。 在多级交换网中考虑多维结构。当业务通过一个多维结构的交换网络时，每 一跳可选择的路由数目将增加，使系统中任意两个分散节点只需较少的跳数即可 到达。由于跳数诫少，多维多级交换结构可显著降低业务通过交换网络的时延和 抖动。埘于这种结构，目前研究得比较多的有疗维m e s h ，3 - d t o m s ( k a r yn c u b e l ， 超立方体( h y p e r c u b e ) 等，它们能够提供高的交换性能，具有良好的扩展性。 2 2 ，高性能路由器的交换结构( c r o s s b a r ) 分析 由于技术和物理j 二的原因，基于c r o s s b a r 的结构是实现g 比特以至t 比特 级交换容量的理想交换结构。因此，以c r o s s b a r 技术为代表的空分型交换结构成 为目前宽带交换领域的研究热点。 第7 页 北京邮电大学博士学位论文第2 章研究背景 c r o s s b a r 型交换内核的体系结构 实质上分为两个主要部分：“数据通道” 和“调度器”。数据通道由输入端口， 输出端口和高速交叉开关电路构成，每 个交叉开关控制一个输入端口到一个 输出端口的数据通道。输入输出端口与 c r o s s b a r 之间通过高速串行差分信号 线进行连接，这在很大程度上降低了数 据通道的设计复杂度。因此，只要提高 串行链路的速率和端口的值，就可 输入端口 c r o s s b a r 输出端i a x 瓣匿 图2 4 基于c r o s s b a r 的交换结构 以很容易地扩展到高达t 比特级的交换容量。 调度器是保证c r o s s b a r 型交换内核无阻塞的重要构件，主要功能是使用特定 的调度算法来合理的配置每个输入端口对c r o s s b a r 的访问，并提高其利用率。在 实际当中，设计一个高带宽的数据通道是比较容易，而如何为调度器设计一个好 的调度算法是非常困难的。因此，调度算法的效率是制约c r o s s b a r 交换容量的重 要因素。 我们知道，在分组交换网络的交换设备都需要缓存队列暂时保存到达的分 组。因此，根据分组在缓存中的排队策略不同，c r o s s b a r 型交换结构可以分为输 出排队( o u t p u tq u e u e d ，o q ) 、输入排队( i n p u tq u e u e d ，i q ) 和组合输入输出 排队( c o m b i n e d i n p u ta n do u t p u tq u e u e d ，c i o q ) 三种pj 。下面就按这种分类进 一步介绍现在比较流行的基于c r o s s b a r 的体系结构。 2 2 。1 输出排队 在很长一段时间里，由于i q 型交换结构存在队头阻塞问题( h e a do f l i n e ) ( 若队头信元被阻塞，同队列的其它信元就不能被转发) 1 q 交换机的性能很差， 当端口数较多，且在所有输出端口均匀分布的b e r n o u l l i 业务到达条件下，1 0 的 吞吐率只有5 8 6 。因此，在相当长一段时间里， 研究人员关注的是o q 交换 机。 o q 型交换结构的含义是：到达交换机的信元可以立即被传送到其目的输出 端口，在输出端口进行缓存排队，换旬话说，交换机的“存储功能”是存“路 由功能”之后执行的。 o q 交换机的主要优点是在任何流量模式f 吞吐率都是1 0 0 ，也就是说任 何输出排队调度算法都不用考虑吞吐率的问题。此外，对于定长分组( h 口信元) 通过交换网络的时延是固定的，这给在输出端口采用不同的队列调度算法来提供 第8 页 北京邮电大学博士学位论文 第2 章研究背景 q o s 特性带来了方便。在o q 方面，具有速率和公平性保证的调度算法已经取得 了很多有意义的结果，如基于轮循的调度算法、基于优先级的调度、基于通用处 理机共享( g p s ) 的算法【4 】、基于时延的调度算法、基于服务曲线【5 i ( s e r v i c e c u r v e ) 的算法等。 但是对于一个n x n 的o q 交换结构而言，在一个时隙内最多可能有个信 元去往同一个输出端1 3 ，因而，输出端口的缓存则需要 ，+ 1 倍线速( 倍写和1 倍读) 。显然，这增加了硬件的成本和复杂性，其可扩展性极差。因此，当路由 器有很多端口，而且端口的速率达到g b i t s 时，现有的工艺水平实现n 加速比 是非常困难的。 2 2 2 输入排队 l q 交换结构的含义是：到达的信元首先被保存在输入端口缓冲区中，然后 由调度算法决定信元何时通过交换结构传送到输出端口，换句话说，“缓存功能” 是在“路由功能”之前。 i q 交换机可能会遇到3 种阻塞。 第种是队头阻塞。如果每个输入端口只有单个f i f o 队列的情况下，就会 出现队头阻塞问题【6 1 ，举个例子说，如果队列头部的分组要去的端口正忙，那么 此分组只能在队列中等待，这时即使它后面的分组要去的端口是空闲的也没有 机会发送。这种阻塞会极大地降低交换机