二、交换网络

主要内容 交换网络的构成和分类 交换单元 交换网络 交换单元的基本概念 开关阵列与空间交换单元 共享存储器型的交换单元——时间交换单元 共享总线型的交换单元——数字交换单元 交换网络 CLOS网络 TST网络 DSN网络 BANYAN网络

1、交换网络的构成和分类 交换的基本功能是在任意的入线和出线之间建立连接。 在交换系统中完成这一基本功能的部件就是交换网络，它是交换系统的核心。交换网络是由若干个交换单元按照一定的拓扑结构和控制方式构成的。 交换单元是构成交换网络的最基本的部件。 交换网络有：空分、时分 数字、模拟

2、交换单元 交换单元的基本概念 开关阵列与空间交换单元 共享存储器型的交换单元——时间交换单元 共享总线型的交换单元——数字交换单元

2.1 交换单元的基本概念 1 1 …… …… 入线 出线 M-1 N-1 控制端 状态端 M X N的交换单元

两种信号的交换 1 1 2 入线 2 出线 3 3 4 4 同步时分复用信号的交换

两种信号的交换 2 1 1 出线 入线 1 1 2 2 2 2 2 异步时分复用信号的交换

交换单元按使用需要的不同可分为： 入线 出线 入线 出线 N-1 M-1 N-1 M-1 集中型（M>N） 扩散型（M<N ） 入线 出线 入线 出线 N-1 M-1 N-1 M-1 集中型（M>N） 扩散型（M<N ） 入线 出线 M-1 N-1 连接型（M=N）

交换单元按信息流向分为： 有向交换单元：当信息经过交换单元时只能从入线 进出线出，具有唯一确定的方向。 无向交换单元：交换单元的每条线即可入也可出， 其入线数必等于出现数。 入线/出线 入线 ….. ….. 出线 M-1 N-1 N-1 M X N有向交换单元 N无向交换单元

交换单元的连接特性 连接特性是交换单元的基本特性，它反映了交换单元入线到出线的连接能力，通常我们用连接集合和连接函数来描述交换单元的连接特性 连接集合： 入线集合：T={0,1,2,…,M-1} 出线集合：R={0,1,2,…,N-1} 定义：t∈T，即t是T的一个元 r∈Rt，Rt是R的一个子集，r是Rt的一个元 则集合 c={t,Rt} 为一个连接。

交换单元的连接特性 若r∈Rt，Rt中只含有一个元，则称该连接为点到点连接。 若r∈Rt，Rt中含有多个元，则称该连接为一点到多点连接。

交换单元的连接特性 一个交换单元的连接同时可有多个，这就构成了交换单元的连接集合： C={c0, c1, c2, …} 其中：起点集 Tc={t; t∈ci, ciC} 终点集 Rc={r; r∈Rt, Rt  ci , ci  C} 连接和连接集合是对应于某一时刻的 连接集合的数目越多，连接能力就越强

交换单元的连接特性 连接函数 一个连接函数对应一种连接，连接函数表示相互连接的入线编号和出线编号之间的一一对应关系，即存在连接函数f，入线x与出线f(x)相连接，0≤x≤M-1，0≤f(x)≤N-1。 连接函数实际上也反映了入线编号构成的数组和出线编号构成的数组之间的置换关系或排列关系，故连接函数也被称作置换函数或排列函数。

x表示入线编号（二进制表示），f(x)表示连接函数。 连接函数的表示形式 函数表示形式 x表示入线编号（二进制表示），f(x)表示连接函数。 排列表示形式 即输入输出对应表示形式 t0，t1，…，t n-1 r0，r1，…，r n-1 图形表示形式

交换单元常用的连接函数 直线连接： 函数表示：I(xn-1xn-2…x1x0)= xn-1xn-2 … x1x0 0，1，2，3 图形表示（N=4）： 1 1 2 2 3 3

交换单元的连接特性 交叉连接： 函数表示：E(xn-1xn-2…x1x0)= xn-1xn-2 … x1x0 1，0，3，2 图形表示（N=4）： 1 1 2 2 3 3

交换单元的连接特性 间隔交叉连接： Ck(xn-1xn-2…xk … x1x0)= xn-1xn-2 …xk … x1x0 1 1 1 1 1 1 1 1 2 2 2 2 3 3 3 3 N=4 k=1 N=4 k=0

