Lingering issues in distributed scheduling
From MaRDI portal
Publication:475112
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.
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
Cites work
- A Limit Theorem for a Branching Process with State-Dependent Immigration
- Delays at signalized intersections with exhaustive traffic control
- Distributed Random Access Algorithm: Scheduling and Congestion Control
- Dynamic server allocation to parallel queues with randomly varying connectivity
- Fast Mixing of Parallel Glauber Dynamics and Low-Delay CSMA Scheduling
- Hardness of Low Delay Network Scheduling
- Joint congestion control and distributed scheduling for throughput guarantees in wireless networks
- Lingering issues in distributed scheduling
- MaxWeight scheduling in a generalized switch: State space collapse and workload minimization in heavy traffic
- Medium Access Using Queues
- Polling systems and multitype branching processes
- Polling systems with zero switchover times: A heavy-traffic averaging principle
- Queue-based random-access algorithms: fluid limits and stability issues
- Randomized scheduling algorithm for queueing networks
- Resource Allocation and Cross-Layer Control in Wireless Networks
- Stability and delay of distributed scheduling algorithms for networks of conflicting queues
- Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks
- Stable Scheduling Policies for Maximizing Throughput in Generalized Constrained Queueing Systems
- Switched networks with maximum weight policies: fluid approximation and multiplicative state space collapse
- Validity of heavy traffic steady-state approximations in generalized Jackson networks
Cited in
(6)- Fluid limits for QB-CSMA with polynomial rates, homogenization and reflection
- On distributed scheduling with heterogeneously delayed network-state information
- Distributed link scheduling in wireless networks
- Delay performance in random-access networks
- Lingering issues in distributed scheduling
- Induced idleness leads to deterministic heavy traffic limits for queue-based random-access algorithms
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)
