交换网络阻塞率计算的分析研究 .doc

《交换网络阻塞率计算的分析研究 .doc》由会员分享，可在线阅读，更多相关《交换网络阻塞率计算的分析研究 .doc（36页珍藏版）》请在沃文网上搜索。

1、交换网络阻塞率计算的分析研究摘要随着交换网络的日益复杂，其交换网络一般都为多级链路系统，这导致要严格计算其阻塞率的难度非常大。本文主要通过对目前存在的一些计算交换网络阻塞率算法的研究，分析其不足，以及可以改进的地方。充分利用数理逻辑方法，简化运算，使其适用于绝大部分大型的复杂交换网络。伴随着阻塞率算法的讨论进而研究实现无阻塞网络的条件，以基于虚连接的Clos 型ATM交换网络为例，研究在内部链路和外部链路的速率相同时,传统Clos 型ATM 交换网络的虚连接路由选择操作中存在的问题，和“内部链路分群”的概念, 以及具有分群结构的Clos 型ATM 交换网络的虚连接无阻塞条件。关键词：交换网络阻

2、塞率；大规模ATM交换网络；Clos型结构；虚连接阻塞；内部链路分群The blocking rate research of switching fabricsAbstractWith the increasingly complex of switching fabrics, and the switching fabrics are generally the multi-links system, which led to strict terms of its blocking of the very great difficulty. This article mainly thr

3、ough mainly through the existing network of some calculation of the exchange rate of obstruction algorithm research, analysis of its shortcomings, and can improve. Make full use of mathematical logic methods to streamline the operation to make it applicable to most of the large complex switching net

4、work. Along with obstruction of the algorithm further discussion on the conditions to achieve non-blocking network, Based on the virtual connection to the Clos-type ATM switching fabrics as an example, study the internal and external links with the same link the rate of traditional Clos-type ATM swi

5、tching fabrics connecting the virtual routing the problems that exist in operations, and internal links Grouping concept, and a cluster of Clos-type ATM switching fabrics connecting the virtual non-blocking conditions.Key words: switching fabrics blocking rate; large-scal ATM switching fabrics; Clos

6、-type architecture; virtual connection blocking; virtual connection blocking; internal links partitioning.目录1.绪论11.1 计算交换网络阻塞的方法概述11.2 Clos型交换网络发展概述12. 网络图和通路图23. 李氏（Lees）法简介34. 等效链路和级的合并34.1 交运算和并运算34.2 等效链路和级的合并45. 串并型通路图的阻塞计算56. 非串联型通路图的阻塞计算77数字交换网络的阻塞计算138. Clos 网络158.1多级交换网络158.2 交换网络内部阻塞168.2.

7、1内部阻塞的基本概念168.2.2阻塞概率的计算178.2.3无阻塞网络208.3 CLOS网络228.3.1 CLOS网络的基本概念228.3.2 三级CLOS网络无阻塞条件238.3.3 非对称CLOS网络249 基于虚连接的Clos型ATM交换网络249.1 基本特性249.2 虚连接严格无阻塞条件的证明259.3 具有内部链路分群结构的虚连接无阻塞条件289.3.1 内部链路分群的Clos型交换网络结构289.3.2无阻塞条件的证明299.3.3 讨论3010 总结3210.1 计算交换网络的阻塞率的计算方法总结3210.2 关于Clos型大规模ATM交换网络无阻塞的总结32参考文献:

8、32331.绪论网络业务的爆炸式增长促进了交换技术的发展，人们一直都在对交换网络中的一些关键性技术难题进行不懈的研究，其中尤其关键的就是交换网络阻塞控制以及如何用最低的成本实现交换网络的无阻塞。交换网络阻塞控制的关键技术难题就是交换网络阻塞问题，因此任何网络的建设，必须计算其阻塞率，得出无阻塞网络必须具备的条件，以及如何建设该网络才可以达到网络无阻塞的特性。随着交换网络的日益复杂，严格地计算其阻塞率，其公式是通常是很复杂的，本文先就如何简便准确地计算交换网络地阻塞率进行初步探讨。然后将首先论述基于虚连接的Clos型ATM交换网络的基本特性，然后，证明传统的Clos型ATM交换网络虚连接的严格无

