Survey of deterministic and stochastic service curve models in the network calculus

TLDR

Service curves provide a versatile model for performance analysis of network elements and entire networks, using min‑plus algebra convolution formulas to determine departures from arrivals and enabling concatenation of tandem systems into a single network service curve. This paper surveys the state‑of‑the‑art deterministic and probabilistic network calculus. It reviews service‑curve concepts, their use in network calculus, identification methods from measurements, and stochastic models derived from time‑varying min‑plus systems theory. These models enable statistical multiplexing gains in a network‑calculus framework that performs end‑to‑end analysis by convolution of service curves.

Abstract

In recent years service curves have proven a powerful and versatile model for performance analysis of network elements, such as schedulers, links, and traffic shapers, up to entire computer networks, like the Internet. The elegance of the concept of service curve is due to intuitive convolution formulas that determine the data departures of a system from its arrivals and its service curve. This fundamental relation constitutes the basis of the network calculus and relates it to systems theory, however, under a different, so-called min-plus algebra. As in systems theory, the particular strength of the minplus convolution is the ability to concatenate tandem systems along a network path. This facilitates the notion of network service curve that has the expressiveness to characterize whole networks by a single transfer function. This paper surveys the state-of-the-art of the deterministic and the recent probabilistic network calculus. It discusses the concept of service curves, its use in the network calculus, and the relation to systems theory under the min-plus algebra. Service curve models of common schedulers and different types of networks are reviewed and methods for identification of a system's service curve representation from measurements are discussed. After recapitulating the state of knowledge on time-varying min-plus systems theory, stochastic service curve models are surveyed. These models allow utilizing the statistical multiplexing gain in a network calculus framework that features end-to-end network analysis by convolution of service curves.