Spring 2004  Routing on Multibutterflies  Abhiram Ranade

The Multibutterfly network was invented by Upfal[4]. Until then, the AKS network was the only network capable of routing permutations deterministically in O(log N) time, where N is the number of nodes in the network. The constants factors in the time taken by AKS are huge, and so far, the networks are completely impractical. Multibutterflies, on the other hand, give O(log N) time with very small constants. Further, multibutterflies possess some fault-tolerance properties that make them interesting candidates to actually build.

Multibutterflies are derived from expander graphs.

1 Expander Graphs

An (α, β, N, d) expander is a bipartite graph of max degree d on vertex sets U, V of size N each such that every subset of U of size k ≤ αN is connected to at least βk nodes in V. β is called the expansion of the graph.

We are typically interested in the case when α, β, d are constants independent of N, α > 0, β > 1. Note that the definition implies that αβ ≤ 1.

Theorem 1 For all α > 0, β > 1 s.t. αβ < 1, there exists an (α, β, N, d) expander, for

d > β + 1 + \frac{β + 1 + ln2β}{ln\frac{1}{αβ}}

Proof: We randomly construct a graph with degree at most d and show it is an (α, β, N, d) expander with non-zero probability. The construction is as follows: (1) Start with 2 sets, U, and V each containing N vertices. (2) Expand each vertex in U and V into d vertices.

(3) Pick a random perfect matching on the respective resulting sets U′ and V′. (4) Collapse each d-tuple of vertices in U′ and V′ back to the vertex from which they were created. At this point we will have a multigraph in which each vertex has degree d. (5) Convert this to a graph by replacing multiple edges (if any) connecting the same pair of vertices with a single edge. We will show that this graph is an expander with non zero probability.

If the graph is not an expander, then there is some S ⊆ U of size k ≤ αN and T ⊆ V of size βk, such that all the neighbors of vertices in S are strictly contained in T. We first consider the probability that this happens for fixed sets S and T. Let S′ and T′ denote the sets resulting from S and T respectively in step 2 above. The number of ways in which the vertices in S′ can be matched is

|V′| (|V′| − 1) … (|V′| − |S′| + 1) = Nd(Nd − 1) … (Nd − kd + 1)

The number of ways in which the vertices of S′ can be matched with vertices in T′ is

|T′| (|T′| − 1) … (|T′| − |S′| + 1) = βkd(βkd − 1)(βkd − kd + 1)

Thus the probability that S′ has all its neighbors in T′ is

\frac{βkd · βkd − 1 · βkd − 2 . . . · βkd − kd + 1}{Nd · Nd − 1 · Nd − 2 . . . · Nd − kd + 1} ≤ (\frac{βkd}{Nd})^{kd} = (\frac{βk}{N} )^{kd}

This is precisely the probability that S has all its neighbors inside T. Now, observe that there are \binom{N}{k} ways of choosing S, and \binom{N}{βk} ways of choosing T for every k ≤ αN Thus, the probability that the graph is not an expander is at most:

∑_{k=1}^{αN}\binom{N}{k}\binom{N}{βk} (\frac{βk}{N} )^{kd} ≤ ∑_{k=1}^{αN} \{(\frac{k}{N} )^{d−β−1} · e^{β+1} · β^{d−β}\}^{k} ≤ ∑_{K=1}^{kN} \{α^{d−β−1} · e^{β+1} · β^{d−β}\}^{k}

Using \binom{n}{r} ≤ (\frac{ne}{r})^{r}, and noting that \frac{k}{N} ≤ α. The series above is geometric, and will be smaller than 1 if we choose

α^{d−β−1} · e^{β+1} · β^{d−β} ≤ 1/2

Simplifying we get:

d > β + 1 + \frac{β + 1 + ln 2β}{ln \frac{1}{αβ}}

For this choice of d, there is non zero probability of finding a (α, β, N, d) expander, i.e. such expanders exist.

Note that by choosing larger values of d we can boost up the probability and make it extremely likely that the above construction gives expanders. The trouble, however, is that no efficient procedure is known for verifying that the graph we generated is an expander!

Instead of randomized constructions such as the one above, one might attempt a more direct, deterministic construction. Such constructions have been found quite hard, and the bounds obtained are weaker[3].

For now, the best course is very likely to use the randomized construction and use simulations to see how well the graph does on standard packet routing problems. This has been found to be quite promising[2].

1.1 Concentrators and Splitters

A (α, β, N, M, d) concentrator has two sets of vertices, U, V, with |U| = N and |V | = M. As in an expander, the max degree of any node is d and any subset of U having k ≤ αN nodes is required to be connected to at least βk nodes in V.