9、阻塞条件。指出在内部链路和外部链路的速率相同时传统Clos型ATM交换网络的虚连接路由选择操作中存在的问题后，提出了“内部链路分群”的概念，并证明了具有分群结构的Clos型ATM交换网络的虚连接无阻塞条件。1.1 计算交换网络阻塞的方法概述交换网络一般为多级链路系统，如要严格地计算其阻塞率，其公式是通常是很复杂的，李氏(C.Y.Lee)曾提出一种网络分析法，可从网络通路图直接列出阻塞计算公式，当各级链路的占用概率服从或接近贝努里分布时，可获得满意的效果。但当网络结构较复杂时，按李氏(Lees)法列出的计算公式较繁琐，且易于出错。后面所介绍的方法是直接按照网络通路图，引入级的合并和等效链路的概念

10、，反复应用“交”和“并”的运算，从而得到简化的计算阻塞的表达式。这是一种工程上实用的计算方法。此外，考虑到一些非串并型网络和某级出现的非贝努里分布以及数字交换网络的阻塞计算方法。1.2 Clos型交换网络发展概述自从异步传递模式(Asychronous Transfer Mode, ATM)由ITU-T(以前的CCITT)建议作为将来宽带综合业务数字网(B-ISDN)的综合传递技术以来，已经提出并开发研制了许多ATM交换网络，但由于技术和物理条件的限制，这些交换网络的规模都不会很大，其超大规模集成电路芯片或者印制电路板的输入/输出端口数通常被限制在100100的范围内，较实际的尺寸如1616和

11、3232等。一个B-ISDN的中心局要求其ATM交换机一般要有10000以上的高速双向端口以提供100000个终端的连接。显然，上述小规模(100100)ATM交换网络的方法。目前已提出了像Clos型网络结构，扩展的Banyan网络结构以及基于Knockout交换网络的结构等几类大规模ATM交换网络结构。作为一种较为典型的结构，Clos型网络已被许多国际著名公司采用作为其下一代ATM交换网络结构，并采用基于虚连接的路由选择算法。对基于虚连接的路由选择算法来说，交换网络是在虚连接建立阶段，在交换网络内部，为属于同一个虚连接的所有信元分配相同的路由，且这个路由在整个连接持续阶段保持不变，直到这个虚

12、连接被释放为止。由于ATM交换的多速率特性，将使Clos型ATM交换网络的路由选择操作要比传统的电路交换Clos网络复杂的多。2. 网络图和通路图图3 图1网络通路图图1 四级接线器组成的交换网络图2 图1所示交换网络网络图图1表示A、B、C、D四级接线器组成的交换网络，每个接线器的出入线都只画了第一条和最后一条。在容量较大的交换机中，网络出端通常为指定试选方式，故对阻塞计算而言，图1为三级链路系统1。图4 一种通路图示例网络阻塞与级间链路的连接方式有关，可使用网络图（network graph）和通路图（Chnnel graph）来简明地表示级间链接方式。网络图反映了整个交换网络的结构，每个

13、接线器用结点表示，链路用结点间的连接线（支路）表示。图1的网络如图2所示。通路表示某一对指定的出入端之间可使用的链路，是计算网络阻塞的依据。图2的通路图如图3所示。实际上，也可以从交换网络的结构直接画出其通路图，即从图一直接得到图4。3. 李氏(Lees)法简介下面用两个示例简要说明李氏（Lees）法2。（1） 试计算图3通路图的阻塞率。设第i级每条 链路的阻塞率（即其负荷话务量）为，接通率为，显然有=1-。按照李氏（Lees）法，可有：AD间一条支路的接通率为 (3-1)AD间1条支路的阻塞率为 (3-2)AD间的阻塞率为 (3-3)（2） 试计算图4通路图的阻塞率。CD间的接通率为 (3-

14、4)BE间的阻塞率为 (3-5)BE间的接通率为 (3-6)AF间的1条支路的接通率为 (3-7)AF间的阻塞率为 (3-8)4. 等效链路和级的合并4.1 交运算和并运算交运算和并运算符合交换律和结合律，其基本运算如下：交运算图5 文氏图并运算从文氏图可以理解交运算与并运算的概念，如图5所示。要注意的是，a，b，c表示各级的每条链路的阻塞率，也就是每条链路的话务量，是不大于1的数。4.2 等效链路和级的合并图6 两条之路的并联、串联及它们的等效通路图两结点间的并联支路可用1条等效链路来表示，该等效链路的阻塞率为各并联支路阻塞率的并运算。也就是n条并联链路等效于1条链路，其等效话务量为个并联链

