网络交换课程论文.docx

PAGE  PAGE 6 题 目 Benes网络及其特性分析 专 业 通信工程 学　　 号 学 生 　　　 日 期 2010-10-11 哈尔滨工业大学  Václav Edvard Bene?出生于捷克，是一名美国籍数学家。1987年开始供职于Bell实验室，其间提出了一种特殊的置换Clos网络——Benes网络。Benes网络是一种典型的多通路、可重排无阻塞网络。 Benes网络 Benes网络的生成 Benes网络是一种多级互连网络，以一种递归的方式生成。将N×NBenes网络记为BN，其中N=2m，m为整数。假设此网络所用交换单元均为2×2交换单元，则此网络由两部分组成：两个N2×N2 Benes网络和N个2×2交换单元。Benes子网络与2×2交换单元以如 REF _Ref274641658 \h \* MERGEFORMAT 图 1的方式互连：将两个N2×N2 Benes子网络上下放???，记上半部分为BuN2，下半部分为BdN2，注意两者具有相同的结构，只是为了区分上下位置才定义不同的符号。在并列放置的Benes子网络左侧和右侧各放置N2个2×2交换单元，在左侧，每个交换单元的两个出线分别与BuN2与BdN2的入线相连，在右侧，每个交换单元的两个入线分别与BuN2与BdN2的出线相连。 图  SEQ 图 \* ARABIC 1 Benes子网络与交换单元的互连方式 接下来以递归的方式生成N2×N 2Benes网络。直到入线及出线数为2，亦即B2，等价于一个2×2交换单元，如 REF _Ref274642346 \h \* MERGEFORMAT 图 2所示。 图  SEQ 图 \* ARABIC 2 2×2 Benes子网络 根据递归的构造方式（ REF _Ref274641658 \h \* MERGEFORMAT 图 1）以及递归的终止条件（ REF _Ref274642346 \h \* MERGEFORMAT 图 2），就可以生成所需要的高阶交换网络。由于递归具有重复性，这种生成方式特别适合于计算机程序自动生成。 N×N Benes网络的级数为2log2N-1，每一级有N2个交换单元，故总共包含2log2N-1×N2=Nlog2N-N2个交换单元。 8×8 Benes网络 此处以8×8 Benes网络为例说明Benes网络的生成方式。首先进行分解（第一次递归）：8×8 Benes网络应由两个4×4 Benes网络与8个2×2交换单元构成，根据 REF _Ref274643796 \r \h 1.1节的叙述，构成方式如 REF _Ref274644170 \h \* MERGEFORMAT 图 3。 图  SEQ 图 \* ARABIC 3 8×8 Benes网络（第一次递归） 再进行第二次递归，生成4×4 Benes网络。每个4×4 Benes网络由两个2×2 Benes网络及4个2×2 Benes网络组成，如 REF _Ref274644939 \h \* MERGEFORMAT 图 4所示 REF _Ref274644170 \h \* MERGEFORMAT 图 3。 图  SEQ 图 \* ARABIC 4 4×4 Benes网络（第二次递归） 最后，第三次递归生成2×2 Benes网络。本次递归符合终止条件，出线及入线数目为2,可由2×2 交换单元直接代替。 根据以上步骤，最终生成的8×8 Benes网络结构如 REF _Ref274646009 \h \* MERGEFORMAT 图 5所示。 图  SEQ 图 \* ARABIC 5 8×8 Benes网络 图中浅色虚线方框内为4×4 Benes网络，深色虚线方框内为2×2Benes网络，即2×2交换单元。每一个实线小方框也代表一个2×2交换单元。 Benes网络与Banyan网络 Banyan网络是一种具有唯一路径的自选路由交换网络，尽管它具有内部阻塞特性，但是对Banyan网络进行一定的改进往往可以获得可重排无阻塞及其它特性。Benes网络可以看作由两个互为镜像的Banyan网络组成，并将中间相邻的两级合为一级，如 REF _Ref274663687 \h \* MERGEFORMAT 图 6所示。 图  SEQ 图 \* ARABIC 6 8×8