Estimating Bandwidth from Passive Measurement Traces

John G. Cleary and H. Stele Martin.
Department of Computer Science, University of Waikato.

A methodology for analysing bandwidth from passive measurement traces is described. Previous analyses of delay times for HTTP requests showed that effects from bandwidth are significant.

Using accurate passive measurement traces we extract Round Trip Times (RTTs) from TCP streams. We start by identifying a TCP connection between two machines (typically this is an HTTP flow and contains traffic in both directions). The TCP connection is then analysed to identify the different message types (for example data, ACK, SYN and FIN) and the state of the TCP stacks at the time when the messages were sent. By pairing packets that are known to have a small amount of host processing (for example SYN and ACK packets), the minimum physical time from the measurement point to the host and back, is approximated.

For small SYN and ACK packets, using just the measured time as an approximation for the RTT works well. When this technique is applied to larger packets, then the effect of the bandwidth over the link is significant and must be taken into account.

The effective bandwidth seen by the user is dependent on the number and speed of the links between the two hosts being measured. Each separate link where the packet has to be stored and forwarded adds extra time proportional to the length of the packet. In the simple case the packets in both directions will travel over the same links and the observed bandwidth will be the same in both directions. We analyse such data by plotting the observed RTTs against the sum of the lengths of the packets in both directions. The slope of the lower edge of this plot gives an estimate of the effective bandwidth. A number of different regression algorithms for estimating this slope are examined for robustness and accuracy.

It is clear that for some of the flows that have been analysed, these plots do not give consistent results. We show that this is a result of the effective bandwidth being different in the forward and reverse directions. It is postulated that this is a result of asymmetric routing of the packets.

Given the size of the packets in each direction, RTT can be plotted on a 3 dimensional graph as a function of forward data size and reverse data size. The effective bandwidth in each direction can then be approximated from the plane which underlies the minima of these times.

The regression algorithms are extended to deal with the estimate of the bandwidths in both the forward and reverse directions. Care is taken to ensure that enough data points are used when estimating each minimum point. A number of example analyses of different flows are given. A resampling technique is used to evaluate the robustness and accuracy of the regressions and the resulting estimated bandwidths.