15、路的话务量的并运算。两结点间的串联支路（经过其它结点）也可用1条等效链路来等效，其阻塞率为各串联支路阻塞率的交运算3。这种等效链路相当于将几个交换级别合并为等效的一级。图6表示两条支路的并联、串联及它们的等效通路图。显然，也可以照此扩展到n条支路。应用上述概念不难得到对于图7中(a)至(d)通路图的等效链路阻塞率P：图7 几种通路图a. 并串型： (4-1)b. 串并型： (4-2)c. 并串并型： (4-3)d. 串并串型： (4-4)5. 串并型通路图的阻塞计算现通过几个示例说明串并型通路图的计算方法。(1) 计算图4通路图的阻塞率。按照等效链路和级的合并概念，图4可等效为图8，即将5级链

16、路化为3级链路BE间的3级链路所等效的1级链路的阻塞率为），于是从图8便可立即得到整个通路图的阻塞率： (5-1)图8 图4通路图的等效图(2) 计算图9的小鸡图的阻塞率实用上常用小鸡图表示网络结构。图9是对出线D自由选择的3级链路，用小鸡图给出，从该小鸡图可得到图10通路图，从而立即可求得阻塞率如下：图9 对出线D自由选择的3级链路组群图 图10 图9所示3级链路的通路图(3) 计算图11中小鸡图的阻塞率图12 图11的通路图图11 从入中继到用户的五级链路组群示意图 图11是从入中继到用户的5级链路，对应的通路图示于图12。从表面上看图中出现了交叉，但经调整后，可化为图13（仍属串并型通路

17、图）。从图13可得到网络阻塞率如下： (5-2)6. 非串联型通路图的阻塞计算在相同的级数、链路数和话务量的条件下，非串并型网络结构的阻塞率比串并型的阻塞率小，故在实用上往往出现非串并型结构。在一定条件下，由于级间连接方式的不同，可出现多种非串并型结构。高木(Takagi)曾提出一种优化方法，按照一定的规则连接可得到阻塞率最低的通路图。图13 图12经过调整后的通路图对于非串并型结构可采用“切割法”，即在通路图中沿某即接线器（通常为第1级或最后1级）处切割，是剩下的通路图变成串并型，即可进行计算，有时则可能不止切割一次。下面先用一简单示例说明切割法。图15 对应于图14的通路图图14 一种实用

18、的小鸡图图16 表示沿B点切割的通路图图17 沿B点切割后及其对应的C链路亦为闭塞的示意图在实用上常常会出现图14所示的小鸡图，对应的通路图如图15所示。这是非串并型的基本结构。图16表示沿B点切割，并又m=4，l=2。虽未沿着B点切割，也就是考虑b链路任占i条的状态概率下，再计算余下的c、d两级链路的阻塞概率。设i=2，b链路占用了2条，从而对应的4条c链路也不能占用（图17中用粗线表示）。未被闭塞的c、d链路示于图18的左端，称为条件通路图（conditional channel graph）。图18 沿B点切割后未被闭塞的c、d链路示意图切割线上的所有结点可以合并，于是图18中左面于右面

19、的图等效，即非串并型通路图化为串并型，其阻塞率为。考虑到未被闭塞的C级链路数受i的影响，可得到阻塞率的一般表达式： (6-1)下面再用几个示例说明非串并型通路图的阻塞计算。图21 某种实用的小鸡图图 19 某种实用的小鸡图图20 对应于图19的通路图1. 计算图19中小鸡图的阻塞率对应的通路图于图20，可分离未两个通路图，即两个同样的非串并型通路的并联，用前述计算方法立即可得到： (6-2)图22 对应于图21的通路图2. 计算图21中小鸡图的阻塞率图23-1 对应于图22的通路图对应的通路图示于图22。在右切割，即在e链路任占i条的状态下，再考虑余下的几级链路，条件通路图示于图23-1。图2

