The second example is quite general. It shows that for any
deterministic strategy that chooses the order in which packets pass
through a switch independent of the future paths of the packets, there
is a network and a set of paths with congestion *c* and dilation *d*
for which the schedule produced has length at least .
This observation covers strategies such as giving priority to the
packet that has spent the most (or least) time waiting in queues, and
giving priority to the packet that arrives first at a switch. The
network is a complete binary tree of height *d-1* with an *
auxiliary edge* from the root to an *auxiliary node*.

**Proof:** We construct the example for congestion *c* and dilation *d*,
, recursively. The base case is the example .
Each of the *c* leaves sends a packet to the auxiliary node, causing
congestion *c* in the auxiliary edge. The network for
contains *c* copies of the network for , as shown in
Figure 9. First, the auxiliary nodes for these copies
are paired up and merged so that there are auxiliary nodes each
with two auxiliary edges into it. Next, the auxiliary nodes become
the leaves of a complete binary tree of height with its own
auxiliary node and edge. For each copy of , the
deterministic scheduling strategy chooses some packet to cross its
auxiliary edge last. We extend the path of this packet so that it
traverses the auxiliary edge in . The dilation of the new set
of paths is *d* and the congestion *c*. The length of the schedule,
, is given by the recurrence

and has solution . Setting in this example gives a routing time of .

to .667emto .667em

The previous example can be modified to show that the strategies of sending the packet with the farthest distance left to go or the packet with the farthest total initial distance to go first can also be made to require time. We simply extend the paths of the packets winning at each switch so that they have total (or remaining) distance equal to or greater than the packets that lose at a switch.

Mon Jul 22 20:27:47 EDT 1996