Internet Measurement

This paper basically analyzes the performance of TCP across the internet. By using more than 30 different sites, they get a relatively good collection of flows across the internet. They measure a few different variables to determine whether or not TCP is working as well as it could be. Among these variables are packet reordering, packet replication, packet corruption, bottleneck bandwidth, packet loss, packet loss independence, and packet delay.

The goal here is to provide suggestions for ways to improve the TCP protocol (or implementation thereof). Let's start with packet reordering. They find that the only real effect that packet reordering has on TCP is that it can occasionally trigger retransmissions, when delaying the duplicate acks would have sufficed. To counteract this, they note that if the number of duplicate acks required to retransmit is reduced to 2, but the receiver waits 20 ms before transmitting a duplicate ack, it reduces the number of unnecessary retransmissions. However, if these two changes are not used together, each of them will actually degrade TCP performance, and so they consider it impractical to deploy.

They found a little bit of packet replication, but could not find a good explanation. They did notice, however, that it was site-specific. In terms of packet corruption, they noted that about 1 packet in 5000 arrives corrupted. With a 16 bit checksum, they argue that there is a one in 3000000 chance that a corrupted packet will be accepted, though this probably fails to take into account the nature of bit corruption, as well as the way the checksum is computed. They still recommend increasing the number of bits in the checksum. Corruption for ack packets seems much less common, possibly due to the smaller payload.

They introduced a new method for determining bottleneck bandwidth. In general, when two packets are sent in immediate succession, they sit behind eachother in the queue of some router, and the time interval between their arrivals is a good estimate for the time it took to send one of the two packets. They introduce the notion of computing this value at the RECEIVER, because this will remove any trouble caused by the delay that ACKs encounter on their way back. Furthermore, since they discover that links can be very asymmetric, this method does not need to compensate for the asymmetry. Since some internet connections are spread across several links, or load-balanced, they introduce the concept of not just doing this for packet pairs, but also doing it with 4 or 5 packets. Their results indicate that estimates made at the SENDER are only accurate around 60% of the time, which is a shame, because it means that the TCP sender cannot use the timing of ACKs to estimate a bottleneck bandwidth.

Next, they examine loss rates. In general, they note that most links have one of two states: quiescent or busy. In the quiescent state, there is no packet loss. In the busy state, the loss rate is usually a few percent. They notice that the state of a link is closely correlated with the time of day, and that a quiescent link usually stays in that state for several hours. They are able to conclude that packet losses are correlated with eachother, and are not independent. They suggest using RED in routers instead of tail-drop. They also note that packet loss is sometimes completely asymmetric (by measuring the packet loss rates in both directions).

They then measure the effectiveness of TCP retransmission. They note that Solaris has some problems estimating round-trip time, and exclude it from their main results. They then note that only about 1/6th of retransmissions are unavoidable, and suggest that SACKs can be used to cut down on the number of retransmissions resulting from coarse feedback.

In general, this paper is really thick, and contains a lot of different computations, as well as a lot of different suggestions for improving TCP. I think this paper is really important, because it analyzes just how well TCP is ACTUALLY working as a protocol across the internet. It's one thing to develop a model and to theorize that one algorithm will work better than another, but it's another to actually do measurements.