20、3-1仍然是非串并型，这说明要继续进行切割。但是，这是两个相同的非串并型通路的并联，而每一个非串并型通路图与图15中的基本结构相同，设其阻塞率为，于是可有 (6-3)结合本例还可说明两个问题：（1）合适地选择切割端在本例中是在右端切割，如在左端切割，则在b链路任占i个时，要考虑具体占用哪i个，这是由于i个的不同分布将对后级链路产生不同的影响。对于图15，可在任意端切割，但当可选左端，当可选右端，以减少求和的次数。（2）起算端链路的状态概率可使用非贝努里分布。因为起算端链路不能采用并运算或交运算，而是计算各种状态的占用概率，故可使用爱尔兰分布或恩科谢特分布。3.计算图24中4个通路图的阻塞率图2

21、4中4个通路图(a)(d)具有相同的级数和链路数，但中间级的连接方式不同，而其中图24(d)实际上是串并型的，其结构于图4一样。根据高木（Takagi）的方法4，分布结点用D表示，汇合结点用M表示，在对应的D和M之间用关系线连接，以表示该M点汇合了D点所分布的通路。于是可有：图23-2按照高木（Takagi）提出的优化方法来判别，显然是(a)优于(b)，(b)优于(c)，(c)优于(d)。亦即(a)的阻塞率最低，(d)的阻塞率最高。图24中的通路图通常是得自单元式组群和各单元间不同的连接方式。故通路图中第1、5级每条链路的话务量均为a，第2、4级每条链路的话务量均为b，中间级的每条链路话务量为

22、c。在计算阻塞率时，对于图24(a)和(b)要切割两次，亦即考虑第1链路任占i条，低5级任占j条的状态概率。显然当i=2或j=2，即产生阻塞。当i和j均小于2时的条件通路图示于图25。图24 4个通路图举例图25 当i和j均小于2时的条件通路图图25中的各个条件通路图都是串并型或串并型基本结构，但容易求得其阻塞率。例如，当i=1和j=0时，对于图25(a)可有： (6-4)当i=0和j=1，对于图25(b)可有： (6-5)将以各种i，j的值所求得的阻塞率相加，即得到总阻塞率。有时，对应于各种i、j的值的条件阻塞率可用一通式表示。本例可做到这一点。令图25(a)、(b)的阻塞率为、，可有： (

23、6-6) (6-7)对于图24(c)、(d)，则易于得到： (6-8) (6-9)7数字交换网络的阻塞计算数字交换网络可化为等效的空分网络后计算其阻塞率。当然，也就可采用本文所介绍的计算方法5-6。实际上，可从数字交换网络直接得到通路图，并立即得到阻塞计算式。下面举两个例子来说明。图 26 某TSST网络图1.计算图26中TSST网络的阻塞率在指定的出入端之间可选用的通路在图26中用粗线表示，考虑每条线是512个时隙，而S级不能进行时隙交换，立即可道道图27所示的通路图（属于串并型），其阻塞率P为： (7-1)图27 对应于图26的通路图图28 具有5级接线器的数字交换网络3. 计算图28中数

24、字交换网络的阻塞率 图29 对应于图28的通路图图30 对应于图29的另一种形式通路图图28中数字交换网络有5级接线器，每级由若干个交换网络单元组成，每个交换单元具有时空结合的交换功能，即任意出入线的任意时隙均可完成交换。指定出入端间的通路用粗线标明，从而得到图29所示的通路图。由于每线有32个时隙，每个交换单元有时隙交换功能，故在通路图中两相邻结点间有32条通路，实际上，不一定画出图29，而可将通路图画成图30中所示的形式，每条线相当于32条通路并联。其阻塞率计算如下： (7-2)8. Clos 网络8.1多级交换网络交换网络通常要由若干级接线器组成，因而从交换网络的入线到出线之间将经过若干

