Details
| Original language | English |
|---|---|
| Article number | 5342449 |
| Pages (from-to) | 1040-1053 |
| Number of pages | 14 |
| Journal | IEEE/ACM Transactions on Networking |
| Volume | 18 |
| Issue number | 4 |
| Early online date | 3 Jan 2008 |
| Publication status | Published - Aug 2010 |
Abstract
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.
Keywords
- Bandwidth estimation, min-plus algebra, network calculus
ASJC Scopus subject areas
- Computer Science(all)
- Software
- Computer Science(all)
- Computer Science Applications
- Computer Science(all)
- Computer Networks and Communications
- Engineering(all)
- Electrical and Electronic Engineering
Cite this
- Standard
- Harvard
- Apa
- Vancouver
- BibTeX
- RIS
In: IEEE/ACM Transactions on Networking, Vol. 18, No. 4, 5342449, 08.2010, p. 1040-1053.
Research output: Contribution to journal › Article › Research › peer review
}
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 -