Bandwidth Estimation: Issues and Approaches

Proposal for a Bandwidth Estimation Testbed

Bandwidth estimation is a problematic measurement where accuracy is difficult to achieve, particularly in high-speed networks. Several tools are available that use various strategies for estimating bandwidth, and some have been tested. However, more testing is needed to fully understand the impact of using different tools in particular configurations or contexts.

Bandwidth / Throughput Measurement Tools

Tool	Input	Measurement				Output
		Active / Passive	Functions	Time Scope	Aggregate Scope
bing	compare RTTs from ICMP/ECHO reply of different size pkts	active	raw bandwidth	real-time	none	raw capacity (bps)
{b\|c}probe	ICMP/ECHO reply	active	bandwidth, congestion	real-time	none	text
clink	UDP w/limited TTL to unused port; ICMP err response or ICMP/ECHO reply	active	bandwidth	real-time	none	text
netperf	UDP w/limited TTL; ICMP time exceeded	active	uni-directional throughput, end-to-end latency	real-time	> 60 secs	text
nettimer	pkt collection; pkt tailgating	both	pkt capture server, pkt capture client, active probe (tailgater)	real-time	two phases for pkt tailgating: entire path scanned once; active probes in tailgating phase until confidence interval reached for measuring link chars	records; space delimited fields in ns trace file format
pathchar	UDP; ICMP	both	bandwidth, throughput, latency, loss, queue chars	real-time	various	GUI
pathrate	UDP based, running from client to sink	active	absolute capacity (bottleneck bandwidth)	real-time	not applicable	absolute capacity (range between a low and high estimate)
pchar	UDP; ICMP	both	bandwidth, throughput, latency, loss, queue chars	real-time	various	GUI
TReno	UDP w/limited TTL to unused port; ICMP err response or ICMP/ECHO reply	both	bandwidth	real-time	none	gnuplot and ppmtogif graphs
ttcp and nttcp	load generator	active	throughput	real-time	none	text

Talks and Papers

nettimer

nettimer uses a technique called 'packet tailgating' to actively measure link bandwidths.

Kevin Lai and Mary Baker. "Measuring Link Bandwidths Using a Deterministic Model of Packet Delay"

Packet tailgating sends an order of magnitude fewer packets, while maintaining approximately the same accuracy as previous bandwidth estimation methods. It does not rely on consistent behavior of routers handling ICMP packets, and does not rely on timely delivery of acknowledgements. Advantages of this technique are its speed, unobtrusiveness, robustness, and ability to handle multiple channels. Disadvantages are its need to send packets back-to-back on the first link, its inability to measure a very fast link after a very slow link, the fact that queuing anywhere along the path disrupts the measurement of all links on the path, and the accumulation of errors in the calculation. Additionally, although nettimer gets timing information directly from the kernel using libpcap instead of the application level, this technique couldn't be extended accross many different NIC drivers. Thus, while the application-kernel node can be removed from the measured path, bridges remain invisible and are not taken into account. This paper includes a comparison of results from four bandwidth estimation tools: nettimer, pathchar, clink, and pchar. Results from both short path (3 hops) and long path (10 hops) measurements are given for each tool on channels of known physical bandwidth.

pathchar

Pathchar (written by Van Jacobon) is a tool that infers (estimates) the characteristics of links along an Internet path.

Van Jacobson, MSRI talk on pathchar (.pdf)
Van Jacobson, MSRI talk on pathchar (.ps.gz)

In this talk, given at the Mathematical Sciences Research Institute (MSRI), Jacobson discusses pathchar strategy as well as specific implementation difficulties.
Kazumine Matoba, Shigo Ata, and Masayuki Murata. "Improving Bandwidth Estimation for Internet Links by Statistical Methods" submitted to ITC, March 2000. (.pdf) [Link no longer available]

This paper focuses on how pathchar's assumption that errors follow a normal distribution affects the accuracy of bandwidth estimation for unexpectedly large errors. Two alternative methods to pathchar's linear least square fitting approach are discussed and evaluated. A parametric approach using an M-estimation method with a Tukey's biweight function is found to be more efficient, yet still inaccurately handles unexpectedly large errors. In contrast, a nonparametric approach using either the Wilcoxon or Kendall method does not exhibit this limitation. Problems with measurement noise and link-layer load-balancing are also discussed.

clink

Allen B. Downey. "Using pathchar to estimate Internet link characteristics" SIGCOMM '99 (.ps and .pdf)
Allen Downey's clink page

clink is a variant of pathchar. Primary differences between pathchar and clink are: 1) clink uses an even-odd technique to generate interval estimates for bandwidth; and 2) when clink encounters a routing instability, it collects data for ALL the paths it encounters until one of those paths generates enough data to yield an estimate.

pathrate

Constantinos Dovrolis, Parameswaran Ramanathan, and David Moore. "What does the dispersion of packet pairs and trains measure?"

This paper, accepted for INFOCOMM 2001, studies the dispersion (spacing) of back-to-back packet pairs and packet trains, focusing on the effects of the cross traffic.