交换单元的连接特性 均匀洗牌连接： σ(xn-1xn-2…xk … x1x0)= xn-2 …xk … x1x0 xn-1 1 1 2 2 1 1 2 2 N=8 3 3 4 4 5 5 6 6 7 7 3

交换单元的连接特性 蝶式连接： β(xn-1 xn-2…xk … x1 x0)= x0 xn-2 …xk … x1 xn-1 1 1 2 2 1 1 2 2 N=8 3 3 4 4 5 5 6 6 7 7

交换单元的性能 容量： 交换单元所有入线可以同时送入的总的信息量 接口： 交换单元需要规定自己的信号接口标准，即信号形式、速率及信息流方向 功能： 点到点、同发、广播 质量： 完成交换动作的速度、任何情况下是否能完成指定连接、信息经过交换单元是否有损伤（时间、语义）

2.2 开关阵列与空间交换单元——开关阵列 在交换单元内部，要建立任意入线和任意出线之间的连接，就在每条入线和每条出线之间都各自接上一个开关，所有开关就构成了交换单元内部的开关阵列。

开关阵列的工作原理 出线 1 N-1 入线 ….. ….. 出线 M-1 N-1 1 入线 M X N有向交换单元 M-1 1 N-1 入线 ….. ….. 出线 M-1 N-1 1 入线 M X N有向交换单元 M-1 M X N有向矩形开关阵列

开关阵列的工作原理 出线 1 N-1 入线 N-1 1 入线 N无向交换单元 N-1 N无向方形开关阵列

无向交换单元开关阵列的实现（补充） N-1 N无向交换单元 入线/出线 N-1 N无向交换单元 若在一个N X N的交换单元中的连接总是对称的，即如果入端i连接到出端j，则入端j一定连接到出端i，那么相同编号的入端和出端可以看作一个同时具有发送和接收信息能力的信息端，既具有N个双向通信的信息端，并且每个信息端都可以和任何其它的信息端相连，这样的交换单元称作N个信息端的无向交换单元，简称N无向交换单元。

无向交换单元开关阵列的实现（补充） 1 2 N-2 1 N-1 2 N无向交换单元 N-2 N-1 N无向交换单元的开关阵列 （用双向开关） 1 2 N-2 入线/出线 1 N-1 2 N无向交换单元 N-2 N-1 N无向交换单元的开关阵列 （用双向开关）

无向交换单元开关阵列的实现（补充） 1 N-1 入线/出线 1 N-1 N-1 N无向交换单元 N无向交换单元的开关阵列 （用单向开关）

无向交换单元开关阵列的实现（补充） … L-1 K-1 K x L无向交换单元 入线/出线 K-1 K x L无向交换单元 L-1 … （信息端） 若N无向交换单元的N个信息端可以分为两组，分别为K和L个信息端。属于其中一组的信息端都可以和另一组的任何信息端相连接，但是不能和本组中的其它信息端相连，则称其为一个K x L的无向交换单元。

无向交换单元开关阵列的实现（补充） 1 K-1 1 L-1 1 1 K-1 K-1 K-1 L-1 … K(K=L)无向方形开关阵列 1 K-1 1 L-1 1 1 K-1 K-1 K(K=L)无向方形开关阵列 K X L无向矩形开关阵列 入线/出线 K-1 K x L无向交换单元 L-1 … （信息端）

无向交换单元开关阵列的实现（补充） 1 L-1 1 K-1 K+0 K+1 K+L-1 1 1 K-1 K-1 K+0 K+1 K+L-1 1 L-1 1 K-1 K+0 K+1 K+L-1 1 1 K-1 K-1 K+0 K X L无向矩形开关阵列 （用双向开关） K+1 K+L-1 (K+L) X (K+L)有向开关阵列 （用单向开关）

无向交换单元开关阵列的实现（补充） 1 K-1 1 K-1 K+0 K+1 K+K-1 1 1 K-1 K-1 K+0 K+1 K+K-1 1 K-1 1 K-1 K+0 K+1 K+K-1 1 1 K-1 K-1 K+0 K 无向方形开关阵列 （用双向开关） K+1 K+K-1 2K X 2K有向开关阵列 （用单向开关）

