|
|
|
|
|
Duality of the Max-Plus and Min-Plus Network Calculus
Author(s): Jörg Liebeherr
Source: Journal:Foundations and Trends® in Networking ISSN Print:1554-057X, ISSN Online:1554-0588 Publisher:Now Publishers Volume 11 Number 3-4, Pages: 147(139-282) DOI: 10.1561/1300000059
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.
|
|
|
|