Next: 4.3 Counterexample to a Up: 4 Counterexamples to on-line Previous: 4.1 Counterexample for routing

## 4.2 Counterexample for various deterministic strategies

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

Figure 9: Example 2.

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.

Next: 4.3 Counterexample to a Up: 4 Counterexamples to on-line Previous: 4.1 Counterexample for routing

Bruce Maggs
Mon Jul 22 20:27:47 EDT 1996