全连接交换单元和部分连接交换单元 出线 出线 1 N-1 1 N-1 1 1 入线 入线 N-1 N-1

多路选择器 出线 出线 1 N-1 入线 1 入线 M-1 入线 出线 N-1 入线 出线 M-1

开关阵列的特性 开关控制简单，从入线到出线具有均匀的单位延迟时间。 开关阵列适合于构成较小的交换单元（开关数反映了实现的复杂度和成本的高低）。 交换单元的性能依赖于所使用的开关。 控制信号简单 容易实现同发和广播功能

实际的开关阵列 继电器：其构成的交换单元是无向的，可交换模拟和数字信息，干扰和噪声大、动作慢（ms级）、体积大（cm级）。 模拟电子开关：一般利用半导体材料制成。 如：MC142100、MC145100（4 x 4开关阵列） 只能单向传送，且衰耗和时延较大。 数字电子开关：由简单的由逻辑门构成，用于数字信号的交 换，开关动作极快且无信号损失。

开关阵列交叉点的实现（1） 通断开关 多路选择器 交叉点可看成是一个具有通/断功能的开关。其具体实现比较复杂，包括FIFO缓冲器和相应的控制逻辑。 多路选择器

开关阵列交叉点的实现（2） Crossbar 交叉点是一个2 x 2的传送门，它有两个状态：bar状态和cross状态。Bar状态是指横向输入连到纵向输出，纵向输入连到横向输出；cross状态是指横向输入连到横向输出，纵向输入连到纵向输出。 交换矩阵在初始状态时，所有交叉点均处于cross状态，即任何入线与任何出线间均不连通。如果要使入线i与出线j连通，则应使处于交叉点（i,j）上的传送门处于bar状态，而在i行和j列的所有其它的传送门仍处于cross状态。

开关阵列交叉点的实现（3） 纵向输入 横向输入 横向输出 bar状态 纵向输出 cross状态

开关阵列交叉点的实现（4） 1 1 2 2 3 3 4 4 1 2 3 4 1 2 3 4 crossbar 通/断开关

2.3 开关阵列与空间交换单元——空间交换单元 空间交换单元也称为空间接线器（Space Switch），简称为S单元或S接线器，用来实现多个输入复用线与多个输出复用线之间的空间交换，而不改变其时隙位置。

空间交换单元的基本结构 S接线器的构成：交叉点矩阵、控制存储器 交叉点矩阵：开关阵列 控制存储器（CM-Control Memory）： S接线器所含CM数量等于入（出）线数 每个CM的所含有的存储单元个数等于入（出） 线上的复用时隙数 每个存储单元为n位bit,且满足N≤2n,其中N 为入（出）线上数

空间交换单元的控制方式 TS12 TS8 TS12 TS8 0 1 2 0 1 2 0 1 2 TS12 TS8 TS12 TS8 8 2 0 1 2 0 1 2 0 1 2 TS12 TS8 TS12 TS8 8 2 1 输入控制方式 12 2 127

空间交换单元的控制方式 TS12 TS8 TS12 TS8 0 1 2 0 1 2 0 1 2 TS12 TS8 TS12 TS8 8 2 0 1 2 0 1 2 0 1 2 TS12 TS8 TS12 TS8 8 2 输出控制方式 12 2 1 127

空间交换单元的工作原理

2.3、共享存储器型的交换单元——时间交换单元 1 输入信号 输出信号 N-1 工作方式：入线缓冲、出线缓冲 共享存储器型交换单元的一般结构

时间交换单元 时间交换单元也称为时间接线器（Time Switch），简称为T单元或T接线器，用来实现时隙交换功能。所谓时隙交换是指入线上各个时隙的内容要按照交换连接的需要，分别在出线上的不同时隙位置输出。

时间交换单元的基本结构 T接线器主要由话音存储器（SM:Speech Memory）和控制存储器(CM:Control memory)构成。 SM用来暂存话音的数字编码信息，故每个单元至少应为8比特。SM的容量等于输入复用线上每帧的时隙数。 CM的容量等于SM的容量；设CM每个单元的比特数为n，SM的单元数为N，则有2n=N，N也就是复用线上的时隙数。

时间交换单元的控制方式

