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.
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.