25、级网络内部的级间的连线链路。当呼叫由入线进入交换网络，但其出线全忙，因而该呼叫找不到一条空闲的出现时，该呼叫将损失掉。但有时出线空闲，而相应的链路不通时，呼叫也将损失掉。由于网络内部级间不通而使呼叫损失掉的情况称作交换网络的内部阻塞。可以增加网络各级的链路数量来降低内部阻塞的概率。当链路数量大到一定程度是，内部阻塞概率将等于零。即成为一种无阻塞的交换网络6。本节就来研究这个问题。将交换网络单元按一定的拓扑结构连接起来，可形成单级或多级交换网络。单级交换网络是由一个交换网络单元或若干个位于同一级的交换网络构成，如图31所示。需交换的信息在单级交换网络中一次通过，即一次入线到出线的连接，只经过一个

26、交换单元。另外，从图31(b)上可以看出，这种单级交换网络中，属于不同交换单元的入线与出线间无法建立连接，这不能算作真正的交换网络。因此，我们一般说到的单级交换网络应如图31(a)所示。通常使用的是多级交换网络，多级交换网络由多级交换单元构成。如果一个交换网络中的交换单元可以分成K级，顺序命名为第1、2、K级，并且满足： 所有的入线都只与第一级交换单元连接； 所有的第一级交换单元都只与入线和第二级交换单元连接； 所有的第二级交换单元都只与第一级交换单元和第三级交换单元连接； 以此类推，所有的第K级交换单元都只与第K-1级交换单元和出线连接。则称这样的交换网络为多级交换网络，或称K级交换网络。多

27、级交换网络的拓扑结构可以用三个参量来说明，这三个参量是：每个交换单元的容量；交换单元的级数；交换单元间的连接通路（链路）。因为一个交换单元入线与出线的关系可以用连接函数表示，而在多级交换网络中不同级交换单元间的拓扑连接也可以用连接函数来表示，这也被称为拓扑描述规则。因此，从数学的的观点，多级交换网络是由一组连接函数组成，包括各级交换单元本身的连接函数和各级之间链路的连接函数，以便实现交换网络的入线与出线之间的某种映射关系。（a）一个交换单元构成（b）同级多个交换单元构成图31 单级交换网络示例8.2 交换网络内部阻塞8.2.1内部阻塞的基本概念交换网络通常要由若干级接线器组成，因而从交换网络的

28、入线到出线之间将经过若干级网络内部的级间的连线链路。由前已述，当呼叫由入线进入交换网络，但其出线全忙，因而该呼叫找不到一条空闲的出现时，该呼叫将损失掉。但有时出线空闲，而相应的链路不通时，呼叫也将损失掉。由于网络内部级间不通而使呼叫损失掉的情况称作交换网络的内部阻塞。可以增加网络各级的链路数量来降低内部阻塞的概率。当链路数量大到一定程度是，内部阻塞概率将等于零。即成为一种无阻塞的交换网络7-8。多级交换网络会出现内部阻塞问题。如图31所示，一个的两级交换网络，它的第一级是由m个的交换单元构成，第二级是由n个的交换单元构成，第一级同一交换单元的不同编号的出现分别接到第二级不同交换单元的相同编号的

29、入线上。交换网络的mn条入线中的如何一条均可与nm条出线中的任一条接通，因此它相当于一个的单级交换网络。图32 与单级交换网络相比，有两点重要的不同。首先，两级交换网络每一对出、入线的连接需要通过两个交换单元和一条级间链路，增加了控制交换单元和搜寻空闲链路的难度；其次，在单级交换网络中，只要有一对出、入线空闲，便可将两者接通。但在两级交换网络中，由于第一级的每一个交换单元与第二级的每一个交换单元之间仅存在一条链路，任何时刻在一对交换器之间只能有一对出、入线接通。例如，当第一级0号交换单元的0号入线和第二级1号交换单元的m-1号出线接通时，第一级0号交换单元的任何其他入线都无法再与第二级1号交换

