Foundations and Trends® in Networking > Vol 11 > Issue 3-4

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

By Jörg Liebeherr, University of Toronto, Canada, jorg@ece.utoronto.ca

 
Suggested Citation
Jörg Liebeherr (2017), "Duality of the Max-Plus and Min-Plus Network Calculus", Foundations and Trends® in Networking: Vol. 11: No. 3-4, pp 139-282. http://dx.doi.org/10.1561/1300000059

Publication Date: 10 Jul 2017
© 2017 J. Liebeherr
 
Subjects
Modeling and Analysis,  Data networks,  Queuing Theory,  Systems Theory,  Performance
 

Free Preview:

Download extract

Share

Download article
In this article:
1. Introduction
2. Motivation
3. Modelling Traffic Arrivals in the Space Domain
4. Max-Plus Algebra of Functions
5. Backlog and Delay in the Space Domain
6. Max-Plus Traffic Envelopes and Traffic Regulators
7. Service Curves in the Max-Plus Network Calculus
8. Performance Bounds
9. A Summary of the Min-Plus Network Calculus
10. Isomorphism between the Min-Plus and Max-Plus Algebra
11. Min-plus and Max-plus Duality in the Network Calculus
12. Scheduling for Rate and Delay Guarantees
13. Related Literature
14. Conclusions
Appendices
References

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.

DOI:10.1561/1300000059
ISBN: 978-1-68083-294-5
156 pp. $99.00
Buy book (pb)
 
ISBN: 978-1-68083-295-2
156 pp. $260.00
Buy E-book (.pdf)
Table of contents:
1. Introduction
2. Motivation
3. Modelling Traffic Arrivals in the Space Domain
4. Max-Plus Algebra of Functions
5. Backlog and Delay in the Space Domain
6. Max-Plus Traffic Envelopes and Traffic Regulators
7. Service Curves in the Max-Plus Network Calculus
8. Performance Bounds
9. A Summary of the Min-Plus Network Calculus
10. Isomorphism between the Min-Plus and Max-Plus Algebra
11. Min-plus and Max-plus Duality in the Network Calculus
12. Scheduling for Rate and Delay Guarantees
13. Related Literature
14. Conclusions
Appendices
References

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.

 
NET-059