第2章 交换单元与交换网络(2.3.4)

如果我们使用12个2×2交换单元就可以构成—个8×8 的三级交换网络，其第1级和第2级之间的连接为子洗牌连接， 第2级和第3级之间的连接为均匀洗牌连接。如图所示。
6
图11 8×8三级BANYAN网络
7
利用递归的方法，可用较小的BANYAN网络构成较大 的BANYAN网络。其构成方法如下：
假设已有N×N的BANYAN网络，需构成2N×2N的
22

连接1：0—3
连接2：1—7
连接3：4—2 连接4：6—4 当连接1和连接3同时到达第2级交换单元时，必然会同时选 择该交换单元的出线1，于是发生内部阻塞。如果不采取 适当措施，就会造成信元丢失，如图中入线4上的信息未 送到出线2。 应该注意的是，BANYAN网络的内部阻塞发生在2×2交换 单元内部,而不是级与级之间的链路上。
27

(1) 排序网络
一个N输入的排序网络，也称为N-排序器，是一种满足 下述条件的具有N个输出的开关阵列。即给定输入
I {i0 , i1 , , iN 1}
对输入I的任意组合，所形成的输出
O {o0 , o1 ,, oN 1} ，且
o0 o1 oN 1
28
一种常用的构成排序网络的开关是由BATCHER首先 定义的2—排序器，即2×2比较器，也称BATCHER比较器。 由它构成的排序网络就被称为BATCHER排序网络。 BATCHER比较器如图所示，它实际上是一个两入线／两出 线的比较交换单元，将入线上的两个数字进行比较后。高地 址信元送到高端(N)．低地址信元送到低端(L)，当仅有一个 信元时，将它送到低端。
011 111 010 011 100 111 010
banyan 网络
010 011 100
100 111
32
batcher 排序网络
011 111 011 011 111 011 011 100 011 010 100 111 111 010 010 011 100 111
banyan 网络
111
21


3)BANYAN网络的内部阻塞
BANYAN网络不是CLOS网络，它不符合CLOS网络的无 阻塞条件，因此BANYAN网络存在内部阻塞
①发生阻塞的2×2交换单元在交换网络的最后一级，即交换 网络的两条或多条入线同时试图占用同一条出线，这称为 出线阻塞。由于出线阻塞不是由于交换网络本身的缺陷造 成的，采用诸如输入或输出缓冲排队方法可以很好地解决。 所以通常内部阻塞不包括出线阻塞。 ②发生阻塞的2×2交换单元在交换网络的各级(除最后一级之 外)，例如在图14中，假设在入线0、1、4、6上同时接收 到信元，其路由标记分别为3、7、2、4，即此时需要建立：
26
4) 排序—BANYAN网络
经过研究发现，只要BANYAN网络同时输入的全部数据 块(信元)的出线地址(路由标签)单调排列(即单调递增或单调
递减)，则不存在内部阻塞。
因此，为了满足BANYAN网络无阻塞条件，解决 BANYAN网络的内部阻塞，可在BANYAN网络前加入排序 网络，构成排序—BANYAN网络。
用2×2变换单元构成BANYAN网络的具体形式可以
有多种，如图所示的几种交换网络均为8×8BANYAN类网 络。
10
图13 8×8三级BANYAN类网络
11

2) 工作原理 因为BANYAN网络的构成非常规则，由其结构可以 引出—些重要的特点。 (1)唯一路径 在BANYAN网络中，我们已经知道它的每条入线与 每条出线之间都有一条路径并且只有这一条路径。这就是 BANYAN网络的唯一路径特点。 可以利用类似于数学归纳法的方法给予证明。
29
图15BATCHER比较器
30
(2) BATCHER—BANYAN网络
BATCHER—BANYAN网络，简称B-B网，是由 BATCHER排序网和BANYAN网络组成的．它用独具匠心
的拓扑结构，成功地避免了BANYAN网络的内部阻塞，这 是目前ATM交换机使用较多的一种网络。
31
batcher 排序网络
2. 自选路由： 从任意一条入线开始，逐个读出各级交换单元相应出
线的数字0和1，那么，这些数字组合起来就是出线的号码。
18
0 1 2
0 1 0
0 1 0
0 1
0 1
3
4 5
1
0 1 0 1
1
0 1 0 1
0 2 1 3 0 4 1 5 0 6 1 7
6
7
ห้องสมุดไป่ตู้
i号入线到3号出线的自选路由特性演示
19
(3)编号数字置换
像任何交换单元及交换网络一样．BANYAN网络的入 线和出线可以都编上号码，并用一组数字的排列或称置换来
表示它的一种连接方式。
20
虽然任何一个交换单元及交换网络都可以用置换来表 示其连接方式，但对BANYAN网络使用置换表示有特别的 意义。这是因为，BANYAN网络是按级由2×2交换单元组 成的，每一个2×2交换单元都完成两个数字的一次置换，每 一级都完成N个数字的一次置换。换句话说，在BANYAN网 络中，表示整个交换网络连接方式的置换是由各级及级间逐 次置换构成。
23
图14 BANYAN网络内部阻塞
24

