BANYAN网络特性.docx

Harbin Institute of TechnologyBANYAN网络的特性哈尔滨工业大学通信工程系2012引言： BANYAN网络是一种空分交换网络，最早使用于并行计算机领域，但目前已在ATM交换机中得到了广泛的应用BANYAN网络具有唯一路径特性和自选路由功能唯一路径特性指任何一条入线和任何一条出线之间存在并仅存在一条通路；自选路由功能指不论信元从哪条入线进入网络，它总能到达指定出线由于到达指定的输出端仅有唯一一条通路，因此路由选择十分简单，即可由输出地址确定输入和输出之间的唯一路由缺点是会发生内部阻塞，这是由于一条内部链路可以被多个不同的输入端同时使用造成的BANYAN网络的优点是结构简单，模块化、可扩展性好，信元交换时延小它适用于统计复用信号的交换，即根据信号中携带的出线地址信息，在交换网络中建立通道，是进行信元交换的有效方法之一BANYAN网络的结构： BANYAN网络其基本结构是由若干个交换单元组成的多级交换网络 交换单元是具有两条入线和两条出线的电子开关元件，具体结构如下图所示： 这种电子开关具有两种状态：平行连接和交叉连接，分别完成不同编号的入线和出线间的连接，达到两条入线中的任意入线和两条出线中的任意出线可进行交换的目的。

由4个交换单元可以构成一个的二级交换网络其结构如下图所示： 其中，第1级和第2级之间的连接为均匀洗牌连接图中画出了由入线0到出线0和由入线3到出线1的路径 同样，如果我们使用12个交换单元就可以构成一个的三级交换网络其第1级和第2级之间的连接为子洗牌连接，第2级和第3级之间的连接为均匀洗牌连接它同样具备上述特点 我们可以把前面的8个交换单元看成是两个的二级交换网络，后面再加上一级4个交换单元，构成的三级交换网络 这种将多个交换单元分成若干级，并按照一定的级间连接方式构成的多级交换网络，就称为BANYAN网络 由上述的和BANYAN网络实例，我们发现BANYAN网络的结构是很规则的，利用递归的方法，可用较小的BANYAN网络构成较大的BANYAN网络其构成方法如下： 假设已有的BANYAN网络，需构成的BANYAN网络则可使用2组，再加上一组N个交换单元构成第一组的N条出线分别与N个的某一入线相连，第二组的N条出线分别与N个的另一入线相连例如，用BANYAN网络构成BANYAN网络时，可用2组，加上8个交换单元构成，共需32个交换单元 对于的BANYAN网络，其级数约为，每一级需要N/2个交换单元，共需个交换单元。

BANYAN网络的特性： ⑴唯一路径 由BANYAN网络的结构我们可以看出，它的每条入线与每条出线之间都有一条路径并且只有这一条路径这就是BANYAN网络的唯一路径特点 首先的BANYAN网络是具有唯一路径的我们假设它对的BANYAN网络也成立，那么，对于的BANYAN网络来说，因为的BANYAN网络是用前述方法来构建的，显然从BANYAN网络到最后一级交换单元中共有条路径，并且要到其中某一条出线必须经过其中唯一的一条路径可见这样构成的的BANYAN网络仍然是在每条入线和每条出线间都存在一条路径并且只有唯一的一条路径 ⑵自选路由 由BANYAN网络的构成方法可知，一个BANYAN网络的入线数和出线数相等并且若假设其为N，则必有,M为级数再设N条出线分别顺序编号为十进制数0、1、2、…、N-1，则必定可用M位二进制数字来区别N条入线和N条出线 由BANYAN网络的唯一路径特点可知，从BANYAN网络的任意一条入线到全部N条出线共有N个连接，这N个连接可以用出线的N个不同的编号表示，即其中的每一个连接都可以用M位二进制数字表示 一个的BANYAN网络共有M级，每一级有N/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. 因此很自然的使我们想到，如果我们把出线的编号（地址）以二进制数字的形式送到交换网络，那么，每一级上的交换单元就只需要根据这个地址中的某一位就可以判别应该将其送到那一条出线上比如说，在第一级上的交换单元中只读地址的第一位，在第二级上的交换单元中只读地址的第二位，……，当所有地址都被读完，这个信元就已经被送到相应的出线上了显然，如果能够利用到这一点，则交换网络的控制部分就可以做得十分简单。

