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

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: Rajeev Agrawal , Rene L. Cruz , Clayton Okino , Rajendran Rajan, Performance bonds for flow control protocols, IEEE/ACM Transactions on Networking (TON), v.7 n.3, p.310-323, June 1999 [doi>10.1109/90.779197]
• 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: Cheng-Shang Chang, Performance Guarantees in Communication Networks, Springer-Verlag, London, 2000
• 5: Florin Ciucu , Almut Burchard , Jörg Liebeherr, A network service curve approach for the stochastic analysis of networks, Proceedings of the 2005 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 06-10, 2005, Banff, Alberta, Canada
• 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: Jean-Yves Le Boudec , Patrick Thiran, Network calculus: a theory of deterministic queuing systems for the internet, Springer-Verlag New York, Inc., New York, NY, 2001
• 13: Jörg Liebeherr , Dallas E. Wrege, Traffic characterization algorithms for VBR video in multimedia networks, Multimedia Systems, v.6 n.4, p.271-283, July 1998 [doi>10.1007/s005300050093]
• 14: Abhay K. Parekh , Robert G. Gallager, A generalized processor sharing approach to flow control in integrated services networks: the single-node case, IEEE/ACM Transactions on Networking (TON), v.1 n.3, p.344-357, June 1993 [doi>10.1109/90.234856]
• 15: Abhay K. Parekh , Robert G. Gallagher, A generalized processor sharing approach to flow control in integrated services networks: the multiple node case, IEEE/ACM Transactions on Networking (TON), v.2 n.2, p.137-150, April 1994 [doi>10.1109/90.298432]
• 16: Scheduling for quality of service guarantees via service curves, Proceedings of the 4th International Conference on Computer Communications and Networks, p.512, September 20-23, 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.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS

General Terms:
Performance

Keywords:
network calculus, packetizers, scaling functions