Banyan网络的结构及其特性

《Banyan网络的结构及其特性》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、Banyan网络是ATM交换网络最具代表性的网络单纯的Banyan网络内部阻塞率非常，无法直接用于ATM交换。为了解决内部阻塞问题，有人提岀对折叠加和排序两种改进措施，但这两种措施都是以增加闷珞的级数为代价的，会增加信元通过网络的时延。而如果将网络改造成单侧折叠式的，则可以避免上述问题。这样不仅能够有效地降低阻塞率，而且还可以降低一部分信元的时延。ATM技术由于能携带多种信息和媒体而日益受到人们的重视。和电话网一样，交换机构是AIM技术的一个重要组成部分，它也可以分为时分和空分两种。时分交换由于所有的信元都会集到一条总线上，数据吞吐量必然受到总线速率的限制。要

2、进一步扩大交换容量，唯有将空分交换和时分交换结合起來。小容量的空分交换网络可以由一个M条人线、N条出线的矩阵形交换单元构成。当某人线上的信息要转送到某出线上吋，就把这个人线和出线之间的交叉开关接通；不需要连接吋，交叉开关就断开。这种单级网络.任意两个人线和出线可随吋接通，不存在内部阻塞现彖。但是在这种交换矩阵屮，交叉点的数目随端口数目的增加以平方速率增加，很快就会达到不可容忍的地步。因此通常当端口数目较多时，一般不采用单个交换单元，而是采用多级互联网络来完成交换功能。在相同的人线和出线的情况下，多级互联网络可以有效地减少交叉点的数目。在多级互联网络中，Bany

3、an网络是比较典型的网络之一，它控制简单，构造规则，因此一提出来，就受到人们的重视。2Banyan网络的结构及其特性Banyan网络采用2><2交换单元，它有两种连接状态：平行连接和交叉连接，如图1所示。平行连接时。入端0和出端0'连接，人端1和出端1'连接；交义连接时，入端0和出端「连接，人靖1和出端0’连接。Banyan网络的构造是非常规则的：4个2x2的交换单元连接起來，可以得到一个4个人端、4个出端的二级网络；12个这样的交换单元连接起来可以得到一个8个人端、8个出端的三级网络i32个交换单元连接起来可以构成一个16个人端、16个出靖的四级网络。图2给

4、出了一个四级Banyan网络，可看出它是由二级、三级Banyan网络递归构成的。1）平行连接2）交夏连接图-1-Banyan网络的两种连接状态仿造上述方法可以推出，假如要用两个N条入线、N条出线的交换网络构成一个2N条人线、2N条出线的交换网络，只要再加上N个2x2交换单元，把第一个NxN交换网络的N条入线分别与新加的N个2x2交换单元的某一出线相连，把另一个NxN交换网络上的N条人线与增加的N个2x2交换单元上的另一条出线相连即可。Banyan网络构造规则，便于扩充。它Z所以受到重视还因为它具冇自选路由特性.这就是说它不需耍路由变换表，而可以根据信元携带的地

5、址信息，门行找到要转接的出线端口。由Banyan网络的构造规则可知.一个NxN的Banyan网络共冇M级，并月.N=2M。如杲把每个交换单元每侧的两个端口依次编号为0和1,则从人端i到j出端的连接通路，所经过的各级交换单元的出靖号码是-•个位的二进制数字，可以证明这个二进制数字正好是出线，的地址。利用这个特性，如果把出线的编号（即出线地址）以二进制形式送到交换单元，那么每一级上的2x2交换单元只需耍根据这个地址中的某一位就可以判别应将其送往哪一个出端上，当所有地址被读完，信元就已经被送到和应的出线上了，这个性质就叫做白选路宙特性。利用门选路由特性，交换单元的控

6、制部分不需要安排复杂的路由变换表，可以做得十分简单。01234567012(010)3(011)4(100)5(101)67图-2-8^8的3级banyan网络1•树型结构特性：从banyan的任一输入端口引出的一组通路形成了2分支树，级数越多，分支越多，级数k=log2N,”=总入线数/出线数,即2k=N。2•单通路特性:banyan的任一入端到任一出端Z间，具有1条且仅有一条通路。3•自选路由特性：门选路由，即是给定出线地址，不用外加控制命令，就可选到出线。可以使用对应于出端号的二进制码的选路标签来自动选路。在每个到來的信元进入MIN（多级互连网络）之前加

7、上路由标签（routingtag）,MIN中各级SE（交换单元）就按照路由标签中相应的路由信息来确定其出线，直到最后一级SE自行选路后就可到达所需的出端。即是给定出线地址，不用外加控制命令，就可选到出线。可以使用对应丁出端号的二进制码的选路标签來口动选路。4•可扩展性：Banyan的构成具有一定的规律，可以采用有规则的扩展方法将较小容量的Banyan扩展成较大规模。已有NxN的Banyan网络，需构成2Nx2N的Banyan网络，则可用2组NxN,再加上一组N个2X2交换单元构成。第一组的NxN的N条出线分别与N个2x2交换单元的某一入线和连，第二组的NXN的

8、N条出线分别与N个2x2交换单元的另一