|
ABOUT |
|
Stochastic models of bandwidth estimation
Abstract
Estimation of available and bottleneck bandwidth is an important task in many end-user applications and network monitoring tools. The goal of bandwidth estimation is to infer the residual rate available in the path and the speed of the slowest link using end-to-end measurements. This is usually accomplished by injecting a sequence of probe packets into the path in question and monitoring their output dispersion at the end of the path. Under certain mild assumptions on cross-traffic, available bandwidth and capacity of the slowest link can be extracted from the inter-packet spacing of probe traffic at the receiver. Unlike prior work that relies on fluid models of cross-traffic, this project studies bandwidth estimation using stochastic (i.e., packet-level) cross-traffic arrival and explains why existing fluid-based tools often do not perform well in practice.
Journal Papers
|
||||
|
||||
|
Conference Papers
|
|
|
|||
|
PDF, PPT | |||
|
||||
|
||||
|
||||
|
||||
|
||||
|
Detailed Project Description
Background
Over the last several years, bandwidth estimation based on end-to-end packet-train probing has attracted significant interest. To understand the various characteristics of the available-bandwidth bottleneck link (i.e., the tight link) and improve end-to-end performance of many applications, a number of techniques have been proposed to measure the cross-traffic rate, residual bandwidth, raw capacity, and location of the tight link. Some of the representative tools are listed in the following table:
|
Tool |
Measurement goal | Maintained by |
| pathload | Available bandwidth | Dovrolis et al. at Gatech |
| IGI/PTR | Available bandwidth, cross-traffic | Hu et al. at CMU |
| Spruce | Available bandwidth | Strauss et al. at MIT |
| pathChirp | Available bandwidth | Ribeiro et al. at Rice |
| Delphi | Cross-traffic | Ribeiro et al. at Rice |
| TOPP | Available bandwidth, tight link capacity | Melander et al. |
| pathneck | Tight link location | Hu et al. at CMU |
| STAB | Tight link location | Ribeiro et al. at Rice |
| Bfind | Tight link location, available bandwidth | Akella et al. at CMU |
Many existing methods, however, are based on a deterministic analytical model that assumes a single-hop path and constant-rate fluid cross-traffic arrival, as illustrated in Figure 1 below. Such a model leads to a deterministic relationship between the input and output signals (inter-packet dispersions or probing rates) carried by the packet-train. Figure 2 shows one form of the single-hop fluid response curve, depicting the mathematical dependency between the ratio of the input and output probing rates and the input rate.
Figure 1: In a single-hop fluid model, cross-traffic has infinitely small packet size and arrives at the hop at a constant rate.
Figure 2: One form of the single-hop fluid response curve.
The single-hop fluid response curve is an important theoretical foundation, based on which a number of existing techniques are designed to measure tight-link bandwidth characteristics over a multi-hop path. These techniques assume that the single-hop fluid curve is a valid first-order approximation of the real situation, largely neglecting cross-traffic burstiness and the effect of non-tight links.
Overview of the Stochastic Foundation
To expand the vision scope offered by the single-hop fluid model and understand the impact of the various factors (e.g., cross-traffic burstiness, packet-train parameters, and multi-hop effects) on the measurement accuracy of existing techniques, we established a stochastic foundation of bandwidth estimation using packet-level bursty cross-traffic models. This foundation includes the following major results:
 |
A mathematical expression of the statistical mean of the output probing signal as a function of the input signal (called the stochastic response curve of the path). |
|
An investigation of the deviation phenomenon between the stochastic response curve and its fluid counterpart. |
|
Examination of the relationship between the response deviation and various factors such as input probing rate, cross-traffic burstiness, packet-train parameters, multi-hop path settings, and the cross-traffic routing pattern. |
|
Identification of the measurement bias caused by the response deviation phenomenon to existing techniques and ways to reduce this bias. |
Single-Hop Case with High Input Rates
Our initial effort in this work focused on the analysis of the output packet-train spacing of a single node when the input spacing was small (i.e., input rate larger than link capacity C). We obtained several important results and documented them in detail in a paper published in ICNP 2004:
|
We derived a closed-form expression of the mean output spacing and showed that the result agreed with the single-hop fluid curve in the high input rate range when the constant cross-traffic rate in the fluid model is replaced by the long-term average rate in the stochastic model. |
|
We showed that this agreement holds for almost any type of cross-traffic as long as its long-term average rate exists. The result also holds for any packet-train parameters. |
|
We proposed two unbiased estimators to measure the capacity and available bandwidth of a single-hop path and showed their asymptotic accuracies. |
Single-Hop Case with Arbitrary Input Rates
In this work, we derived the average output spacing for arbitrary input spacings, uncovering the full picture of the single-hop stochastic response curve. Among many other findings, we obtained the following major results:
|
We showed that when the input rate was less than the link capacity, the average output spacing was larger than the fluid prediction. This led to the response deviation phenomenon in certain input-rate ranges. |
|
We showed that the response deviation vanished when packet-train length or probing packet-size increased and that the vanishing rate was decided by cross-traffic burstiness. |
|
We proposed a method to accurately compute the single-hop stochastic curve from a given cross-traffic trace, enabling an effective experimental observation of our analytical results. |
The single-hop stochastic curve and the response deviation phenomenon is illustrated in Figure 3. Details of these results were reported in IMC 2004 and INFOCOM 2005.
Figure 3: The single-hop stochastic-response curve (blue) deviates from the fluid-response curve (red) in the middle input-rate range from some constant alpha to capacity C.
Multi-Hop Analysis with Arbitrarily Routed Cross-Traffic Flows
In this work, we derived the average output spacing for an arbitrary input into a multi-hop path with arbitrarily routed bursty (but stationary) cross-traffic flows. We investigated the relationship among the three response curves: the multi-hop stochastic response curve, its fluid counterpart, and the single-hop fluid response curve associated with the tight link. Our main results are:
|
The multi-hop stochastic curve is tightly lower bounded by its fluid counterpart. The deviation between these two curve is elastic and vanishes as packet-train length or probing packet-size increases. |
|
The multi-hop fluid curve is piece-wise linear and is lower bounded by the single-hop fluid curve of the tight link. The deviation between these two curves are non-elastic and stays constant for any packet-train parameters. This deviation is affected by the cross-traffic routing pattern. |
|
The two types of curve deviations cause two types of measurement biases to existing techniques. The bias caused by elastic deviation can be overcome using long packet-trains. |
The relationship among the three response curves and the two types of curve deviations are illustrated in the Figure 4. Details of these results were reported in IMC 2005.
Figure 4: Illustration of the multi-hop stochastic response curve (blue), the multi-hop fluid response curve (green), and the single-hop fluid curve (red). In the figure, A is the available bandwidth of the path and A2 is the available bandwidth of the remaining hops.
Internet Measurements of Multi-Hop Response Curves
We conducted an extensive measurement of multi-hop response curves for a total of 272 paths in the RON testbed. This study not only confirmed the validity of our multi-hop stochastic foundation, but also showed that the stochastic curves sufficiently converged to their fluid lower bounds with just 10-40 packets in each probing train. This result enables accurate estimation of tight-link capacity and utilization from measured stochastic curves using trains of moderate size. More details of this study can be found in our PAM 2006 paper.