10.9. Bene ̆s Network 293
in 0 in 1 in 2out 0 out 1 out 2(b)Give an input/output permutation, 0 , that forces maximum congestion:
0 .0/D 0 .1/D 0 .2/D(c)Give an input/output permutation, 1 , that allowsminimumcongestion:
1 .0/D 1 .1/D 1 .2/D(d)What is the latency for the permutation 1? (If you could not find 1 , just
choose a permutation and find its latency.) 0.5in
Class Problems
Problem 10.2.
The Beneˇs network has a max congestion of 1; that is, every permutation can be
routed in such a way that a single packet passes through each switch. Let’s work
through an example. Within the Benes network of sizeˇ N D 8 shown in Fig-
ure 10.4, the two subnetworks of sizeN D 4 are marked. We’ll refer to these as
theupperandlowersubnetworks.
(a)Now consider the following permutation routing problem:.0/D 3 .4/D 2
.1/D 1 .5/D 0
.2/D 6 .6/D 7
.3/D 5 .7/D 4Each packet must be routed through either the upper subnetwork or the lower sub-
network. Construct a graph with vertices 0, 1,... , 7 and draw adashededge
between each pair of packets that can not go through the same subnetwork because
a collision would occur in the second column of switches.
(b)Add asolidedge in your graph between each pair of packets that can not go