中国与世界研究：太平洋战争爆发后的BANYAN网络

2．2．5　BANYAN网络

1．BANYAN网络概念

BANYAN网络是一种空分交换网络，是由若干个2×2个交换单元组成的交换网络，最早应用于计算机领域，与电信交换毫不相干，但它适于统计时分复用信号和异步时分复用信号的交换，目前在电信领域的ATM交换机中得到了广泛的应用。

（1）交换单元的结构

2×2交换单元是具有两条入线和两条出线的电子开关，它在不同的控制信号作用下，工作在不同的状态，实现入线和出线之间的不同互联。其工作状态有5种：平行连接、交叉连接、上播、下播和环回连接，如图2．30所示。

（2）BANYAN网络

由4个2×2交换单元可以构成一个4×4的二级交换网络，如图2．31所示。其中，第一级和第二级之间的连接为均匀洗牌连接，其排列表示式为：

图2．30　2×2交换单元的连接方式

注意，这种交换网络的每一条入线到每一条出线都有一条路径，并且只有一条路径。例如，在图2．31中画出了由入线0到出线0和由入线3到出线1的路径。

同样，用12个2×2交换单元就可以构成一个8×8的三级交换网络，其第一级和第二级之间的连接为子洗牌连接，第二级和第三级之间的连接为均匀洗牌连接，如图2．32所示。它同样具备上述特点。

图2．31　4×4交换网络

图2．32　8×8交换网络

分析图2．32可见，前面的8个2×2交换单元可看成是2个4×4的二级交换网络，后面再加上一级4个2×2交换单元，构成8×8的三级交换网络。

这种将多个2×2交换单元分成若干级，并按照一定的级间连接方式构成的多级交换网络，被称为BANYAN网络。

BANYAN网络的结构是很规则的，利用递归的方法，可用较小的网络构成大型网络。假设已有N×N的BANYAN网络，构成2N×2N的BANYAN网络，则可使用2组N×N的BANYAN网络以及N个2×2的交换单元构成。第一组N×N的N条出线分别与N个2×2的某一入线相连，第二组N×N的N条出线分别与N个2×2的另一入线相连。例如，用8×8 BANYAN网络构成16×16 BANYAN网络时，可用2组8×8，加上8个2×2交换单元构成，如图2．33所示。

对于N×N的BANYAN网络，其级数约为M＝lbN，即2　^M＝N。每一级需要N/2个2×2交换单元，共需要（N/2）lbN个2×2交换单元。用2×2交换单元构成BANYAN网络的具体形式可以有多种，如图2．34中的几种交换网络均为8×8 BANYAN网络。

2．BANYAN网络及其特性

由于BANYAN网络的构成非常规则，由其结构可以引出4个重要的特点。

图2．33　16×16交换网络

图2．34　8×8 BANYAN网络的各种形式

（1）树型结构

从网络的任一输入端口引出的一组通路形成了二分叉树，级数越多，分叉（分支）越多，如图2．35所示。

（2）唯一路径

BANYAN网络的任一入线与任何一条出线之间都有一条路径并且仅有一条路径。对于这一点，可以用类似于数学归纳法的办法来证明，这里不再证明。

图2．35　BANYAN网络的树型结构

（3）自选路由

以上分析可知，BANYAN网络是基于树型结构，且还是二叉树结构，即在任一级的交换单元上，一条输入线上的信息可有两个输出选择，这两个输出选择可用二进制的0和1来表示。一个BANYAN网络的入线数和出线数相等，假设为N，则必有N＝2^M，M为级数，每一级需要N/2个2×2交换单元。再设N条入线和N条出线的编号分别为十进制数0，1，2，…，N－1，则必定可用M位二进制数字来区别N条入线和N条出线。

由BANYAN网络的唯一路径特点可知，从BANYAN网络的任意一条入线到全部N条出线共有N个连接，每一个连接都可以用M位二进制数字表示。

