Response Time Distribution in a Tandem Pair of Queues with Batch Processing
Open Access
- 30 June 2021
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 68 (4), 1-41
- https://doi.org/10.1145/3448973
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.Keywords
This publication has 30 references indexed in Scilit:
- Stability and structural properties of stochastic storage networksJournal of Applied Probability, 1996
- Sojourn times in a tandem queue with overtaking: reduction to a boundary value problemCommunications in Statistics. Stochastic Models, 1986
- The Product Form for Sojourn Time Distributions in Cyclic Exponential QueuesJournal of the ACM, 1984
- The Distribution of Cycle Times in Tree-Like Networks of QueuesThe Computer Journal, 1984
- Sojourn times in closed queueing networksAdvances in Applied Probability, 1983
- Passage times for overtake-free paths in Gordon–Newell networksAdvances in Applied Probability, 1982
- Sojourn times and the overtaking condition in Jacksonian networksAdvances in Applied Probability, 1980
- The Cycle Time Distribution of Exponential Cyclic QueuesJournal of the ACM, 1980
- Multiple channel queues in heavy traffic. IAdvances in Applied Probability, 1970
- Multiple channel queues in heavy traffic. II: sequences, networks, and batchesAdvances in Applied Probability, 1970