End-to-end Available Bandwidth Estimation and its Applications

Abstract

As the Internet continues to evolve, without providing any performance guarantees or explicit feedback to applications, the only way to infer the state of the network and to dynamically react to congestion is through end-to-end measurements. The emph{available bandwidth} (avail-bw) is an important metric that characterizes the dynamic state of a network path. Its measurement has been the focus of significant research during the last 15 years. However, its estimation remained elusive for several reasons. The main contribution of this thesis is the development of the first estimation methodology for the avail-bw in a network path using end-to-end measurements. In more detail, our first contribution is an end-to-end methodology, called SLoPS, to determine whether the avail-bw is larger than a given rate based on the sequence of one-way delays experienced by a periodic packet stream. The second contribution is the design of two algorithms, based on SLoPS, to estimate the mean and the variation range, respectively, of the avail-bw process. These algorithms have been implemented in two measurement tools, referred to as PathLoad and PathVar. We have validated the accuracy of the tools using analysis, simulation, and extensive experimentation. Pathload has been downloaded by more than 6000 users since 2003. We have also used PathVar to study the variability of the avail-bw process as a function of various important factors, including traffic load and degree of multiplexing. Finally, we present an application of avail-bw estimation in video streaming. Specifically, we show that avail-bw measurements can be used in the dynamic selection of the best possible overlay path. The proposed scheme results in better perceived video quality than path selection algorithms that rely on jitter or loss-rate measurements.