Does Link Scheduling Matter on Long Paths?
Jörg Liebeherr, Yashar Ghiassi-Farrokhfal, Almut Burchard · 2010
We seek to provide an analytical answer whether the impact of the selection of link scheduling algorithms diminishes on long network paths. The answer is provided through a detailed multi-node delay analysis, which is applicable to a broad class of scheduling algorithms, and which can account for statistical multiplexing. The analysis is enabled by two contributions: (1) We derive a function that can characterize the available bandwidth at a node for various scheduling algorithms. The function has an accuracy that recovers necessary and sufficient conditions for satisfying worst-case delay bounds at a single node, (2) We obtain end-to-end delay bounds by providing an explicit solution to an optimization problem, in which the service received at multiple nodes is subsumed into a single function. By presenting a unified analysis that captures the properties of a broad group of schedulers in a single parameter, we can provide insight how the choice of scheduling algorithms impacts end-to-end delay bounds. An important finding of this paper is that some schedulers show noticeable performance differences which persist in a network setting with long paths.