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 .