A system-theoretic approach to bandwidth estimation

This paper presents a new foundational approach to reason about available bandwidth estimation as the analysis of a min-plus linear system. The available bandwidth of a link or complete path is expressed in terms of a service curve, which is a function that appears in the network calculus to express the service available to a traffic flow. The service curve is estimated based on measurements of a sequence of probing packets or passive measurements of a sample path of arrivals. It is shown that existing bandwidth estimation methods can be derived in the min-plus algebra of the network calculus, thus providing further mathematical justification for these methods. Principal difficulties of estimating available bandwidth from measurements of network probes are related to potential nonlinearities of the underlying network. When networks are viewed as systems that operate either in a linear or in a nonlinear regime, it is argued that probing schemes extract the most information at a point when the network crosses from a linear to a nonlinear regime. Experiments on the Emulab testbed at the University of Utah, Salt Lake City, evaluate the robustness of the system-theoretic interpretation of networks in practice. Multinode experiments evaluate how well the convolution operation of the min-plus algebra provides estimates for the available bandwidth of a path from estimates of individual links.