skip to main content
article

On the way to a distributed systems calculus: an end-to-end network calculus with data scaling

Published: 26 June 2006 Publication History

Abstract

Network calculus is a min-plus system theory which facilitates the efficient derivation of performance bounds for networks of queues. It has successfully been applied to provide end-to-end quality of service guarantees for integrated and differentiated services networks. Yet, a true end-to-end analysis including the various components of end systems as well as taking into account mid-boxes like firewalls, proxies, or media gateways has not been accomplished so far. The particular challenge posed by such systems are transformation processes, like data processing, compression, encoding, and decoding, which may alter data arrivals drastically. The heterogeneity, which is reflected in the granularity of operation, for example multimedia applications process video frames which, however, are represented by packets in the network, complicates the analysis further. To this end this paper evolves a concise network calculus with scaling functions, which allow modelling a wide variety of transformation processes. Combined with the concept of packetizer this theory enables a true end-to-end analysis of distributed systems.

References

[1]
R. Agrawal, R. L. Cruz, C. Okino, and R. Rajan. Performance bounds for flow control protocols. IEEE/ACM Trans. Networking, 7(3):310--323, June 1999.
[2]
F. Baccelli, G. Cohen, G. J. Olsder, and J.-P. Quadrat. Synchronization and Linearity: An Algebra for Discrete Event Systems. Probability and Mathematical Statistics. John Wiley & Sons Ltd., West Sussex, Great Britain, 1992.
[3]
C.-S. Chang. On deterministic traffic regulation and service guarantees: A systematic approach by filtering. IEEE Trans. Inform. Theory, 44(3):1097--1110, May 1998.
[4]
C.-S. Chang. Performance Guarantees in Communication Networks. Telecommunication Networks and Computer Systems. Springer-Verlag, London, Great Britain, 2000.
[5]
F. Ciucu, A. Burchard, and J. Liebeherr. A network service curve approach for the stochastic analysis of networks. In Proc. ACM SIGMETRICS, pages 279--290, June 2005.
[6]
R. L. Cruz. A calculus for network delay, Part I: Network elements in isolation. IEEE Trans. Inform. Theory, 37(1):114--131, January 1991.
[7]
R. L. Cruz. A calculus for network delay, Part II: Network analysis. IEEE Trans. Inform. Theory, 37(1):132--141, January 1991.
[8]
R. L. Cruz. Quality of service guarantees in virtual circuit switched networks. IEEE J. Select. Areas Commun., 13(6):1048--1056, August 1995.
[9]
R. L. Cruz. SCED+: Efficient management of quality of service guarantees. In Proc. IEEE INFOCOM, volume 2, pages 625--634, March 1998.
[10]
F. H. P. Fitzek and M. Reisslein. MPEG--4 and H.263 video traces for network performance evaluation. IEEE Network, 15(6):40--54, November/December 2001.
[11]
J.-Y. Le Boudec. Application of network calculus to guaranteed service networks. IEEE Trans. Inform. Theory, 44(3):1087--1096, May 1998.
[12]
J.-Y. Le Boudec and P. Thiran. Network Calculus A Theory of Deterministic Queuing Systems for the Internet. Number 2050 in Lecture Notes in Computer Science. Springer-Verlag, Berlin, Germany, 2001.
[13]
J. Liebeherr and D. E. Wrege. An efficient solution to traffic characterization of VBR video in quality-of-service networks. ACM/Springer Multimedia Systems Journal, 6(4):271--284, July 1998.
[14]
A. K. Parekh and R. G. Gallager. A generalized processor sharing approach to flow control in integrated services networks: The single-node case. IEEE/ACM Trans. Networking, 1(3):344--357, June 1993.
[15]
A. K. Parekh and R. G. Gallager. A generalized processor sharing approach to flow control in integrated services networks: The multiple-node case. IEEE/ACM Trans. Networking, 2(2):137--150, April 1994.
[16]
H. Sariowan, R. L. Cruz, and G. C. Polyzos. Scheduling for quality of service guarantees via service curves. In Proc. IEEE ICCCN, pages 512--520, September 1995.
[17]
D. E. Wrege and J. Liebeherr. Video traffic characterization for multimedia networks with a deterministic service. In Proc. IEEE INFOCOM, pages 537--544, March 1996.

