Stationary analysis of the shortest queue problem

DOI10.1007/S11134-017-9556-8MaRDI QIDQ1688928zbMATH OpenOpenAlexFDO

Authors Plinio S. Dester, Christine Fricker, Danielle Tibi

Publication date 12 January 2018

Published in Queueing Systems (Search for Journal in Brave)

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

zbMATH Keywords

finite capacitystationary probabilitiesbivariate generating functionshortest queue

Mathematics Subject Classification ID

Queueing theory (aspects of probability theory) (60K25) Continuous-time Markov processes on discrete state spaces (60J27)

Abstract: A simple analytical solution is proposed for the stationary loss system of two parallel queues with finite capacity $K$, in which new customers join the shortest queue, or one of the two with equal probability if their lengths are equal. The arrival process is Poisson, service times at each queue have exponential distributions with the same parameter, and both queues have equal capacity. Using standard generating function arguments, a simple expression for the blocking probability is derived, which as far as we know is original. Using coupling arguments and explicit formulas, comparisons with related loss systems are then provided. Bounds are similarly obtained for the average total number of customers, with the stationary distribution explicitly determined on $K,dots,2K$, and elsewhere upper bounded. Furthermore, from the balance equations, all stationary probabilities are obtained as explicit combinations of their values at states $(0,k)$ for $0lekleK$. These expressions extend to the infinite capacity and asymmetric cases, i.e., when the queues have different service rates. For the initial symmetric finite capacity model, the stationary probabilities of states $(0,k)$ can be obtained recursively from the blocking probability. In the other cases, they are implicitly determined through a functional equation that characterizes their generating function. The whole approach shows that the stationary distribution of the infinite capacity symmetric process is the limit of the corresponding finite capacity distributions. For the infinite capacity symmetric model, we provide an elementary proof of a result by Cohen which gives the solution of the functional equation in terms of an infinite product with explicit zeroes and poles.

Recommendations

• J.comput. appl. math
• The shortest queue problem
• Stationary analysis of the shortest queue first service policy
• Martingales and buffer overflow for the symmetric shortest queue model
• Two parallel queues with infinite servers and \textit{join the shortest queue} discipline

Cites work

• scientific article; zbMATH DE number 4066100 (Why is no real title available?)
• scientific article; zbMATH DE number 836619 (Why is no real title available?)
• A Large Deviation Principle for Join the Shortest Queue
• A SUCCESSIVE LUMPING PROCEDURE FOR A CLASS OF MARKOV CHAINS
• A compensation approach for two-dimensional Markov processes
• A join the shorter queue model in heavy traffic
• Analysis of the asymmetric shortest queue problem
• Analysis of the asymmetric shortest queue problem with threshold jockeying
• Analysis of the asymmetrical shortest two-server queueing model
• Analysis of two queues in parallel with jockeying and restricted capacities
• Bounds for performance characteristics: a systematic approach via cost structures
• DES and RES processes and their explicit solutions
• Deciding Which Queue to Join: Some Counterexamples
• Geometric Decay in a QBD Process with Countable Background States with Applications to a Join-the-Shortest-Queue Model
• Introduction to Matrix Analytic Methods in Stochastic Modeling
• J.comput. appl. math
• Join the shortest queue with many servers. The heavy-traffic asymptotics
• Join the shortest queue: Stability and exact asymptotics
• Large deviations for join the shorter queue
• Large deviations without principle: join the shortest queue
• Malyshev's theory and JS-queues. Asymptotics of stationary probabilities
• On the optimal assignment of customers to parallel servers
• Optimality of the shortest line discipline
• Power Series for Stationary Distributions of Coupled Processor Models
• Quasi-Birth-and-Death Processes, Lattice Path Counting, and Hypergeometric Functions
• Queueing system with selection of the shortest of two queues: An asymptotic approach
• Random walks in the quarter plane. Algebraic methods, boundary value problems, applications to queueing systems and analytic combinatorics
• Stationary analysis of the shortest queue first service policy
• Stationary analysis of the shortest queue problem
• TWO QUEUES IN PARALLEL
• The Longer Queue Model
• The Power-Series Algorithm Applied to the Shortest-Queue Model
• The autostrada queueing problem
• The shortest queue problem
• Two Parallel Queues with Dynamic Routing
• Two Similar Queues in Parallel
• Two coupled processors: The reduction to a Riemann-Hilbert problem
• Two queues in parallel
• Upper and lower bounds for the waiting time in the symmetric shortest queue system

Cited in

(9)

• Stability of parallel server systems
• Stationary analysis of the shortest queue problem
• Two-choice regulation in heterogeneous closed networks
• A polling system with `join the shortest -- serve the longest' policy
• Martingales and buffer overflow for the symmetric shortest queue model
• The Power-Series Algorithm Applied to the Shortest-Queue Model
• Stationary analysis of the shortest queue first service policy
• J.comput. appl. math
• Stationary Distribution of Discrete-Time Finite-Capacity Queue with Re-sequencing

This page was built for publication: Stationary analysis of the shortest queue problem

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