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.

to .667emto .667em

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 .

Mon Jul 22 20:27:47 EDT 1996