next up previous
Next: 4.2 Counterexample for various Up: 4 Counterexamples to on-line Previous: 4 Counterexamples to on-line

4.1 Counterexample for routing on leveled networks

In the first example, we examine a routing strategy for scheduling packets on leveled networks from [6, 8, 9]. A leveled network is a network whose switches can be partitioned into sets or levels labeled with integers so that every edge goes from a switch in some level i to a switch in the next level i+1. The depth of the network is the maximum distance between two switches.

The routing strategy consists of randomly choosing ranks for the packets to be routed and using this value as a priority in a very strong manner; all the packets that use a switch must use it in order of rank. That is, the lowest ranked packet that uses the switch passes through the switch first, then the second lowest ranked packet passes through the switch and so on. Notice that at some point a packet with some rank may reach a switch before a packet with a lower rank reaches the switch through a different edge. In this case the packet must wait for the lower ranked packet to reach and use the switch before it can use the switch. So in order for a packet to decide if it can use a switch or not it must somehow know what the highest ranked packet that is going to enter the switch through some other edge is. This is achieved through the use of ghost messages. When a packet uses an outgoing edge of a switch it sends a ghost message consisting only of the packet's rank down all the other edges. These messages serve as a lower bound to each of these switches for the rank of any packet coming through this incoming edge, and are appropriately forwarded. Finally, end-of-stream(EOS) messages are used to indicate that no more packets will come from a switch. Thus, a packet is allowed to go if it is the lowest ranked packet on any incoming edge and it has a lower rank than the last ghost that arrived on incoming edges that do not have a packet and have not recieved an EOS message. This strategy is described in more detail in each of [6, 8, 9]. With high probability, it produces a schedule of length tex2html_wrap_inline2106 using constant-size queues for any set of N packets whose paths have congestion c on any bounded-degree leveled network with depth L. For a wide variety of networks (both leveled and non-leveled), this algorithm can be used as a subroutine to derive a routing algorithm that delivers all the packets to their destinations in tex2html_wrap_inline2114 time, with high probability.

In our first example, however, we show that this is not always the case. We describe an N-node leveled network in which a set of packets with congestion and dilation tex2html_wrap_inline2118 requires tex2html_wrap_inline2120 steps to be delivered using the strategy for scheduling packets on leveled networks from [6, 8, 9]. Our example does not contradict the previous analysis of the algorithm, since the network has tex2html_wrap_inline2122 levels. However, it shows that reducing the congestion and dilation below the depth of the network does not necessarily improve the running time.


Proof: The network consists of many disjoint copies of the subnetwork pictured in Figure 8. For simplicity, we dispense with the initial queues; the packets originate in edge queues. The subnetwork is composed of tex2html_wrap_inline2134 linear chains of length k, where k shall later be shown to be tex2html_wrap_inline2140 . The second node of each linear chain is connected to the second to last node of the previous chain by a diagonal edge. We assume that at the end of each edge there is a queue that can store 2 packets. Initially, the queue into the first node of each chain contains an end-of-stream (EOS) signal and one packet, and the queue into the second node contains two packets. A packet's destination is the last node in the previous chain. Each packet takes the diagonal edge to the previous chain and then the last edge in the chain. Thus, the length of the longest path is d=3. However, the depth of this subnetwork or any number of disjoint copies of this subnetwork is tex2html_wrap_inline2146 . That is, there are at least tex2html_wrap_inline2148 levels in this network. We now proceed by showing that the time for routing can be tex2html_wrap_inline2150 .

Figure 8: Example 1.

When the ranks tex2html_wrap_inline2152 of the packets tex2html_wrap_inline2154 are chosen so that tex2html_wrap_inline2156 for tex2html_wrap_inline2158 , packet tex2html_wrap_inline2160 requires tex2html_wrap_inline2162 steps to reach its destination. The scenario unfolds as follows. Packets tex2html_wrap_inline2164 and tex2html_wrap_inline2166 take a diagonal edge in the first two steps. These packets cannot advance until the EOS reaches the end of the first chain, in step k. Thus tex2html_wrap_inline2170 remains in the previous queue until step k. In the meantime, ghosts with ranks tex2html_wrap_inline2174 , tex2html_wrap_inline2176 , and tex2html_wrap_inline2178 , travel down the second chain, but packet tex2html_wrap_inline2180 blocks an EOS signal from traveling down the chain. Packets tex2html_wrap_inline2182 and tex2html_wrap_inline2184 move out of their chain and must wait for this EOS signal. They cannot advance until step 2k. So tex2html_wrap_inline2188 cannot move out of its chain and let the EOS signal behind it through until this step, so tex2html_wrap_inline2190 cannot move out of its chain until step 3k and so on. In this fashion, a delay of tex2html_wrap_inline2194 is propagated down to packet tex2html_wrap_inline2196 .

A simple calculation reveals that the probability that tex2html_wrap_inline2198 for tex2html_wrap_inline2200 is tex2html_wrap_inline2202 . Thus, if we have tex2html_wrap_inline2204 copies of the subnetwork, we expect the ranks of the packets to be sorted in one of them. For the total number of nodes in the network to be N, we need tex2html_wrap_inline2208 . In this case, we expect some packet to be delayed tex2html_wrap_inline2210 steps in one copy of the subnetwork.

to .667emto .667em

It is somewhat unfair to say that the optimal schedule for this example has length tex2html_wrap_inline2212 , since ghosts and EOS signals must travel a distance of tex2html_wrap_inline2214 . However, even if the EOS signals are replaced by packets with equivalent ranks, the dilation is only tex2html_wrap_inline2216 , and thus the optimum schedule has length tex2html_wrap_inline2218 .

next up previous
Next: 4.2 Counterexample for various Up: 4 Counterexamples to on-line Previous: 4 Counterexamples to on-line

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