Decay of tails at equilibrium for FIFO join the shortest queue networks

DOI10.1214/12-AAP888zbMATH Open1287.60110arXiv1106.4582MaRDI QIDQ373835FDOQ373835

Authors: Maury Bramson, Yi Lu, Balaji Prabhakar 

Publication date: 25 October 2013

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

Abstract: In join the shortest queue networks, incoming jobs are assigned to the shortest queue from among a randomly chosen subset of $D$ queues, in a system of $N$ queues; after completion of service at its queue, a job leaves the network. We also assume that jobs arrive into the system according to a rate-$alphaN$ Poisson process, $alpha<1$, with rate-1 service at each queue. When the service at queues is exponentially distributed, it was shown in Vvedenskaya et al. [Probl. Inf. Transm. 32 (1996) 15-29] that the tail of the equilibrium queue size decays doubly exponentially in the limit as $Nightarrowinfty$. This is a substantial improvement over the case D=1, where the queue size decays exponentially. The reasoning in [Probl. Inf. Transm. 32 (1996) 15-29] does not easily generalize to jobs with nonexponential service time distributions. A modularized program for treating general service time distributions was introduced in Bramson et al. [In Proc. ACM SIGMETRICS (2010) 275-286]. The program relies on an ansatz that asserts, in equilibrium, any fixed number of queues become independent of one another as $Nightarrowinfty$. This ansatz was demonstrated in several settings in Bramson et al. [Queueing Syst. 71 (2012) 247-292], including for networks where the service discipline is FIFO and the service time distribution has a decreasing hazard rate. In this article, we investigate the limiting behavior, as $Nightarrowinfty$, of the equilibrium at a queue when the service discipline is FIFO and the service time distribution has a power law with a given exponent $$, for $$. We show under the above ansatz that, as $Nightarrowinfty$, the tail of the equilibrium queue size exhibits a wide range of behavior depending on the relationship between $$ and $D$. In particular, if $$, the tail is doubly exponential and, if $$, the tail has a power law. When $$, the tail is exponentially distributed.

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

Recommendations

• Stability of join the shortest queue networks
• Asymptotic behavior for MAP/PH/\(c\) queue with shortest queue discipline and jockeying
• Join the shortest queue among \(k\) parallel queues: tail asymptotics of its stationary distribution
• Stability of join-the-shortest-queue networks
• Decay rate for a PH/M/2 queue with shortest queue discipline

zbMATH Keywords

decay of tailsFIFOjoin the shortest queue

Mathematics Subject Classification ID

Queueing theory (aspects of probability theory) (60K25) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Stochastic network models in operations research (90B15)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Queueing system with selection of the shortest of two queues: An asymptotic approach
• Balanced Allocations
• Fast Jackson networks
• Fast Jackson networks with dynamic routing
• On the maximum queue length in the supermarket model
• Title not available (Why is that?)
• Chaoticity on path space for a queueing network with selection of the shortest queue among several
• Asymptotic independence of queues under randomized load balancing
• Stability of queueing networks
• On the stability of a partially accessible multi-station queue with state-dependent routing
• On the power of two choices: balls and bins in continuous time
• Stability of join the shortest queue networks

Cited In (19)

• Large-scale join-idle-queue system with general service times
• Approximations for a queueing game model with join-the-shortest-queue strategy
• Join Idle Queue with Service Elasticity: Large-Scale Asymptotics of a Nonmonotone System
• On a doubly dynamically controlled supermarket model with impatient customers
• The mean-field computation in a supermarket model with server multiple vacations
• Decay rate for a PH/M/2 queue with shortest queue discipline
• Randomized longest-queue-first scheduling for large-scale buffered systems
• Asymptotic independence of queues under randomized load balancing
• k-nearest neighbor queues with delayed information
• Subdiffusive load balancing in time-varying queueing systems
• Delay, memory, and messaging tradeoffs in distributed service systems
• Tail probabilities in queueing processes
• Pull-based load distribution among heterogeneous parallel servers: the case of multiple routers
• Pull-based load distribution in large-scale heterogeneous service systems
• The hydrodynamic limit of a randomized load balancing network
• Block-structured supermarket models
• A lower bound on the queueing delay in resource constrained load balancing
• Large-scale heterogeneous service systems with general packing constraints
• Stability of join the shortest queue networks

This page was built for publication: Decay of tails at equilibrium for FIFO join the shortest queue networks

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