Large number of queues in tandem: scaling properties under back-pressure algorithm

DOI10.1007/S11134-010-9203-0MaRDI QIDQ632216zbMATH OpenOpenAlexFDO

Authors Alexander L. Stolyar

Publication date 15 March 2011

Published in Queueing Systems (Search for Journal in Brave)

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

zbMATH Keywords

stabilityinteracting particle systemsqueueing networksTASEPback-pressureinfinite tandem queuesMaxWeight

Mathematics Subject Classification ID

Interacting random processes; statistical mechanics type models; percolation theory (60K35) Queueing theory (aspects of probability theory) (60K25) Stochastic network models in operations research (90B15) Network protocols (68M12)

Abstract: We consider a system with N unit-service-rate queues in tandem, with exogenous arrivals of rate lambda at queue 1, under a back-pressure (MaxWeight) algorithm: service at queue n is blocked unless its queue length is greater than that of next queue n+1. The question addressed is how steady-state queues scale as N goes to infinity. We show that the answer depends on whether lambda is below or above the critical value 1/4: in the former case queues remain uniformly stochastically bounded, while otherwise they grow to infinity. The problem is essentially reduced to the behavior of the system with infinite number of queues in tandem, which is studied using tools from interacting particle systems theory. In particular, the criticality of load 1/4 is closely related to the fact that this is the maximum possible flux (flow rate) of a stationary totally asymmetric simple exclusion process.

Recommendations

• Large tandem queueing networks with blocking
• Tandem Brownian queues
• A scaling limit for queues in series
• Large deviations for tandem queueing systems
• Large deviations for the total queue size in non-Markovian tandem queues

Cites work

• scientific article; zbMATH DE number 1350307 (Why is no real title available?)
• scientific article; zbMATH DE number 3892344 (Why is no real title available?)
• scientific article; zbMATH DE number 3274494 (Why is no real title available?)
• scientific article; zbMATH DE number 3322728 (Why is no real title available?)
• Ergodic Theorems for the Asymmetric Simple Exclusion Process
• Large deviations and overflow probabilities for the general single-server queue, with applications
• Large tandem queueing networks with blocking
• Logarithmic asymptotics for steady-state tail probabilities in a single-server queue
• Maximizing queueing network utility subject to stability: greedy primal-dual algorithm
• Maximum Pressure Policies in Stochastic Processing Networks
• Optimal resource allocation for multicast sessions in multi-hop wireless networks
• Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks

Cited in

(6)

• Stability of longest-queue-first scheduling in linear wireless networks with multihop traffic and one-hop interference
• How to Scale Exponential Backoff: Constant Throughput, Polylog Access Attempts, and Robustness
• Heavy Tails in Queueing Systems: Impact of Parallelism on Tail Performance
• Tandem queueing networks with neighbor blocking and back-offs
• Large tandem queueing networks with blocking
• Concave switching in single-hop and multihop networks

This page was built for publication: Large number of queues in tandem: scaling properties under back-pressure algorithm

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