Stationary analysis of the shortest queue first service policy

DOI10.1007/S11134-013-9383-5zbMATH Open1309.60087arXiv1305.3490OpenAlexW2083217436MaRDI QIDQ475121FDOQ475121

Authors: Alain Simonian, Fabrice M. Guillemin 

Publication date: 25 November 2014

Published in: Queueing Systems (Search for Journal in Brave)

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Analysis of the asymmetrical shortest two-server queueing model
• Title not available (Why is that?)
• A two-queue, one-server model with priority for the longer queue
• Stationary analysis of the “Shortest Queue First” service policy: The asymmetric case
• Rate conservation laws for multidimensional processes of bounded variation with applications to priority queueing systems

Cited In (6)

• 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
• Stationary analysis of the “Shortest Queue First” service policy: The asymmetric case
• Martingales and buffer overflow for the symmetric shortest queue model
• Stationary analysis of the shortest queue problem
• Serve the shortest queue and Walsh Brownian motion
• Some first passage time problems for the 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)