哈工大交换技术排序banyan网络

Harbin Institute of Technology

排序—Banyan网络 及内部阻塞的避免

院 系： 电信学院 班 级： 1105104班 姓 名： 学 号： 指导教师：

哈尔滨工业大学

排序—Banyan网络及内部阻塞的避免

摘要：Banyan网络是由2?2交换单元组成的一种空分交换网络，多用于ATM交换机和光交换系统。Banyan网络具有唯一路径特性和自选路由功能，路由选择十分简单，缺点是会发生内部阻塞，这是由于一条内部链路可以被多个不同的输入端同时使用造成的。本文先介绍了Banyan网络的结构和特点；然后分析了非阻塞条件，并提出了避免内部阻塞的方法；最后，介绍排序—Banyan网络，回答了为什么当输入信息的地址按单调顺序排列时，可避免N×N的狭义Banyan网络内部阻塞这一问题。

关键词：Banyan网络 内部阻塞 排序—Banyan网络

一、Banyan网络的结构和特点

（一）Banyan网络的结构

Banyan网络是由2?2交换单元组成的一种空分交换网络，多用于ATM和光交换系统。

这种电子开关具有两种状态：平行连接和交叉连接，分别完成不同编号的入线和出线间的连接，达到两条入线中的任意入线和两条出线中的任意出线可进行交换的目的。由4个2?2交换单元可以构成一个4?4的二级交换网络。

其结构如下图所示：

(a)平行连接第1级0123(b)交叉连接图2.36 2X2交换单元第2级0123图2.37 4X4交换单元 8?8网络，由3级12个单元组成，我们可以把前面的8个2?2交换单元看成是两个4?4的二级交换网络，后面再加上一级4个2?2交换单元，构成8?8的三级交换网络，8?8网络的结构如下图所示。16?16网络，需4级共32个单元组成。

- 1 -

第1级0123第2级第3级012345674567

8?8交换网络

由此我们可知，一个N?N的Banyan网络，级数为M?log2N，每级需N/2个单元，共需(

N?M)个2?2的交换单元。 2（二）Banyan网络的特点

1、唯一路径，入线到出线只有一条路经。

由Banyan网络的结构我们可以看出，它的每条入线与每条出线之间都有一条路径并且只有这一条路径。这就是Banyan网络的唯一路径特点。

2、自选路由，网络入出线相等。

自选路由，即给定出线地址，不用外加控制命令，就可选择到出线。

由Banyan网络的构成方法可知，一个Banyan网络的入线数和出线数相等。并且若假设其为N，则必有N?2M，M为级数再设N条出线分别顺序编号为十进制数0、1、2、?、N-1，则必定可用M位二进制数字来区别N条入线和N条出线。由此可知，如果我们把出线的编号（地址）以二进制数字的形式送到交换网络，那么，每一级上的2?2交换单元就只需要根据这个地址中的某一位就可以判别应该将其送到那一条出线上。比如说，在第一级上的2?2交换单元中只读地址的第一位，在第二级上的2?2交换单元中只读地址的第二位，??，当所有地址都被读完，这个信元就已经被送到相应的出线上了。

3、编号数字置换，即实现入线编号顺序变换。

Banyan网络的入线和出线可以都编上号码，并用一组数字的排列（置换）来表示它的一种连接方式。例如，连接函数：

? 0 1 2 3? ? ?? 3 0 2 1?

- 2 -

可以实现：

01230123

二、Banyan网络的内部阻塞

多条入线都想从同一出线输出，称作出线阻塞，属业务竞争，与网络结构无关。除最末级外，网络内部不能实现到某一空闲出线的连接，称作内部阻塞。Banyan网络的内部阻塞随着网络级数的增加而变大，因此不能实现大容量网络。

（一）Banyan网络的非阻塞条件

BN本身是一个阻塞网络，入的分组具有相同的目的地址，它们就会在相同的出线路上碰撞 ，这也称为输出阻塞。对于一个K阶段的BN，如果在同一时隙内两个分组在前面第K-1阶段的任何交换结点的输出链路上相遇，就会产生内部阻塞。在一定的条件下，BN由阻塞网络变成非阻塞网络，只要对BN的输入分组作一定的排列和限制就能做到这一点。如果假设激活（具有数据信息的）分组的输入端号为X1，?，Xn(1Y2>?>Yn。

②激活的输入端的分组必须是连续的或集中在一块。也就是说在两个激活输入端之间的任何输入端也是被激活的，即X1

下面对其结论给予详细的证明和论述。

已知BN有N个输入端和输出端及K个阶段，从图3可以看出，在第m(1

(ak?m...a1,b1...bm?1)来表示。需要说明的是ak?m...a1是阶段m子网络内部交换节点

b1...bm?1从顶往下数的标号，取值范围是从0到（2k?m?1），且当m=k时，取0值。是阶段m子网络的标号，取值范围是从0到（2m?1?1），特殊情况下m=1时取0值。

由于阶段m+1的交换节点(ak?m?1...a1,b1...bm)与阶段m的交换节点

(ak?m...a1,b1...bm?1)的输出链路bm(0，1)有关。一个分组从输入端x =am?a1，到

- 3 -