Proving the congestion of a butterfly network.

Question

In MIT's 6.042j course assignment 6. In problem 5, it is required to prove that a butterfly network has congestion of \sqrt{N}. If we have an 8-input butterfly network and let's assume that all of the data , from all the input nodes, is sent to output 0. Won't this make a congestion of 8 at the switch at level 3 row 000? Doesn't this contradict with the congestion being \sqrt{N}? Is there something I am missing here?

Answer 1

I had the same issue doing this 6.042 question, and I think it's to do with a misunderstanding on what congestion means. However, first, I notice a problem with your question. As stated in the book $N = 2^n$, and congestion is $\sqrt{N}$ if n is even, or $\sqrt{{N \over 2}}$ if n is odd.

If we have an 8-input butterfly network, this works out to $N = 2^3$, making n odd, so the congestion should be $\sqrt{{8 \over 2}} = 2$.

OK, so what is congestion? As you mentioned in your comment, it consists of a routing, but in your question you incorrectly assume all inputs are going to the same output. This is not how routing works, a routing is a permutation (I believe this can also be called a total bijective function) - that is every input corresponds to one and only one output. For example here is a routing for your 8-input butterfly network:

• $\pi(0) = 0$
• $\pi(1) = 1$
• $\pi(2) = 2$
• ...
• $\pi(7) = 7$

If you were to draw that out you'd notice that congestion for this routing would be 1, because each switch has at most 1 path passing through it. However, congestion is also defined as the worst possible routing, so consider this partial routing;

• $\pi(0) = 0$
• $\pi(4) = 1$

I've only drawn out two paths in solid, arrow-headed lines, to illustrate the point. The paths shown are:

• $P_{i_0, o_0} = ((i_0, s_{1, 0}), (s_{1, 0}, s_{2, 0}), (s_{2, 0}, o_0))$
• $P_{i_4, o_1} = ((i_0, s_{1, 0}), (s_{1, 0}, s_{2, 0}), (s_{2, 0}, o_1))$

(note: I think this is complicated enough without adding in binary notation, so my notation for switches is $s_{level, row}$ where level is the 'column' of switches)

Notice that switches $s_{1, 0}$ and $s_{2, 0}$ both have two paths passing through them so the congestion is 2.

Notice also, that the congestion cannot get any worse than this. Switch $s_{1, 0}$ has one unused output edge, $(s_{1, 0}, s_{2, 2})$, but it is already using both of its available inputs from $i_0$ and $i_4$, so it cannot possibly have another path passing through. Similarly $s_{2, 0}$ has one unused input edge, $(s_{1, 2}, s_{2, 0})$, but it is already using both of its outputs to $o_0$ and $o_1$ - and as I mentioned earlier, a routing is a permutation, so no further routes can be assigned to these outputs in this permutation.

As mentioned in the 6.042 question hints, the total possible paths coming in to a switch at level i is $2^i$, and the total possible paths going out are $2^{n-i}$. Plugging these values in for $s_{1, 0}$ we can see there are $2^i = 2^1 = 2$ possible paths coming in and $2^{n-i} = 2^{3-1} = 4$ paths going out. The congestion of the switch, then is the minimum of these two values, again because routing is one-to-one.

So now we have to prove that;

$max( min(2^i, 2^{n-i})\ \forall\ i \in [0, n]) = \sqrt{{N \over 2}}\ or\ \sqrt N $

First, let's look at the first few values of n, at each level seeing what the total number of possible incoming and outgoing paths are.

n	L0	L1	L2	L3	L4	L5
1	$(2^0, 2^1)$	$(2^1, 2^0)$
2	$(2^0, 2^2)$	$(2^1, 2^1)$	$(2^2, 2^0)$
3	$(2^0, 2^3)$	$(2^1, 2^2)$	$(2^2, 2^1)$	$(2^3, 2^0)$
4	$(2^0, 2^4)$	$(2^1, 2^3)$	$(2^2, 2^2)$	$(2^3, 2^1)$	$(2^4, 2^0)$
5	$(2^0, 2^5)$	$(2^1, 2^4)$	$(2^2, 2^3)$	$(2^3, 2^2)$	$(2^4, 2^1)$	$(2^5, 2^0)$

As you can see, the value of the exponent on the incoming paths is an increasing sequence, $[0, n]$ e.g. $(2^0, 2^1, 2^2, 2^3, 2^4, ..., 2^n)$, and the outgoing paths is a decreasing sequence of $[n, 0]$ e.g. $(2^n, 2^{n-1}, 2^{n-2}, ..., 2^0)$. The point where $min(2^i, 2^{n-i})$ is at its greatest value will be halfway. Since congestion is dealt in whole numbers this makes it ${n \over 2}$ if n is even and ${(n-1) \over 2}$ if n is odd.

This then explains why the congestion is $\sqrt N$ where n is even, since $N = 2^n$, so by simple algebra $2^{{n \over 2}} = \sqrt {2^n} = \sqrt N$. Similarly where n is odd $2^{n-1 \over 2} = 2^{n \over 2^2} = \sqrt{2^n \over 2} = \sqrt{N \over 2}$.