Harbin Institute of Technology
BANYAN网络的特性
哈尔滨工业大学 通信工程系
2012
引言：
BANYAN网络是一种空分交换网络，最早使用于并行计算机领域，但目前已在ATM交换机中得到了广泛的应用。BANYAN网络具有唯一路径特性和自选路由功能。唯一路径特性指任何一条入线和任何一条出线之间存在并仅存在一条通路；自选路由功能指不论信元从哪条入线进入网络，它总能到达指定出线。由于到达指定的输出端仅有唯一一条通路，因此路由选择十分简单，即可由输出地址确定输入和输出之间的唯一路由。缺点是会发生内部阻塞，这是由于一条内部链路可以被多个不同的输入端同时使用造成的。BANYAN网络的优点是结构简单，模块化、可扩展性好，信元交换时延小。它适用于统计复用信号的交换，即根据信号中携带的出线地址信息，在交换网络中建立通道，是进行信元交换的有效方法之一。
BANYAN网络的结构：
0BANYAN网络其基本结构是由若干个2?2交换单元组成的多级交换网络。
具体结构如下图2?2交换单元是具有两条入线和两条出线的电子开关元件，
000所示：
1111平行连接交叉连接
这种电子开关具有两种状态：平行连接和交叉连接，分别完成不同编号的入
线和出线间的连接，达到两条入线中的任意入线和两条出线中的任意出线可进行
交换的目的。
由4个2?2交换单元可以构成一个4?4的二级交换网络。其结构如下图所示：
第1级01第2级0123234?4交换网络
其中，第1级和第2级之间的连接为均匀洗牌连接。图中画出了由入线0到同样，如果我们使用12个2?2交换单元就可以构成一个8?8的三级交换网
出线0和由入线3到出线1的路径。
络。其第1级和第2级之间的连接为子洗牌连接，第2级和第3级之间的连接为
均匀洗牌连接。它同样具备上述特点。
我们可以把前面的8个2?2交换单元看成是两个4?4的二级交换网络，后面
第1级0123第2级第3级0123再加上一级4个2?2交换单元，构成8?8的三级交换网络。
456745678?8交换网络
这种将多个2?2交换单元分成若干级，并按照一定的级间连接方式构成的多
级交换网络，就称为BANYAN网络。 由上述的4?4和8?8BANYAN网络实例，我们发现BANYAN网络的结构是很规则的，利用递归的方法，可用较小的BANYAN网络构成较大的BANYAN网络。其构成方法如下： 假设已有N?N的BANYAN网络，需构成2N?2N的BANYAN网络。则可使用2组N?N，再加上一组N个2?2交换单元构成。第一组N?N的N条出线分别与N个2?2的某一入线相连，第二组N?N的N条出线分别与N个2?2的另一入线相连。例如，用8?8BANYAN网络构成16?16BANYAN网络时，可用2组8?8，加上8个2?2交换单元构成，共需32个2?2交换单元。
对于N?N的BANYAN网络，其级数约为M?log2N，每一级需要N/2个
个2?2交换单元。
2?2交换单元，共需?N/2?log2NBANYAN网络的特性：
⑴唯一路径
由BANYAN网络的结构我们可以看出，它的每条入线与每条出线之间都有一条路径并且只有这一条路径。这就是BANYAN网络的唯一路径特点。
首先4?4的BANYAN网络是具有唯一路径的。我们假设它对N?N的BANYAN网络也成立，那么，对于2N?2N的BANYAN网络来说，因为2N?2N的BANYAN网络是用前述方法来构建的，显然从N?NBANYAN网络到最后一
级2?2交换单元中共有2N条路径，并且要到其中某一条出线必须经过其中唯一的一条路径。可见这样构成的2N?2N的BANYAN网络仍然是在每条入线和每条出线间都存在一条路径并且只有唯一的一条路径。
⑵自选路由
由BANYAN网络的构成方法可知，一个BANYAN网络的入线数和出线数
相等。并且若假设其为N，则必有N?2M,M为级数再设N条出线分别顺序编号为十进制数0、1、2、…、N-1，则必定可用M位二进制数字来区别N条入线和N条出线。
由BANYAN网络的唯一路径特点可知，从BANYAN网络的任意一条入线到全部N条出线共有N个连接，这N个连接可以用出线的N个不同的编号表示，即其中的每一个连接都可以用M位二进制数字表示。
一个N?N的BANYAN网络共有M级，每一级有N/2个2?2交换单元。如果把每个交换单元的两条入线和两条出线都依照在图上的上下位置分别编号为0和1。考虑一个由入线i到出线j的连接，这个连接是由M个属于不同级的交换单元顺序连接组成的。从第一级开始顺序排列该连接经过的各个交换单元的出线编号（0或1），则恰好组成一个M位二进制数字，这M位二进制数字正是出线j的编号。也就是说，BANYAN网络的每一级正好对应M位二进制数字中的一位。我们从任意一条入线开始，逐个读出各级交换单元相应出线的数字0或1,那么，这些数字组合起来就是出线的号码。可以说明，这个数字的N种不同的取值正好表示了从同一条入线出发的N个不同的连接或路径。下图是一个BANYAN网络，在图中标示了全部8条通往出线3上的路径，每条路径
上三个交换单元的出线号码都分别是0、1、1，组合起来的二进制数字011正是BANYAN网络的出线号码3.
第1级01230101第2级0101第3级010101238?8的
45670101自选路由示例010101014567
因此很自然的使我们想到，如果我们把出线的编号（地址）以二进制数字的形式送到交换网络，那么，每一级上的2?2交换单元就只需要根据这个地址中的
某一位就可以判别应该将其送到那一条出线上。比如说，在第一级上的2?2交换单元中只读地址的第一位，在第二级上的2?2交换单元中只读地址的第二位，……，当所有地址都被读完，这个信元就已经被送到相应的出线上了。显然，如果能够利用到这一点，则交换网络的控制部分就可以做得十分简单。这显然也是一个很大的优点。这就叫做自选路由，即给定出线地址，不用外加控制命令，就可选择到出线。对于统计复用信号，每个信元均携带有控制信息，包括路由信息，即出线地址，使用BANYAN网络可以很方便的进行交换。
⑶编号数字置换
BANYAN网络的入线和出线可以都编上号码，并用一组数字的排列（置换）来表示它的一种连接方式。例如，对于4?4BANYAN网络，给定连接函数的排列表示为
?0??310223?? 1?这表示，四条入线和四条出线分别编号为0、1、2、3，入线3连接到出线1，入线2连接到出线2，入线1连接到出线0，入线0连接到出线3.如下图所示。
第1级010101第2级0123232323编号数字置换示例
虽然任何一个交换单元及交换网络都可以用置换来表示其连接方式，但对BANYAN网络使用置换表示有特别意义。这是因为，BANYAN网络是按级由
2?2交换单元组成的每一个交换单元都完成两个数字的一次置换，每一级都完成
N个数字的一次置换。换句话说，在BANYAN网络中，表示整个交换网络连接方式的置换是由各级及级间逐次置换构成，例如，上图的连接方式的实现是有以下各级间置换的叠加：
第一级交换单元完成的连接置换：
?0??110233?? 2?第一级交换单元和第二级交换单元之间完成的连接置换：
?0??012213?? 3?第二级交换单元完成的连接置换：