Network calculus. A theory of deterministic queueing systems for the Internet. (English) Zbl 0974.90003

Lecture Notes in Computer Science. 2050. Berlin: Springer. xix, 274 p. (2001).
The monograph under review represents a comprehensive and up-to-date treatment of a fast growing and topical area of modern network calculus. Network calculus provides deep insights into concurrent programs, digital circuits, communication networks and Petri nets. Its foundation lies in the mathematical theory of dioids. It leads to a better understanding of integrated services networks, window flow control and buffer dimensioning.
This book is organized in three parts. Part I (Chapters 1 and 2) is a self contained first course on network calculus and can be used at the undergraduate level. Chapter 1 deals with arrival and service curves, concatation and shapers. Chapter 2 presents the applications of network calculus relevant to network engineers.
Part II describes the mathematical background such as min-plus convolution and sub-additive closure. Chapter 3 introduces in detail the basic concepts of min-plus and max-plus algebras and the operations, convolution, deconvolution and subadditive closure. Chapter 4 focuses on min-plus system theory. Max-plus system theories as developed in F. L. Baccelli, G. Cohen , G. J. Olsder and J.-P. Quadrat [Synchronization and linearity, An Algebra of Discrete Event Systems, John Wiley and Sons (1992; Zbl 0824.93003)] follows by replacing minimum by maximum and infimum by supremum.
Part III surveys the state of the art of research and points to open problems in network calculus and its applications in different fields such as multimedia smoothing, aggregate scheduling, adaptive guarantees in Internet differential services, renogiated reserved services and losses in flow systems.
Chapter 5 applies network calculus to smooth multimedia data over a network offering reservation based services, such as ATM or RSVP/IP, for which there exists one minimal service curve. The authors employ a novel and effective approach to smooth the video stream using a smoother fed by the encoder and compute the minimal client buffer size required given a maximal peak rate.
In Chapter 6, the authors present a panorama of new results in aggregate scheduling. Chapter 7 analyzes adaptive guarantees that are used by the Internet differentiated services. Chapter 8 deals in detail time varying shapers and obtain explicit results for shapers made of a conjunction of leaky buckets. Chapter 9 shows that network calculus can also be applied to lossy systems using a ’clipper’ to a lossless system.
This well-written book provides an elegant and serious introduction to the basic concepts and results of network calculus. In addition, there is a whole set of largely unexplored fundamental relations that can be obtained in this book. Concepts such as ’shapers keep arrival constraints’ and ’pay burst only once’ are of practical importance to network engineers. The authors have evidently paid great attention to the presentation of the material and the prerequisites are not too high. The treatment is not only appropriate for understanding, but even more effective. I believe this book will inspire further research and can be strongly recommended to researchers and graduate students involved in communication.


90B18 Communication networks in operations research
90-02 Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming
68-02 Research exposition (monographs, survey articles) pertaining to computer science
68M10 Network design and communication in computer systems
68M11 Internet topics
68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
68Q85 Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)
90B22 Queues and service in operations research


Zbl 0824.93003
Full Text: DOI