|
Analysis of Available
Bandwidth Measurement Techniques
|
Introduction | Methodology
|
|
Publications | Collaborator
| Links |
Tools | Code
Introduction
As the internet evolves, link speeds
are getting faster and large amounts of data is being transferred over it. As
a result the need to know the spare or unused capacity of a path has become
critical for the proper utilization of network resources. In this
scenario it is conjectured that several applications can benefit from
the knowledge of the Available Bandwidth (AB). For instance:
- Transport Protocols can use the
knowledge to quickly get to the maximum unused capacity.
- Peer-to-Peer and Overlay networks can
use the knowledge of the AB to select better paths
- The knowledge of the AB could be
used for server/source selection.
Many tools have
been designed to measure the AB. Some of them are Pathload, Pathchirp,
Abing, Spruce, IGI/PTR, Cprobe, netest and Iperf. All these tools
work by injecting a "probe stream" into the end-to-end
path. As the "probe stream" interacts with the
cross-traffic on the path, it gets perturbed. The receiver then
analyses these perturbations to infer the AB of the path. This part of the
tool is referred to as the "inference logic". A few applications
which use the knowledge of the AB have also been designed, for
instance SOBAS.
However the area of the AB estimation has many
shortcomings which we have classified into three areas.
- Tool Evaluation: Most tools are accompanied by an
evaluation. However
- There have been no
comprehensive evaluation of all the tools in a common environment.
- Most evaluations have been limited
to paths of 100Mbps or less.
Our
goal in evaluating the tools in two fold. First evaluate the tools as
black boxes under identical test conditions and explain the differences
between the performance of the tools. Second we evaluate the
tool algorithms, independent
of any systemic effects or biases, to evaluate the methodology that can best
estimate the AB. This is because some tools are limited in their
implementations because of systemic limitations.
- Temporal Aspects of the AB: No AB tool currently available gives due
consideration to the temporal aspect of the estimation of the
AB. We identify three temporal quantities- (i) The Measurement
Time-Scale or the length of the stream used to probe for the AB,
(ii) the Sampling Intensity or the number of probes used to make an
inference about the AB, (iii) The Tool Run-time the time after which the
tool returns a measurement. We study the impact of the these
three quantities on the accuracy, variability and stability of the
AB.
- Applications that use the knowledge
of AB: A lot of
work has been put into designing tools that can measure the AB.
However currently the only place where the knowledge of the AB is being
used is in network monitoring applications. Here too,
operators prefer generic tools like "iperf" for measuring
the AB. Our goal is to study the value of adding the
knowledge of AB to certain typical Internet applications, and to study an applications
requirements for the knowledge of the AB. Some applications that
we propose to look at are Bulk-Transfer, Streaming protocols, Overlay
Routing and Source Selection.
Methodology
- Tool Evaluation: In order to
evaluate the tools and design components we use a combination of (i)
experiments in a Laboratory test-bed, (ii) experiments on instrumented
internet paths and (iii) simulations using ns-2. For our black-box
evaluation of the tools we used the laboratory test-bed and instrumented
paths and gained some initial insights into the performance of certain
AB tools. We then used ns-2 simulations in order to evaluate the
efficacy of different probing and inference mechanisms of the AB
tools.
- Temporal Aspects of the AB: One
approach to evaluate the effects of temporal parameters on the AB, is to
use a tool which can perfectly measure the AB of a path. If we
have such a tool we can then vary different temporal parameters and
study the effect this has on the AB. However such a tool does not
exist so this approach is not feasible. Another approach is to
take link level traces and compute the AB from these traces. This
method also gives us perfect knowledge of the AB process. We use
this technique to study the impact of temporal quantities like the
Measurement Time-Scale, Sampling Intensity and Run-Length of a tool on
the Accuracy, Variability and Stability of AB
estimates.
Publications
- Empirical Study on the
Evaluation of Techniques to Measure Available Bandwidth Infocom 2007 (pdf)
- Empirical Study of the Impact of
Sampling Timescales and Strategies on Measurement of Available Bandwidth
PAM 06 (pdf)
- Comparison of Public End-to-End
Bandwidth Estimation Tools on High Speed Links PAM 05 (pdf)
- Identifying Bottleneck Links Using
Distributed End-to-End Available Bandwidth Measurements BEst'03 (doc)
Collaborators
Margaret Murray (TACC), kc
claffy (CAIDA), Marina Fomenkov (CAIDA), Andre Broido(CAIDA currently
at GOOGLE)
Other
links
Schooner Lab Environment
Emulab Experimental Environment
Tools
Pathload
Pathchirp
Spruce
Abing
IGI/PTR
IPERF
Applications
SOBAS:
Socket Buffer Auto-Sizing
AB
in Overlay Networks
Large Scale AB
estimation
CODE
This is the
code that we used in the INFOCOM 2007 study. (.tar.gz)
Instructions:
A couple of points regarding this code.
1) You need to unzip the code in the ns-<version number> ( use
the command "tar -zxvf <filename>") of your ns
installation. It should put all the files in the right places.
A word of caution, this unzip will overwrite file ./tcl/lib/ns-default.tcl, ./tcl/lib/ns-packet.tcl
and ./common/packet.h and makefile.in. Either back those
files up if you have changes that you do not want to loose or you can add in
the things by hand by looking at the contents of the file../* Look for the
string Alok to find out what I changed*/
2) the tool code is present in the directory ./bwtools/
3) the NS-Basic scripts are some basic .tcl scripts to help you figure out
how to invoke the tools.
4) Finally I have built this code on
ns-2.29, and I am not sure how well these changes will hold up in successive
versions or releases of ns.
In case you have any other questions.. let me know and I will do what I can
to help.
Other resources:
-
A set of sample scripts to invoke the
various tools. (.tar.gz)
-
A sample script to run tcp-replay (.tcl)
-
A perl script to convert an ascii trace
to NS-trace replay format (.pl). This script is
modified from the original script written by Pentikousis Kostas (http://ipv6.willab.fi/kostas/)
-
The traces that we used for the study in
binary NS-trace replay format (.tar.gz ) (Caution
Large File 250 Mb)
|