benes

Benes的网络特性及无阻塞条件的证明

Benes网络

Benes网络是一种多级互连网络，一个N?N Benes网络记作B(n)，它有N个输入和N个输出，共2n?1级，其中，可以用递归来定义：一个N?N n?log2N。Benes网络如图1-1所示，其中Si,j表示第i级第j个交换单元，其中0?i?2n?1且0?j?N/2。当n?1时，Benes网络即B(1)就是一个基本的交换单元。当n?1时，在B(n)中间，有两个独立的B(n?1)上下排列组成，记作B0(n?1)和B1(n?1)。在它们的两边加上第0级和第2n?2级，而且，第0级的交换单元S0,j的上输出连接B0(n?1)，下输出连接B1(n?1)，第2n?2级的交换单元S2n?2,j的上输入连接

B0(n?1)，下输入连接B1(n?1)。如一个16?16的Benes网络，即B(4)。 在B(n)中，任意的i级，0?i?2n?1，交换单元Si,j，0?j?N/2能够被2i组相对独立的子集SSi,k，0?k?2i，对于每一个SSi,k形成了某个B(n?i)的第一级，把这个B(n?i)记作Bk(n?i)。对每一个SSi,k的上输出和下输出分别是

B2k(n?i?1)和B2k?1(n?i?1)的输入，而B2k(n?i?1)和B2k?1(n?i?1)的输出分别是SS2n?2?i,k的上输入和下输入。具有这种特性的B2k(n?i?1)和B2k?1(n?i?1)称作共轭网络。如图1-1中B0(2)和B1(2)是一对共轭网络。Benes网络具有很好的共轭性，利用这种性质，我们会在路径上得到一些结果。

010S0,0S2n?2,01?23B0(n?1)?2S0,1S2n?2,1??3??N-4N-3N-4S0,2/N?2S2n?2,2/N?2N-3?N-2N-1B1(n?1)?N-2S0,2/N?1S2n?2,2/N?1N-1级数01?(2n?3)2n-1

图1 一个BENES网络B?n?

图2一个16*16的BENES网络

路径及共轭路径

定义1：在一个N?N多级互连的网络中，从任意一个输入端到任意一个输出端间的连接称为一条路径，它包括途中所经过的交换单元、交换单元之间的链路以及交换单元的选路等。

在Benes网络中，可以用2n?1位二进制位来表示任意给定输入端的一条路

径，记作?2n?2?2n?3...?1?0，其中，?i(0?i?2n?1)表示在这条路径中第2n?2?i级交换单元的路由选择，当交换单元选择上输出?i为0，选择下输出?i为1。 定理1：在B(n)中，任意一条路径?2n?2?2n?3...?1?0中，路径后半部分?n?1...?1?0的二进制编码值等于输出端口号。

证明：用数学归纳法证明。当n?1时，B(1)就是一个基本的交换单元。任意一条路径?0，当?0?0时，从上输出端口输出，输出端口号为0。当?0?1时，从下输出端口输出，输出端口号为1。显然成立。

假设在B(n)中成立，即任意一条路径?2n?2?2n?3...?1?0中，路径后半部分

?n?1...?1?0的二进制编码值等于输出端口号。

我们来看B(n?1)。设任意一条路径?2n?2n?1...?1?0从输出端口i(0?i?2n?1)输出，我们要证明的是：?n?1...?1?0?i。

首先，来看输出端的情况，当i是偶数时，它是上输出端，由?i的取值方法可知?0?0；同理当i是奇数时，它是下端输出，得?0?1。另外，Benes网络中每个交换单元有两个输出端，所以它所在的交换单元是第[i/2]个。

其次，由Benes网络的递归结构可知，该路径的中间部分?2n?2...?1必然在

B0(n)或B1(n)。不妨设是B0(n)，由假设可知，?n...?2?1的二进制编码值等于端口号，设为k;又已知第2n级的输出端口是i，所以k?[i/2]，即?n...?2?1?[i/2]。对此式两边乘2，分以以下两种情况讨论：

当i是偶数时，左边乘以2即把二进制编码左移一位，得?n...?2?10，右边乘以2得i，所以?n...?2?10?i。又因为?0?0，得到?n...?2?1?0??n...?2?10?i，即命题成立。

当i是奇数时，左边乘2可得?n...?2?10，对于右边，因为[i/2]?(i?1)/2，乘2后得?n...?2?10?i?1，两边加1得?n...?2?11?i。又因为?0?1，得

?n...?2?1?0??n...??1i，即命题成立。定理1证毕。 21? 推论1：在B(n)中，任意两条路径?2n?2?2n?3...?1?0和?2n?2?2n?3...?1?0，它们到达相同的输出端的充分必要条件是，?i??i(i?0,...,n?1)。

现在已知Benes网络中，任意一条路径?2n?2?2n?3...?1?0的后半部分是决定输出端，下面来讨论前半部分的作用。先引入共轭路径。

定义2：在Benes网络中，任意一条路径p1??2n?2?2n?3...?1?0，把它的第i级

?2n?2?i(0?i?n?1)取反，得到一条新的路径p2，则p1和p2称为在i级上的共轭

路径。

定理2：在Benes网络中，任意一对共轭路径能够保证同一对输入端口和输出端口之间的连接。

定理3：在B(n)中，任意一对输入端和输出端之间，存在着2n?1条不同的路径。

定理4：在B(n)中，任意一个无冲突路径集，它的每条路径在i(0?i?n?1)级上的共轭路径所组成的集合，也是无冲突的。

证明：设B(n)中任意一个无冲突路径集?，它的每条路径在i(0?i?n?1)级上的共轭路径所组成的集合?。要证?也是无冲突的。

