Network Calculus

The book

The Network Calculus book by Jean-Yves Le Boudec and Patrick Thiran is available for free download: part I (PDF), parts II and III (PDF).

It is also available soon as Springer-Verlag Lecture Notes on Computer Science number 2050. We are very grateful to Springer-Verlag for this generous arrangement.

What is Network Calculus ?

Network Calculus is a collection of results based on Min-Plus algebra, which applies to deterministic queuing systems found in communication networks. It can be used for example to understand

• the computations for delays used in the IETF guaranteed service
• why re-shaping delays can be ignored in shapers or spacer-controllers
• a common model for schedulers
• deterministic effective bandwidth
• and much more.

If you want to learn more about this exciting topic, read the Network Calculus book. It is available for free download.

Network Calculus is also the name of a project at EPFL/ICA.

About this page:

This page contains pointers to :

• results of the EPFL project called "network calculus"
• state of the art material related to the project.

This page is maintained at http://ica1www.epfl.ch/PS_files/NetCal.htm by jean-yves.leboudec@epfl.ch. If you would like to contribute with a pointer, please send me an email.

References

Four sources introduced in parallel the concepts of service curve. These are:

• H. Sariowan, R. L. Cruz, and G. C. Polyzos, "Scheduling for Quality of Service Guarantees via Service Curves," Proceedings of the International Conference on Computer Communications and Networks (ICCCN) 1995, Las Vegas, September 20-23, 1995, pp. 512-520. Full paper (211K,postscript).
• "Application of Network Calculus To Guaranteed Service Networks", JY Le Boudec, IEEE Trans on Information theory, (44) 3, May 1998 (introductory material)
• "On deterministic traffic regulation and service guarantee: Asystematic approach by filtering", IEEE TIT vol 44, May 98, pp 913--931. One of the papers which introduced (in parallel to Agrawal, Cruz, Okino, Rajan on one hand, Le Boudec on the other hand) the concepts of service curve. Uses the language of filtering theory, or traditional linear systems. Unlike the other authors mentioned above, uses discrete time, which simplifies the approach, probably without any loss of generality (we call this the time method, as opposed to the space method).
• " Performance Bounds for Flow Control Protocols", R. Agrawal, R. L. Cruz, C. Okino and R. Rajan, IEEE ToN vol 7, No3, June 99, pp 310--323. " The service curve theory, applied to flow control protocols.

The four papers above were based on Cruz's original contribution, which itself built upon the service curve concept introduced by Parekh and Gallager:

• Parekh, A. K., & Gallager, R. G., "A Generalized Processor Sharing Approach to flow control in Integrated Services Networks - The Multiple Node Case," IEEE/ACM Transactions on Networking, Vol 2 #1, pp 137-150, April 1994. Contains the seminal definition of service curves.
• R. L. Cruz, "Quality of Service Guarantees in Virtual Circuit Switched Networks," IEEE Journal of Selected Areas in Communication, special issue on "Advances in the Fundamentals of Networking" (vol. 13 no. 6), August, 1995 Full paper (529K,postscript). First attempt to generalize Parekh, A. K., & Gallager's service curve.

More:

• H. Sariowan, "A Service-Curve Approach to Performance Guarantees in Integrated-Service Networks," Ph.D. thesis, Department of Electrical & Computer Engineering, UCSD, June, 1996. Full thesis (1M,postscript).
• "SCED+. Efficient Management of Quality of Service Guarantees", R.L. Cruz, Proc Infocom 98, March 1998
  Introduces the concept of "maximum service curve". Applies to a method for guaranteeing end to end bounds on delay jitter, using the SCED+ scheduling method. With SCED+, every packet carries information about its lateness and nodes delay packets that are too early. A benefit is for best effort traffic which then gets lower delay. Introduces the concept of "damper".
• R. Agrawal, F. Baccelli, R. Rajan, `` An Algebra for Queueing Networks with Time Varying Service and its application to the analysis of integrated service networks,'' Technical Report ECE-98-2, ECE Dept., University of Wisconsin - Madison, May 1998. (Also INRIA Report 3435.)
• Stochastic Aspects: a starting point is R. Boorstyn, A. Burchard, J. Liebeherr, and C. Oottamakorn, University of Virginia, Department of Computer Science, CS-99-21, July 1999: Statistical Multiplexing Gain of Link Scheduling Algorithms in QoS Networks