（运筹学与控制论专业论文）三层clos网络不阻塞问题的研究.pdf

摘要 摘要 开关网络问题是一个起源于电话网络连接的组合优化问题。起初，人们研 究的是经典的线路转接模型下的开关网络。但是，随着数字和信息技术的不断 发展，又产生了许多新的模型，比如：多速模型、多点传送模型以及多速多点 传送模型。开关网络越来越受到人们的广泛关注，在许多领域发挥了重要的作 用，比如说数据传输、电话会议、广播、卫星传送等等。在开关网络的诸多经 典网络中，三层c l o s 网络被认为是最基本、最常用的多层互联网。本文主要研 究和分析三层c l o s 网络在这些新的模型下的不阻塞性质：严格不阻塞、广义不 阻塞和可重排不阻塞。全文共分为五章。第一章主要介绍与开关网络有关的一 些基本概念和预备知识。 由于我们在研究三层c l o s 网络的可重排不阻塞性质时用到了图论中的着色 理论，所以第二章的第一节主要介绍了图论的一些基本概念和基础知识，第二 节则介绍了着色理论。但是，利用图论中的知识和方法来研究开关网络的问题 时，我们不得不面l 临的一个问题就是图的存储问题。因此，第三节主要介绍和 图理论，并给出了我们得到的结果。 第三章主要研究三层c l o s 网络在多速环境下的不阻塞性质。本章第一节详 细介绍了多速模型，第二节则主要介绍三层c l o s 网络在多速模型下的一些己知 结果。本章第三节主要研究在只有两种速度b 和b 的情况下三层c l o s 网络的 广义不阻塞性质。由于以前人们对两速c l o s 网络的研究并不包括b 1 2 的 情形。本文针对b 1 2 的情形，我们给出了最好的预留方案来完成对一般 的两速情形的讨论。第四节主要研究三层c l o s 网络在多速环境下的可重排不 阻塞性质。c h u n g 和r o s s 给出了一个猜想：若每个请求的权重取自一个给定 的具有k 个重量的集合，则三层c l o s 网络c ( n ，m ，r ) 是可重排不阻塞的当且 仅当m 2 n 一1 。更进一步，这个猜想看起来不仅对离散带宽是正确的，而 且对连续带宽也是正确的。本文证明了当r 警一警时，c h u n g 和r o s s 对多 速c l o s 网络的可重排性的猜想在离散带宽情形和连续带宽情形下都是正确的。 第四章主要研究三层c l o s 网络在多点传送环境下的广义不阻塞性质。本章 第一节详细介绍了多点传送模型，第二节则主要介绍三层c l o s 网络在多点传送 模型下的一些已知结果。y a n g 和m a s s o n 证明了，如果m r a i n ( 7 , 一 l 1 2 t h e r e f o r e i nt h i ss e c t i o nw eg i v et h eb e s tr e s e r v a t i o n - s c h e m em u t i n gf o r t h eb 1 2c a s e t oc o m p l e t et h ed i s c u s s i o no nt h eg e n e r a l2 - r o t ec a s e t h ef o u r t hs e c t i o ns t u d i e st h e r e a r r a n g e a b l en o n b l o c k i n g n e s so ft h r e e - s t a g ec l o sn e t w o r ki nm u l t i r a t ee n v i r o n m e n t 一m 一 a b s t 阳c t c h u n ga n dr o s sp r o d u c eac o n j e c t u r e ：t h es u f f i c i e n ta n dn e c e s s a r yc o n d i t i o nf o rt h r e e - s t a g ec l o sn e t w o r kc ( n ，m ，r ) t ob er e a r r a n g e a b l en o n b l o c k i n gi sm 2 n 一1i fe a c h c a l lh a sw e i g l l tc h o s e nf r o mag i v e ns e to f 七w e i g h t s f u r t h e r m o r e ，t h ec o n j e c t u r e s e e h i st ob et r u en o to n l yi nt h ed i s c r e t eb a n d w i d t hc a s eb u ta l s oi nt h ec o n t i n u o u so n e i nt h i ss e c t i o nw es h o wt h a tt h ec o n j e c t u r eo fc h u n ga n dr o s sh o l d sn o to n l yi nt h e d i s c r e t eb a n d w i d t hc a s eb u ta l s oi nc o n t i n u o u so n ef o r r 警一百2 3 t h e f o u r t h c h a p t e r i n v e s t i g a t e s t h e w i d e - s e n s e n o n b l o c k i n g p r o p e r t y o f t h r e e s t a g e c l o sn e t w o r ki nm u l t i c a s te n v i r o n m e n t i nt | l ef i r s ts e c t i o nw ei n t r o d u c et h em u l t i c a s t m o d e li nd e t a i l w h i l ei nt h es e c o n ds e c t i o nw e p r e s e n ts o m ek n o w nr e s u l t sa b o u tt h r e e - s t a g e c l o sn e t w o r k y a n ga n dm a s s o ns h o w e dt h a tt h r e e s t a g ec l o sn e t w o r kc ( n ，m ，r ) 1 5 舢1 6 。笛w 出姗8 8 “。蒯溅n g m ：卿m i 。i n ，) 一1 ) ( 蚪r l z ) ，w 胁z i sap o s i t i v ei n t e g e r f r o mt h i sr e s u l tt h e yo b t a i n e dab o u n do fma saf u n c t i o no fna n d rb yg i v i n gaf i x e dv a l u et oz h o w e v e r , t h eb o u n dh a sad e f e c t , i e t h eg i v e nv a l u et o z m a y n o t b e l o n g t o t h e i n t e r v a l 【1 ，m i n n l ，r ) 1 i n t h i r ds e c t i t n o f t h i sc h a p t e r w e s h o wt h a tt h r e e s t a g ec l o sn e t w o r kc ( n ，m ，r ) i sm u l t i c a s tw i d e - s e n s en o n b l o c k i n gi f m m i n ( n 一1 ) ( z + t 1 x ) ，w h e r ez i sap o s i t i v ei n t e g e r o u rr e s u l ti sb e t t e rt h a ny a n g a n dm a s s o n sf o rt h a ti tl o o s e n st h er e s t r i c t i o nt oz a n d j u s tf o rt h a tt h eb o u n do fz i sc a n c e l e d w es a yt h a tt h eb o u n do fma saf u n c t i o no fna n drg i v e nb yy a n ga n d m a s s o ni sr i g h t f u r t h e r m o r e ，w ec a ni m p r o v et h eb o u n db ya n a l y s i s t h ef i f t hc h a p t e rc h i e f l ys t u d i e st h en o n b l o e k i n g n e s so ft h r e e s t a g ec l o sn e t w o r k i nm u l t i r a t em u l t i c a s te n v i r o n m e n t t h ef i r s ts e c t i o ni n t r o d u c e st h em u l t i r a t em u l t i c a s t m o d e li nd e t a i l ，w h i l et h es e c o n ds e c t i o np r e s e n t ss o m ek n o w nr e s u l t so i lt h r e e s t a g e c l o sn e t w o r k t h em u l f i r a t em u l t i c a s tm o d e li st h em o s tc o m p l i c a t e dc a s ea n dh a r d t oa n a l y z e s o ，v e r yl i t t l ei sk n o w nf o rt h i sc a s e i nt h et h i r ds e c t i o no ft h i sc h a p t e r w ei n v e s t i g a t et h ew i d e - s e n s en o n b l o c k i n gp r o p e r t yo ft h r e e s t a g ec l o sn e t w o r ki nt w o m o s ts i m p l em u l t i r a t em u l t i c a s tm o d e l ：1 - r a t em u l t i c a s ta n d2 - r o t em u l t i c a s te n v i r o n - m e n t k i ma n dd ug a v ear e s u l ta b o u tm u l t i r a t em u l t i c a s tr e a r r a n g e a b l en o n b l o c k i n g c i o sn e t w o r ki nt h ec o n d i t i o no fr e s t r i c t e db a n d w i d t h i nf o u r t hs e c t i o nw es h o wt h a t t h e ym a d eas m a l le l t o ri nt h ec o u n t ，a n dc o r r e c ti t f u r t h e r m o r e ，o n rr e s u l ti m p r o v e k i ma n dd u s k e yw o r d s ： s w i t c h i n gn e t w o r k , t h r e e - s t a g ec l o sn e t w o r k ，s t r i c t l yn o n b l o c k i n g ， 一一 a b s t i a c t w i d e s e n s en o n b l o c k i n g ，r e a r r a n g e a b l en o n b l o c k i n g ，c o l o r i n g ，s u mg r a p h ，s u mn u m b e r 一v 一 第一章绪论 第一章绪论 近几十年来，组合优化和图论得到了迅猛地发展，在运筹学、计算机科 学、管理科学和应用数学等诸多学科都发挥了重要的作用。它们在社会生产和 生活中有着广泛的应用，已经渗入到人们生活的方方面面。图论中存在着很多 的组合优化问题，同时图论中的一些理论和方法又为解决组合优化问题提供了 一种很好的方法和思路，它们是相辅相成的。 本文所研究的开关网络问题也是一种组合优化问题。随着数字和信息技术 的不断发展，开关网络越来越深入到人们生活的中心，在许多领域发挥了重要 的作用，比如说通讯、数据传输、电话会议、广播、卫星传送等等。本章将对 本文所涉及的组合优化和开关网络的一些基本知识和研究成果作逐一介绍。至 于图论中的一些基础知识和研究成果我们将在下一章中介绍。 1 1 组合优化问题与算法 组合优化问题又称离散优化问题，是一类重要的优化问题。尽管某些组合 优化问题有着悠久的历史渊源，被费马( f e r m a t ) 、欧拉( e u l e r ) 等众多著名 的数学家研究过，但作为运筹学的一个独立分支而发展壮大起来还是近儿十年 的事。随着计算机科学、管理科学和现代化生产技术等的日益发展，这类问题 与日俱增，越来越受到运筹学、应用数学、计算机科学及管理科学等诸多学科 的高度重视。随着人们对组合优化问题的研究的不断深入，现在这类问题和研 究方法已在网络通信、物流管理等诸多领域发挥了重要作用，对人们的生产、 生活产生了重要的影响，显示了它的巨大的生命力和发展前景。 定义1 1 1 ：组合优化问题7 r 是一个极小化问题，或是一个极大化问题，它由述 三部分组成： ( 1 ) 实例集合； ( 2 ) 对每一个实例，有一个有穷的可行解集合s ( ，) ； ( 3 ) 目标函数，它对每一个实例j 和每一个可行解盯s ( ，) ，赋以一个有理 数f ( i ，仃) 如果7 1 是极小化问题( 极大化问题) ，则实例，的最优解为这样一个可行 解c r l s ( j ) ，它使得对所有的盯s ( ，) ，都有f ( t ，矿) f ( i ，盯) ( ，( j ，矿) 第一章绪论 f ( 1 ，口) ) 常见的组合优化问题有分划问题( p a r t i t i o n ) 、排序问题( s c h e d u l i n g ) 、 装箱问题( b i np a c k i n g ) 、背包问题( k n a p s a c k ) 、指派问题( a s s i g n m e n t ) 、 旅行售货商问题( t r a v e l l i n gs a l e s m a np r o b l e m ) 、斯坦纳最小树问题( s t e i n e r m i n i m a lt r e e ) 等网络中的组合优化问题还包括最短路问题( s h o r t e s t p a t h ) 、最小生成树问题( m i n i m a ls p a n n i n gt r e e ) 、最大流问题( m a x - f l o w p r o b l e m ) 、最小费用流问题( m i n - c o s tf l o wp r o b l e m ) 等 尽管大部分组合优化问题可以转化为整数规划( 或混合整数规划) 问题， 但由于求解整数规划问题的工作量很大，而且没有一个普遍的解法较快地得到 最优解，因此人们根据各个问题自身的特殊的组合结构，有针对性地来研究其 性质，试图找到该问题的求解方法 定义1 1 2 ：算法是指一步步求解问题的通用程序，它是解决问题的程序步骤的 一个清晰描述。本文中仅涉及确定型算法，即算法从前一步到后一步的运行是 由当时状态唯一确定的。如果存在一个算法，它对组合优化问题7 r 的每个实 例j r ，在有限步后，一定可得到该实例的关于7 r 的提问的答案，那么我们就称 该算法解此组合优化问题7 r 。 定义1 1 3 ：对于一个组合优化问题7 r ，如果给定任意一个实例，算法a 总能 找到一个最优解矿，那么就称a 为最优算法( o p t i m a la l g o r i t h m ) 。 详细的组合优化知识参见【7 7 。在此，我们只对本文研究的开关网络问题 作一介绍 1 2 开关网络问题 开关网络( s w i t c h i n gn e t w o r k ) 起源于电话连接的需求。在还没有多少电 话时，任意两部电话之间都会直接铺设一条线路。但是，随着电话数目的与日 俱增，这些线路的传输费用就越来越负担不起了。这时，“开关”或“转换” ( s w i t c h i n g ) 的概念就应运而生了。因而，人们把一个给定区域内的每部电话 都连接到一个“转换”中心，连接这些电话的线路在这里通过一个网络相互连 接，这个网络就称为开关网络。后来，开关网络又应用于并行计算机来连接一 组带有记忆的处理器。目前，开关网络又有了许多其他的应用，比如说数据传 一2 一 第一漳绪论 输、电话会议、广播、卫星传送等等。它与人们的生产、生活息息相关，密不 可分。可以说，人们对开关网络的需求正在迅速的增长。 一个开关网络既可以连接一群用户，称为单边网络( 1 - s i d e dn e t w o r k ) ，也 可以连接两群用户，称为双边用户( 2 s i d e dn e t w o r k ) 。注意到通过在双边网络 的两边放置相同的实体集合，一个双边网络可以用作一个单边网络，尽管从转 换的角度来讲这样做是不经济的。若不做特别说明，本文所说的网络都是指双 边网络。 开关网络的基本组成部分是纵横转换器( c r o s s b a rs w i t c h ) ( 偶尔也会使 用其他的转换器) 和链接( 1 i n k ) 。链接是用来连接这些转换器的。我们把纵 横转换器简记为转换器。一个具有n 个入口( i n p u tp o r t ) 和m 个出口( o u t p u t p o r t ) 的转换器，记为x 。，它是交叉点( e r o s s p o i n t ) 的一个矩形排列，其尺 寸( s i z e ) 是几m 的。这也是最简单的一种开关网络，如图i 1 所示。 n i n p u t p o r t s mo u t p u tp o r t s 图1 i一个n m 转换器五。 大多数开关网络是按层来组织的，每一层由一列转换器组成。除最后一层 外，每层的每个转换器的出口都连接到下一层的一个转换器的入口。某些转换 器是连接到外部世界的。对双边网络来讲，这种连接到外部世界的转换器分为 两类，一类是第一层的转换器，称为输入转换器( i n p u ts w i t c h ) ，另一类是最 后一层的转换器，称为输出转换器( o u t p u ts w i t c h ) 。输入转换器上的连接于外 部世界的链接称为网络的输入( i n p u t ) ，而输出转换器上的连接于外部世界的 链接称为网络的输出( o u t p u t ) 。他们有时也称为外部链接( e x t e r n a ll i n k ) ，而 其他的链接称为内部链接( i n t e r n a ll i n k ) 。 一3 一 第章绪论 在一个s 层网络中，这些转换器被排列成s 列，每列称为一层。 有时不对s 作特别说明，网络就称为多层互联嘲( m u l t i s t a g ei n t e r c o n n e c t i o n n e t w o r k ) 。同一层的转换器具有相同的尺寸。只有在相邻的层之间才会存 在链接。第i 层的转换器和第i + 1 层的转换器之间的链接是从前者的出口 到后者的入口的。第一层( 最后一层) 的转换器是输入( 输出) 转换器， 其入口( 出口) 是网络的输入( 输出) 。常见的网络有c l o s 网络、b e n e s 网 络、c a n t o r 网络、l o g d ( n ，m ，p ) 等。本文主要研究的是三层c l o s 网络，我们将 在下一节中对其进行详细说明。目前对其他的常见网络的研究也很多，参见 【9 ；1 7 ；1 8 ；3 9 ；4 2 ；4 3 ；4 5 ；5 0 ；6 0 ；6 1 ；6 9 。 开关网络具有一个输入集合和一个输出集合，前者产生请求( r e q u e s t ， 或c a l l ) ，通过网络连接到后者。理论上讲，一个输入可以请求连接任意一个 输出，正如一个电话可以打给任意其他的电话。因此，网络必须提供从任意一 个输入到任意一个输出的通路。更进一步，一旦一个请求被连接( 或实现) ， 它就需要持续一段时间，在此期间其他的输入可能会产生它们自己的请求。一 个开关网络所要做的就是同时连接这些请求，其方式会因为某些终端的挂断和 其他一些终端产生新的请求而不断的变化。从经济的角度来讲，网络通常不会 给一个输入到一个输出提供一条专用的路线。因此，一个请求的连接可能会阻 塞另外一个请求的连接，即网络无法为另外这个请求提供一条通路，使得该通 路上的链接都没有被使用。c l o s ( 1 9 5 3 ) 取得了一个令人惊异的成就，他通过 一些精巧的设计，证明了存在不阻塞网络，但是它们的硬件却比专用线路构成 的网络所使用的硬件要少得多。 对任意一个请求，如果存在一条路连接它，而且在这条路上没有链接被 其他的连接路所使用过，那么我们就称这个请求是可实现的( r o u t a b l e ) 。开 关网络的不阻塞性质一般可分为三类：在一个网络中，如果不管已经存在 的请求是怎样连接的，一个新的请求总是可实现的，则这个网络称为严格 不阻塞的( s t r i c t l yn o n b l o c k i n g ) ；只要所有的请求都是按照一个给定的算法 来连接的，那么一个新的请求也总是可实现的，这时我们称这个网络是广义 不阻塞的( w i d e s e n s en o n b l o 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 ) 。显然，一个严格不阻塞网络必是一个广义不阻 塞网络，一个广义不阻塞网络也必是一个可重排不阻塞网络 对电话网络来讲，或许“不阻塞”这个目标有些高。这是因为并不是所有 一4 一 第。章绪论 的用户会同时打电话，故即使是一个阻塞的网络也可满足大多数的实际需求。 另外，当一个请求被阻塞时，用户通常会接受现状，并过一段时间会重试。但 是，许多其他应用对阻塞就有比较低的忍受力，而且阻塞的费用也比较昂贵。 比如说，军事或者高安全性网络通常要求不阻塞：在数据网络中如果被阻塞的 数据非常重要，那么可能会导致很严重的问题。从另外一个方面来讲，随着硬 件费用的迅速降低，不阻塞网络越来越成为一个现实的选择，甚至有时是必要 的选择。尽管世界上的大多数网络仍然是阻塞类型的，并且已经建立一些有意 思的理论，但是本文只研究网络的不阻塞性质。在早期的电动机械( 或机电) 系统时代，由于交叉点( c r o s s p o i n t ) 是一个网络中最贵重的部分，因此交叉点 的数目是费用的一个很好的指标。我们在设计一个不阻塞网络时就要使得交叉 点的数目尽可能的少。但是，随着许多新技术( 比如，超大规模集成电路) 的 不断发展，交叉点的费用不再是一个主导因素，但是交叉点的数目仍然是网络 性能的一个普遍的测量标准，这是因为它对于其他一些重要特征还具有许多优 点，比如一个网络的物理大小和控制复杂性，或者当一个网络被剖分成薄片时 所需要的端口的数目。我们定义网络的费用为该网络中交叉点的数目。我们的 目的就是要建立一种网络，使得它既能满足不阻塞的性质，又能尽可能的减少 网络的费用。 1 3 三层c l o s 网络 三层c l o s 网络被认为是最基本、最常用的多层互联网，它广泛地应用于数 据传输、并行计算系统来给两部分提供连接。 三层c l o s 网络( t h r e e s t a g ec l o sn e t w o r k ) ，记为e ( m ，r 1 ， 1 7 1 , ，n , z ，r 2 ) ，是一 个三层互联网，它的第一层由7 1 个n 1 1 7 1 的转换器组成，称为输入层( i n p u t s t a g e ) ，第二层由m 个nxr 2 的转换器组成，称为中间层( m i d d l es t a g e ) ，第 三层由您个mxn 2 的转换器组成，称为输出层( o u t p u ts t a g e ) 。每个输入层转 换器和每个中问层转换器之间有且仅有一个链接相连。类似地，每个中间层转 换器和每个输出层转换器之间也是有且仅有一个链接相连。但是，输入层转换 器和输出层转换器之间没有链接。若7 1 = 您，礼1 = n , z ，则三层c l o s 网络称为 对称的三层c l o s 网络，记为c ( n ，m ，r ) 。图1 2 所示即为c l o s 网络c ( 3 ，4 ，2 ) 。 对称的三层c l o s 网络一开始是为纯粹的线路转接( c i r c u i ts w i t c h i n g ) 而设计 的，它必须在一个请求的出发点和目的地之间建立一条通路，而且这条通路上 的所有链接都不能被其他的请求使用过。本文主要以对称的三层c l o s 网络为研 一5 一 第章绪论 究对象。 图1 2 对称的三层c l o s 网络c ( 3 ，4 ，2 ) 在上一节中已经提到过，我们的目的是要建立一个网络，使得它既能满足 不阻塞的性质，又能尽可能的减少网络的费用。而网络的费用是该网络中交叉 点的数目。对于三层c l o s 网络来讲，它的交叉点的数目是r 1n 1m + m r l 您+ i 2n 2m = m ( r 1 竹1 + r 1r 2 + r 2 竹2 ) 。所以，三层c l o s 网络的费用是跟m 的取 值是成正比的。因此，如果要使得该网络的费用尽可能的减少，那么尽量减 小m 的值就是一个很好的方法。所以，我们的问题就是确定最小的m ，使得 对所有的m m ，c ( 扎，m ，r ) 是严格不阻塞的( 或广义不阻塞的，可重排不阻 塞的) 。 到目前为止，已经有很多人研究过三层c l o s 网络。在经典的线路转 接中，对于严格不阻塞，c l o s 【1 6 已经证明m + = 2 n 一1 ，而对于可重排 不阻塞，b e n e 【2 】证明了m + = n 。尽管对于广义不阻塞m + 还没有完全 确定，c h a n g 【1 2 】等人证明了对几乎所有的已经研究过的算法，都有m = 2 n 一1 ，除了c ( n ，m ，2 ) 在“p a c k i n g ”算法下有m = 协l 2 j ( 1 2 ；3 】) 。但是， 我们还不确定对于r 3 ，若m 1 3 n 2 i ，c ( n ，m ，r ) 在“p a c k i n g ”策略下 是否是广义不阻塞的。y a n g 和w a n gf 7 6 】证明了，如果m 1 ( 2 一是i ) 州， 则c ( n ，m ，r ) 在“p a c k i n g ”策略下是广义不阻塞的。 随着科学技术的不断发展和人们需求的日益提高，在经典的线路转接的基 础上，又出现了许多新的模型。我们知道在经典的网络转接理论中，连接转换 器的外部链接和内部链接在任何时候都只能由一个电话会话来使用。但是随着 数字技术的不断发展，我们要处理许多具有不同带宽要求的通信，比如说声 音、传真、录像等。由此产生了更为一种优美的模型，我们称之为多速模型。 在这种新的模型中，只要一个链接的负载不超过其容量，就允许多个连接共享 一条链接。经典的线路转接模型和多速模型中的请求都是一对一的。但是除了 一6 一 第一章绪论 前面所说的这种一对一的请求外，还产生了从一个设备到多个设备的数据传 输。许多网络应用( 例如，通信网络中的音频或视频多媒体会议、远程教育 等) 展示了对这种多点传送通信方式的需求。在多点传送模型中，一个输入可 以请求连接到多个输出。同时，这种模型跟经典的线路转接模型也有相同的性 质，就是每个链接在任何时候只能被一个请求所使用。如果我们把多点传送模 型和多速模型结合起来，得到的模型将会更加符合实际的需要，这样一种模型 称为多速多点传送模型。在多速多点传送模型中，一方面，个输入可以请求 连接到多个输出；另一方面，只要一个链接的负载不超过其容量，就允许多个 连接共享一条链接。我们将在第3 5 章中分别介绍这三种模型。 1 4 论文概述 本文主要研究开关网络中的三层c i o s 网络的广义不阻塞和可重排不阻塞 性质。在研究广义不阻塞性质时，我们通常是先给出一个策略( 或算法) 来 。安排每个到达的请求的线路，然后分析在该策略下，使得三层c l o s 网络是广 义不阻塞的m 的最小值。而对于可重排不阻塞问题，图论中着色( c o l o r i n g ) 理论是解决该问题的一个好的方法。在经典的线路转接中，人们就是通过把 三层c l o s 网络的可重排不阻塞问题转化为一个二分图上的着色问题，从而得 到1 3 节中所提到的结果。因此，在第二章中，我们将给出图论中的一些基础 知识和我们得到的一些结果。 在第三章中，我们研究三层c l o s 网络在多速情况下的广义不阻塞性质和 可重排不阻塞性质。在第3 1 节中我们将详细介绍多速模型，而在第3 2 节 中我们将介绍三层c l o s 网络在多速模型下的一些已知结果。本章第3 3 节主 要研究在只有两种速率b 和b 的情况下三层c l o s 网络的广义不阻塞性质。由 于以前人们对两速c l o s 网络的研究并不包括b 1 2 的情形。因此，本文针 对b 1 2 的情形，我们将给出一个最好的预留方案来实现请求。第3 4 节 主要研究三层c l o s 网络在多速环境下的可重排不阻塞性质。c h u n g 和r o s s r 1 7 给出了一个在离散带宽情形下的猜想：若每个请求的权重取自一个给定的 具有七个重量的集合，则m + 2 n 一1 。l i n 【4 7 】等人证明了这个猜想在受限制 的离散带宽情形下是正确的，即每个请求的权重取自集合 l p l m p 1 2 m + 1 p k ，其中对i = h + 1 ，后一1 有，a 是p i + 1 的整 数倍。人们猜测这个猜想不仅对离散带宽是正确的，而且对连续带宽也是正确 的。本文将证明当r 警一警时，c h u n g 和r o s s 对多速c l o s 网络的可重排性 一7 一 第一章绪论 的猜想在离散带宽情形和连续带宽情形下都是正确的。 第四章主要研究三层c l o s 网络在多点传送环境下的广义不阻塞性质。 在第4 1 节中我们将详细介绍多点传送模型，而在第4 2 节中我们将介绍 三层c i o s 网络在多点传送模型下的一些已知结果。y a n g 和m a s s o n 【7 5 证明 了，如果m n f m 一1 ) 扛+ r l z ) ，则三层c l o s 网络c ( 礼，m ，r ) 是 l a r m i n ( n 一1 ) + r x z ) ，则三层c l o s 网络c ( n ，m ，r ) 是多 点传送广义不阻塞的，其中z 是正整数。我们的结果放宽了对z 的限制，从 而比y a n g 和i a s s o n 的结果要好。同时，由于z 没有了取值范围的限制，从 而y a n g 和m a g s o n 给出的以竹和r 的函数为表达式的m 的界限是正确的。经过 进一步的分析，我们可以改进了他们的这个界限。 第五章主要研究三层c l o s 网络在多速多点传送环境下的广义不阻塞性质 和可重排不阻塞性质。在第5 1 节中我们将详细介绍多速多点传送模型，而 在第5 2 节中我们将介绍三层c l o s 网络在多速模型下的一些已知结果。由 于多速多点传送极其复杂，分析起来极为困难，因此，到至今为止所得结论 仍很少。一速多点传送和两速多点传送是最简单的两种多速多点传送模型。 在第5 3 节中我们主要研究三层c l o s 网络在这两种模型下的广义不阻塞性 质。k i m 和d u 【4 4 】给出了一个限制的离散带宽条件下的关于多速多点传送可重 排不阻塞c l o s 网络的结果。在第5 4 节中我们将说明他们的这个结果在计数上 的一点错误，并加以纠正，但是得到结果的条件却比k i m 和d u 的松一些。 一8 一 第一二章图的基本知识和若一1 ：结果 第二章图的基本知识和若干结果 在上一章中，我们已经知道图论可以为研究组合优化问题提供一个很好的 思路和方法。更进一步，我们在研究开关网络问题也的确用到了图论中的一