这显然也是一个很大的优点这就叫做自选路由，即给定出线地址，不用外加控制命令，就可选择到出线对于统计复用信号，每个信元均携带有控制信息，包括路由信息，即出线地址，使用BANYAN网络可以很方便的进行交换⑶编号数字置换BANYAN网络的入线和出线可以都编上号码，并用一组数字的排列（置换）来表示它的一种连接方式例如，对于BANYAN网络，给定连接函数的排列表示为这表示，四条入线和四条出线分别编号为0、1、2、3，入线3连接到出线1，入线2连接到出线2，入线1连接到出线0，入线0连接到出线3.如下图所示虽然任何一个交换单元及交换网络都可以用置换来表示其连接方式，但对BANYAN网络使用置换表示有特别意义这是因为，BANYAN网络是按级由交换单元组成的每一个交换单元都完成两个数字的一次置换，每一级都完成N个数字的一次置换换句话说，在BANYAN网络中，表示整个交换网络连接方式的置换是由各级及级间逐次置换构成，例如，上图的连接方式的实现是有以下各级间置换的叠加：第一级交换单元完成的连接置换：第一级交换单元和第二级交换单元之间完成的连接置换：第二级交换单元完成的连接置换：显然，BANYAN网络具有简单、模块化、可扩展性好及信元交换时延小等优点，但它也存在着明显的问题，即内部阻塞。

BANYAN网络的内部阻塞 当BANYAN网络中某一个交换单元的两条入线同时要向同一条出线发送信元时，就会发生阻塞根据发生阻塞的交换单元在交换网络中的位置，会出现下面两种情况： ⑴发生阻塞的交换单元在交换网络的最后一级，即交换网络的两条或多条入线同时试图占用同一条出线，这称为出线阻塞由于出线阻塞不是由于交换网络本身的缺陷造成的，采用诸如输入或输出缓冲排队方法可以很好地解决 ⑵发生阻塞的交换单元在交换网络的各级（除最后一级以外），即交换网络的两条或多条入线试图占用同一条出线，发生阻塞如果不采取适当措施，就会造成信元丢失 应当注意的是，BANYAN网络的内部阻塞发生在交换单元内部，而不是级与级之间的链路上 BANYAN网络不仅有内部阻塞，而且这种内部阻塞是随着阵列级数的增加而增加当级数太多时，内部阻塞就会变得不可容忍因为交换网络太大了，级数就会增加，所以，由于内部阻塞，BANYAN网络不可能做得很大 内部阻塞是BANYAN网络必须解决的一个问题解决办法可有如下考虑： ①内部阻塞是在交换单元的两条入线要向同一个出线发送信元产生的，在最坏的情况下，这个概率是1/2.但是，如果入线上并不总是存在信号，这个概率就会下降。

因此，可以通过适当限制入线上的信息量或加大缓冲存储器来减少内部阻塞 ②可以通过增加多级交换网络的级数来消除内部阻塞，例如，把BANYAN网络的级数由3增加到5，就可以消除内部阻塞事实上，有人已经证明了，若要完全消除的BANYAN网络（其级数为）的内部阻塞，至少需要级 ③可以增加BANYAN网络的平面数，构成多通道交换网络 ④使用排序-BANYAN网络，这是近年来解决BANYAN网络的内部阻塞问题的一个重要研究成果 ⑤上述后三种方法能很好地消除内部阻塞，但会增加网络单元数，这样做不仅会增加网络的复杂性，而且还会增加信元通过网络的时延，尤其不适宜传送对信元敏感的信息，而AIM技术的本意就是要将多种信息综合到一个网络进行传输交换如果将BANYAN网络改造成单侧折叠式的，则可以避免上述问题在单侧折叠式网络中，每一对入线和出线之间都有多条可供利用的路径这样就能大大减少信元碰撞的机会，从而使内部阻塞率降低证明BANYAN网络自选路由的特性证明：①对于的BANYAN网络，当N=1时，其级数为对于任意一条入线，比如入线‘0’，只需在数据位后添加一位二进制数就可以表示其唯一出线的编号如：‘0’表示出线‘0’，‘1’表示出线‘1’。

②设对于的BANYAN网络，需要位的2进制数来表示其唯一出线路径的编号 ③对于的BANYAN网络，其级数为 由BANYAN网络的构造方法可知，的BANYAN网络是由两个的BANYAN网络再加上一级个交换单元构成 从的BANYAN网络到最后一级交换单元共有条路径，并且要到其中一条出线必须经过其中的唯一的一条路径并且这样构成的的BANYAN网络仍然是在每条入线和每条出线间都存在一条路径并且只有唯一的一条路径 由二进制地址的性质可知，对于位的二进制地址，若增加一位二进制数，其地址数增加个对于级数为的的BANYAN网络来说，增加一位二进制即位二进制正好可以表示构成的BANYAN网络的两个的BANYAN网络的条路径由BANYAN网络的唯一路径可知，的BANYAN网络可由位二进制地址唯一地表示其路径 综上所述，BANYAN网络的自选路由特性得证。