Chapter 10 Communication Networks380
2 inputs 2 outputs
À À
ND 2
1Figure 10.1 F 1 , the Butterfly Net switches withND 21.iD1;:::;2n. The output switches ofFnC 1 are simply the output switches of each
of theFncopies.
SoFnC 1 is laid out in columns of height 2 nC^1 by adding one more column of
switches to the columns inFn. Since the construction starts with two columns
whennD 1 , theFnC 1 switches are arrayed innC 1 columns. The total number of
switches is the height of the columns times the number of columns, 2 nC^1 .nC1/.
Remembering thatnDlogN, we conclude that the Butterfly Net withNinputs
hasN.logNC1/switches.
Since every path inFnC 1 from an input switch to an output is the same length,
nC 1 , the diameter of the Butterfly net with 2 nC^1 inputs is this length plus two
because of the two edges connecting to the terminals (square boxes) —one edge
from input terminal to input switch (circle) and one from output switch to output
terminal.
There is an easy recursive procedure to route a packet through the Butterfly Net.
In the base case, there is only one way to route a packet from one of the two inputs
to one of the two outputs. Now suppose we want to route a packet from an input
switch to an output switch inFnC 1. If the output switch is in the “top” copy ofFn,
then the first step in the route must be from the input switch to the unique switch
it is connected to in the top copy; the rest of the route is determined by recursively
routing the rest of the way in the top copy ofFn. Likewise, if the output switch is in
the “bottom” copy ofFn, then the first step in the route must be to the switch in the
bottom copy, and the rest of the route is determined by recursively routing in the
bottom copy ofFn. In fact, this argument shows that the routing isunique: there is
exactly one path in the Butterfly Net from each input to each output, which implies
that the network latency when minimizing congestion is the same as the diameter.
The congestion of the butterfly network is about
p
N. More precisely, the con-
gestion is
p
NifNis an even power of 2 andp
N=2ifNis an odd power of 2. A