用反证法证明。设在?中有两条路径p,q在j(0?j?2n?2)级上发生冲突，

p,q在?中的对应共轭路径分别为p1和q1。

若0?j?i时，p,q在第0级到第i?1级上与p1,q1在?中相应部分完全相同，则p1和q1也是无冲突的，与已知矛盾。

若j?i时，p和q同时使用某一上端口（或下端口），则它们的共轭路径p1和，即p1和q1也是无冲突的，与已知矛盾。 q1同时使用某一下端口（或上端口）

若i?j?2n?2?i时，p，q冲突的端口必定属于B2k(n?i?1)或B2k?1(n?i?1)， 不妨设为Bk(n?i)，则它们的共轭路径p1和q1在B2k?1(n?i?1)中在对应的端口冲突，与已知矛盾。

若2n?2?i?j?2n?2时，p，q在第2n?2?i级到第2n?3级上与p1，q1在

?中对应部分完全相同，则p1和q1也是无冲突的，与已知矛盾。定理4得证。

因此，在Benes网络中，一旦某条路径发生故障时，我们可以用共轭路径来代替，当有多条路径发生故障时，我们可以用这条路径在某级上的共轭路径来代替。这样充分利用Benes网络的冗余路径，以保证网络的正常运行，提高网络的可靠性。由Benes网络具有共轭路径特性可知，Benes网络具备无阻塞的可能性。

BENES网络的无阻塞特性证明

由图可以看出，BENES网络实际上相当于两个BANYAN（BANYAN与反转BANYAN）的背对背相连，并将中间相邻两级合并为1级。因此先证明BANYAN网络的物阻塞特性。

经过研究发现，只要BANYAN网络同时输入的全部数据块的出线地址单调排列，则不存在内部阻塞。即若BANYAN网络是非阻塞的，如果其活动输入x1，x2，…，

xk和相应的目的地址y1，y2，…，yk满足以下条件：(1)输出单调：y1y2>…>yk）；(2)输入集中：x1,x2,…,xk占据连续的输入端口。

首先假设BANYAN网络的输入信元的出线地址是连续单调的。

在N级BANYAN网络的第k级（1?k?N）还有2k-1个子网络。第k级的每个节点可独立的表示为两个二进制数(aN-k….a1，b1…..bk-1)。其中aN-k….a1自上而下表示第k级子网络各个节点，b1…..bk-1自上而下表示每个子网络的分网。

第k+1级节点通过输出连接bk与第k级节点(aN-k….a1，b1…..bk-1)联系起来，其可表示为（aN-k-1….a1，b1…..bk-1bk）。因此，对于一个输入为x= aN….a1，输出为y= b1…..bN （表示为）的路径存在以下一系列的节点：(aN-1….a1,?)，(aN-2….a1, b1) ，(aN-k….a1, b1…..bk-1)，…，(?,b1…..bN-1)。假设有两个数据报，一个输入为x= aN….a1输出为y= b1…..bN，另一个输入为x= aN'.....a1'输出为y= b1'.....bN'，二者在第k即产生冲突。即两条路和径通过相同节点，可表示为(aN?k.....a1,b1.....bk?1)?(aN?k'.....a1',b1'.....bk?1')，共用相同的输出端，即bk?bk'。那么我们可以得出

aN?k.....a1?aN?k'.....a1' (1)

b1.....bk?b1'.....bk' (2) 既然假设BANYAN网络的输入信元是连续单调的（单调增或单调减），那么位于x和x'之间的有效信元总数x'?x?1一定小于等于位于y和y'之间的有效信元总数y'?y?1。可得

x'?x?y'?y (3)

根据(1)和(2)，我们可以得出

x'?x?aN.....a1?aN'.....a1'

?2N?k(aN.....aN?k?1?aN'.....aN?k?1')?2N?k (4) y'?y?b1'.....bN'?b1.....bN

?bk?1'.....bN'?bk?1.....bN?2N?k?1 (5) 经比较(3)，(4)，(5)三式，可发现矛盾。因此路径和必相互独立而不产生冲突。故上面结论得证。

经过证明可知，地址单调的N个信元经过左边BANYAN网络，出线地址单调，再作为右边BANYAN网络的入线地址单调，故出线地址单调，故不存在内部阻塞。因此，BENES网络具有可重排无阻塞特性。这种网络具有以下一些很好的特性：

（1） BENES网络由两个背靠背的BANYAN网络连接而成。该网络可以通过开

关状态的改变实现N*N的任意交换。 （2） BENSES网络可以被拆分成不同的级，因此可以逐级利用和控制整个网

络。

（3） 规模为N的BENES网是由2log2N?1 级的 2*2的开关构成，开关总

数是Nlog2N?N 。

2（4） BENES网的每一个2*2开关，2个输入和2个输出定义为互斥对。这

些互斥对可以由一个比特配置，即每一级的N个开关可以由N个

22比特来配置。

（5） BENES网络是一种递归结构。可以用较小的BENES网构成较大的BENES

网。 BENES网是一种可重排网，能实现输入端到输出端的所有置换，作为非阻塞开关网络在通信领域得到广泛的应用。这种网络的特点是可以通过具体的寻径路由算法，根据全通道排序的要求，实时改变各级节点开关的状态（直通或交叉），从而有效避免路径冲突。

参考文献

[1]一种基于BENES网络的可重构比特置换系统设计 向楠等 计算机工程 2007 [2]证明BANYAN网络具有可重排无阻塞特性 王巽冬 2009 [3]现代通信中的排队论 陈鑫林 电子工业出版社 1999 [4] BENES网络中路径特性的探讨 顾沈明等 2006.06

本文来源：https://www.bwwdw.com/article/jiut.html