   Next: 5 Routing on shuffle-exchange Up: Randomized Routing and Sorting Previous: 3 Routing on meshes

# 4 Routing on butterflies

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 , 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 lth 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 lth 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   Next: 5 Routing on shuffle-exchange Up: Randomized Routing and Sorting Previous: 3 Routing on meshes

Bruce Maggs
Mon Jul 22 22:57:44 EDT 1996