In this section we apply the scheduling algorithm from
Section 2 to route *N* packets in steps on an *N*-node butterfly using constant size queues. We
essentially duplicate the result of Ranade [29], but the
proof is simpler.

In a *butterfly network*, each node has a distinct label , where *l* is its level and *r* is its row. In an
*n*-input butterfly, *l* is an integer between *0* and , and
*r* is a -bit binary number. The nodes on level *0* and are called the inputs and outputs, respectively. Thus, an
*n*-input butterfly has nodes. For , a
node labeled is connected to nodes and , where
denotes *r* with the *l*th bit complemented. An 8-input butterfly
network is illustrated in Figure 3. Sometimes the
input and output nodes in each row are identified as the same node.
In this case the number of nodes is . The butterfly has
several natural recursive decompositions. For example, removing the
nodes on level *0* (or and their incident edges leaves two
-input subbutterflies.

**Figure 3:** An *8*-input butterfly
network. Each node has a level number between *0* and *3*, and a
*3*-bit row number. A node on level *l* in row *r* is connected to
the nodes on level *l+1* in rows *r* and , where where
denotes *r* with the *l*th bit complemented.

**Proof:**

Routing is performed on a logical network consisting of levels. The first levels of the logical network are linear arrays. The packets originate in these arrays, one to a node. Levels through form a butterfly network. Levels through consist of a butterfly with its levels reversed. The last levels are again linear arrays. Each packet has its destination in one of the arrays spanning levels to . Packets with the same destination are combined. The butterfly simulates each step of this logical network in a constant number of steps. Paths for the packets are selected using Valiant's paradigm; each packet travels to a random intermediate destination on level before moving on to its final destination. This strategy ensures that with high probability, say at least , where is a constant, the congestion is . Since the paths are chosen independently of the ranks for the packets, the scheduling algorithm can treat the paths as if they were fixed. Assuming that the paths have congestion , by Theorem 2.9 the scheduling algorithm delivers all of the packets in steps, with high probability, say at least . Thus, the probability that either the congestion is too large or that the scheduling algorithm takes too long to deliver the packets is at most .

to .667emto .667em

**Proof:**
If each input sends a single packet, the congestion will be
, with high probability. Given paths with
congestion , by Theorem 2.9
the delay is , with high probability.

to .667emto .667em

Mon Jul 22 22:57:44 EDT 1996