Next: 5 Acknowledgements Up: 4 Counterexamples to on-line Previous: 4.2 Counterexample for various

## 4.3 Counterexample to a randomized strategy

The third example shows that the natural strategy of assigning priorities to the packets at random is not effective either.

Proof: As in Example 1, the network consists of many copies of a subnetwork. Each subnetwork is constructed so that . A subnetwork consists of a linear chain of length d, with loops of length between adjacent nodes (see Figure 10). The packets are broken into groups numbered 0 through of packets each. The packets in group i use the linear chain for steps and then use loops as their path. As in the previous example, we assume that queues have unlimited capacity and that at each step a node can send a single packet.

Figure 10: Example 3.

If the random ranks are assigned so that the packets in group i have smaller ranks than the packets in groups with larger numbers, then the packets in group i delay the packets in group i+1 by steps. Thus the last packet experiences an delay.

Once again the ranks of the packets must have a specific order, which can be shown to happen with high probability given enough copies of the subnetwork. As in Observation 4.1, it is not hard to show this requires .

to .667emto .667em

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