第2章 交换网络 第一章中介绍了交换系统的基本组成，其中信息传送子系统包括接口电路和交换网络。交换网络是构成交换系统的重要组成部分，它完成信息交换的功能。 本章介绍构成交换网络的交换单元的基本特性、功能和交换网络的构成，以及现在广泛使用的典型的交换网络的工作原理。

2.1 交换单元 2.1.1 交换单元的基本概念 1、交换单元 交换单元（Switch Element -- SE）是构成交换网络的最基本的部件，若干个交换单元按照一定的拓扑结构连接起来就可以构成各种各样的交换网络。可以说交换单元是完成交换功能的最基本的部件。 图2.1 M×N的交换单元

如图2.1所示，一个交换单元从外部看主要由四个部分组成：一组输入端口、一组输出端口、控制端与状态端。交换单元的输入端口又称为入线，输出端口也称为出线，一个具有M条入线，N条出线的交换单元，称为M×N的交换单元，同时把入线编号为0到M-1，出线编号为0到N-1； 控制端主要用来控制交换单元的动作，可以通过控制端的控制把交换单元的特定入线与特定出线连接起来，让信息从入线交换到出线而完成交换的功能； 状态端用来描述交换单元的内部状态(状态字)，不同的交换单元有不同的内部状态集，通过状态端口让外部及时了解到其工作情况。

从内部看交换单元，其构成是多种多样的，可以是一个时分总线或是一个空分的开关阵列。 但无论其内部构成如何，交换单元都应能够完成最基本的交换功能，即把交换单元任意入线的信息交换到任意出线上去。

对交换单元有多种分类方法，可以从不同的角度对交换单元进行分类，一般采用以下4种分类方法。 （1）按照入线与出线上信息传送的方向是单向还是双向可以把一个交换单元分为有向交换单元与无向交换单元，如图2.2所示。 有向交换单元指任何入线或出线上信息的传输是单方向的，即信息只能从入线进入交换单元，从出线上交换出来，如果一个有向交换单元有M条入线、N条出线，那么我们把这个交换单元称为M×N有向交换单元。 图2.2 交换单元分类1：有向与无向

无向交换单元主要有两种类型：N无向交换单元与K×L无向交换单元。其中N无向交换单元并没有入线与出线的区别，它相当于把一个N×N的有向交换单元（入线数与出线数相等的交换单元）的相同编号的入线与出线合并在一起，将其看作同时具有发送和接收信息能力的一个信息端，那么这个N×N有向交换单元就变成一个具有N个双向通信信息端的N无向交换单元；

设N=K+L，K×L无向交换单元是指在N无向交换单元的基础上把N个信息端分为一组输入端与一组输出端，输入端假设有K个信息端(K个输入端)，输出端有L个信息端（L个输出端），并且只有输入的K个信息端与输出的L个信息端之间才能有信息交换，在输入的K个信息端之间不能进行信息交换，同样L个输出端之间也不能进行信息交换，满足这种条件的N无向交换单元称为K×L无向交换单元。

（2）按照交换单元入线与出线的数量关系可以把一个M×N的交换单元分为集中型，连接型以及扩散型，如图2.3所示。 图2.3 交换单元分类2：按照入线与出线数目

集中型交换单元是指入线数大于出线数（M>N）的交换单元，也叫集中器（concentrator）；连接型交换单元是指入线数等于出线数（M=N）的交换单元，也称为置换器或连接器（connector）；扩散型交换单元是指入线数小于出线数（M<N）的交换单元，扩散型交换单元也可称为扩展器（expander）。注意图2.3中表示的为有向交换单元。

（3）按照交换单元的所有入线与所有出线之间是否共享单一的通路，可以把交换单元分为时分交换单元与空分交换单元，如图2 （3）按照交换单元的所有入线与所有出线之间是否共享单一的通路，可以把交换单元分为时分交换单元与空分交换单元，如图2.4所示。这是按照交换单元内部结构来进行的分类。 图2.4 交换单元分类3：时分与空分

时分交换单元的基本特征是所有的输入端口与输出端口之间共享唯一的一条通路，从入线来的所有的信息都要通过这条唯一的通路才能交换到目的出线上去，这条唯一的通路可以是一个共享总线，也可以是一个共享存储器。 空分交换单元的所有入线与出线之间存在多条通路，从不同入线来的信息可以并行的在这些通路上传送，空分交换单元也可称为空间交换单元，典型的空间交换单元就是开关阵列。 （4）按照交换单元所接受的信号是模拟信号还是数字信号，可以把交换单元分为数字交换单元与模拟交换单元

2、交换单元的连接特性 交换单元的基本功能就是要在入线与出线之间建立一定的连接，使信息能从入线交换到出线。交换单元的连接特性（connectivity）反映出交换单元从入线到出线的连接能力（连接关系），是交换单元的基本特性。 交换单元的连接特性有两种描述方式，可以用集合来描述，也可以用函数方式来描述。

（1）集合描述方式 用集合方式来描述一个M×N交换单元的连接特性，可以把该交换单元的所有入线组成一个集合，用T来表示： T = {0，1，2，……M-1} 把该交换单元的所有出线组成一个集合，用R表示： R = {0，1，2，……N-1} 记入线集合T中的元素为t（t∈T），出线集合R中的元素为r（r∈R），同时记Rt为出线集合R的一个子集，那么可以把一个连接定义为一个集合，用c表示： c = {t，Rt}

该集合表示了该M×N交换单元的入线t与一组出线Rt之间的连接，可以把t称为连接的起点，把r∈Rt称为连接的终点。如果Rt中只含有唯一的一个元素，那么把该连接称为点到点连接；如果Rt中包含多个元素，那么把该连接称为点到多点连接。特别的对于点到多点连接，如果Rt≠R，称此连接具有同发（组播）功能，如果Rt=R，称此连接具有广播功能。

一个交换单元的连接方式表示了该交换单元在某个时刻建立的所有从入线到出线之间的连接，连接方式可以表示为一个集合，我们用C来表示，那么： C = {c1，c2，c3，……} 该集合是由若干个连接组成的一个集合（表示各个连接的集合c的下标不代表任何实际意义，只是区分不同的连接）。特别要说明的是一个交换单元的连接方式总是对应于某个具体时刻的，在这个时刻的连接方式是这样的，在另一个时刻，它的连接方式又会变为那样。在某一时刻，一个交换单元总是处在一定的连接方式C下，也就是说该交换单元的各个入线与各个出线按照该连接方式连接着。 一个交换单元的连接方式可以通过该交换单元的控制端口改变，同时也可以通过该交换单元的状态端口反映出来。

Rc = {r：r∈Rt，Rt∈ci，ci∈C } 对于一个连接方式，可以定义连接方式的起点集，表示该连接方式中所有连接的起点组成的集合，用Tc表示： Tc = {t：t∈ci，ci∈C} 同样可以定义该连接方式的终点集，表示该连接方式中所有连接的终点组成的集合，用Rc表示： Rc = {r：r∈Rt，Rt∈ci，ci∈C } 同时可以判定，当交换单元处于连接方式C下，若某条入线t∈Tc，称该入线处于占用状态，否则处于空闲状态；同样若某条出线r∈Rc，称该出线处于占用状态，否则处于空闲状态。

（2）函数描述方式 用函数方式来描述一个M×N的交换单元的连接特性，可以将其连接方式用函数f(t)表示： f(t) = Rt（Rt包含于R） 该函数的自变量为t，它的定义域为交换单元的入线集合T，值域为交换单元的出线集合R的各个子集组成的集合。一个连接函数对应一种连接，连接函数表示相互连接的入线编号和出线编号之间的一一对应关系，即存在连接函数f，入线t与出线集合f(t)中每条出线相连接。如果该入线t空闲，那么与它连接的出线的集合为一个空集。对于一个点到点连接，

上述表示连接方式的函数称为连接函数，可以有三种更直观的形式来表示连接函数，一种是排列表示形式，另一种是通过图形来表示。第三种方式：对于点到点连接方式我们经常采用2进制函数表示方法。 （1）排列表达式 交换单元的连接实际上是交换单元的入线与出线之间的一种对应关系，那么可以通过罗列的方式来表达连接方式，我们称为连接方式的排列表达式，表示为： t1，t2，……tn r1，r2，……rn

其中ti为入线编号，ri为出线编号，上述的排列表达式表示了入线t1连接到出线r1，入线t2连接到出线r2……入线tn连接到出线rn，其中n≤N（注意入线t1并不表示入线1，出线rn也不表示为出线n）。考虑到存在点到多点的连接，因此t1，t2，……tn中可能有重复的元素存在，因此也可以把排列表达式称为重排表达式。 所谓存在出线竞争，就是指在排列表达式中出线r1，r2，……rn之间存在着重复的元素，表明在同一时刻，有多条入线共同连接到同一条出线，造成出线的冲突，也就是说从多条入线上来的信息，同时要交换到同一条出线上，共同竞争这条出线，这是应该避免或要采取一定措施来解决的问题。

