TY - JOUR

T1 - A System-Theoretic Approach to Bandwidth Estimation

AU - Liebeherr, Jörg

AU - Fidler, Markus

AU - Valaee, Shahrokh

N1 - Funding information: Manuscript received December 31, 2007; revised September 22, 2008 and June 23, 2009; approved by IEEE/ACM TRANSACTIONS ON NETWORKING Editor N. Duffield. First published December 01, 2009; current version published August 18, 2010. This work was supported in part by the National Science Foundation under Grant CNS-0435061, grants from the Natural Sciences and Engineering Council of Canada (NSERC), and an Emmy Noether grant from the German Research Foundation. This is an extended version of a paper that appeared in the Proceedings of IEEE INFOCOM 2007.

PY - 2010/8

Y1 - 2010/8

N2 - 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.

AB - 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.

KW - Bandwidth estimation

KW - min-plus algebra

KW - network calculus

UR - http://www.scopus.com/inward/record.url?scp=77955775110&partnerID=8YFLogxK

U2 - 10.1109/TNET.2009.2035115

DO - 10.1109/TNET.2009.2035115

M3 - Article

AN - SCOPUS:77955775110

VL - 18

SP - 1040

EP - 1053

JO - IEEE/ACM Transactions on Networking

JF - IEEE/ACM Transactions on Networking

SN - 1063-6692

IS - 4

M1 - 5342449

ER -