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 .