Skip to Main content Skip to Navigation

Reduced complexity in M/Ph/c/N queues

Alexandre Brandwajn 1 Thomas Begin 2
2 DANTE - Dynamic Networks : Temporal and Structural Capture Approach
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme, IXXI - Institut Rhône-Alpin des systèmes complexes
Abstract : A large number of real-life systems can be viewed as instances of the classical M/G/c/N queue. The exact analytical solution of this queueing model is not known, and a frequently-used approach is to replace the general service time distribution by a phase-type distribution. The advantage of this approach is that the resulting M/Ph/c/N queue can be described by familiar balance equations. The downside is that the size of the resulting state space suffers from the "dimensionality curse", i.e., exhibits combinatorial growth as the number of servers and/or phases increases. To circumvent this complexity issue, we propose to use, instead of the classical full state description, a reduced state description in which the state of only one server is represented explicitly, while the other servers are accounted for through their rate of completions. The accuracy of the resulting approximation is generally good and, moreover, tends to improve as the number of servers in the system increases. Its computational complexity in terms of the number of states grows only linearly in the number of servers and phases, thus making the numerical solution of such queues with hundreds of servers and a reasonable number of phases computationally affordable.
Complete list of metadata

Cited literature [1 references]  Display  Hide  Download
Contributor : Thomas Begin Connect in order to contact the contributor
Submitted on : Monday, May 13, 2013 - 12:39:36 AM
Last modification on : Thursday, January 20, 2022 - 5:31:11 PM
Long-term archiving on: : Wednesday, August 14, 2013 - 3:00:10 AM


Files produced by the author(s)


  • HAL Id : hal-00821769, version 1


Alexandre Brandwajn, Thomas Begin. Reduced complexity in M/Ph/c/N queues. [Research Report] RR-8303, INRIA. 2013, pp.15. ⟨hal-00821769⟩



Les métriques sont temporairement indisponibles