TY - JOUR

T1 - Stochastic Bandwidth Estimation in Networks With Random Service

AU - Lübben, Ralf

AU - Fidler, Markus

AU - Liebeherr, Jörg

PY - 2014/4

Y1 - 2014/4

N2 - Numerous methods for available bandwidth estimation have been developed for wireline networks, and their effectiveness is well-documented. However, most methods fail to predict bandwidth availability reliably in a wireless setting. It is accepted that the increased variability of wireless channel conditions makes bandwidth estimation more difficult. However, a (satisfactory) explanation why these methods are failing is missing. This paper seeks to provide insights into the problem of bandwidth estimation in wireless networks or, more broadly, in networks with random service. We express bandwidth availability in terms of bounding functions with a defined violation probability. Exploiting properties of a stochastic min-plus linear system theory, the task of bandwidth estimation is formulated as inferring an unknown bounding function from measurements of probing traffic. We present derivations showing that simply using the expected value of the available bandwidth in networks with random service leads to a systematic overestimation of the traffic departures. Furthermore, we show that in a multihop setting with random service at each node, available bandwidth estimates requires observations over (in principle infinitely) long time periods. We propose a new estimation method for random service that is based on iterative constant-rate probes that take advantage of statistical methods. We show how our estimation method can be realized to achieve both good accuracy and confidence levels. We evaluate our method for wired single-and multihop networks, as well as for wireless networks.

AB - Numerous methods for available bandwidth estimation have been developed for wireline networks, and their effectiveness is well-documented. However, most methods fail to predict bandwidth availability reliably in a wireless setting. It is accepted that the increased variability of wireless channel conditions makes bandwidth estimation more difficult. However, a (satisfactory) explanation why these methods are failing is missing. This paper seeks to provide insights into the problem of bandwidth estimation in wireless networks or, more broadly, in networks with random service. We express bandwidth availability in terms of bounding functions with a defined violation probability. Exploiting properties of a stochastic min-plus linear system theory, the task of bandwidth estimation is formulated as inferring an unknown bounding function from measurements of probing traffic. We present derivations showing that simply using the expected value of the available bandwidth in networks with random service leads to a systematic overestimation of the traffic departures. Furthermore, we show that in a multihop setting with random service at each node, available bandwidth estimates requires observations over (in principle infinitely) long time periods. We propose a new estimation method for random service that is based on iterative constant-rate probes that take advantage of statistical methods. We show how our estimation method can be realized to achieve both good accuracy and confidence levels. We evaluate our method for wired single-and multihop networks, as well as for wireless networks.

KW - Bandwidth estimation

KW - communications technology

KW - computer networks

KW - IP networks

KW - random systems

KW - stochastic network calculus

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

U2 - 10.1109/TNET.2013.2261914

DO - 10.1109/TNET.2013.2261914

M3 - Article

AN - SCOPUS:84899563954

VL - 22

SP - 484

EP - 497

JO - IEEE/ACM Transactions on Networking

JF - IEEE/ACM Transactions on Networking

SN - 1063-6692

IS - 2

M1 - 6517905

ER -