next up previous
Next: 2.3.1 Packet combining Up: 2 An scheduling algorithm Previous: 2.2 The algorithm

2.3 Analysis

Our analysis of the algorithm uses a delay sequence argument similar to the ones in [2], [29], and [36]. Each delay sequence corresponds to an event in the probability space. We first show that if some packet is delayed, then a delay sequence occurs. Then by counting all possible delay sequences, we show that it is unlikely that any delay sequence occurs with delay greater than tex2html_wrap_inline2153 .


The only use of randomness in the algorithm is in the choice of ranks for the packets. Thus, the probability space consists of tex2html_wrap_inline2175 equally likely elementary outcomes, one for each possible setting of the ranks. Each delay sequence corresponds to the event in the probability space in which the rank chosen for packet tex2html_wrap_inline2177 is tex2html_wrap_inline2179 , for tex2html_wrap_inline2181 . Each such event consists of tex2html_wrap_inline2183 elementary outcomes and occurs with probability tex2html_wrap_inline2185 . We call these events bad events. We say that a delay sequence occurs whenever the corresponding bad event occurs. The following lemma shows that whenever the routing takes too long, some delay sequence occurs.


The informal idea behind the proof is that whenever routing takes too long, we can identify a sequence of packets tex2html_wrap_inline2193 , tex2html_wrap_inline2195 , that are in some sense responsible. We will show that the first w elements of this sequence, i.e., tex2html_wrap_inline2199 are the packets on an tex2html_wrap_inline2201 delay sequence that has occurred.

We first present an incremental construction to identify the packets tex2html_wrap_inline2203 . We will use auxiliary sequences tex2html_wrap_inline2205 and tex2html_wrap_inline2207 to facilitate the discussion. The sequence starts with tex2html_wrap_inline2209 being the last packet delivered and tex2html_wrap_inline2211 being the step at which tex2html_wrap_inline2213 reached its destination.

In general, given tex2html_wrap_inline2215 and tex2html_wrap_inline2217 , we show how the sequence can be extended. If tex2html_wrap_inline2219 is not a ghost, then we set tex2html_wrap_inline2221 . If tex2html_wrap_inline2223 is a ghost, then we follow tex2html_wrap_inline2225 back in time until reaching the node in which tex2html_wrap_inline2227 was created from some tex2html_wrap_inline2229 . In either case we next follow tex2html_wrap_inline2231 back until time tex2html_wrap_inline2233 when it was forced to wait in some node tex2html_wrap_inline2235 . The next packet in the sequence is identified by using Lemma 2.3. If tex2html_wrap_inline2237 was m-delayed by tex2html_wrap_inline2239 in tex2html_wrap_inline2241 , we set tex2html_wrap_inline2243 . Suppose tex2html_wrap_inline2245 was f-delayed by tex2html_wrap_inline2247 in tex2html_wrap_inline2249 , where tex2html_wrap_inline2251 has the largest rank and tex2html_wrap_inline2253 has the smallest. Then we set tex2html_wrap_inline2255 , tex2html_wrap_inline2257 and tex2html_wrap_inline2259 for tex2html_wrap_inline2261 , and tex2html_wrap_inline2263 . If some queue in tex2html_wrap_inline2265 was empty at tex2html_wrap_inline2267 , or if tex2html_wrap_inline2269 we terminate the construction.

The incremental construction extends each sequence by 1 element, or by q elements, depending upon whether there was a m-delay or a f-delay. We apply the construction until a total of tex2html_wrap_inline2271 f-delays are encountered, or the construction terminates. Let j denote the number of incremental steps used, of which tex2html_wrap_inline2275 involve f-delays, and the remaining j-f involve m delays.

The key observation is that each time a new packet is added to the delay sequence, the lag of the packet being followed back in time is reduced by either one or two.


Proof: Since there is no waiting between tex2html_wrap_inline2293 and tex2html_wrap_inline2295 , we get tex2html_wrap_inline2297 . But since tex2html_wrap_inline2299 waits at tex2html_wrap_inline2301 , we have tex2html_wrap_inline2303 . For m-delays, we know that tex2html_wrap_inline2305 and tex2html_wrap_inline2307 are in the same node at tex2html_wrap_inline2309 , and hence must have identical lags. For f-delays, we get tex2html_wrap_inline2311 , since tex2html_wrap_inline2313 is on the next level.

