Average-Case Analysis of Greedy Packet Scheduling
Zvi Lotker & Boaz Patt-Shamir
To appear at Nineteenth Annual
ACM SIGACT-SIGOPS Symposium on PRINCIPLES OF DISTRIBUTED COMPUTING (PODC
2000), Portland, Oregon, 16-19 July 2000
Abstract
We study the average number of delays suffered by packets routed using
greedy (work conserving) scheduling policies. We obtain tight bounds on
the worst-case average number of delays in a few cases as follows. First,
we show that the average number of delays is a function of the number of
sources of packets, which is interesting in case a node may send many packets.
Then, using a new concept we call \emph{delay race}, we prove a tight bound
on the average number of delays in a leveled graph. Finally, using delay
races in a more involved way, we prove nearly-tight bounds on the average
number of delays in directed acyclic graphs (DAGs). The upper bound for
DAGs is expressed in terms of the underlying topology, and as a result
it holds for any acyclic set of routes, even if they are not shortest paths.
The lower bound for DAGs, on the other hand, holds even for shortest paths
routes.