第2章 交换单元与交换网络(2.3.4)

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. 自选路由自选路由： 从任意一条入线开始，逐个读出各级交换单元相应出从任意一条入线开始，逐个读出各级交

10、换单元相应出线的数字线的数字0和和1，那么，这些，那么，这些数字组合起来就是出线的号码数字组合起来就是出线的号码。19i i号入线到号入线到3 3号出线的自选路由特性演示号出线的自选路由特性演示010123456723456701010101010101010101010120 (3)编号数字置换编号数字置换 像任何交换单元及交换网络一样像任何交换单元及交换网络一样BANYAN网络的入线网络的入线和出线可以都编上号码和出线可以都编上号码，并用一组数字的排列或称置换来表，并用一组数字的排列或称置换来表示它的一种连接方式。示它的一种连接方式。 21 虽然任何一个交换单元及交换网络都可以用置换来表虽

11、然任何一个交换单元及交换网络都可以用置换来表示其连接方式，但对示其连接方式，但对BANYAN网络使用置换表示有特别的网络使用置换表示有特别的意义。这是因为，意义。这是因为，BANYAN网络是按级由网络是按级由22交换单元组交换单元组成的，每一个成的，每一个22交换单元都完成两个数字的一次置换，交换单元都完成两个数字的一次置换，每每一级都完成一级都完成N个数字的一次置换个数字的一次置换。换句话说，在。换句话说，在BANYAN网网络中，表示整个交换网络连接方式的置换是由各级及级间逐络中，表示整个交换网络连接方式的置换是由各级及级间逐次置换构成。次置换构成。 22n3)BANYAN网络的内部阻塞网络

12、的内部阻塞nBANYAN网络不是网络不是CLOS网络，它不符合网络，它不符合CLOS网络的无网络的无阻塞条件，因此阻塞条件，因此BANYAN网络存在内部阻塞网络存在内部阻塞发生阻塞的发生阻塞的22交换单元在交换网络的最后一级，即交换交换单元在交换网络的最后一级，即交换网络的两条或多条入线同时试图占用同一条出线，这称为网络的两条或多条入线同时试图占用同一条出线，这称为出线阻塞出线阻塞。由于出线阻塞不是由于交换网络本身的缺陷造。由于出线阻塞不是由于交换网络本身的缺陷造成的，采用诸如成的，采用诸如输入或输出缓冲排队方法输入或输出缓冲排队方法可以很好地解决。可以很好地解决。所以通常所以通常内部阻塞不包

13、括出线阻塞内部阻塞不包括出线阻塞。发生阻塞的发生阻塞的22交换单元在交换网络的各级交换单元在交换网络的各级(除最后一级之除最后一级之外外)，例如在图，例如在图14中，假设在入线中，假设在入线0、1、4、6上同时接收上同时接收到信元，其路由标记分别为到信元，其路由标记分别为3、7、2、4，即此时需要建立：，即此时需要建立：23n连接连接1：03n连接连接2：17n连接连接3：42n连接连接4：64 当连接当连接1和连接和连接3同时到达第同时到达第2级交换单元时，必然会同时选级交换单元时，必然会同时选择该交换单元的出线择该交换单元的出线1，于是发生内部阻塞。如果不采取，于是发生内部阻塞。如果不采取

14、适当措施，就会造成信元丢失，如图中入线适当措施，就会造成信元丢失，如图中入线4上的信息未上的信息未送到出线送到出线2。 应该注意的是，应该注意的是，BANYAN网络的内部阻塞发生在网络的内部阻塞发生在22交换交换单元内部单元内部,而不是级与级之间的链路上。而不是级与级之间的链路上。24图14 BANYAN网络内部阻塞25n内部阻塞是在内部阻塞是在22交换单元的两条入线要向同一个出线上交换单元的两条入线要向同一个出线上发送信元时产生的，在最坏的情况下，这个概率是发送信元时产生的，在最坏的情况下，这个概率是12。但。但是，如果入线上并不总是有信号，这个概率就会下降。因此，是，如果入线上并不总是有信

15、号，这个概率就会下降。因此，可以可以通过适当限制入线上的信息量或加大缓冲存储器来减少通过适当限制入线上的信息量或加大缓冲存储器来减少内部阻塞。内部阻塞。n可以通过增加多级交换网络的级数来消除内部阻塞可以通过增加多级交换网络的级数来消除内部阻塞。例如，。例如，把把88BANYAN网络的级数由网络的级数由3增加到增加到5，就可以消除内部，就可以消除内部阻塞。事实上，有人已经证明了，若要完全消除阻塞。事实上，有人已经证明了，若要完全消除NN的的BANYAN网络网络(其级数为其级数为Mlog2N)的内部阻塞，至少需要的内部阻塞，至少需要2log2N一一1级。级。26n可以增加可以增加BANYAN网络的

16、平面数，构成多通道交换网络。网络的平面数，构成多通道交换网络。n使用排序使用排序BANYAN网络，这是近年来解决网络，这是近年来解决BANYAN网网络的内部阻塞问题的一个重要研究成果。络的内部阻塞问题的一个重要研究成果。27 4) 排序排序BANYAN网络网络 经过研究发现，经过研究发现，只要只要BANYAN网络同时输入的全部数据网络同时输入的全部数据块块(信元信元)的的出线地址出线地址(路由标签路由标签)单调排列单调排列(即单调递增或单调即单调递增或单调递减递减)，则不存在内部阻塞，则不存在内部阻塞。 因此，为了满足因此，为了满足BANYAN网络无阻塞条件，解决网络无阻塞条件，解决BANYA

17、N网络的内部阻塞，网络的内部阻塞，可在可在BANYAN网络前加入排序网络前加入排序网络网络，构成排序，构成排序BANYAN网络。网络。28n (1) 排序网络排序网络 一个一个N输入的排序网络，也称为输入的排序网络，也称为N-排序器，是一种满足排序器，是一种满足下述条件的具有下述条件的具有N个输出的开关阵列。即给定输入个输出的开关阵列。即给定输入 对输入对输入I的任意组合，所形成的输出的任意组合，所形成的输出 ，且，且 ,110NiiiI,110NoooO110Nooo29 一种常用的构成排序网络的开关是由一种常用的构成排序网络的开关是由BATCHER首先首先定义的定义的2排序器，即排序器，即22比较器比较器，也称，也称BATCHER比较器比较器。由它构成的排序网络就被称为由它构成的排序网络就被称为BATCHER排序网络。排序网络。BATCHER比较器如图所示，它实际上是一个两入线两出比较器如图所示，它实际上是一个两入线两出线的比较交换单元，将入线上的两个数字进行比较后。线的比较交换单元，将入线上的两个数字进行比较后。高地