（通信与信息系统专业论文）基于benes的超大容量交换结构仿真研究.pdf

摘要 摘要 近年来，随着i n t e r n e t 业务的持续高速增长，电信级路由交换系统成为业界研 发的重点之一。为了满足电信级路由交换设备大容量、易扩张、高度可靠的性能 要求，希望对其核心关键技术超大容量交换结构研究有所突破。如何优化设 计交换网络内部流量控制机制及队列组织调度方法，攻克其中的关键技术，是产 业界研制相关产品所面临的核心问题。基于b e n e s 拓扑的多平面多路径( 多级) 超大容量交换结构在c i s c o 公司最新推出的c r s 一1 ( c a r r i e rr o u t i n gs y s t e m ) 系统 中得到运用，最高可支持9 2 t b p s 交换容量。本文主要针对基于b e n e s 超大容量交 换结构的扩展性、q o s 性能、容错性、多播性能、分组重排序方法等关键问题展 开仿真研究。 本文对c i s c oc r s 一1 系统交换平面内部所采用的b e n e s 结构和交换系统从 1 2 t b p s 到9 2 t b p s 的升级过程进行理论分析；对b e n e s 拓扑路径特性和路由选择 算法进行理论研究。 本文提出一种适用于基于完全可重排无阻塞b e n e s 拓扑构建的多平面多路径 ( 多级) 超大容量交换结构的两级负载均衡策略，通过在输入流量管理器和b e n e s 交换平面内部实施合理而高效的队列组织调度方法，有效实现了基于不同目的地 址的i p 流量在两个层次上的负载均衡，较好弥补了c i s c oc r s 1 系统在平面选择 和中间级选择时所采用的简单随机或轮循方案的不足。 本文提出了几种仿真实验方案，并详细描述了在o p n e t 平台上所搭建的仿真 模型；同时，对b e n e s 平面内部缓存、交换时延和重排序规模等进行了仿真结果 分析，详细比较了不同均衡策略在系统性能方面的差异。该仿真平台的完整建立， 对于今后继续深入研究基于b e n e s 的超大容量交换结构中的关键技术，具有积极 的推动作用。 在多种业务源模型环境下的计算机仿真实验表明，通过应用本文提出的两级 负载均衡策略，随着网络负载、交换规模( 端口数量) 和业务流个数的增加，与 传统的随机策略和轮循策略相比，不仅可以较大幅度降低b e n e s 交换平面内部的 缓存消耗，使其随网络负载增大而增长的速度得到了明显控制，而且极大减小了 重排序规模( 体现在重排序队列长度) ，为经济地实现重排序提供了可能，同时， 该策略降低了交换时延，提供了必要的服务质量保证( q u a l i t yo f s e r v i c e ，q o s ) 。 摘要 该两级负载均衡装置及方法简单、高效、硬件易实现，适用于构建支持数十t b i t 甚至更高的电信级路由交换设备。 本文提出的一些新的基于b e n e s 超大容量交换结构的优化实现方案，相对现 有方案在扩展性、o o s 性能、分组重排序等方面具有综合优势，可以支持1 t b i t 扩 展到1 0 0 t b i t 甚至更高，为产业界开发相关产品提供理论支持和关键技术解决方案。 关键词：超大容量，可扩展性，交换结构，多平面多级，负载均衡，仿真模型 i l a b s t r a ( 了 a b s t r a c t r e c e n t l y ，t ok e e pp a c ew i t hc o n t i n u o u s l yr a p i dd e v e l o p m e n to fi n t e r n e tt r a f f i c g r o w t h ，t h et e c h n o l o g yo ft e r a b i to re v e np e t a b i tt e l e c o m m u n i c a t i o nr o u t e rh a sb e c o m e t h eh i g h l i g h to fr e s e a r c h e r so fi n d u s t r i e sa n da c a d e m i c s r e s e a r c h e r sh a v eb e e n c o n t i n u a l l ye x p l o r i n gn e ws w i t c ha r c h i t e c t u r e s a sac o r et e c h n o l o g yo ft e r a b i ta n d p e t a b i tr o u t e r ，u l t r a - s c a l a b l es w i t c ha r c h i t e c t u r e sa r en e e d e dt om e e tt h er e q u i r e m e n to f c a p a c i t y ，s c a l a b i l i t ya n dr e l i a b i l i t y h o wt oi n t e l l i g e n t l yi m p l e m e n t e da f l o wc o n t r o l m e c h a n i s mw h i l em a x i m i z i n gt h em e m o r yu t i l i z a t i o na n ds y s t e mp e r f o r m a n c e ，h o wt o m i n i m i z el i n kc o n g e s t i o na n dp r e v e n tb u f f e ro v e r f l o wa n dh o wt om a i n t a i np a c k e t s o r d e r si ft h e ya r ed e l i v e r e do v e rm u l t i p l ep a t h sa r et h ec h a l l e n g i n gd e s i g ni s s u e sr e l a t e d t od e s i g n i n gt h eu l t r a s c a l a b l es w i t c ha r c h i t e c t u r e s o n em e t h o dt os c a l et h es w i t c hi st o u s et h em u l t i p l a n e m u l t i s t a g e b u f f e r e da r c h i t e c t u r e f o ri n s t a n c e ，c i s c o sc r s 一1 s y s t e mb a s e do nb e n e sn e t w o r kc a ns c a l eu pt o9 2t b p s t h i sd i s s e r t a t i o nf o c u s e so n t h es t u d yo f s c a l a b i l i t y ，q u a l i t y o f s e r v i c e ，f a u l tt o l e r a n c e ，m u l t i c a s tc a p a b i l i t y ， r e s e q u e n c i n g ，a n dp r o v i d e ss e v e r a ls o l u t i o n sf o re a c hi s s u e t h i sd i s s e r t a t i o nh a ss h o w n b ys i m u l a t i o nt h a tt h eu l t r a - s c a l a b l em u l t i p l a n em u l t i - s t a g es w i t c ha r c h i t e c t u r ei sa b l e t op e r f o r mn e a r l ya sw e l la st h eo u t p u tb u f f e r e ds w i t c hu n d e rm o s ti n t e r e s t e dt r a f f i c d i s t r i b u t i o n s t h i sd i s s e r t a t i o n a n a l y z e s c i s c o sc r s - 1s y s t e m ，d e s c r i b e sa n ds t u d i e st h e p r o p e r t i e so ft h ep a t hi nb e n e sn e t w o r ka n dt h en o n - b l o c k i n gc o n d i t i o n sf o rb e n e s n e t w o r k a c c o r d i n gt ot h e s en o n b l o c k i n gc o n d i t i o n s ，s o m ea l g o r i t h m sf o rc o m p o s i n g r o u t i n gl a b e l sa r ed i s c u s s e d f i n d i n gaf e a s i b l ea n de f f i c i e n tl o a db a l a n c e ds t r a t e g yf o rt h eu l t r a s c a l a b l e m u l t i p l a n em u l t i - s t a g es w i t c ha r c h i t e c t u r e i sa t o po fn o w a d a y sr e s e a r c h t h e d i s s e r t a t i o n p r o p o s e s a t w o - s t a g e l o a db a l a n c e ds c h e m ef o r t h eu l t r a s c a l a b l e m u l t i p l a n em u l t i - s t a g es w i t c h a r c h i t e c t u r eb a s e d s e l f - r o u t i n g a n d n o n b l o c k i n g p e r m u t a t i o nb e n e sn e t w o r k t h ea p p r o a c hu s e s r e a s o n a b l ea n de f f i c i e n t l o g i c a l q u e u e i n gs t r a t e g ya n ds c h e d u l es c h e m ei ni n g r e s st r a f f i cm a n a g e r sa n ds w i t c hp l a n e st o r e a l i z et h et w o s t a g el o a db a l a n c i n go fi pt r a f f i cw h i c hf o rd i f f e r e n td e s t i n a t i o n a d d r e s s e s 1 l i a b s l r a c t s e v e r a ls c h e m e so ft h es i m u l a t i o ne x p e r i m e n ta r ep r e s e n t e di nt h i sd i s s e r t a t i o n ， a n dt h eo p n e t b a s e ds i m u l a t i o nm o d e li sd e s c r i b e d m e a n w h i l e ，i ta n a l y z e sa n d c o m p a r e st h et h r e el o a db a l a n c e ds c h e m e sb yc o m p u t e rs i m u l a t i o n s t h ee s t a b l i s h m e n t o fo p n e t b a s e ds i m u l a t i o nm o d e li sac o n t r i b u t i o nf o rt h ef a r t h e rs t u d yo ft h e u l t r a s c a l a b l e m u l t i - p l a n em u l t i s t a g e s w i t c ha r c h i t e c t u r eb a s e ds e l f - r o u t i n ga n d n o n b l o c k i n gp e r m u t a t i o nb e n e sn e t w o r k i nf u t u r e t h ep e r f o r m a n c eo fc o n s i d e r e da p p r o a c h e si sd e r i v e db yt h e o r e t i c a la n a l y s i sa n d c o m p u t e rs i m u l a t i o n s t h ed e s i g na c h i e v e sw e l ln e t w o r kp e r f o r m a n c e s t h ed i s s e r t a t i o n p r o p o s e s s e v e r a ln e wa p p r o a c h e sf o r h i g h s p e e d s w i t c h a r c h i t e c t u r eb a s e d b e n e sn e t w o r k i te n h a n c e st h ep e r f o r m a n c eo fs c a l a b i l i t y ，q u a l i t yo f s e r v i c e ，f a u l tt o r r a n c e ，m u l t i c a s tc a p a b i l i t y ，r e s e q u e n c i n ga n do t h e rf e a t u r e st h a nb e f o r e ， w h i c hc a nb ea d a p t e di ns w i t c ha r c h i t e c t u r et h a ts u p p o r t s1 t b p st o1 0 0 t b p s t h i s s e v e r a la p p r o a c h e sw o u l dp r o v i d et h e o r ya n dk e yt e c h n i q u e sf o rr e l a t e dp r o d u c t s k e y w o r d ：u l t r a - s c a l a b l e 、s c a l a b f l i t y 、s w i t c h i n gf a b r i c s 、m u l t i - p l a n em u l t i s t a g e 、l o a db a l a n c e d 、 s i m u l a t i o nr o o d e l i v 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确 的说明并表示谢意。 关于论文使用授权的说明 年月日 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘， 允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文的全 部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描 等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：呈星垒导师签名：i 龛熊笙 日期：年月日 第一章绪论 1 1 课题研究背景 第一章绪论 近年来，随着宽带城域网、宽带小区接入网和3 g 网络建设的逐步深入，i n t e m e t 的用户迅速增加、业务种类越来越丰富，这些业务需求对骨干通信网路的传输带 宽和交换容量提出了前所未有的要求。由于波分复用( w a v e l e n g t hd i v i s i o n m u l t i p l e x i n g ，w d m ) 和密集波分复用( d e n s ew 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 ， d w d m ) 技术的不断应用和成熟，数据链路可提供的传输带宽资源迅速增长，网 络容量的压力开始转向网络节点设备，作为骨干网路由交换设备的电信级路由交 换系统日益成为骨干网络容量迅速提升的瓶颈。电信级路由交换系统是路由器技 术发展的重要方向，作为架构高性能信息网络的解决方案，日益成为学术和工程 实现的研究热点。由于电信级路由交换系统的交换能力取决于交换网络，因此， 如何优化设计交换网络内部流量控制机制及队列组织调度方法，攻克其中的关键 技术，是产业界研制相关产品所面临的核心问题。 交换结构( s w i t c h i n gf a b r i c s ) 是线卡之间的一种互连网络，其交换能力在很 大程度上决定着分组交换系统的性能，如吞吐率、交换时延及时延抖动、丢失和 乱序等 ”。当端口线卡( l i n dc a r d ) 数增加，交换结构的规模将增大，需要多个机 柜上的交换单元通过光纤线路连接构成。所谓的超大容量交换结构，是指交换容 量在1 t 比特以上、可平滑扩展至数十t 比特甚至更高的交换结构，是电信级路由 交换系统的核心技术之一。 目前，t b i t 级路由器已经在电信运营商的i p 骨干网上得到应用。这种路由器 一般是装在一个机柜内，端口速率为2 5 g b i t s 或l o g b i t s ，端口数为1 6 6 4 。当 流量进一步增加，电信运营商需要将路由器扩容，增加端口数，增大交换容量。 如何将单机柜平滑扩展到多机柜系统，尽量减小升级代价，是一个需要研究的重 要问题。与单机柜的路由器相区别，称由多个机柜组成的路由器为路由系统，路 由系统可以简化网络设计，降低网络管理开销，代表了路由技术重要的发展方向。 从1 t b i t 可平滑扩展到几十t b i t 甚至上百t b i t 的交换结构是路由系统的关键组成 部分。研究和攻克这种超大容量交换结构中的关键技术和优化实现方案，对于产 业界研制相关产品将有很大的参考价值。 电子科技大学硕士学位论文 1 t b i t 以下的交换结构，一般采用多个并行交换的c r o s s b a r 构成【2 ，可称为多 平面单路径的交换结构，每个c r o s s b a r 完成几十g b i t s 到上百g b i t s 的交换。但 是，基于c r o s s b a r 的交换结构存在扩展性差的问题：一方面，实现很大的c r o s s b a r 有一定困难，主要受芯片的管脚和i c 实现复杂度的限制( 其复杂度以n n 关系 增长，其中n 为单级交换单元的端口数目) ：另一方面，c r o s s b a r 采用集中调度的 仲裁器，当端口速率增大到1 0 g b i t 以上，端口数增加到1 0 0 以上时，仲裁器难于 在一个信元时隙完成仲裁【”，其处理速度极大地限制了系统容量的提升。因此， 1 t b i t 以上的超大容量交换结构一般不采用基于c r o s s b a r 的结构。一种较好的途径 是采用由多个交换单元构成连接网络的方法来实现一个更大规模的交换网络，这 是目前可扩展交换网络最常用的解决方案。1 t b i t 以上的超大容量交换结构一般都 是多平面多路径1 4 ，即有多个独立的交换平面，每个平面是多路径结构。 1 2 多平面大容量分组交换结构 目前大型路由器和交换机流行m s m ( m e m o r ys p a c em e m o r y ) 架构。m s m 架 构在交换网络的输入端和输出端放置了大量的缓存，用以减少分组( 信元) 的丢 失，而在内部采用无缓存或少量缓存结构。概括地说就是输入输出缓存加内部缓 存( 或内部无缓存) 。为了提高网络性能，m s m 架构内部多采用1 5 倍以上的加速 比，采用多平面并行处理的技术。本文将当前实用的多平面大容量分组交换结构 归纳为三类：多平面单路径无缓存交换结构、多平面单路径缓存交换结构和多平 面多路径交换结构。 1 2 1 多平面单路径无缓存交换结构 如图1 - 1 所示的多平面单路径无缓存结构中，变长的分组可以被切割成定长的 信元在交换网络中传输，由于每个c r o s s b a r 交换平面没有缓存，因此分组( 信元) 之间的顺序是很容易被保持的。在输出接口中，与每个输入v o q ( v i r t u a lo u t p u t q u e u e i n g ，v 0 0 ) 对应p j ，存在一个v i q ( v i r t u a li n p u tq u e u e i n g ，v i q ) 队列，用 来将信元重组成分组，即重排序队列。c i s c o 的1 2 0 0 0 系列路由器、p m c s i e r r a 的 1 1 1 芯片组【6 】1 7 1 【8 1 、z e t t a c o m 公司的交换芯片组以及l u c e n t 的交换芯片组p 1 4 0 9 】 均采用了上述多平面单路径无缓存交换结构。 第一章绪论 i n p u tp o r tm k r 觚e c r o s s b a rs w i t c ha n d s c h e d u l e r o u t p u tp o ai n t e r f a c e v o q v i q t p a t0 u t m 图1 - 1 多平面单路径无缓存交换结构 图1 - 1 中每个输入接口控制器( i n p u tp o r tc o n t r o l l e r ，i p c ) 包含n 组v o q 队 列，每组队列对应一个输出端，每组队列又分为m 个子队列。这些队列形成m 个 虚拟输出队列( v i r t u a lo u t p u tq u e u e i n g ，v o q ) ，即对应每个交换平面有一个v o q 。 这样，分组可以在多个交换平面的多条路径上并行传输，调度算法首先要完成i p c 内v o q 到i p c 输出端口的匹配，即v o q 与交换平面匹配，然后要完成i p c 输出 端口与交换平面的匹配。图1 - 1 也可以用一个v o q 来取代m 个v o q 。每个i p c 给多个交换平面的调度器发送请求，接收它们的应答，根据应答信号决定将v o q 中的信元发往哪个交换平面。 1 2 2 多平面单路径缓存交换结构 另一种实现大容量交换网络的途径是在每个交换平面内使用共享存储器【1 0 1 ， 如图1 2 所示。使用共享存储器的优点在于不再需要利用调度器来解决竞争。当一 个信元进入交换平面后，它就被写入共享存储器，它的地址指针被送入逻辑输出 队列，该队列中存放着所有去往这个输出端口的信元的指针。当信元被调度离开 电子科技大学硕士学位论文 交换平面时，逻辑输出队列通过指针将信元从共享存储器中读出。因为在一个时 隙里，共享存储器要执行n 次读操作和n 次写操作，因此需要很高带宽的总线。 通常共享存储器和逻辑输出队列是设计在一个芯片中的。i b m 公司的交换芯片组 p r s 和i n t e r n e tm a c h i n e 公司的交换芯片组采用了上述多平面单路径缓存交换结 构。 v o q 图1 - 2 多平面单路径缓存的交换结构 因为共享存储器的容量是有限的，所以需要反压策略( b a c k p r e s s u r e ) 来避免 共享存储器溢出。一旦输出队列长度超出了门限，它就对输入控制器的数据流实 行反压。通常，在一个交换平面中有多个服务优先级，不同的分组流可能对应不 同的服务优先级。对应不同优先级的分组有不同的反压信号。在逻辑输出队列中 每个优先级都对应一个门限，图1 2 中分别用t 。，t 1 ，一，r 。表示。若某个优先级的 业务流在逻辑输出队列中占有的容量超出了门限，那么所有的输入端口都将收到 关于这种业务流的反压信号，从而使这种业务流暂时不能进入交换平面。图1 2 示出各队列含有不同的门限，一旦超过门限就激活反压信号。图1 2 中的虚线箭头 4 第一章绪论 表示对输入控制器的反压操作。 设计多平面单路径缓存交换网络的关键问题是保持信元的顺序。如果同一业 务流的信元通过不同的中间级共享缓存交换网络，那么它们可能会经历不同的时 延。因此，在输出端口对信元进行重排序是很必要的。若分组的时延抖动越大， 则重排序所需的缓存容量也越大。另外一种保持信元顺序的方法是使属于同一分 组流的信元通过相同的中间级共享缓存交换平面，然而这样就无法将业务流均匀 地分摊到多个交换平面【1 ”。 1 2 3 多平面多路径交换结构 图1 3 给出一种典型的多平面多路径( 多级) 交换结构，它的每个平面包含一 个多级b e n e s 网纠1 2 】i t 3 【1 4 】【1 5 】1 1 6 1 。在b e n e s 网络中，输入端口和输出端口之间存 在多条并行路径，可使该结构具有内部无阻塞特性。通常，在设计一个具有多级 b e n e s 网络的分组交换网络时，面临两个问题。如果交换单元具有内部缓存，可以 减小内部信元丢失，然而保持信元顺序的问题就变得很有挑战性了。因为对于输 入输出端口对之间的不同路径，内部缓存会引入不同的信元时延，造成分组( 信 元) 的失序现象。另一方面，如果交换网络没有缓存，通过分布式调度算法为分 组选择一条路径以达到高的吞吐率，在计算上是比较复杂的。对于高速大容量交 换网络而言，如果简单的调度算法不能取得高的吞吐率，那么只有通过内部链路 加速来提升交换网络的性能【1 7 】【1 8 】。 图1 - 3 多平面多级( 多路径) 交换结构 电子科技大学硕士学位论文 目前，基于b e n e s 拓扑构建的多平面多级超大容量交换结构的典型( 唯一) 例子是c i s c o 公司最新推出的c r s 一1 ( c a r r i e r r o u t i n g s y s t e m ) 系统【”1 。c i s c o c r s 1 单机柜系统支持1 6 个4 0 g 线路板，共计1 2 t 交换容量；多机柜系统配置可扩展 至7 2 个线卡机柜，配合8 个交换机柜，可提供总共1 1 5 2 个4 0 g 线路接口，最高 达到9 2 t 交换容量。c r s 1 采用8 个交换平面，每个交换平面是完全可重排无阻 塞的b e n e s 结构。8 个交换平面并行工作，每个交换平面承载所需交换带宽的一部 分。为了确保信元均匀通过激活的交换平面，每个输入流量管理器( i n g r e s s ) 均匀 地分配信元通过8 个交换平面。就交换平面内部而言，c i s c oc r s 一1 系统将所使用 的b e n e s 结构定义为三级：第一级交换单元以轮循方式向所连接的第二级基本交 换单元发送信元；第二级交换单元将信元路由到相应的第三级交换单元，并提供2 倍的加速比；第三级交换单元将信元发送到目的线卡，并提供2 倍的加速比。 1 3 本文主要研究内容 为了适应通信业务流量的增长，解决可扩展性的问题，当单级交换单元的交 换容量不能满足需求时，为了实现一个更大容量的交换网络，采用由多个基本交 换单元构成的多平面多级网络是目前的一个发展趋势。在对完全可重排无阻塞 b e n e s 拓扑结构进行深入研究的基础上，本文主要针对基于b e n e s 拓扑构建的多平 面多路径( 多级) 超大容量交换结构的扩展性、q o s 性能、容错性、多播性能、 分组重排序方法等关键问题展开研究，目的是提出一些新的基于b e n e s 超大容量 交换结构的优化实现方案，相对现有方案在扩展性、q o s 性能、分组重排序等方 面具有综合优势，以支持1 t b i t 扩展到1 0 0 t b i t 甚至更高，为产业界开发相关产品 提供理论支持和关键技术解决方案。概括地，本文的主要研究内容包括： 1 对c i s c oc r s 1 系统交换平面内部所采用的b e n e s 结构和交换系统从 1 2 t b p s 到9 2 t b p s 的升级过程进行理论分析：对b e n e s 拓扑路径特性、无阻塞条 件和路由选择算法进行理论研究；理解c r s 1 系统实现大容量交换和扩容的实质， 为进一步的仿真工作建立基础。仿真模型在架构上采用基于负载平衡理论和反向 复用技术的多平面并行交换模式，其基本思想是利用多个b e n e s 结构通过并行处 理来组建一个超大容量的交换结构，通过两个层次的流量负载均衡，在各个完全 可重排无阻塞b e n e s 结构中实现负载均衡的并行处理，然后通过输出端口复用， 从而使其模拟一个输出排队( o u t p u tq u e u e i n g ，o q ) 结构。 2 为了弥补c i s c oc r s 1 系统在平面选择和中间级选择时所采用的简单随机 第一章绪论 或轮循方案的不足，需要找到一种适用于基于完全可重排无阻塞b e n e s 拓扑构建 的多平面多路径( 多级) 超大容量交换结构的两级负载均衡装置及方法，以有效 实现了交换平面间和b e n e s 交换平面内部路径间的、基于目的地址流的负载均衡。 3 详细给出本次仿真研究的3 种端口规模仿真方案设计和研究思路，对基于 b e n e s 的超大容量交换结构的扩展性( 扩容方法) 、队列组织调度方法、流量管理 器中的调度算法( i n g r e s s 中的平面选择策略) 、路由选择机制、反压机制、多播实 现方法和重排序方法等给予说明，同时分析3 种端口规模仿真方案中各模块的功 能和在o p n e t 仿真中的具体实现。该仿真平台的完整建立，对于今后继续深入研 究基于b e n e s 的超大容量交换结构关键技术，具有积极的推动作用。 4 仿真重点对提出的两级负载均衡策略进行考察，对各b e n e s 平面内各级基 本交换单元的缓存占用情况、通过各平面数据包的时延情况、重排序规模等进行 统计，具体考虑了平面选择策略对各平面各级缓存、平均时延及重排序规模的影 响、b e n e s 分发负载均衡策略对各平面各级缓存、平均时延及重排序规模的影响、 不同业务源对该交换结构性能的影响、各业务源不同负载对该交换结构性能的影 响等。 本文的研究采用基于w i n d o w s 2 0 0 0 操作系统的通用p c 机作为仿真基本平台。 根据对基于b e n e s 的超大容量交换结构需求分析及仿真工具的性能，选择o p n e t m o d e l e r1 0 5 作为主要的仿真工具。业务源模型除了包括b e r n o u l l i 、p o i s s o n 、o no f f ， 也对合成自相似业务源( s e l f - s i m i l a r t r a f f i c ) 【2 0 】t 2 1 1 、合成b e r n o u l l i 流及合成p o i s s o n 流进行了考虑。 1 4 论文章节安排 本文共分为六章。 第章绪论部分。将当前多平面大容量交换结构分为三类，c i s c oc r s 1 系统 属于其中的多平面多路径( 多级) 交换结构，是本文研究的重点。同时，本章对 本文的主要研究内容进行定义，给出了本文的研究思路和研究方法。 第二章对c i s c oc r s 1 系统交换平面内部所采用的b e n e s 结构和交换系统从 1 2 t b p s 到9 2 t b p s 的升级过程进行了理论分析；对b e n e s 拓扑路径特性、无阻塞 条件和路由选择算法进行了理论研究。本章指出了c r s 1 系统实现大容量交换和 扩容的实质，为进一步的仿真工作建立基础。 第三章提出一种适用于基于完全可重排无阻塞b e n e s 拓扑构建的多平面多路 电子科技大学硕士学位论文 径( 多级) 超大容量交换结构的两级负载均衡装置及方法，并给出该技术方案的 实现原理及实施方式。该方案弥补了c i s c oc r s 一1 系统在平面选择和中间级选择时 所采用的简单随机或轮循方案的不足，有效实现了交换平面间和b e n e s 交换平面 内部路径间的、基于目的地址流的负载均衡。 第四章提出了几种仿真实验方案，并详细描述了在o p n e t 平台上所搭建的仿 真模型。该仿真平台的完整建立，对于今后继续深入研究基于b e n e s 的超大容量 交换结构中的关键技术，具有积极的推动作用。 第五章对b e n e s 平面内部缓存、交换时延和重排序规模等进行了仿真结果分 析，重点比较了不同均衡策略在系统性能方面的差异。仿真实验结果表明本文提 出的两级负载均衡策略简单、高效、硬件易实现，适用于构建支持数十t b i t 甚至 更高的电信级路由交换设备。 第六章总结全文。 第二章b e n e s 拓扑及c i s c oc r s 1 系统分析 2 1 概述 第二章b e n e s 拓扑及c is c oo r s 一1 系统分析 1 t b i t 以上的超大容量交换结构一般采用多平面多路径结构。一种较好的途径 是采用由多个交换单元构成连接网络的方法来实现个交换平面，这是目前可扩 展交换网络最常用的解决方案。多级连接网络之间的不同取决于交换单元之间的 互连方式不同，典型的拓扑包括b e n e s 网络、c l o s 网络及k 元n 方多维交换网络 等。c i s c oc r s 1 分为单机架模式和多机架模式两种u9 1 ，可以在同一个系统中从1 6 个4 0 g b p s 端口扩展到1 1 5 2 个，其交换容量相应从6 4 0 g b p s 扩展到9 2 t b p s 。下面 通过对c r s 一1 系统交换平面内部所采用的b e n e s 结构和c r s 一1 系统从1 2 t b p s 到 9 2 t b p s 的升级过程进行理论分析，给出了b e n e s 拓扑路径特性和路由选择算法的 研究进展，指出了c r s 一1 系统实现大容量交换和扩容的实质，为进一步的仿真工 作建立基础。 2 2b e n e s 拓扑结构研究 2 2 1b e n e s 结构定义 b e n e s 网络是一种多级互连网络( m u l t i s t a g e n t e r c o n n e c t i o nn e t w o r k ) ，一个 n n b e n e s 网络记作b “1 ，它有个输入和个输出，共有2 n 一1 级，其中 n = l 0 9 2 n 。可以用递归来定义：一个n b e n e s 网络如图2 1 所示，其中的s ；，表 示第f 级第，个交换单元，其中0 s f 2 n 一1 且0 s ， n 2 。当n ：1 时，b e n e s 网 络即b ( 1 ) 就是一个基本的2 2 交换单元。当n ，1 时，在b b ) 的中间，由两个独立 的bn 一1 ) 上下排列组成，记作曰。 一”和b ，q 一1 ) 。在它们的两边加上第o 级和 第2 n 2 级，而且，第0 级的交换单元s 。的上输出连接b 。0 一1 ) ，下输出连接 b 。一1 ) ，第2 n 一2 级的交换单元s ：。，的上输入连接口。 一1 ) ，下输入连接 b ，仍一1 ) 。图2 2 所示是一个1 6 1 6 的b e n e s 网络，即b ( 4 ) 。 9 电子科技大学硕士学位论文 o l ； 糖人； n - 4 n 一3 n 一2 n i 缓敷； 输出 n 一4 n 一3 n 一2 冀一1 圈2 - 1 一个n x n b e n e s 网络b ) 在b ) 中，任意的i 级，0 ic h 一1 ，交换单元s “，0s ，c 2 ，能够被分 成2 i 组相对独立的子集豁。，0 kc2 i ，对于每一个豁难形成了某个b ( n f ) 的第 一级，把这个b ( n i ) 记作m 0 一i ) 。对每一个船城的上输出和下输出分别是 口：。0 一i 一1 ) 和b ：。0 一i 一1 ) 的输入，而b ：。一f 一1 ) 和b ：m 0 一f 一1 ) 的输出分别 是豁：。的上输入和下输入。具有这种特性的b ：。0 一i 一1 ) 和占：m 0 一i 一1 ) 称作 共轭网络。如图2 2 中的b 。( 2 ) 和鼠( 2 ) 是一对共轭网络。b e n e s 网络具有很好的共 轭性，利用这种性质，我们会在路径上得到一些结果。 i2345 图2 - 2 一个1 6 x 1 6 的b e n e sn 络b ( 4 ) 第二章b e n c s 拓扑及c i s c oc r s 一1 系统分析 2 2 2b e n e s 路径特性 2 2 2 1 路径 定义1 ：在一个n x n 多级互连网络中，从任意个输入端到任意一个输出端 间的连接称为一条路径，它包括途中所经过交换单元、交换单元间的链路以及交 换单元的选路等。 在b o n e s 网络中，可以用2 n 一1 位二进制位来表示任意给定输入端的一条路径， 记作z 2 n - 2 z ：。z 。，其中，咒( 0e i 2 n 一1 ) 表示在这条路径中第2 n 一2 一i 级交 换单元的路由选择，当交换单元选择上输出，咒为0 ，选择下输出，船为1 。 定理1 ：在b 0 ) 中，任意一条路径z 2 n - 2 z ：。z ，z 。中，路径后半部分的二进 制编码值等于输出端口号。 证明：用数学归纳法证明。当n = 1 时，占( 1 ) 就是一个基本的交换单元。任意 一条路径z 。，当x o = 0 时，从上输出端口输出，输出端口号为0 。当z 。= i 时， 从下输出端口输出，输出端口号为1 。显然成立。 假设在b ) 中成立，即任意一条路径z 2 n - 2 z 。一。z 。z 。中，路径后半部分的二 进制编码值等于输出端口号。 我们来看b 如+ 1 ) 。设任意一条路径z ：。z ：。x ，从输出端口i ( o s f c2 n + 1 ) 输出，我们要证明的是：z ：x z x 。= f 。 首先来看输出端的情况，当i 是偶数时，它是上输出端，由z ，的取值方法可知 = 0 ；同理当i 是奇数时，它是下输出端，得z 。= 1 。另外，b o n e s 网络中每个 交换单元有二个输出端，所以它所在的交换单元是第l f 2 1 个。 其次是由b o n e s 网络的递归结构可知，该路径的中间部分z 2 n - 1 而必然在 b o ) 或b 。) 。不妨设是b 。n ) ，由假设可知，z ：z 。的二进制编码值等于端 口号，设为k 。再由b e n e s 网络的连接方式，b 。( n ) 的输出端是连接口b + 1 ) 中第2 n 级的上输入，所以与它相连的下一级交换单元的编号就是k ；又已知第知级的输 出端口是f ，所以女一i 2 j ，即x ：x 1 = 【f 2 j 。对此式两边乘2 ，分以下两种情 况讨论： 当f 是偶数时，左边乘2 即把二进制编码左移一位，得以z ：z ，0 ，右边乘2 得。，所以z 2 2 1 0 = i 。又因为z o = 0 ，得到z 2 兢；九z 2 2 1 0 = i ， 即命题成立。 当i 是奇数时，左边乘2 可得z ：新o ，对于右边，因为【f 2 】= g 一1 ) 2 ， 乘2 得后z 2 2 1 0 = i - 1 ，两边加一得z 2 托1 = f 。又因为z o ；1 ，得到 1 1 电子科技大学硕士学位论文 丸z 2 2 1 = 以z 2 2 1 1 = i ，即命题成立。定理1 证毕。 推论1 ：在b “) 中，任意两条路径x 2 - 2 z 。一，z 。和2 2 - 2 a 2 n - 3 a t a o ，它 们到达相同的输出端的充分必要条件是，z ；= 九( f = 0 ，n - 1 ) 。 现知道b e n e s 网络中，任意一条路径z 2 n - 2 z ：。z l 甄的后半部分是决定输出 端，下面来讨论前半部分z ：。+ 。的作用。先引入共轭路径a 2 2 2 2 共轭路径 定义2 ：在b e n e s 网络中，任意一条路径p 1 = x 2 。- 2 2 2 “炳z o ，把它的第级 z ：。一；( 0s f cn 一1 ) 取反，得到一条新的路径p ：，则p 。和p 2 称为在f 级上的共轭路 径。 定理2 ：在b e n e