在点到点的连接情况下，并且不存在出线竞争的情况下，排列表达式中的t1，t2，……tn之间没有重复的元素，同时r1，r2，……rn之间也没有重复的元素，那么点到点连接方式的排列表达式可以改写为： 我们把这种排列表达式称为入线排列表达式，它实际上是使出线的编号按照自然数顺序排列，表示入线t0连接到出线0，入线tN-1连接到出线N-1， 上式也可以进一步简化表示为： (t0，t1，……tN-1)

同样，也可以定义出线排列表达式为： 0，1， ……N-1 r1，r2，……rN-1 它的简化表示为： (r1，r2，……rN-1) 根据排列表示形式，对于一个N×N的交换单元，假设没有空闲的入线与出线，N条入线与N条出线任意进行点到点连接，那么N个元素可以有N！种不同的排列，因此一个N×N的交换单元可以最多有N！种不同的点到点连接方式。

（2）图形表示 还可通过图形方式来表达连接函数。分别把入线与出线按编号由上到下排列，然后入线与出线之间可以用一条直线连接起来，表示该入线与出线有连接。如图2.5所示，表示了一个常用的N=8的交叉连接方式。 图2.5 连接函数的图形表示

E(xn-1xn-2……x1x0) = xn-1xn-2……x1 （3）2进制函数表示 有一种更为常用的方法来表示点到点连接方式。假设入线编号可以用一个n位2进制数字xn-1xn-2……x1x0表示（2进制比特流），用该2进制数字作为连接函数的变量，连接函数的值也用一个2进制数字表示，表示与该入线连接的出线的编号。我们把这种函数表现形式称为2进制函数表示。对于图2.5所示的连接方式，用2进制函数表示则为： E(xn-1xn-2……x1x0) = xn-1xn-2……x1

下面我们来看看几种常用的连接方式： a）直线连接 对于连接型交换单元，把相同编号的入线与出线直接连接起来而形成的点到点连接方式称为直线连接，也称为恒等置换（identity permutation）。一个恒等置换的8×8交换单元的排列表达式为： 0，1，2，……7 入线排列表达式为： (0，1，2，……7)

恒等置换（常用I表示）的2进制函数表示为： I(x2x1x0) = x2x1x0 恒等置换的图形表示如图2.6所示。 恒等置换（常用I表示）的2进制函数表示为： I(x2x1x0) = x2x1x0 图2.6 恒等置换的图形表示

b）交叉连接 在交换单元入线数M等于出线数N，并且入/出线数为偶数（N为偶数）的情况下，把相邻编号的2条入线与2条出线交叉连接起来，入线0连接出线1，入线1连接出线0，入线2连接出线3……这种连接方式称为交叉连接，也称为交换置换（exchange permutation），交换置换的入线排列表示式为： (1，0，3，2，……N-1，N-2)

E(xn-1xn-2……x1x0) = xn-1xn-2……x1 交换置换的图形表示如图2.7所示。 交换置换（常用E表示）的2进制函数表示为： E(xn-1xn-2……x1x0) = xn-1xn-2……x1 图2.7 交换置换的图形表示

可以看出，蝶式置换是将输入端2进制编号的最高位xn-1与最低位x0互换位置而得到输出端的2进制编号。 c）蝶式连接 蝶式连接方式也称为蝶式置换（butterfly permutation 一般用β表示），蝶式置换这个名称来自FFT变换的实现时其图形形状如蝴蝶一样。这种连接方式被定义为：β(xn-1xn-2……x1x0) = x0xn-2……x1xn-1 可以看出，蝶式置换是将输入端2进制编号的最高位xn-1与最低位x0互换位置而得到输出端的2进制编号。 同样可以定义子蝶式(subbutterfly)置换β(k)与超蝶式(superbutterfly)置换β(k)： β(k) (xn-1 xn-2……xk+1 xkxk-1……x1x0) = xn-1 xn-2……xk+1 x0xk-1……x1xk β(k) (xn-1 xn-2……xn-k xn-k-1xn-k-2……x1x0) = xn-k-1 xn-2……xn-k xn-1xn-k-2……x1x0

图2.8显示了N=8的β、β(1)与β(1)图形表示。

d）均匀洗牌连接 均匀洗牌置换一般表示为：δ(xn-1xn-2……x1x0) = xn-2xn-3……x1x0xn-1 由此表达式可见均匀洗牌置换是将入线2进制地址循环左移一位，即得到对应的输出端2进制地址。

δ(k) (x n-1 xn-2……xk+1 xkxk-1……x1x0) = xn-1 xn-2……xk+1 xk-1……x1 x0xk 还可以定义子洗牌(subshuffle)连接δ(k)与超洗牌(supershuffle)连接δ(k)： δ(k) (x n-1 xn-2……xk+1 xkxk-1……x1x0) = xn-1 xn-2……xk+1 xk-1……x1 x0xk δ(k) (xn-1 xn-2……xn-k xn-k-1xn-k-2……x1x0) = xn-2……xn-k xn-k-1xn-1xn-k-2……x1x0 图2.9显示了N=8的δ、δ(1)、δ(1)变换图形。 图2.9 N=8的洗牌置换

Ck(x n-1 xn-2……xk+1 xkxk-1……x1x0) e）间隔交叉连接 间隔交叉连接也称为方体置换(cube permutation)，实现了2进制地址编号中第k位位值不同的输入端和输出端之间的连接，定义为： Ck(x n-1 xn-2……xk+1 xkxk-1……x1x0) = x n-1 xn-2……xk+1 xk-1……x1x0 以N = 8为例，共有三种方体置换： C0(x2x1x0) = x2x1 C1(x2x1x0) = x2 x0 C2(x2x1x0) = x1x0

其图形表示如图2.11所示。 2.11 N=8的方体置换

交换单元的性能 对于交换单元，我们通过以下几个指标来描述其特性： （1）容量 交换单元的容量，包含两方面的内容，一个是交换单元的入线与出线数目，一个是每条入线上可以送入交换的信息量大小，如模拟信号的带宽与数字信号的速率。因此交换单元的容量就是交换单元所有入线可以同时送入的总的信息量。

（2）接口 交换单元的各个入线与出线要规定信号接口标准，如速率大小，信号单、双向等。 如果是有向交换单元，那么就有入线与出线的区别，且入线与出线的信息传送方向是单向的，既信息从入线进入然后从出线输出； 如果是无向交换单元，可以说没有入线或出线的区别，信息可以经过交换单元进行双向传送。 如果是模拟交换单元，那么只能交换模拟信号；如果是数字交换单元，只能交换数字信号，当然有的交换单元既能交换模拟信号，又能交换数字信号。

（3）功能 交换单元的基本功能是能在入线与出线之间建立连接并传送信息。从外部看交换单元，主要有3个功能，一个是点到点连接功能，一个是同发功能，还有一个是广播功能，要根据实际情况选择合适的功能。

（4）质量 一个交换单元的质量主要体现在两个方面，一个是完成交换功能的能力，它通常指交换单元完成交换动作的速度，以及是否在任何情况下都能完成指定的连接；另一个是信息是否存在损伤，如信息经过交换单元的时延。这里要说明的是，信息经过交换单元的时延（从入线进入交换单元到从出线输出所经历的时间）是衡量交换单元质量的一个重要的指标，时延越短越好。 信息经交换单元交换时，如果存在出线竞争，交换单元必须设置相应的措施来保证不丢失信息。

如图2.12所示是S1240数字程控交换系统的交换网络所采用的交换单元专用芯片，我们习惯上称它为数字交换单元（Digital Switching Element -- DSE），它有16个双向端口，每个端口接一条双向的32路PCM链路，这个交换单元的容量为512×512，它的接口为双向的PCM数字信号。 图2.12 数字交换单元的性能

2.1.3 时分交换单元 1、时分交换单元的一般构成 相对于空间交换单元而言，时分交换单元的内部只存在一条唯一的通路，该通路由输入复用线上的各个子信道分时共享，从入线上来的各个子信道的信息都必须通过这个唯一的通路才能完成交换。通常人们按照时分交换单元内这个唯一的公共通路是存储器还是总线，将时分交换单元划分为两种类型：共享存储器型交换单元与共享总线型交换单元。

（1）共享存储器型交换单元 共享存储器型交换单元的一般结构如图2.21所示。该交换单元具有N路输入信号（N个时隙）与N路输出信号，作为交换单元核心部分的存储器被划分为N个区域，N路输入信号被放在存储器的N个区域中，然后不同区域的N路信号被读出，形成N路输出信号。 图2.21 共享存储器型交换单元的一般结构

