（通信与信息系统专业论文）应用于mdf的多级clos网络优化设计与路由算法研究.pdf

摘要 摘要 总配线架系统( m d f , m a i nd i s t r i b u t i o nf r a m e ) ，是用来连接电信业铜线用户与 局端机房的大型交换装置。其中由s i m p l e r n e t w o r k s 公司提出的自动化m d f 受到了广泛关注，它的核心是由大量的微继电器交换开关( m e m s ) 组成的空分 c l o s 交换网络。c l o s 网络是一种可扩展的多级交换结构，从功能上讲它在整个总 配线架中充当了连接交换的通道作用。但是随着通信用户的爆炸式增长，配线架 的端口也越来越多，c l o s 交换网络开关数量过大，成本较高。虽然有阻塞c l o s 网 络能在不改变交换规模的情况下有效降低组网成本，但是在降低成本的同时也会 增加网络阻塞率。 针对以上问题，本文对c l o s 网络的性能和结构之f 日j 的关系进行了深入的分析， 从网络设计和路由算法两方面出发，达到了低成本和较低阻塞概率的平衡，并仿 真表明了本方案的可行性。 一方面，c l o s 网络扩展优化设计，它是从网络结构角度出发减少开关数和降 低阻塞概率。首先，网络的扩展性会带来交换模块种类增多等问题，种类越多， 成本越高。其次，在工程实现上交换模块的集成度受到芯片管脚的限制。这些问 题是本文进行网络设计时必须考虑的因素。第二章分析了传统的无阻塞无约束网 络优化设计，在此基础上对带模块约束的有阻塞网络规模，级数，开关数和交换 模块关系进行了详细分析和理论推导，最后对c l o s 网络进行了综合优化设计，大 胆增加首尾级扩展方式，并仿真验证了理论推导的正确性及其网络优化设计的可 行性。 另一方面，路由算法，它是从业务选路角度改善网络的阻塞性能，在有阻塞 c l o s 交换网络中，由于到达业务的随机性，会造成系统阻塞。现有的顺序选择法 ( m lm i n i m u mi n d e x ) 和最多占用优先级法( p ，p a c k i n g ) 只能确保找出一条可行 路，却无法保证找出最优路。如此，系统就会因资源利用不合理，使得阻塞率增 大。在第三章中提出了种新的基于概率的c l o s 最优路由算法( o r b p ) ，在算法 中，我们首先确定当前业务可能影响的后续业务，称这些业务为相关业务，然后 运用概率统计的方式，计算出当前业务的不同路由对于相关业务的阻塞概率影响 大小，最后选出一条对后续业务影响最小的路径作为当前业务的路由。 最后，为了考察带模块约束的网络设计的合理性与可行性，验证路由算法的 摘要 阻塞性能，我们搭建了这个网络结构的仿真模型，并在此基础上实现了传统算法 和o r b p 算法，对他们进行了多方面的仿真实验和仿真结果分析，对目前系统的 不足提出了下一步的改进方向。 关键词：配线架，c l o s 网络，网络设计，路由算法，阻塞概率 i i a b s t r a c t a bs t r a c t t h em a i nd i s t r i b u t i o nf l a m e ( m d f ) i sl a r g es w i t c h i n gs y s t e mt h a ti su s e dt o c o n n e c tc o p p e ru s e r so ft h et e l e c o m m u n i c a t i o n si n d u s t r ya n di n f r a s t r u c t u r er o o m t h e a u t o m a t i cm d fa d v a n c e db ys i m p l e rn e t w o r k sc o m p a n yh a sb e e nw i d e l yc o n c e r n e d ； i t sc o r ei st h es p a c e - s p a c e - - s p a c ec l o ss w i t c h i n gn e t w o r kw h i c hi sc o m p o s e do fal a r g e n u m b e ro fm i c r o r e l a ys w i t c h i n gd e v i c e s ( m e m s ) c l o si sas c a l a b l ea n dm u l t i s t a g e s w i t c h i n gf a b r i c i ts e r v e sa sac h a n n e ll i n k i n gr o l ei nm d f h o w e v e r , a st h ee x p l o s i v e g r o w t ho fn e t w o r k su s e r s ，t h ep o r t sn u m b e ro fm d fi sm o r ea n dm o r e e x c e s s i v e n e t w o r ks w i t c h e so fc l o sa r en o ts u i t a b l ef o rt h eh i g hc o s t s t h eb l o c k i n g - c l o s n e t w o r k sc a ne f f e c t i v e l yr e d u c en e t w o r kc o s t s ，w i t h o u tc h a n g i n gt h es c a l eo fn e t w o r k s b u tr e d u c i n gc o s t sw i l li n c r e a s en e t w o r kc o n g e s t i o n i nv i e wo ft h ea b o v ep r o b l e m s ，t h ep a p e ra n a l y s e st h er e l a t i o n s h i pb e t w e e nt h e p e r f o r m a n c ea n dt h es t r u c t u r eo fc l o si n d e p t h w ef i n i s ht h en e t w o r kd e s i g n i n ga n d r o u t i n ga l g o r i t h m ，w h i c ht o r e d u c ec o s t sa n dt h ep r o b a b i l i t yo fb l o c k i n g ，a n dt h e s i m u l a t i o ns h o w st h a tt h ep r o g r a mi sf e a s i b l e o nt h eo n eh a n d ，t h ep o i n ti so p t i m i z e dd e s i g no fc l o sn e t w o r kw h i c hi st or e d u c e c o n g e s t i o n r a t ea n dt h en u m b e ro fs w i t c h e sf r o mt h ep e r s p e c t i v eo ft h en e t w o r k s t r u c t u r e f i r s t ，t h ee x p a n s i o no ft h en e t w o r kw i l lb r i n gm o r et y p e so fs w i t c h i n g m o d u l e s ，t h em o r et y p e s ，t h eh i g h e rc o s t s e c o n d l y , c h i pp i nw i l lr e s t r i c ti n t e g r a t i o no f t h em o d u l e si nt h ep r o j e c t t h e s ep r o b l e m sm u s tb et a k e ni n t oa c c o u n ti nt h ed e s i g no f t h i sn e t w o r k c h a p t e ri i a n a l y s e s t h et r a d i t i o n a ln o n b l o c k i n ga n du n c o n s t r a i n e d n e t w o r ko p t i m i z a t i o nd e s i g n ，o nt h eb a s i so fw h i c hw ec a r r yo u tad e t a i l e da n a l y s i sa n d t h e o r e t i c a la n a l y s i st ot h er e l a t i o n s h i po fn e t w o r ks i z e ，s e r i e s ，s w i t c h e sn u m b e r , s w i t c h m o d u l ei nt h eb l o c k i n g n e t w o r k s w eh a v ei n t e g r a t e dn e t w o r ko p t i m i z a t i o nd e s i g na n d p r o v e d t h e a c c u r a c yo ft h et h e o r e t i c a la n a l y s i s a n dt h ef e a s i b i l i t yo fn e t w o r k o p t i m i z a t i o nd e s i g nb ys i m u l a t i o n o nt h eo t h e rh a n d ，r o u t i n ga l g o r i t h mi m p r o v e st h eb l o c k i n gp e r f o r m a n c eo f n e t w o r k sf r o mp e r s p e c t i v eo ft h es e s s i o n sr o u t i n g i nc l o ss w i t c h i n gn e t w o r k ，b l o c k i n g o c c u r sb e c a u s eo ft h er a n d o m l ya r r i v e dt r a f l c i c s e x i s t i n gr o u t i n ga l g o r i t h m sa r em a i n l y i i i a b s t r a c t f o c u s e do nf i n d i n gaf e a s i b l ep a t h ，b u tn o ta no p t i m a lo n e n o n - o p t i m a lp a t ho f t e n m e a l l sw a s t eo fr e s o u r c ea n dh i g h e rb l o c k i n gr a t e i nt h i sp a p e r , w ep r o p o s e dan o v e l r o u t i n ga l g o r i t h mc a l l e do p t i m a lr o u t i n ga l g o r i t h mb a s e do np r o b a b i l i t y ( o r b p ) i n t h ea l g o r i t h m ，w ef i r s td e t e r m i n et h ep o s s i b l es e s s i o n sc a nb ei n f l u e n c e db yc u r r e n tp a t h s e l e c t i o n ，a n dc a l lt h e mr e l a t i v et r a f f i c s ；t h e nw ec a l c u l a t et h eb l o c k i n gr a t eo f e a c hp a t h ； a tl a s t ，w ec h o o s et h ep a t hw i t hm i n i m i z e db l o c k i n gr a t ea st h eo p t i m a lp a t ho fc u r r e n t s e s s i o n f i n a l l y , i no r d e rt oc e r t i f i c a t et h er a t i o n a l i t ya n df e a s i b i l i t yo ft h en e t w o r kd e s i g n w i t hm o d u l eb o u n da n dt h eb l o c k i n gp e r f o r m a n c eo ft h er o u t i n ga l g o r i t h m ，w es e tu p t h en e t w o r ks i m u l a t i o nm o d e la n do nt h eb a s i so ft h em o d e lw er e a l i z et h et r a d i t i o n a l a l g o r i t h m sa n do r b pa l g o r i t h m w ec o n d u c t e daw i d er a n g eo fs i m u l a t i o na n da n a l y s i s o fs i m u l a t i o nr e s u l t s ，p r o m o t i n gt h en e x ts t e pi nt h ed i r e c t i o no fi m p r o v i n g k e yw o r d s ：m a i nd i s t r i b u t i o nf r a m e ；c l o sn e t w o r k ；n e t w o r kd e s i g n ；r o u t i n g a l g o r i t h m ；b l o c k i n gp r o b a b i l i t y i v 图目录 图目录 图1 1 开关连接网络3 图1 2c r o s s b a r 结构4 图1 3 交换开关分类6 图1 4b a n y a n 网络结构7 图1 5 三级c l o s 网络结构8 图1 - 6c l o s 网络分类图8 图2 1c r o s s b a r 平方阵列12 图2 2c l o s 网络内部连接图一l3 图2 3 三级c l o s 网络扩展图1 4 图2 4 两种单元模块c l o s 网络18 图2 5 中间级扩展图2 0 图2 6 首尾级两级扩展图2 1 图2 7 首尾级完全扩展图一2 2 图2 8 网络设计流程图2 2 图2 - 9 一种单元模块c l o s 网络2 3 图2 1 0 对称网络设计框架图2 3 图2 1 1 不对称c l o s 网络结构2 5 图2 1 2 不对称完全无阻塞连接图2 5 图2 1 3 相同模块种类不同集成度仿真结果比较1 2 8 图2 1 4 相同模块种类不同集成度仿真结果比较2 2 9 图2 1 5 相同集成度不同模块种类仿真结果比较l 3 0 图2 1 6 相同集成度不同模块种类仿真结果比较2 3 1 图3 1 路由算法流程图3 4 图3 2 业务路径选择端口对应图3 5 图3 3m i 算法业务路径示意图3 6 图3 4m i 算法流程图3 6 图3 5p 算法流程图3 8 图3 - 6c l o s 网络端口分析图3 9 v i i 图目录 图3 7c d 算法业务路径示意图3 9 图3 8c d 算法流程图4 0 图3 - 9 业务路由示意图4 3 图3 1 0 中间模块内部资源示意图4 5 图3 1 1n f ( n ) 曲线比较：4 9 图4 1 功能模块图一5 l 图4 2 网络优化设计模块实现流程图5 6 图4 3 路由算法模块实现流程图5 7 v t i i 缩略语表 a m d f c d c s i c s i d f m i m i n m m m m s m o c s o r b p p r n b s n b s s s w s n b 缩略语表 a u t o m a t i cm a i nd i s t r i b u t i o nf r a m e 自动化总配线架 c y c l i cd y n a m i c c r o s s b a rs w i t c h i n p u tc r o s s b a rs w i t c h 轮循算法 纵横转换器 输入转换器 i n t e r m e d i a t ed i s t r i b u t i o nf r a m e中f u j 连接配线架 m i n i m u mi n d e x顺序选择算法 m u l t i s t a g ei n t e r c o n n e c t i o nn e t w o r k 多级互连网 m e m o r y m e m o r y - m e m o r y 全缓存交换 m e m o r y s p a c e m e m o r y 缓存空分混合交换 o u t p u tc r o s s b a rs w i t c h 输出转换器 o p t i m a lr o u t i n gb a s e do np r o b a b i l i t y 基于概率的最优路由算法 p a c k i n g 最多占用优先级算法 r e a r r a n g e a b l yn o n b l o c k i n g 可重排无阻塞 s t r i c t l yn o n b l o c k i n g 严格无阻塞 s p a c e - s p a c e - s p a c e 全空分交换 w i s e s e n s en o n - b l o c k i n g广义无阻塞 i x 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名：硷当亟 日期：厶8 年莎月厂日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：途麴塑导师签名：三邀 日期：厶眸月乡日 第一章绪论 第一章绪论弟一早珀了匕 配线架是在通信系统中为了配线的需要，在交换机、电缆和用户的交接处安 装的配线装置。我们把这些配线装置分为两部分，一部分为用户和电缆敷设所采 用的配线设备，另一种为交换机出线所用的总配线架，即m d f ( m a i nd i s t r i b u t i o n f r a m e ) 。m d f 通常安装于局端机房里，是一个用来连接电信业铜线用户与局端机 房的大型交换装置，它确保每一个铜线用户都可以连接到正确的电信公司和争取 的服务。 s i m p l e rn e t w o r k 公司的自动化m d f 是基于微电子m e m s 开关技术的自动化 配线架系统。m e m s 比传统技术更快速，可扩展性更强，更可靠。该技术使得可 扩展性低成本的结构变为可能，并且取代了自动化人工配线架，在服务自动化和 维护方面也节省了大笔开支，该配线架系统已经逐步占领了市场。而当业务规模 较大时，m d f 中的连接网络开关数过大，晶片的生产成本就成了其推广应用的限 制因素，为了更好地节约成本，减少开关数量，自动化m d f 使用有阻塞网络结构， 但是在开关成本的预算范围内又必须尽量提高其性能，阻塞率尽量接近于0 ，因此 在m d f 系统中如何平衡成本和性能之间的关系，提高性价比成了一个急待解决的 问题。下面，我们讲简单介绍配线架的组成分类和发展，为后续章节的进一步展 开做好铺垫。 1 1 配线架 配线架是电缆或光缆进行端接和连接的装置，在配线架上可进行互连或交接 操作。通讯室和设备室的作用就像是布线系统的神经中枢，从工作区接过来的水 平线缆在这里的配线架上用互配或交叉的方式连接到设备端口。线缆的互配或交 叉连接的是通过模块化连接线或跳线来实现的。 1 配线架按照主次分为总配线架和中间级配线架，即m d f ( m a i n d i s t r i b u t i o n f r a m e ) 和i d f ( i n t e r m e d i a t ed i s t r i b u t i o nf r a m e ) 。 m d f 为总配线架，它是与程控交换机相连的配线设备，用以接续内外线、跳配 线，测试内外线，并保护交换机及传输设备、线路及施工人员免受过电压、过电流的 伤害。它由架体( 机架) 、模块、保安单元、告警器和跳线这几部分组成。 电子科技大学硕士学位论文 i d f 为中间级配线架，它是楼中利用星形网络拓扑的二级通信室，i d f 依赖于 m d f 。m d f 代表主机房，而i d f 则代表辅机房，m d f 主要放置服务器、集线器、 路由器、d s l 设备等，而i d f 是指一些较为偏远的分线房间，以光纤电缆与m d f 连接，在i d f 中一般会放置集线器及配线架。 2 按照传输介质可分为光纤配线架和铜缆配线架。配线架是少有的既广泛用 于铜缆又用于光纤配线网络的组件之一。光纤配线架的价格在过去的几年中的增 长要远远高于铜缆配线架。铜缆配线架与光纤配线架有着很大的差别【lj ，铜线可以 在一个端口上即一对线上实现信号双向传输。然而光纤必须通过两个端口才能实 现信号的发送和接收，这是因为在光纤中只能实现单方向的传输。有人认为光纤 配线架没有真正的配线，因为光纤只是通过连接器被连接，并没有通过硬连线连 接。毫无疑问，光纤的数据传输速度要远远高于铜线。但是配线架的主要功能在 于为提供信号业务流的直接连接，而不是提供特定速度下的数据传输。 对配线架的设计主要内容包括两个方面：配线架种类的选择和容量的确定以 及安装方式。确定配线架的种类需要根据水平线缆的种类，并参考用户对日常使 用和管理的要求而定。根据所选择的水平缆线的种类，可以决定是选择对绞线配 线架、同轴电缆配线架还是光纤配线架。从用户的日常管理维护出发，决定是选 择卡接式配线架、快接式配线架、还是模块化配线架。事实上，随着布线技术的 发展，配线架自身也在沿着高密度、易管理和易安装的方向发展。 本文研究的是s i m p l e rn e t w o r k s 公司的自动化铜缆总配线架( a m d f ， a u t o m a t i cm a i nd i s t r i b u t i o nf r a m e ) 。为满足基于m e m s 技术的可扩展配线架系统， 本文选用多级c l o s 网络进行研究，选用c l o s 网络是因为它具有的诸多优点，比如 组网简单，可扩展性强等。c l o s 网络在e z m d f 中充当了连接通道的作用，将铜 线用户与设备连接起来，是配线架的核心，要减少m e m s 开关数，降低成本就得 从c l o s 网络入手。因为c l o s 网络作为开关交换网络被配线架采用，为了更好地阐 述c l o s 网络的发展特性，我们以其归属类开关交换网为介绍背景，引出c l o s 网络。 1 2 开关交换网 开关交换网越来越受到人们的广泛关注，在许多领域发挥了重要的作用，比 如说数据传输、电话会议、广播、卫星传送等等。很多国际著名的网络设备商和 服务商都竞相开发和配置了越来越快的交换器和路由器。从共享总线式交换器到 交叉开关结构的出现曾一度掀起了交换结构研究的新潮流。交叉开关不但可以使 第一章绪论 得多个端口之间并行地进行信息的传递，也可以高效地进行一对多的多播传输， 开关类型决定了开关网络的功能。 开关交换网络就是由交换开关组成的网络，开关交换网络起源于电话连接的 需求，是电路交换网络的典型代表 2 1 。在还没有多少电话时，任意两部电话之间都 会直接铺设一条线路。但是，随着电话数目的与目俱增，这些线路的传输费用就 越来越负担不起了。这时，“开关 或“转换”的概念就应运而生了。因而，人们 把一个给定区域内的每部电话都连接到一个“转换 中心，连接这些电话的线路 在这里通过一个网络相互连接，这个网络就称为开关交换网络。后来，开关交换 网络又应用于并行计算机来连接一组带有记忆的处理器【4 j 。目前，开关交换网络又 有了许多其他的应用，比如说数据传输、电话会议、广播、卫星传送等等。它与 人们的生产、生活息息相关，密不可分。可以晚，人们对开关交换网络的需求正 在迅速的增长。 - l 、v 输出 ( a ) 双边网络 厂。一r _ _ 卜- 一r ，i 卜一， 厂卜+ t 一一一一一卜_ j ! 广一一一一一一一j 输入输出i ：一 一一_ 一- l 一 一二一一_ 一卜一 厂 ( 一卜卜卜 ，一一卜 ；c 卜_ _ j ，c 一 ( b ) 单边网络 图1 - i 开关连接网络 一个开关交换网络既可以连接一群用户，称为单边网络，也可以连接两群用 户，称为双边网络( 如图1 1 ) 。注意到通过在双边网络的两边放置相同的实体集 合，一个双边网络可以用作一个单边网络，尽管从转换的角度来讲这样做是不经 济的。若不做特别说明，本文所说的网络都是指双边网络。 开关交换网络的基本组成部分是纵横转换器( c s ，c r o s s b a rs w i t c h ) ( 偶尔也会 使用其他转换器) 和链接。链接是用来连接这些c s 的，c s 也就是本文配线架上 使用的单元模块。我们把具有n 个输入端口和m 个输出端口的转换器记为x 。它 电子科技大学硕十学位论文 是交叉点( c r o s s p o i n t ) 的一个矩形排列，其尺寸是n 木m 的。如图1 2 尺寸为3 术4 。 这也是最简单的一种开关交换网络。每个交叉连接点只存在两种状态：一种是 “c r o s s ”状态，它表示上下、左右直通连接；另一种是“b a r 状态，它表示上端 与右端、左端与下端已连接。当交叉点( 工y ) 的开关处于“b a r ”状态时，数据 就从x 输入端输出到】，输出端。交叉点的闭合与断开是由调度器来控制的。c l o s 结构就是由一定数量的转换器构成的。 c r o s s p o i n t s w i t c h l _ z 口口口口 ，。广 。 l7 l l 7 y c r o s s 状态 b a r 状态 图1 2c r o s s b a r 结构 大多数开关交换网络是按级来组织的，每一级由一列转换器组成。除最后一 级外，每级的每个c s 的出口都连接到下一级的某个转换器的入口。某些转换器是 连接到外部世界的。对双边网络来讲，这种连接到外部世界的c s 分为两类，一类 是第一级的c s ，称为输入转换器( i c s ，i n p u tc r o s s b a rs w i t c h ) ，另一类是最后一 级的c s ，称为输出转换器( o c s ，o u t p u tc r o s s b a rs w i t c h ) 。i c s 上的连接于外部世 界的链接称为网络的输入，而o c s 上的连接于外部世界的链接称为网络的输出。 他们有时也称为外部链接，而其他的链接称为内部链接。 在一个j 级网络中，这些c s 被排列成s 列，每一列称为一级。同一级的c s 具有相同的尺寸，只有在相邻的级之间才会存在链接。如果不特别定义s ，我们称 这样的网络为多级互连网( m i n ，m u l t i s t a g ei n t e r c o n n e c t i o nn e t w o r k ) 【s j ( 对多级互 连网的研究已经有很多【3 1 - 【6 】) ，第f 级和第汁l 级的c s 之间的链接是从前者的出口 到后者的入口。第一级和最后一级的转换器是输入输出转换器，其入口( 出口) 是网 络的输入( 输出) ，我们称其为输入输出级。常见的网络有c l o s 网络、b e n e s 网络、 c a n t o r 网络等。目前对其它网络的研究也很多，参见【9 】- 1 1 2 】。本文主要研究的是c l o s 网络，我们将在下一节中对其进行详细说明。 4 第一章绪论 开关网络具有一个输入集合和一个输出集合，前者产生请求，通过网络连接到 后者。理论上讲，一个输入可以请求连接任意一个输出，正如一个电话可以打给 任意其他的电话。因此，网络必须提供从任意一个输入到任意一个输出的通路。 更进一步，一旦一个请求被连接( 或实现) ，它就需要持续一段时间，在此期间其 他的输入可能会产生它们自己的请求。一个开关网络所要做的就是同时连接这些 请求，其方式会因为某些终端的挂断和其他一些终端产生新的请求而不断的变化。 从经济的角度来讲，网络通常不会给一个输入到一个输出提供一条专用的路线。 因此，一个请求的连接可能会阻塞另外一个请求的连接，即网络无法为另外这个 请求提供一条通路，使得该通路上的链接都没有被使用。c l o s ( 1 9 5 3 ) 取得了一个令 人惊异的成就，他通过一些精巧得设计，证明了存在不阻塞网络，但是他们的硬 件却比专用线路构成得网络所使用的硬件要少得多。 对任意一个请求，如果存在一条路连接它，而且在这条路上没有链接被其他 的连接路所使用过，那么我们就称这个请求是可实现的。开关网络的不阻塞性质 一般可分为三类：在一个网络中，如果不管己经存在的请求是怎样连接的，一个 新的请求总是可实现的，则这个网络称为严格不阻塞的( s n b ，s t r i c t l y n o n b l o c k i n g ) 1 3 】；只要所有的请求都是按照一个给定的算法来连接的，那么一个 新的请求也总是可实现的，这时我们称这个网络是广义不阻塞的( w s n b ， w i s e s e n s en o n b l o c k i n g ) 1 4 】；如果在可以重新连接已经存在的请求的条件下，一 个新的请求总是可实现的，我们就称这个网络是可重排不阻塞的( r n b ， r e a r r a n g e a b l yn o n b l o c k i n g ) z 5 】。显然，一个s n b 网络必是一个w s n b 网络，一 个w s n b 网络也必是一个r n b 网络。 1 2 2 开关交换网的分类 交换开关是网络交换设备的重要组成部分，它直接决定连接交换设备的性能。 高性能交换开关的设计对网络核心交换设备的研制十分关键，下面我们简要介绍 开关交换网络的分类。交换开关分为时分交换开关和空分交换开关两类，如图1 3 所示。 在时分交换结构中，不能同时交换一个以上的输入端口数据。从交换结构的 角度来看，每个输入端口数据的处理是串行的。典型的时分交换结构包括共享总 线结构和共享缓存结构，且他们都属于单级结构。 与时分交换结构相比，空分交换结构适用范围更广，其输入输出端口处理数 5 电子科技大学硕士学位论文 据是并行的。空分结构分为单级和多级。c r o s s b a r 是典型的单级网络结构。多级交 换结构是由多个交换单元互联组成。多级结构之间的不同取决于交换单元之间是 如何互联的。这种互联方式又分为两大类，一是直接连接网络，另一种是间接连 接网络。直接连接网络最早应用于并行交换机中把多个计算结点连接起来，而后 又应用于路由器中，如a v i c i 公司的路由器t s r 。4 0 就采用这种结构。另一种连接 方式是间接连接网络，传统的a t m 交换机都采用这种方式，典型的如b a n y a n 网 络、c l o s 网络。三级c l o s 网络由于其扩展性好，网络性能优越，所以得到了广泛 应用。在j u n i p e r 的t 6 4 0 中就是采用c l o s 网络来实现路由器的逐级扩展。多级又 可分为单路径空分交换结构和多路径空分交换结构。单路径空分交换结构，从一 个输入端到一个输出端只有一条路径，这类结构中应用最广泛的是b a n y a n 网络。 在多路径交换中，从某个输入到某个输出端的路径有多条，如c l o s 网络。下面先 介绍c r o s s b a r 和b a n y a n 网络。 图1 - 3 交换开关分类 ( 1 ) c r o s s b a r 结构 c r o s s b a r 为典型的单级结构，即上一节中组成开关交换网络的转换器( 如图 1 2 ) ，后面我们一致称为交换单元，c r o s s b a r 结构可以同时提供多个数据通路【7 j 。 它是c l o s 网络的基本组成部分。c r o s s b a r 的网络复杂度随着端口数的增加以2 增大。因此，在大容量连接网络中存在两个问题。第一、对于小规模系统，每端 口成本还算合理，但随着规模的扩大，其成本涨得也很快。第二、所有的单级交 换结构在技术上受限于其尺寸与速度。一旦达到这些极限，单级网络无法再增加 端口或提升线路速率。正因为如此，可扩展的交换网络系统必须采用多级结构。 6 第章绪论 ( 2 ) b a n y a n 结构 b a n y a n 网络是典型的多级单路径网络，它是最早引入到a t m 交换结构设计中 的一种多级互连网络【1 6 1 。它是一个由2 * 2 的基本交换单元以一定的互连规则连接 起来的多级网络，如图1 4 中的b a n y a n 网络。任意输入线到任意输出线间仅有一 条通路，如果超过一个信元在同一时刻到达一个交换单元的话，就会产生碰撞冲 突。 _ 1 ，i ：j ! 一 1 3c l o s 网络结构 图1 - 4b a n y a n 网络结构 在多路径交换中，从某个输入到某个输出端的路径有多条，c l o s 网络是典型 的多级多路径结构【l 。7 1 ，而三级c l o s 网络是研究得最多的网络，它被认为是最基本、 最常用的多级互联网。它广泛地应用于数据传输、并行计算系统，提供连接作用。 三级c l o s 网络记为c ( n ， ，m ，z ：，乃) i l s 】，它的第一级由个宰m 的转换器组成， 即开关交换单元( 本文使用的是m e m s 晶片开关) ，称为输入级；第二级由研个 乖巧的交换单元组成，称为中间级；第三级由r 2 个m 牵n ：的开关交换单元组成， 称为输出级。每个输入级交换单元和每个中间级交换单元之间有且仅有一个链接 相连。类似地，每个中间级交换单元和每个输出级交换单元之间也是有且仅有一 个链接相连。但是，输入级交换单元和输出级交换单元之间没有链接。若 = r 2 ， n ，= n ，则三级c l o s 网络称为对称三级网络，记为c ( n ，m ，) 。如图1 5 所示即为 网络c ( 3 ，4 ，2 ) 。对称的三级c l o s 网络一开始是为纯粹的线路转接而设计的，它必 须在个请求的出发点和目的地之间建立一条通路，而且这条通路上的所有链接 都不能被其他的请求使用过。 7 电子科技人学硕十：学位论文 一 、 ；i 、一 1 、 弋二l 一= jj 二 一一 il l 、卜、厂 一 图1 5 二级c l o s 网络结构 本文主要以对称c l o s 网络为研究对象，也会涉及不对称c l o s 网络设计。如上 一节开关分类所说，根据c l o s 结构中交换单元的不同，如缓存m 交换，空分s 交 换等，又可分为三种基于c l o s 的交换网络：m m m ( m e m o r y - m e m o r y m e m o r y ) ， m s m ( m e m o r y - s p a r e - m e m o r y ) 和s s s ( s p a c e s p a c e s p a c e ) ，如图1 6 所示。本文 研究的是面向连接的空分开关交换单元，即s s s 网络【2 。c l o s 网络支持从源节点 到目的节点多路径路由，因此它比许多互连网络的链路拥有更好的容错性，c l o s 网络的多路径是由中间级交换单元提供的，中间级交换单元在c l o s 网络中起着交 通转接站的作用，其交换单元数目决定了c l o s 网络任意输入输出端口对之间存在 的路径数。路径数越多，阻塞概率就越低。然后存在路径选择就存在路由算法问 题。业务的随机性又会增加网络的阻塞率，好的路由算法可以降低阻塞概率。 ( a ) 空分s s s 结构 ( b ) 带缓存i 构i m s m 结构 图1 - 6c l o s 网络分类图 第一章绪论 我们的目的是要建立一个c l o s 网络，使得它既能满足低阻塞的性质，又能尽 可能的减少网络成本。网络成本由该该网络中交叉点的数目和交换单元的种类决 定。对于三级c l o s 网络来讲，它的交叉点的数目为m ( 2 n r + ，2 ) 。显然，c l o s 网络 成本跟m 的取值成正比。那么要降低网络成本，就得尽量减小m 的取值，但是减 小m 的取值又会增大网络的阻塞概率，因此开关数和阻塞问题成了不可调和的矛 盾。到目前为止，已经有很多人研究过三级c l o s 网络。在经典的线路转接中，对 于严格不阻塞，c l o s 1 1 】证明了，z = 2 ，z l ；对于可重排不阻塞，b e n e s 证明了m - - n 。 本文不考虑重排，且业务选择随机，那么如果m 2 n 一1 就必定存在一定程度的阻 塞。采用三级c l o s 网络所能构建的交换网络的端口数目是很有限的，往往因为端 口数太多导致了交换单元集成度太大，管脚太多而无法实现，所以采用多级是必 然的，本文的研究就是针对配线架的多级c l o s 有阻塞扩展网络。而多级c l o s 网络 最大的问题就是交换单元种类太多，路由相对复杂，成本较高。本文在控制交换 单元种类的同时优化网络，给制造商提供了很有用的参考平台。从下一章开始我 们就从网络优化设计和路由算法两方面着手，达到c l o s 网络较小开关数与降低阻 塞概率的平衡。 1 4 全文的研究思路及内容安排 本文的研究主要针对应用于总配线架中的连接网络开关数过大，模块种类过 多，成本较高，实现困难的问题。任务就是研究如何组网以减少开关数量，较少 模块种类以及如何降低其阻塞概率。c l o s 网络因为其组网简单，路由简单，好的 扩展性等良好性能而被总配线架选用，本文从c l o s 网络设计和路由算法两方面着 手，达到降低成本，减小阻塞概率的目的。网络设计是从改善网络结构入手减小 开关数，较少交换模块种类；路由算法是从改善网络阻塞性能出发减小阻塞概率。 本文所有的研究与仿真工作都是围绕着上述两点展开。 网络设计本文采用穷举筛选方式，把对硬件的需求作为设计时重点关注的问 题，充分考虑了因为扩展性带来的交换模块集成度的实现和交换模块种类成本问 题。一方面，受芯片管脚的影响，交换模块集成度会有上限，在组网时不能超过 这个上限；另一方面，交换模块种类太少，扩展时组网困难，种类太多成本又太 高，所以在组网时一般不超过2 种。鉴于上述问题，本文进行了优化设计，打破 了传统的仅仅中间级扩展c l o s 网络，穷举出