{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T23:52:43Z","timestamp":1771026763286,"version":"3.50.1"},"reference-count":40,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2021,6,30]],"date-time":"2021-06-30T00:00:00Z","timestamp":1625011200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2021,8]]},"abstract":"<jats:p>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 \u201craw\u201d batch-queues\u2014with no special arrivals\u2014and 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.<\/jats:p>","DOI":"10.1145\/3448973","type":"journal-article","created":{"date-parts":[[2021,6,30]],"date-time":"2021-06-30T19:11:05Z","timestamp":1625080265000},"page":"1-41","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Response Time Distribution in a Tandem Pair of Queues with Batch Processing"],"prefix":"10.1145","volume":"68","author":[{"given":"P. G.","family":"Harrison","sequence":"first","affiliation":[{"name":"Imperial College London, London"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J.","family":"Bor","sequence":"additional","affiliation":[{"name":"Imperial College London, London"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,6,30]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2422.322419"},{"key":"e_1_2_1_2_1","volume-title":"Queueing Networks: Customers, Signals and Product form Solutions","author":"Chao X.","year":"1999","unstructured":"X. Chao , M. Miyazawa , and M. Pinedo . 1999 . Queueing Networks: Customers, Signals and Product form Solutions . Wiley . X. Chao, M. Miyazawa, and M. Pinedo. 1999. Queueing Networks: Customers, Signals and Product form Solutions. Wiley."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2568088.2568102"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/193201.194066"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/322186.322193"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/647412.724892"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.2307\/1426680"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings. 1\u201313","author":"Ezhilchelvan Paul D.","year":"2018","unstructured":"Paul D. Ezhilchelvan , Isi Mitrani , and Jim Webber . 2018 . On the degradation of distributed graph databases with eventual consistency. In Computer Performance Engineering - 15th European Workshop (EPEW\u201918) , Proceedings. 1\u201313 . DOI:https:\/\/doi.org\/10.1007\/978-3-030-02227-3_1 10.1007\/978-3-030-02227-3_1 Paul D. Ezhilchelvan, Isi Mitrani, and Jim Webber. 2018. On the degradation of distributed graph databases with eventual consistency. In Computer Performance Engineering - 15th European Workshop (EPEW\u201918), Proceedings. 1\u201313. DOI:https:\/\/doi.org\/10.1007\/978-3-030-02227-3_1"},{"key":"e_1_2_1_9_1","volume-title":"Handbooks in Operations Research and Management Science","author":"Glynn Peter W.","unstructured":"Peter W. Glynn . 2006. Simulation algorithms for regenerative processes . In Simulation, Shane G. Henderson and Barry L. Nelson (Eds.). Handbooks in Operations Research and Management Science , Vol. 13 . Elsevier , 477\u2013500. DOI:https:\/\/doi.org\/10.1016\/S0927-0507(06)13016-9 10.1016\/S0927-0507(06)13016-9 Peter W. Glynn. 2006. Simulation algorithms for regenerative processes. In Simulation, Shane G. Henderson and Barry L. Nelson (Eds.). Handbooks in Operations Research and Management Science, Vol. 13. Elsevier, 477\u2013500. DOI:https:\/\/doi.org\/10.1016\/S0927-0507(06)13016-9"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/956750.956778"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/27.1.27"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(02)00375-4"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-02227-3_17"},{"key":"e_1_2_1_15_1","volume-title":"A semi-product-form for a pair of queues with finite batches: Equilibrium state probabilities and response time densities. Performance Evaluation 143","author":"Harrison P. G.","year":"2020","unstructured":"P. G. Harrison . 2020. A semi-product-form for a pair of queues with finite batches: Equilibrium state probabilities and response time densities. Performance Evaluation 143 ( 2020 ). DOI:https:\/\/doi.org\/10.1016\/j.peva.2020.102120 10.1016\/j.peva.2020.102120 P. G. Harrison. 2020. A semi-product-form for a pair of queues with finite batches: Equilibrium state probabilities and response time densities. Performance Evaluation 143 (2020). DOI:https:\/\/doi.org\/10.1016\/j.peva.2020.102120"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/573107"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3306309.3306316"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.peva.2013.08.011"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02411466"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.2307\/3518347"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.2307\/1426324"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1080\/15326348608807024"},{"key":"e_1_2_1_23_1","unstructured":"O. Kella and W. Whitt. 1992. A tandem fluid network with L\u00e9vy input. In Queueing and Related Models U.N. Bhat and I. V. Basawa (Eds.). Oxford University Press 112\u2013128.  O. Kella and W. Whitt. 1992. A tandem fluid network with L\u00e9vy input. In Queueing and Related Models U.N. Bhat and I. V. Basawa (Eds.). Oxford University Press 112\u2013128."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.2307\/3214994"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/2025239"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.2307\/1426623"},{"key":"e_1_2_1_27_1","volume-title":"Traffic Modeling of IP Networks Using the Batch Markovian Arrival Process","author":"Klemm Alexander","unstructured":"Alexander Klemm , Christoph Lindemann , and Marco Lohmann . 2002. Traffic Modeling of IP Networks Using the Batch Markovian Arrival Process . Springer , Berlin , 92\u2013110. DOI:https:\/\/doi.org\/10.1007\/3-540-46029-2_6 10.1007\/3-540-46029-2_6 Alexander Klemm, Christoph Lindemann, and Marco Lohmann. 2002. Traffic Modeling of IP Networks Using the Batch Markovian Arrival Process. Springer, Berlin, 92\u2013110. DOI:https:\/\/doi.org\/10.1007\/3-540-46029-2_6"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.4108\/ICST.VALUETOOLS2009.7787"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11134-017-9534-1"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.2517-6161.1985.tb01368.x"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10479-011-0932-1"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0269964817000286"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-5316(94)00025-F"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.5555\/1941831"},{"key":"e_1_2_1_35_1","volume-title":"5th IEEE Workshop on Mobile Computing Systems and Applications.","author":"Papathanasiou A. E.","unstructured":"A. E. Papathanasiou and M. L. Scott . 2003. Energy efficiency through burstiness . In 5th IEEE Workshop on Mobile Computing Systems and Applications. A. E. Papathanasiou and M. L. Scott. 2003. Energy efficiency through burstiness. In 5th IEEE Workshop on Mobile Computing Systems and Applications."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.5555\/550582"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1147\/rd.193.0301"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3322276.3322369"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(88)90036-3"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.2307\/1426753"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.30.2.223"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3448973","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3448973","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:47:55Z","timestamp":1750193275000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3448973"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,30]]},"references-count":40,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,8]]}},"alternative-id":["10.1145\/3448973"],"URL":"https:\/\/doi.org\/10.1145\/3448973","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,6,30]]},"assertion":[{"value":"2019-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-06-30","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}