A (α, β, N, 2d) splitter has three sets of vertices, U, V_{0}, V_{1}, with |U| = N and |V_{0}| = |V_{1}| = N/2. The subgraph on vertex sets U and V_{0} as well as the subrgaph on vertex sets U, V_{1} are each required to form an (α, β, N, N/2, d) concentrator. We will refer to the set U as the inputs of the splitter, the set V_{0} as the upper outputs, and the set V_{1} as the lower outputs, and the corresponding concentrators as the upper and lower concentrators.

Following the ideas for expanders, it is possible to show that for α > 0, β > 1 s.t. αβ < 1/2, there exist splitters for

d > β + 1 + \frac{β + 1 + ln 4β}{ln \frac{1}{2αβ}}

A minor technical property of a splitter that we will need later concerns edge coloring. We note that it is possible to color the edges of a splitter with colors 1, …, 2d such that edges leaving any splitter input have distinct colors, and also edges entering any splitter output. This follows easily using Hall’s matching theorem.

2 Multibutterflies

A (α, β, 2^{n}, 2d) multibutterfly has (n + 1)2^{n} nodes, arranges in n + 1 levels. The levels are numbered 0 through n, and nodes in level 0 are called inputs, and nodes in level n outputs. Within each level, the nodes are numbered 0 through 2^{n} −1. I will use N to denote the number of inputs (2^{n}) rather than the number of nodes. The network has a recursive structure as follows. Let U denote all nodes in level 0, V_{0} denote nodes 0, …, 2n − 1 − 1 in level 1, and V_{1} denote nodes 2^{n}, …, 2^{n} − 1 in level 1. Then U, V_{0}, V_{1} are connected using a (α, β, 2^{n}, 2d) splitter. V_{0} and V_{1} form inputs to (α, β, 2^{n−1}, 2d) multibutterflies.

Path selection on a multibutterfly is similar to a Butterfly, in level 0 we determine whether the packet is destined for outputs belonging to the upper submultibutterfly or lower, and continue the process recursively. This, as in the Butterfly, can be done by considering the bits in the destination address. The crucial difference from the Butterfly is that we are no longer restricted to a unique path from any input to output. Each node in level 0 has d edges going to the top multibutterfly and d edges going to the bottom multibutterfly. Thus at each level a packet has d choices.

We assume that each node of the multibutterfly has a single buffer, capable of holding a single packet.

2.1 Light Loading

In these notes, I will only consider the problem of routing N = 2^{n} packets on an N input multibutterfly. (note that N does not refer to the number of nodes). In particular, I will show how to route an arbitrary permutation of N packets situated one per input to the outputs in O(log N) time. A somewhat more complicated analysis will give the same time for routing N log N packets.

2.2 Waves

The first step in routing is to break up the packets into L waves, numbered 0, 1, …, L − 1, with L = 1/2α. Each wave is routed independently. In fact, in what follows, we only consider the problem of routing a single wave. Since there are only a constant number of waves, the total time for N packets is only a constant multiple of the time for one wave of packets.

A packet with destination x is placed in wave x mod L. This has the following useful effect. Consider any splitter from any level i to level i + 1. The splitter has M = N/2^{i} inputs and M/2 upper outputs and M/2 lower outputs. Clearly, only M/2 destinations are reachable from the upper or lower outputs, of which only M/2L belong to any single wave. Thus we know that at most M/2L = Mα packets from any single wave pass through either the upper or lower concentrator. This fact will be crucial in utilizing the expansion properties of the concentrators later.

2.3 Routing algorithm

We will move the packets from the inputs of the multibutterfly to the outputs in an essentially greedy manner, ensuring at each step that no buffers overflow.

In a basic routing step, we attempt to move packets between adjacent levels in the network. For simplicity, in the even routing steps, we move packets from even levels to odd, and in odd routing steps, from odd levels to even levels.

Consider any even step, and any node in any even level i. If the node has a packet, then it attempts to send it on to the next level during the step. By looking at the destination addres of the packet, the node can determine whether the packet needs to be sent to the upper concentrator, or the lower concentrator. But even within a concentrator, it has a choice of d edges for sending the packet. It must determine which edge to send the packet along based on which of the nodes in the next level have space for the packet.

This is done by dividing the step into 2d substeps. The edges belonging to each splitter are likewise colored in 2d colors. In the cth substep each node checks if its packet can reach its destination if transmitted along edge of color c, and if the node in the next level has space to receive the packet. It then transmits the packet if necessary. Notice that each substep, every node in level i + 1 can receive at most 1 packet since each level i + 1 node has at most one incoming edge of any color. Thus, we are guaranteed that there will be no queue overflows.

