Analysis of Available Bandwidth Measurement Techniques
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.
- 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.
- 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)
Margaret Murray (TACC)
KC Claffy (CAIDA)
Marina Fomenkov (CAIDA)
Andre Broido (CAIDA currently at GOOGLE)
SOBAS : Socket Buffer Auto-Sizing
This is the code that we used in the INFOCOM 2007 study. ( .tar.gz )
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.
If you have any other questions, please let me know and I will do what I can to help.
A set of sample scripts to invoke the various tools. (. tar.gz )
A sample script to run tcp-replay (. tcl)
The traces that we used for the study in binary NS-trace replay format ( .tar.gz ) (Caution Large File 250 Mb)