2.4、共享总线型交换单元——数字交换单元

共享总线型交换单元 入线控制部件的功能： 接收入线信号，进行相应的格式变换，放在缓冲存储器中，并在分配给该部件的时隙上把收到的信息送到总线上。 出线控制部件的功能： 检测总线上的信号，并把属于自己的信息读入一个缓冲存储器中，进行格式变换，放在缓冲存储器中，由出线送出，形成出线信号。

共享总线型交换单元 总线： 一般包括多条数据线和控制线。数据线用于在入线控制部件和出线控制部件传送信号；控制线用于控制各入线控制部件获得时隙和发送信息，以及出线控制部件读取属于自己的信息。 总线按时隙轮流分配给各个入线控制部件和出线控制部件使用，其时隙的分配有一定的规则。

数字交换单元（DSE）

数字交换单元（DSE）的工作原理 S TS18 TS12 端口RAM 话路RAM 数据RAM 31 D P C 12 18 8

3、交换网络 交换网络是由若干个交换单元按照一定的拓扑结构和控制方式构成的网络。 交换网络的三个基本要素是：交换单元、不同交换单元间的拓扑连接和控制方式。

交换网络的一般结构 交换单元 交换单元 … … … … 入线 出线 交换单元 交换单元 交换网络 控制单元

单级交换网络和多级交换网络 交换网络按拓扑连接方式可分为：单级交换网络 多级交换网络 交换单元 入线 出线 M-1 N-1 单级交换网络

单级交换网络和多级交换网络 如果一个交换网络中的交换单元可以分为N级，顺序命名为第1,2,…,N级，并且满足： 所有入线都只与第1级交换单元连接； 所有第1级交换单元都只与入线和第2级交换单元连接； 所有第2级交换单元都只与第1级和第3级交换单元连接； 依此类推，所有第N级交换单元都只与第N-1级和出线 连接； 则称这样的交换网络为多级交换网络，或N级交换网络。

单级交换网络和多级交换网络 多级交换网络的拓扑结构可用三个参数来说明： 每个交换单元的容量 交换单元的级数 交换单元间的连接通路（链路）

多级交换网络(nm x nm两级交换网络) 1级 2级 O O 1 O O … 1 … … … n-1 m-1 O O 1 … 1 1 …

多级交换网络的内部阻塞 若出、入线空闲，但因交换网络级间链路被占用而无法接通的现象，称为多级交换网络的内部阻塞。 严格无阻塞网络： 不管网络处于何种状态，任何时刻都可以在交换网络中建立一个连接，只要这个连接的起点、终点是空闲的，而不会影响网络中已建立起来的连接。

多级交换网络的内部阻塞 可重排无阻塞网络： 不管网络处于何种状态，任何时刻都可以在交换网络中直接或对已有的连接重选路由来建立一个连接，只要这个连接的起点、终点是空闲的，而不会影响网络中已建立起来的连接。 广义无阻塞网络： 指一个给定的网络存在着固有的阻塞可能，但又可能存在着一种精巧的选路方法，使得所有的阻塞均可避免，而不必重新安排网络中已建立起来的连接。

可重排无阻塞网络 C2 1 1 C1 2 2 3 3 C2 C1 4 4 1，2，3，4 4，2，1，3

可重排无阻塞网络 1 1 C1 2 cc2 2 3 3 cc2 C1 4 4

3.1 CLOS网络 为了减少交叉点总数而同时具有严格的无阻塞特性，CLOS C.很早就提出一种多级结构，推出了严格无阻塞的条件，这就是著名的CLOS网络。 1 1 1 1 1 1 … 1 1 1 … 1 r r m n n m … … … 1 1 1 1 1 1 … r 1 m r … m r r m n n 3级CLOS网络

CLOS网络 在最坏情况下，中间级会有（n-1）X 2个交换单元被占用，因此中间级至少要有（n-1）X 2+1=2n-1个交换单元，即m≥2n-1时，可确保无阻塞（严格无阻塞）。

3.2 TST网络 TST网络是在电路交换系统中经常使用的一种交换网络，它是三级交换网络，两侧为T接线器，中间一级为S接线器，S级的出入线数决定于两侧T接线器的数量。 第1级T接线器：负责输入母线的时隙交换。 S接线器：负责母线之间的空间交换交换。 第2级T接线器：负责输出母线的时隙交换。