to .667emto .667em


Proof: Suppose tex2html_wrap_inline2321 . We know that each f-delay adds q elements to the sequence, and thus tex2html_wrap_inline2325 . Otherwise, we have tex2html_wrap_inline2327 , and we know that the construction was terminated because at the last step there was neither an f-delay nor an m-delay, but some queue was found empty, or tex2html_wrap_inline2329 . We know that tex2html_wrap_inline2331 , and by Lemma 2.3, tex2html_wrap_inline2333 . Thus, tex2html_wrap_inline2335 . By applying Lemma 2.6 j times we get tex2html_wrap_inline2339 . Thus tex2html_wrap_inline2341 . But tex2html_wrap_inline2343 .

to .667emto .667em



The path has f forward edges. Since it goes back at most L levels, its total length is at most tex2html_wrap_inline2361 .

to .667emto .667em

We now prove Lemma 2.5.

Proof of Lemma 2.5: The nodes and the packets belonging to the delay sequence are obtained by taking the first w elements of the sequences tex2html_wrap_inline2365 and tex2html_wrap_inline2367 . The sequence of ranks is tex2html_wrap_inline2369 . This is in decreasing order by construction. The delay path is obtained from Lemma 2.8. This has length at most tex2html_wrap_inline2371 as required. To complete the proof we observe that all tex2html_wrap_inline2373 must be real packets, i.e., not EOS or ghost packets, since they delay other packets as well as wait in queues.

to .667emto .667em


Proof: By Lemma 2.5, to bound the probability that some packet is delayed w steps, it suffices to bound the probability that some tex2html_wrap_inline2389 -delay sequence occurs. We begin by counting the number of tex2html_wrap_inline2391 -delay sequences. The delay path can start on any packet's path. Since there are N packets and each follows a path of length at most L, there are at most tex2html_wrap_inline2397 possible starting points. At each node on the path, there are at most tex2html_wrap_inline2399 choices for the next node on the path. Thus, the number of paths is at most tex2html_wrap_inline2401 . The number of ways of locating the nodes tex2html_wrap_inline2403 on the path is at most tex2html_wrap_inline2405 . The number of ways of choosing the packets tex2html_wrap_inline2407 such that for tex2html_wrap_inline2409 , packet tex2html_wrap_inline2411 passes through node tex2html_wrap_inline2413 is at most tex2html_wrap_inline2415 . The number of ways of choosing ranks tex2html_wrap_inline2417 such that tex2html_wrap_inline2419 for tex2html_wrap_inline2421 and tex2html_wrap_inline2423 for tex2html_wrap_inline2425 is at most tex2html_wrap_inline2427 . Each of these delay sequences occurs with probability at most tex2html_wrap_inline2429 . Hence, the probability that any delay sequence occurs is at most


Using the inequality tex2html_wrap_inline2433 to bound tex2html_wrap_inline2435 and the inequalities tex2html_wrap_inline2437 and tex2html_wrap_inline2439 to bound tex2html_wrap_inline2441 , the probability is at most


Observing that tex2html_wrap_inline2445 and factoring tex2html_wrap_inline2447 out of the first factor, our upper bound becomes


If tex2html_wrap_inline2451 , then for any tex2html_wrap_inline2453 , there is a tex2html_wrap_inline2455 such that for tex2html_wrap_inline2457 , the probability is at most tex2html_wrap_inline2459 . If tex2html_wrap_inline2461 , then for any tex2html_wrap_inline2463 , there is a tex2html_wrap_inline2465 such that tex2html_wrap_inline2467 and tex2html_wrap_inline2469 , and for any tex2html_wrap_inline2471 , the probability is at most tex2html_wrap_inline2473 .

to .667emto .667em

next up previous
Next: 2.3.1 Packet combining Up: 2 An scheduling algorithm Previous: 2.2 The algorithm

Bruce Maggs
Mon Jul 22 22:57:44 EDT 1996