On the Impact of Link Scheduling on End-to-End Delays in Large Networks
Authors:
- 21 April 2011
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Journal on Selected Areas in Communications
- Vol. 29 (5) , 1009-1020
Abstract
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.Keywords
This publication has 20 references indexed in Scilit:
- Closed-form analysis of end-to-end network delay with Markov-modulated Poisson and fluid trafficComputer Communications, 2009
- A Network Calculus With Effective BandwidthIEEE/ACM Transactions on Networking, 2007
- A survey of envelope processes and their applications in quality of service provisioningIEEE Communications Surveys & Tutorials, 2006
- Scaling properties of statistical end-to-end bounds in the network calculusIEEE Transactions on Information Theory, 2006
- Delay bounds for FIFO aggregates: a case studyComputer Communications, 2005
- Coordinated multihop scheduling: a framework for end-to-end servicesIEEE/ACM Transactions on Networking, 2002
- Network Calculus2001
- Statistical service assurances for traffic scheduling algorithmsIEEE Journal on Selected Areas in Communications, 2000
- Efficient network QoS provisioning based on per node traffic shapingIEEE/ACM Transactions on Networking, 1996
- Exact admission control for networks with a bounded delay serviceIEEE/ACM Transactions on Networking, 1996