TY - GEN
T1 - Lingering issues in distributed scheduling
AU - Simatos, F.
AU - Bouman, N.
AU - Borst, S.C.
PY - 2013
Y1 - 2013
N2 - Recent advances have resulted in queue-based algorithms for medium access control which operate in a distributed fashion, and yet achieve the optimal throughput performance of centralized scheduling algorithms. However, fundamental performance bounds reveal that the "cautious" activation rules involved in establishing throughput optimality tend to produce extremely large delays, typically growing exponentially in 1/(1-r), with r the load of the system, in contrast to the usual linear growth. Motivated by that issue, we explore to what extent more "aggressive" schemes can improve the delay performance. Our main finding is that aggressive activation rules induce a lingering effect, where individual nodes retain possession of a shared resource for excessive lengths of time even while a majority of other nodes idle. Using central limit theorem type arguments, we prove that the idleness induced by the lingering effect may cause the delays to grow with 1/(1-r) at a quadratic rate. To the best of our knowledge, these are the first mathematical results illuminating the lingering effect and quantifying the performance impact.
In addition extensive simulation experiments are conducted to illustrate and validate the various analytical results.
AB - Recent advances have resulted in queue-based algorithms for medium access control which operate in a distributed fashion, and yet achieve the optimal throughput performance of centralized scheduling algorithms. However, fundamental performance bounds reveal that the "cautious" activation rules involved in establishing throughput optimality tend to produce extremely large delays, typically growing exponentially in 1/(1-r), with r the load of the system, in contrast to the usual linear growth. Motivated by that issue, we explore to what extent more "aggressive" schemes can improve the delay performance. Our main finding is that aggressive activation rules induce a lingering effect, where individual nodes retain possession of a shared resource for excessive lengths of time even while a majority of other nodes idle. Using central limit theorem type arguments, we prove that the idleness induced by the lingering effect may cause the delays to grow with 1/(1-r) at a quadratic rate. To the best of our knowledge, these are the first mathematical results illuminating the lingering effect and quantifying the performance impact.
In addition extensive simulation experiments are conducted to illustrate and validate the various analytical results.
U2 - 10.1145/2465529.2465758
DO - 10.1145/2465529.2465758
M3 - Conference contribution
T3 - ACM SIGMETRICS Performance Evaluation Review
SP - 141
EP - 152
BT - ACM Sigmetrics International Conference on Measurement and Modeling of Computer Systems (SIGMETRICS'13, Pittsburgh PA, USA, June 17-21, 2013)
PB - Association for Computing Machinery, Inc
CY - New York NY
ER -