北京邮电大学计算机科学与技术学院 卞佳丽 1
二、交换网络
北京邮电大学计算机科学与技术学院 卞佳丽 2
1,交换网络的构成和分类
2,交换单元
? 交换单元的基本概念
? 开关阵列与空间交换单元
? 共享存储器型的交换单元 ——时间交换单元
? 共享总线型的交换单元 ——数字交换单元
3,交换网络
? CLOS网络
? TST网络
? DSN网络
? BANYAN网络
主要内容
北京邮电大学计算机科学与技术学院 卞佳丽 3
交换 的基本功能是在任意的入线和出线之间
建立连接。
在交换系统中完成这一基本功能的部件就是
交换网络,它是交换系统的核心。交换网络是由
若干个交换单元按照一定的 拓扑结构 和 控制方式
构成的。
交换单元 是构成交换网络的最基本的部件。
交换网络有,空分、时分
数字、模拟
1、交换网络的构成和分类
北京邮电大学计算机科学与技术学院 卞佳丽 4
? 交换单元的基本概念
? 开关阵列与空间交换单元
? 共享存储器型的交换单元 ——时间交换单元
? 共享总线型的交换单元 ——数字交换单元
2、交换单元
北京邮电大学计算机科学与技术学院 卞佳丽 5
2.1 交换单元的基本概念
入线 出线
控制端 状态端
…… ……
M X N的交换单元
0 0
1 1
M-1 N-1
北京邮电大学计算机科学与技术学院 卞佳丽 6
入线 出线
0 0
1 1
4 4
2
3
2
3
同步时分复用信号的交换
两种信号的交换
北京邮电大学计算机科学与技术学院 卞佳丽 7
入线 出线
0 0
1
22
1
异步时分复用信号的交换
02
1 0
0 0
1
22 2
两种信号的交换
北京邮电大学计算机科学与技术学院 卞佳丽 8
交换单元按使用需要的不同可分为,
入线
0
M-1
出线0
N-1
入线 0
M-1
出线
0
N-1
出线
0
N-1
入线
0
M-1
集中型（ M>N） 扩散型（ M<N ）
连接型（ M=N）
北京邮电大学计算机科学与技术学院 卞佳丽 9
交换单元按信息流向分为：
? 有向交换单元：当信息经过交换单元时只能从入线
进出线出，具有唯一确定的方向。
? 无向交换单元：交换单元的每条线即可入也可出，
其入线数必等于出现数。
出线
0
N-1
入线
0
M-1
M X N有向交换单元
入
线
/
出
线
0
N-1
N无向交换单元
…
..
…
..
北京邮电大学计算机科学与技术学院 卞佳丽 10
交换单元的连接特性
连接特性是交换单元的基本特性，它反映了交换单元
入线到出线的连接能力，通常我们用 连接集合 和 连接函数
来描述交换单元的连接特性
? 连接集合：
入线集合,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} 为一个连接。
北京邮电大学计算机科学与技术学院 卞佳丽 11
? 若 r∈Rt, Rt中只含有一个元，则称该连接为点到点
连接。
? 若 r∈Rt, Rt中含有多个元，则称该连接为一点到多
点连接。
? 若一个交换单元可以提供点到多点的功能，但 Rt≠R,
则称其具有同发功能；若 Rt=R,则该交换单元具有广
播功能。
交换单元的连接特性
北京邮电大学计算机科学与技术学院 卞佳丽 12
交换单元的连接特性
一个交换单元的连接同时可有多个，这就构成了交
换单元的连接集合：
C={c0,c1,c2,…}
其中：起点集 Tc={t; t∈ ci,ci?C}
终点集 Rc={r; r∈ Rt,Rt ? ci,ci ? C}
? 连接和连接集合是对应于某一时刻的
? 连接集合的数目越多，连接能力就越强
北京邮电大学计算机科学与技术学院 卞佳丽 13
? 连接函数
一个连接函数对应一种连接，连接函数表示相互
连接的入线编号和出线编号之间的一一对应关系，即存
在连接函数 f,入线 x与出线 f(x)相连接,0≤x≤M-1，
0≤f(x)≤N-1。
连接函数实际上也反映了入线编号构成的数组和出
线编号构成的数组之间的置换关系或排列关系，故连接
函数也被称作 置换函数 或 排列函数 。
交换单元的连接特性
北京邮电大学计算机科学与技术学院 卞佳丽 14
? 函数表示形式
x表示入线编号（二进制表示）,f(x)表
示连接函数。
? 排列表示形式
即输入输出对应表示形式
t0,t1,…, t n-1
r0,r1,…, r n-1
? 图形表示形式
连接函数的表示形式
北京邮电大学计算机科学与技术学院 卞佳丽 15
直线连接：
函数表示,I(xn-1xn-2…x 1x0)= xn-1xn-2 … x1x0
排列表示（ N=4）, 0,1,2,3
0,1,2,3
图形表示（ N=4）,0 0
1
2
3
1
2
3
交换单元常用的连接函数
北京邮电大学计算机科学与技术学院 卞佳丽 16
交叉连接：
函数表示,E(xn-1xn-2…x 1x0)= xn-1xn-2 … x1x0
排列表示（ N=4）, 0,1,2,3
1,0,3,2
图形表示（ N=4）,0 0
1
2
3
1
2
3
交换单元的连接特性
北京邮电大学计算机科学与技术学院 卞佳丽 17
间隔交叉连接：
Ck(xn-1xn-2…x k … x1x0)= xn-1xn-2 …x k … x1x0
0 0
1
2
3
1
2
3
0 0
1
2
3
1
2
3
N=4 k=1 N=4 k=0
交换单元的连接特性
北京邮电大学计算机科学与技术学院 卞佳丽 18
均匀洗牌连接：
σ(xn-1xn-2…x k … x1x0)= xn-2 …x k … x1x0 xn-1
0
1
2
3N=8
4
5
6
7
0
1
2
3
4
5
6
7
交换单元的连接特性
北京邮电大学计算机科学与技术学院 卞佳丽 19
蝶式连接：
β(xn-1 xn-2…x k … x1 x0)= x0 xn-2 …x k … x1 xn-1
0
1
2
3N=8
4
5
6
7
0
1
2
3
4
5
6
7
交换单元的连接特性
北京邮电大学计算机科学与技术学院 卞佳丽 20
交换单元的性能
? 容量：
交换单元所有入线可以同时送入的总的信息量
? 接口：
交换单元需要规定自己的信号接口标准，即信号形式、
速率及信息流方向
? 功能：
点到点、同发、广播
? 质量：
完成交换动作的速度、任何情况下是否能完成指定连
接、信息经过交换单元是否有损伤（时间、语义）
北京邮电大学计算机科学与技术学院 卞佳丽 21
2.2 开关阵列与空间交换单元 ——开关阵列
在交换单元内部，要建立任意入线和任意出
线之间的连接，就在每条入线和每条出线之间都
各自接上一个开关，所有开关就构成了交换单元
内部的 开关阵列 。
北京邮电大学计算机科学与技术学院 卞佳丽 22
M X N有向交换单元
0 1 N-1
0
1
M-1
入线
出线
M X N有向矩形开关阵列
开关阵列的工作原理
出线
0
N-1
入线
0
M-1
…
..
…
..
北京邮电大学计算机科学与技术学院 卞佳丽 23
N无向方形开关阵列
入线
0
N-1
N无向交换单元
0 1 N-1
0
1
N-1
入线
出线
开关阵列的工作原理
北京邮电大学计算机科学与技术学院 卞佳丽 24
入线 /出线
0
N-1
N无向交换单元
无向交换单元开关阵列的实现（补充）
若在一个 N X N的交换单元中的连接总是对称的，即
如果入端 i连接到出端 j,则入端 j一定连接到出端 i,那么
相同编号的入端和出端可以看作一个同时具有发送和接
收信息能力的信息端，既具有 N个双向通信的信息端，
并且每个信息端都可以和任何其它的信息端相连，这样
的交换单元称作 N个信息端的无向交换单元，简称 N无向
交换单元。
北京邮电大学计算机科学与技术学院 卞佳丽 25
N无向交换单元的开关阵列
（用双向开关）
入线 /出线
0
N-1
N无向交换单元
0 1 N-2
1
N-1
无向交换单元开关阵列的实现（补充）
2
N-2
2
北京邮电大学计算机科学与技术学院 卞佳丽 26
0 1
0
1
N-1
N-1
无向交换单元开关阵列的实现（补充）
入线 /出线
0
N-1
N无向交换单元
N无向交换单元的开关阵列
（用单向开关）
北京邮电大学计算机科学与技术学院 卞佳丽 27
无向交换单元开关阵列的实现（补充）
若 N无向交换单元的 N个信息端可以分为两组，
分别为 K和 L个信息端。属于其中一组的信息端都可
以和另一组的任何信息端相连接，但是不能和本组
中的其它信息端相连，则称其为一个 K x L的无向交
换单元。
入线 /出线 0
K-1
K x L无向交换单元
0
L-1
… 入线 /出线…
（信息端） （信息端）
北京邮电大学计算机科学与技术学院 卞佳丽 28
K X L无向矩形开关阵列
0 1 L-1
0
1
K-1
K(K=L)无向方形开关阵列
0 1 K-1
0
1
K-1
入线 /出线 0
K-1
K x L无向交换单元
0
L-1
… 入线 /出线…
（信息端） （信息端）
无向交换单元开关阵列的实现（补充）
北京邮电大学计算机科学与技术学院 卞佳丽 29
K X L无向矩形开关阵列
（用双向开关）
0 1 L-1
0
1
K-1
无向交换单元开关阵列的实现（补充）
(K+L) X (K+L)有向开关阵列
（用单向开关）
0 1
0
1
K-1
K+0
K+L-1
K+0K+1 K+L-1K-1
K+1
北京邮电大学计算机科学与技术学院 卞佳丽 30
K 无向方形开关阵列
（用双向开关）
0 1 K-1
0
1
K-1
无向交换单元开关阵列的实现（补充）
2K X 2K有向开关阵列
（用单向开关）
0 1
0
1
K-1
K+0
K+K-1
K+0K+1 K+K-1K-1
K+1
北京邮电大学计算机科学与技术学院 卞佳丽 31
全连接交换单元和部分连接交换单元
0 1 N-1
0
1
N-1
入线
出线
0 1 N-1
0
1
N-1
入线
出线
北京邮电大学计算机科学与技术学院 卞佳丽 32
0
1
M-1
入线
出线
入线
0
M-1
出线
入线
0
N-1
出线
0 1 N-1
入线
出线
多路选择器
北京邮电大学计算机科学与技术学院 卞佳丽 33
开关阵列的特性
? 开关控制简单，从入线到出线具有均匀的单位延迟时
间。
? 开关阵列适合于构成较小的交换单元（开关数反映了
实现的复杂度和成本的高低）。
? 交换单元的性能依赖于所使用的开关。
? 控制信号简单
? 容易实现同发和广播功能
北京邮电大学计算机科学与技术学院 卞佳丽 34
继电器：其构成的交换单元是无向的，可交换模拟和数字信息，
干扰和噪声大, 动作慢（ ms级）、体积大（ cm级）。
模拟电子开关：一般利用半导体材料制成。
如,MC142100,MC145100（ 4 x 4开关阵列）
只能单向传送，且衰耗和时延较大。
数字电子开关：由简单的由逻辑门构成，用于数字信号的交
换，开关动作极快且无信号损失。
实际的开关阵列
北京邮电大学计算机科学与技术学院 卞佳丽 35
? 通断开关
交叉点可看成是一个具有通 /断功能的开关。其具体
实现比较复杂，包括 FIFO缓冲器和相应的控制逻辑。
? 多路选择器
开关阵列交叉点的实现（ 1）
北京邮电大学计算机科学与技术学院 卞佳丽 36
? Crossbar
交叉点是一个 2 x 2的传送门，它有两个状态,bar状
态和 cross状态。 Bar状态是指横向输入连到纵向输出，纵
向输入连到横向输出； cross状态是指横向输入连到横向输
出，纵向输入连到纵向输出。
交换矩阵在初始状态时，所有交叉点均处于 cross状态，
即任何入线与任何出线间均不连通。如果要使入线 i与出线 j
连通，则应使处于交叉点 （ i,j） 上的传送门处于 bar状态，
而在 i行和 j列的所有其它的传送门仍处于 cross状态。
开关阵列交叉点的实现（ 2）
北京邮电大学计算机科学与技术学院 卞佳丽 37
横向输入
纵向输入
纵向输出
横向输出
bar状态
cross状态
开关阵列交叉点的实现（ 3）
北京邮电大学计算机科学与技术学院 卞佳丽 38
1
2
3
4
1
2
3
4
1 2 3 41 2 3 4
crossbar 通 /断开关
开关阵列交叉点的实现（ 4）
北京邮电大学计算机科学与技术学院 卞佳丽 39
空间交换单元也称为 空间接线器 （ Space
Switch）,简称为 S单元 或 S接线器,用来实现
多个输入复用线与多个输出复用线之间的空间
交换，而不改变其时隙位置。
2.3 开关阵列与空间交换单元 ——空间交换单元
北京邮电大学计算机科学与技术学院 卞佳丽 40
S接线器的构成,交叉点矩阵, 控制存储器
交叉点矩阵,开关阵列
控制存储器 （ CM-Control Memory）：
? S接线器所含 CM数量等于入（出）线数
? 每个 CM的所含有的存储单元个数等于入（出）
线上的复用时隙数
? 每个存储单元为 n位 bit,且满足 N≤2 n,其中 N
为入（出）线上数
空间交换单元的基本结构
北京邮电大学计算机科学与技术学院 卞佳丽 41
空间交换单元的控制方式
0
1
2
0
1
20 1 2
TS12 TS8
TS12 TS8 0
8
12
127
2
TS8
TS8
输入控制方式
1
TS12
TS12
2 0
北京邮电大学计算机科学与技术学院 卞佳丽 42
空间交换单元的控制方式
0
1
2
0
1
20 1 2
TS12 TS8
TS12 TS8 0
8
12
2
TS8
TS8
输出控制方式
1
TS12
TS12
2
0
127
北京邮电大学计算机科学与技术学院 卞佳丽 43
空间交换单元的工作原理
北京邮电大学计算机科学与技术学院 卞佳丽 44
2.3、共享存储器型的交换单元 ——时间交换单元
0
1
N-1
输入信号 输出信号
共享存储器型交换单元的一般结构
工作方式：入线缓冲、出线缓冲
北京邮电大学计算机科学与技术学院 卞佳丽 45
时间交换单元也称为 时间接线器 （ Time
Switch）,简称为 T单元 或 T接线器,用来实现
时隙交换功能。所谓时隙交换是指入线上各个
时隙的内容要按照交换连接的需要，分别在出
线上的不同时隙位置输出。
时间交换单元
北京邮电大学计算机科学与技术学院 卞佳丽 46
T接线器主要由 话音存储器 （ SM:Speech
Memory） 和 控制存储器 (CM:Control memory)构
成。
SM用来暂存话音的数字编码信息，故每个单
元至少应为 8比特。 SM的容量等于输入复用线上
每帧的时隙数。
CM的容量等于 SM的容量；设 CM每个单元的比
特数为 n,SM的单元数为 N,则有 2n=N,N也就是复
用线上的时隙数。
时间交换单元的基本结构
北京邮电大学计算机科学与技术学院 卞佳丽 47
时间交换单元的控制方式
北京邮电大学计算机科学与技术学院 卞佳丽 48
2.4、共享总线型交换单元 ——数字交换单元
北京邮电大学计算机科学与技术学院 卞佳丽 49
入线控制部件的功能,
接收入线信号，进行相应的格式变换，放在缓冲存
储器中，并在分配给该部件的时隙上把收到的信息送到
总线上。
出线控制部件的功能,
检测总线上的信号，并把属于自己的信息读入一个
缓冲存储器中，进行格式变换，放在缓冲存储器中，由
出线送出，形成出线信号。
共享总线型交换单元
北京邮电大学计算机科学与技术学院 卞佳丽 50
总线,
一般包括多条数据线和控制线。数据线用于在入线
控制部件和出线控制部件传送信号；控制线用于控制各
入线控制部件获得时隙和发送信息，以及出线控制部件
读取属于自己的信息。
总线按时隙轮流分配给各个入线控制部件和出线控
制部件使用，其时隙的分配有一定的规则。
共享总线型交换单元
北京邮电大学计算机科学与技术学院 卞佳丽 51
数字交换单元（ DSE）
北京邮电大学计算机科学与技术学院 卞佳丽 52
数字交换单元（ DSE） 的工作原理
S
TS18
S
TS12
端口
RAM
话路
RAM
数据
RAM
0 0 0
31
D
31 31
P C
1212 188 18 S
北京邮电大学计算机科学与技术学院 卞佳丽 53
3、交换网络
交换网络 是由若干个交换单元按照一定的拓
扑结构和控制方式构成的网络。
交换网络的三个基本要素是,交换单元,不
同交换单元间的 拓扑连接 和 控制方式 。
北京邮电大学计算机科学与技术学院 卞佳丽 54
交换网络的一般结构
… …
控制单元
出线入线 … …
交换
单元
交换
单元
交换
单元
交换
单元
交换网络
北京邮电大学计算机科学与技术学院 卞佳丽 55
单级交换网络和多级交换网络
交换网络按拓扑连接方式可分为：单级交换网络
多级交换网络
出线
0
N-1
入线
0
M-1
单级交换网络
交换
单元
北京邮电大学计算机科学与技术学院 卞佳丽 56
单级交换网络和多级交换网络
如果一个交换网络中的交换单元可以分为 N级，顺序
命名为第 1,2,…,N级，并且满足：
所有入线都只与第 1级交换单元连接；
所有第 1级交换单元都只与入线和第 2级交换单元连接；
所有第 2级交换单元都只与第 1级和第 3级交换单元连接；
依此类推，所有第 N级交换单元都只与第 N-1级和出线
连接；
则称这样的交换网络为 多级交换网络,或 N级交换网络 。
北京邮电大学计算机科学与技术学院 卞佳丽 57
多级交换网络的拓扑结构可用三个参数来说明：
每个交换单元的容量
交换单元的级数
交换单元间的连接通路（链路）
单级交换网络和多级交换网络
北京邮电大学计算机科学与技术学院 卞佳丽 58
多级交换网络 (nm x nm两级交换网络 )
…
…
…
…
…
O
1
n-1
O
1
n-1
…O1
n-1
O
1
m-1
O
1
m-1
O
1
m-1
…
…
…
…
…
…
… …
O O
1 1
m-1 n-1
1级 2级
北京邮电大学计算机科学与技术学院 卞佳丽 59
多级交换网络的内部阻塞
若出、入线空闲，但因交换网络级间链路被占用而
无法接通的现象，称为多级交换网络的内部阻塞。
严格无阻塞网络,
不管网络处于何种状态，任何时刻都可以在交换网
络中建立一个连接，只要这个连接的起点、终点是空闲
的，而不会影响网络中已建立起来的连接。
北京邮电大学计算机科学与技术学院 卞佳丽 60
可重排无阻塞网络,
不管网络处于何种状态，任何时刻都可以在交换网
络中直接或对已有的连接重选路由来建立一个连接，只要
这个连接的起点、终点是空闲的，而不会影响网络中已建
立起来的连接。
广义无阻塞网络,
指一个给定的网络存在着固有的阻塞可能，但又可
能存在着一种精巧的选路方法，使得所有的阻塞均可避免，
而不必重新安排网络中已建立起来的连接。
多级交换网络的内部阻塞
北京邮电大学计算机科学与技术学院 卞佳丽 61
1
3
4
2
1
3
4
2C1
C1C2
C2
1,2,3,4
4,2,1,3
可重排无阻塞网络
北京邮电大学计算机科学与技术学院 卞佳丽 62
1
3
4
2
1
3
4
2C1
C1cc2
cc2
可重排无阻塞网络
北京邮电大学计算机科学与技术学院 卞佳丽 63
3.1 CLOS网络
为了减少交叉点总数而同时具有严格的无阻塞特性，
CLOS C.很早就提出一种多级结构，推出了严格无阻塞的
条件，这就是著名的 CLOS网络。
… …
…
1
n
…1
n
1
n
1
n
… …
1
…
1
m
1
r
1
1r
m
m
m
m
1
1
1 1
1 1
1
1
r
r
r
r
3级 CLOS网络
北京邮电大学计算机科学与技术学院 卞佳丽 64
在最坏情况下，中间级会有（ n-1） X 2个交换单元被
占用，因此中间级至少要有（ n-1） X 2+1=2n-1个交换
单元，即 m≥2n-1时，可确保无阻塞（严格无阻塞）。
CLOS网络
北京邮电大学计算机科学与技术学院 卞佳丽 65
3.2 TST网络
TST网络是在电路交换系统中经常使用的一种交换网
络，它是三级交换网络，两侧为 T接线器，中间一级为 S
接线器,S级的出入线数决定于两侧 T接线器的数量。
第 1级 T接线器：负责输入母线的时隙交换。
S接线器：负责母线之间的空间交换交换。
第 2级 T接线器：负责输出母线的时隙交换。
北京邮电大学计算机科学与技术学院 卞佳丽 66
1
2
3
1
2
31 2 3
TS2
TS31
0
7
23
31
3
TS2
TS31
S(输入控制 )
TS7
TS23
1
0
31
2
7 2
0
31
3123
23 2 2
317 31
CMA
CMA
SMA
SMA
SMB
SMB
CMB
CMB
TS23
TS7
T(输出控制 ) T(输入控制 )
A
B
A
B
北京邮电大学计算机科学与技术学院 卞佳丽 67
为减少选路次数，简化控制，可使两个方向的内部时
隙具有一定的对应关系，通常可相差半帧，俗称 反相法,
即：
设,Nf=一帧的时隙数
Na=A到 B方向的内部时隙数
Nb=B到 A方向的内部时隙数
则,Nb= Na +Nf/2
TST网络完全无阻塞的条件：
m（ 内部时隙数） =2n（ 输入时隙数）
3.2 TST网络
北京邮电大学计算机科学与技术学院 卞佳丽 68
关于 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
北京邮电大学计算机科学与技术学院 卞佳丽 69
3.3 BANYAN 网络
? Banyan 网络的基本结构
? Banyan 网络的基本特性
? BATCHER-BANYAN网络
? 基于 banyan的多通路结构
? Benes网络
北京邮电大学计算机科学与技术学院 卞佳丽 70
banyan网络可分为一些子类,L级 banyan是其中的一类，
其特征是只有相邻级之间才有链路相连，即任何输入到任何
输出之间的通路都经过 L级。
L级 banyan网络又可分为 规则 banyan和 不规则 banyan。
规则 banyan是指构成 banyan网络的各个交换单元都是等同的，
而不规则 banyan则不然。
如果规则 banyan中的各个交换单元不仅是等同的，而
且每个交换单元的入线数等于出线数，则称此规则 banyan为
矩形 banyan。
1,Banyan 网络的基本结构
北京邮电大学计算机科学与技术学院 卞佳丽 71
通常将由 2 X 2的交换单元构成的单通路网
络称为 banyan网络。
banyan网络是基于树型的拓扑结构，但每
一个交换单元却是基于 crossbar的结构。 2 X 2
的交换单元也具有 bar和 cross两种状态。
1,Banyan 网络的基本结构
北京邮电大学计算机科学与技术学院 卞佳丽 72
0
1
2
3
4
5
6
7
0
1
2
3
4
5
6
7
8 x 8的 3级 banyan网络
北京邮电大学计算机科学与技术学院 卞佳丽 73
树型结构特性,
从 banyan的任一输入端口引出的一组通路形成了 2
分支树，级数越多，分支越多，级数 k=㏒ 2N,N=总入
线数 /出线数，即 2k=N。
单通路特性,
banyan的任一入端到任一出端之间，具有 1条且仅
有一条通路。
自选路由特性,
自选路由，即是给定出线地址，不用外加控制命令，
就可选到出线。可以使用对应于出端号的二进制码的选
路标签来自动选路。
2,Banyan 网络的基本特性
北京邮电大学计算机科学与技术学院 卞佳丽 74
0
1
2
3
4
5
6
7
0
1
2(010)
3(011)
4(100)
5(101)
6
7
8 x 8的 3级 banyan网络
1
0
1
1
0
(011)
(010)
(100)
(101)
Banyan网络的自选路由特性
北京邮电大学计算机科学与技术学院 卞佳丽 75
可扩展性,
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是具有内部竞争的有阻塞网络。
2,Banyan 网络的基本特性
北京邮电大学计算机科学与技术学院 卞佳丽 76
16X
16BA
NY
AN
交
换
网
络
的
构
成
Banyan网络的可扩展性
北京邮电大学计算机科学与技术学院 卞佳丽 77
16X
16BA
NY
AN
交
换
网
络
的
构
成
Banyan网络的可扩展性
北京邮电大学计算机科学与技术学院 卞佳丽 78
1）内部阻塞是在 2X2交换单元的两条入线要向同一个出线
上发送信元时产生的，最坏情况下概率为 50%，若减少
入线上的信息量，就可减少阻塞的概率，故可通过适当
限制入线上的信息量或加大缓冲存储器来减少内部阻塞。
2）可以通过增加多级交换网络的级数来消除内部阻塞。已
有证明，若要完全消除 N X N的 banyan网络的内部阻塞，
至少需要 2㏒ 2N-1级。
3）可以增加 banyan网的平面树，构成多通道交换网络。
4） 使用排序 -banyan网络。
解决内部阻塞的方法
北京邮电大学计算机科学与技术学院 卞佳丽 79
该网络也简称为 B-B网，是由 BATCHER排序网和
BANYAN网组成，它成功地避免了 BANYAN网络的内
部阻塞，这是目前 ATM交换机使用较多的一种网络。
BATCHER排序网是由 2X2的比较器（ BATCHER比较器）
构成的。
x
y
min(x,y)
max(x,y)
x
y min(x,y)
max(x,y)
3,BATCHER-BANYAN网络
北京邮电大学计算机科学与技术学院 卞佳丽 80
BATCHER-BANYAN网络
011
111
010
100
011
010
100
111
111
100
010
011
BATCHER-BANYAN网络
北京邮电大学计算机科学与技术学院 卞佳丽 81
为了减少或消除 banyan的内部阻塞，提高吞吐率，
除了构成 B-B网络之外，还可以构成基于 banyan的的各种
多通路网络。
（ 1） 增长型 banyan
增长型 banyan就是前面加上分配级，以扩大每个入端
的选择范围，从而形成多通路网络。每增加 1级，每个入
端与每个出端之间的通路数就增加 1倍 。 前置分配级还可
以使业务流均衡地进入 banyan的入端，减少 banyan对流入
的业务流模型的敏感性。
4、基于 BANYAN的多通路结构
北京邮电大学计算机科学与技术学院 卞佳丽 82
0
1
2
3
4
5
6
7
0
1
2
3
4
5
6
7
增长型 banyan
增长型 BANYAN
北京邮电大学计算机科学与技术学院 卞佳丽 83
（ 2） 扩展型 banyan
考察 banyan中的交换单元，对应于每个交换单元输出
地址有 1条链路，如果使每个输出地址有 d条链路，也就是
可以任意选择 d条中的 1条，就称为扩展型 banyan。
在扩展型 banyan 网中, 2× 2的 交换单 元变成了
2d× 2d的交换单元 。 但输出地址并非 2d个, 而仍然是 2个,
只要用 1个比特来区别 。 于是在任何时刻, 最多可有 d个信
息单元传送到交换单元的每个输出；如果对应于同一输出
地址同时有多于 d个的信元到达, 只能传送其中的 d个 。
4、基于 BANYAN的多通路结构
北京邮电大学计算机科学与技术学院 卞佳丽 84
0
1
2
3
4
5
6
7
0
1
2
3
4
5
6
7
扩展型 banyan
扩展型 BANYAN
北京邮电大学计算机科学与技术学院 卞佳丽 85
（ 3） 膨胀型 banyan
膨胀型 banyan是膨胀度 d在各级可以变化的扩展型
banyan。
（ 4） 复份型 banyan
复份型 banyan是将若干个相同的 banyan并接在一起,
形成多平面的网络结构 。
从复份型 banyan的每个输入端进入的信息单元, 可
以随机地选择某个平面, 也可以按负荷均分原则分配到各
个平面, 还可以广播到所有的平面 。
4、基于 BANYAN的多通路结构
北京邮电大学计算机科学与技术学院 卞佳丽 86
0
1
2
3
4
5
6
7
0
1
2
3
4
5
6
7
膨胀型 banyan
d=2 d=3 d=4
膨胀型 BANYAN
北京邮电大学计算机科学与技术学院 卞佳丽 87
Banyan 1
Banyan 2
Banyan r
… …
…
…
……
…
…
… …
1
2
n
1
2
n
复份型 banyan
复份型 BANYAN
北京邮电大学计算机科学与技术学院 卞佳丽 88
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交换单元为止 。
4,BENES网络
北京邮电大学计算机科学与技术学院 卞佳丽 89
0
1
2
3
4
5
6
7
0
1
2
3
4
5
6
7
8 X 8 benes网络
8 X8 BENES 网络
北京邮电大学计算机科学与技术学院 卞佳丽 90
0
1
2
3
4
5
6
7
0
1
2
3
4
5
6
7
benes网络构成方法
N/2 X N/2
N/2 X N/2
BENES 网络构成方法
北京邮电大学计算机科学与技术学院 卞佳丽 91
作业（ 1）
1、有一个 T-S-T交换网络，有 8条输入母线和 8条输出
目线，每条母线为一帧 256个 TS,其第一级 T接线
器为输入控制方式,S接线器为输出控制方式，第
二级 T接线器为输出控制方式，请画图表示该网络
将 HW6TS8交换到 HW2TS23的过程（内部选定的空闲
时隙为 TS15 ），并标出各级 SM和 CM的容量及相关
单元内容，给出 CP的时间 。
北京邮电大学计算机科学与技术学院 卞佳丽 92
作业（ 2）
2、构造 16*16的交换单元：采用基本开关阵列时，需要
多少个开关？采用 K=4的绳路开关阵列时，需要多
少个开关？采用可重排无阻塞网络时，需多少个 2*2
交叉单元？采用 BANYAN网络时，需多少个 2*2交叉
单元？采用共享存贮器结构时，至少需 多少个存储
单元。
3、构造 256*256的三级严格无阻塞 CLOS网络。要求：
入口级选择 8入线的交换单元，出口级选择 8出线的
交换单元。画出该网络连接示意图（标出各级交换
单元的个数，入出线）。
北京邮电大学计算机科学与技术学院 卞佳丽 93
本章小结
描述交换单元连接特性的方法
交换单元的外部特性描述的描述指标
三种典型的交换单元的结构、特性及工作原理
无阻塞网络的概念，构成无阻塞网络的方法
TST,CLOS,BANYAN网络的结构及特性
二、交换网络
北京邮电大学计算机科学与技术学院 卞佳丽 2
1,交换网络的构成和分类
2,交换单元
? 交换单元的基本概念
? 开关阵列与空间交换单元
? 共享存储器型的交换单元 ——时间交换单元
? 共享总线型的交换单元 ——数字交换单元
3,交换网络
? CLOS网络
? TST网络
? DSN网络
? BANYAN网络
主要内容
北京邮电大学计算机科学与技术学院 卞佳丽 3
交换 的基本功能是在任意的入线和出线之间
建立连接。
在交换系统中完成这一基本功能的部件就是
交换网络,它是交换系统的核心。交换网络是由
若干个交换单元按照一定的 拓扑结构 和 控制方式
构成的。
交换单元 是构成交换网络的最基本的部件。
交换网络有,空分、时分
数字、模拟
1、交换网络的构成和分类
北京邮电大学计算机科学与技术学院 卞佳丽 4
? 交换单元的基本概念
? 开关阵列与空间交换单元
? 共享存储器型的交换单元 ——时间交换单元
? 共享总线型的交换单元 ——数字交换单元
2、交换单元
北京邮电大学计算机科学与技术学院 卞佳丽 5
2.1 交换单元的基本概念
入线 出线
控制端 状态端
…… ……
M X N的交换单元
0 0
1 1
M-1 N-1
北京邮电大学计算机科学与技术学院 卞佳丽 6
入线 出线
0 0
1 1
4 4
2
3
2
3
同步时分复用信号的交换
两种信号的交换
北京邮电大学计算机科学与技术学院 卞佳丽 7
入线 出线
0 0
1
22
1
异步时分复用信号的交换
02
1 0
0 0
1
22 2
两种信号的交换
北京邮电大学计算机科学与技术学院 卞佳丽 8
交换单元按使用需要的不同可分为,
入线
0
M-1
出线0
N-1
入线 0
M-1
出线
0
N-1
出线
0
N-1
入线
0
M-1
集中型（ M>N） 扩散型（ M<N ）
连接型（ M=N）
北京邮电大学计算机科学与技术学院 卞佳丽 9
交换单元按信息流向分为：
? 有向交换单元：当信息经过交换单元时只能从入线
进出线出，具有唯一确定的方向。
? 无向交换单元：交换单元的每条线即可入也可出，
其入线数必等于出现数。
出线
0
N-1
入线
0
M-1
M X N有向交换单元
入
线
/
出
线
0
N-1
N无向交换单元
…
..
…
..
北京邮电大学计算机科学与技术学院 卞佳丽 10
交换单元的连接特性
连接特性是交换单元的基本特性，它反映了交换单元
入线到出线的连接能力，通常我们用 连接集合 和 连接函数
来描述交换单元的连接特性
? 连接集合：
入线集合,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} 为一个连接。
北京邮电大学计算机科学与技术学院 卞佳丽 11
? 若 r∈Rt, Rt中只含有一个元，则称该连接为点到点
连接。
? 若 r∈Rt, Rt中含有多个元，则称该连接为一点到多
点连接。
? 若一个交换单元可以提供点到多点的功能，但 Rt≠R,
则称其具有同发功能；若 Rt=R,则该交换单元具有广
播功能。
交换单元的连接特性
北京邮电大学计算机科学与技术学院 卞佳丽 12
交换单元的连接特性
一个交换单元的连接同时可有多个，这就构成了交
换单元的连接集合：
C={c0,c1,c2,…}
其中：起点集 Tc={t; t∈ ci,ci?C}
终点集 Rc={r; r∈ Rt,Rt ? ci,ci ? C}
? 连接和连接集合是对应于某一时刻的
? 连接集合的数目越多，连接能力就越强
北京邮电大学计算机科学与技术学院 卞佳丽 13
? 连接函数
一个连接函数对应一种连接，连接函数表示相互
连接的入线编号和出线编号之间的一一对应关系，即存
在连接函数 f,入线 x与出线 f(x)相连接,0≤x≤M-1，
0≤f(x)≤N-1。
连接函数实际上也反映了入线编号构成的数组和出
线编号构成的数组之间的置换关系或排列关系，故连接
函数也被称作 置换函数 或 排列函数 。
交换单元的连接特性
北京邮电大学计算机科学与技术学院 卞佳丽 14
? 函数表示形式
x表示入线编号（二进制表示）,f(x)表
示连接函数。
? 排列表示形式
即输入输出对应表示形式
t0,t1,…, t n-1
r0,r1,…, r n-1
? 图形表示形式
连接函数的表示形式
北京邮电大学计算机科学与技术学院 卞佳丽 15
直线连接：
函数表示,I(xn-1xn-2…x 1x0)= xn-1xn-2 … x1x0
排列表示（ N=4）, 0,1,2,3
0,1,2,3
图形表示（ N=4）,0 0
1
2
3
1
2
3
交换单元常用的连接函数
北京邮电大学计算机科学与技术学院 卞佳丽 16
交叉连接：
函数表示,E(xn-1xn-2…x 1x0)= xn-1xn-2 … x1x0
排列表示（ N=4）, 0,1,2,3
1,0,3,2
图形表示（ N=4）,0 0
1
2
3
1
2
3
交换单元的连接特性
北京邮电大学计算机科学与技术学院 卞佳丽 17
间隔交叉连接：
Ck(xn-1xn-2…x k … x1x0)= xn-1xn-2 …x k … x1x0
0 0
1
2
3
1
2
3
0 0
1
2
3
1
2
3
N=4 k=1 N=4 k=0
交换单元的连接特性
北京邮电大学计算机科学与技术学院 卞佳丽 18
均匀洗牌连接：
σ(xn-1xn-2…x k … x1x0)= xn-2 …x k … x1x0 xn-1
0
1
2
3N=8
4
5
6
7
0
1
2
3
4
5
6
7
交换单元的连接特性
北京邮电大学计算机科学与技术学院 卞佳丽 19
蝶式连接：
β(xn-1 xn-2…x k … x1 x0)= x0 xn-2 …x k … x1 xn-1
0
1
2
3N=8
4
5
6
7
0
1
2
3
4
5
6
7
交换单元的连接特性
北京邮电大学计算机科学与技术学院 卞佳丽 20
交换单元的性能
? 容量：
交换单元所有入线可以同时送入的总的信息量
? 接口：
交换单元需要规定自己的信号接口标准，即信号形式、
速率及信息流方向
? 功能：
点到点、同发、广播
? 质量：
完成交换动作的速度、任何情况下是否能完成指定连
接、信息经过交换单元是否有损伤（时间、语义）
北京邮电大学计算机科学与技术学院 卞佳丽 21
2.2 开关阵列与空间交换单元 ——开关阵列
在交换单元内部，要建立任意入线和任意出
线之间的连接，就在每条入线和每条出线之间都
各自接上一个开关，所有开关就构成了交换单元
内部的 开关阵列 。
北京邮电大学计算机科学与技术学院 卞佳丽 22
M X N有向交换单元
0 1 N-1
0
1
M-1
入线
出线
M X N有向矩形开关阵列
开关阵列的工作原理
出线
0
N-1
入线
0
M-1
…
..
…
..
北京邮电大学计算机科学与技术学院 卞佳丽 23
N无向方形开关阵列
入线
0
N-1
N无向交换单元
0 1 N-1
0
1
N-1
入线
出线
开关阵列的工作原理
北京邮电大学计算机科学与技术学院 卞佳丽 24
入线 /出线
0
N-1
N无向交换单元
无向交换单元开关阵列的实现（补充）
若在一个 N X N的交换单元中的连接总是对称的，即
如果入端 i连接到出端 j,则入端 j一定连接到出端 i,那么
相同编号的入端和出端可以看作一个同时具有发送和接
收信息能力的信息端，既具有 N个双向通信的信息端，
并且每个信息端都可以和任何其它的信息端相连，这样
的交换单元称作 N个信息端的无向交换单元，简称 N无向
交换单元。
北京邮电大学计算机科学与技术学院 卞佳丽 25
N无向交换单元的开关阵列
（用双向开关）
入线 /出线
0
N-1
N无向交换单元
0 1 N-2
1
N-1
无向交换单元开关阵列的实现（补充）
2
N-2
2
北京邮电大学计算机科学与技术学院 卞佳丽 26
0 1
0
1
N-1
N-1
无向交换单元开关阵列的实现（补充）
入线 /出线
0
N-1
N无向交换单元
N无向交换单元的开关阵列
（用单向开关）
北京邮电大学计算机科学与技术学院 卞佳丽 27
无向交换单元开关阵列的实现（补充）
若 N无向交换单元的 N个信息端可以分为两组，
分别为 K和 L个信息端。属于其中一组的信息端都可
以和另一组的任何信息端相连接，但是不能和本组
中的其它信息端相连，则称其为一个 K x L的无向交
换单元。
入线 /出线 0
K-1
K x L无向交换单元
0
L-1
… 入线 /出线…
（信息端） （信息端）
北京邮电大学计算机科学与技术学院 卞佳丽 28
K X L无向矩形开关阵列
0 1 L-1
0
1
K-1
K(K=L)无向方形开关阵列
0 1 K-1
0
1
K-1
入线 /出线 0
K-1
K x L无向交换单元
0
L-1
… 入线 /出线…
（信息端） （信息端）
无向交换单元开关阵列的实现（补充）
北京邮电大学计算机科学与技术学院 卞佳丽 29
K X L无向矩形开关阵列
（用双向开关）
0 1 L-1
0
1
K-1
无向交换单元开关阵列的实现（补充）
(K+L) X (K+L)有向开关阵列
（用单向开关）
0 1
0
1
K-1
K+0
K+L-1
K+0K+1 K+L-1K-1
K+1
北京邮电大学计算机科学与技术学院 卞佳丽 30
K 无向方形开关阵列
（用双向开关）
0 1 K-1
0
1
K-1
无向交换单元开关阵列的实现（补充）
2K X 2K有向开关阵列
（用单向开关）
0 1
0
1
K-1
K+0
K+K-1
K+0K+1 K+K-1K-1
K+1
北京邮电大学计算机科学与技术学院 卞佳丽 31
全连接交换单元和部分连接交换单元
0 1 N-1
0
1
N-1
入线
出线
0 1 N-1
0
1
N-1
入线
出线
北京邮电大学计算机科学与技术学院 卞佳丽 32
0
1
M-1
入线
出线
入线
0
M-1
出线
入线
0
N-1
出线
0 1 N-1
入线
出线
多路选择器
北京邮电大学计算机科学与技术学院 卞佳丽 33
开关阵列的特性
? 开关控制简单，从入线到出线具有均匀的单位延迟时
间。
? 开关阵列适合于构成较小的交换单元（开关数反映了
实现的复杂度和成本的高低）。
? 交换单元的性能依赖于所使用的开关。
? 控制信号简单
? 容易实现同发和广播功能
北京邮电大学计算机科学与技术学院 卞佳丽 34
继电器：其构成的交换单元是无向的，可交换模拟和数字信息，
干扰和噪声大, 动作慢（ ms级）、体积大（ cm级）。
模拟电子开关：一般利用半导体材料制成。
如,MC142100,MC145100（ 4 x 4开关阵列）
只能单向传送，且衰耗和时延较大。
数字电子开关：由简单的由逻辑门构成，用于数字信号的交
换，开关动作极快且无信号损失。
实际的开关阵列
北京邮电大学计算机科学与技术学院 卞佳丽 35
? 通断开关
交叉点可看成是一个具有通 /断功能的开关。其具体
实现比较复杂，包括 FIFO缓冲器和相应的控制逻辑。
? 多路选择器
开关阵列交叉点的实现（ 1）
北京邮电大学计算机科学与技术学院 卞佳丽 36
? Crossbar
交叉点是一个 2 x 2的传送门，它有两个状态,bar状
态和 cross状态。 Bar状态是指横向输入连到纵向输出，纵
向输入连到横向输出； cross状态是指横向输入连到横向输
出，纵向输入连到纵向输出。
交换矩阵在初始状态时，所有交叉点均处于 cross状态，
即任何入线与任何出线间均不连通。如果要使入线 i与出线 j
连通，则应使处于交叉点 （ i,j） 上的传送门处于 bar状态，
而在 i行和 j列的所有其它的传送门仍处于 cross状态。
开关阵列交叉点的实现（ 2）
北京邮电大学计算机科学与技术学院 卞佳丽 37
横向输入
纵向输入
纵向输出
横向输出
bar状态
cross状态
开关阵列交叉点的实现（ 3）
北京邮电大学计算机科学与技术学院 卞佳丽 38
1
2
3
4
1
2
3
4
1 2 3 41 2 3 4
crossbar 通 /断开关
开关阵列交叉点的实现（ 4）
北京邮电大学计算机科学与技术学院 卞佳丽 39
空间交换单元也称为 空间接线器 （ Space
Switch）,简称为 S单元 或 S接线器,用来实现
多个输入复用线与多个输出复用线之间的空间
交换，而不改变其时隙位置。
2.3 开关阵列与空间交换单元 ——空间交换单元
北京邮电大学计算机科学与技术学院 卞佳丽 40
S接线器的构成,交叉点矩阵, 控制存储器
交叉点矩阵,开关阵列
控制存储器 （ CM-Control Memory）：
? S接线器所含 CM数量等于入（出）线数
? 每个 CM的所含有的存储单元个数等于入（出）
线上的复用时隙数
? 每个存储单元为 n位 bit,且满足 N≤2 n,其中 N
为入（出）线上数
空间交换单元的基本结构
北京邮电大学计算机科学与技术学院 卞佳丽 41
空间交换单元的控制方式
0
1
2
0
1
20 1 2
TS12 TS8
TS12 TS8 0
8
12
127
2
TS8
TS8
输入控制方式
1
TS12
TS12
2 0
北京邮电大学计算机科学与技术学院 卞佳丽 42
空间交换单元的控制方式
0
1
2
0
1
20 1 2
TS12 TS8
TS12 TS8 0
8
12
2
TS8
TS8
输出控制方式
1
TS12
TS12
2
0
127
北京邮电大学计算机科学与技术学院 卞佳丽 43
空间交换单元的工作原理
北京邮电大学计算机科学与技术学院 卞佳丽 44
2.3、共享存储器型的交换单元 ——时间交换单元
0
1
N-1
输入信号 输出信号
共享存储器型交换单元的一般结构
工作方式：入线缓冲、出线缓冲
北京邮电大学计算机科学与技术学院 卞佳丽 45
时间交换单元也称为 时间接线器 （ Time
Switch）,简称为 T单元 或 T接线器,用来实现
时隙交换功能。所谓时隙交换是指入线上各个
时隙的内容要按照交换连接的需要，分别在出
线上的不同时隙位置输出。
时间交换单元
北京邮电大学计算机科学与技术学院 卞佳丽 46
T接线器主要由 话音存储器 （ SM:Speech
Memory） 和 控制存储器 (CM:Control memory)构
成。
SM用来暂存话音的数字编码信息，故每个单
元至少应为 8比特。 SM的容量等于输入复用线上
每帧的时隙数。
CM的容量等于 SM的容量；设 CM每个单元的比
特数为 n,SM的单元数为 N,则有 2n=N,N也就是复
用线上的时隙数。
时间交换单元的基本结构
北京邮电大学计算机科学与技术学院 卞佳丽 47
时间交换单元的控制方式
北京邮电大学计算机科学与技术学院 卞佳丽 48
2.4、共享总线型交换单元 ——数字交换单元
北京邮电大学计算机科学与技术学院 卞佳丽 49
入线控制部件的功能,
接收入线信号，进行相应的格式变换，放在缓冲存
储器中，并在分配给该部件的时隙上把收到的信息送到
总线上。
出线控制部件的功能,
检测总线上的信号，并把属于自己的信息读入一个
缓冲存储器中，进行格式变换，放在缓冲存储器中，由
出线送出，形成出线信号。
共享总线型交换单元
北京邮电大学计算机科学与技术学院 卞佳丽 50
总线,
一般包括多条数据线和控制线。数据线用于在入线
控制部件和出线控制部件传送信号；控制线用于控制各
入线控制部件获得时隙和发送信息，以及出线控制部件
读取属于自己的信息。
总线按时隙轮流分配给各个入线控制部件和出线控
制部件使用，其时隙的分配有一定的规则。
共享总线型交换单元
北京邮电大学计算机科学与技术学院 卞佳丽 51
数字交换单元（ DSE）
北京邮电大学计算机科学与技术学院 卞佳丽 52
数字交换单元（ DSE） 的工作原理
S
TS18
S
TS12
端口
RAM
话路
RAM
数据
RAM
0 0 0
31
D
31 31
P C
1212 188 18 S
北京邮电大学计算机科学与技术学院 卞佳丽 53
3、交换网络
交换网络 是由若干个交换单元按照一定的拓
扑结构和控制方式构成的网络。
交换网络的三个基本要素是,交换单元,不
同交换单元间的 拓扑连接 和 控制方式 。
北京邮电大学计算机科学与技术学院 卞佳丽 54
交换网络的一般结构
… …
控制单元
出线入线 … …
交换
单元
交换
单元
交换
单元
交换
单元
交换网络
北京邮电大学计算机科学与技术学院 卞佳丽 55
单级交换网络和多级交换网络
交换网络按拓扑连接方式可分为：单级交换网络
多级交换网络
出线
0
N-1
入线
0
M-1
单级交换网络
交换
单元
北京邮电大学计算机科学与技术学院 卞佳丽 56
单级交换网络和多级交换网络
如果一个交换网络中的交换单元可以分为 N级，顺序
命名为第 1,2,…,N级，并且满足：
所有入线都只与第 1级交换单元连接；
所有第 1级交换单元都只与入线和第 2级交换单元连接；
所有第 2级交换单元都只与第 1级和第 3级交换单元连接；
依此类推，所有第 N级交换单元都只与第 N-1级和出线
连接；
则称这样的交换网络为 多级交换网络,或 N级交换网络 。
北京邮电大学计算机科学与技术学院 卞佳丽 57
多级交换网络的拓扑结构可用三个参数来说明：
每个交换单元的容量
交换单元的级数
交换单元间的连接通路（链路）
单级交换网络和多级交换网络
北京邮电大学计算机科学与技术学院 卞佳丽 58
多级交换网络 (nm x nm两级交换网络 )
…
…
…
…
…
O
1
n-1
O
1
n-1
…O1
n-1
O
1
m-1
O
1
m-1
O
1
m-1
…
…
…
…
…
…
… …
O O
1 1
m-1 n-1
1级 2级
北京邮电大学计算机科学与技术学院 卞佳丽 59
多级交换网络的内部阻塞
若出、入线空闲，但因交换网络级间链路被占用而
无法接通的现象，称为多级交换网络的内部阻塞。
严格无阻塞网络,
不管网络处于何种状态，任何时刻都可以在交换网
络中建立一个连接，只要这个连接的起点、终点是空闲
的，而不会影响网络中已建立起来的连接。
北京邮电大学计算机科学与技术学院 卞佳丽 60
可重排无阻塞网络,
不管网络处于何种状态，任何时刻都可以在交换网
络中直接或对已有的连接重选路由来建立一个连接，只要
这个连接的起点、终点是空闲的，而不会影响网络中已建
立起来的连接。
广义无阻塞网络,
指一个给定的网络存在着固有的阻塞可能，但又可
能存在着一种精巧的选路方法，使得所有的阻塞均可避免，
而不必重新安排网络中已建立起来的连接。
多级交换网络的内部阻塞
北京邮电大学计算机科学与技术学院 卞佳丽 61
1
3
4
2
1
3
4
2C1
C1C2
C2
1,2,3,4
4,2,1,3
可重排无阻塞网络
北京邮电大学计算机科学与技术学院 卞佳丽 62
1
3
4
2
1
3
4
2C1
C1cc2
cc2
可重排无阻塞网络
北京邮电大学计算机科学与技术学院 卞佳丽 63
3.1 CLOS网络
为了减少交叉点总数而同时具有严格的无阻塞特性，
CLOS C.很早就提出一种多级结构，推出了严格无阻塞的
条件，这就是著名的 CLOS网络。
… …
…
1
n
…1
n
1
n
1
n
… …
1
…
1
m
1
r
1
1r
m
m
m
m
1
1
1 1
1 1
1
1
r
r
r
r
3级 CLOS网络
北京邮电大学计算机科学与技术学院 卞佳丽 64
在最坏情况下，中间级会有（ n-1） X 2个交换单元被
占用，因此中间级至少要有（ n-1） X 2+1=2n-1个交换
单元，即 m≥2n-1时，可确保无阻塞（严格无阻塞）。
CLOS网络
北京邮电大学计算机科学与技术学院 卞佳丽 65
3.2 TST网络
TST网络是在电路交换系统中经常使用的一种交换网
络，它是三级交换网络，两侧为 T接线器，中间一级为 S
接线器,S级的出入线数决定于两侧 T接线器的数量。
第 1级 T接线器：负责输入母线的时隙交换。
S接线器：负责母线之间的空间交换交换。
第 2级 T接线器：负责输出母线的时隙交换。
北京邮电大学计算机科学与技术学院 卞佳丽 66
1
2
3
1
2
31 2 3
TS2
TS31
0
7
23
31
3
TS2
TS31
S(输入控制 )
TS7
TS23
1
0
31
2
7 2
0
31
3123
23 2 2
317 31
CMA
CMA
SMA
SMA
SMB
SMB
CMB
CMB
TS23
TS7
T(输出控制 ) T(输入控制 )
A
B
A
B
北京邮电大学计算机科学与技术学院 卞佳丽 67
为减少选路次数，简化控制，可使两个方向的内部时
隙具有一定的对应关系，通常可相差半帧，俗称 反相法,
即：
设,Nf=一帧的时隙数
Na=A到 B方向的内部时隙数
Nb=B到 A方向的内部时隙数
则,Nb= Na +Nf/2
TST网络完全无阻塞的条件：
m（ 内部时隙数） =2n（ 输入时隙数）
3.2 TST网络
北京邮电大学计算机科学与技术学院 卞佳丽 68
关于 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
北京邮电大学计算机科学与技术学院 卞佳丽 69
3.3 BANYAN 网络
? Banyan 网络的基本结构
? Banyan 网络的基本特性
? BATCHER-BANYAN网络
? 基于 banyan的多通路结构
? Benes网络
北京邮电大学计算机科学与技术学院 卞佳丽 70
banyan网络可分为一些子类,L级 banyan是其中的一类，
其特征是只有相邻级之间才有链路相连，即任何输入到任何
输出之间的通路都经过 L级。
L级 banyan网络又可分为 规则 banyan和 不规则 banyan。
规则 banyan是指构成 banyan网络的各个交换单元都是等同的，
而不规则 banyan则不然。
如果规则 banyan中的各个交换单元不仅是等同的，而
且每个交换单元的入线数等于出线数，则称此规则 banyan为
矩形 banyan。
1,Banyan 网络的基本结构
北京邮电大学计算机科学与技术学院 卞佳丽 71
通常将由 2 X 2的交换单元构成的单通路网
络称为 banyan网络。
banyan网络是基于树型的拓扑结构，但每
一个交换单元却是基于 crossbar的结构。 2 X 2
的交换单元也具有 bar和 cross两种状态。
1,Banyan 网络的基本结构
北京邮电大学计算机科学与技术学院 卞佳丽 72
0
1
2
3
4
5
6
7
0
1
2
3
4
5
6
7
8 x 8的 3级 banyan网络
北京邮电大学计算机科学与技术学院 卞佳丽 73
树型结构特性,
从 banyan的任一输入端口引出的一组通路形成了 2
分支树，级数越多，分支越多，级数 k=㏒ 2N,N=总入
线数 /出线数，即 2k=N。
单通路特性,
banyan的任一入端到任一出端之间，具有 1条且仅
有一条通路。
自选路由特性,
自选路由，即是给定出线地址，不用外加控制命令，
就可选到出线。可以使用对应于出端号的二进制码的选
路标签来自动选路。
2,Banyan 网络的基本特性
北京邮电大学计算机科学与技术学院 卞佳丽 74
0
1
2
3
4
5
6
7
0
1
2(010)
3(011)
4(100)
5(101)
6
7
8 x 8的 3级 banyan网络
1
0
1
1
0
(011)
(010)
(100)
(101)
Banyan网络的自选路由特性
北京邮电大学计算机科学与技术学院 卞佳丽 75
可扩展性,
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是具有内部竞争的有阻塞网络。
2,Banyan 网络的基本特性
北京邮电大学计算机科学与技术学院 卞佳丽 76
16X
16BA
NY
AN
交
换
网
络
的
构
成
Banyan网络的可扩展性
北京邮电大学计算机科学与技术学院 卞佳丽 77
16X
16BA
NY
AN
交
换
网
络
的
构
成
Banyan网络的可扩展性
北京邮电大学计算机科学与技术学院 卞佳丽 78
1）内部阻塞是在 2X2交换单元的两条入线要向同一个出线
上发送信元时产生的，最坏情况下概率为 50%，若减少
入线上的信息量，就可减少阻塞的概率，故可通过适当
限制入线上的信息量或加大缓冲存储器来减少内部阻塞。
2）可以通过增加多级交换网络的级数来消除内部阻塞。已
有证明，若要完全消除 N X N的 banyan网络的内部阻塞，
至少需要 2㏒ 2N-1级。
3）可以增加 banyan网的平面树，构成多通道交换网络。
4） 使用排序 -banyan网络。
解决内部阻塞的方法
北京邮电大学计算机科学与技术学院 卞佳丽 79
该网络也简称为 B-B网，是由 BATCHER排序网和
BANYAN网组成，它成功地避免了 BANYAN网络的内
部阻塞，这是目前 ATM交换机使用较多的一种网络。
BATCHER排序网是由 2X2的比较器（ BATCHER比较器）
构成的。
x
y
min(x,y)
max(x,y)
x
y min(x,y)
max(x,y)
3,BATCHER-BANYAN网络
北京邮电大学计算机科学与技术学院 卞佳丽 80
BATCHER-BANYAN网络
011
111
010
100
011
010
100
111
111
100
010
011
BATCHER-BANYAN网络
北京邮电大学计算机科学与技术学院 卞佳丽 81
为了减少或消除 banyan的内部阻塞，提高吞吐率，
除了构成 B-B网络之外，还可以构成基于 banyan的的各种
多通路网络。
（ 1） 增长型 banyan
增长型 banyan就是前面加上分配级，以扩大每个入端
的选择范围，从而形成多通路网络。每增加 1级，每个入
端与每个出端之间的通路数就增加 1倍 。 前置分配级还可
以使业务流均衡地进入 banyan的入端，减少 banyan对流入
的业务流模型的敏感性。
4、基于 BANYAN的多通路结构
北京邮电大学计算机科学与技术学院 卞佳丽 82
0
1
2
3
4
5
6
7
0
1
2
3
4
5
6
7
增长型 banyan
增长型 BANYAN
北京邮电大学计算机科学与技术学院 卞佳丽 83
（ 2） 扩展型 banyan
考察 banyan中的交换单元，对应于每个交换单元输出
地址有 1条链路，如果使每个输出地址有 d条链路，也就是
可以任意选择 d条中的 1条，就称为扩展型 banyan。
在扩展型 banyan 网中, 2× 2的 交换单 元变成了
2d× 2d的交换单元 。 但输出地址并非 2d个, 而仍然是 2个,
只要用 1个比特来区别 。 于是在任何时刻, 最多可有 d个信
息单元传送到交换单元的每个输出；如果对应于同一输出
地址同时有多于 d个的信元到达, 只能传送其中的 d个 。
4、基于 BANYAN的多通路结构
北京邮电大学计算机科学与技术学院 卞佳丽 84
0
1
2
3
4
5
6
7
0
1
2
3
4
5
6
7
扩展型 banyan
扩展型 BANYAN
北京邮电大学计算机科学与技术学院 卞佳丽 85
（ 3） 膨胀型 banyan
膨胀型 banyan是膨胀度 d在各级可以变化的扩展型
banyan。
（ 4） 复份型 banyan
复份型 banyan是将若干个相同的 banyan并接在一起,
形成多平面的网络结构 。
从复份型 banyan的每个输入端进入的信息单元, 可
以随机地选择某个平面, 也可以按负荷均分原则分配到各
个平面, 还可以广播到所有的平面 。
4、基于 BANYAN的多通路结构
北京邮电大学计算机科学与技术学院 卞佳丽 86
0
1
2
3
4
5
6
7
0
1
2
3
4
5
6
7
膨胀型 banyan
d=2 d=3 d=4
膨胀型 BANYAN
北京邮电大学计算机科学与技术学院 卞佳丽 87
Banyan 1
Banyan 2
Banyan r
… …
…
…
……
…
…
… …
1
2
n
1
2
n
复份型 banyan
复份型 BANYAN
北京邮电大学计算机科学与技术学院 卞佳丽 88
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交换单元为止 。
4,BENES网络
北京邮电大学计算机科学与技术学院 卞佳丽 89
0
1
2
3
4
5
6
7
0
1
2
3
4
5
6
7
8 X 8 benes网络
8 X8 BENES 网络
北京邮电大学计算机科学与技术学院 卞佳丽 90
0
1
2
3
4
5
6
7
0
1
2
3
4
5
6
7
benes网络构成方法
N/2 X N/2
N/2 X N/2
BENES 网络构成方法
北京邮电大学计算机科学与技术学院 卞佳丽 91
作业（ 1）
1、有一个 T-S-T交换网络，有 8条输入母线和 8条输出
目线，每条母线为一帧 256个 TS,其第一级 T接线
器为输入控制方式,S接线器为输出控制方式，第
二级 T接线器为输出控制方式，请画图表示该网络
将 HW6TS8交换到 HW2TS23的过程（内部选定的空闲
时隙为 TS15 ），并标出各级 SM和 CM的容量及相关
单元内容，给出 CP的时间 。
北京邮电大学计算机科学与技术学院 卞佳丽 92
作业（ 2）
2、构造 16*16的交换单元：采用基本开关阵列时，需要
多少个开关？采用 K=4的绳路开关阵列时，需要多
少个开关？采用可重排无阻塞网络时，需多少个 2*2
交叉单元？采用 BANYAN网络时，需多少个 2*2交叉
单元？采用共享存贮器结构时，至少需 多少个存储
单元。
3、构造 256*256的三级严格无阻塞 CLOS网络。要求：
入口级选择 8入线的交换单元，出口级选择 8出线的
交换单元。画出该网络连接示意图（标出各级交换
单元的个数，入出线）。
北京邮电大学计算机科学与技术学院 卞佳丽 93
本章小结
描述交换单元连接特性的方法
交换单元的外部特性描述的描述指标
三种典型的交换单元的结构、特性及工作原理
无阻塞网络的概念，构成无阻塞网络的方法
TST,CLOS,BANYAN网络的结构及特性