Each substep takes a constant amount of time, and since d is a constant, so does a step. We run the basic step O(log N) times. The next section shows that this is sufficient to

route all packets, and determines the precise number of steps required.

3 Analysis

Instead of directly analyzing the number of timesteps needed, it turns out to be convenient to estimate the number of sweeps, defined as follows. Define the sth sweep to consist of transmissions of packets from level i to i + 1 during time step i + s, for all i. Clearly, if the total time taken is T, then there are (T − log N)/2 sweeps. Thus, to show that total time is logarithmic, it suffices to show that all the N/L packets get delivered in a logarithmic number of sweeps.

The analysis uses a potential function argument. With any configuration of packets in the multibutterfly we associate a potential, which informally represents the difficulty of delivering the packets starting in that potential. We then show that in a single sweep the potential of the system drops by a constant fraction, using which it is possible to show that all packets get delivered in a logarithmic number of sweeps.

3.1 Potential Function

Each packet in level i of the multibutterfly is assigned a potential w^{i} where w < 1 is a constant to be determined later. The potential of the entire system is simply the sum of the potentials of all packets in the system. Initially, all packets are in level 0, so the potential is clearly N/L.

Define x_{i} to be the number of packets in level i before sweep s. Let X denote the total potential before the sweep. We have

X = ∑_{i=0}^{n} x_{i}w^{i}

Let y_{i} denote the number of packets moving into level i during sweep i. It will be convenient to set y_{0} = 0. Further, all the packets arriving into level n get immediately removed; and so we will think of them as moving into a fictitious level n+1. This is modelled by setting y_{n+1} = y_{n}. The number of packets in level i after the sweep is x_{i} + y_{i} − y_{i+1}. Define Y = ∑_{i=0}^{n} y_{i}w^{i}. Let X′ denote the potetial after the sweep. We have,

X′ = ∑_{i=0}^{n}(x_{i} + y_{i} − y_{i+1})w^{i} = X + Y − w^{−1} ∑_{i=0}^{n} y_{i+1}w^{i+1} = X + Y − w^{−1}Y − y_{n}w^{n}

since y_{0} = y_{n+1} = 0. Next we relate X and X′ by accounting for expansion.

3.2 Effect of expansion

Consider the state of any splitter S from level i to level i + 1 at a time instant t at which packets have moved from level i to i + 1 during a sweep s, but not yet moved from level i + 1 to i + 2. Let I(S) denote the set of splitter inputs having a packet at time instant t, and O(S) the set of outputs having packets at instant t. Further let I_{u}(S) denote the set of inputs that have packets that need to be sent through the upper concentrator, and likewise I_{l}(S). We know from section 2.2 that |I_{u}(S)| and I_{l}(S) are both at most Mα,

During sweep s, each of the inputs I_{u}(S) attempted to send its packet through the upper concentrator but failed. Thus, it must be the case that each node in the neighborhood of I_{u}(S) must have a packet. But from section 2.2 we know that |I_{u}(S)| ≤ Mα, where M is the number of inputs to the splitter. Thus expansion property applies to I_{u}(S) and thus the size of the neighborhood is at least β|I_{u}(S)|. Thus the upper concentrator has at least β|I_{u}(S)| packets in it, and likewise the lower concentrator has at least β|I_{l}(S)|. Thus |O(S)| ≥ β(|I_{u}(S)| + |I_{l}(S)|) = β|I(S)|.

Further note that at instant t, y_{i+1} packets have already arrived into level i + 1 but none have yet left out of level i + 1. Thus we have

∑_{S} O(S) = x_{i+1} + y_{i+1}

where the sum is over all splitters in level i. For level i, however, y_{i} packets have arrived, and y_{i+1} have left by time instant t. Thus summing over all splitters we have

∑_{S} I(S) = x_{i} + y_{i} − y_{i+1}

Thus we know for all i = 0, …, n − 1:

x_{i+1} + y_{i+1} ≥ β(x_{i} + y_{i} − y_{i+1})

Thus

x_{i+1} + y_{i+1} ≥ β(x_{i} + y_{i} − y_{i+1})
x_{i+1} + y_{i+1} + βy_{i+1} ≥ β(x_{i} + y_{i})

∑_{i=0}^{i=n−1}(x_{i+1} + y_{i+1} + βy_{i+1})ω^{i+1} ≥ ∑_{i=0}^{i=n−1} β(x_{i} + y_{i})ω^{i+1}

X + Y + βY ≥ ωβX + ωβY − βy_{n}ω^{n+1}

Y (β + 1 − βω) ≥ X(ωβ − 1) − βy_{n}ω^{n+1}