通常共享存储器有两种工作方式：输入缓冲方式与输出缓冲方式。 输入缓冲方式是指存储器中N个区域是与N路输入信号一一对应的，即0~N-1路输入信息分别对应存放在存储器的0~N-1个区域中，并在适当的时候输出到目的输出信道上去。（输出控制方式） 输出缓冲方式是指存储器中N个区域是与N路输出信号一一对应的，即存储器的0~N-1个区域分别对应0~N-1路输出信息。从不同输入信道来的信息如果要交换到输出信道中，那么就把信息放在这个输出信道所对应的存储器的相应区域中，当输出时刻到来时输出信息。（输入控制方式）

（2）共享总线型交换单元 共享总线型交换单元的一般结构如图2.22所示，总线型交换单元有N条入线与N条出线，每条入线都经过各自的输入部件连接到总线上去，同时每条出线也都经过各自的输出部件连接到总线上去。 图2.22 共享总线型交换单元一般结构

共享总线的工作原理是把总线的工作时间划分为N个时间片（我们称其为时隙），在每一个时隙内把总线分给相应入线所对应的输入部件，同时当一个输入部件获得总线上的输入时隙后，就把入线上的信息送到总线上去，与此同时，信息的目的出线相对应的输出部件将总线上的信息读出（到出线），然后从出线上输出信息。

2、时间接线器 时间接线器也称为T接线器，它是一个典型的共享存储器型的交换单元，它的输入是一条同步时分复用线（简称为入复用线），同时它的输出也是一条同步时分复用线（简称为出复用线）。时间接线器主要应用在数字电话交换系统中，用于完成一条同步时分复用线上各个时隙之间话音信息的交换 （时隙交换）。

每个用户固定占用1个时隙 （来话、去话用同一个时隙）

要进行时隙交换，就要有一个能存储话音信息的话音存储器（SM）和一个控制话音存储器的存储和取出的控制设备，称为控制存储器（CM）。 为了形象说明时隙交换原理，下图用两个时序开关控制话音信息的交换

由于输入端的时序开关与时隙相同，可省略； 而输出端的时序开关需要变化（如一次通话完成后，该时隙需要收回），CM反映了这种变化的时序开关

时间接线器由话音存储器（Speech Memory -- SM）与控制存储器（Control Memory -- CM）构成，如下图。 TS1交换到TS8；SM、CM单元个数、单元内容、单元地址（时隙） ；CM特点不变

其中话音存储器用来暂时存放数字编码的话音信息，（SM单元的个数与每个单元大小）话音存储器大小与入复用线（或出复用线）上的时隙数相关，如果一条入复用线（或出复用线）上有n个时隙，那么话音存储器相对应必须有n个单元，由于每个时隙上传输的是8位编码，因此话音存储器每个单元的大小也应该是8位。 例如一个时间接线器它的入复用线（或出复用线）上的时隙数为32，那么该接线器的SM有32个存储单元，每个单元的大小为8比特，话音存储器的容量为32×8比特。

控制存储器用来控制话音存储器的读或写，它存放的内容是话音存储器在当前时隙内应该写入或读出的地址。控制存储器与话音存储器的单元个数相等（等于每线复用的时隙数）（CM单元个数与内容） 每个CM单元的大小与话音存储器的单元数目n（时隙数）有关系，设控制存储器每个单元大小为c比特，那么c至少应该满足条件2c=n，才能控制寻址到话音存储器的所有单元。 假设一条输入或输出复用线上的时隙数为32，那么话音存储器就应具有32个单元，控制存储器也具有32个单元，且每个CM单元大小为5比特，控制存储器的容量就应该为32×5比特。

（2）控制方式 （2种） 控制存储器对话音存储器的控制方式分为：输出控制方式与输入控制方式。 (1) 输出控制方式 （读出控制方式） 在输出控制方式下，时间接线器入复用线上来的信息按照时隙号顺序写入话音存储器相对应的单元中，即第i路时隙的8比特话音存入话音存储器地址为i的单元。 同时对于出复用线来说，第j个时隙到来的时候，总要从话音存储器中某个单元读出信息放到复用线上传输，而从话音存储器中所要读出的这个单元的地址就存储在控制存储器第j个单元中。

上图中，第k个时隙到来的时候，从入复用线上来的信息a存储在话音存储器中的第k个单元中，当第i个时隙到来时，从控制存储器第i个单元中读出地址k，用这个地址访问话音存储器第k个单元，读出信息a，如此完成了入复用线上k时隙到出复用线上i时隙的信息交换，这种将输入线信息顺序写入话音存储器中，在输出时隙到来时控制读出的工作方式就是输出控制方式。

②输入控制方式 （写入控制方式） 如果时间接线器工作在输入控制方式下，当入复用线上第i个时隙到来时，接线器首先从控制存储器第i个单元读出一个地址j，该地址是话音存储器存储i时隙信息的地址，然后接线器把输入复用线上第i个时隙的信息存储在话音存储器的j单元，对于出复用线来说，当第j个时隙到来的时候，话音存储器j单元的信息被顺序读出。

在下图中，当第k个时隙到来时，首先从控制存储器第k个单元中读出SM的地址i，将入复用线上来的信息a存储在话音存储器中的第i个单元中，当第i个时隙到来时，出复用线顺序从话音存储器中读出信息a，如此完成了入复用线上k时隙到出复用线上i时隙的信息交换， 这种将输入线信息控制写入话音存储器中，在输出时隙到来时顺序读出的工作方式就是输入控制方式。

图2.25 时间接线器的写入控制方式

输出控制方式（读出控制方式）实际上是采用输入缓冲的共享存储器型交换单元，它的工作方式可以简单地描述为：顺序写入，控制读出 （针对SM）。 输入控制方式（写入控制方式）实际上是采用输出缓冲的共享存储器型交换单元，它的工作方式可以简单的描述为：控制写入，顺序读出。

对于时间接线器，我们应注意以下三点： a）时间接线器的控制存储器是由控制单元（CPU）写入数据的，实际上控制存储器（CM）就相当于一条同步时分复用线上各个时隙之间信息交换的交换控制表，向控制存储器写入不同的控制信息，就能实现不同时隙间信息的交换。 b）写操作：SM需要在1个周期（125us）写入1次；而CM在整个通话过程中只向其缓存中写入1次； 读操作：每个1个时隙，CM读1次， SM至少读1次。

c）经过时间接线器交换的信息存在着时延，时延最好的情况是入复用线上第i个时隙的信息要交换到出复用线第i+1个时隙（只经过1个时隙的时延）；时延最坏的情况是入复用线上第i个时隙的信息要交换到出复用线上第i-1个时隙，那么从入复用线上来的第i个时隙的信息将会存储在话音存储器中，直到下一帧第i-1个时隙到来时，才从出复用线上输出，其时延为n-1个时隙的时间（n为1帧的时隙数）。

2.1.2 空间交换单元 空分交换单元也称为空间交换单元，一般来说，空间交换单元是由空间上分离的多个小的交换部件或开关部件按照一定的规律连接构成的。从空间交换单元的内部来看，其入线到出线之间存在着多条通路，所有的这些通路可以并行的传送信息，也就是说从不同入线上来的信息可以并行的交换到不同的出线上去。

1、开关阵列 交换单元完成的最基本的功能就是交换。在交换单元内部，要把某条入线上的信息交换到某条出线上去，最简单最直接的方法就是把该入线与该出线在需要的时候直接连接起来。为了做到在需要的时候直接将入线和出线连接起来，人们自然会想到在入线与出线之间加上一个开关，开关接通，则入线与出线连接；开关断开，则入线与出线连接断开。如此构成的交换单元的内部就是一个由大量开关组成的阵列，因此，我们把这样的交换单元称为开关阵列。

开关阵列的开关一般位于入线与出线的交叉点上，它有两种状态：接通与断开。图2 开关阵列的开关一般位于入线与出线的交叉点上，它有两种状态：接通与断开。图2.13表示了一个开关的两种不同状态。如图所示当开关接通的时候，入线与出线就连接在一起；当开关断开的时候入线与出线就不连接。 开关阵列的开关分为两种：单向开关与双向开关，单向开关主要用于有向交换单元，它只允许信息从入线传送到出线；而双向开关一般用于无向交换单元中，它允许信息双向传送。 图2.13 开关阵列中的开关及其两种状态

对于一个M×N的有向交换单元，其开关阵列的实现如图2 对于一个M×N的有向交换单元，其开关阵列的实现如图2.14所示。在入线与出线上的每个交叉点都有一个开关，且开关为单向开关，那么它总共需要M×N个开关。一般把入线i与出线j交叉点的开关记为Kij。如果需要将入线i与出线j连接，只要把开关Kij置为接通状态就可以了。 图2.14 M×N有向交换单元的开关阵列实现

一个N无向交换单元的开关阵列实现如图2.15（a）所示。

