We seek to provide an analytical answer whether the impact of link scheduling algorithms on end-to-end delays diminishes on long network paths. The answer is provided through a detailed multi-hop 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 buffered link for various scheduling algorithms. This characterization is sharp enough to provide necessary and sufficient conditions for satisfying worst-case delay bounds at a single link; (2) We obtain end-to-end delay bounds by solving an optimization problem, in which the service received on a multi-hop path is subsumed into a single function. Since our analysis captures the properties of a broad group of schedulers in a single parameter, it can provide insight how the choice of scheduling algorithms impacts end-to-end delay bounds. An important finding of this paper is that schedulers may exhibit noticeable performance differences which persist in a network setting with long paths.

, , ,
doi.org/ 10.1109/JSAC.2011.110511, hdl.handle.net/1765/79422
IEEE journal on Selected Areas in Communication
Rotterdam School of Management (RSM), Erasmus University

Liebeherr, J., Ghiassi-Farrokhfal, Y., & Burchard, A. (2011). On the impact of link scheduling on end-to-end delays in large networks. In IEEE journal on Selected Areas in Communication (Vol. 29, pp. 1009–1020). doi: 10.1109/JSAC.2011.110511