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

DOI10.1214/13-SSY104zbMATH Open1301.60104arXiv1302.5945MaRDI QIDQ2921185FDOQ2921185

Authors: Javad Ghaderi, Phil Whiting, Sem Borst 

Publication date: 7 October 2014

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

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.

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

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

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)

Cites Work

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

Cited In (15)

• Mean-field limits for large-scale random-access networks
• Crossover times in bipartite networks with activity constraints and time-varying switching rates
• Fluid limits for QB-CSMA with polynomial rates, homogenization and reflection
• 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
• A stochastic analysis of resource sharing with logarithmic weights
• Delay performance in random-access networks
• Lingering issues in distributed scheduling
• Transition time asymptotics of queue-based activation protocols in random-access networks
• Induced idleness leads to deterministic heavy traffic limits for queue-based random-access algorithms
• Queues with random back-offs
• The paging drum queue: A uniform perspective and further results
• Analysis of the shortest relay queue policy in a cooperative random access network with collisions
• Detecting Markov chain instability: a Monte Carlo approach
• Adding edge dynamics to bipartite random-access networks

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)