Introduction

A common complaint about the Internet is that it is slow. Some of this slowness is due to properties of the end points, like slow servers, but some is due to properties of the network, like propagation delay and limited bandwidth. Propagation delay can be measured using widely deployed and well understood algorithms implemented in tools like ping and traceroute. Unfortunately, tools to measure bandwidth are neither widely deployed nor well understood. This work attempts to develop further understanding of how to measure bandwidth.

Current bandwidth measurement techniques have many problems: poor accuracy, poor scalability, lack of statistical robustness, poor agility in adapting to bandwidth changes, lack of flexibility in deployment, and inaccuracy when used on a variety of traffic types. We propose solutions to these problems and demonstrate their effectiveness:

Packet Window

We use a packet window (not the TCP window) to adapt quickly to bandwidth changes. In the presence of link failure, a small window is 144% more accurate than an infinite window.

Receiver Only Packet Pair

We use Receiver Only Packet Pair to allow the deployment of special software at only one host while achieving accuracy within 1% of Receiver Based Packet Pair [12].

Potential Bandwidth Filtering

We use Potential Bandwidth Filtering to measure bandwidth accurately in the presence of a variety of packet sizes. In such an environment, it is at least 37% more accurate than previously used filtering algorithms [5] [12].

Our overall goal is to make Packet Pair algorithms practical and robust enough to be widely and frequently used. Our approach has been to derive simple algorithms from statistically valid network models and avoid heuristics. Heuristics, especially in combination, tend to be difficult to debug and explain and lack the robustness to apply to diverse network environments.

The rest of the paper is organized as follows: In Section II, we present motivation for examining bandwidth measurement techniques. In Section III, we propose ways to make Packet Pair algorithms robust and practical. In Section IV, we describe bottleneck bandwidth algorithms. In Section V, we describe our new Packet Pair filtering algorithm, Potential Bandwidth Filtering. In Section VI, we describe how we simulated different bottleneck bandwidth algorithms on a variety of networks. In Section VII, we present the results of our simulations. In Section VIII, we describe our plans for further exploration of this area. Finally, we conclude in Section IX with our overall observations about the algorithms.