可以把实现N无向交换单元的开关阵列与实现N×N有向交换单元的开关阵列相比较，它们的功能基本相同，区别主要是：对于N无向交换单元的开关阵列，1）若入线i与出线j相连，那么入线j与出线i一定相连；2）编号相同的入线与出线之间没有连接关系。N无向交换单元的开关阵列，若采用双向开关实现时，共需要N(N-1)/2个开关 （组合Cn2 ，无序），即有这么多的交叉点。

N无向交换单元的开关阵列若采用单向开关，则其开关阵列的实现如图2.15（b）所示。

相同编号的入线和出线的复合构成了N无向交换单元的信息端。 与N×N有向交换单元的开关阵列结构相似，只是相同编号的入线和出线不需要连接，故没有开关。采用单向开关实现时，共需要N（N-1）（排列，有序）个开关，很明显其开关阵列的开关数要比采用双向开关的多。

一个M×N无向交换单元的开关阵列实现如图2 一个M×N无向交换单元的开关阵列实现如图2.16所示。由图可知，M×N无向交换单元的开关阵列与M×N有向交换单元的开关阵列的实现结构完全相同，所不同的只是其信息端是双向传送信息的并且所使用的开关为双向的。 图2.16 M×N无向交换单元的开关阵列实现

如果一个交换单元的每条入线都能够与每条出线相连接，那么我们称这个交换单元为全连通交换单元；如果一个交换单元的每条入线只能与部分出线相连接，那么我们称这个交换单元为非全连通交换单元。图2.14、图2.16的交换单元是全连通交换单元，图2.15的交换单元是非全连通交换单元。 如果要用开关阵列实现全连通的交换单元，那么所需要的开关数目会比非全连通的多。

开关阵列的特点主要表现在以下几个方面： （1）容易实现同发与广播功能。如果一条入线上的信息要交换到多条出线上，那么只要把这条入线与相应的出线所对应的开关打开就可以了，这样就实现了同发和广播；反之，如果不允许同发和广播，那么每一入线与所有出线相对应的开关只有一个处于连接状态即可。 （2）信息从入线到出线具有均匀的单位延迟时间。信息从任一入线到任一出线经过的开关数是相等的，因而经开关阵列构成的交换单元的信息延迟时间是均等的，不存在时延抖动。

（3）开关阵列的控制简单。构成开关阵列的每一个开关都有一个控制端和一个状态端，用于控制和反映开关的通断情况。开关的状态不外乎“通”和“断”，用两值信号表示就可以了，因而开关阵列的控制简单。 （4）开关阵列适合于构成较小规模的交换单元。当交换单元的入线数M与出线数N较大时交叉点数目会迅速增加，那么相应所需要的开关数目也会迅速增加。比如要构成一个100×80的全连通的有向交换单元，其开关阵列的开关数为8000个之多，这表明实际使用开关数的多少反映了开关阵列实现的复杂度和成本的高低，所以要尽量减少开关的数目。

在实际应用中，一般存在三种开关阵列：继电器、模拟电子开关与数字电子开关。 继电器一般构成小型的交换单元，所构成的交换单元是无向的，可交换模拟和数字信息，其缺点是干扰和噪声大、动作慢（ms级）、体积大（cm级）。 模拟电子开关一般由半导体材料制成，只能单向传送信息，且衰耗和时延较大。但模拟电子开关的开关动作比继电器快得多，构成的交换单元与继电器构成的交换单元相比，体积小，一般用来代替继电器构成小型的交换单元。 数字电子开关由简单的逻辑门构成，开关动作极快且无信号损失，用于完成数字信号的交换，目前得到广泛的应用。

2、空间接线器

空间接线器主要由交叉点开关矩阵与一组控制存储器构成，如图2.19和图2.20所示 2、空间接线器 （1）基本结构 空间接线器主要由交叉点开关矩阵与一组控制存储器构成，如图2.19和图2.20所示 图2.19 空间接线器的输入控制方式 图2.20 空间接线器的输出控制方式

空间接线器的交叉点矩阵，即开关阵列，一般具有相同数量的入线和出线。一个N×N的空间接线器有N条输入复用线与N条输出复用线，N条输入复用线与N条输出复用线共同组成了一个开关阵列，这个开关阵列有N2个交叉点，每个交叉点有接通与断开两种状态，这些交叉点的状态由该输入复用线或输出复用线所对应的控制存储器来控制。

空间接线器的控制存储器也称为CM（Control Memory），它控制每条输入复用线与输出复用线上的各个交叉点开关在什么时候打开或闭合。空间接线器的CM的数量等于输入线数或输出线数，而每个CM所含有的单元数等于输入线或输出线所复用的时隙数。 一个N×N的空间接线器，具有N条输入复用线与N条输出复用线，则其需要N个控制存储器，每个控制存储器对应一条输入复用线或输出复用线，控制该输入复用线或输出复用线上的所有交叉点的接续和断开。

假设每条复用线上一帧有n个时隙，那么每个控制存储器就应该具有n个单元。假设每个CM单元的比特数为m，则m应该满足2m=N（N为入线数或出线数）。 例如一个4×4的空间接线器，有4条输入复用线与4条输出复用线，每条入线与出线复用了32个时隙，那么需要4个（N个）控制存储器，且每个控制存储器有32个单元（每线复用时隙数），每个CM单元的大小为2bit（m比特） 。

（2）控制方式 （2种） 空间接线器的控制存储器控制交叉点矩阵的工作有两种方式：输入控制方式与输出控制方式。 如果控制存储器按照输入复用线配置，即控制每条输入复用线上应该打开的交叉点开关，我们把这种控制方式叫做输入控制方式； 如果控制存储器按照输出复用线配置，即控制每条输出复用线上应该打开的交叉点开关，我们把这种控制方式叫做输出控制方式。 空间接线器的这两种控制方式分别对应了空间接线器的两种工作方式。

①输入控制方式 在输入控制方式下，控制存储器的数量取决于输入复用线数，每条输入复用线对应着相同编号的一个控制存储器；每个CM所含有的单元数等于输入复用线所复用的时隙数；每个CM单元的内容表示输入复用线与所有输出复用线的交叉点开关（出线号），哪一个在该单元所对应的时隙内接通。

图2.19为输入控制方式的空间接线器。该空间接线器的大小为N×N，其控制存储器有N个，图中每一列代表一个控制存储器，用来控制编号相同的输入复用线上的所有开关。每个控制存储器的单元数为n个（行数），标号为0~n-1，分别对应着TS0~TSn-1。 在TS0到来的时候，对于入线0来说，从第0号控制存储器第0号单元读出数据1（出线号），表明在TS0到来的时候，应该打开输入复用线0与输出复用线1相交叉的开关，关闭其它开关，使入线0上TS0时隙的信息a交换到出线1的TS0上去。 注意，空间接线器只能实现不同复用线之间的空间交换，时隙不变。

由此我们还可以看到，在TS0内，入线1上的信息b交换到出线N-1上去，而入线N-1上的信息c交换到出线0上去。各条入线上的TSn-1时隙上的信息同样在控制存储器的控制下完成了交换。

②输出控制方式 在输出控制方式下，控制存储器的数量（列数）取决于输出复用线的数量，每条输出复用线对应着相同编号的一个控制存储器；控制存储器所含有的单元数（行数）等于输出复用线所复用的时隙数；每个CM单元的内容表示对应输出复用线上的所有交叉点(入线号)，哪一个在该单元所对应的时隙内接通。

图2.20为输出控制方式的空间接线器。该空间接线器的大小为N×N，其控制存储器有N个，图中每一列代表一个控制存储器，用来控制编号相同的输出复用线上的所有开关。每个控制存储器的单元数为n个，标号为0~n-1，分别对应着TS0~TSn-1。在图中，出线0由第0号控制存储器（图中CM左起第一列）控制着其与入线的所有交叉点， 当TS0到来的时候，其对应的第0号单元（图中第一列第一个单元）的数据为1，表明在TS0时隙内，应该打开出线0与入线1相交叉的开关，关闭其它开关，使入线1上TS0时隙的信息b交换到出线0的TS0上去。 由此我们还可以看到，在TS0内，入线0上的信息a交换到出线N-1上去，而入线N-1上的信息c交换到出线1上去。

空间接线器不管工作在哪种方式下，都具有如下的特点： ①只完成空间交换，不进行时隙的交换。即完成输入复用线与输出复用线相同时隙内信息的空间交换。 ②空间接线器按时分方式工作。空间交换单元的输入线和输出线都是时分复用线(PCM时分复用)，交叉点矩阵的各个开关均按照复用时隙而高速接通和闭合，因而我们说它按照时分方式工作（在1个时隙内完成）。 空间接线器经常采用“输出控制方式”，即CM控制输出线，这样便于实现组播。

