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.

to .667emto .667em

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

to .667emto .667em

**Proof:**

The path has *f* forward edges. Since it goes back at most
*L* levels, its total length is at most .

to .667emto .667em

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.

to .667emto .667em

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

to .667emto .667em

Mon Jul 22 22:57:44 EDT 1996