Bandwidth Measurement Algorithms

In this section, we describe the models and assumptions of the algorithms for measuring bottleneck bandwidth. We consider their accuracy, timeliness, and agility as well as whether they are active or passive and whether they require measurements from multiple network hosts.

We know of two families of bottleneck bandwidth algorithms. The first family of algorithms, which we call the Pathchar Algorithms, is used in the tools pathchar [8] and utimer [6]. The second family of algorithms is based on the Packet Pair algorithm and is used in the tools bprobe [5], cprobe [5], and tcpanaly [11]. Variants of the Packet Pair algorithm are Sender Based Packet Pair (SBPP), Receiver Based Packet Pair (RBPP), Packet Bunch Mode (PBM) [12], and our own Receiver Only Packet Pair (ROPP).

An orthogonal issue for Packet Pair algorithms is how they filter bandwidth samples. We call the standard algorithms Measured Bandwidth Filtering (MBF) and propose our own Potential Bandwidth Filtering (PBF). In addition, we describe our refinements of the Packet Pair algorithms and their filtering methods: the use of a kernel density function to increase statistical robustness, the use of gradual bandwidth calculation to increase timeliness, and the use of a packet window to increase agility.

Pathchar Algorithm

In this section, we analyze the time taken and bandwidth consumed by the Pathchar algorithm. The program works by sending packets of varying sizes and measuring their round trip time. It correlates the round trip times with the packet sizes to calculate bandwidth. It uses the results from earlier hops for calculations on father hops. For a more thorough description of how and why pathchar works, see [8]. For our purposes, all we need to know is that the pathchar program uses an active algorithm that sends packets varying in size from 64 bytes to the path MTU with a stride of 32 bytes. Therefore, the number of different packet sizes pathchar sends is

$$\left\lfloor\vphantom{\frac{MTU}{32}}\right. {\frac{MTU}{32}} \left.\vphantom{\frac{MTU}{32}}\right\rfloor$$ (1)

For Ethernet, the MTU is 1500 bytes, so s is 45. In addition, it sends p packets per size for every hop. In the default configuration, p = 32. It must wait for each packet it sends to be acknowledged before sending the next packet. Thus, the total time for pathchar to run is

$$\sum_{i = 1}^{h}$$ (2)

where h is the number of hops and l_i is the round trip latency from the sender to hop i. We assume that the receiver immediately sends an ack in response to a packet and that the sender immediately sends out the next packet when an ack arrives. For a 10-hop Ethernet network with an average round trip latency of 10ms, pathchar would run in 144 seconds. This is too slow for a host to run it for every TCP connection, or even every 10 minutes. It can be configured to send fewer packets of each size, but at the cost of accuracy.

More importantly, pathchar consumes considerable amounts of network bandwidth. The average bandwidth used for probing a particular hop is

$${\frac{average\ packet\ size}{round\ trip\ latency}} {\frac{\frac{32 \cdot s}{2} + 32}{l_i}}$$ (3)

in bytes/s, where l_i is the round trip latency (in seconds) across that hop. For a 1-hop Ethernet network with a latency of 1ms, the average bandwidth consumed is 6.02Mb/s. This would be a considerable imposition on a 10Mb/s Ethernet. Farther hops would consume less bandwidth, but pathchar always has to probe closer hops before farther hops. Furthermore, the total data transferred is

$$\left(\vphantom{\sum_{i = 2}^s 32i}\right. \sum_{i = 2}^{s} \left.\vphantom{\sum_{i = 2}^s 32i}\right)$$ (4)

where h is the number of hops. For the 10-hop Ethernet network mentioned before, pathchar sends 10 MB of data. In fact, pathchar will send 10 MB of data on a 10-hop network regardless of the bandwidth of the network, since it only depends on the number of hops, the path MTU, and p. If the path MTU is high and one of the early hops is a low bandwidth network link, such as a 56K modem, then pathchar can consume most of the bandwidth of that link for an extended amount of time. This means that we would have problems scaling pathchar usage up to a large number of hosts.

Packet Pair

Figure 1: This figure shows how the Packet Pair algorithm works. Note how the data packets have a greater separation after the bottleneck link and how this separation is maintained by the acks. The arrows pointing to SBPP, RBPP, and ROPP indicate what timing information must be sent from the sender and receiver for each of the algorithms.

The basic Packet Pair algorithm [9] relies on the fact that if two packets are queued next to each other at the bottleneck link, then they will exit the link t seconds apart:

$${\frac{s_{2}}{b_{bnl}}}$$ (5)

where s₂ is the size of the second packet and b_bnl is the bottleneck bandwidth. This is the ``bottleneck separation'' (see Figure 1). Since there are no links with lower bandwidth than the bottleneck link downstream of that link, and assuming the packets are the same size, the second packet will never catch up to the first packet.

The two packets have to be the same size because different size packets have different ``velocities''. If the second packet were smaller than the first, then its transmission delay would always be less than the first packet's. Consequently, it would pass through links faster than the first packet and quickly eliminate the bottleneck separation. Similarly, if the the first packet is smaller, then it will be faster than the second packet and continuously grow the bottleneck separation.

Assuming the bottleneck separation is constant, the two packets will arrive at the receiver spaced t seconds apart. Since we know s₂, we can then calculate the bottleneck bandwidth:

$${\frac{s_{2}}{t}}$$ (6)

This algorithm makes several assumptions that may not hold in practice. For instance, it is impossible to guarantee that two packets will queue next to each other at the bottleneck link. If other packets queue in between the two measurement packets, then (6) becomes

$${\frac{s_{2} + s_{o}}{t}}$$ (7)

where s_o is the total size of the other packets. In addition, if other packets queue ahead of the first packet when it is downstream of the bottleneck link, those extra packets will delay the first packet, causing time compression of the two packets. Similarly, other packets could only delay the second packet, causing the packets to be time extended. Time compression can cause a high estimate of the bottleneck bandwidth, while time extension can cause a low estimate.

Packet Pair Filtering

The main problem with the basic Packet Pair algorithm is how to filter out the noise caused by time compressed and extended packets. One solution would be to take the mean or median of all the bandwidth samples. Unfortunately, the noise has little correlation to the true bandwidth, so this gives wildly varying estimates.

Previous Packet Pair research has proposed finding the point of greatest density in the distribution of bandwidth estimates. The idea is that valid samples should be closely clustered around the correct value, while incorrect samples should not be clustered around any one value.

A well known method for doing this is to use a histogram. Unfortunately, there are several problems with histograms. One problem is that bin widths are fixed, and it is difficult to choose an appropriate bin width without previously knowing something about the distribution. Another problem is that bin boundaries do not respect the distribution. Two points could lie very close to each other on either side of a bin boundary and the bin boundary ignores that relationship. Finally, a histogram will report the same density for points with the same value as points which are in the same bin, but at opposite ends of the bin.

Previous Packet Pair filtering algorithms [5] [11] have overcome some of these problems, but not all of them. We use the kernel density estimator algorithm, which overcomes all of these problems. This algorithm is well known to statisticians [14] [16]. To use it, we first define a kernel function K(t) with the property

$$\int^{+\infty}_{-\infty}$$ (8)

Then the density at any point x is

$${\frac{1}{n}} \sum^{n}_{i=1} {\frac{1}{h}} \left(\vphantom{\frac{x - x_i}{h}}\right. {\frac{x - x_i}{h}} \left.\vphantom{\frac{x - x_i}{h}}\right)$$ (9)

where h is the kernel width, n is the number of points within h of x, and x_i is the ith such point. The kernel function we use is

$$\left\{\vphantom{ \begin{array}{ll} 1 + x & x \leq 0 \\ 1 - x & x > 0 \end{array}}\right. \begin{array}{ll} 1 + x & x \leq 0 \\ 1 - x & x > 0 \end{array} \left.\vphantom{ \begin{array}{ll} 1 + x & x \leq 0 \\ 1 - x & x > 0 \end{array}}\right\}$$ (10)

This function has the desirable properties that it gives greater weight to samples closer to the point at which we want to estimate density, and it is simple and fast to compute. The kernel density estimator algorithm is known to be statistically valid and we show in section VII that it gives accurate results. Most importantly, it makes no assumptions about the distribution it operates on and therefore should be just as accurate on other data sets.

Receiver and Sender Based Packet Pair

Receiver Based Packet Pair (RBPP) and Sender Based Packet Pair (SBPP) (both [12]) are types of Packet Pair algorithms. They differ in how the t from (6) is measured. Figure 1 shows the difference in where timing measurements must be taken. In Receiver Based Packet Pair, t is measured at the receiver, so (6) becomes

$${\frac{s_{2}}{a_{2} - a_{1}}}$$ (11)

where a₁ and a₂ are the arrival times of the first and second packets, respectively.