例如，一个8×8的BANYAN网络共有三级，每一级有8/2个2×2交换单元。如果把每个交换单元的两条入线和两条出线都分别用0和1表示。考虑BANYAN网络的每一级的出线号码正好对应三位二进制数字中的一位。从任意一条入线开始，逐个读出各级交换单元相应出线的数字0或1，这些数字组合起来就是出线的号码。可以说明，这个数字的8种不同的取值正好表示了从同一条入线出发的8个不同的连接或路径。图2．36标出了0、2、4、7四条通往出线3上的路径，如图中虚线所示，每条路径上3个交换单元的出线号码都是0、1、1，组合起来的二进制数字011正是BANYAN网络的出线号码3。因此，BAN－YAN网络可实现自选路由，方法是给进入交换网络要进行交换的信息加上选路标签，该标签就是信息要交换到的目的输出线号的二进制值。每一级交换单元根据选路标签中的二进制值的相应位来选路，该位二进制的值为0则选0号出线，为1则选1号出线，网络的第一、二、直至M级分别与二进制值的由高到低位相对应。BANYAN网络中的第一、二、三级交换单元分别根据选路标签中的最高位、第二位和最低位二进制代码进行选路，选路标签中相应位为0时，交换单元将信息送往相应交换单元的0输出线上，当选路标签中相应位为1时，交换单元将信息送往相应交换单元的1输出线上，根据这个原则BANYAN网络自动把选路标签011的信息交换到二进制编码为011的出线3上。这叫做自选路由，即给定出线地址，不用外加控制命令，就可选择到出线。如果能够利用这一点，则交换网络的控制部分就可以做得十分简单。对于统计复用信号，每个信元均携带有控制信息，包括路由信息，即出线地址，使用BANYAN网络可以很方便地进行交换。因此，目前BANYAN网络在ATM交换机中应用很广泛。

（4）内部竞争

BANYAN是有阻塞的网络，因为BANYAN网络的任意一条入线到任意一条出线之间都具有唯一的一条通路。假如在某一时刻，信息要从入线0交换到出线3，同时还有信息要从入线2交换到出线2，那么在这一时刻会在第二级与第三级的公共链路上产生竞争，发生阻塞，如图2．37所示。

BANYAN网络的内部阻塞是随着网络级数的增加而增加的，当级数太多时，内部阻塞就会变得不可容忍，所以，必须解决BANYAN网络的内部阻塞问题。

3．BATCHER－BANYAN网络

目前解决BANYAN网络内部阻塞问题的方法很多，但用得较多的是使用排序的方法来解决，如果BANYAN网络同时输入的全部数据块（信元）的出线地址（路由标签）单调排列（即单调递增或单调递减），那么，BANYAN网络就不会出现内部阻塞。因此，为了解决BANYAN网络的内部阻塞问题，可以在BANYAN网络前加入排序网络－－BATCHER网络，构成BATCHER－BANYAN网络，简称B－B网。

(www.xing528.com)

图2．36　BANYAN网络自选路由示意图

图2．37　BANYAN网络的内部竞争示意图

BATCHER网络是由被称为BATCHER排序器的2×2排序器构成。BATCHER排序器如图2．38所示。它实际上是一个两入线/两出线的比较单元，将两入线上信息的选路标签进行比较，高地址信元送到高端（H），低地址信元送到低端（L），当仅有一个信元时，将它送到低端，作为选路标签小的信息来处理。

图2．38　BATCHER排序器

BA TCHER排序器分为向上排序器和向下排序器两种，向上排序器是将路由标签大的信息排到输出端上面的输出线上（按路由标签升序排列），向下排序器是将路由标签大的信息送到输出端下面的输出线上（按路由标签降序排列）。

用向上排序器和向下排序器，就可以构成BATCHER排序网络，在BATCHER排序网络后面加上BANYAN网络，可构成B－B网络。图2．39是一个8×8的B－B网网络，其中BA TCHER排序网络是按递增顺序排序的。

假设在入线0、1、4、6上同时输入信息，其选路标签分别是011、111、010、100，即分别要交换到出线3、7、2、4上，即此时需要在交换网络中建立4条连接：

连接1：0→3

