Potential Bandwidth Filtering

In this section we describe a previously unaddressed problem with using the filtering algorithm described above in Section IV-C. We call that algorithm Measured Bandwidth Filtering (MBF) to distinguish it from our solution to the problem, Potential Bandwidth Filtering (PBF).

The Potential Bandwidth Problem

One problem with Packet Pair algorithms is that they cannot measure a higher bandwidth than the bandwidth at which the sender sends. If a sender sends two packets of 1000 bytes each with 1ms separation, then the receiver cannot measure a higher bottleneck bandwidth than 8Mb/s, even if the true bottleneck bandwidth is 100Mb/s. This is a fundamental property of all Packet Pair algorithms regardless of how the filtering is done. We call the bandwidth at which the sender sends two packets the potential bandwidth because the measured bandwidth cannot exceed it.

The problem arises when the sender sends small packets, or sends packets slowly, or both. Then the potential bandwidth is likely to be lower than the actual bottleneck bandwidth of the path, and any measured bandwidth will be wrong.

Fortunately, some packets have a large potential bandwidth. Most HTTP and FTP packets are large and rapidly sent, and therefore have a high potential bandwidth. Unfortunately, it may be that not all packets in a flow have a high potential bandwidth, and in fact, it may frequently be the case that the high potential bandwidth packets are not the most common type of packets.

For example, consider someone browsing a site using HTTP/1.1. HTTP/1.1 opens one TCP connection to a site and uses that connection for all communication. The client will receive many large packets filled with HTML pages while sending many acks and a few medium-sized packets filled with HTTP requests. The outbound link will be dominated by many small packets, with a few medium-sized packets. If we used the normal MBF algorithm, we would report the measured bandwidth of the small packets.

We discovered this problem in our simulation of an asymmetric network, where this is even more of a problem. On an asymmetric network with a high bandwidth inbound link and low bandwidth outbound link, an inbound data transfer will fill the outbound link with acks at a packet/second rate that is likely to exceed that of any outbound data packets.

The Potential Bandwidth Filtering Solution

Figure 2: This graph shows how PBF works. The dots represent bandwidth samples plotted using their potential and measured bandwidth. All samples above the x = y line are filtered out. Notice how there is a knee in the samples.

The general idea of Potential Bandwidth Filtering is that we should correlate the potential bandwidth and measured bandwidth of a sample in deciding how to filter. Samples with the same potential bandwidth and measured bandwidth are not particularly informative because the actual bandwidth could be much higher. Samples with a high measured bandwidth and low potential bandwidth are time compressed and should be filtered out. Samples with a high potential bandwidth and low measured bandwidth are the most informative because they are likely to indicate the true bandwidth.

We implement the algorithm by plotting all the samples on a graph with potential bandwidth on the x-axis and measured bandwidth on the y-axis. An example is shown in Figure 2. We would expect that in the absence of congestion, the samples would fall along the line x = y until some point x = b. These samples have potential bandwidth approximately equal to measured bandwidth. The packets that generated these samples did not queue behind each other at the bottleneck link. After b the samples should run along the line y = b. These are the samples with a higher potential bandwidth than measured bandwidth. The packets that generated these samples did queue behind each other at the bottleneck link. The value b is the actual bandwidth.

If the samples never divert from the line x = y, then we know that our samples had insufficient potential bandwidth. For example, this would be case if we only had the samples to the left of x = b in Figure 2.In this case, we should try an active algorithm.

To compensate for noise, we fit the x = y and y = b lines to the data and compute the relative error for each point as the distance of that point to the nearest line divided by the x-value of that point. This ensures that errors when x is large do not dominate the calculation. We then sum the errors for all the points and attempt to minimize the sum to choose the optimal b.

Our results show that PBF is just as accurate as MBF on an Ethernet network and 37% to 435% more accurate than MBF on an asymmetric network (see Section VII-C). We believe that PBF is essential to the practical use of passive Packet Pair algorithms.