30、单元的其余出线接通。这种出、入线空闲，但因交换网络级间链路被占用而无法接通的现象称为多级交换网络的内部阻塞。若用计算机术语，阻塞也可称为冲突，即不同入线上的信息试图同时占用同一条链路。单级交换网络是不存在内部阻塞的，而且它的控制机制比多级交换网络简单，时延短，因为时延与级数成正比。那么，为什么实际使用的大多是多级交换网络？一般而言，交换网络中交叉点越多，成本越高，建立连接的路径亦越多，阻塞的机会也越小、连接能力也就越强。交换网络拓扑设计的总目标，就是在满足一定的连接能力的要求下、尽量最小化交叉点数。容量相同的多级与单级交换网络比较，交叉点数会大大减少。例如，图32中的两级交换网络，共有交叉点个

31、，而的单级交换网络，交叉点数目为。现设n=m=8，则一个的单级交换网络，交叉点数目为个；而若是两级交换网络，交叉点个。而且，交叉点数目会随着入、出现数的增加而迅速增加。8.2.2阻塞概率的计算由于空分模拟交换网络简明直观，因而可先将数字交换网络等效成相应的空分模拟交换网络，然后分析该空分模拟交换网络的内部阻塞问题，并结合数字交换网络在呼叫接续中的特点，即可得出数字交换网络的内部阻塞概率8。下面以常用的TST数字交换网络为例来进行分析。图33为一条具有16条输入母线及16条输出母线、每条母线上均为256个时隙的TST数字交换网络，T-S及S-T级间链路母线上的时隙数为256.图中，公共话路HW即

32、为母线。图 33 TST 交换网络举例上述的TST数字交换网络的等效空分模拟交换网络如图34所示。图34的等效空分模拟交换网络的输入线及输出线各有256x16=4 096条，A级于B级之间及B级与C级之间的链路也各有256x16=4 096条。假定每条入线的话务流量（忙时的话务量强度）为，即每条入线的占用概率为。因各级间的链路数和入线数相等，故每条链路占用的概率也为，因而每条链路的空闲概率为（1-）。为使所有呼叫到来的的入线与所要求的出线接通，至少必须有一条能达到的AB级间链路和一条相应的BC级间链路同时空闲形成一条空闲通路才行。而这条通路空闲的概率为，这里K为交换网络的级数。图8.7而言，L

33、=256.当这L条通路全忙时，则无法完成连接，因而交换网络发生阻塞的概率为。图34 TST网络的等效网络由于呼叫的空分模拟交换网络中只需接通一条通路即可完成主叫到被叫方向及被叫到主叫方向的双向话音传输，而数字交换网络中一条通路只能完成主叫到被叫或被叫到主叫的单项话音传输，要完成双向传输必须同时有主叫到被叫方向及被叫到主叫方向的两条通路才行。因而对上面得出的阻塞概率公式必须进行修正：两条通路同时空闲的概率应为。所以两条通路不同时空闲的概率为。当两条通路都处在同一个T型接线器中时，（即图34中的同一个A级接线器及C级接线器）则通路阻塞概率为。这样，呼叫在交换网络中发生阻塞概率应为 (8-1)对图3

34、3而言，L=256，T=16，则 (8-2)若，则 (8-3)若，则 (8-4)可见，当交换网络输入线上的每线话务量较高（也即每线利用率较高）时，若网络采用如图34那样输入线与链路数相等的无集中无扩散网络，则每条链路上的话务量也较高（与输入线相同），这样交换网络的阻塞概率就很大。上例中当 时，P=67%时。为降低阻塞概率，应采用A级扩散、C级集中的交换网络，即是增加网络内的链路数。例如，当A级入线数与其出线数（即是AB级间链路数）之比为1：1.5及C级入线数（即是BC级间链路数）与其出线数之比为1.5：1时，若交换网络的每条话务量仍为0.8Erl，则每条链路上的话务量将减少为 (8-5)链路数