①内部阻塞是在2×2交换单元的两条入线要向同一个出线上 发送信元时产生的，在最坏的情况下，这个概率是1／2。但 是，如果入线上并不总是有信号，这个概率就会下降。因此， 可以通过适当限制入线上的信息量或加大缓冲存储器来减少 内部阻塞。
②可以通过增加多级交换网络的级数来消除内部阻塞。例如，
111
010 011 100
010 100 100 010 100 010 100
010
111
33
15
由BANYAN网络的唯一路径特点可知，从 BANYAN网络的任意一条入线到全部N条出线共有N个 连接，这N个连接可以用出线的N个不同的编号表示， 即: 其中的每一个连接都可以用M位二进制数字表示。
16
一个N×N的BANYAN网络共有M级，每一级有
N／2个2×2交换单元。可以把每个交换单元的两条入线和 两条出线都依照在图上的上下位置分别编号为0和1。
2
3
1) 结构 2×2交换单元是具有两条入线和两条出线的电子开关
元件，如图所示。
4
两种状态：平行连接和交叉连接，
分别完成不同编号的入线与出线间的连接，达到两条 入线中的任意入线和两条出线中的任意出线可进行交换的目
的。
一个特点: 就是它的每一条入线到每一条出线都有一条路径，并 且只有一条路径。
5
12
假设它对N×N的BANYAN网络也成立．那么: 对于2N×2N的BANYAN网络来说，因为2N×2N的
BANYAN网络是用前述的方法来构成的．显然从N×N BAHYAN网络到最后一级2×2交换单元中共有2N条路 径．要到其中某一条出线必须经过其中唯一的—条路径。
13
BANYAN网络特性
Error!
考虑一个由入线i到出线j的连接，这个连接是由M个 属于不同级的交换单元顺序连接组成的。 从第1级开始顺序排列该连接经过的各个交换单元的 出线编号(0或1)，则恰好组成一个M位二进制数字，这M 位值二进制数字正是出线ｊ的编号。
17
我们从任意一条入线开始，逐个读出各级交换单元相
应出线的数字０或1，那么，这些数字组合起来就是出线 的号码。可以说明，这个数字的Ｎ种不同的取值正好表示 了从同一条入线出发的N个不同的连接或路径。

2.3.4. BANYAN网络
BANYAN网络是—种空分交换网络，是由若干个2×2交换 单元组成的多级交换网络，它最早使用干并行计算机领域，
目前巳在ATM交换机中得到广泛应用。
它适用于统计复用信号的交换，即根据信号中携带的出线 地址信息，在交换网络中建立通道，是进行信元交换的有效 方法之一。
1
孟加拉榕树（banyan）

把8×8BANYAN网络的级数由3增加到5，就可以消除内部 阻塞。事实上，有人已经证明了，若要完全消除N×N的 BANYAN网络(其级数为M＝log2N)的内部阻塞，至少需要 2log2N一1级。 25

③可以增加BANYAN网络的平面数，构成多通道交换网络。
④使用排序—BANYAN网络，这是近年来解决BANYAN网 络的内部阻塞问题的一个重要研究成果。
0 1 2 3 0 1 2 3
惟一路径
Error!
4
5 6 7
4 5 6 7
Error!
0号入线到3号出线的惟一路径特性演示
14
(2) 自选路由
由BANYAN网络的构成方法可知，一个BANYAN 网络的入线数和出线数相等。并且若假设其为N。则必 有N=2M，M为级数。再设N条入线和N条出线分别顺序 编号为十进制数0、1、2、……N-1，则必定可用M位二 进制数字来区别N入线和N条出线。
BANYAN网络。
则可使用2组N×N，再加上一组N个2×2交换单元构 成。第一组和第二组N×N的2N条出线分别与N个2×2的入 线用洗牌连接方式相连。
8
图12 用8×8三级BANYAN网络构造16×16四级BANYAN
9
对于N×N的BANYAN网络，其级数约为M＝log2N，每 一级需要N/2个2×2交换单元，共需要(N／2) log2N个2×2变 换单元。