（计算机软件与理论专业论文）clos交叉矩阵中的路由算法研究.pdf

摘要 摘要 c l o s 网络自从诞生以来，广泛应用于电话网络、多处理器系统以及路由交换 机中。作为一种流行的的多级交叉结构，具有成本低、可扩展性好以及良好的路 由性能的特点，因此一直是研究的热点。 目前智能光网络的发展要求交叉矩阵具有高容量、快速的端口配置和组播支 持能力。而目前的c l o s 交叉矩阵，主要采用可重构无阻塞结构，在发生阻塞时需 要对交叉矩阵的状态进行重构，目前的算法搜索重构解的时间长，无法找到最优 的重构解，受影响的业务多，在单播业务和组播业务同时存在的时候组播业务的 阻塞率太高。 本文主要对c l o s 交叉矩阵中的路由算法进行了研究，主要的工作和贡献包括 以下两个方面： 1 针对单播业务中的重构问题，提出了一种改进的路由算法一最优重构路 由算法( o r r a ) 。该算法首先采用顺序方法分配中间模块，出现阻塞时再进行重构， 采用的重构算法是一种最优重构算法，它是在p a u l l 算法的基础上，通过并行搜索 不同的重构解，并在搜索过程中将这些重构解的集合构成输入重构树和输出重构 树，重构树的每一个路径代表一个重构解，每个路径的深度代表一个重构解的重 构次数，故按照此算法搜索到的第一个找到的解即为最优重构解。该重构算法是 基于p a u l l 算法的改进算法，因此重构树在有限的高度下必然能够找到最优的重构 解。通过o p n e t 软件的仿真，发现通过o r r a 算法在搜索出最优重构解的基础 上并没有增加算法的运行时间和交叉矩阵中的阻塞率。 2 研究了c l o s 交叉矩阵中的组播问题，并提出了一种基于四级c l o s 交叉矩 阵结构的单组播混合业务的路由算法一置换路由算法( p r a ) 。该算法在三级c l o s 交叉矩阵的输入级前增加一级，称之为置换级，路由时先将每一个请求业务按照 其扇出值及输入模块的负载置换到不同的输入模块，利用输入模块完成扇出，最 后采用o r r a 算法完成扇出后业务的路由。通过o p n e t 软件的仿真结果可以看 出，通过该算法能够明显的降低单组播混合业务的阻塞率，特别是组播业务的阻 塞率。 关键词：o l o s 交叉矩阵路由算法组播重构 a b s t r a c t c l o sn e t w o r kh a sw i d e l yu s e di nt e l e p h o n en e t w o r k s ，m u l t i - p r o c e s s o rs y s t e ma n d s w i t c h r o u t e r ss i n c ei tw a sf i r s tp r o p o s e d a n dc l o sn e t w o r k ，o n et y p eo ft h em u l t i - s t a g e n e t w o r k ，w a se x t e n s i v e l yr e s e a r c h e db e c a u s eo fi t sc h a r a c t e r i s t i c so fg o o ds c a l a b i l i t y , l o w e rh a r d w a r ec o s ta n de x c e l l e n t r o u t i n gp e r f o r m a n c e a tp r e s e n t ，t h ed e v e l o p m e n to fi n t e l l i g e n to p t i c a ln e t w o r kr e q u i r e st h em a t r i xw i t h 1 1 i g h - c a p a c i t y , r a p i dp o r tc o n f i g u r a t i o na n dm u l t i c a s ts u p p o r t e d b u tt h ew i d e l yu s e d r e a r r a n g e a b l et h r e es t a g ec l o sm a t r i xs h o u l db er e a r r a n g e dw h e nt h ec a l li sb l o c k e d ，a n d t h ec u r r e n tr o u t i n ga l g o r i t h mh a st h ed i s a d v a n t a g eo fm o r et i m ec o n s u m i n g ，m o r e e x i s t i n g c o n n e c t i o ni n f l u e n c e d ，h i g h e r p e r c e n t a g e o fm u l t i c a s tt r a f f i c b l o c k i n g p r o b a b i l i t y , a n dr e a r r a n g es o l u t i o ni sn o to p t i m a l t os o l v et h i sp r o b l e m ，t w on e w r o u t i n ga l g o r i t h m sa r ep r o p o s e df o rc l o sn e t w o r k t h e m a j o rw o r k sa n dc o n t r i b u t i o n sa r et h ef o l l o w i n gt w oa s p e c t s o r r a ( o p t i m a lr e a r r a n g e a b l er o u t i n ga l g o r i t h m ) w h i c hs o l v e st h ep r o b l e m so f u n i c a s tc o n n e c t i o n sr e a r r a n g e m e n t ，s e a r c h e sp a t hi ns e q u e n c eo r d e ra tf i r s t a n dt h e c l o sm a t r i xs h o u l db er e a r r a n g e di ft h ec a l li sb l o c k e d t h er e a r r a n g e a b l ea l g o r i t h mo f o r r ai m p r o v e df r o mp a u l la l g o r i t h m ，i sat y p eo fo p t i m a lr e a r r a n g e a b l ea l g o r i t h m i t s e a r c h e sa l lt h e r e a r r a n g e m e n ts o l u t i o n s i nt h e p a r a l l e l f a s h i o nu n t i lt h ef i r s t r e a r r a n g e m e n ts o l u t i o ni sf o u n d f o rt h es a k eo fr e c o r d i n gr e a r r a n g e m e n ts o l u t i o n st h e i n p u tr e a r r a n g et r e ea n do u t p u tr e a r r a n g e m e n tt r e ea r ec o n s t r u c t e d e v e r yp a t ho ft r e e r e p r e s e n t sar e a r r a n g e m e n ts o l u t i o n , a n dt h er e a r r a n g e m e n tt i m ec o u l db ed e n o t e db y t h ed e e po ft h ep a t h s i m u l a t i o n sw e r ec a r r i e do u to nd i f f e r e n ts c a l ec l o sm a t r i xw i t h o p n e ts o f t w a r e ，a n dt h er e s u l t ss h o wt h a tt h eo p t i m a lr e a r r a n g e m e n ts o l u t i o ni s a c h i e v e dt h r o u g ho r r aw i t h o u ti n c r e a s i n gt i m ec o n s u m i n ga n db l o c k i n gp r o b a b i l i t y p r a ( p e r m u t a t i o nr o u t i n ga l g o r i t h m ) w h i c ha p p l i e df o ru n i c a s ta n dm u l t i c a s t t r a f f i ci si n t r o d u c e dt of o u rs t a g e sc l o sm a t r i xw h i c ha d d so n ep e r m u t a t i o ns t a g eb e f o r e i n p u ts t a g eo ft h r e es t a g ec l o sm a t r i x i nt h ef i r s tp l a c e ，t h ec a l l sa r ep e r m u t a t e dt o d i f f e r e n ti n p u tp o r t sb yt h ep e r m u t a t i o ns t a g ea c c o r d i n gt ot h ef a n o u to fc a l la n dt h e o u t p u tp o r tl o a d so fi n p u tm o d u l e ，a n dt h e nc o m p l e t e dt h ef a n o u ti nt h ei n p u ts t a g e f i n a l l y , r o u t et h eu n i c a s tc a l l st h r o u g ho r r aa l g o r i t h m s i m u l a t i o n sw e r ec a r r i e do u t i nd i f f e r e n ts c a l ef o u rs t a g e sc l o sm a t r i x 谢t 1 1o p n e ts o f t w a r e ，a n dt h er e s u l t ss h o w t h a tp r aa c h i e v e sal o w e rb l o c k i n gp r o b a b i l i t yt h a no t h e ra l g o r i t h m s ，e s p e c i a l l yf o r m u l t i c a s tt r a f f i c k e y w o r d ：c l o sm a t r i xr o u t i n ga l g o r i t h m m u l t i e a s t r e a r r a n g ea l g o r i t h m 创新性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或 其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做 的任何贡献均已在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：蓖鲎鲎 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕 业离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。 学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全 部或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。( 保密的论文 在解密后遵守此规定) 本学位论文属于保密在一年解密后适用本授权书。 本人签名： 导师签名： 壶丝垒： 日期圣竺查：三：了 日期上趟盖乒 第1 章绪论 第1 章绪论 1 1 研究背景及现状 随着i n t e m e t 的迅速发展，人们对数据业务的需求激增，特别是具有突发、多 变、不确定等特性的i p 业务正在成为网络中的主导业务，并且以指数式增长。而 传统的光传送网在传送i p 业务方面有着明显的不足，主要表现在：网络支配过于 复杂、传输开销过大；网络互联方面不够灵活；无法实现带宽的动态分配。这一 系列缺点都促使开发新一代的光网络以满足用户以及开发商对不断增长的数据业 务需求。 通信技术的发展历史其实是一个不断提高载波频率和增加传输容量的的历 史。自从1 9 6 6 年英籍华裔科学家高锟( c k k a o ) 提出利用光纤进行信息传输的 可能后，光通信技术不断更新换代，通信能力不断提高，应用范围不断扩大。目 前的光网络传送层基本是以s d h ( s y n c h r o n o u sd i g i t a lh i e r a r c h y ) 和w d m ( w a v e d i v i s i o nm u l t i p l e x i n g ) 两层构筑，采用环式拓扑结构，主要应用在静态传输网络中， 使得光网络向动态、高度灵活性方向发展受到了极大限制，因此，研究人员正在 积极研制下一代光网络，以便集传输、交换、智能于一体，实现高度灵活和适应 性强的大容量光传送网。 1 1 1 自动交换光网络 光传送网逐渐从单纯的传送平台演进为一个与上层业务网紧密结合的综合 网，网络的组网灵活性、高可靠性和智能性已成为人们关注的焦点。为了顺应光 网络的演进趋势。使现有的静态传输网络向动态、可运营管理的智能化网络演进， 人们将a t m 和i p 路由功能引入到光传送网中，使得以w d m 为基础的光层组网 技术和以i p 为基础的网络智能化技术迅速发展并结合起来，形成了自动交换光网 络a s o n ( a u t os w i t c ho p t i c a ln e t w o r k ) 。 a s o n 通过在传统的静态光网络中引入动态交换和智能控制能力，完成“光传 送网+ 智能化”，从而使光网络从传统的“承载网络”向“业务网络”演进，从被动的网 络管理( 监控) 向主动地控制网络演进。这种演进以现有传送网的光层网络为基 础，是一个无缝融合的革新过程；既保护了运营商的原有投资，又把富有潜力的 光网络发展成能高度自主地应对业务需要、经济有效、可在光层上直接为全网提 供端到端服务的智能化控制光网络，而且可以根据不同也业务提供不同的服务等 级，保证高优先级的业务的服务质量【2 】。 a s o n 的每个网元都具有智能性，网元间可进行路由信息和链路状态信息的 2 c l o s 交叉矩阵中的路由算法研究 交换【3 1 。每个网元依据动态路由协议掌握着整个网络的拓扑结构和相关链路的状 态，实现资源的动态发现【4 】o 网元知道哪些网元具有可达性，并知道通过哪些路径 可达。智能光网络充分简化了网络管理系统，通过一个网管系统就可实现对网络 的有效管理，实现端到端的配置、故障管理和性能管理等功能。 a s o n 具有自身的网管系统，它是光传送网网管体系结构的一个组成部分【5 】。 在逻辑上，a s o n 网管系统与s d h 网管系统、w d m 网管系统并行管理光传送网， 它们属于同一层面。因此，a s o n 网络管理应采取以a s o n 网管系统管理为主， 需要时应与s d h 网管系统相配合来协调管理整个传送网，充分发挥a s o n 网在传 送网中的智能化电路调度作用。同时以网格状的组网方式，通过分布式智能管理， 提供更为完善的恢复机制、快速的电路响应、有效的资源利用和便捷的带宽管理。 新一代智能光网络a s o n 具有多方面的优势： 1 智能化：快速提供网络业务，提供新的业务利润增长点，如光虚拟专网 ( o v p n ) ，业务流量工程( t e ) ，三重播放( t r i p l ep l a y ) 等高a r p u ( a v e r a g er e v e n u e p e ru s e r ) 值业务；提高业务的生存性，有效抵抗网络多点故障，真正达到9 9 9 9 9 以上的电信级业务等级； 2 标准化：通过采用标准化的协议和接口实现多厂商，多运营商环境下的 网络互操作； 3 个性化：灵活提供不同的业务等级满足目前迅速发展的差异化( d i f f - s e r v ) 服务的需要； 4 简易化：实现对业务的自动保护和拓扑发现，减少人工配置的工作量， 充分降低维护难度。 a s o n 在传统的静态光网络中引入动态交换和智能控制能力，从而使传送网 实现从承载网向业务网的演进。随着它的技术框架体系结构和协议的成熟，作为 传送网的主流发展方向已获得业界的普遍认同。目前各大通信设备提供商均有 a s o n 网络设备，而且各大运营商已经开始在局部地区构建a s o n 网络。 1 1 2a s o n 网络中的业务 在传统的光网络中，主要提供端到端的面向连接业务，随着宽带技术的不断 发展，f t p 、h t t p 、s m t p 等传统数据业务已经难以满足人们对信息业务的需求， 视频点播、远程教学、新闻发布、网络电视等业务将成为新一轮运营竞争的焦点。 这类新型业务的特点是，由一个服务器( 媒体流服务器) 发布信息，大数量的客户 端接收信息，其数量可能是成千上万，而且具体数目不固定。而组播技术非常适 合这类新型业务，并具有下列优点： 1 ) 流服务器不必知道某个客户端是否存在，它只负责按组播地址将媒体流播放 出去； 2 ) 流数据在网上仅仅传送一份即可，即使有成千上万个客户端； 第1 章绪论 3 3 ) 用户端如果希望接收某媒体流服务器的数据时，只需加入该媒体流服务器播 放数据使用的组播组即可1 6 j 。 所以传送网能否很好的支持组播业务则对传送网性能的又一大挑战，对于传 输网络要支持组播业务的关键就是要交叉连接设备能够实现一对多或多对一的输 入输出端口完成交换功能；做为交叉连接设备的核心，交叉矩阵是实现交换的最 终承担者，因此这也是本文研究的意义所在。 m l c - 0 x c ：组播光交叉连接：具有组播能力的光交叉连接设备 图1 1 光网络中的组播 图1 1 是一个光网络中的组播实例，数据从一个客户节点s 要同时传送到三 个目的客户节点d 1 、d 2 、d 3 ，如果网络中的交换设备不支持组播交换，那么就需 要从原节点到目的节点分别建立连接；但是如果交叉连接设备具有组播功能，如 图1 1 中的m c o x c ，那么就可以通过在交叉连接设备中进行扇出，如蓝色线条 所示。从图中可以看出要实现网络的组播，网络中必须包含具有组播能力的交叉 连接设备，通过该交叉连接设备来实现一对多的连接，因此具有组播能力的交叉 连接设备是支持网络实现组播业务的基础。 1 1 3 光网络中的传输设备 交叉矩阵是a s o n 节点设备传送平面的核心部分，a s o n 设备和传统的 s d h m s t p 设备相比，除了增加控制平面外，在传送平面硬件方面也有更高的要 求。例如交叉容量的提升和交叉矩阵对组播业务的支持。这主要是基于以下三方 面的原因：首先，a s o n 是基于格状网络构建的，相对于以往的环网结构来说，a s o n 节点设备上要提供更多的光接口，要有更强的业务调度和疏导能力。其次，在基 于格状网络拓扑结构的a s o n 网络中，网络的保护和恢复都是根据网络中当前资 源进行动态实时配置，因而交叉矩阵必须能够快速的完成输入输出端口的配置， 来提高恢复时间。最后，交叉矩阵具有组播能力可以更好地支持a s o n 网络中的 组播业务。 目前在交换设备中应用最为广泛的交换结构为c r o s s b a r 结构和三级c l o s 结 4 c l o s 交叉矩阵中的路由算法研究 构，c r o s s b a r 结构具有但组播严格无阻塞的特点，但是成本高，可扩展性差的不 足，目前主要采用b i t s l i c e 技术来提高单板的交叉能力。三级c l o s 结构是一种多级 网络结构，常用的是重构无阻塞结构，他的优点是成本低，可扩展性好，但是在 存在组播业务时，网络的阻塞率比较高，由于传统的三级c l o s 矩阵的重构无阻塞 特性，在网络发生故障时，a s o n 节点设备的交叉连接要进行内部路由搜索，延 长了全网恢复时间。 1 2c l o s 网络的介绍 c l o s 网络于1 9 5 3 由贝尔实验室的c h a r l e sc l o s 提出i | 7 1 ，它通过使用多个较小 交换容量的交换单元来构建大容量交叉矩阵。c l o s 网络具有良好的可扩展性瞄驯、 高度的灵活性和可靠性【1 0 d 1 1 。良好的可扩展性是指网络的规模能够适应网络业务 发展的需要，随着网络业务量的增长，网络的交换容量可以平滑升级，提高网络 设备初期投资的利用率；高度的灵活性指的是网络能够满足传输网络业务多样化、 综合化的要求，能够实现多颗粒度，不同服务质量保证的业务转发要求；网络的 可靠性指的是网络结构具有路径多样性，拥有强大的容错能力并且具有对业务转 发的自动保护机制，因此能够适应网络业务对传输设备可靠性的要求。 1 2 1 结构及分类 常见的三级对称的c l o s 网络如图1 2 所示，第一级是由r 个n x m 交换单元构 成；第二级是由m 个r r 交换单元构成；第三级是由r 个m n 交换单元构成， 相邻两级的任意一对模块之间均存在一条物理链路，因此可以用符号c ( m ，n ，r ) 来表示。如果将一个三级c l o s 网络中的任一级交换模块用一个三级c l o s 网络来代 替，就可以构造出一个五级的交叉矩阵，以此类推可以构造出任意奇数级的c l o s 网络【1 2 1 。 图1 2 三级c l o s 交叉矩阵c l o s ( m ，刀，) 一。 “ 。一一 ；州一一 第1 章绪论 5 1 2 2 单播阻塞条件分析 对于一个c l o s 交叉矩阵，按照网络状态的特征( 网络状态定义为正在进行的 呼叫在中间级交换单元的占用格局) ，定义某些空闲的输入输出端口对之间不能建 立连接的网络状态为阻塞状态。根据网络的阻塞特性可以将其分为以下三种【1 3 】： ( a ) c l o s 网络是可重配置无阻塞的( r e a r r a n g e a b l e ) 指的是当且仅当给定一 组正在进行的呼叫和任一对空闲的输入输出端口，通过对当前进行中的呼叫重选 路由，可以在这对空闲的输入输出端1 2 1 之间至少建立一条连接路径。d s l e p i a n i l 4 】 证明了三级c l o s 网络v ( m ，1 1 ，) 的可重配置无阻塞条件为m 刀。 ( b ) c l o s 网络是广义无阻塞的( n o n b l o c k i n gi nt h ew i d es e n s e ) ：指的是当且仅 当合理的为每个呼叫分配路径以避免阻塞状态而且还能为每对空闲输入输出端口 分配新的路径，而不需要重新调整已建立的连接路径。a j a j s z c z y k 和c lj e k e l 在 r e p a c k i n g 概念的基础上提出了r e p a c k a b l e 无阻塞的概刽1 5 j 。通过定义非永久状态 ( n o n p e r m a n e n t ) 和过载状态( o v e r w e i g h ts t a t e ) ，他们证明如果网络的控制算法使得 网络的每一个过载状态都是非永久状态，网络的无阻塞充要条件是 m 2 n - f n ( r - 1 ) 。 ( c ) c l o s 网络是严格无阻塞的( n o n b l o c k i n gi nt h es t r i c ts e n s e ) ，是指不管采用 何种选路策略都不存在任何阻塞状态。c h a r l e s c l o s 最早给出了三级c l o s 网络 v ( m ，刀，) 的严格无阻塞条件为m 2 n 一1 。 上面给出了可重配置无阻塞三级c l o s 交叉矩阵，广义无阻塞三级c l o s 交叉矩 阵和严格无阻塞三级c l o s 交叉矩阵的定义以及条件，可以看出区别在于中间级交 换单元的数目以及为到达的呼叫采用的选路策略。虽然广义无阻塞和严格无阻塞 的c l o s 交叉矩阵可以无阻塞的建立连接，但是由于成本和实际应用中负载不可能 达到饱和，因此可重构无阻塞交叉矩阵的应用最为广泛。 1 2 3 组播阻塞条件分析 对于组播业务目前理论上只给出了严格无阻塞和一些广义无阻塞的条件，对 于可重构无阻塞目前还没有理论上的结论。而且对于组播业务阻塞特性和交叉矩 阵的组播扇出位置有很大关系。 g m m a s s o n 和b w j o r d a n 在文献【l6 】中第一次提出了严格无阻塞条件和可重构 无阻塞条件，当中间级交换单元数目满足条件m n + 【厂+ 1 ) 一l 时，则c l o s 交叉 矩阵对于组播业务是严格无阻塞的，而当满足条件m 玎木，时，网络对于组播业务 则是可重构无阻塞的。这个条件的得到是基于输入级扇出机制下得到的，网络成 本很高，没有实用价值。h w a n g 在文献【l7 1 指出，如果中间级交换单元没有组播扇 出能力时，以至于所有连接扇出必须在第一级和第三级进行，在这种假设条件下 m a s s o n 提出的对中间级交换单元数目的要求实现可重构无阻塞则是充分必要的。 6 c l o s 交叉矩阵中的路由算法研究 后来y u a n y u a ny a n g 又在【1 8 】提出了当m 1 1 1 j h ( ( 1 1 - - 1 ) ， + ，”，其中x 表示组播业务 使用的中间模块数，并且满足l sx s 蛐n 【n - l , r ) ，这样该c l o s 交叉矩阵对于组播 业务可以实现无阻塞条件。下表1 1 是在给定扇出值f 时，各种不同扇出模式下严 格无阻塞条件，其中扇出值f 表示一个组播业务要占用的输出模块数i l 圳。 上面简要分析了c l o s 交叉矩阵中组播无阻塞条件，而且对于任意一个组播严 格无阻塞网络，需要的开关数最少为u i 川j 【2 0 1 ，上面的严格无阻塞c l o s 交叉矩阵 的规模已经远远超出了c r o s s b a r 网络的规模，因此采用传统的c l o s 交叉矩阵对于 组播业务来说阻塞率太高。 表1 1 各种结构限制下的严格无阻塞的充分必要条件 网络结构特点( 扇出机制) 充分必要条件 三级均可自由扇出 m m i n ( n l 一1 ) 厂+ 他，( l - 1 ) f ，2 ) 第一级无扇出能力 m m i n n 2 一吃+ ( + n 2 1 ) n 2 ，1 ) 第二级无扇出能力 m _ n i n ( t t 一咖一1 + n i n 呸) “一骖厂 州疋呸 ，趣) 第三级无扇出能力 m m i n ( r 一1 ) f + t h ，( m 一1 ) f + m i n f , 吃) ，m ) 1 2 4 阻塞率分析 对于传统的三级c l o s 交叉矩阵，在全单播的情况下，要建立一条从确定的输 入端口到确定的输出端口之间连接，则要从输入模块到某个中间模块之间的链路 和中间模块到输出模块之间的链路均为空。如果用p 表示每条链路被占用的概率， 则p = pn m ，q = l - p 表示为空的概率，经过某个中间模块建立成功的概率为( 1 p ) 2 ， 由于有m 个中间模块，因此一个单播请求被阻塞的概率p b = 1 - ( 1 - p ) 2 】m 。对于一个 多链路c l o s 结构，由于每组有v 条链路，因此每一组全被占用的概率为p v ，这样 阻塞的概率p b = 1 一( 1 - p v ) 2 】m 。 对于一个组播请求，用输出模块表示，那么扇出值f 则满足1 ，用q ，吃， 表示从输入模块到中间模块之间的连接，瓦表示该链路被占用，q 表示该链路空闲； 魄。，：，k 表示从中间模块到输出模块k 之间的链路。用e 表示对一个扇出为f 的 组播请求产生阻塞的状态，o 表示输入级与中间级之间的链路的状态，尸( i 口) 表 示在状态表示在状态0 下产生阻塞的概率，尸( 仃) 表示处于该状态的概率。那么对 于该请求的阻塞率可以表示如下【2 1 】： 名( f ) = p ( s ) = p ( 仃) 尸( sl 仃) ：= 薹( ：l 户j ，”一尸( 占f 百，：i - ，口t + - ，a ) ( 。) 其中： 第1 章绪论 7 p ( s 雨，- ，) 1 _ ( 1 一p ) ，( 1 2 ) 将式( 1 2 ) 代入式( 1 1 ) 后阻塞率可以表示为： w ) 2 敲声p - k l - ( t 卅，( 1 3 ) 假如组播请求的输出值均匀分配分布，那么对于任意扇出的阻塞率可以对式 ( 1 3 ) 中所有的扇出情况可以取平均值表示如下： b = 尼( 厂) = 吾烈：户p - k ，如) ， 。，4 ， 虽然以上的分析给出了阻塞率与负载和扇出值的关系，但是首先从输出单元 的限制性上考虑到输出单元自身的限制性可以对式( 1 2 ) 描述的阻塞概率表达式 加以修改。这里考虑点对多点和点对点两种连接，且每一个输出单元有n 个输出 端1 3 ，如果某一个输出交换单元在一个组播请求中被选中，那么这个输出交换单 元至少有一个空闲输出端口，最多有n - 1 个输入端口处于忙状态。特别是当k n 1 的情况，f 个输出交换单元中每个都必须有空闲的输入端口。所以在k n 1 时p b = o 。 其次从处于忙状态的链路比例考虑到在任意时刻输入级和中间级处于忙状态 的链路数目以及中间级和输出级之间处于忙状态的链路数目，仍然分析点对多点 和点对点的连接请求。一般来讲输入级到中间级的处于忙的链路数应该比从中间 级到输出级处于忙状态的链路数要少。所以在这里假设从中间级到输出级链路遇 忙的概率和空闲的概率分别为所和吼 岛2 ；q b2 1 一p b ( 1 5 ) 这样从输入级到中间级的链路遇忙和空闲的概率则可以修改为 岛= a 见；和吼= 1 一见 ( 1 6 ) 其中口1 ，所以计算扇出值f 的组播请求被阻塞概率表达式( 1 3 ) 又被修改 成下面形式 忍( 厂) = n - , o 。2 儿”一。【1 一( 1 一见) ，】 b = 吾嘉茎( ? 卜。见”廿c 一。一见七，l c n - 1 【兄= 0 1 c 行 ( 1 7 ) ( 1 8 ) 8 c l o s 交叉矩阵中的路由算法研究 1 3 论文内容及结构 c l o s 网络是一种应用非常广泛的多级网络结构，特别是在大容量的交换设备 中，随着光网络的智能化的发展，网络中的服务要求越来越高，网络规模越来越 大，而且组播业务的出现给交叉矩阵的结构和算法的设计提出了更高的要求，本 文主要是在c l o s 网络结构的基础上，给出c l o s 交叉矩阵的路由算法设计的基础。 本文的内容及结构安排如下：第二章分别介绍并比较了c l o s 交叉矩阵中的几 种单播和组播算法；第三章在原有的单播算法的基础上提出了单播业务的o 鼬乙； 第四章在第三章算法的基础上，结合四级c l o s 交叉矩阵提出了种可以同时支持 单播和组播业务的路由算法；第5 章总结全文。 第2 章现有的路由算法研究 9 第2 章现有的路由算法研究 c l o s 交叉矩阵根据其阻塞特性可以分为三类，严格无阻塞、广义无阻塞和可 重构无阻塞。严格无阻塞和广义无阻塞虽然可以消除交叉矩阵中的阻塞问题，但 是成本过高，因此一般应用中均采用可重构无阻塞交叉矩阵。在可重构无阻塞交 叉矩阵中当业务量较小时，c l o s 交叉矩阵可以满足几乎所有的请求，并可以建立 成功的所需输入输出连接，这时无需对已有连接进行调整；但是在实际应用中， 业务量是随机的，很多时候会有突发的业务到来，这时就会引起交叉矩阵的阻塞， 使得业务无法建立，于是需要对现有的连接进调整，即重构，使得所需要的连接 能够建立成功。本章主要讨论可重构无阻塞条件下的路由算法。 在交叉矩阵中的组播业务根据目的节点数目的不同，可以分为单播、组播和 广播三种类型，单播是指待转发的消息在传送网中要求实现点对点的传输；广播 业务是指在传送网中把待转发的一个消息从源节点转发到传送网的全部输出端口 上，而组播业务是则把消息转发到传送网中的一组输出端口上。故从广义上来讲， 单播和广播是组播的一个特例。虽然单播业务可以理解为组播业务的一个特例， 但是在路由算法的设计和性能上还是有很大的区别，因此根据处理的业务的不同 可以将算法分为单播算法和组播算法，其中组播业务包括广播业务。下面就分别 对不同的算法进行介绍。 2 1 单播路由算法分析 c l o s 交叉矩阵中的单播路由算法主要解决在输入和输出模块确定时中间模块 的分配及调整的问题，因此在路由时都是以模块为路由单位，将输入端口和输出 端口的编号映射成模块编号进行处理。如表2 1 为一个c ( 3 ，3 ，4 ) 的一个可重构无阻 塞c l o s 交叉矩阵的请求输入输出端口表示，表2 2 为对应的模块表示。具体连接 关系见图2 1 ，在以下的所有的路由算法中，如果没有特殊说明，均采用模块对来 表示交叉矩阵中的请求链路。 表2 1 端口表示 表2 2 模块表示 1 0 c l o s 交叉矩阵中的路由算法研究 图2 1 交叉矩阵路由分配图 根据路由算法对新到的请求的处理方式不同可分为一次统一调整和逐条调整 法两大类。一次统一调整是将已建立的请求和新到的请求进行统一处理，进行一 次全网的输入输出匹配。具体算法有： 1 多步分解法； 2 矩阵分解法； 3 二部图的最大匹配与着色； 逐条调整算法则是对于每一条新到的请求分配，如果没有空闲的中间模块供 分配，则按照一定的规则将已建立的连接进行调整，以释放出空闲的中间模块， 来建立新的连接。最经典的为p a u l l 算法，以及以此为基础的一些改进算法。以下 将分别对这些算法进行分析对比。 2 1 1 一次统一调整算法 1 多步分解法 多步分解法是基于c l o s 交叉矩阵可重构证明理论( h a l l 定理) 的一种算法， 因此首先给出h a l l 定理，然后说明h a l l 定理在c l o s 交叉矩阵可重构的证明中的应 用。 h a l l 定理： 对于集合a 的r 个子集a 卜a 2 、，a r ，存在r 个不同的相异元素，a l 、a 2 、 a r ，满足a i e a i 及i j 时啦码的充分必要条件是a l ，a 2 ，a r 中任意k 个子集的 并集有至少k 个元素，其中1 k r 。 证明： 在c l o s 交叉矩阵中以输出模块为集合a ，每个输入模块所对应的输出模块为 第2 章现有的路由算法研究 一个子集，应用以上定理可以在每个子集中找出一个相异元素，由这些相异元素 组成一个相异代表系s d r ( s y s t e md i s t i n c tr e s p r e s e n t a t i v e ) ，由于这些相异元素属于 不同的子集，即不同的输入模块，同时它们又各不相同，即属于不同的输出模块， 因此可以给这些请求分配一个中间模块。同样在剩下的元素同样满足h a l l 定理， 因此进行n 1 次分配就可以完成交叉矩阵中的所有请求的路由。如图2 2 所示为一 相异代表系分配的中间模块。 i n p u ts t a g e m i d d l es t a g e o u t p u ts t a g e 图2 2 中间模块分配图 m h a l l 给出了一个求s d r 的算法，由于所讨论的问题已经证明符合h a l l 定理， 因此只讨论相异代表系一定存在时的情况田】。算法的具体实现如下： 设有元素集合s l ，一，s n ，用集合d 表示相异代表系并置为为空；从集合s i 任意 选取一个元素a i ，如果a i 与集合d 中的元素不冲突，则将该元素置入集合d 中， 继续搜索下一个集合s i + l ；如果到集合s ，时无法找到一个元素不于集合d 中已有 的元素冲突，那么意味着集合s ，中的元素b l ，“，b t ，已经包含在了相异代表系中， 这样就必须对现有的相异代表系进行调整，如果将b 1 ，“，b t 作为一个有序列表，并 记为t l ，那么第二个列表t 2 就由t l 加上以b 1 为代表元素的集合中不属于序列t l 的元素组成表示为b b , b t ，k l ，”，b 。；如果用s ( b i ) 表示以b i 为代表元素的集合，那 么依次类推可以用列表t i 加上s ( b i ) 中没有添加到列表t i 中的元素构造出列表t i + l ； 如果在列表瓦中找到一个元素b u ，它不是任何集合的代表元素，也不属于列表t l ， 但是属于集合s ( k ) 中的元素，并且不在列表k l 中，这里t 1 2 要满足条件u 2 u ， 如果k 属于列表t l ，那么就用b u 作为集合s ( k ) 中的代表元素，用屯作为集合s r 的代表元素；如果k 不属于列表t l ，那么k 必然属于集合s ( k ) ，并且满足u 3 a ( a ) 交叉矩阵状态( b ) 矩