Making Packet Pair Robust and Practical

The bandwidth measurement technique we have chosen to investigate is called Packet Pair [2] (described in more detail in Section IV-B). The advantages it has over the techniques mentioned above are that 1) it measures the true bandwidth of the network (instead of throughput), 2) it does not cause packet loss (unlike TCP), 3) it does not require many packet round trips to work, and 4) it does not send massive amounts of data (unlike pathchar). On the other hand, each of those techniques currently has a robust and practical implementation and is in common use in the Internet, while Packet Pair does not have such an implementation and is rarely used at all (although several tools implement a version of the Packet Pair algorithm, including bprobe [5] and tcpanaly [11]).

Here are some of the key problems with current Packet Pair algorithms and how we propose to solve them:

Not statistically robust

Previous work on filtering Packet Pair samples has used techniques such as adding error bars to values and intersecting them [5], or clustering values that are close together [12]. Such heuristics do not have well understood statistical properties and their effectiveness may depend on a particular data set.

Instead, we use a kernel density estimator to filter data, which has well understood statistical properties [14]. In particular, it makes no assumptions about the data, and is therefore statistically robust (see Section IV-C).

Not scalable

Active Packet Pair implementations [5] generate their own traffic and therefore have the same scalability problems as pathchar (see Section IV-A).

Packet Pair algorithms do not need to do this [12]. Our passive Packet Pair implementation uses existing network traffic to measure bandwidth.

Slow

On the other hand, previous passive implementations are designed to analyze a TCP connection after its completion [12], instead of while it is occurring. Given the long duration of some TCP connections, this could be too late for some of the applications mentioned above.

Our gradual Packet Pair implementation forms a bandwidth estimate for every packet that arrives. It initially gives inaccurate answers and then gradually converges to an accurate answer. In this way, applications obtain an estimate as soon as it is available (see Section IV-E). Our results show that Packet Pair can give the correct estimate within three packets of the start of the connection.

Not robust on all traffic

Most passive implementations are designed to use traffic composed of mostly large packets. However, Internet traffic is a mix of many packet sizes and any one flow between two hosts may contain a wide variety of packet sizes. Existing passive implementations do not account for this and thus give inaccurate results on diverse traffic such as a mix of predominantly small packets and a few large packets (see Section V). This is because the network model used in those implementations does not account for potential bandwidth.

We designed a new Packet Pair filtering algorithm, called Potential Bandwidth Filtering (PBF), which can deliver an accurate answer despite variation in packet size and transmission rate. On a mix of packet sizes, PBF is at least 37% more accurate than the standard filtering algorithm.

Not flexible to bandwidth changes

Some prior implementations detect only one bandwidth over time [5]. Other implementations can detect multiple bandwidths, but only those which differ by a large amount [12]. Although not as frequent as congestion changes, bottleneck bandwidth changes do happen because of routing changes [12] or because of mobility [1]. Some of the applications described above would like to know as soon as possible that the bandwidth has changed and what the new bandwidth is, regardless of magnitude.

To accomplish the above, we propose the use of a limited window of past packets to calculate bandwidth. This increases the speed at which the algorithm can adapt to a new bandwidth (the agility), but it leaves the results more vulnerable to noise. We believe that an increase in agility fundamentally requires becoming more vulnerable to noise (see Section IV-E). We show that a small window is 144% more accurate than an infinite window in the presence of link failure, but 10% less accurate in the presense of congestion.

Difficult to deploy

A current highly accurate Packet Pair algorithm, Receiver Based Packet Pair (RBPP) [12], requires that packet timings be taken at both the sender and receiver of those packets. This means that special software must be deployed at both the sender and receiver, which may not be possible. Another algorithm, Sender Based Packet Pair (SBPP) [12] requires timings (and therefore special software) only on the sender. Unfortunately, SBPP is far less accurate than RBPP.

We describe a variation of RBPP, called Receiver Only Packet Pair (ROPP), which is more accurate than SBPP (but less than RBPP), while only requiring timings at the receiver (see Section IV-D). This allows applications to trade some accuracy for ease of deployment. Our results show that ROPP is accurate within 1% of RBPP.

Not studied under controlled conditions

There have been several studies of Packet Pair algorithms using data from the Internet. This has the advantage of using real TCP/IP code, routers, and network traffic. However, we would like: 1) verifiable and reproducible results and 2) testing under a variety of controlled conditions. Testing under controlled conditions in the Internet at large would be difficult, if not impossible.

To overcome these limitations, we use a network simulator (fully described in Section VI) to compare the effectiveness of the algorithms and modifications described above to previous Packet Pair implementations.