35、增加为 (8-6)这时网络阻塞概率为 (8-7)因此，阻塞概率大幅度减小。当比例进一步扩大，达到A级入、出线之比为1：2，C级如、出线之比为2：1时，则使每条链路上的话务量为 (8-8)链路数增加为 (8-9)这时网络阻塞概率为 (8-10)实际上这样低的阻塞率已经可以被看作为零，即交换网络已经是一种无阻塞网络。这一结论也可以通过下面的分析得到。8.2.3无阻塞网络研究无阻塞交换网络的目的是如何尽量减少，以至最后消除多级交换网络的内部阻塞。下面给出三种无阻塞交换网络的概念9。 严格无阻塞网络。不管网络处于何种状态，任何时刻都可以在交换网络中建立一个连接，只要这个连接的起点、终点是空闲的，而不会

36、影响网络中已经建立起来的连接。 可重排无阻塞网络。不管网络处于何种状态，任何时刻都可以在一个交换网络中直接或已有的连接重选路由来建立一个连接，只要这个连接的起点和终点是空闲的。 广义无阻塞网络。指一个给定的网络存在着固有的阻塞的可能，但有可能存在着一种精巧的选路方法，使得所有的阻塞均可以避免，而不必重新安排网络中已经建立起来的连接。因为目前真正实用的冠以无阻塞网络非常少见，所有下面只讨论严格无阻塞网络和可重排无阻塞网络。图35 无阻塞交换网络图35为1个三级交换网络，A级接线器的入线与出线（即是AB级间链路）之比为3：5，C级接线器的入线（即是BC级间链路）与出现之比为5：3.对于交换网络的每

37、一条入线（即是A级入线），有5条AB级间链路可供选择；对交换网络的每一条出线（即是C级出线），也有5条BC级间链路可供利用。因此，在交换网络的每一条入线与每一条出线之间共有5条通路可走。最不利的情况发生在：当A级的某条入线进来呼叫时，该入线所在的接线器已经有两条入线建立了连接，因此只剩下3条AB级间链路可供选择；而该入线所要求连接的C级出现所在的接线器也已经有两条出线建立了连接，该出线也只有3条BC间链路可供利用；并且，A级这台接线器的两条入线建立的连接与C级这台接线器的两条出线建立的连接完全无关的，即是两条已经占用的AB级间链路与两条已经占用的BC级间链路完成的是完全不同的连接，也就是说，已

38、经建立了个连接。那么，至少还有一条AB间链路和一条阻塞。因此图34所示的三级交换网络是一种无阻塞的交换网络。推广带一般的情况：令A级接线器入线数与出线数之比为n：m，C级接线器的入线数与出线数之比为m：n，则无阻塞交换网络必须使 (8-11)当n相当大时，一般取 (8-12)例如当n=256时，可取。因此，为得到无阻塞的TST数字交换网络，只需使得网络的内部时隙数为网络的输入（或输出）时隙数的两倍。这对于采用体积小，功耗小的大规模集成电路构成的数字交换网络来说是可行的，实际上有些数字交换机已经采用了无阻塞交换网络。8.3 CLOS网络8.3.1 CLOS网络的基本概念为了降低多级交换网络的成本

39、，长期以来人们一直在寻找一种交叉点数随入、出线数增长较慢的交换网络，其基本是思想就是采用多个较小规模的交换单元按照某种连接方式连接起来形成多级交换网络。CLOS首次构造了一类如图36所示的的无阻塞交换网络，他指出：采用足够多的级数，对于较大的N，能够设计出一种无阻塞网络，其交叉点增长的速度小于，也就是说，使用CLOS网络，既可以减少交叉点数，又可以做到无阻塞10。图36 三级Clos网络由图36可知，CLOS网络的结构：两边各有r个对称的矩形交换单元，中间是m个个的方形交换单元。每一个交换单元都与下一级的各个交换单元有链接且仅有一条连接，因此任意一条入线与出线之间存在一条通过中间级交换单元的路

