Mathematics for Computer Science

10.9. Beneˇs Network 381

⎧

⎨

F

⎨

⎩

2 n Fn

⎩ 2 n1 tt

⎧

⎨

F

2 n+^1 outputs

⎨

⎩

2 n Fn

F

newinputs

⎩

Fn+1

Figure 10.2 FnC 1 , the Butterfly Net switches with 2 nC^1 inputs and outputs.

simple proof of this appears in Problem10.8.

Let’s add the butterfly data to our comparison table:

network diameter switch size # switches congestion

complete binary tree 2 logNC 2 3  3 2N 1 N

2-D array 2N 2  2 N^22

butterfly logNC 2 2  2 N.log.N/C1/

p

Nor

p

N=2

The butterfly has lower congestion than the complete binary tree. It also uses fewer

switches and has lower diameter than the array. However, the butterfly does not

capture the best qualities of each network, but rather is a compromise somewhere

between the two. Our quest for the Holy Grail of routing networks goes on.

10.9 Beneˇs Network

In the 1960’s, a researcher at Bell Labs named Vaclav E. Bene ́ ˇs had a remarkable

idea. He obtained a marvelous communication network with congestion 1 by plac-

ingtwobutterflies back-to-back. This amounts to recursively growingBeneˇs nets

by adding both inputs and outputs at each stage. Now we recursively defineBn