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