Stationary analysis of the shortest queue first service policy

DOI10.1007/S11134-013-9383-5MaRDI QIDQ475121zbMATHOpenAlexFDO

Authors Alain Simonian, Fabrice M. Guillemin

Publication date 25 November 2014

Published in Queueing Systems (Search for Journal in Brave)

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

zbMATH Keywords

functional equationMarkovian analysisqueue asymptoticsshortest queue first service

Mathematics Subject Classification ID

Queues and service in operations research (90B22) Queueing theory (aspects of probability theory) (60K25) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Abstract: We analyze the so-called Shortest Queue First (SQF) queueing discipline whereby a unique server addresses queues in parallel by serving at any time that queue with the smallest workload. Considering a stationary system composed of two parallel queues and assuming Poisson arrivals and general service time distributions, we first establish the functional equations satisfied by the Laplace transforms of the workloads in each queue. We further specialize these equations to the so-called "symmetric case", with same arrival rates and identical exponential service time distributions at each queue; we then obtain a functional equation ${\displaystyle }$ M(z) = q(z) cdot M circ h(z) + L(z) ${\displaystyle }$ for unknown function $M$, where given functions $q$, $L$ and $h$ are related to one branch of a cubic polynomial equation. We study the analyticity domain of function $M$ and express it by a series expansion involving all iterates of function $h$. This allows us to determine empty queue probabilities along with the tail of the workload distribution in each queue. This tail appears to be identical to that of the Head-of-Line preemptive priority system, which is the key feature desired for the SQF discipline.

Recommendations

• Stationary analysis of the ``shortest queue first service policy: the asymmetric case
• Stationary analysis of the shortest queue problem
• J.comput. appl. math
• Some first passage time problems for the shortest queue model
• Two parallel queues with infinite servers and \textit{join the shortest queue} discipline

Cites work

• scientific article; zbMATH DE number 3791325 (Why is no real title available?)
• scientific article; zbMATH DE number 1947316 (Why is no real title available?)
• scientific article; zbMATH DE number 2114364 (Why is no real title available?)
• scientific article; zbMATH DE number 3320700 (Why is no real title available?)
• scientific article; zbMATH DE number 2237386 (Why is no real title available?)
• A two-queue, one-server model with priority for the longer queue
• Analysis of the asymmetrical shortest two-server queueing model
• Rate conservation laws for multidimensional processes of bounded variation with applications to priority queueing systems
• Stationary analysis of the ``shortest queue first service policy: the asymmetric case

Cited in

(6)

• Some first passage time problems for the shortest queue model
• Stationary analysis of the ``shortest queue first service policy: the asymmetric case
• Stationary analysis of the shortest queue problem
• Serve the shortest queue and Walsh Brownian motion
• On partially homogeneous nearest-neighbour random walks in the quarter plane and their application in the analysis of two-dimensional queues with limited state-dependency
• Martingales and buffer overflow for the symmetric shortest queue model

This page was built for publication: Stationary analysis of the shortest queue first service policy

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