\frac{Y}{X} ≥ \frac{(ωβ − 1)}{(β + 1 − βω)} − \frac{βω^{n+1}y_{n}}{X(β + 1 − βω)}

We can use this to estimate the factor f by which the potential drops in a single sweep:

f = \frac{X − Y (\frac{1}{ω} − 1) − y_{n}ω^{n}}{X}
= 1 − \frac{Y (1 − ω)}{Xω} − \frac{y_{n}ω^{n}}{X}
≤ 1 − \frac{1 − ω}{ω} (\frac{ωβ − 1}{β + 1 − βω} − \frac{βy_{n}ω^{n+1}}{X(β + 1 − βω)}) − \frac{y_{n}ω^{n}}{X}
= \frac{βω + ω − βω^{2} − βω + 1 + βω^{2} − ω}{ω(β + 1 − βω)} + \frac{1 − ω}{ω} \frac{βy_{n}ω^{n+1}}{X(β + 1 − βω)} − \frac{y_{n}ω^{n}}{X}
= \frac{1}{ω(β + 1 − βω)} + \frac{y_{n}}{X} (\frac{βω^{n} − βω^{n+1} − βω^{n} − ω^{n} + βω^{n+1}}{β + 1 − βω} )
= \frac{1}{ω(β + 1 − βω)} + \frac{y_{n}}{X} (\frac{−ω^{n}}{β + 1 − βω} )
≤ \frac{1}{ω(β + 1 − βω)}

It may be seen that f < 1 for any β > 1 and w = (1 + β)/2β. In particular, suppose β = 2, we get f < 8/9.

Thus the potential drops by a constant factor in each step. The potential of a single packet in the last level is w^{log N}, so we can be assured that all packets are delivered if the potential of the entire system goes below w^{log N}. The number of sweeps needed is thus

log_{f} (\frac{N/L}{w^{log N}} ) = O(log N)

4 Summary

The previous section shows how a single wave can be routed deterministically in O(log N) sweeps. Since there are 1/2α waves, the total time is O(log N) for routing all waves.

Leighton-Maggs[2] and Upfal[4] show how to solve the loaded multibutterfly problem as well in time O(log N). In this each input starts off with log N packets such that each output is the destination of log N packets as well. This requires a slightly more complicated routing algorithm, as well as a slightly more complicated potential function for the analysis.

Leighton and Maggs also show that the multibutterfly can tolerate faults. The idea is that destroying some routing nodes is fine so long as the expansion properties hold: if we start off with a network having high enough expansion, then if each node fails with a small enough probability, we can expect expansion to not drop much.

Leighton, Maggs and Arora also show how to establish conflict free paths and design a rearrangeable network[1].

Exercises

1. Show that an ordinary Butterfly is a (1, 0.5, 2^{n}, 2) multibutterfly. Show that it is not really possible to improve the estimates of the first two parameters.

2. Consider the following bipartite graph having 2N left vertices and N right vertices. Vertex i on the left is connected to vertices i mod N and i + 3 mod N, with N a power of 2. Does this have β > 1 when considered a concentrator for any constant α?

3. Consider the decision problem of deciding whether a given bipartite graph is an expander. Show that this is in co-NP.

4. Estimate the values for which the construction will give an expander with probability at least 0.99.

5. In circuit switched routing, an edge disjoint path has to be allocated for every origin destination pair. In this problem we will consider the permutation routing problem, but in this circuit switched model.

Suppose given an permutation on N elements, a network is said to have capacity M if it can find paths for some M of the N source destination pairs. The capacity can be different if we allow path computation to be off-line, or if we require that the path computation happen in an on-line manner (i.e. the messages move forward from the source towards the destinations, and we count how many survive till the end in the worst case)

As an example, for the off-line model, we know that the Benes network has capacity N, since it is possible to find paths for all N source-destination pairs (assuming permutations).

(a) What is the off-line capacity of the multibutterfly network? Give a lower bound in terms of alpha, beta, etc.

(b) What is the off-line capacity of the Butterfly network?

References

[1] S. Arora, T. Leighton, and B. Maggs. On-line algorithms for path selection in a nonblocking network. In Proceedings of the ACM Annual Symposium on Theory of Computing, pages 149–158, May 1990.

[2] F. T. Leighton and B. M. Maggs. Fast algorithms for routing around faults in multibutterflies and randomly-wired splitter networks. IEEE Transactions on Computers, 41(5):578–587, May 1992.

[3] A. Lubotzky, R. Phillips, and P. Sarnak. Ramanujan graphs. Combinatorica, 8:261–277, 1988.

[4] E. Upfal. An O(log N) deterministic packet routing scheme. In Proceedings of the ACM Annual Symposium on Theory of Computing, pages 241–250, May 1989.