Queue-based random-access algorithms: fluid limits and stability issues

DOI10.1214/13-SSY104MaRDI QIDQ2921185zbMATH OpenFDO

Authors Javad Ghaderi, Phil Whiting, Sem Borst

Publication date 7 October 2014

Published in Stochastic Systems (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1302.5945, https://projecteuclid.org/euclid.ssy/1411044993

zbMATH Keywords

fluid limitsstability issuescarrier-sense multiple access (CSMA)queue-based strategies

Mathematics Subject Classification ID

Queues and service in operations research (90B22) Queueing theory (aspects of probability theory) (60K25) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Communication networks in operations research (90B18)

Abstract: We use fluid limits to explore the (in)stability properties of wireless networks with queue-based random-access algorithms. Queue-based random-access schemes are simple and inherently distributed in nature, yet provide the capability to match the optimal throughput performance of centralized scheduling mechanisms in a wide range of scenarios. Unfortunately, the type of activation rules for which throughput optimality has been established, may result in excessive queue lengths and delays. The use of more aggressive/persistent access schemes can improve the delay performance, but does not offer any universal maximum-stability guarantees. In order to gain qualitative insight and investigate the (in)stability properties of more aggressive/persistent activation rules, we examine fluid limits where the dynamics are scaled in space and time. In some situations, the fluid limits have smooth deterministic features and maximum stability is maintained, while in other scenarios they exhibit random oscillatory characteristics, giving rise to major technical challenges. In the latter regime, more aggressive access schemes continue to provide maximum stability in some networks, but may cause instability in others. Simulation experiments are conducted to illustrate and validate the analytical results.

Recommendations

• Fluid approximations for a processor-sharing queue
• Per-queue stability analysis of a random access system
• The fluid limit of a heavily loaded processor sharing queue
• Stable memoryless queuing under contention
• Stability of N interacting queues in random-access systems
• On queueing problems in random-access communications
• The Fluid Limit of an Overloaded Processor Sharing Queue
• On the comparison of queueing systems with their fluid limits

Cites work

• scientific article; zbMATH DE number 739283 (Why is no real title available?)
• scientific article; zbMATH DE number 765034 (Why is no real title available?)
• scientific article; zbMATH DE number 3274494 (Why is no real title available?)
• scientific article; zbMATH DE number 3313523 (Why is no real title available?)
• scientific article; zbMATH DE number 2237386 (Why is no real title available?)
• scientific article; zbMATH DE number 3059214 (Why is no real title available?)
• A fluid limit model criterion for instability of multiclass queueing networks
• A stability criterion via fluid limits and its application to a polling system
• Distributed Random Access Algorithm: Scheduling and Congestion Control
• Fast Mixing of Parallel Glauber Dynamics and Low-Delay CSMA Scheduling
• Hardness of Low Delay Network Scheduling
• Medium Access Using Queues
• On positive Harris recurrence of multiclass queueing networks: A unified approach via fluid limit models
• On the stability of a queueing system with uncountably branching fluid limits
• Probability with Martingales
• Random fluid limit of an overloaded polling model
• Randomized scheduling algorithm for queueing networks
• Stability and convergence of moments for multiclass queueing networks via fluid limit models
• Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks
• Transience of multiclass queueing networks via fluid limit models
• Weak Convergence of Probability Measures on the Function Space $C\lbrack 0, \infty)$

Cited in

(15)

• Queues with random back-offs
• Mean-field limits for large-scale random-access networks
• Analysis of the shortest relay queue policy in a cooperative random access network with collisions
• Fluid limits for QB-CSMA with polynomial rates, homogenization and reflection
• Adding edge dynamics to bipartite random-access networks
• The paging drum queue: A uniform perspective and further results
• Crossover times in bipartite networks with activity constraints and time-varying switching rates
• A stochastic analysis of resource sharing with logarithmic weights
• On partially homogeneous nearest-neighbour random walks in the quarter plane and their application in the analysis of two-dimensional queues with limited state-dependency
• Componentwise accurate fluid queue computations using doubling algorithms
• Transition time asymptotics of queue-based activation protocols in random-access networks
• Detecting Markov chain instability: a Monte Carlo approach
• 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: Queue-based random-access algorithms: fluid limits and stability issues

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