dtm@MBUNIX.MITRE.ORG (06/28/89)
I've been trying to get a hold of Jacobson's algorithm to compute the TCP smoothed round-trip time. Does anyone know of any on-line copies or other references than: "Congestion Avoidance and Control," V. Jacobson, ACM SIGCOMM '88, August 1988. David Miller dtm@mitre.org
mankin@GATEWAY.MITRE.ORG (06/29/89)
David, >I've been trying to get a hold of Jacobson's algorithm to >compute the TCP smoothed round-trip time. Does anyone know >of any on-line copies or other references than: >"Congestion Avoidance and Control," V. Jacobson, >ACM SIGCOMM '88, August 1988. The SIGCOMM paper is *the* reference as things stand for Jacobson's variance estimation round trip time algorithm. I chair a working group at the IETF that is writing an RFC on TCP performance algorithms. Here is a part of our draft which deals with the RTT estimation (notice, by the way, that it's important to do the Karn algorithm on the sampling, in addition to Jacobson). The Performance W.G. draft will be submitted as an RFC probably in the fall, so it's not really something to cite yet, but I hope the section is helpful to you. By the way, another place where these algorithms will be specified in time is for TP4 in the NIST Implementors' Agreements. A colleague and I prepared a text for this and he submitted it to the Lower Layer SIG this past month. Allison Mankin MITRE-Washington Networking Center ---------------------------------------------------------------------------- RTT ESTIMATION AND RTO CALCULATION In normal operation, TCP implementations use estimates of Round Trip Time (RTT: the elapsed time between the transmission of segments and the receipt of their acknowledgements) as the basis for calculating the value for Retransmission Timeout (RTO: the maximum time a TCP implementation will await acknowledgement without retransmitting a segment). The RTO value is calculated dynamically from RTT estimates so that TCP can operate over a wide range of network hardware and under varying load conditions. For acceptable TCP performance, the RTO must be neither too low nor too high. If a TCP implementation consistently uses too large an RTO, then it will be slow in detecting dropped segments. Dropped packets will cause the TCP peers to become inactive, as the sending TCP waits for RTO to expire and the receiving TCP waits for a sequence number it can acknowledge. On the other hand, too low an RTO value will result in spurious retransmissions, since the sending TCP will misinterpret delays as loss. This is clearly wasteful, and can cause congestion. The TCP specification (RFC 793) includes an algorithm "given...as illustration," that calculates RTO based on an RTT estimate. Though the algorithm is widely used in TCP implementations, it has known flaws, and has proven to be inadequate. The two major problems with this RTO algorithm are: 1. It does not address the issue of sampling RTTs in the event of segment retransmission; and 2. It cannot cope with the high variation in RTT that typifies highly utilized systems. Phil Karn has developed an algorithm that solves the first of the above problems (Karn and Partridge, SIGCOMM '87), and Van Jacobson has developed an algorithm that solves the second (Jacobson, SIGCOMM '88). Experience has shown that using Jacobson's algorithm, starting with the SYN segments exchanged during the 3-way handshake of a TCP open, to compute RTO based on RTT samples, and Karn's algorithm to select RTT samples, can dramatically improve TCP performance. As a result, the Host Requirements RFC mandates the use of these algorithms (Section 4.2.3.1). The RTT sampling problem that arises when segments are retransmitted is that it is impossible for the sending TCP to determine which transmission is being acknowledged. In other words, there is no way to tell whether the RTT should be measured from the initial segment transmission, or from excess traffic as a result of a poor RTT estimate. Jacobson's algorithm addresses problems in RTO calculation. Originally, RTO was calculated as: RTO = beta * SRTT, where beta is a constant between 1.3 and 2, and SRTT is the "Smoothed Round Trip Time." SRTT is obtained by the formula: SRTT(n+1) = alpha*SRTT(n) + (1 - alpha)RTT(n) where alpha is a constant between 0.8 and 0.9, and RTT(n) is the nth RTT measurement. This approach for calculating an average is known as "exponential smoothing." It is a weighted average: the most recent observations are given the most weight, while the impact of earlier observations decreases as the algorithm is iterated. The problem with the original RTO calculation is that a fixed multiplier is used to cope with the variance of round trip delay. This approach is inadequate for the Internet; it is well known that RTT varies tremendously. This is not surprising: from queuing theory, we expect that systems under heavy load will display large variance in delay. Increasing a fixed beta sufficiently to accommodate the range of delay variance would result in an RTO much too inflated. In the Jacobson algorithm, RTO is calculated as: RTO = SRTT + 2 * MDEV, where MDEV is the average absolute error -- the "mean deviation" -- of SRTT. Jacobson chose mean deviation rather than standard deviation because it is much simpler to calculate. As he points out, however, the mean deviation is itself a rather good estimator for standard deviation. A rough summary of the Jacobson algorithm is that delays as great as roughly two standard deviations above average will be accepted without retransmission. The most important feature of this algorithm is that RTO is dynamically tailored for the sampled RTT variance. In Jacobson's algorithm, the estimate for MDEV is derived from second-order exponential smoothing, as follows: Err = | RTT - SRTT | SErr(n+1) = gamma*SErr(n) + (1 - gamma)Err where Serr(n) is the nth "smoothed error." Because it is desirable to have RTO adapt quickly when network load and delay increases, the value for gamma should probably be lower than the value used for alpha. Jacobson suggest 0.75. In TCP implementations, SRTT and SErr are recalculated often. Hence, the calculation should be efficient. In an appendix of "Congestion Control and Avoidance," (SIGCOMM '88), Jacobson presents an integer arithmetic implementation of his algorithm that requires only 6 adds, three shifts, and a compare, to get values for SRTT, SErr, and RTO. The procedures for calculating SRTT and SErr are recursive, as each new SRTT and SErr is a function of the previously calculated SRTTs or SErrs, respectively. For the first calculation, however, there are no previously calculated values to use. Hence, these algorithms need seeds for the first calculation. The Host Requirements RFC encourages an initial value of 0 for RTT and 3 for RTO. It also recommends that the Jacobson algorithm begin operation with the SYN segments exchanged during the 3-way handshake of a TCP open (Section 4.2.3.1).