Queues with random back-offs

DOI10.1007/S11134-013-9374-6MaRDI QIDQ742451zbMATH OpenOpenAlexFDO

Authors Onno Boxma, Niek Bouman, Sem Borst, Johan S. H. van Leeuwaarden

Publication date 18 September 2014

Published in Queueing Systems (Search for Journal in Brave)

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

zbMATH Keywords

delay performanceCSMA protocolheavy-traffic analysisstate-dependent vacationsvacation queue

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)

Abstract: We consider a broad class of queueing models with random state-dependent vacation periods, which arise in the analysis of queue-based back-off algorithms in wireless random-access networks. In contrast to conventional models, the vacation periods may be initiated after each service completion, and can be randomly terminated with certain probabilities that depend on the queue length. We examine the scaled queue length and delay in a heavy-traffic regime, and demonstrate a sharp trichotomy, depending on how the activation rate and vacation probability behave as function of the queue length. In particular, the effect of the vacation periods may either (i) completely vanish in heavy-traffic conditions, (ii) contribute an additional term to the queue lengths and delays of similar magnitude, or even (iii) give rise to an order-of-magnitude increase. The heavy-traffic asymptotics are obtained by combining stochastic lower and upper bounds with exact results for some specific cases. The heavy-traffic trichotomy provides valuable insight in the impact of the back-off algorithms on the delay performance in wireless random-access networks.

Recommendations

• Delay performance in random-access networks
• Tandem queueing networks with neighbor blocking and back-offs
• Burst arrival queues with server vacations and random timers
• Induced idleness leads to deterministic heavy traffic limits for queue-based random-access algorithms
• Control of Polling in Presence of Vacations in Heavy Traffic with Applications to Satellite and Mobile Radio Systems

Cites work

• scientific article; zbMATH DE number 3146363 (Why is no real title available?)
• scientific article; zbMATH DE number 49989 (Why is no real title available?)
• scientific article; zbMATH DE number 2106909 (Why is no real title available?)
• scientific article; zbMATH DE number 3206641 (Why is no real title available?)
• A distributional form of Little's law
• Distributed Random Access Algorithm: Scheduling and Congestion Control
• Fast Mixing of Parallel Glauber Dynamics and Low-Delay CSMA Scheduling
• Foundations of Modern Probability
• Heavy-traffic analysis for the GI/G/1 queue with heavy-tailed distributions
• Medium Access Using Queues
• Polling systems with multiple coupled servers
• Queue-based random-access algorithms: fluid limits and stability issues
• Queues with random back-offs
• Some Conditions for Ergodicity and Recurrence of Markov Chains
• State Dependence in M/G/1 Server-Vacation Models
• Stochastic Decompositions in the M/G/1 Queue with Generalized Vacations
• Sufficient Conditions for Positive Recurrence and Recurrence of Specially Structured Markov Chains

Cited in

(9)

• Slow transitions and starvation in dense random-access networks
• Queues with regular variation
• A GI|G|1|\( \infty\) system with service device vacations
• Delay performance in random-access networks
• On queue length in a queueing system with Erlang incoming flow
• Two queues with random time-limited polling
• Induced idleness leads to deterministic heavy traffic limits for queue-based random-access algorithms
• Queues with random back-offs
• Tandem queueing networks with neighbor blocking and back-offs

This page was built for publication: Queues with random back-offs

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