Response time distribution in a tandem pair of queues with batch processing
File(s)JACM-00080-2019-R2.pdf (2.66 MB)
Accepted version
Author(s)
Harrison, Peter
Bor, Julianna
Type
Journal Article
Abstract
Response time density is obtained in a tandem pair of Markovian queues with both batch arrivals and batch departures. The method uses conditional forward and reversed node sojourn times and derives the Laplace transform of the response time probability density function in the case that batch sizes are finite. The result is derived by a generating function method that takes into account that the path is not overtake-free in the sense that the tagged task being tracked is affected by later arrivals at the second queue. A novel aspect of the method is that a vector of generating functions is solved for, rather than a single scalar-valued function, which requires investigation of the singularities of a certain matrix. A recurrence formula is derived to obtain arbitrary moments of response time by differentiation of the Laplace transform at the origin, and these can be computed rapidly by iteration. Numerical results for the first four moments of response time are displayed for some sample networks that have product-form solutions for their equilibrium queue length probabilities, along with the densities themselves by numerical inversion of the Laplace transform. Corresponding approximations are also obtained for (non-product-form) pairs of “raw” batch-queues – with no special arrivals – and validated against regenerative simulation, which indicates good accuracy. The methods are appropriate for modeling bursty internet and cloud traffic and a possible role in energy-saving is considered.
Date Issued
2021-08-01
Date Acceptance
2021-02-01
Citation
Journal of the Association for Computing Machinery (ACM), 2021, 68 (4)
ISSN
0004-5411
Publisher
Association for Computing Machinery (ACM)
Journal / Book Title
Journal of the Association for Computing Machinery (ACM)
Volume
68
Issue
4
Copyright Statement
© 2021 Association for Computing Machinery. Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without feeprovided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice andthe full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored.Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requiresprior specific permission and/or a fee. Request permissions frompermissions@acm.org.
Sponsor
Engineering & Physical Science Research Council (EPSRC)
Engineering & Physical Science Research Council (EPSRC)
Grant Number
EP/I030921/1
EP/L00738X/1
Subjects
08 Information and Computing Sciences
Computation Theory & Mathematics
Publication Status
Published
Article Number
ARTN 22