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.

Mon Jul 22 22:57:44 EDT 1996