In the first example, we examine a routing strategy for scheduling packets on leveled networks from [6, 8, 9]. A leveled network is a network whose switches can be partitioned into sets or levels labeled with integers so that every edge goes from a switch in some level i to a switch in the next level i+1. The depth of the network is the maximum distance between two switches.
The routing strategy consists of randomly choosing ranks for the packets to be routed and using this value as a priority in a very strong manner; all the packets that use a switch must use it in order of rank. That is, the lowest ranked packet that uses the switch passes through the switch first, then the second lowest ranked packet passes through the switch and so on. Notice that at some point a packet with some rank may reach a switch before a packet with a lower rank reaches the switch through a different edge. In this case the packet must wait for the lower ranked packet to reach and use the switch before it can use the switch. So in order for a packet to decide if it can use a switch or not it must somehow know what the highest ranked packet that is going to enter the switch through some other edge is. This is achieved through the use of ghost messages. When a packet uses an outgoing edge of a switch it sends a ghost message consisting only of the packet's rank down all the other edges. These messages serve as a lower bound to each of these switches for the rank of any packet coming through this incoming edge, and are appropriately forwarded. Finally, end-of-stream(EOS) messages are used to indicate that no more packets will come from a switch. Thus, a packet is allowed to go if it is the lowest ranked packet on any incoming edge and it has a lower rank than the last ghost that arrived on incoming edges that do not have a packet and have not recieved an EOS message. This strategy is described in more detail in each of [6, 8, 9]. With high probability, it produces a schedule of length using constant-size queues for any set of N packets whose paths have congestion c on any bounded-degree leveled network with depth L. For a wide variety of networks (both leveled and non-leveled), this algorithm can be used as a subroutine to derive a routing algorithm that delivers all the packets to their destinations in time, with high probability.
In our first example, however, we show that this is not always the case. We describe an N-node leveled network in which a set of packets with congestion and dilation requires steps to be delivered using the strategy for scheduling packets on leveled networks from [6, 8, 9]. Our example does not contradict the previous analysis of the algorithm, since the network has levels. However, it shows that reducing the congestion and dilation below the depth of the network does not necessarily improve the running time.
Proof: The network consists of many disjoint copies of the subnetwork pictured in Figure 8. For simplicity, we dispense with the initial queues; the packets originate in edge queues. The subnetwork is composed of linear chains of length k, where k shall later be shown to be . The second node of each linear chain is connected to the second to last node of the previous chain by a diagonal edge. We assume that at the end of each edge there is a queue that can store 2 packets. Initially, the queue into the first node of each chain contains an end-of-stream (EOS) signal and one packet, and the queue into the second node contains two packets. A packet's destination is the last node in the previous chain. Each packet takes the diagonal edge to the previous chain and then the last edge in the chain. Thus, the length of the longest path is d=3. However, the depth of this subnetwork or any number of disjoint copies of this subnetwork is . That is, there are at least levels in this network. We now proceed by showing that the time for routing can be .
Figure 8: Example 1.
When the ranks of the packets are chosen so that for , packet requires steps to reach its destination. The scenario unfolds as follows. Packets and take a diagonal edge in the first two steps. These packets cannot advance until the EOS reaches the end of the first chain, in step k. Thus remains in the previous queue until step k. In the meantime, ghosts with ranks , , and , travel down the second chain, but packet blocks an EOS signal from traveling down the chain. Packets and move out of their chain and must wait for this EOS signal. They cannot advance until step 2k. So cannot move out of its chain and let the EOS signal behind it through until this step, so cannot move out of its chain until step 3k and so on. In this fashion, a delay of is propagated down to packet .
A simple calculation reveals that the probability that for is . Thus, if we have copies of the subnetwork, we expect the ranks of the packets to be sorted in one of them. For the total number of nodes in the network to be N, we need . In this case, we expect some packet to be delayed steps in one copy of the subnetwork.
It is somewhat unfair to say that the optimal schedule for this example has length , since ghosts and EOS signals must travel a distance of . However, even if the EOS signals are replaced by packets with equivalent ranks, the dilation is only , and thus the optimum schedule has length .