The scheduling algorithm is similar to the one in [29]
except that instead of ordering the packets based on destination
address, we order them according to randomly-chosen ranks. In
particular, each packet is assigned an integer rank chosen randomly,
independently, and uniformly from the range 
, where R will be
specified later. The ranks are used by the algorithm to determine the
order in which packets move through each node. The algorithm
maintains two important invariants. First, throughout the execution
of the algorithm, the packets in each edge queue are arranged from
head to tail in order of increasing rank. Second, a packet is routed
through a node only after all the other packets with lower ranks that
must pass through the node have done so. Special ghost
packets are used to help the algorithm maintain these invariants.
The algorithm begins with an initialization phase in which the packets in each initial queue are sorted according to their ranks. Ties in rank are broken according to destination address. At the tail of each initial queue a special end-of-stream (EOS) packet is inserted, and is assigned rank R+1.
After initialization, the algorithm operates as follows. At each step, a node examines the head of its initial queue and the heads of any edge queues into the node. If any of these queues are empty, then the node does nothing. Otherwise, it selects the packet with the smallest rank as a candidate to be transmitted. Ties are again broken using the destination address. The selected packet is sent forward only if the queue at the head of the next edge on its path contained fewer than q packets at the beginning of the step. (We assume that the nodes at both the head and tail of an edge can determine how many packets are stored in the edge's queue in constant time.) Thus, an edge queue is guaranteed never to hold more than q packets.
To prevent queues from becoming empty, whenever a node selects a packet for transmission, it sends a ghost packet with the same rank on each of the other edges out of the node, provided that their edge queues contained fewer than q packets at the beginning of the step. Because the node sends packets out in order of strictly increasing rank, the rank of the ghost packet provides the receiving node with a lower bound on the ranks of the packets that it will receive on the same edge in the future.
Like other packets, a ghost packet can be selected for transmission if it is at the head of its queue and has a smaller rank than the ranks of packets in all of the other queues. A ghost never remains at a node for more than one step, however. At the end of each step a node destroys any ghosts that were present in its edge queues at the beginning of the step.
End-of-stream (EOS) packets are also given special treatment. Since an EOS packet has rank R+1, it cannot be selected by a node unless there is an EOS packet at the head of the node's initial queue and at the head of each of the queues on all of the node's incoming edges. Once an EOS packet has been selected, the node will create a new EOS packet for each of its outgoing edges and for each edge will attempt to send the corresponding packet at each step until it succeeds. After sending an EOS packet along an edge, a node will not send any more packets along that edge.
Figure 1 shows an example in which a ghost packet expedites the delivery of another packet. For simplicity, initial and final queues are not shown. The next edge on the path for the packet with rank 35 is the upper edge out of node A. By sending a ghost with rank 35 on the lower edge, node A informs node B that subsequent packets will not have rank smaller than 35. Node B can then transmit the packet with rank 25 on the next step. Without the ghost packet, the transmission of the packet with rank 25 would be delayed until a packet actually arrived at the top queue of node B.
Figure 1: A ghost with rank 35 expedites the delivery of a packet with rank 25.
In the manner of [29], we summarize the properties of the routing algorithm in the following lemmas.
Proof: The proof is by induction on the number of steps executed by the algorithm.
Proof: The proof is by induction on the number of steps executed by the algorithm.
In the following lemma we denote the rank of a packet p by
, and the level of a node s by 
.
Proof: Straightforward.
It is useful to define the lag of a packet p at node s at
time t as 
. The lag gives a lower bound on
the amount of time the packet has waited in queues before step t.
