第2章 交换单元与交换网络(2.3.4)
《第2章 交换单元与交换网络(2.3.4)》由会员分享，可在线阅读，更多相关《第2章 交换单元与交换网络(2.3.4)（33页珍藏版）》请在文档大全上搜索。
1、1n2.3.4. BANYAN网络网络 BANYANBANYAN网络是网络是种种空分交换网络空分交换网络，是由，是由若干个若干个2 22 2交换交换单元单元组成的组成的多级交换网络多级交换网络，它最早使用干并行计算机领域，它最早使用干并行计算机领域，目前目前巳在巳在ATMATM交换机交换机中得到广泛应用。中得到广泛应用。 它它适用于适用于统计复用信号的交换统计复用信号的交换，即，即根据信号中携带的出线根据信号中携带的出线地址信息，在交换网络中建立通道，是进行信元交换的有效地址信息，在交换网络中建立通道，是进行信元交换的有效方法之一方法之一。2孟加拉榕树孟加拉榕树（banyan） 341) 结构
2、结构 22交换单元是具有两条入线和两条出线的电子开关交换单元是具有两条入线和两条出线的电子开关元件，如图所示。元件，如图所示。5 两种两种状态状态：平行连接平行连接和和交叉连接交叉连接， 分别完成不同编号的入线与出线间的连接，达到两条分别完成不同编号的入线与出线间的连接，达到两条入线中的任意入线和两条出线中的任意出线可进行交换的目入线中的任意入线和两条出线中的任意出线可进行交换的目的。的。 一个一个特点特点: 就是它的就是它的每一条入线到每一条出线都有一条路径，并每一条入线到每一条出线都有一条路径，并且只有一条路径且只有一条路径。6 如果我们使用如果我们使用12个个22交换单元就可以构成交换单
3、元就可以构成个个88的三级交换网络，其第的三级交换网络，其第1级和第级和第2级之间的连接为级之间的连接为子洗牌连接子洗牌连接，第第2级和第级和第3级之间的连接为级之间的连接为均匀洗牌连接均匀洗牌连接。如图所示。如图所示。7图11 88三级BANYAN网络8 利用利用递归的方法递归的方法，可用，可用较小的较小的BANYAN网络构成较大网络构成较大的的BANYAN网络网络。其构成方法如下：。其构成方法如下： 假设假设已有已有NN的的BANYAN网络网络，需构成，需构成2N2N的的BANYAN网络。网络。 则可则可使用使用2组组NN，再加上，再加上一组一组N个个22交换单元交换单元构构成。第一组和第
4、二组成。第一组和第二组NN的的2N条出线分别与条出线分别与N个个22的入的入线线用洗牌连接方式用洗牌连接方式相连。相连。9图12 用88三级BANYAN网络构造1616四级BANYAN10 对于对于NN的的BANYAN网络，其网络，其级数约为级数约为Mlog2N，每，每一级需要一级需要N/2个个22交换单元交换单元，共需要，共需要(N2) log2N个个22变变换单元。换单元。 用用22变换单元构成变换单元构成BANYAN网络的网络的具体形式可以具体形式可以有多种有多种，如图所示的几种交换网络均为，如图所示的几种交换网络均为88BANYAN类网类网络。络。 11图13 88三级BANYAN类网
5、络12n2) 工作原理工作原理 因为因为BANYAN网络的构成非常规则，由其结构可以网络的构成非常规则，由其结构可以引出引出些重要的特点。些重要的特点。 (1)唯一路径唯一路径 在在BANYAN网络中，我们已经知道它的网络中，我们已经知道它的每条入线与每条入线与每条出线之间都有一条路径并且只有这一条路径每条出线之间都有一条路径并且只有这一条路径。这就是。这就是BANYAN网络的唯一路径特点。网络的唯一路径特点。 可以利用类似于数学归纳法的方法给予证明。可以利用类似于数学归纳法的方法给予证明。13 假设它对假设它对NN的的BANYAN网络也成立网络也成立那么那么: 对于对于2N2N的的BANYA
6、N网络网络来说，因为来说，因为2N2N的的BANYAN网络是用前述的方法来构成的显然从网络是用前述的方法来构成的显然从NN BAHYAN网络到最后一级网络到最后一级22交换单元中共有交换单元中共有2N条路条路径要到其中某一条出线必须经过其中唯一的径要到其中某一条出线必须经过其中唯一的条路径。条路径。14BANYAN网络特性0101234567234567Error!Error!Error!惟一路径惟一路径0 0号入线到号入线到3 3号出线的惟一路径特性演示号出线的惟一路径特性演示15 (2) 自选路由自选路由 由由BANYAN网络的构成方法可知，一个网络的构成方法可知，一个BANYAN网络的网
7、络的入线数和出线数相等入线数和出线数相等。并且若。并且若假设其为假设其为N。则必。则必有有N=2M，M为级数。再设为级数。再设N条入线和条入线和N条出线分别顺序条出线分别顺序编号为十进制数编号为十进制数0、1、2、N-1，则必定，则必定可用可用M位二位二进制数字进制数字来区别来区别N入线和入线和N条出线条出线。16 由由BANYAN网络的唯一路径特点可知，从网络的唯一路径特点可知，从BANYAN网络的网络的任意一条入线到全部任意一条入线到全部N条出线共有条出线共有N个个连接连接，这，这N个连接个连接可以用出线的可以用出线的N个不同的编号表示个不同的编号表示，即即: 其中的其中的每一个连接都可以
8、用每一个连接都可以用M位二进制数字表示位二进制数字表示。17 一个一个NN的的BANYAN网络共有网络共有M级，每一级有级，每一级有 N2个个22交换单元。可以交换单元。可以把把每个每个交换单元的两条交换单元的两条入线和入线和两条出线两条出线都依照在图上的都依照在图上的上下位置上下位置分别编号为分别编号为0和和1。 考虑一个考虑一个由入线由入线i到出线到出线j的连接的连接，这个连接是由，这个连接是由M个个属于不同级的交换单元顺序连接组成的。属于不同级的交换单元顺序连接组成的。 从从第第1级开始顺序排列级开始顺序排列该连接经过的各个交换单元的该连接经过的各个交换单元的出线编号出线编号(0或或1)
9、，则，则恰好恰好组成一个组成一个M位二进制数字，这位二进制数字，这M位值二进制数字位值二进制数字正是出线正是出线的编号的编号。18 我们从任意一条入线开始，逐个读出各级交换单元相我们从任意一条入线开始，逐个读出各级交换单元相应出线的数字或应出线的数字或1，那么，这些数字组合起来就是出线，那么，这些数字组合起来就是出线的号码。可以说明，这个数字的的号码。可以说明，这个数字的种不同的取值正好表示种不同的取值正好表示了从同一条入线出发的了从同一条入线出发的N个不同的连接或路径个不同的连接或路径。2. 自选路由自选路由： 从任意一条入线开始，逐个读出各级交换单元相应出从任意一条入线开始，逐个读出各级交
