Ten fallacies and pitfalls on end-to-end available bandwidth estimation

Manish Jain, Constantinos DovrolisInternet Measurement Conference 2004 · DOI

TL;DR

This paper dissects common misconceptions in estimating available network bandwidth, a crucial metric for performance analysis and optimization. By clarifying definitions and identifying ten "fallacies and pitfalls," the authors aim to foster a more accurate understanding and practical application of these estimation techniques.

What Problem Does This Paper Address?

Estimating the available bandwidth (avail-bw) of an end-to-end network path is vital for understanding network performance, diagnosing issues, and optimizing applications like TCP. While numerous techniques and tools have emerged, the authors observe that fundamental aspects of avail-bw definition, estimation, and validation are often misunderstood or misinterpreted. This leads to inaccurate measurements, flawed comparisons between tools, and ultimately, a less effective use of this important metric. The paper aims to address this by clarifying these ambiguities and highlighting common pitfalls that researchers and practitioners fall into.

Methods

The paper categorizes existing avail-bw estimation techniques into two main approaches:

  • Direct Probing: These methods send probing packets and directly infer the avail-bw based on observed packet behavior (e.g., output rate vs. input rate). An example is Delphi, which assumes a multifractal cross-traffic model.
  • Iterative Probing: These techniques don't directly measure avail-bw but rather determine if a probing rate is above or below the avail-bw. By iteratively adjusting the probing rate, they converge to an estimate. Examples include TOPP and Pathload.

The authors then systematically identify and explain ten "fallacies and pitfalls," which are essentially common misunderstandings or overlooked factors that can lead to inaccurate avail-bw estimates. These include issues related to statistical variability, the impact of probing duration, the assumptions underlying queueing models, and the influence of real-world network conditions like traffic burstiness and multiple bottlenecks.

Datasets

The paper discusses simulations and uses a specific NLANR packet trace (ANL-1070432720) for analysis. This trace is described as providing accurate knowledge of the avail-bw process across a range of time scales.

Key Insights and Ideas

  • Avail-bw is a Dynamic Process: Avail-bw isn't a static value but a random process that varies over time. Its variance decreases with longer averaging time scales, a statistical fact often ignored in comparisons.
  • Probing Duration Matters: The duration of a probing stream directly controls the averaging time scale (τ), which in turn affects the variance of the estimated avail-bw. This relationship is crucial and often overlooked.
  • Faster Isn't Always Better: Tools that aim for faster estimation by using shorter streams or fewer samples often sacrifice accuracy due to increased statistical variance.
  • Packet Pairs vs. Trains: While theoretically equivalent under fluid traffic, packet pairs can be significantly inaccurate in practice when cross traffic consists of larger packets.
  • Tight Link Capacity is Tricky: Direct probing methods often assume knowledge of the "tight link" capacity. End-to-end capacity estimation tools might estimate the narrow link capacity, which can be smaller and lead to underestimation.
  • Burstiness and Multiple Bottlenecks Cause Underestimation: Real-world traffic burstiness and the presence of multiple bottlenecks can cause queues to build up even when the probing rate is below the theoretical avail-bw, leading to significant underestimation errors.
  • OWD Trends are Richer: While increasing One-Way Delays (OWDs) can indicate Ri > A, analyzing the trend of OWDs provides more information than just the average input/output rate ratio, especially in the presence of bursty traffic.
  • Iterative Probing Yields Ranges, Not Single Values: Iterative probing converges to a range of possible avail-bw values, reflecting the dynamic nature of the process, rather than a single precise estimate.

Key Results

The paper doesn't present a single quantitative result but rather uses simulations and trace analysis to illustrate the impact of the identified fallacies. For example:

  • Figure 1 shows that with only 20 samples, significant relative errors in the sample mean can occur, especially for shorter averaging time scales (e.g., 1ms).
  • Table 1 demonstrates that the relative error of avail-bw estimation increases significantly with larger cross-traffic packet sizes (e.g., 1500B) when using packet pairs.
  • Figure 3 illustrates how traffic burstiness (Poisson and Pareto ON-OFF) causes the Ro/Ri ratio to drop below 1.0 much earlier than with constant-bit-rate traffic, leading to underestimation.
  • Figure 4 shows that increasing the number of tight links in a path further exacerbates underestimation errors.
  • Figure 5 provides a visual comparison of OWDs, highlighting how burstiness can affect the output rate even when Ri < A.
  • Figure 6 shows a sample avail-bw path varying significantly over time, emphasizing that iterative probing estimates a range.

Limitations and Future Work

The authors acknowledge that their objective is to clarify issues and foster better understanding, not to debunk specific tools. They suggest that future work could explore:

  • Developing improved estimation techniques or statistical processing methods to address underestimation errors caused by traffic burstiness and multiple bottlenecks.
  • Establishing reproducible and controllable conditions for comparing estimation techniques, using consistent parameters.
  • Integrating avail-bw estimation into actual applications to evaluate their effectiveness under real-world accuracy and latency constraints.

Summary updated

BibTeX
@inproceedings{jain2004ten,
  author = {Manish Jain and Constantinos Dovrolis},
  title = {{Ten fallacies and pitfalls on end-to-end available bandwidth estimation}},
  booktitle = {Internet Measurement Conference},
  year = {2004},
  doi = {10.1145/1028788.1028825},
}
Figure