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

DOI10.1007/S11134-010-9203-0zbMATH Open1217.90048arXiv1002.3940OpenAlexW2168055141MaRDI QIDQ632216FDOQ632216

Authors: Alexander L. Stolyar 

Publication date: 15 March 2011

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

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• 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
• Maximizing queueing network utility subject to stability: greedy primal-dual algorithm
• Optimal resource allocation for multicast sessions in multi-hop wireless networks
• Logarithmic asymptotics for steady-state tail probabilities in a single-server queue
• Large deviations and overflow probabilities for the general single-server queue, with applications
• Maximum Pressure Policies in Stochastic Processing Networks
• Large tandem queueing networks with blocking
• Ergodic Theorems for the Asymmetric Simple Exclusion Process

Cited In (6)

• Stability of longest-queue-first scheduling in linear wireless networks with multihop traffic and one-hop interference
• Large tandem queueing networks with blocking
• Concave switching in single-hop and multihop networks
• 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

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)