Serve the shortest queue and Walsh Brownian motion

DOI10.1214/18-AAP1432zbMATH Open1409.60037arXiv1802.02748WikidataQ128891946 ScholiaQ128891946MaRDI QIDQ670753FDOQ670753

Authors: Rami Atar, Asaf Cohen 

Publication date: 20 March 2019

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

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).

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

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

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)

Cites Work

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

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)