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