40、径。m、n、r是整数，决定了交换单元的容量，称为网络参数，并记为C（m，n，r）。CLOS实际地构造了一个N=36的三级CLOS网络。其中，第一级有6个的矩形交换单元，中间级有11个的方形交换单元，第三级有6个的矩形交换单元。该网络共有1188个交叉点，小于。8.3.2 三级CLOS网络无阻塞条件参见图36，可以看出，在最不利情况下，中间级会有个交换单元被占用，因此中间级至少要有个交换单元，即时可确保无阻塞。所以对于C（m，n，r）CLOS网络，如果，则此网络是严格无阻塞的。图 37 三级可重排无阻塞网络对于三级CLOS网络C（m，n，r）,如果则词网络是可重排无阻塞的。图36示出一个m=n=

41、r的三级可重排无阻塞CLOS网络。严格无阻塞网络的概念比较好理解，而可重排无阻塞网络则比较抽象，下面用一个简化的例子来说明可重排无阻塞网络的基本原理。假设有一个的三级可重排无阻塞CLOS网络，如图38所示，其中，m=n=r=2，显然，它不满足严格无阻塞的条件。仅考虑点到点连接，则这种交换实际上再数学上等效于对4个数的排列置换。但是，这种网络并不能实现入线和出线之间的所有可能的置换。例如，参考图38，我们欲作如下的交换，其连接函数排列表示为如图38（a）所示，1到4的连接已经过路径C1，3到1的连接已经过路径C2，那么2到2和4到3的连接就无法建立，即发生了阻塞。但有可能重新调整一下已有1到4和

42、3到1的链接，来建立2到2的和4到3的连接。为此如图38（b）所示，不改变原来的1到4的路径C1，而将3到1的路径改为CC2，那么2到2和4到3的连接就可以建立（如图38（b）中虚线所示）。这样总共改变了原有连接1次。可见，对于如图38所示的m=n=r=2的三级CLOS网络，改变原有连接1次，就可以实现所指定的无阻塞连接，但需要有一套重新安排路径的算法。图 38 m=n=r=2三级可重排CLOS网络8.3.3 非对称CLOS网络若CLOS网络入线数为M，出线数为N，则称为非对称CLOS网络。三级非对称CLOS网络记为，它表示：第一级有个输入交换单元，其中每个都具有条入线和m条出线，且；第三级有

43、个输出交换单元，其中每个都具有条出线和m条入线，且中间级有m个的交换单元，如果，该网络就简化成图36所示的对称三级CLOS网络C（m，n，r）。对于三级非对称CLOS网络，如果，则此网络是严格无阻塞的，如果，则此网络是可重排无阻塞的。9 基于虚连接的Clos型ATM交换网络9.1 基本特性ATM交换网络的多速率动态业务特性，使得基于虚连接的Clos型ATM交换网络具有与传统的Clos型电路交换网络不同的特性。在传统的Clos型电路交换网络中,内部和外部链路上的业务速率都是固定的64kb/s，即到达的业务就是一个64kb/s速率的业务。在内部链路的带宽分配中，一条链路被分配就是占用了64kb/s

44、的带宽，而未被分配的链路就是一条空闲链路，即是单速率的固定带宽分配方式，而在Clos型ATM交换网络中，到达交换网络的业务特性以及交换网络内部链路的带宽分配和占用特性都要比传统的电路交换网络复杂11，主要表现在以下两点：第一，ATM交换网络是多速率的.实际上，按照ATM的基本原理，一个ATM交换网络要能处理任何速率的业务。从带宽分配的观点来看，如果假设交换网络的一条内部链路的总带宽是1,对新到达的呼叫(在ATM中要提供虚连接,以下简称为“连接”)分配的带宽是，只有当一条链路上已被占用的带宽小于时，该连接才可能在这条链路被分配带宽.在任何的电路交换网络中，是恒等于1的。第二，ATM交换网络内部链路的带宽是由许多具有不同带宽的连接统计复用(共享)的，即一条内部链路上可能承载着不同带宽的连接().不同链路上的带宽种类和分布也是不同的。而在传统的电路交换网络中，每一条链路上要么空闲(没有承载业务),要么承载着=1的业务.正是因为ATM交换网络对速率所固有的高度灵活性，直观上看，其虚连接级的严格无阻塞条件将要比传统的电路交换网络严，且其虚连接阻塞概率的计算也就变得非常复杂。9.2