Banyan网络的结构及其特性

1引言Banyan网络是ATM交换网络最具代表性的网络之一。单纯的Banyan网络内部阻塞率非常，无法直接用于ATM交换。为了解决内部阻塞问题，有人提出对折叠加和排序两种改良措施，但这两种措施都是以增加闷珞的级数为代价的，会增加信元通过网络的时延。而如果将网络改造成单侧折叠式的，那么可以防止上述问题。这样不仅能够有效地降低阻塞率，而且还可以降低一局部信元的时延。ATM技术由于能携带多种信息和媒体而日益受到人们的重视。和网一样，交换机构是AIM技术的一个重要组成局部，它也可以分为时分和空分两种。时分交换由于所有的信元都会集到一条总线上，数据吞吐量必然受到总线速率的限制。要进一步扩大交换容量，唯有将空分交换和时分交换结合起来。小容量的空分交换网络可以由一个M条人线、N条出线的矩阵形交换单元构成。当某人线上的信息要转送到某出线上时，就把这个人线和出线之间的交叉开关接通；不需要连接时，交叉开关就断开。这种单级网络．任意两个人线和出线可随时接通，不存在内部阻塞现象。但是在这种交换矩阵中，交叉点的数目随端口数目的增加以平方速率增加，很快就会到达不可容忍的地步。因此通常当端口数目较多时，一般不采用单个交换单元，而是采用多级互联网络来完成交换功能。在相同的人线和出线的情况下，多级互联网络可以有效地减少交叉点的数目。在多级互联网络中，Banyan网络是比拟典型的网络之一，它控制简单，构造规那么，因此一提出来，就受到人们的重视。2Banyan网络的结构及其特性Banyan网络采用2×2交换单元，它有两种连接状态：平行连接和交叉连接，如图1所示。平行连接时。入端0和出端0’连接，人端l和出端1’连接；交叉连接时，入端0和出端1’连接，人靖1和出端0’连接。Banyan网络的构造是非常规那么的：4个2×2的交换单元连接起来，可以得到一个4个人端、4个出端的二级网络；12个这样的交换单元连接起来可以得到一个8个人端、8个出端的三级网络i32个交换单元连接起来可以构成一个l6个人端、l6个出靖的四级网络。图2给出了一个四级Banyan网络，可看出它是由二级、三级Banyan网络递归构成的。1〕平行连接2〕交夏连接图-1-Banyan网络的两种连接状态仿造上述方法可以推出，假设要用两个N条入线、N条出线的交换网络构成一个2N条人线、2N条出线的交换网络，只要再加上N个2×2交换单元，把第一个N×N交换网络的N条入线分别与新加的N个2×2交换单元的某一出线相连，把另一个N×N交换网络上的N条人线与增加的N个2×2交换单元上的另一条出线相连即可。Banyan网络构造规那么，便于扩充。它之所以受到重视还因为它具有自选路由特性．这就是说它不需要路由变换表，而可以根据信元携带的地址信息，自行找到要转接的出线端口。由Banyan网络的构造规那么可知．一个N×N的Banyan网络共有M级，并且N=2M。如果把每个交换单元每侧的两个端口依次编号为0和1，那么从人端i到j出端的连接通路，所经过的各级交换单元的出靖号码是一个位的二进制数字，可以证明这个二进制数字正好是出线，的地址。利用这个特性，如果把出线的编号(即出线地址)以二进制形式送到交换单元，那么每一级上的2×2交换单元只需要根据这个地址中的某一位就可以判别应将其送往哪一个出端上，当所有地址被读完，信元就已经被送到相应的出线上了，这个性质就叫做自选路由特性。利用自选路由特性，交换单元的控制局部不需要安排复杂的路由变换表，可以做得十分简单。图-2-8×8的3级banyan网络1.树型结构特性：从banyan的任一输入端口引出的一组通路形成了2分支树，级数越多，分支越多，级数k=㏒2N，N=总入线数/出线数，即2k=N。2.单通路特性：banyan的任一入端到任一出端之间，具有1条且仅有一条通路。3.自选路由特性：自选路由，即是给定出线地址，不用外加控制命令，就可选到出线。可以使用对应于出端号的二进制码的选路标签来自动选路。在每个到来的信元进入MIN〔多级互连网络〕之前加上路由标签(routingtag)，MIN中各级SE〔交换单元〕就按照路由标签中相应的路由信息来确定其出线，直到最后一级SE自行选路后就可到达所需的出端。即是给定出线地址，不用外加控制命令，就可选到出线。可以使用对应于出端号的二进制码的选路标签来自动选路。4.可扩展性：Banyan的构成具有一定的规律，可以采用有规那么的扩展方法将较小容量的Banyan扩展成较大规模。已有N×N的Banyan网络，需构成2N×2N的Banyan网络，那么可用2组N×N，再加上一组N个2X2交换单元构成。第一组的N×N的N条出线分别与N个2×2交换单元的某一入线相连，第二组的NXN的N条出线分别与N个2×2交换单元的另一入线相连。5.内部阻塞性：在没有出线冲突时，纵横开关阵列是没有内部阻塞的。但上面讨论的Banyan网络那么是有内部阻塞的。Banyan网络不仅有内部阻塞，而且这种内部阻塞随着阵列级数的增加而增加。内部阻塞是在2×2交叉连接单元的两个入线要向同一个出线上发送信元时产生的。从Banyan网络的自选路由特性可以知道，任何一条人线到任何一条出线之间只有一条路由，这是因为通路所经过的各级交换单元都是按照目的地址来选择出端号码的，它只有一种选择。因此当两对人线、出线之间的通路发生碰撞时，就会产生内部阻塞，在图2上标出了从人端0100到出端0ll0和从人端0l10到出端0100时通路发生碰撞的情况。由于Banyan网络在任一对人线、出线之间只有一条路由，因此它的内部阻塞是非常高的，极端时候可以到达50％。显然要使Banyan网络应用于实际当中，必须解决它的内部阻塞问题。在这方面，典型的方案有两种：一种是把一个级Banyan网络对折叠加，使其级数增加到2M+1，那么总能找到任一条人线到任一条出线的通路；另一种是Banyan网络前面添加一个排序网络，对各人端到出端的连接进行排序，那么彼此所经过的路由不会重叠，因此也就不会发生内部阻塞。Banyan网络的这两种改良方法，从消除内部阻塞方面来说是非常成功的，它们都把内部阻塞降到了0。但是它们都是通过增加网络单元数到达目的的，这样做不仅会增加网络的复杂性，而且会增加信元通过网络的时延．尤其是不适宜传送对信元敏感的信息，而AIM技术的本意就是要将多种信息综合到一个网络进行传输交换。如果将网络改造成单侧折叠式的，那么可以防止上述问题。在单侧折叠式网络中。每一对人线和出线之间都有多条可供利用的路径。这样就能大大减少信元碰撞的时机，从而使内部阻塞率降低。这种网络还有一个优点，即通路不一定需要经过网络的全程，根据人线和出线的相对位置，信元可在不同级的交换单元上反应回来，因此有些信元的时延还会降低。在单侧折叠式Banyan网络中，交换单元的内部链路应该工作在双向模式，也就是要求每条人线和出线应该既能接收，又能发送。这一点并不难实现。在一个普通的4×4的交换单元中，安排其中的一半交换单元在一个方向上作2×2交换，而另一半在相反方向上作2×2交换，即可构成一个2×2的双向交换单元。3单侧折叠式Banyan网络的构造方法及其特点我们知道，目前在网中获得广泛应用的并不是无阻塞网络．而是有阻塞网络。这是因为，在效劳质量允许的情况下，有阻塞网络比无阻塞网络能够节约大量的交叉点数。以一个三级网络为例，在10万条人线，10万条出线情况下，构造无阻塞网络需要的交叉点数大约为4×108个；而在系统话务量为20000erl的情况下，构造内部阻塞率小于l0-100的有阻塞网络那么需要2×108。个交叉点，比前者节约了大约一半的交叉点数。可见，只要内部阻塞率足够低，有阻塞网络比无阻塞网络更经济实用。在ATM交换网络中，采用有阻塞网络同样能够到达降低网络复杂性的目的。下面所说的单侧折叠式网络就是有阻塞的，它是通过在人线和出线之间提供多条路径，来降低信元的碰撞时机。和单纯的Banyan同相比，这种方法，不仅保存了自选路由特性，而且当两个终端建立连接时，根据它们的相对位置不一定需经过网络的全程。利用选种双向交换单元构成的Banyan网连接方法和原来类似，只是所有的输入端口和输出端口均位于网络的左侧。在单侧折叠式网络中，建立一条人线到一条出线的通路，可以不经过网络的全程，根据人线和出线的相对位置，通路可在第l级、第2级或者最后一级反应回来对于图2所示的网络，将每个端口的编号用4位二进制数XYZW表示。通过比拟人线X1Y1Z1W1和出X2Y2Z2W2的地址就可以决定通路从哪级反应。当X1≠X2时，通路在第4级反应由于从第4级的哪一个交换单元都能找到连接到指定输出端口的通路．所以从人线到第4级的通路可自由寻找，即所经过的交换单元可以选择0、l任一条连接到下一级的空闲出线。但因为输出端口是固定的，所以在从反应级向输出端口建立通路时，要根据出线地址指定选择交换单元的出线号。当X1=X2、Y1≠Y2时，通路的反应点在第3级，此时从人线到第3级的通路是自由选择；从第3级到出线的路由是指定选择。当X1=X2=、Y1≠Y2时，通路的反应点在第2级，此时从人线到第2级的通路是自由选择；从第2级到出线的路由是指定选择。当X1=X2、X1=X1、Y1=Y2、Z1≠Z2时，通路的反应点在第l级，此时只要在第l级的交换单元上，根据出线号码，指定选择一次即可。和原来的Banyan网络相比，这种网络也不需要路由变换表。在自由选择时，所经过的交换单元可任意选择一条连接到下一级的空闲出线；在指定选择时，交换单元可以根据出端地址的二进制形式依次选择相应的出线。由于建立通路时，从人线到反应级之间的路由是自由选择的，因此它在输入端口和输出端口之间可能有多条通路，且通路数随着反应级的深入而增加，通路数L与反应级位置K的关系是：L=2K-1，图中示出了从端口10410到端口1010的2条通路。在这种多径网络中，对于给定的输入，可以存在几条不同的路径到达预期的输出端，因此有利于降低信元的碰撞时机，减少内部阻塞率。单侧折叠式还有一个特点，即从人线到出线的连接可不经过网络的全程。对一些联系比拟密切的线对，位置可安排近一些，这样就能有敛地降低信元通过网络的时延。这种单向折叠式网络的扩充比拟方便。当业务流量增大，需要扩充ATM交换机的规模时，原有的连线不需要变动．只需要将最后一级交换单元的出线和新增加的交换单元相连即可。在图2中同时示出了网络由二级到三级、四级扩充方法。如果网络到达了预期最大规模，最后一级交换单元的端口就可以全部和前一级相连，这样该级采用的交换单元端口数量可以只为原来的～半。例如对于图2所示的四级网络，第一、二、三级各需要8个4×4的交换单元，第四级需要8个2×2的交换单元，网络可完成的交换容量为16×16端口。4解决内部阻塞的其它方法由于Banyan网络有内部阻塞的性质，解决内部阻塞是能否能让此网络应用于实际的关键，可以有以下方法：1.内部阻塞是在2X2交换单元的两条入线要向同一个出线上发送信元时产生的，最坏情况下概率为50%，假设减少入线上的信息量，就可减少阻塞的概率，故可通过适当限制入线上的信息量或加大缓冲存储器来减少内部阻塞。2.可以通过增加多级交换网络的级数来消除内部阻塞。已有证明，假设要完全消除NXN的banyan网络的内部阻塞，至少需要2log2N