Our analysis of the algorithm uses a delay sequence argument similar
to the ones in [2], [29], and [36].
Each delay sequence corresponds to an event in the probability space.
We first show that if some packet is delayed, then a delay sequence
occurs. Then by counting all possible delay sequences, we show that
it is unlikely that any delay sequence occurs with delay greater than
.
The only use of randomness in the algorithm is in the choice of ranks
for the packets. Thus, the probability space consists of 
equally likely elementary outcomes, one for each possible setting of
the ranks. Each delay sequence corresponds to the event in the
probability space in which the rank chosen for packet 
is 
,
for 
. Each such event consists of 
elementary outcomes and occurs with probability
. We call these events bad events. We
say that a delay sequence occurs whenever the corresponding bad event
occurs. The following lemma shows that whenever the routing takes too
long, some delay sequence occurs.
The informal idea behind the proof is that whenever routing takes too
long, we can identify a sequence of packets 
, 
, that are in some sense responsible. We will show that the first
w elements of this sequence, i.e., 
are the packets
on an 
delay sequence that has occurred.
We first present an incremental construction to identify the packets
. We will use auxiliary sequences
and 
to facilitate the
discussion. The sequence starts with 
being the last packet
delivered and 
being the step at which 
reached its
destination.
In general, given 
and 
, we show how the sequence can
be extended. If 
is not a ghost, then we set 
. If
is a ghost, then we follow 
back in time until reaching
the node in which 
was created from some 
. In either case
we next follow 
back until time 
when it was forced to wait
in some node 
. The next packet in the sequence is identified by
using Lemma 2.3. If 
was m-delayed by 
in 
, we set 
. Suppose 
was f-delayed by
in 
, where 
has
the largest rank and 
has the smallest. Then we set
, 
and 
for 
, and 
. If some queue in
was empty at 
, or if 
we terminate the construction.
The incremental construction extends each sequence by 1 element, or by
q elements, depending upon whether there was a m-delay or a f-delay.
We apply the construction until a total of 
f-delays are
encountered, or the construction terminates. Let j denote the
number of incremental steps used, of which 
involve
f-delays, and the remaining j-f involve m delays.
The key observation is that each time a new packet is added to the delay sequence, the lag of the packet being followed back in time is reduced by either one or two.
Proof:
Since there is no waiting between 
and 
, we
get 
. But since 
waits at
, we have 
.
For m-delays, we know that 
and 
are in the same node
at 
, and hence must have identical lags. For f-delays, we get
, since 
is on the next
level.
Proof:
Suppose 
. We know that each f-delay adds q
elements to the sequence, and thus 
. Otherwise, we
have 
, and we know that the construction was terminated because
at the last step there was neither an f-delay nor an m-delay, but some
queue was found empty, or 
. We know that 
, and by Lemma 2.3, 
. Thus, 
.
By applying Lemma 2.6 j times we get
. Thus 
. But 
.
Proof:
The path has f forward edges. Since it goes back at most
L levels, its total length is at most 
.
We now prove Lemma 2.5.
Proof of Lemma 2.5: The nodes and the
packets belonging to the delay sequence are obtained by taking the
first w elements of the sequences 
and
. The sequence of ranks is
. This is in decreasing order by
construction. The delay path is obtained from
Lemma 2.8. This has length at most 
as
required. To complete the proof we observe that all 
must be
real packets, i.e., not EOS or ghost packets, since they delay other
packets as well as wait in queues.
Proof:
By Lemma 2.5, to bound the probability that
some packet is delayed w steps, it suffices to bound the probability
that some 
-delay sequence occurs. We begin by counting
the number of 
-delay sequences. The delay path can
start on any packet's path. Since there are N packets and each
follows a path of length at most L, there are at most 
possible starting points. At each node on the path, there are at
most 
choices for the next node on the path. Thus, the
number of paths is at most 
. The number of
ways of locating the nodes 
on the path is at
most 
. The number of ways of choosing the packets 
such that for 
, packet 
passes through node 
is at most
. The number of ways of choosing ranks 
such that 
for 
and
for 
is at most 
. Each of these delay sequences occurs with probability at most
. Hence, the probability that any delay sequence occurs is at
most
Using the inequality 
to bound 
and the inequalities 
and
to bound 
, the probability is at most
Observing that
and factoring 
out of the first factor, our upper bound becomes
If 
, then for any 
, there is a
such that for 
, the probability is at most
. If 
, then for any 
, there is a
such that 
and 
,
and for any 
, the probability is at most 
.
