Abstract

The network calculus is a framework for the analysis of communication networks, which exploits that many computer network models become tractable for analysis if they are expressed in a min-plus or max-plus algebra. In a min-plus algebra, the network calculus characterizes amounts of traffic and available service as functions of time. In a max-plus algebra, the network calculus works with functions that express the arrival and departure times or the required service time for a given amount of traffic. While the min-plus network calculus is more convenient for capacity provisioning in a network, the max-plus network calculus is more compatible with traffic control algorithms that involve the computation of timestamps. Many similarities and relationships between the two versions of the network calculus are known, yet they are largely viewed as distinct analytical approaches with different capabilities and limitations. We show that there exists a one-to-one correspondence between the min-plus and max-plus network calculus, as long as traffic and service are described by functions with real-valued domains and ranges. Consequently, results from one version of the network calculus can be readily applied for computations in the other version. The ability to switch between min-plus and max-plus analysis without any loss of accuracy provides additional flexibility for characterizing and analyzing traffic control algorithms. This flexibility is exploited for gaining new insights into link scheduling algorithms that offer rate and delay guarantees to traffic flows.

Duality of the Max-Plus and Min-Plus Network Calculus

Network calculus is a methodology for performance evaluation of communication networks that expresses the analysis of networks in a min-plus or max-plus algebra. In these algebras, the conventional addition and multiplication operations are replaced by the minimum or maximum operation, respectively, and addition.

This monograph gives an accessible and concise review of the research conducted in Network Calculus to date. In doing so, it unearths the question: why are min-plus and max-plus calculus not isomorphic whereas the underlying min-plus and max-plus algebras upon which they are based are? This question is fully investigated and the differences between a max-plus and min-plus analysis are presented. This enables scheduling algorithms with rate and delay guarantees by service curves of the network calculus to be characterized, leading to useful results for their use in network research.

The monograph is of interest to students and researchers working on the mathematical theory of networks.