Introduction

As long as Internet bandwidth has increased, the amount of traffic sent over the Internet has grown to consume it. This means that despite the increasing link bandwidth in network backbones and into homes and offices, optimizing the use and allocation of bandwidth continues to be an interesting problem. Although many applications are more interested in available bandwidth than link bandwidth, knowing the link bandwidth along a path enables more accurate measurement of available bandwidth. In addition, several applications can directly use link bandwidth, including planning networks to minimize bottlenecks and analyzing network performance as a whole [14].

However, the Internet's current size, heterogeneity, and rate of change make determining link bandwidth a challenging research problem. This is true even though applications are usually only interested in the bandwidth along a particular path or even just the smallest bandwidth (the bottleneck bandwidth) along that path. A database to store bandwidth information would neither scale well nor cope with the rate at which routes change [13]. Routers currently do not report link bandwidths. Since routers gain much of their speed by being as simple as possible, slowing them to answer link bandwidth queries is probably not acceptable. The easiest approach to deploy, and consequently the one in which we are most interested, is for end hosts to infer link bandwidth by actively probing or passively listening to traffic. Hosts can share this information if the probing or listening is expensive [17].

The challenge of the inference approach is to measure link bandwidth as accurately, quickly, robustly, and unobtrusively as possible. By robust we mean it is usable in the variety of network environments that exists in the Internet: few or many hops from source to destination, empty or saturated links, one or several channels per link, different wired and wireless link technologies, different queueing disciplines, and different router implementations. By unobtrusive we mean it places minimal additional load on the network, since it is desirable to prevent measurement traffic from delaying application data traffic.

As we describe in Section 2, existing solutions to infer all link bandwidths along a path are built from a deterministic model that considers only one measurement packet. As a result, these techniques rely on routers handling ICMP packets consistently, and timely delivery of acknowledgements. These techniques use significant amounts of network bandwidth to perform their measurements and can be slow enough to become impractical for some of the applications that most need them.

In this paper, we describe a new deterministic model of packet delays that unifies previous models. Using this model, we derive a novel technique, called packet tailgating, for measuring link bandwidths along a path through the Internet. Packet tailgating captures link-specific characteristics by causing queuing of packets at particular links. For each link, the technique sends a large packet with a time-to-live (TTL) set to expire at that link followed by a very small packet that will queue continuously behind the large packet until where the large packet expires.

Packet tailgating consumes less network bandwidth than previous techniques, does not rely on consistent router behavior for handling ICMP packets, does not rely on timely delivery of acknowledgements, can theoretically detect multi-channel links and can be run on multicast trees. Using our prototype tailgating implementation on a path through the Internet, we demonstrate that packet tailgating sends an order of magnitude fewer packets than previous techniques while maintaining similar accuracy. Unfortunately, all currently available bandwidth measurement tools, including our prototype implementation of packet tailgating, have low accuracy on paths longer than a few hops.

In addition, we use our multi-packet delay model to derive the packet pair [2] property of FIFO-queueing networks which has previously been used to measure bottleneck link bandwidth. Packet pair has previously been derived for fair-queueing networks [9], but not for FIFO-queuing networks.

The rest of the paper is organized as follows. In Section 2 we review related work on packet delay models used for measuring link bandwidths along a path and for measuring bottleneck bandwidth. In Section 3 we present a multi-packet deterministic model of packet delay and show how we can use it to derive previous packet delay models and the new tailgating technique. In Section 4, we describe how we use the technique to measure link bandwidths and analyze the technique's strengths and weaknesses. In Section 5, we compare preliminary measurements of our packet tailgating implementation with those of previous link bandwidth techniques. In Section 6, we conclude. We include a derivation of the packet pair property in the appendix.