next up previous
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.

  observation422

Proof: As in Example 1, the network consists of many copies of a subnetwork. Each subnetwork is constructed so that tex2html_wrap_inline2284 . A subnetwork consists of a linear chain of length d, with loops of length tex2html_wrap_inline2288 between adjacent nodes (see Figure 10). The packets are broken into tex2html_wrap_inline2290 groups numbered 0 through tex2html_wrap_inline2294 of tex2html_wrap_inline2296 packets each. The packets in group i use the linear chain for tex2html_wrap_inline2300 steps and then use tex2html_wrap_inline2302 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.

   figure433
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 tex2html_wrap_inline2310 steps. Thus the last packet experiences an tex2html_wrap_inline2312 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 tex2html_wrap_inline2314 .


to .667emto .667em



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