[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
research-article

Unleashing the Power of Paying Multiplexing Only Once in Stochastic Network Calculus

Published: 06 June 2022 Publication History

Abstract

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.

References

[1]
François Baccelli, Guy Cohen, Geert Jan Olsder, and Jean-Pierre Quadrat. 1992. Synchronization and linearity: an algebra for discrete event systems. John Wiley & Sons Ltd.
[2]
Michael A Beck. 2016. Advances in Theory and Applicability of Stochastic Network Calculus. Ph. D. Dissertation. TU Kaiserslautern.
[3]
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.
[4]
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).
[5]
Anne Bouillard. 2022. Trade-off between accuracy and tractability of network calculus in FIFO networks. Performance Evaluation 153 (2022), 102250.
[6]
Anne Bouillard, Marc Boyer, and Euriell Le Corronc. 2018. Deterministic Network Calculus: From Theory to Practical Implementation. John Wiley & Sons.
[7]
Anne Bouillard, Céline Comte, Élie de Panafieu, and Fabien Mathieu. 2018. Of Kernels and Queues: when network calculus meets analytic combinatorics. In 2018 30th International Teletraffic Congress (ITC 30). 49--54.
[8]
Anne Bouillard, Bruno Gaujal, Sébastien Lagrange, and Eric Thierry. 2008. Optimal routing for end-to-end guarantees using network calculus. Performance Evaluation 65, 11--12 (2008), 883--906.
[9]
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]
[10]
Hugh Boyes, Bil Hallaq, Joe Cunningham, and Tim Watson. 2018. The industrial internet of things (IIoT): An analysis framework. Computers in Industry 101 (2018), 1--12.
[11]
Cheng-Shang Chang. 2000. Performance guarantees in communication networks. Springer-Verlag, London.
[12]
Florin Ciucu, Almut Burchard, and Jörg Liebeherr. 2006. Scaling properties of statistical end-to-end bounds in the network calculus. IEEE/ACM Transactions on Networking (ToN) 14, 6 (2006), 2300--2312.
[13]
Florin Ciucu, Felix Poloczek, and Jens Schmitt. 2014. Sharp Per-Flow Delay Bounds for Bursty Arrivals: The Case of FIFO, SP, and EDF Scheduling. In Proc. IEEE International Conference on Computer Communications (INFOCOM'14).
[14]
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.
[15]
Rene L Cruz. 1991. A calculus for network delay, part I: Network elements in isolation. IEEE Transactions on information theory 37, 1 (1991), 114--131.
[16]
Rene L Cruz. 1991. A calculus for network delay, part II: Network analysis. IEEE Transactions on information theory 37, 1 (1991), 132--141.
[17]
Rene L Cruz. 1996. Quality of service management in integrated services networks. In Proc. Semi-Annual Research Review, CWC. 4--5.
[18]
Feng-Cheng Chang. 1973. Recursive formulas for the partial fraction expansion of a rational function with multiple poles. Proc. IEEE 61, 8 (1973), 1139--1140.
[19]
Gerhard Paul Fettweis. 2014. The tactile internet: Applications and challenges. IEEE Vehicular Technology Magazine 9, 1 (2014), 64--70.
[20]
Markus Fidler. 2003. Extending the network calculus pay bursts only once principle to aggregate scheduling. In International Workshop on Quality of Service in Multiservice IP Networks. Springer, 19--34.
[21]
Markus Fidler. 2006. An end-to-end probabilistic network calculus with moment generating functions. In Proc. IEEE IWQoS'06. 261--270.
[22]
Philippe Flajolet and Fabrice Guillemin. 2000. The formal theory of birth-and-death processes, lattice path combinatorics and continued fractions. Advances in Applied Probability 32, 3 (2000), 750--778. https://doi.org/10.1239/aap/1013540243
[23]
Philippe Flajolet and Robert Sedgewick. 2009. Analytic combinatorics. Cambridge University Press.
[24]
Fabien Geyer and Steffen Bondorf. 2019. DeepTMA: Predicting effective contention models for network calculus using graph neural networks. In Proc. IEEE International Conference on Computer Communications (INFOCOM'19). 1009--1017.
[25]
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).
[26]
Gerald J Hahn and William Q Meeker. 2011. Statistical intervals: a guide for practitioners. Vol. 92. John Wiley & Sons.
[27]
Yuming Jiang and Yong Liu. 2008. Stochastic network calculus. Vol. 1. Springer.
[28]
Michael Mitzenmacher and Eli Upfal. 2005. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press.
[29]
Paul Nikolaus and Jens Schmitt. 2017. On Per-Flow Delay Bounds in Tandem Queues under (In)Dependent Arrivals. In Proc. 16th IFIP Networking Conference (NETWORKING'17). 1--9.
[30]
Paul Nikolaus and Jens Schmitt. 2020. Improving Delay Bounds in the Stochastic Network Calculus by Using Less Stochastic Inequalities. In Proc. 13th EAI International Conference on Performance Evaluation Methodologies and Tools Proc. ACM Meas. Anal. Comput. Syst., Vol. 6, No. 2, Article 31. Publication date: June 2022. 31:22 Anne Bouillard, Paul Nikolaus, and Jens Schmitt (VALUETOOLS'20). 96--103.
[31]
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.
[32]
Paul Nikolaus, Jens B. Schmitt, and Malte Schütze. 2019. h-Mitigators: Improving your stochastic network calculus output bounds. Computer Communications 144 (2019), 188--197.
[33]
Felix Poloczek and Florin Ciucu. 2014. Scheduling analysis with martingales. Performance Evaluation 79 (2014), 56 -- 72. Special Issue: Performance 2014.
[34]
Amr Rizk and Markus Fidler. 2011. Leveraging statistical multiplexing gains in single-and multi-hop networks. In Proc. IEEE International Workshop on Quality of Service (IWQoS'17). 1--9.
[35]
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).
[36]
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.
[37]
The Sage Developers. 2020. SageMath, the Sage Mathematics Software System (Version 9.2). https://www.sagemath.org.
[38]
Timothy Zhu, Daniel S Berger, and Mor Harchol-Balter. 2016. SNC-Meister: Admitting More Tenants with Tail Latency SLOs. In Proc. ACM Symposium on Cloud Computing (SoCC'16). 374--387.

Cited By

View all
  • (2024)MGF-based SNC for stationary independent Markovian processes with localized application of martingalesDiscrete Event Dynamic Systems10.1007/s10626-024-00399-x34:2(375-401)Online publication date: 8-May-2024
  • (2023)Quasi-Deterministic Burstiness Bound for Aggregate of Independent, Periodic FlowsQuantitative Evaluation of Systems10.1007/978-3-031-43835-6_15(205-220)Online publication date: 20-Sep-2023

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Proceedings of the ACM on Measurement and Analysis of Computing Systems
Proceedings of the ACM on Measurement and Analysis of Computing Systems  Volume 6, Issue 2
POMACS
June 2022
499 pages
EISSN:2476-1249
DOI:10.1145/3543145
Issue’s Table of Contents
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the 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, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 06 June 2022
Published in POMACS Volume 6, Issue 2

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. pay multiplexing only once
  2. stochastic network calculus

Qualifiers

  • Research-article

Funding Sources

  • This work was partially supported by Huawei Technologies Co. Ltd.

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)37
  • Downloads (Last 6 weeks)4
Reflects downloads up to 21 Dec 2024

Other Metrics

Citations

Cited By

View all
  • (2024)MGF-based SNC for stationary independent Markovian processes with localized application of martingalesDiscrete Event Dynamic Systems10.1007/s10626-024-00399-x34:2(375-401)Online publication date: 8-May-2024
  • (2023)Quasi-Deterministic Burstiness Bound for Aggregate of Independent, Periodic FlowsQuantitative Evaluation of Systems10.1007/978-3-031-43835-6_15(205-220)Online publication date: 20-Sep-2023

View Options

Login options

Full Access

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media