《排序banyan网络无阻塞性证明.doc》由会员分享，可在线阅读，更多相关《排序banyan网络无阻塞性证明.doc（6页珍藏版）》请在金锄头文库上搜索。
1、网络交换课程报告 一、Banyan网络及其性质 Banyan网络是ATM交换网络最具代表性的网络之一。Banyan网络采用22交换单元，它有两种连接状态：平行连接和交叉连接。Banyan网络的构造是非常规则的：4个22的交换单元连接起来，可以得到一个4个人端、4个出端的二级网络；12个这样的交换单元连接起来可以得到一个8个人端、8个出端的三级网络i 32个交换单元连接起来可以构成一个l6个人端、l6个出靖的四级网络。图2给出了一个四级Banyan网络，可 看出它是由二级、三级Banyan网络递归构成的。仿照上述方法可以推出，假如要用两个N条入线、N条出线的交换网络构成一个2N条人线、2N条出线
2、的交换网络，只要再加上N个22交换单元，把第一个NN交换网络的N条入线分别与新加的N个22交换单元的某一出线相连，把另一个NN交换网络上的N条人线与增加的N个22交换单元上的另一条出线相连即可。Banyan网络构造规则，便于扩充。它之所以受到重视还因为它具有自选路由特性这就是说它不需要路由变换表，而可以根据信元携带的地址信息， 自行找到要转接的出线端口。由Banyan网络的构造规则可知一个NN的Banyan网络共有M级，并且N=2M 。如果把每个交换单元每侧的两个端口依次编号为0和1，则从人端i到j出端 的连接通路，所经过的各级交换单元的出靖号码是一个位的二进制数字，可以证明这个二进制数字正好
3、是出线的地址 。利用这个特性，如果把出线的编号(即出线地址)以二进制形式送到交换单元，那么每一级上的22交换单元只需要根据这个地址中的某一位就可以判别应将其送往哪一个出端上， 当所有地址被读完，信元就已经被送到相应的出线上了，这个性质就叫做自选路由特性。利用自选路由特性，交换单元的控制部分不需要安排复杂的路由变换表，可以做得十分简单。Banyan网络具有如下性质：1. 唯一路径特性，Banyan网络在任一输入端和任一输出端之间有且仅有一条通路。 2.自选路由特性，自选路由，即是给定出线地址，不用外加控制命令，就可选到出线。可以使用对应于出端号的二进制码的选路标签来自动选路。在每个到来的信元进入
4、MIN（多级互连网络）之前加上路由标签(routing tag)，MIN中各级SE（交换单元）就按照路由标签中相应的路由信息来确定其出线，直到最后一级SE自行选路后就可到达所需的出端。即是给定出线地址，不用外加控制命令，就可选到出线。可以使用对应于出端号的二进制码的选路标签来自动选路。 3.有阻塞性，在没有出线冲突时，纵横开关阵列是没有内部阻塞的。但上面讨论的Banyan网络则是有内部阻塞的。Banyan网络不仅有内部阻塞，而且这种内部阻塞随着阵列级数的增加而增加。内部阻塞是在22交叉连接单元的两个入线要向同一个出线上发送信元时产生的。从Banyan网络的自选路由特性可以知道，任何一条人线到任
5、何一条出线之间只有一条路由，这是因为通路所经过的各级交换单元都是按照目的地址来选择出端号码的，它只有一种选择。因此当两对人线、出线之间的通路发生碰撞时，就会产生内部阻塞。由于Banyan网络在任一对人线、出线之间只有一条路由，因此它的内部阻塞是非常高的，极端时候可以达到50。显然要使Banyan网络应用于实际当中，必须解决它的内部阻塞问题。可以通过适当限制入线上的信息来减少内部阻塞，也可以通过加大缓冲存储器容量来减少内部阻塞。下面是消除内部阻塞的两种思路。（1） 增加多级开关阵列的级数。把一个级的Banyan网络对折叠加，使其级数增加到，得到的网络是无阻塞的，称为Benes网络。（2） 排序B
6、anyan网络，即通过在Banyan网络前面添加一个排序网络使其成为一个无阻塞网络。二、一种排序-Banyan网络成为无阻塞网络当Banyan网络入线按出线地址排序，在经洗牌连接入Banyan网络，Banyan网络就变成了无阻塞网络。意思是当输入线的顺序是单调的（单调增或单调减），再经过洗牌连接的方式接入Banyan网络，则Banyan网络变为无阻塞的网络。要证明这个结论我们可以先看看88网络是如何成为无阻塞网络的。由上面的叙述，我们可以得到如下所示的88网络： 000 0 0 0 000 001 1 1 1 001 010 0 0 0 010 011 1 1 1 011 100 0 0 0
7、100 101 1 1 1 101 110 0 0 0 110 111 1 1 1 111 图一. 无阻塞的Banyan网络在88网络中的Banyan网络中，输入线顺序经洗牌连接进入Banyan网络后，Banyan网络内部确实不再有内部阻塞的问题。由上述的88无阻塞Banyan网络，可以得到次结构的简化交换方式： 000 000 000 000 001 100 010 001 010 001 001 010 011 101 011 011 100 010 100 100 101 110 110 101 110 011 101 110 111 111 111 111 图二.无阻塞Banyan网络
8、的简化图在上面的简化图中，可以很清楚地看出每个信元在网络中的行进路线。除第一列外，其余各列的相邻两个数字是同时经过一个交换单元的两个信元的地址。可以看到在每个交换单元的地址都只有一位数字不同，其余各位都相同。在地址值不同的那一位也有规律，即在第级交换单元，进入交换单元的两个地址值的第位不同。在每个交换单元的两个地址中，总是地址值小的信元从交换单元的上输入线进入，地址值大的信元从下输入线进入，输出时还是地址值小的在上面，地址值大的在下面，这样就保证了交换过程中不存在阻塞。在Banyan网络的输入端，将按顺序单调排列的入线经洗牌连接进网络，使第一级的每一个交换单元内两个信元的地址值相差23-1，保
9、证了第一级交换顺利进行。还可以看到，从第一级到第二级，经过网络后，分为两组，一组的地址首位数字为0，在上半部分，另一组的地址首位为1，在下半部分； 经过第二级交换单元后，原来的每一组又各自分为两组，一组地址第二位为0，另一组地址二位为1。就这样按规律1组分为2组，2组分为4组，在每级中组地址可以这样算出，组地址=信元地址的前（级数-1）位的数值。若为的Banyan网络，只要其满足如88网络那样的规律，则其也必为无阻塞网络。00000 0000000001 1000000010 0000100011 10001 00010 1001010000 0001110001 10011 10010 10
10、011 11111 11111图三.顺序输入经洗牌连接进Banyan网络 下面考察网络的交换，该交换网络共有级，每级有个交换单元，其交换过程的简化图如图三所示。由图知，经洗牌连接后，个输入共分成组进入交换单元，每组地址值总是相差，也即是每组地址只是第一位不同，其他位都相同。且地址小的从上输入线进入，地址大的从下输入线进入，输出保持上下关系，交换过程无阻塞。同样可以画出一、二级，二、三级之间交换关系：00000 00000 0000010000 01000 0010000001 00001 0000110001 01001 00101 00111 00111 0101110111 01111 0
11、1111 01000 10000 10000 11000 11000 10100 01110 10110 1101011110 11110 1111001111 10111 1101111111 11111 11111图四.Banyan网络前三级交换关系上面是Banyan网络的交换简略图，从图中可以看出其具有与88网络相同的性质，即每经一级交换，Banyan网络可以分为两个更小的网络，且其具有相同的结构。每个分组的第一级都是与顺序排列输入线经洗牌连接进Banyan网络的第一级是相同的，如此就可以把的Banyan网络分为个88的Banyan网络，我们前面已经验证88的Banyan网络是无阻塞的，则由此可以推得这样的的Banyan网络也是无阻塞的。另外观察网络的前三级交换也可以验证。Banyan网络第一级经过洗牌连接进入输入端的两个信元地址的第一位分别为0和1，由Banyan网络的自选路由特性知道经过交换单元无阻塞，第二级，三级也是如此，以此类推，网络
