Next: 5.4 Packets from bad Up: 5 Routing on shuffle-exchange Previous: 5.2 A leveled network

5.3 Path selection and congestion

For each packet we choose its path by uniformly choosing a random good necklace for it to route through before it goes to its final destination. So the path for a packet consists of a path through L to the node on level 0 of its necklace, a path through to its random intermediate necklace, a path through the second to its destination necklace, and a path through the second L to the proper node of its destination necklace.

The following lemma shows that if at most packets originate and terminate in each good necklace, then this method yields paths with congestion with high probability.

Proof: We observe that for the paths in the copies of L, we have congestion at most , since at most packets start or end in any good necklace. By symmetry we claim that the analysis of the path portions in both copies of is the same. Finally we recall that in , we route packets going to intermediate destination necklaces with fewer 0's straight across (i.e, without using any flip edges) in network A. Thus, the congestion of the straight across paths in A is at most . Also, we route packets going to intermediate necklaces with the same or more 0's straight across in network . We will show that any intermediate necklace gets packets with high probability, so the straight across portion of the paths in will have congestion. To finish, we analyze the congestion in network A due to packets routing to intermediate necklaces with the same or more 0's, and claim that the arguments will hold by symmetry for .

Consider a shuffle or flip edge e in the first copy of network A. Suppose that e traverses levels m and m+1. Let x be the length of the longest string of 0's in the necklace to which e goes. If m < x, then e must be a shuffle edge and no packet from any other necklace can use e, since we only map to a necklace via flip edges after its longest string of 0's. Otherwise ( ) we consider the number of packets from other necklaces that can use e. We know that only packets from at most other necklaces with can use e since at most l bits can change by level m+1 (there are no flip edges in the first levels of any necklace). Thus the number of packets that can use e is at most since each necklace starts with at most packets. The probability that a specific packet uses e is the number of necklaces that can be reached using e, at most (i.e., necklaces that match e's necklace in the first bits), divided by the total number of good necklaces, at least , which is just .

The probability that more than packets use e is at most

since there are Bernoulli trials, each succeeding with probability . The probability that any of the edges of this stage has congestion more than is times this probability. Using the inequality , for any we can bound the product by by choosing large enough.

to .667emto .667em

Because the congestion and number of levels are , with high probability, the time to route the packets between the good nodes is also , with high probability, and the queue size is constant.

Next: 5.4 Packets from bad Up: 5 Routing on shuffle-exchange Previous: 5.2 A leveled network

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