Lingering issues in distributed scheduling

DOI10.1007/S11134-014-9404-ZzbMATH Open1309.68024arXiv1302.2824OpenAlexW2156939316MaRDI QIDQ475112FDOQ475112

Authors: Florian Simatos, Sem Borst, Niek Bouman 

Publication date: 25 November 2014

Published in: Queueing Systems (Search for Journal in Brave)

Abstract: 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.

Full work available at URL: https://arxiv.org/abs/1302.2824

Recommendations

• Delay performance in random-access networks
• Stability and delay of distributed scheduling algorithms for networks of conflicting queues
• Distributed link scheduling in wireless networks
• Dynamic Distributed Scheduling in Random Access Networks
• Queue-based random-access algorithms: fluid limits and stability issues

zbMATH Keywords

wireless networksdelay performancedistributed scheduling algorithmsheavy traffic scaling

Mathematics Subject Classification ID

Queues and service in operations research (90B22) Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Communication networks in operations research (90B18)

Cites Work

• MaxWeight scheduling in a generalized switch: State space collapse and workload minimization in heavy traffic
• Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks
• Polling systems with zero switchover times: A heavy-traffic averaging principle
• Dynamic server allocation to parallel queues with randomly varying connectivity
• A Limit Theorem for a Branching Process with State-Dependent Immigration
• Polling systems and multitype branching processes
• DELAYS AT SIGNALIZED INTERSECTIONS WITH EXHAUSTIVE TRAFFIC CONTROL
• Randomized scheduling algorithm for queueing networks
• Validity of heavy traffic steady-state approximations in generalized Jackson networks
• Resource Allocation and Cross-Layer Control in Wireless Networks
• Distributed Random Access Algorithm: Scheduling and Congestion Control
• Switched networks with maximum weight policies: fluid approximation and multiplicative state space collapse
• Fast Mixing of Parallel Glauber Dynamics and Low-Delay CSMA Scheduling
• Stability and delay of distributed scheduling algorithms for networks of conflicting queues
• Hardness of Low Delay Network Scheduling
• Queue-based random-access algorithms: fluid limits and stability issues
• Joint congestion control and distributed scheduling for throughput guarantees in wireless networks
• Lingering issues in distributed scheduling
• Stable Scheduling Policies for Maximizing Throughput in Generalized Constrained Queueing Systems
• Medium Access Using Queues

Cited In (4)

• Fluid limits for QB-CSMA with polynomial rates, homogenization and reflection
• Lingering issues in distributed scheduling
• Induced idleness leads to deterministic heavy traffic limits for queue-based random-access algorithms
• Distributed link scheduling in wireless networks

This page was built for publication: Lingering issues in distributed scheduling

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q475112)