Serve the shortest queue and Walsh Brownian motion

DOI10.1214/18-AAP1432MaRDI QIDQ670753zbMATH OpenWikidataFDO

Authors Rami Atar, Asaf Cohen

Publication date 20 March 2019

Published in The Annals of Applied Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1802.02748, https://projecteuclid.org/euclid.aoap/1544000438

zbMATH Keywords

diffusion limitsheavy trafficWalsh Brownian motionserve the shortest queue

Mathematics Subject Classification ID

Applications of Brownian motions and diffusion theory (population genetics, absorption problems, etc.) (60J70) Central limit and other weak theorems (60F05) Queueing theory (aspects of probability theory) (60K25) Brownian motion (60J65) Stochastic systems in control theory (general) (93E03)

Abstract: We study a single-server Markovian queueing model with $N$ customer classes in which priority is given to the shortest queue. Under a critical load condition, we establish the diffusion limit of the workload and queue length processes in the form of a Walsh Brownian motion (WBM) living in the union of the $N$ nonnegative coordinate axes in $mathbb{R}^N$ and a linear transformation thereof. This reveals the following asymptotic behavior. Each time that queues begin to build starting from an empty system, one of them becomes dominant in the sense that it contains nearly all the workload in the system, and it remains so until the system becomes (nearly) empty again. The radial part of the WBM, given as a reflected Brownian motion (RBM) on the half-line, captures the total workload asymptotics, whereas its angular distribution expresses how likely it is for each class to become dominant on excursions. As a heavy traffic result it is nonstandard in three ways: (i) In the terminology of Harrison (1995) it is unconventional, in that the limit is not an RBM. (ii) It does not constitute an invariance principle, in that the limit law (specifically, the angular distribution) is not determined solely by the first two moments of the data, and is sensitive even to tie breaking rules. (iii) The proof method does not fully characterize the limit law (specifically, it gives no information on the angular distribution).

Recommendations

• Bounding functions of Markov processes and the shortest queue problem
• scientific article; zbMATH DE number 6458577
• A Large Deviation Principle for Join the Shortest Queue
• Many-server asymptotics for join-the-shortest-queue: large deviations and rare events
• scientific article; zbMATH DE number 5363765
• Queueing for ergodic arrivals and services
• On the maximum workload of a queue fed by fractional Brownian motion.
• Join the shortest queue: Stability and exact asymptotics

Cites work

• scientific article; zbMATH DE number 3934148 (Why is no real title available?)
• scientific article; zbMATH DE number 3951715 (Why is no real title available?)
• scientific article; zbMATH DE number 18222 (Why is no real title available?)
• scientific article; zbMATH DE number 1354815 (Why is no real title available?)
• scientific article; zbMATH DE number 2006037 (Why is no real title available?)
• scientific article; zbMATH DE number 786511 (Why is no real title available?)
• scientific article; zbMATH DE number 932422 (Why is no real title available?)
• A multiclass closed queueing network with unconventional heavy traffic behavior
• A multiclass queue in heavy traffic with throughput time constraints: Asymptotically optimal dynamic controls
• An open queueing network with asymptotically stable fluid model and unconventional heavy traffic behavior
• Construction of right processes from excursions
• Discrete approximations to solution flows of Tanaka's SDE related to Walsh Brownian motion
• It� excursion theory via resolvents
• On skew Brownian motion
• Stationary analysis of the ``shortest queue first service policy: the asymmetric case
• Stationary analysis of the shortest queue first service policy
• Stochastic integral equations for Walsh semimartingales
• The equivalence of diffusions on networks to Brownian motion
• The hitting time density for a reflected Brownian motion
• The weak convergence of regenerative processes using some excursion path decompositions
• Triple points: From non-Brownian filtrations to harmonic measures
• Weak convergence theorems for priority queues: preemptive-resume discipline

Cited in

(2)

• Semimartingales on rays, Walsh diffusions, and related problems of control and stopping
• Induced idleness leads to deterministic heavy traffic limits for queue-based random-access algorithms

This page was built for publication: Serve the shortest queue and Walsh Brownian motion

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