网络交换课程论文.doc

题 目 Benes网络及其特性分析 专 业 通信工程 学 号 学 生 日 期 2010-10-11 哈尔滨工业大学Vclav Edvard Bene出生于捷克，是一名美国籍数学家。1987年开始供职于Bell实验室，其间提出了一种特殊的置换Clos网络Benes网络。Benes网络是一种典型的多通路、可重排无阻塞网络。1. Benes网络1.1 Benes网络的生成Benes网络是一种多级互连网络，以一种递归的方式生成。将NNBenes网络记为BN，其中N=2m，m为整数。假设此网络所用交换单元均为22交换单元，则此网络由两部分组成：两个N2N2 Benes网络和N个22交换单元。Benes子网络与22交换单元以如图 1的方式互连：将两个N2N2 Benes子网络上下放置，记上半部分为BuN2，下半部分为BdN2，注意两者具有相同的结构，只是为了区分上下位置才定义不同的符号。在并列放置的Benes子网络左侧和右侧各放置N2个22交换单元，在左侧，每个交换单元的两个出线分别与BuN2与BdN2的入线相连，在右侧，每个交换单元的两个入线分别与BuN2与BdN2的出线相连。图 1 Benes子网络与交换单元的互连方式接下来以递归的方式生成N2N 2Benes网络。直到入线及出线数为2，亦即B2，等价于一个22交换单元，如图 2所示。图 2 22 Benes子网络根据递归的构造方式（图 1）以及递归的终止条件（图 2），就可以生成所需要的高阶交换网络。由于递归具有重复性，这种生成方式特别适合于计算机程序自动生成。NN Benes网络的级数为2log2N-1，每一级有N2个交换单元，故总共包含2log2N-1N2=Nlog2N-N2个交换单元。1.2 88 Benes网络此处以88 Benes网络为例说明Benes网络的生成方式。首先进行分解（第一次递归）：88 Benes网络应由两个44 Benes网络与8个22交换单元构成，根据1.1节的叙述，构成方式如图 3。图 3 88 Benes网络（第一次递归）再进行第二次递归，生成44 Benes网络。每个44 Benes网络由两个22 Benes网络及4个22 Benes网络组成，如图 4所示图 3。图 4 44 Benes网络（第二次递归）最后，第三次递归生成22 Benes网络。本次递归符合终止条件，出线及入线数目为2,可由22 交换单元直接代替。根据以上步骤，最终生成的88 Benes网络结构如图 5所示。图 5 88 Benes网络图中浅色虚线方框内为44 Benes网络，深色虚线方框内为22Benes网络，即22交换单元。每一个实线小方框也代表一个22交换单元。1.3 Benes网络与Banyan网络Banyan网络是一种具有唯一路径的自选路由交换网络，尽管它具有内部阻塞特性，但是对Banyan网络进行一定的改进往往可以获得可重排无阻塞及其它特性。Benes网络可以看作由两个互为镜像的Banyan网络组成，并将中间相邻的两级合为一级，如图 6所示。图 6 88 Benes网络的左侧为88 Banyan网络由于Benes网络较Banyan网络复杂，Benes网络具有无阻塞特性和多通路的特性。2. Benes网络的特性2.1 多通路特性Benes网络具有多通路特性，即从一条入线到一条出线的路径不唯一。具体来讲，NN Benes网络在理想情况下一条入线到一条出线的路径数为N2条。这是因为，Benes网络后log2N级组成的Banyan网络任何一条路径都是唯一的，而前面剩余的路径可以任意选择。由前述可知Benes网络级数为2log2N-1,则可以任意选择路径的级数为log2N-1，故路径总数为2log2N-1=N2。仍然以88 Benes网络为例，到达指定出线最多有4条路径。图 7说明了从入线2到出线1的四条路径。图 7 88 Benes网络的多通路特性2.2 自选路由特性同Banyan网络一样，Benes网络也具有自选路由的特性。差别在于，Benes网络的路径不是唯一的。若将N级网络端口号用二进制表示，其位数为log2N，而Benes网络共有2log2N-1级，且前log2N-1级的路径可以任意选择。假设出线端口号的二进制表示为nk-1nk-2n0，其中k=log2N，N为端口号。在后log2N级，路径需按此编号选择路由。记整条路径为Hl-1Hl-2H0nk-1nk-2n0其中l=log2N-1，Hi，i0，l可取0或1。据此可以确定路由，事实上，Benes网络的自选路由特性并非完全的自选路由，而需要加上补偿路由（可添加符合长度的任意路由）。如何添加路由是Benes网络路由算法的重要内容。图 8表示了88 Benes网络从入线2到出线1（二进制形式001）的自选路由。图 8 88 Benes网络的自选路由特性2.3 可重排无阻塞特性Benes网络重要的特性是其无阻塞的特性。无阻塞特性是此网络应用于实际场合的重要因素。Benes网络是可重排无阻塞网络，下面给出证明。由Benes网络的生成方法可知，Benes网络具有递归性质，因此，用归纳法来证明Benes网络的可重排无阻塞特性。证明：N=2为最小阶情况，此时，Benes网络就是22交换单元，显然，它是可重排无阻塞的。假设N=2k，k2时，Benes网络是可重排无阻塞的。则当N=2k+1，k2时，其结构如图 9所示。图 9 2k+1 阶Benes网络在最坏情况下，需要完成全置换，即所有入线和出线都不空闲。不失一般性，假设此时入线i到出线j发生阻塞，i,j0,2k-1。图 9可看作一个三级Clos网络，且中间一级是可重排无阻塞的，这样的情况满足P. Hall定理3，总是可以找到一种重排方法使得该网络是无阻塞的12。于是，当N=2k+1时，Benes网络也满足可重排无阻塞条件。3. 总结Benes网络被提出后首先用于电话交换，目前Benes由于简单的递归构造方式和优秀的负载均衡能力已被用在ATM交换机上。本文给出了Benes网络的定义及其构造方法，在此基础上分析了Benes网络的多通路特性、自选路由特性和可重排无阻塞特性。参 考 文 献1. F. K. HWANG. On Bene Rearrangeable Networks. January, 1971, The Bell System Technical Journal.2. Bene, V. E. Mathematical Theory of Connectin