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

CSMA protocoldelay performanceheavy-traffic analysisstate-dependent vacationsvacation queue

Mathematics Subject Classification ID

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

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.

Review text

The paper under review studies a broad class of queueing models with random state-dependent vacation periods. This class of models arises in the analysis of queue-based back-off algorithms in wireless random access networks. The paper under review considers an \(\mathrm{M}/\mathrm{G}/1\) queue with vacations. The server of this queueing system can be active or inactive. When active, customers are served with generally distributed service times having finite second moment. The service times are assumed to be independent of the interarrival and vacation times. Immediately after the service completion that leaves \(i\) customers behind, the server becomes inactive with probability \(\psi(i)\), \(\psi(0)=1\). When the server is inactive, no customer is served and the server is said to be on vacation. The server becomes active after random time depending on the number of waiting customers at the beginning of the vacation period and the number of customers arriving during the vacation period, but it does not depend on future arrivals. The paper first presents exact queue-length and delay results for some specific cases and derives stochastic bounds for a richer set of scenarios. On the basis of this, together with stochastic relations between systems with different vacation disciplines, the paper examines the scaled queue-length and delay in a heavy-traffic regime, and demonstrates a sharp trichotomy, depending on how the activation rate and vacation probability behave as functions of 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-length and delays of similar magnitude, or (iii) give rise to an order-of-magnitude increase.

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

• 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
• 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?)
• 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

(11)

• Induced idleness leads to deterministic heavy traffic limits for queue-based random-access algorithms
• A matrix analytic approach to study the queuing characteristics of nodes in a wireless network
• Queues with regular variation
• Slow transitions and starvation in dense random-access networks
• On queue length in a queueing system with Erlang incoming flow
• Tandem queueing networks with neighbor blocking and back-offs
• Two queues with random time-limited polling
• Delay performance in random-access networks
• A GI|G|1|\( \infty\) system with service device vacations
• A queueing system with general vacation
• Queues with random 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)