Cited By

View all
  • (2023)On the Choice of a Model for Representing Data Flow Parameters in a Digital System2023 International Russian Smart Industry Conference (SmartIndustryCon)10.1109/SmartIndustryCon57312.2023.10110741(306-310)Online publication date: 27-Mar-2023
  • (2023)Accurate Selection of proper network system and concern Cloud Services through computing2023 3rd International Conference on Advance Computing and Innovative Technologies in Engineering (ICACITE)10.1109/ICACITE57410.2023.10182775(1696-1699)Online publication date: 12-May-2023
  • (2021)A methodology for the evaluation of the message transmission delay over IEC 61850 communication network — a real-time HV/MV substation case studySustainable Energy, Grids and Networks10.1016/j.segan.2021.10055528(100555)Online publication date: Dec-2021
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM SIGMETRICS Performance Evaluation Review
ACM SIGMETRICS Performance Evaluation Review  Volume 34, Issue 1
Performance evaluation review
June 2006
388 pages
ISSN:0163-5999
DOI:10.1145/1140103
Issue’s Table of Contents
  • cover image ACM Conferences
    SIGMETRICS '06/Performance '06: Proceedings of the joint international conference on Measurement and modeling of computer systems
    June 2006
    404 pages
    ISBN:1595933190
    DOI:10.1145/1140277
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: 26 June 2006
Published in SIGMETRICS Volume 34, Issue 1

Check for updates

Author Tags

  1. network calculus
  2. packetizers
  3. scaling functions

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)13
  • Downloads (Last 6 weeks)1
Reflects downloads up to 20 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2023)On the Choice of a Model for Representing Data Flow Parameters in a Digital System2023 International Russian Smart Industry Conference (SmartIndustryCon)10.1109/SmartIndustryCon57312.2023.10110741(306-310)Online publication date: 27-Mar-2023
  • (2023)Accurate Selection of proper network system and concern Cloud Services through computing2023 3rd International Conference on Advance Computing and Innovative Technologies in Engineering (ICACITE)10.1109/ICACITE57410.2023.10182775(1696-1699)Online publication date: 12-May-2023
  • (2021)A methodology for the evaluation of the message transmission delay over IEC 61850 communication network — a real-time HV/MV substation case studySustainable Energy, Grids and Networks10.1016/j.segan.2021.10055528(100555)Online publication date: Dec-2021
  • (2018)ReferencesDeterministic Network Calculus10.1002/9781119440284.refs(303-315)Online publication date: 26-Oct-2018
  • (2017)Cloud service performance evaluation: status, challenges, and opportunities – a survey from the system modeling perspectiveDigital Communications and Networks10.1016/j.dcan.2016.12.0023:2(101-111)Online publication date: May-2017
  • (2016)Load balancing - towards balanced delay guarantees in NFV/SDN2016 IEEE Conference on Network Function Virtualization and Software Defined Networks (NFV-SDN)10.1109/NFV-SDN.2016.7919504(240-245)Online publication date: Nov-2016
  • (2015)Stochastic delay analysis of a wireless safety-critical avionics network10th IEEE International Symposium on Industrial Embedded Systems (SIES)10.1109/SIES.2015.7185045(1-10)Online publication date: Jun-2015
  • (2015)Performance of in-network processing for visual analysis in wireless sensor networks2015 IFIP Networking Conference (IFIP Networking)10.1109/IFIPNetworking.2015.7145292(1-9)Online publication date: May-2015
  • (2015)A coupled processors model for 802.11 ad hoc networks under non saturation2015 IEEE International Conference on Communications (ICC)10.1109/ICC.2015.7248392(628-634)Online publication date: Jun-2015
  • (2014)Performance optimization of a UWB-based network for safety-critical avionicsProceedings of the 2014 IEEE Emerging Technology and Factory Automation (ETFA)10.1109/ETFA.2014.7005191(1-9)Online publication date: Sep-2014
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media