If we cannot measure the arrival times at the receiver, we have to use the round trip time, which is measured at the sender (SBPP). Equation (6) becomes

$${\frac{s_{2}}{r_{2} - r_{1}}}$$ (12)

where r₁ and r₂ are the arrival times of the acks to the first and second packets, respectively. This assumes that the receiver promptly sends back an acknowledgement for both of the packets. With SBPP, packets from other hosts could interfere with the acks as well as the original packets.

In both the receiver and sender based algorithms, we can apply additional filtering techniques to reject incorrect estimates. We can detect time compression or reordering when two packets have a difference between their transmission times greater than the difference between their arrival times (for RBPP) or their round trip times (for SBPP).

RBPP and SBPP are useful in different circumstances. RBPP is more accurate, but it can be harder to deploy since it requires measurement collection at both endpoints. SBPP is easy to deploy, but its results can be highly inaccurate during congestion (see Section VII).

Another difference is that SBPP requires that packets be acknowledged (as in TCP) and that the acks be constant size and relatively small. The acks must be constant size because variation in ack size causes variation in total round trip time, which would causes noise in the bandwidth samples. The acks must be small because as they become larger, the bandwidth of the path back to the sender would start to become the bottleneck. If the bottleneck bandwidth of the path back to the sender is much less than that from the sender (as in an asymmetric network) then ack size becomes that much more important (we see this effect in Section VII).

Finally, the algorithms differ in the kind of traffic they can use and the paths they can measure. SBPP relies on data packets flowing away from the measurement host and can only measure the bandwidth of the path from the sender to the receiver. RBPP can use whatever traffic is available. In the usual situation of data packets flowing in one direction and acks flowing in the other, RBPP can determine the bandwidth in both directions. However, the usually small size of the acks will limit the bandwidth that can be measured (see Section V).

Some applications may need the high accuracy of RBPP and the ease of deployment of SBPP. For those applications, we propose Receiver Only Packet Pair (ROPP). As shown in Figure 1, ROPP only takes timing measurements from the receiver and is therefore easier to deploy than RBPP. However, without timing information from the sender, ROPP cannot filter out time compressed packets or reordered packets, as SBPP and RBPP can. On the other hand, it is much less likely than SBPP to have such samples (like RBPP) because it is not relying on round trip latency. Another limitation is that it cannot use the new Potential Bandwidth Filtering algorithm described in Section V. Finallym, it has the limitation that it needs packets (although these can be acks) flowing on paths towards the measurement host and can only determine the bandwidth of such paths.

Despite these limitations, our results show that ROPP achieves accuracy within 1% of RBPP (see VII). We conclude that ROPP achieves the ease of deployment of SBPP, while sacrificing little accuracy. It is an excellent choice for applications needing to know the bandwidth of paths towards a host.

Timeliness versus Accuracy

In this section we describe the tradeoff of accuracy versus timeliness in Packet Pair algorithms and how we implemented our algorithms to take advantage of these tradeoffs.

The Packet Pair algorithms described in the previous sections are usually implemented as running over a fixed number of packets or over an entire connection before providing an estimate. This translates into a long delay before providing an estimate. One problem is that some applications would prefer to have a ballpark answer sooner in addition to an accurate answer later.

Our solution is to calculate bandwidth gradually. Instead of calculating a single bandwidth, we calculate a new estimate with every packet arrival. In Section VII-B, we show that a gradual algorithm can converge to the correct bandwidth within three packets, instead of having to wait the entire life of the connection.

A problem with the gradual Packet Pair algorithm is that it is slow to detect a bandwidth change, i.e. it has poor agility. A bandwidth change may be caused by a route change such as a link failing or host mobility. The gradual algorithm described above will initially detect a bandwidth change as noise and stick to its initial estimate.

To compensate for this problem and to be able to detect multiple bandwidth changes, we use a packet window. We use at most w (the window size) packets into the past to calculate the bandwidth at a particular packet. This has the advantage that only the most recent and probably most relevant samples are used to calculate bandwidth.

The disadvantage of using a window is that it may reduce stability. With smaller windows, we are more affected by transient conditions like congestion, which we may detect as a temporary bandwidth change, as shown in Section VII-B. We believe this is a fundamental tradeoff. A Packet Pair algorithm cannot distinguish between true changes in bandwidth and persistent congestion. However, given this fundamental limitation, our addition of windows to the basic Packet Pair algorithm enables it to distinguish bandwidth changes in the presence of light to moderate congestion.