（运筹学与控制论专业论文）不阻塞交换网络中的一些新问题.pdf

摘要 摘要 在这篇论文中，我们辛要考虑了以下四个问题第一个问题是 以b 玎1 ( n ，) 网络为基础构造严格不阻塞网络k o l m a n 在b e n e s 网络的基础上 通过只保留特定的输入和输出构造了一个严格不阻塞网络我们将此方法扩展到 一般的b 圩1 ( n ，纠网络当k = n 一1 时，l ! l j b e n e s 网络，我们将k o l m a n 的下界1 2 n 提高为l 加当= o 时，我们就得到了一个自路由网络，而且他在广播通信下电 是严格不阻塞的第二个问题是关于l o g d ( n ，m ，v ) n n 在f c a s t 条件下严格不阻 塞的条件此问题主要的难点在于对输出被占用情况的仔细分析我们的结果包 含h w a n g 在点到点通信下的结果和k a b a c i n s k i 在广播通信下的结果第三个问题 是关于在多频模型- f l o g d ( ，m ，p ) 网络的严格不阻塞条件，我们从两个方面扩展 t c h u n g 芹w r o s s 的结果茸先，我们从c a n t o r 网络扩展到更一般的l o g d ( n ，m ，p ) 网 络其次，我们考虑l i n k 具有不同容量，而不仅仅是u n i f o r m 的情形第四个问题是 关于以l o g d ( n ，m ，p ) 网络为基础的多频可重排网络的构造我们将h u 等提出的单 调路由法应用 ：l o g a ( n ，m ，p ) 网络这是第一个以l o g d ( n ，m ，p ) 网络为基础的多 频可重排网络 关键词：严格不阻塞，宽性不阻塞，可重排，交换网络，多频，广播，一广播 a b s t r a c t a b s t r a c t s w i t c h i n gn e t w o r k sh a v eb e e nw i d e l yu s e di nt e l e c o m m u n i c a t i o n ，d a t ac o m m u n i c a t i o n ，s a t e l l i t ec o m m u n i c a t i o na n de t c t h en o n b l o c k i n gc o n d i t i o no fs w i t c h i n g n e t w o r k sa r o u s e sg r e a ti n t e r e s t ss i n c ei tc a ns i g n i f i c a n t l yr e d u c et h eh a r d w a r ec o s t s e v e r a ln o n b l o c k i n gc o n c e p ma r ep r o p o s e d ，i n c l u d i n gs 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 e n o n b l o c k i n ga n dr e a r r a n g e a b l e s e v e r a ls w i t c h i n gn e t w o r k sh a v eb e e nw i d e l yu s e d ， i n c l u d i n gc l o s ，s e l f r o u t i n gn e t w o r k ，b e n e s ，c a n t o r , b 玎1 ( n ，k ) a n dl o g d ( n i ，p ) i nt h i sd i s s e r t a t i o n ，w es o l v e df o u rp r o b l e m s ，f i r s t l y ，w ec o n s u u c t e ds t r i c l t yn o n b l o c k - i n gn e t w o r k sb a s i n go nb r d - 1 ，m ) k o l m a nc o n s t r u c t e dap o i n tt op o i n ts t r i c t l y n o n b l o c k i n gn e t w o r kb a s i n go nb e n e sn e t w o r kb yk e e p i n go n l yas m a l lp o r t i o no fi n p u t sa n do u t p u t s w ee x t e n d e dh i sm e t h o dt og e n e r a lb 玎1n ，k ) w h e nk = n 一1 ，i t i sb e n e sn e t w o r ka n dw ei m p r o v e dh i sl o w e rb o u n dt o1 肪w h e nk = 0 ，i ti sas e l f r o u t i n gn e t w o r k s e c o n d l yw eo b t m n e dt h en e c e s s a r ya n ds u f f i c i e n tc o n d i t i o n sf o r l o g d ( n ，m ，p t ob e | 一c a s ts t r i c t l yn o n b l o c k i n gf o r e v e r y a n dt h u sc o v e r e d t h ep o i n t t o - p o i n tc a s e ( ，= 1 ) a n dt h eb r o a d c a s tc a s e ( ，= n ) a ss p e c i a lc a s e s t h i r d l y ，w e s t u d i e ds t r i c t l yn o n b l o c k i n gu n d e rm u l t i r a t em o d e l a sw ek n o w ，c a n t o rn e t w o l ki s j u s t l o g d ( n ，n 一1 ，p ) a n dc h u n ga n dr o s s sr e s u l tw a so nc a n t o rn e t w o r ka n d i tw a sa l s o u n d e rt h eu n i f o r l t lm o d e l t h u sw ee x t e n d e dt h e i rr e s u l tj nt w od i r e c t i o n s w et r i e dt o g e tag e n e r a lr e s u l tf o rl o g d ( ：q 、m ，p ) ，m = 1 ，2 ，n la tf i l s t t h e nw ec o n s i d e r e d t h es i t u a t i o nw h e r el i n k sh a v ed i f f e r e n tc a p a c i t i e s f o u r t h l y , w es t u d i e dt h em u l t i r a t e s t r i c l yn o n b l o c k i n gc o n d i t i o no fs w i t c h i n gn e t w o r k t h ec u r r e n tr e s e a r c ho nm u l t i r e t e r e a r r a n g e a b l en e t w o r k sa r ea l if o c u s e do n3 - s t a g ec l o sn e t w o r k w ec o n s i d e r e du s i n g h u sm e t h o do nl o g d ( n ，m ，p ) u s i n gt h em e t h o do fa n a l y z i n g ，- c a s t ，w ec o n s t r u c t e d a r e a r r a n g e a b l en o n b l o c k i n gn e t w o r kb a s i n go nl o g a ( n ，m ，p ) k e yw o r d s ： s 【i c t i 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 e ，s w i t c h i n gn e t w o r k ，m u l t i r a t e ，b r o a d c a s t ，f c a s t 一一 第章绪论 1 1 问题的起源 第一章绪论 交换网络在通信网络，数据交互，卫星通信，光纤通信等诸多方面都获得了广 泛应用交换网络首先是被应用于连接需要进行通话的电话用户当用户人数比 较少时，我们可以将每两个用户都用电线连接起来但当用户人数激增时，如果仍 然使用完全连接的方法，在电路和传输上的花费就变得难以忍受因此，我们需要 采纳交换网络。c l o s 6 】首先提出如果在某些数学理论的指弓l 下进行网络设计，与 以前建立完全连接的网络相比，我们可以极大的降低硬件花费我们将简要介绍 一些基本的概念更详细的解释和定义请参昭, , h w a n gf 1 0 】 我们假设网络中有一组输入终端和一组输出终端每个输入都可以产牛一个 请求，并通过网络连接到h 的输出理论上一个输入可以要求连接到任何一个输 山，就好比一个电话可以要求连接到任何地方一个交换网络最基本的构成的单 元叫做c r o s s b a r , 或者s w i t c h 一个( p 口) 一c r o s s b a r 有p 个输入和q 个输出，在图1 1 中 画出了一个c r o s s b a r 在一个有s 个s t a g e 的交换网络中，许多c r o s s b a r 被按顺序排成s 列，而每一列就被称为一级( s t a g e ) 记s t a g e 为第i 级，i = 1 ，s 有时s 并没有被 明确指明这个网络就被称为多级内联网( m i n ) 在同一级中的c r o s s b a r 都有同样的 尺寸大小第一级被称为输入级，最后一级被成为输出级连线只存在于相邻的两 级之间设s t a g e j ，即第i 级，含有n 个( n lx ) - c r o s s b a r 因此对于t = 1 ，r 一1 ， 我们有n m 。= r i + l n 成立，在下一节中将介绍以下几种非常重要的交换网络： 3 级c l o s 网络，自路由网络，b e n e s 网络，c a n t o r 网络，b y _ 1 ( n ，m ) $ u l o g d ( j ，7 1 7 , ，p ) 网 络 1 2 各种常用交换网络 我们用记号x 。v 来表示( zx ) 一c r o s s b a r 令k b x d 表示2 一s t a g e 络，其 r # s t a g e l 由c 个x 。6 组成，s t a g e 一2 由b 个x “组成，而且两级之问的连接方式是 完全图令 。k b ，x 耐，托。 表示3 - s t a g e n 络，其 s t a g e l 包含c 个x 。b ，s t a g e 2 包 含b 个x 。d ，s t a g e 一3 包含d 个x k ，且两级之间的连接方式是完全图这些记号是占 先由c a n t o r 【4 】提出的，并且被经常使用描叙多级内联网图1 2 中画山了两个网 络 第一章绪论 p 图1 1 0 g ) - c r o s s b a r 图1 2 ( a ) 恐tx 弱2c o ) 【x a a ，x 4 4 ，x 3 3 】 c l o s 6 1 首先介绍7 3 - 级c l o s 网络：g ( n 1 ，r 1 ，m ，n 2 ，t 2 ) 第一级副输入级 有r 1 个( 扎1 x m ) 一c r o s s b a r , 笫三级即输出级有r 2 个( mxn 2 ) 一c r o s s b a r 中i r j 一级则 有m 个( r l r 2 ) 一c r o s s b a r 令 2 l = 礼2 = n ，r l = 7 2 = r ，我们就可以得到对称c l o s 网 络c ( n ，m ，r ) 图1 3 中的就是c ( 2 ，3 ，4 ) 3 - s t a g ec l o s n 络的传统记号是【五u 。，墨m ，葺。】m = n l r l 为输入的数h ， n 2 = 扎2 r 2 为输出的数1 = t 现在，我们来看看b e n e s n l 绍- 2 1 对于上文中的i 4 q x 。b ，x 商x k l ，我们【乜 可以用一个网络来代替中问的c r o s s b a r 例如，( 2 n 1 ) 一s t a g eb e n e s 网络就是如下 定义的：b 1 只是一个( 2x2 ) - c r o s s b a r , b 2 = 【x 2 2 ，x 2 2 ，x 2 2 ，b 。，n l 其实就 是玩= 2 2 ，最- i ) 恐2 】图1 4 中画出了b 1 ，玩，岛 一2 一 第漳绪论 ( a ) 图1 3c ( 2 ，3 ，4 ) ( c ) ( a ) b 1 ，( b ) b 2 ，( c ) b a 一个d n a r y 的网络( 多级内联网) 是指一个只使用d d 太小的c r o s s b a r 来构造 的网络因此在d n a r y 网络中每级都有相同数量的c r o s s b a r 设一个d n a r y 网络总i t - 有个输入，n = l o g d n 而术语“几乎d n a v y 网络”通常用来指除了输入级和输出 级比较特殊以外，其他部分全部是由d d 大小的c r o s s b a r 组成d - n a r yb e n e s 网络 的定义类似于b e n e s 网络，唯一的差别就是完全使用d d 大小的c r o s s b a r 白路由旨先是由l a w r i e f l 7 1 针对o m e g a 网络提出的它表示一个请求可以 在只告知输入和输出信息的条件下就可以被路由这类网络通常具有以下特 性：( 1 ) 它是一个n s t a g eb i n c r y n 络( n = l 0 9 2 n ) ( 2 ) 每个输入和输出之问有唯 一的路( 3 ) 令u 年t l v 为两个s t a g e 一c r o s s b a r , v j ( u ) 和v j ( u ) 分别表示u 和v 可以到达 i n s t a g e ( k + j ) 的c r o s s b a r 的集合那么这个网络具有( k ，j ) 好友性质，如果对于所有 t n u ，v ，嵋( u ) n 码( ”) = 0 或者k ( u ) = k ( ”) ，或简而言之，具有好友性质 自路由网络丰要有以下几种：o m e g a ，b a n y a n ，b a s e l i n e ( 见图1 5 ，图中画山 的都是b i n a r y l n ) 我们首先刻画一下这些网络的自路由性质自路由表现在可 一3 4l 图 b 第章绪论 以通过目的地的地址的n 个比特来决定路由对于o m 和b l 我们从输入路由到 输出在s t a g e ic r o s s b a r 中，如果输出地址的第i 个比特是o ，就将选抒走较上的输 出，1 则走较下的输出对于b y 我们从输出路由到输入在s t a g e 一们+ l i ) c r o s s b a r i = 1 ，n 中，在路由时，当且仅当输入地址的第i 个比特是0 ，我们将选择走较上 的输出，图1 5 画出了请求( o 叭，l o t ) 的路由 0 0 l ( & ) b 矗s e l j n c ( b l ) 0 0 1 ( c ) o m e g a ( o m ) 图1 5几个白路由网络 1 d l 以上的b i n a r y 网络可以很容易的被推广n d n a r y 情况，只要在上述条件( 1 ) 中 代替n = d “新网络由n 级x “构成 p a r k e r 【2 3 1 首先提出以上自路由网络在某种意义上其实都是等价的( 关于同 一级上的s w i t c h 的置换) ，而b e r m o n d ，f o u r n e a u 和j e a n m a r i ef 3 】也刻画了这个类 s h y y ；f t l l e a 2 4 考虑在b y 。后面增加k 个额外的级，并且这k 级恰好就是 从输入级开始的那级的镜像我们称这个具有k 个额外级的新得到的网络 为b y - 1 ( n ，) 我们可以看到以这种加额外级的方式下，b y _ 1 ( n ，k ) 可以被顺序 分解j 次，l js ，成为个b y 。m j ，一j ) 且每个b y - 1 ( n ，七) 的输入( 输出) c r o s s b a r 都有唯一的线路到达每个b y - 1 一j ，女一) ，如图虚线所示 很容易看到前文提到的晶实际上就是b y 一1 ( n ， 一i ) 如粜用f d d ) 一 c r o s s b a r 来代替网络中的( 2 2 ) 一c r o s s b a r 我们就得到t b y 丁1 ( 7 7 ，k ) l e a 8 阿先提 山l o g d ( n ，0 ，p ) ，随后s h y y f f 口l e a 【2 4 】将它推广l o g d ( n ，m ，p ) 网络l o g d ( 、”l ，p ) 也可以按照我们上面介绍的记号表示成 x l 。p ，b ，7 1 ( n ，m ) ，x ，。1 如果 一4 第一- 章绪论 图1 6 b y - 1 ( 4 ，2 ) 令m = n 一1 我们就得到- y l o g d ( n ，n 一1 ，p ) ，而这就是c a n t o r 唰络图1 7 中表 示的就是l 0 9 2 ( 8 ，1 ，3 ) 1 3 不阻塞的定义 在介绍了几种非常重要的内联网之后，我们将简单的给出几种不阻塞性质的 定义，在后续部分我们将给山在各种不阻塞条件下比较经典的结果当我们醣一 个网络具有某种不阻塞的性质时候，都是针对某种特定的通信丽言的，因此，在介 绍不阻塞定义之前将先给出各种通信模型的定义 在一个广播网中，每个输入都可以被连接到任何数量的输出，只要这些输山 没有被其他的输入所使用有列我们会给输出的数量加上一个上限，表示一个 输入最多只能同时被连接到，个输出那么此时，这个网络就叫做f e a s t 网络我 们称一个网络中的通信量为古典( c l a s i c c a l ) 的如果每条l i n k 只能承载一个请求，称 为多频( m u l t i r a t e ) 的如果每个请求都有一个权重，而每条l i n k 也有一个容量只要 它未使用的容量对于一个新请求而言足够，这条l i n k 就能承载这个新请求今后， 我们所提到的古典模型就是指其中的通信量是古典的，而多频模型则对应于多频 通信量在这里，我们要详细的解释一下l i n k 和p a t h 的概念当一个输入要求被连 接到另一个输出时，我们说一个请求产生了，l i n k 表示两级之削的连线p a t h ( 路) 则 表示能将两个请求连通并使之路由成功的l i n k 的集合显然，在古典模型中，两个 第一章绪论 图1 7 l 0 9 2 ( 8 ，1 ，3 ) 能同时共存于一个网络中的请求所对应的p a t l 一定没有公共的l i n k ，否则阻塞将 会发生在多频模型中则无此限制一条l i n k 只要有足够的容量，两个请求就可以 一个通过显而易见，在多频模型下研究不阻塞将更加网难 一个网络被称为严格不阻塞，如果不论当前网络的连接状态如何( 由以前的 请求连接组成的) ，当前的一个新请求都可以被连通另一种较弱的不阻塞性质被 称为可重排这是指任何一个合法的请求的集合在空闲无连接的网络上都可以 被连接实现宽性不阻塞是指当前的任何一个请求都可以依照特别指定的路由 算法来连接 1 4 论文概述 研究者已经在不阻塞内联网方面开展了许多工作，f h 同时也仍然有不少问题 有待解决 6 第章绪论 问题l ：以b y _ 1 ( 礼，) 为基础构造严格不阻塞网络 k o l m a n 构造了一个点到点的严格不阻塞网络并证明了上界为1 2 n 我们 证明了他所得到的上界1 2 n 可以被提高倍，即l n 同时我们猜测这个上界 其实还是一个必要条件我们已经在b 4 ，b 5 和口b 中构造成功，f h 是对于一般 的玩却很难证明另一方面，我们将把k o l m a n 的方法推广到b y - 1 ( n ，k ) 网络 k = 1 ，n 一1 更进一步的，我们希望他的方法可以适用于广播通信，因为广播 通信在实际应用中更受关注我们还将在自路由网络上得到相麻的结粜，因为自 路由是非常吸引人的性质 问题2 ：在f - c a s t 下，= 1 ，2 ，n ，l o g , i ( n ，m ，p ) 的严格不阻塞条件 h w a n g 和k a b a c i n s k i 分别在，= 1 和，= n h # l o g , t ( n ，m ，的严格不阻塞条 件而我们则得到一个对于一般大4 , 的充分必要条件他们文章中所用到的基本 方法仍然适用，但是我们必须对输出进行仔细的分组讨论 问题3 ：l o g a ( n ，m ，p ) 网络在多频模型下的严格不阻塞条件 在上一节中，我们已经提到了c a n t o r 网络实际上就是l o g a ( n ，n 一1 p ) 网 络而c h u n g 和r o s s 5 j 的结果就是在c a n t o r 网络上得到的，而且是在u n i f o r m 条 件下我们将向两个方面推广其结果首先我们对m = 0 ，1 ，n l ，得 i l j l o g , i ( ，m ，p ) 网络的严格不阻塞条件其次，我们在连接具有不同的容量时 也得到一个相麻的结粜m e l e n 的方法仍然可以继续使用 问题4 ：多频可重排网络 多频网的j 可重排阀题h 前是一个热点问题 h 当前的研究，比如【7 】1 9 】 2 i 】1 2 2 1 都是集中于3 级c l o s 网络的，我们将现有的方法推广至：l j l o g d ( ，m ，p ) 网络上显 然，这个问题将变得非常复杂因为在l o g a ( n ，m ，p ) 网中间的每个c o p y ，任何一 对输入和输出之间都存在好几条道路可以选择路由，而且还有其他的输入茅 j 输山 可以来阻挡我们将使用h u ，j i a ，d u 和h w a n g 9 的单调路由法 本文将以不阻塞网络的构造为丰第二章丰要是关于在古典模型下严格不阻 塞网络的构造在第三章，我们将得至i l 0 9 d ( ，m ，p ) 网络在多频模型下的严格不 阻塞条件在第四章中，我们将构造一个l o g a ( n ，m ，p ) 多频不阻塞网络 7 第_ 章古典模犁下的严格不耻塞内联网 2 1 介绍 第二章古典模型下的严格不阻塞内联网 第一章中，我们已经给出了严格不阻塞的定义现在我们来看一个c l o s 给出 的关于严格不阻塞的著名的定理 定理2 1 0 1 ：【五。，x v ：，x 。 是严格不阻塞的当且仅当m m o 且 n n 。= i v 2 , i f nl!，；曼。，i。 证明：不失一般性，假设新的请求是从i i 至l j 0 1 的，我们记这个请求为( 、0 1 ) 对 于与厶属于同一个s w i t c h 的那些输入，我们称为c o i n l e 4n 0 1 同属于一个s w i t c h 的 输出称为c o o u t p u t 先证明充分性显然，巩= 1 或者2 是足够的，因为仅仅 有m 饥f n l ，n 2 ，个请求能够被产生，而他们也可以通过不同的中间一级s w i t c h 来 路由进一步的，与j 1 和0 1 同属于个c r o s s b a r 的c o i n l e t 或者c o o u t p u t 能, 够与请 求( ，l ，d 1 ) 争夺中闸一级的s w i t c h ，i n 是他们总共能占用的s w i t c h 数h 为( 1 一1 ) + ( “2 1 ) ，因此中州一级只需要n l + n 2 1 个s w i t c h 就可以满足不阻塞 接下来，我们来证明必要性假定m 种当m 芝2 时，我们可以 有m i n m ，n 2 1 ，个c o i n l e t 4 每个都占用了一个中问一级s w i t c h 很显然，新的 请求被阻塞了n 2 n l 的情形的证明也类似而专n l 肌，n 2 n 1 吨那 些c o i n l e t 可以阻塞n 1 1 个中问一级s w i t c h ，而那些c o o u t p u t 可以阻塞， 2 1 个中 问一级s w i t c h ，且两者阻塞的s w i t c h 集合可咀不相交，那么新请求( ，1 ，0 1 ) 也被阻塞 了 2 - 2 基于b e n e s 网络构造严格不阻塞网络 k o l m a n 【1 6 】在b e n e s 匿 络的基础上构造了一个点到点的严格不阻塞网络他 是按照下面的步骤来做的占先，每个输入c r o s s b a r 和输出c r o s s b a r 都只有一个输 入和输出可以使用称这个被修改的b 。为( 1 ，1 ) 一占n 然后他讨论输f 1 c r o s s b a r 稀l 输出c r o s s b a r 当中只保留多大的比例可以使得这个被重构的网络是严格不阻塞的 8 第_ 章古典模型下的严格不阻塞内联网 他得到了一个上界为l 2 礼，下界为3 8 ( 注意到他称为b n 的网络实际上是e 竹+ 1 他所得的上界下界我们也都做山了相应的调整) 2 2 1 ( 1 ，1 ) 一b 。 我们假定存在有一个正整数“使得，对于n k ，如果我们只保留b 。当 中t 2 。的输入和输出，则得到的( 1 ，1 ) 一风就是严格不阻塞的，那么我们有 定理2 2 1 1 ：k = 2 0 + 1 - t - k + 1 对于k 0 证明：我们使用s h y 和k a 2 4 提山的c h a n n e lg r a p h 来分析很容易看到，在输入i 和 输出。之问的c h a n n e lg r a p h 是两棵完全相同二叉树组成的，且两棵树的叶子之间 存在一一对应图中给出的是风的c h a n n e lg r a p h 图2 1硗的c h a n n e lg r a p h 将这2 1 个输入c r o s s b a r 和2 1 个输出c r o s s b a r 按照2 进制进行编号，使得每个 输入输l 山都对应于一个n 一1 位的二进制数k l o m a n 证明了，如果两个输入的最 后f 位完全相同，而倒数第2 + 1 位不同，那么他们就可以到达同一条s t a g e = ( n f ) l i n k 我们将保留的i 2 输入和输出是前位编号完全一样的那些因此，我们可以 不看他们的前面位，而专注于后n k 一1 位易知，- 5 0 f n 一一3 时，恰好 有2 一o 。一2 个输入与输入i 的最后f 位相同，而倒数第f + l 位不同按照s h y 利l e a 的 分析方法，能阻塞j l i n k 的路可以阻塞1 2 j 的c h a n n e lg r a p h 那么在s t a g e - j 所能产牛 9 第_ 事古典模型下的严格不阻塞内联网 的总的阻塞就是 2 n - k - l - 2 丽1 ：土，。r o z n 一一3 2 k + 22 “一z o 。“。 那么从s t a g e 一( + 2 ) 开始一直到s t a g e - ( n 1 ) 合计阻塞 类似的，我们考虑从s t a g e 一竹开始一直到s t a g e 一( 2 n 一2 ) 的堵塞情况由b e n e s 网络的 对称性，可以得到阻塞也为! 高所一一，一n 。- k - 2 如果它小于l ，就说 明c h a n n e lg r a p h 中还有一条路可以供其使用此时有 n k 一2 2 k + 1 即得证 推论2 2 1 ：( 1 ，1 ) 一b ，。是严格不阻塞的，如果我们保留2 2 q 。7 ， 即约1 n 部分的输 入和输山( 按照以上定理中描叙的方式选取那些输入和输山) 证明：我们只要令= f l 0 9 2 n 1 一l ，那么 如= 2 i 0 9 2 州+ f l o g e n l n 2 2 2 猜想的上界 令“ 表示最大的n ，使得只要保留1 2 输入和输出就能使( 1 ，1 ) 一b 。为严格不 阻塞 猜想：“k = 靠 要证明此猜想，我们只要证明当扎= “+ 1 时，就存在一些不相交的路的集合， 将给定输入输出对之间的c h a n n e lg r a p h 完全阻塞而问题的重点就在于这些路必 须是不相交的要构造这些路并不容易，在这里我们先来看看= o 的情况 当= 0 时，k = 3 仍然假定待连接的请求是第一个输入到第一个输山的我 们在( 1 ，t ) 一反图中画出了6 条不相交的路为了简便，我们只画出路的一半，用黑 一1 0 一 警 | i h | 舭 州 i 第_ 章古典模犁下的严格不阻塞内联网 线表示 图2 2 ( 1 ，1 ) 一b 4i sn o ts t r i c t l yn o n b l o c k i n g 当= 1 时，我们同样可以看出( 1 ，1 ) 一b 7 不是严格不阻塞的因为图较复杂 我们此处不画出对于一般的k 的构造仍然有待解决 2 3 基于自路由网络构造严格不阻塞网络 如前所述，有一系列的自路由网络，包括o m e g a ，b a n y a n ，b a s e l i n e 和l 他们的逆 网络他们都有n = 2 “个输入和输出，且包含有n 个s t a g e ，每个s t a g e 有2 ”1 个2 2 的s w i s h p a r k e r 2 3 】旨先证明他们是等价的，而b e r m o n d ，f o u m e a u 年w j e a n m a r i e 【3 】刻画了这一个类 因为在自路由网络中，每对输入和输出之问只有一条p a t h ，显见他们不是 严格不阻塞的，甚至不满足可重排不阻塞，然而，通过去除一些输入和输出( 或 者使他们失效) ，我们就可以使之成为严格不阻塞的首先，我们使每个输入输 山s w i s h 都只保留有一个输入或者输山然后，对于剩下的输入刹输出我们只 保留1 2 2 ，整数k 待定，我们将说明如何具体选取那l 2 2 的s w i t c h ，并且对于给定 的1 3 找到最小的k 注意到，在除去一些输入和输入之后，剩下的网络仍然满足自路 由性质 我们可以从一组自路由网络中选取一个作为例子来说明，因为他们都是等价 的这里我们将以b a n y a n 网络为侧令b y ( n ) 表示一个n s t a g e 的b a n y a n 隔j 络 第_ 章古典模酗下的严格不阻塞内联网 2 3 1 主要结果 考虑b y ( n ) 用n 一1 位的二进制的序列来顺序表示输入输山级的c r o s s b a r , 从0 开始我们用b y 。( n ，) 来表示按照如下步骤从b y ( n ) 得到的网络： ( i ) 每个输入c r o s s b a r 都只保留一个i n p u t , 每个输出c r o s s b a r 只保留一个o u t p u t ( i i ) 保留输入c r o s s b a r 当中最后k 个比特都是0 的那些；保留输出c r o s s b a r 当中最 前k 个比特都是0 的那些 图2 3 中画出了b y + ( 5 ，1 ) 图中的数字就是输入和输出的编号 图2 3 b y 。( 5 ，1 ) 因为每个输入( 输山) c r o s s b a r 都只有一个输入( 输出) ，我们没有必要区分输 入( 输山) 和输入( 输出) c r o s s b a r 考虑从i 至1 , 1 0 的一个点到点请求那么从i 至l j o 的唯 一的路j 就e h n 一1 条l i n k 组成，记为l l ，l 2 ，l 。l 其中厶是s t a g e jl i n k 定理2 3 1 1 ：b y + ( n ，) 对于点到点连接是严格不阻塞的当且仅 2 k + 3 一1 2 一 一 一 j j o o j j j j ， 0 ， 叭 m 引 m 叫 m 洲 叭 川 叭 m m 第_ 章古典模犁下的严格不阻塞内联网 证明：不失一般性，假设当前的请求是从第一个输入c r o s s b a ri 出发，到达第个输 出c r o s s b a r0 充分性：因为i 中只有一个输入，没有其他的输入可以和它竞争l ，因为其 他2 女一1 个标号以n k 个0 开始的输入都已经被移去了，没有输入可以到达厶，对 于i n k 一1 而每条可以阻塞厶，对于某个i ，的输入必须从异于i 的输入出发， 且到达异于0 的输出因此，如果扎一七一1 = ( k + 1 ) + 1 ，那么就没有厶能够被阻 塞，b l l ( i ，o ) 能够被连通由i ，o 的任意性，定理得证 必要性：假定n 2 k + 4 设待连接请求为( 0 o ) 则源于第( n 2 ) 个b i t 为1 其 他b i t 为0 的输入，终于第2 个b i t 为1 其他b i t 为0 的输出的请求将阻塞0 0 路( 对 于b y ( 6 ，1 ) ，这个请求是从( o o o i o ) 至o ( o i 0 0 0 ) 的) ， 推论2 3 i ：以上定理依然正确，如果当前的请求是点到点的，但是网络中存在的 连接是广播的( 在原定理中他们都是点到点的) 定理2 3 1 2 ：b y + ( n ，自) 在广播下是严格不阻塞的当且仅当n 2 k + 3 证明：假定当前的请求是从输入i 到输出集 0 l ，d ，) 充分性：将请求按照0 1 ，0 ，的顺序一个一个的路由假定，存在j ，l jsf ，使得q 是第一个不能被路由的输出由推论2 3 1 ，从i 到0 ，的路一定被从1 到 0 1 ：，o j 一1 ) 的路阻塞f h 这显然不可能，因为从i 出发的所以路可以相互共 用l i n k 因此 不存在 必要性：这可以扶定理2 3 1 i 的必要性得出因为点到点连接只是广播f 的 一个特例 推论2 3 2 ：x c 给定- n n ，b y ( n ) 是广播不阻塞的当且仅肖k 孚 令胪= 字 设，表示b p ( n ，) 中输入输山的数1 4 那么 ，0 = 2 一一1 = 2 吲因此b y + ( 2 m l ，奄一1 ) 和b y ( 2 m ，是) 可以得到相同的a 岛我们选择奇数 的n ，l j n o = 2 l o g a n 一1 此时所用的c r o s s p o i n t 的数目为 2 , * - 1 ( 2 ( 1 2 ) + ( n 一4 ) ( 2 2 ) ) = ( n 一3 ) 2 “+ 1 = ( 2 l 0 9 2 n 一4 ) n 2 因为每缴都只有2 ”1 个c r o s s b a r , 在s t a g el 芹l j s t a g en 的c r o s s b a r 大小为1 1 ( 无c r o s s p o i n t ) ，在s t a g e2 和n 一1 ，尺寸为1 2 ，在其他级尺寸为2 2 第_ 章古典模裂下f f 勺严格不耻塞内联闷 我们所有的结果可以被推广到的d n a r y 情形，只要把2 2c r o s s b a r 以d d c r o s s b a r 代替，1 2 ( 2 1 ) c r o s s b a r 用l d ( d 1 ) c r o s s b a r 来代替 2 3 2 其他严格不阻塞广播网络 f r i e d m a n 8 1 证明了一个严格不阻塞广播镨要至少n 2 个c r o s s p o i n t ，因此没有 网络能在c r o s s p o i n t 数科上取胜然而，当前的技术不能构造较大的n 的c r o s s b a r 对 于光c r o s s b a r ，对于n 的限制更强因此对于较大的n ，一个多级内联网是需要的 两个相似的内联网已经被提出我们将他们与我们的网络做个比较第一 个是3 一s t a g ec l o s 网络和它的( 2 k + 1 ) 一s t a g e 扩展另一个就是m u l t i l 0 9 2 网络对 于广播模型。3 - s t a g ec i o s 网络中闻级c r o s s b a r 要求的数筒是n 那么他们祷要 的c r o s s p o i n t 的数h 就是 2 n r n + 一：2 2 + r 2 然而。这个网络仍然需要大尺寸的c r o s s b a r , ：n n 在s t a g el 和s t a g e3 中且rx r e s t a g e2 中而( 2 k + 1 ) s t a g e 扩展可以降低对大尺寸c r o s s b a r 的要求，f h 仍然不能 达到2 2 ，而这对于当前光网络是前提要求此# b c | o s 网络不是s e l f - r o u t i n g 的， 当( 2 k + 1 ) s t a g e 模型当中路由的负担将随着k 增多而加重 而l 0 9 2 ( n ，0 ，p ) 网络则类似于伊( n ，) 输入( 输出) 级有n 个i p ( p 1 ) 输l ( 输 出) c r o s s b a r 中问一级则包括了p 个b y - 1 ( n ) 最近k a b a c i n s k i 和d a n i l e w i c z 【t 5 】证 明了他是广播严格不阻塞的当且仅肖p2 譬c r o s s p o i n t 的数秘在p = 孚下是 2 j v ( 1 。i n ) + 鲁( 2 l 。9 2 n ) = n 2 + 2 l 。9 2 而且在s t a g e1 l l j s t a g en ，c r o s s b a r 的尺寸为1 譬，而中间一级有譬个口y 1 ( n ) ，且每 个都有2 n l 0 9 2 n 个c r o s s p o i n t f h 是，l 0 9 2 ( ，0 、p ) 网络中仍然有尺寸较大的c r o s s b a r ，而且在除了仡输入级 和输山线都是满足自路由性质的 2 3 3 基于b y - 1 ( 忆，血) 的严格不阻塞网络构造 在前面，我们已经以b y 一1 ( n ) 和b e n e s 网络为基础构造了两个严格不阻塞网 络而在构造过程中，最重要的方法就是从中问将网络分成两部分，同时从输入 1 4 第一章古舆模型下的严格不阻塞内联网 矛u 输出端开始考虑阻塞类似的分析方法也可以推广至r j b y _ 1 ( 他，m ) ，对于般 的m = 1 ，2 ，n 一1 更进一步的，前面获得的关于逆b a n y a n 和b e n e s l n 络的结祟 只是更一般模型的特殊情况像前面一样，我们采取如下步骤 ( i ) 每个输入e r o s s b a r 并, l l 输出c r o s s b b a r 都只保留一个输入和输出； ( i i ) 只保留最前k 个b i t 为0 的那些输入和输出c r o s s b a r 我们称修改后的网络 为b 巧1 ( n ，m ) 注意到b k l ( n ，m ) 只有2 “2 1 个输入和输山假定待连接的请求是从输 入o 到输出0 ，所有的输入利输出按照对0 0p a t h 的阻塞能力分组表示能阻 塞( j + 1 ) - l i n k 而不能阻尚一l i n k 的输入集合o ：