连接2：1→7

连接3：4→2

连接4：6→4

若直接使用8×8 BANYAN网络完成上述交换任务，则会发生内部竞争现象，产生内部阻塞，连接3未成功，造成连接3的信元丢失，如图2．39所示。

图2．39　BANYAN网络发生内部竞争示意图

现在BANYAN网络前加上BATCHER排序网，将交换网络的出线地址（路由标记）3、7、2、4首先送入排序网络进行排序，注意，经过排序网络的数据就是BATCHER交换网络的出线地址，也是BANYAN交换网络的入线路由标记。这样，排序网络将路由数据按顺序排列在BATCHER排序网络的出线上，图中路由标记3、7、2、4经BATCHER网排序后，出线0、1、2、3上分别是2（010）、3（011）、4（100）、7（111），BATCHER排序网络的出线再按顺序单调进入BANYAN网络，如图2．40所示。B－B网满足了BANYAN网络无阻塞条件，成功消除了BANYAN网络的内部竞争，4个输入线上的信元均成功送到出线上。

B－B网络成功地消除了内部阻塞，但它不能消除出线阻塞，消除出线阻塞常采用输入或输出缓冲排队方法，这种方法对消除其他网络的出线阻塞也是很有效的。

4．多通路BANYAN网络

为了减少或消除BANYAN网络的内部竞争，除了采取上面介绍的B－B网络以外，多通路BANYAN网络也是一种较好的方法。下面简要介绍几种常见的多通路BANYAN网络。

（1）多平面BANYAN网络

多平面BANYAN网络是将若干个相同的BANYAN网络并接在一起，形成多平面的网络结构，如图2．41所示。多平面BANYAN的每个输入端的信息可以按负荷均分原则分配到各个平面，也可以随机地选择某个平面，还可以广播到所有的平面。平面数越多，内部冲突的机会越少。在一定的入线数（或出线数）N值下，平面数增加到一定值时可以得到无阻塞网络。

图2．40　B－B网络

（2）增长型BANYAN网络

在常规BANYAN网络前面加上分配级交换单元，就构成了增长型BANYAN交换网络，它使得信息要交换到目的端口有了更多的通路选择，使单通路网络成为多通路网络，减少了内部阻塞情况的发生。由BANYAN网络的结构可知，每增加一级分配级，每个输入端口与每个输出端口之间的通路数就增加了一倍。图2．42所示是增长型BANYAN交换网络，它靠增加级数来减少内部阻塞的发生，从而提升了交换网络的性能。它的缺点是信息到达每一级增长的交换单元都要进行选路，以决定通过哪条通路到达输出端口，所以，选路较复杂；另外增长的级数要足够大，才能使整个交换网络达到满意的消除阻塞的效果。

图2．41　多平面BANYAN网络（平面数为r）

图2．42　增长型BANYAN多通路交换网络

（3）扩展型BANYAN网络

BANYAN网络中的2×2交换单元的两条出线各自对应一个输出地址，即BANYAN网络的每个输出地址只对应一条输出链路。扩展型BANYAN网络各交换单元的输出地址对应的链路数扩展到d条，信息可以任意选择d条链路中的一条，如图2．43所示。

在扩展型BANYAN网络中，把2×2的交换单元变成了2d×2d的交换单元（第一级为2×2d），但每个交换单元的输出地址仍然是2个。该网络在任何时刻，最多可有d个信息单元被传送到交换单元的同一个输出端。d称为扩展度，增大d可以减少信元丢失。

（4）膨胀型BANYAN网络

如果使扩展型BANYAN网络中的d在各级可以变化，构成的网络称为膨胀型BANYAN网络。图2．44所示为一个8×8的膨胀型BANYAN网络，它的第一级交换单元的d＝2，第二级交换单元的d＝3，第三级交换单元的d＝4。

以上多通路BANYAN网络是以增加复杂程度和硬件实现的难度为代价换来网络内部竞争的减少或消除的。

图2．43　d＝2扩展型BANYAN交换网络

图2．44　8×8的膨胀型BANYAN网络