T(输出控制) S(输入控制) T(输入控制) CMA CMB 7 2 TS2 23 2 TS2 A 2 A 2 1 2 3 1 2 3 31 TS23 TS7 SMB SMA SMB SMA TS31 TS31 B B TS23 1 2 3 TS7 CMB 7 3 31 31 7 31 23 31 23 1 CMA 31

3.2 TST网络 为减少选路次数，简化控制，可使两个方向的内部时隙具有一定的对应关系，通常可相差半帧，俗称反相法，即： 设：Nf=一帧的时隙数 Na=A到B方向的内部时隙数 Nb=B到A方向的内部时隙数 则： Nb= Na +Nf/2 TST网络完全无阻塞的条件： m（内部时隙数）=2n（输入时隙数）

关于T-S组合网络 T-S(n)-T T-S-T网络：AXE10，FETEX-150，E10B，5ESS等 T-S-S-T网络：NEAX61 T-S-S-S-T网络：EWSD T-S-S-S-S-T网络：4ESS (长途) S-T(n)-S

3.3 BANYAN 网络 Banyan 网络的基本结构 Banyan 网络的基本特性 BATCHER-BANYAN网络 Benes网络

1、Banyan 网络的基本结构 banyan网络可分为一些子类，L级banyan是其中的一类，其特征是只有相邻级之间才有链路相连，即任何输入到任何输出之间的通路都经过L级。 L级banyan网络又可分为规则banyan和不规则banyan。规则banyan是指构成banyan网络的各个交换单元都是等同的，而不规则banyan则不然。 如果规则banyan中的各个交换单元不仅是等同的，而且每个交换单元的入线数等于出线数，则称此规则banyan为矩形banyan。

1、Banyan 网络的基本结构 通常将由2 X 2的交换单元构成的单通路网络称为banyan网络。 banyan网络是基于树型的拓扑结构，但每一个交换单元却是基于crossbar的结构。 2 X 2的交换单元也具有bar和cross两种状态。

8 x 8的3级banyan网络 01 01 2 3 23 45 4 5 67 67

2、Banyan 网络的基本特性 树型结构特性： 从banyan的任一输入端口引出的一组通路形成了2分支树，级数越多，分支越多，级数k=㏒2N，N=总入线数/出线数，即2k=N。 单通路特性： banyan的任一入端到任一出端之间，具有1条且仅有一条通路。 自选路由特性： 自选路由，即是给定出线地址，不用外加控制命令，就可选到出线。可以使用对应于出端号的二进制码的选路标签来自动选路。

Banyan网络的自选路由特性 8 x 8的3级banyan网络 (011) 01 01 (101) 2(010) 3(011) 23 1 45 4(100) 5(101) 1 (100) 67 67 1 8 x 8的3级banyan网络

2、Banyan 网络的基本特性 可扩展性： banyan的构成具有一定的规律，可以采用有规则的扩展方法将较小容量的banyan扩展成较大规模。 已有N X N的BANYAN网络，需构成2N X 2N的BANYAN网络，则可用2组N X N，再加上一组N个2X2交换单元构成。第一组的N X N的N条出线分别与N个2X2交换单元的某一入线相连，第二组的N X N的N条出线分别与N个2X2交换单元的另一入线相连。 内部竟争性： banyan是具有内部竞争的有阻塞网络。

Banyan网络的可扩展性 16X16BANYAN交换网络的构成

Banyan网络的可扩展性 16X16BANYAN交换网络的构成

解决内部阻塞的方法 1）内部阻塞是在2X2交换单元的两条入线要向同一个出线上发送信元时产生的，最坏情况下概率为50%，若减少入线上的信息量，就可减少阻塞的概率，故可通过适当限制入线上的信息量或加大缓冲存储器来减少内部阻塞。 2）可以通过增加多级交换网络的级数来消除内部阻塞。已有证明，若要完全消除N X N的banyan网络的内部阻塞，至少需要2㏒2N-1级。 3）可以增加banyan网的平面树，构成多通道交换网络。 4）使用排序-banyan网络。

