{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,2]],"date-time":"2026-07-02T04:03:05Z","timestamp":1782964985084,"version":"3.54.5"},"reference-count":38,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2022,5,26]],"date-time":"2022-05-26T00:00:00Z","timestamp":1653523200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"This work was partially supported by Huawei Technologies Co. Ltd."}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Meas. Anal. Comput. Syst."],"published-print":{"date-parts":[[2022,5,26]]},"abstract":"<jats:p>The stochastic network calculus (SNC) holds promise as a versatile and uniform framework to calculate probabilistic performance bounds in networks of queues. A great challenge to accurate bounds and efficient calculations are stochastic dependencies between flows due to resource sharing inside the network. However, by carefully utilizing the basic SNC concepts in the network analysis the necessity of taking these dependencies into account can be minimized. To that end, we unleash the power of the pay multiplexing only once principle (PMOO, known from the deterministic network calculus) in the SNC analysis. We choose an analytic combinatorics presentation of the results in order to ease complex calculations. In tree-reducible networks, a subclass of general feedforward networks, we obtain an effective analysis in terms of avoiding the need to take internal flow dependencies into account. In a comprehensive numerical evaluation, we demonstrate how this unleashed PMOO analysis can reduce the known gap between simulations and SNC calculations significantly, and how it favourably compares to state-of-the art SNC calculations in terms of accuracy and computational effort. Motivated by these promising results, we also consider general feedforward networks, when some flow dependencies have to be taken into account. To that end, the unleashed PMOO analysis is extended to the partially dependent case and a case study of a canonical example topology, known as the diamond network, is provided, again displaying favourable results over the state of the art.<\/jats:p>","DOI":"10.1145\/3530897","type":"journal-article","created":{"date-parts":[[2022,6,6]],"date-time":"2022-06-06T17:16:18Z","timestamp":1654535778000},"page":"1-27","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Unleashing the Power of Paying Multiplexing Only Once in Stochastic Network Calculus"],"prefix":"10.1145","volume":"6","author":[{"given":"Anne","family":"Bouillard","sequence":"first","affiliation":[{"name":"Huawei Technologies France, Boulogne-Billancourt, France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Paul","family":"Nikolaus","sequence":"additional","affiliation":[{"name":"TU Kaiserslautern, Kaiserslautern, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jens","family":"Schmitt","sequence":"additional","affiliation":[{"name":"TU Kaiserslautern, Kaiserslautern, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2022,6,6]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Geert Jan Olsder, and Jean-Pierre Quadrat","author":"Baccelli Fran\u00e7ois","year":"1992","unstructured":"Fran\u00e7ois Baccelli , Guy Cohen , Geert Jan Olsder, and Jean-Pierre Quadrat . 1992 . Synchronization and linearity: an algebra for discrete event systems. John Wiley & Sons Ltd . Fran\u00e7ois Baccelli, Guy Cohen, Geert Jan Olsder, and Jean-Pierre Quadrat. 1992. Synchronization and linearity: an algebra for discrete event systems. John Wiley & Sons Ltd."},{"key":"e_1_2_1_2_1","unstructured":"Michael A Beck. 2016. Advances in Theory and Applicability of Stochastic Network Calculus. Ph. D. Dissertation. TU Kaiserslautern.  Michael A Beck. 2016. Advances in Theory and Applicability of Stochastic Network Calculus. Ph. D. Dissertation. TU Kaiserslautern."},{"key":"e_1_2_1_3_1","volume-title":"Beck and Jens Schmitt","author":"Michael","year":"2012","unstructured":"Michael A. Beck and Jens Schmitt . 2012 . On the Calculation of Sample-Path Backlog Bounds in Queueing Systems over Finite Time Horizons. Technical Report. University of Kaiserslautern , Germany. Michael A. Beck and Jens Schmitt. 2012. On the Calculation of Sample-Path Backlog Bounds in Queueing Systems over Finite Time Horizons. Technical Report. University of Kaiserslautern, Germany."},{"key":"e_1_2_1_4_1","volume-title":"Proc. 7th International Conference on Performance Evaluation Methodologies and Tools (VALUETOOLS'13)","author":"Michael","unstructured":"Michael A. Beck and Jens Schmitt. 2013. The DISCO Stochastic Network Calculator Version 1.0 - When Waiting Comes to an End . In Proc. 7th International Conference on Performance Evaluation Methodologies and Tools (VALUETOOLS'13) . Michael A. Beck and Jens Schmitt. 2013. The DISCO Stochastic Network Calculator Version 1.0 - When Waiting Comes to an End. In Proc. 7th International Conference on Performance Evaluation Methodologies and Tools (VALUETOOLS'13)."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.peva.2021.102250"},{"key":"e_1_2_1_6_1","volume-title":"Deterministic Network Calculus: From Theory to Practical Implementation","author":"Bouillard Anne","unstructured":"Anne Bouillard , Marc Boyer , and Euriell Le Corronc . 2018. Deterministic Network Calculus: From Theory to Practical Implementation . John Wiley & Sons . Anne Bouillard, Marc Boyer, and Euriell Le Corronc. 2018. Deterministic Network Calculus: From Theory to Practical Implementation. John Wiley & Sons."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/ITC30.2018.10061"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.peva.2008.04.008"},{"key":"e_1_2_1_9_1","doi-asserted-by":"crossref","unstructured":"Anne Bouillard Paul Nikolaus and Jens Schmitt. 2021. Fully Unleashing the Power of Paying Multiplexing Only Once in Stochastic Network Calculus. arXiv:2104.14215 [cs.PF]  Anne Bouillard Paul Nikolaus and Jens Schmitt. 2021. Fully Unleashing the Power of Paying Multiplexing Only Once in Stochastic Network Calculus. arXiv:2104.14215 [cs.PF]","DOI":"10.1145\/3489048.3530964"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.compind.2018.04.015"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-0459-9"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2006.874380"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFOCOM.2014.6848129"},{"key":"e_1_2_1_14_1","volume-title":"Proc. ACM Conf. on Applications, Technologies, Architectures, and Protocols for Computer Commun. (SIGCOMM'12)","author":"Ciucu Florin","year":"2012","unstructured":"Florin Ciucu and Jens Schmitt . 2012 . Perspectives on Network Calculus -- No Free Lunch, But Still Good Value . In Proc. ACM Conf. on Applications, Technologies, Architectures, and Protocols for Computer Commun. (SIGCOMM'12) . 311--322. Florin Ciucu and Jens Schmitt. 2012. Perspectives on Network Calculus -- No Free Lunch, But Still Good Value. In Proc. ACM Conf. on Applications, Technologies, Architectures, and Protocols for Computer Commun. (SIGCOMM'12). 311--322."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.61109"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.61110"},{"key":"e_1_2_1_17_1","volume-title":"Proc. Semi-Annual Research Review, CWC. 4--5.","author":"Cruz Rene L","year":"1996","unstructured":"Rene L Cruz . 1996 . Quality of service management in integrated services networks . In Proc. Semi-Annual Research Review, CWC. 4--5. Rene L Cruz. 1996. Quality of service management in integrated services networks. In Proc. Semi-Annual Research Review, CWC. 4--5."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/PROC.1973.9216"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/MVT.2013.2295069"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-36480-3_2"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/IWQOS.2006.250477"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1239\/aap\/1013540243"},{"key":"e_1_2_1_23_1","volume-title":"Analytic combinatorics","author":"Flajolet Philippe","unstructured":"Philippe Flajolet and Robert Sedgewick . 2009. Analytic combinatorics . Cambridge University Press . Philippe Flajolet and Robert Sedgewick. 2009. Analytic combinatorics. Cambridge University Press."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFOCOM.2019.8737496"},{"key":"e_1_2_1_25_1","volume-title":"Analysis of generalized processor-sharing systems with two classes of customers and exponential services. Journal of Applied Probability 41 (09","author":"Guillemin Fabrice","year":"2004","unstructured":"Fabrice Guillemin and Didier Pinchon . 2004. Analysis of generalized processor-sharing systems with two classes of customers and exponential services. Journal of Applied Probability 41 (09 2004 ). Fabrice Guillemin and Didier Pinchon. 2004. Analysis of generalized processor-sharing systems with two classes of customers and exponential services. Journal of Applied Probability 41 (09 2004)."},{"key":"e_1_2_1_26_1","volume-title":"Statistical intervals: a guide for practitioners","author":"Hahn Gerald J","unstructured":"Gerald J Hahn and William Q Meeker . 2011. Statistical intervals: a guide for practitioners . Vol. 92 . John Wiley & Sons . Gerald J Hahn and William Q Meeker. 2011. Statistical intervals: a guide for practitioners. Vol. 92. John Wiley & Sons."},{"key":"e_1_2_1_27_1","volume-title":"Stochastic network calculus","author":"Jiang Yuming","unstructured":"Yuming Jiang and Yong Liu . 2008. Stochastic network calculus . Vol. 1 . Springer . Yuming Jiang and Yong Liu. 2008. Stochastic network calculus. Vol. 1. Springer."},{"key":"e_1_2_1_28_1","volume-title":"Probability and Computing: Randomized Algorithms and Probabilistic Analysis","author":"Mitzenmacher Michael","unstructured":"Michael Mitzenmacher and Eli Upfal . 2005. Probability and Computing: Randomized Algorithms and Probabilistic Analysis . Cambridge University Press . Michael Mitzenmacher and Eli Upfal. 2005. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.23919\/IFIPNetworking.2017.8264856"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3388831.3388848"},{"key":"e_1_2_1_31_1","volume-title":"Proc. International Conference on Analytical and Stochastic Modeling Techniques and Applications (ASMTA'19)","author":"Nikolaus Paul","year":"2019","unstructured":"Paul Nikolaus , Jens Schmitt , and Florin Ciucu . 2019 . Dealing with Dependence in Stochastic Network Calculus -- Using Independence as a Bound . In Proc. International Conference on Analytical and Stochastic Modeling Techniques and Applications (ASMTA'19) . Springer. Paul Nikolaus, Jens Schmitt, and Florin Ciucu. 2019. Dealing with Dependence in Stochastic Network Calculus -- Using Independence as a Bound. In Proc. International Conference on Analytical and Stochastic Modeling Techniques and Applications (ASMTA'19). Springer."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comcom.2019.05.016"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.peva.2014.07.004"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/IWQOS.2011.5931352"},{"key":"e_1_2_1_35_1","volume-title":"Proceedings of the First International Conference on Performance Evaluation Methodologies and Tools (VALUETOOLS'06)","author":"Schmitt Jens","unstructured":"Jens Schmitt and Frank A. Zdarsky . 2006. The DISCO Network Calculator - A Toolbox for Worst Case Analysis . In Proceedings of the First International Conference on Performance Evaluation Methodologies and Tools (VALUETOOLS'06) . Jens Schmitt and Frank A. Zdarsky. 2006. The DISCO Network Calculator - A Toolbox for Worst Case Analysis. In Proceedings of the First International Conference on Performance Evaluation Methodologies and Tools (VALUETOOLS'06)."},{"key":"e_1_2_1_36_1","volume-title":"Proc. GI\/ITG Conference on Measurement, Modeling, and Evaluation of Computer and Communication Systems (MMB'08)","author":"Schmitt Jens","year":"2008","unstructured":"Jens Schmitt , Frank A Zdarsky , and Ivan Martinovic . 2008 . Improving Performance Bounds in Feed-Forward Networks by Paying Multiplexing Only Once . In Proc. GI\/ITG Conference on Measurement, Modeling, and Evaluation of Computer and Communication Systems (MMB'08) . 1--15. Jens Schmitt, Frank A Zdarsky, and Ivan Martinovic. 2008. Improving Performance Bounds in Feed-Forward Networks by Paying Multiplexing Only Once. In Proc. GI\/ITG Conference on Measurement, Modeling, and Evaluation of Computer and Communication Systems (MMB'08). 1--15."},{"key":"e_1_2_1_37_1","unstructured":"The Sage Developers. 2020. SageMath the Sage Mathematics Software System (Version 9.2). https:\/\/www.sagemath.org.  The Sage Developers. 2020. SageMath the Sage Mathematics Software System (Version 9.2). https:\/\/www.sagemath.org."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/2987550.2987585"}],"container-title":["Proceedings of the ACM on Measurement and Analysis of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3530897","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3530897","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T18:09:26Z","timestamp":1750183766000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3530897"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,5,26]]},"references-count":38,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,5,26]]}},"alternative-id":["10.1145\/3530897"],"URL":"https:\/\/doi.org\/10.1145\/3530897","relation":{},"ISSN":["2476-1249"],"issn-type":[{"value":"2476-1249","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,5,26]]},"assertion":[{"value":"2022-06-06","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}