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

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.