3、数字交换单元 数字交换单元（DSE）是共享总线型交换单元的典型代表，可以用来组成大规模的数字交换网络（DSN）。 （1）DSE的结构 DSE可完成16条双向PCM复用线之间的信息交换。DSE结构如图2.26所示，它的内部有16个双向端口，每个双向端口接一条双向32路的PCM线路，每路子信道16bit，该条PCM线路速率为4096Kbit/s，这16个双向端口通过一条时分复用总线（TDM）连接在一起。 图中为16条PCM入线，16条PCM出线，相当于512X512的话音交换

图2.26 数字交换单元结构

把这16个端口从0到15编号，把每个双向的端口分为RX（PCM链路接收部分）与TX（PCM链路的发送部分）两个部分，并且16个双向端口的RX与TX分别从0到15编号。

RX的输入同步器用于完成输入信息的帧同步和位同步，(如：因为各个电话到交换机的距离不同，因此各路话音存在时延，所以需要同步调整； 端口存储器有32个单元，每个单元与该RX上输入PCM的32个时隙相对应；单元大小为4bit，用来存储目的端口号； 信道存储器也具有32个单元，每个单元5bit，用来存储目的信道号（时隙号）。 小结： 在Rx的每个时隙有1个端口存储器的单元和1个信道存储器的单元，用于为该路话音选择目的端口和目的信道

TX的话音存储器有32个单元，每个单元16bit，用来存储TX上PCM线路相应时隙所要输出的数据和控制信息； 端口比较器将TDM上的端口号与本端口号相比较，以确定数据总线上的数据是否是到本端口的； 发送控制器用于TX内部控制 （如：控制话音RAM的读写、控制路由选择、信道选择等）。

DSE中TDM时分复用总线主要包括这样几种总线 1）数据总线（16bit），用来传递PCM链路上每个时隙的16位数据，它将RX的输入同步器与TX的话音存储器连在一起，数据总线由16个RX分时复用； 2）端口总线（4bit，共16个端口），用来连接RX的端口RAM、TX的端口比较器与TX的发送控制器； 3）信道总线（5bit, PCM链路共32个时隙，即32个信道），用来连接RX的信道存储器与TX的发送控制器。 此外还有控制总线、时钟线、证实线等。

（2）工作原理 PCM链路有32个时隙，即32个信道，注意它的每个信道传输16比特的信息，在这16bit的信息中，除了8bit的用户话音/数据信息外，还包括了用于选路的控制信息，我们一般把这16bit的信息称为信道字，DSE就是根据从PCM链路接收到的信道字进行工作的。

信道字主要有以下四种类型 （通过F、E两位来区分） 数据信道字：包含了话音与数据信息，一般只用到了16bit中的8位，用来传送数据； (FE=11) 置闲信道字：使占用的话路置为空闲，用来拆除已经建立的连接。(FE=00) 换码信道字：用于表示信道字中有处理机之间相互传送的控制信息。 (FE=10)

下面举例说明DSE的工作原理，见图2.27。假设RX3的PCM线路时隙5（信道5）上的信息a要交换到TX8上的时隙19（信道19）上输出，则交换的过程如下： 数 据 总 线 端 口 信 道 TDM总线 端口存储器 输入同步器 信道存储器 a TS 5 TX8 31 19 发送控制器 比 较 器 话音存储器 8 图2.27 DSE信息交换过程

1）当RX3的TS5处于空闲状态的时候，从PCM链路TS5上收到选择信道字，其中包括了该信道上的信息要交换到的目的地址（目的端口号、目的时隙号）：端口8的TS19； 当TX8的端口比较器从端口总线上得到数据与自己的端口号8比较成功，同时检查19信道为空闲时，通过证实总线向RX5回送一个证实消息（ACK）；

3）当RX3收到TX8的证实后，把选择信道字中的（目的）端口号存入端口存储器中的第5个单元（单元号与时隙号相对应），同时把信道号19存入信道存储器中的第5单元（单元号与时隙号相对应）。 这样，在DSE内部，RX3的第5个信道（TS5）就与TX8的第19个信道（TS19）之间建立了一条内部通道；（内部通路建立） 4）当RX3在TS5上接收到数据信道字后，从端口存储器第5个单元读出里面的内容8（端口号）送到端口总线上去，从信道存储器第5个单元读出里面的内容19（信道号）送到信道总线上去，表明RX5的TS5上信息要交换到TX8的TS19上去，同时将数据信道字中的话音信息a送到数据总线上去；

5）当TX8把端口总线上的数据8与自己的端口号比较，发现一致后，先从信道总线上读出信道号19，把数据总线上的话音信息a存放到话音存储器的第19个单元（也就是从信道总线上读出的信道号所对应的单元）中； （话音信息发送：）当TX8上TS19到来的时候，就将话音存储器中的第19个单元的信息a放到PCM线上输出，从而完成交换。实际上在这里话音存储器的工作方式是：控制写入、顺序读出。

DSE是比较复杂的交换单元，它不仅能完成不同复用线之间信息的交换（空间交换，通过端口号），还能完成不同时隙之间的信息交换（时隙交换，信道号），即它同时具有空间交换功能和时间交换功能，因而我们也称其为时空结合交换单元。

2.2 交换网络 2.2.1 交换网络的基本概念 交换网络的基本结构如图2.28所示，可以说交换网络是由交换单元按照一定的拓扑结构扩展而成的，这样构成的交换网络也称为互连网络。交换网络从外部看，也是有一组输入端与一组输出端，我们将其分别称为交换网络的入线与交换网络的出线，如果交换网络有M条入线与N条出线，我们把这个交换网络称为M×N的交换网络。 图2.28 交换网络的一般结构

交换网络也有多种分类方法，下面我们来看看交换网络的分类。 （1）单级交换网络与多级交换网络 单级交换网络是由一个或者多个位于同一级的交换单元所构成的交换网络，即需要交换的信息从交换网络入线到交换网络出线只经过一个交换单元，并且当同一级有多个交换单元构成时，不同交换单元的入线与出线之间可建立连接。

图2.29所示就是一个基于均匀洗牌交换的单级交换网络，该网络由四个2×2的交换单元构成，需要交换的信息从入线到出线只经过一个交换单元，并且这四个交换单元的入线和出线之间可建立连接。 图2.29 单级交换网络

如果一个多级互连网络的交换单元可以分为k级，顺序命名为第1级、第2级、…第k级，并且满足以下条件： 所有输入端都只连接到第1级交换单元的入线； 所有第1级交换单元的出线只连接到第2级交换单元的入线； 所有第2级交换单元的出线只连接到第3级交换单元的入线； …… 以此类推，所有第k-1级交换单元的出线只连接到第k级交换单元的入线； 所有交换网络的输出端只连接到第k级交换单元的出线上。

那么我们称这样的交换网络为k级交换网络或者k级互连网络。k级交换网络的应用十分广泛。下面将介绍的CLOS网络，banyan网络，TST网络，以及benes网络，就属于k级交换网络。图2.30显示了一个3级的banyan网络。 图2.30 3级交换网络

（2）有阻塞交换网络与无阻塞交换网络 交换网络的阻塞是指从交换网络不同输入端来的信息在交换网络中交换时发生了对同一公共资源争抢的情况，这时在竞争资源中失败的信息就会被阻塞，直到这个公共资源被释放。图2.31是一个两级交换网络， 假设在同一时刻，入线0有信息要交换到出线2，入线1有信息要交换到出线3，那么此时就会发生争强内部链路的情况，在竞争中失败的信息被阻塞 (内部竞争)。 图2.31 交换网络的阻塞

对同一公共资源的竞争一般有两种情况，一种为内部竞争，一种为出线竞争。图2 对同一公共资源的竞争一般有两种情况，一种为内部竞争，一种为出线竞争。图2.31中所示的竞争为内部竞争，同时要交换的两路信息同抢交换单元内部的通路资源；出线竞争是不同入端来的信息同时争抢交换网络同一个输出端口而发生的竞争（多对1）。 我们把因为内部竞争而发生的阻塞称为内部阻塞，把存在内部阻塞的交换网络称为有阻塞交换网络，把不存在内部阻塞的交换网络称为无阻塞交换网络。

对于无阻塞交换网络，一般存在三种不同意义的无阻塞交换网络： a）严格无阻塞交换网络：在这种交换网络中，只要连接的起点与终点是空闲的，则任何时候都可以在交换网络中建立一个连接。 b）可重排无阻塞交换网络：在这种交换网络中，任何时候都可以在交换网络中直接地或间接地对已有的连接重新选路来建立一个连接，只要这个连接的起点或终点处于空闲状态。 c）广义无阻塞交换网络：如果在顺序建立各个连接时遵循一定的规则来选择路径，从而在任何时候都可以在交换网络中建立一个连接，只要这个连接的起点与终点处于空闲状态。

（3）单通路交换网络与多通路交换网络 在单通路交换网络中，任一条入线与出线之间只存在唯一的一条通路，也就是从一个输入端口来的信息要交换到一个输出端口，信息只能在唯一的一条通路上传送，没有其他可供选择的通路。 在多通路交换网络中，任一条入线与出线之间存在着多条通路。如果信息要从一个输入端口交换到一个输出端口，可以选择这多条通路中的一条来进行交换，而不像单通路交换结构只有唯一的一条通路。

单通路交换网络不存在内部阻塞，控制简单。多通路空分交换网络比单通路空分交换网络复杂，但是多通路交换网络有很好的容错性能。 多通路交换网络的概念如图2.32所示，图中信息要从交换网络入线1交换到出线5，可以选择多条路径（图中示例出了两条路径），而不是只有唯一的一条。 单通路交换网络不存在内部阻塞，控制简单。多通路空分交换网络比单通路空分交换网络复杂，但是多通路交换网络有很好的容错性能。 图2.32 多通路交换网络

（4）时分交换网络与空分交换网络 与交换单元的分类方法一样，交换网络也可以分为时分交换网络与空分交换网络。 时分结构的基本特征是所有的输入与输出端口分时共享单一的通信通路，具有时隙交换功能； 而空分结构的基本特征是可以在多对输入端口与输出端口间同时并行地传送信息，具有空间交换的功能，CLOS网络与banyan网络属于典型的空分交换网络。 在电话交换系统中广泛应用的是时空结合的交换网络，即既能完成时隙交换也能完成空间交换，如TST网络和DSN网络。

2.2.2 CLOS网络 研究构成交换网络的交叉点数目随入线、出线数目增长较慢的方法（提高可扩展性），一直是交换领域研究的重点课题，这些方法的基本思想都是采用多个较小规模的交换单元按照某种连接方式连接起来从而构成多级交换网络。CLOS网络就是其中的一种，如图2.33所示 图2.33 三级CLOS网络

它由CLOS首次提出，一般使用在大型电话交换系统中，属于多级交换网络。假设CLOS网络有M条入线与N条出线，如果M=N，我们称这样的CLOS网络为对称的CLOS网络，否则为非对称的CLOS网络。对称的CLOS网络使用广泛，在这里我们主要介绍对称的CLOS网络，下面所介绍的CLOS网络除非特别说明一般指对称的CLOS网络。

1、 3级CLOS网络 3级CLOS网络非常容易理解，而且应用广泛，除非特别指明，我们一般说CLOS网络也指3级CLOS网络，更多级的CLOS网络可以由3级CLOS网络递归构造而成。一个N×N的3级CLOS网络的基本结构如图2.33所示，N为入线数与出线数。 图2.33 三级CLOS网络

其中，入线N（第1级）被划分为r组，每组有n条入线，即N = r×n。第一级共有r个n×m的交换单元，r组入线正好分别接入交换网络中第一级r个交换单元；假设第二级也恰好有m个r×r的交换单元，那么第一级的每个交换单元的m条出线，分别接到第二级的m个交换单元。第二级的每一个交换单元共有r条输入线；第三级交换单元是m×n规模的，共有r个，第二级交换单元的r个输出分别连接到这第三级的r个交换单元，这就是一个3级CLOS网络。

假设CLOS网络的第K级交换单元的个数为nk，K级每个交换单元的输入线数和输出线数分别为ik、ok，则对于一个N×N的3级CLOS网络，有下列关系存在： n1= N/i1 （上图中n1＝r, i1=n），o1= n2 (上图中o1＝m )，i2= n1，o2= n3，i3= n2，n3= N/o3； 对于一个N×N的K级CLOS网络，有下列关系存在： n1= N/i1，ok= nk+1，ik= nk-1，nk= N/ok。 从图2.33可知，n1= n3= r，i1= o3= n，o1= i3= m，即N×N的3级CLOS网络是左右对称的，这也是对称的CLOS网络名称的由来。CLOS网络属于多通路交换网络，在一个入线与出线对之间存在着多条通路。

2、3级CLOS网络严格无阻塞条件 在图2.34中，该CLOS网络的第1级交换单元的入线数与第3级交换单元的出线数均为n，即i1= o3= n，第二级的交换单元的个数n2= m。 图2.34 CLOS网络的无阻塞条件

假如我们要确立一条从a到b的信息交换通路，那么最不利的情况是：第一级与a相连的交换单元中除去a之外所有剩余的n-1条入线均有信息要交换，那么第一级与a相连的交换单元中n-1条输出线均处于忙状态；并且所有的n-1条输出线都连接到第二级不同的交换单元上；最后一级与b相连的交换单元除去b以外所有的n-1条输出线也均有信息要交换出来，并且对第二级来说需要另外的n-1个交换单元，而且这些交换单元都要有一条出线连接到与b相连的交换单元上。

那么在最坏情况下，总共需要（n-1）+（n-1） = 2（n-1）个可供选择的第2级交换单元，这时候为了确保链路无阻塞，完成a到b的信息交换，至少还应该存在一条空闲链路，即中间级交换单元要有（n-1）+（n-1）+1 = 2n-1个，因此我们得出3级CLOS交换网络严格无阻塞的条件是： m ≥ 2n – 1 （m为第2级交换单元的个数，n为第1级或第3级中每个交换单元的线数）

3、3级CLOS网络可重排无阻塞条件 我们先来看看3级CLOS网络可重排无阻塞的概念，如图2.35所示，其中3级CLOS网络的n2=2，i1=o3=2，显然，不满足严格无阻塞条件。 图2.35 n2=i1=o3=2的3级可重排CLOS网络

图2.35（a）所示，假设在某一时刻，入线0到出线3的连接经过路径C1，入线2到出线0的连接经过了路径C2，那么在这个时刻，假设要建立入线1到出线1的连接以及从入线3到出线2的连接，就会发生阻塞。 但是有可能重新调整一下已有的从入线2到出线0的连接，使其由路径C2变成路径RC2，这样我们就会发现调整后入线1到出线1以及入线3到出线2的连接就能够建立了，如图2.35（b）虚线所示。这样的网络就是可重排无阻塞的CLOS网络，它可对已有路径进行重排使得有阻塞的CLOS网络成为无阻塞的网络。图2.35是3级可重排无阻塞CLOS网络。

设n2=m，i1=o3=n，Slepian-Duguid定理给出了对称3级CLOS网络可重排无阻塞的条件是m≥n，其中m为CLOS网络第2级所需要的交换单元的个数，n为CLOS网络第1级交换单元入线数或第3级交换单元的出线数。

4、3级CLOS网络规模 下面来看看3级CLOS交换网络规模。让我门回到图2.33，假设CLOS交换网络的交换单元为开关阵列结构，设3级CLOS交换网络所需要的交叉点数目为C3，那么 C3 = 2 × N × m + m （N/n）2 其中N为入线（出线）数目，m为CLOS网络第2级所需要的交换单元个数，n为CLOS网络第1级交换单元入线数目或第3级交换单元出线数目。假设CLOS网络为严格无阻塞交换网络，那么m=2n-1，就有 C3 = 2 × N × （2n - 1）+（2n - 1）（N/n）2

C3 = 3 × N ×（2N1/2 - 1） = 6 × N3/2-3N = O（N3/2） 可以知道，采用3级CLOS交换网络的复杂度为O（N3/2），比全部采用开关阵列来实现的N×N交换网络O(N2)要好，并且同样满足无阻塞的需求。3级CLOS交换网络有很高的可靠性，因为它是多通路的，而不是单通路的。

对于3级CLOS交换网络，有两种方法可以减少内部竞争，一是增加中间级交换单元的数量来增加内部通路数，二是采用随机选路方法，在中间级交换单元内部设置缓冲，但这种方法要求在输出端口采用一定的机制来保证信息的顺序性。

2.2.3 TST网络 1、TST网络结构 TST交换网络结构如图2.36所示 ,该TST网络具有32条双向时分复用线，并且每条时分复用线上有32个时隙，注意TST交换网络编号相同的入线与出线共同组成一条双向时分复用线。TST交换网络的第1级有32个T接线器，分别连在每一条输入线上（每条输入线一个T接线器）；第2级为一个32×32的S接线器，第3级由32个T接线器组成，分别连在每一条输出线上。

图2.36 TST交换网络 ... a 2 31 5 21 CMC A B 复用线0 复用线31 b 读出控制 输入控制 写入控制 第1级 31 5 21 CMC A B 复用线0 复用线31 b 读出控制 输入控制 写入控制 第1级 第2级 第3级 TS CMA SMA SMB CMB

在图2.36中，TST交换网络的第1级T接线器采用的是输出控制方式，第3级T接线器采用了输入控制方式。一般情况，为了方便交换的控制，TST网络的两级T接线器通常采用不同的工作方式，当然对于第1级和第3级T接线器也可分别采用输入控制方式和输出控制方式。对于中间级S接线器，采用什么控制方式都可以，在图2.36中采用了输入控制方式。

2、TST网络工作原理 下面我们以图2.36为例来说明TST网络是如何工作的。假设复用线0（输入端口0）上TS2与复用线31（输出端口31）上TS31存在信息交换，注意这是两个方向上的信息交换：A→B与B→A方向。 （1） （A→B，选择内部时隙）：在中间级S接线器上应选择一个对其入线0与出线31都空闲的内部时隙进行A→B方向的信息交换，假设这个内部时隙为TS5；中间级S接线器同时还要选择一个对其入线31与出线0都空闲的内部时隙进行B→A方向的信息交换，假设这个内部时隙为TS21；

最后由第3级T接线器完成复用线31上由内部时隙TS5到最终输出时隙TS31上的信息交换，为此在CMB31中第5个单元写入31； （2） （A→B，通路建立）： 那么第1级与复用线0相连的T接线器的工作目的就非常明显了，它的工作是要将复用线0上TS2来的信息交换到内部时隙TS5上去，为此在它的CMA0中第5个单元中写入2； 当内部时隙TS5到来的时候，中间级S接线器完成该信息从复用线0（入端口0）交换到复用线31（出端口31），为此在S接线器中CMC0中第5个单元写入31； 最后由第3级T接线器完成复用线31上由内部时隙TS5到最终输出时隙TS31上的信息交换，为此在CMB31中第5个单元写入31；

（3）（ A→B，话音传输 ） 第1级（T接线器）：复用线0 （输入端口0）的 TS2到来时，TS2上信息a按顺序写入复用线0对应的第1级T接线器（输出控制）SMA0的第2个单元。当TS5时隙到来时，从CMA0中第5个单元读出数据2，即将SMA0中第2个单元信息a放到内部时隙TS5上去； 第2级（S接线器） 中间级S接线器（输入控制）从CMC0中第5个单元读出数据31，打开入复用线0与出复用线31之间的开关，完成不同复用线上相同内部时隙TS5的信息交换； 第3级（T接线器）：复用线31对应的最后一级T接线器（输入控制）从CMB31中第5个单元读出数据31，把TS5上来的信息a写入SMB31的31号单元中；最后当复用线31的TS31到来的时候，从SMB31的31号单元中顺序读出信息a输出。 完成A→B方向上的信息交换。

（4）（ B→A ，选择内部时隙和通路建立）与上面从A→B方向上信息交换的过程相似，从B→A方向上的信息交换将通过内部复用线31与内部复用线0上共同的内部时隙TS21完成信息交换。此时，CMA31中第21个单元中写入31，CMC31中第21个单元写入0，CMB0中第21个单元写入2；

（5）（ B → A ，话音传输 ）： 第1级 T接线器：当复用线31的 TS31到来时，TS31上信息b按顺序写入复用线31对应的第1级T接线器（输出控制）SMA31的第31个单元。当TS21时隙到来时，从CMA31中第21个单元读出数据31，即将SMA31中第31个单元信息b放到内部时隙TS21上去； 第2级 S接线器：中间级空间接线器（输入控制）从CMC31中第21个单元读出数据0，打开入复用线31与出复用线0之间的开关，完成不同复用线上相同内部时隙TS21的信息交换； 第3级 T接线器：复用线0对应的最后一级T接线器（输入控制）从CMB0中第21个单元读出数据2，把TS21上来的信息b写入SMB0的2号单元中；最后当复用线0的TS2到来的时候，从SMB0的2号单元中顺序读出信息b输出，完成B→A方向上的信息交换。

如果第1级T接线器采用输入控制方式而第3级T接线器采用输出控制方式，同时中间级的S接线器采用输入控制方式不变，这时候得到TST网络的另一个实现方案，如下图 ，它同样可完成复用线0上TS2与复用线31上TS31的信息交换。

关于TST网络，有几个方面必须注意： （1）交换网络一般是建立双向通路，即除了建立上述A→B方向上的信息传输，还要建立B→A方向上的信息传输，因此内部时隙的选择一般采用“反相法”，即两个方向的内部时隙相差半个帧（该帧是指TST网络输入线或输出线的复用帧）。 在图2.36和图2.37的TST网络中，复用帧大小为32，半帧为16时隙，故A→B方向上选择了内部时隙TS5，那么B→A方向上的内部时隙就是TS21（16+5=21）。一般地，设：TST交换网络输入线或输出线的帧为F，选定的A→B方向上的内部时隙为TSA→B，则B→A方向上的内部时隙为TSB→A=TSA→B+ F/2。

（2）在一般情况下，TST网络存在内部阻塞，但概率非常小，大概是10-6。 （3）构成TST网络的第1级T接线器与第3级T接线器一般采用不同的控制方式，但无论采用输入控制方式，还是输出控制方式，除了操作方式不同外，本质是一样的。

2.2.4 DSN网络 1、DSN结构 DSN是一个多平面结构网络，其平面最多可有4个，同时它又是一个多级交换网络，级数最多可以达到4级。对于一个4级的DSN，第1级称为入口级，其余3级称为选组级，DSN的每一级都由相同的DSE构成。其网络结构如图2.38所示。 2..38 数字交换网络（DSN）

（1）入口级 入口级也叫做选面级，它是由若干对DSE组成的，这些DSE可称为接入交换器（AS）。每个AS的16个端口接16条32时隙的PCM线路，其中端口0-7与端口12-15（图中入口级DSE左侧标出）用来连接各种终端模块，端口8-11（图中入口级DSE右侧标出）分别接到选组级，也就是第2级的4个平面。 入口级有512对DSE，共1024个DSE，每个DSE的端口8、9、10、11分别接到第1个平面、第2个平面、第3个平面和第4个平面的选组级。

（2）选组级 选组级有3级（即DSN的第2、3、4级），前两级每级有16组，每组8个DSE ，最后一级只有8组，每组8个DSE。前两级DSE的端口0-7与前一级DSE相连，端口8-15与后一级DSE相连；最后一级DSE的16个端口都与前一级DSE相连。注意，选组级的前两级，即第2、3级之间组号相同的两级间进行交叉连接（组内交换），选组级的后两级即第3、4级是不同组之间进行交叉连接（组间交换）。

2、DSN工作原理及其特点 在DSN中，两个终端之间的信息交换，可以只经过入口级，也可以经过选组级。如果两个终端模块同时连接在入口级的同一个DSE上，那么信息就可以只通过该入口级的DSE交换。如果两个终端模块不是连接在入口级的同一个DSE上，那么就要经过DSN的选组级进行信息交换了。 DSN入口级的每个端口都具有唯一的网络地址，不同端口之间连接的建立是根据目的端口的网络地址逐级选路进行的。该网络地址有13比特的编码，分为A、B、C、D四部分，分别对应着DSN的1~4级。

A：4比特，对应于第1级，表示终端模块与AS连接的端口号（0~7，12~15，共12个）。 B：2比特，是第二级DSE入口端的端口号，表示AS对连接到第二级DSE的4对端口中的哪一对（0－7），有4种组合，需2bit。 C：3比特，是第三级DSE入口端的端口号，第三级DSE有8个端口（0－7）与第二级DSE相连，故有8种组合，需3bit。（第二级与第三级之间为组内交换，第二级每组有8个DSE，第二级第i个DSE的所有出线（8－15）分别连接到第三级本组内8个DSE的第i个入口。） D：4比特，是第四级DSE的端口号，第四级DSE有16个端口，均可与第三级DSE相连，故有16种组合，需4bit

当某一终端模块要与另一终端模块通过DSN建立通路连接时，就将自己（源端口）的网络地址与目的端口的网络地址相比较： 若D相同，C不同，说明两个终端模块之间所建立的通路连接位于同一组内，连接的建立只涉及到选组级的第2、3级； 若D、C相同，B不同，则说明两个终端模块之间所建立的通路连接经过第2级的同一个DSE，该通路的建立折回点在第2级； 若D、C、B相同，只有A不同，此时通路的建立只经过网络的第1级。如此通过网络地址的比较确定通路的折回点，并发送选择命令进行逐级选路，从而建立起通路连接，完成交换功能。

DSN具有以下的特点： （1）DSN是一种单侧折叠式网络。 DSN网络与我们前面介绍的其它网络不同，它所有的端口不像双侧型网络那样分为输入侧和输出侧，而是位于同一侧，DSN网络的最后一级，如图2.38中的第4级为网络的折叠中心，DSN的任一端口输入的信息在网络的相应级上折回到目的输出端口。当一个输入端口要与一个输出端口建立连接时，可根据目的输出端口的地址（唯一的目的网络地址），来决定接续通路需要的网络级数，即信息在DSN网络中的折回点在哪一级。

（2）DSN可自选路由。 在前面章节我们介绍了构成DSN的DSE的结构与工作原理，我们知道DSE本身具有通路选择和控制功能，因而它不需要设置交换网络的集中控制处理机来控制其一步步的交换，而是根据分布在各个终端模块中的终端控制单元送来的选择命令字（信道字，16bit）等控制信息，由其硬件来完成选路，进而实现交换功能，因而DSN具有自选路由功能。

（3）DSN的扩展性好。 DSN网络采用多平面、多级结构，当容量增加时可通过扩充DSN网络的级数（最多4级）来增加端口数，当话务负荷增加时可通过扩充DSN网络的平面数（最多4个）来均匀分担话务负荷，并且这种扩充不影响网络结构和系统运行，因而由较小规模的交换网络扩展为较大规模的交换网络方便灵活。 （4）DSN采用逐级推进的选试方式，能承受较大话务量 DSN由1到4级组成，如果两个终端要进行信息交换，那么DSN将采用逐级试选的方式，对每一级进行试选路，直到两个终端所在的端口之间能建立起连接进行信息交换。

2.2.5 banyan网络 基于banyan的交换网络（Banyan-Based Switches）是具有多级结构的交换网络，它覆盖范围较广，包含有许多子类。在这类网络中，如果任何一条入线到任何一条出线之间的通路都经过L级，即只有相邻级之间才有链路相连，则我们称这种banyan网络为L级banyan网络。在L级banyan网络中，如果构成网络的所有交换单元都相同，则为规则banyan（regular banyan）网络，否则为不规则banyan（irregular banyan）网络。如果规则banyan网络的每个交换单元的入线数与出线数相等，那么称此规则banyan网络为矩形banyan网络。

在实际应用中，我们更多使用的是由2×2的交换单元构成的矩形banyan网络，它是多级、空分、单通路的交换网络，人们一般将其简称为banyan网络。在后续章节中，如果不加特别说明，banyan网络就是指这样的网络。banyan网络应用广泛，最早应用于并行计算机领域，目前在电信领域的ATM交换机中得到广泛的应用，它适于统计时分复用信号和异步时分复用信号的交换。

其中直连与交换两种状态是交换网络最常用的，只有这两种功能的交换单元我们把它称为2×2两功能交换开关 1、交叉连接单元 banyan网络由若干个2×2的最小交换单元构成，这样的2×2交换单元也称为交叉连接单元。交叉连接单元是具有2条入线和2条出线的电子开关元件，它在不同的控制信号的作用下，工作在不同的状态，来实现2条入线和2条出线之间的不同互连。交叉连接单元有5种工作状态，如图2.39所示。 其中直连与交换两种状态是交换网络最常用的，只有这两种功能的交换单元我们把它称为2×2两功能交换开关 图2.39 交叉连接单元的工作状态

2、banyan网络及其特性 图2.40表示了N=8的由2×2 交换单元构成的3级banyan网络。从图中可以看出，banyan网络的第1级交换单元与第2级交换单元采用蝶式连接，第2级交换单元与第3级交换单元为子洗牌连接。 图2.40 8×8的3级banyan网络

banyan网络结构具有以下特点： （1）banyan是基于树型结构的。 每个输入端通过3级交换单元均可以到达任何输出端，这样就构成了以某一输入端为根节点，以所有输出端为叶子节点的树型结构。 （2）banyan网络的级数k = log2N，每级有N/2个交换单元。 （3）banyan网络的构成具有一定的规律。

观察图2.40的8×8的3级banyan网络，我们可以看到，它的第2、3级是由两个4×4的2级banyan网络构成，其第1级是由4个2×2的交换单元组成，因而我们可以采取有规则的方法使用较小规模的banyan网络来构成较大规模的banyan网络。 一般的方法是：设已有N×N的banyan网络，要构成2N×2N的banyan网络，则需要2组N×N的banyan网络，以及N个2×2的交换单元，并且使第1组N×N的N条出线分别与N个2×2交换单元的某一入线相连，使第2组N×N的N条出线分别与N个2×2交换单元的另一入线相连。

图2.41，表示了将两个8×8的banyan网络扩展成16×16的banyan网络的方法。

具体做法是在2组8×8的banyan网络的基础上，加上了一组8个2×2的交换单元，并且第1个8×8的banyan网络的8条输出线分别与这8个2×2的交换单元的1号入线相连接，而另一个8×8的banyan网络的8条输出线分别与这8个2×2的交换单元的2号入线相连接，从而构成了一个16×16的banyan网络。

（4）banyan网络具有唯一路径特性。 如果网络的任何一条入线与任何一条出线之间都有一条路径并且仅有一条路径，则称该网络具有唯一路径特性。假设N×N的banyan网络具有唯一路径特性，则对于2N×2N的banyan网络，由其有规则的构成方法可知，其第2级到第3级2N个2×2交换单元的任一条出线有且仅有一条路径，因而2N×2N的banyan网络也具有唯一路径特性，又由于最小的banyan网络是4×4的banyan，显而易见由其按上诉方法构成的banyan网络具有唯一路径特性，因此banyan网络具有唯一路径特性。

（5）banyan网络具有自选路由的特性。 我们在前面谈到banyan网络是基于树型结构的，而且还是2叉树结构的，即在任一级的交换单元上，一条输入线上的信息可有两条输出选择，这两个输出选择可用二进制的0和1来表示。此外，banyan网络的级数k = log2N，即若用2进制来表示输出线编号0~N-1，则所需的二进制位数与网络的级数相等，因而每一位二进制可与网络的每一级相对应。因而banyan网络可实现自选路由，方法是给进入交换网络要进行交换的信息加上选路标签，该标签就是信息要交换到的目的输出线号的二进制值，每一级交换单元根据选路标签中的二进制值的相应位来选路，该位二进制的值为0则选0号出线，为1则选1号出线，网络的第1、2、……、k级分别与二进制值的由高到低位相对应着。

在图2.42中，入线4要将信息交换到出线5，该信息使用出线5的2进制编码101作为选路标签。banyan网络中的第1、2、3级交换单元分别根据选路标签中的最高位、第2位和最低位二进制代码进行选路，选路标签中相应位为0时，交换单元将信息送往上面的那条出线（0号线），当选路标签中相应位为1时，交换单元把该信息送往下面的那条出线（1号线），就这样banyan网络自动把该信息交换到二进制编码为101的出线5上。

图2.42 banyan网络的自选路由特性 图2.43 banyan网络的内部竞争

（6）banyan网络具有内部竞争性。 banyan网络的任意一条入线到任意一条出线之间都具有唯一的一条通路，但各个入线与出线之间的单通路并非是完全分离的，会有公共的内部链路，因而内部竞争是不可避免的。如图2.43所示，在某一时刻，信息要从入线0交换到出线3，同时还有信息要从入线2交换到出线2，因而在这一时刻会在第2级与第3级的公共链路上产生竞争，发生阻塞。banyan是有阻塞的网络。

下面我们来看一看delta网络，如图2.45所示，它是一个由2×2的交换单元构成的3级delta网络，该网络的规模是8×8。这种8×8的3级delta网络也属于banyan类网络中的一种。

delta网络的定义是这样的：delta网络具有k级的交换网络，其网络规模为ak×bk，ak为网络的入线数，bk为网络的出线数，它由a×b的交换单元构成，a为交换单元的入线数，b为交换单元的出线数。delta网络级间互连一般采用有规则的均匀洗牌方式连接。图2.46中的交换网络就是一个32×22的delta网络。 2.46 32×22 delta网络

图2.47 batcher排序器（路由标签大的信息往箭头方向送） 4、Batcher-Banyan网络 为了满足banyan网络的无阻塞条件，我们可以在banyan网络前加入排序网络—batcher网络，构成Batcher-Banyan网络（B-B网络）。 Batcher网络是由被称为batcher排序器（sorter）的2×2排序器构成。Batcher排序器如图2.47所示，它实际上是一个两入线/两出线的比较单元，分为向上排序器与向下排序器两种 图2.47 batcher排序器（路由标签大的信息往箭头方向送）

在将入线上的信息的选路标签进行比较后，向上排序器将路由标签大的信息送到输出端上面那条输出线，向下排序器将路由标签大的信息送到输出端下面的那条输出线，即前者是按路由标签升序排列，后者是按路由标签降序排列，当排序器的输入只有一个时，则排序器将它作为选路标签小的信息来处理。

有了向上排序器与向下排序器两种batcher排序器，就可以构成batcher排序网络，在batcher排序网络后面加上banyan网络，可构成Batcher-Banyan网络。图2.48是一个8×8的Batcher-Banyan网络，其中batcher排序网络是按递增顺序排序的。 图2.48 Batcher-Banyan网络

图2.49 对比Batcher-Banyan网络，banyan网络出现内部竞争

若使用Batcher-Banyan网络来完成上述的交换，则这4路信息经过batcher网络后，完全按照递增的顺序排列，信息按照递增顺序进入banyan网络，满足了banyan网络无阻塞的条件，消除了内部竞争，如图2.48所示。通过对比，我们可知Batcher-Banyan网络能够成功消除内部竞争。但需要说明的是Batcher-Banyan网络能够消除内部竞争，但不能消除外部竞争。