3、BATCHER-BANYAN网络 该网络也简称为B-B网，是由BATCHER排序网和BANYAN网组成，它成功地避免了BANYAN网络的内部阻塞，这是目前ATM交换机使用较多的一种网络。 BATCHER排序网是由2X2的比较器（BATCHER比较器）构成的。 x min(x,y) y max(x,y) x max(x,y) y min(x,y)

BATCHER-BANYAN网络 BATCHER-BANYAN网络 011 010 111 011 010 100 011 111 100

4、基于BANYAN的多通路结构 为了减少或消除banyan的内部阻塞，提高吞吐率，除了构成B-B网络之外，还可以构成基于banyan的的各种多通路网络。 （1）增长型banyan 增长型banyan就是前面加上分配级，以扩大每个入端的选择范围，从而形成多通路网络。每增加1级，每个入端与每个出端之间的通路数就增加1倍。前置分配级还可以使业务流均衡地进入banyan的入端，减少banyan对流入的业务流模型的敏感性。

增长型BANYAN 01 01 2 3 23 45 4 5 67 67 增长型banyan

4、基于BANYAN的多通路结构 （2）扩展型banyan 考察banyan中的交换单元，对应于每个交换单元输出地址有1条链路，如果使每个输出地址有d条链路，也就是可以任意选择d条中的1条，就称为扩展型banyan。 在扩展型banyan网中，2×2的交换单元变成了2d×2d的交换单元。但输出地址并非2d个，而仍然是2个，只要用1个比特来区别。于是在任何时刻，最多可有d个信息单元传送到交换单元的每个输出；如果对应于同一输出地址同时有多于d个的信元到达，只能传送其中的d个。

扩展型BANYAN 01 01 2 3 23 45 4 5 67 67 扩展型banyan

4、基于BANYAN的多通路结构 （3）膨胀型banyan 膨胀型banyan是膨胀度d在各级可以变化的扩展型banyan。

膨胀型BANYAN d=3 d=4 d=2 01 01 2 3 23 45 4 5 67 67 膨胀型banyan

复份型BANYAN … … … … … … … … … … Banyan 1 Banyan 2 Banyan r 复份型banyan 1 1

4、BENES网络 benes网络是著名的多通路网络，具有再配置无阻塞的特点。 可以看出，Benes网络实际上相当于两个banyan（banyan与反转banyan）的背对背相连，并将中间相邻两级合并为1级。由于每个banyan有log2 N级，因此Benes网络共有2log2 N-1级。 benes网络的构成也有一定的规律。使用2X2交换单元的N X N benes网络的构成方法为：两侧各有N/2个2X2交换单元，中间为两个N/2 X N/2的子网络，每个交换单元以一条链路连到每个子网络；再将中间子网络按上述方法继续分解，直到中间子网络就是2X2交换单元为止。

8 X8 BENES 网络 01 01 2 3 23 45 4 5 67 67 8 X 8 benes网络

BENES 网络构成方法 01 01 N/2 X N/2 2 3 23 45 4 5 N/2 X N/2 67 67 benes网络构成方法

作业（1） 1、有一个T-S-T交换网络，有8条输入母线和8条输出目线，每条母线为一帧256个TS，其第一级T接线器为输入控制方式，S接线器为输出控制方式，第二级T接线器为输出控制方式，请画图表示该网络将HW6TS8交换到HW2TS23的过程（内部选定的空闲时隙为TS15 ），并标出各级SM和CM的容量及相关单元内容，给出CP的时间。

作业（2） 2、构造16*16的交换单元：采用基本开关阵列时，需要 多少个开关？采用K=4的绳路开关阵列时，需要多少个开关？采用可重排无阻塞网络时，需多少个2*2交叉单元？采用BANYAN网络时，需多少个2*2交叉单元？采用共享存贮器结构时，至少需 多少个存储单元。 3、构造256*256的三级严格无阻塞CLOS网络。要求：入口级选择8入线的交换单元，出口级选择8出线的交换单元。画出该网络连接示意图（标出各级交换单元的个数，入出线）。

本章小结 描述交换单元连接特性的方法 交换单元的外部特性描述的描述指标 三种典型的交换单元的结构、特性及工作原理 无阻塞网络的概念，构成无阻塞网络的方法 TST、CLOS、BANYAN网络的结构及特性