Improve accuracy of Rx RTT calculation by skipping retransmitted packets

Rx RTT calculations are based on Van Jacobson's work using
constants that make computations fast but are not necessarily
the best for modeling Rx protocol exchanges.  This patch does
not alter the constants but does improve the comments to show
that the math is correct.

Phil Karn in 1987 demonstrated that Van Jacobson's algorithms
produced inaccurate results when the RTT computed from an
acknowledgement of a retransmitted packet were included.  The
resulting RTT would either be too small causing the system to
retransmit too many packets or too long resulting in too few
being sent.

This patch follows Phil Karn's advice which was also adopted
as mandatory for TCP in RFC2988.  Retransmitted packets and
delayed acks are skipped and the retransmit time is backed off
(up to a maximum of 3 seconds) until a successful acknowlegement
is received for an initially transmitted packet.

LICENSE BSD

Reviewed-on: http://gerrit.openafs.org/580
Tested-by: Jeffrey Altman <jaltman@openafs.org>
Reviewed-by: Jeffrey Altman <jaltman@openafs.org>

diff --git a/src/rx/rx.c b/src/rx/rx.c
index 5c344d8..2f7518e 100755 (executable)
--- a/src/rx/rx.c
+++ b/src/rx/rx.c
@@ -3666,8 +3666,11 @@ rxi_ComputePeerNetStats(struct rx_call *call, struct rx_packet *p,
 {
     struct rx_peer *peer = call->conn->peer;
 
-    /* Use RTT if not delayed by client. */
-    if (ap->reason != RX_ACK_DELAY)
+    /* Use RTT if not delayed by client and
+     * ignore packets that were retransmitted. */
+    if (!(p->flags & RX_PKTFLAG_ACKED) &&
+        ap->reason != RX_ACK_DELAY &&
+        clock_Eq(&p->timeSent, &p->firstSent))
        rxi_ComputeRoundTripTime(p, &p->timeSent, peer);
 #ifdef ADAPT_WINDOW
     rxi_ComputeRate(peer, call, p, np, ap->reason);
@@ -3691,6 +3694,7 @@ rxi_ReceiveAckPacket(struct rx_call *call, struct rx_packet *np,
     afs_uint32 skew = 0;
     int nbytes;
     int missing;
+    int backedOff = 0;
     int acked;
     int nNacked = 0;
     int newAckCount = 0;
@@ -3779,9 +3783,7 @@ rxi_ReceiveAckPacket(struct rx_call *call, struct rx_packet *np,
        if (tp->header.seq >= first)
            break;
        call->tfirst = tp->header.seq + 1;
-       if (serial
-           && (tp->header.serial == serial || tp->firstSerial == serial))
-           rxi_ComputePeerNetStats(call, tp, ap, np);
+        rxi_ComputePeerNetStats(call, tp, ap, np);
        if (!(tp->flags & RX_PKTFLAG_ACKED)) {
            newAckCount++;
        }
@@ -3841,9 +3843,7 @@ rxi_ReceiveAckPacket(struct rx_call *call, struct rx_packet *np,
        if (tp->header.seq >= first)
 #endif /* RX_ENABLE_LOCKS */
 #endif /* AFS_GLOBAL_RXLOCK_KERNEL */
-           if (serial
-               && (tp->header.serial == serial || tp->firstSerial == serial))
-               rxi_ComputePeerNetStats(call, tp, ap, np);
+            rxi_ComputePeerNetStats(call, tp, ap, np);
 
        /* Set the acknowledge flag per packet based on the
         * information in the ack packet. An acknowlegded packet can
@@ -3877,13 +3877,28 @@ rxi_ReceiveAckPacket(struct rx_call *call, struct rx_packet *np,
            missing = 1;
        }
 
+        /*
+         * Following the suggestion of Phil Kern, we back off the peer's
+         * timeout value for future packets until a successful response
+         * is received for an initial transmission.
+         */
+        if (missing && !backedOff) {
+            struct clock c = peer->timeout;
+            struct clock max_to = {3, 0};
+
+            clock_Add(&peer->timeout, &c);
+            if (clock_Gt(&peer->timeout, &max_to))
+                peer->timeout = max_to;
+            backedOff = 1;
+        }
+
        /* If packet isn't yet acked, and it has been transmitted at least 
         * once, reset retransmit time using latest timeout 
         * ie, this should readjust the retransmit timer for all outstanding 
         * packets...  So we don't just retransmit when we should know better*/
 
        if (!(tp->flags & RX_PKTFLAG_ACKED) && !clock_IsZero(&tp->retryTime)) {
-           tp->retryTime = tp->timeSent;
+            tp->retryTime = tp->timeSent;
            clock_Add(&tp->retryTime, &peer->timeout);
            /* shift by eight because one quarter-sec ~ 256 milliseconds */
            clock_Addmsec(&(tp->retryTime), ((afs_uint32) tp->backoff) << 8);
@@ -5978,13 +5993,15 @@ rxi_ComputeRoundTripTime(struct rx_packet *p,
         * srtt is stored as fixed point with 3 bits after the binary
         * point (i.e., scaled by 8). The following magic is
         * equivalent to the smoothing algorithm in rfc793 with an
-        * alpha of .875 (srtt = rtt/8 + srtt*7/8 in fixed point).
-        * srtt*8 = srtt*8 + rtt - srtt
-        * srtt = srtt + rtt/8 - srtt/8
+        * alpha of .875 (srtt' = rtt/8 + srtt*7/8 in fixed point).
+         * srtt'*8 = rtt + srtt*7
+        * srtt'*8 = srtt*8 + rtt - srtt
+        * srtt' = srtt + rtt/8 - srtt/8
+         * srtt' = srtt + (rtt - srtt)/8
         */
 
-       delta = MSEC(rttp) - (peer->rtt >> 3);
-       peer->rtt += delta;
+       delta = _8THMSEC(rttp) - peer->rtt;
+       peer->rtt += (delta >> 3);
 
        /*
         * We accumulate a smoothed rtt variance (actually, a smoothed
@@ -5995,16 +6012,20 @@ rxi_ComputeRoundTripTime(struct rx_packet *p,
         * rttvar is stored as
         * fixed point with 2 bits after the binary point (scaled by
         * 4).  The following is equivalent to rfc793 smoothing with
-        * an alpha of .75 (rttvar = rttvar*3/4 + |delta| / 4).  This
-        * replaces rfc793's wired-in beta.
+        * an alpha of .75 (rttvar' = rttvar*3/4 + |delta| / 4).
+         *   rttvar'*4 = rttvar*3 + |delta|
+         *   rttvar'*4 = rttvar*4 + |delta| - rttvar
+         *   rttvar' = rttvar + |delta|/4 - rttvar/4
+         *   rttvar' = rttvar + (|delta| - rttvar)/4
+        * This replaces rfc793's wired-in beta.
         * dev*4 = dev*4 + (|actual - expected| - dev)
         */
 
        if (delta < 0)
            delta = -delta;
 
-       delta -= (peer->rtt_dev >> 2);
-       peer->rtt_dev += delta;
+       delta -= (peer->rtt_dev << 1);
+       peer->rtt_dev += (delta >> 3);
     } else {
        /* I don't have a stored RTT so I start with this value.  Since I'm
         * probably just starting a call, and will be pushing more data down
@@ -6012,15 +6033,15 @@ rxi_ComputeRoundTripTime(struct rx_packet *p,
         * little, and I set deviance to half the rtt.  In practice,
         * deviance tends to approach something a little less than
         * half the smoothed rtt. */
-       peer->rtt = (MSEC(rttp) << 3) + 8;
+       peer->rtt = _8THMSEC(rttp) + 8;
        peer->rtt_dev = peer->rtt >> 2; /* rtt/2: they're scaled differently */
     }
-    /* the timeout is RTT + 4*MDEV + 0.35 sec   This is because one end or
+    /* the timeout is RTT + 4*MDEV but no less than 350 msec   This is because one end or
      * the other of these connections is usually in a user process, and can
      * be switched and/or swapped out.  So on fast, reliable networks, the
      * timeout would otherwise be too short.  
      */
-    rtt_timeout = (peer->rtt >> 3) + peer->rtt_dev + 350;
+    rtt_timeout = MIN((peer->rtt >> 3) + peer->rtt_dev, 350);
     clock_Zero(&(peer->timeout));
     clock_Addmsec(&(peer->timeout), rtt_timeout);
 

diff --git a/src/rx/rx.h b/src/rx/rx.h
index 5e2550b..eb9699e 100644 (file)
--- a/src/rx/rx.h
+++ b/src/rx/rx.h
@@ -371,15 +371,15 @@ struct rx_peer {
 
     /* For garbage collection */
     afs_uint32 idleWhen;       /* When the refcountwent to zero */
-    afs_uint32 refCount;               /* Reference count for this structure */
+    afs_uint32 refCount;       /* Reference count for this structure */
 
     /* Congestion control parameters */
     u_char burstSize;          /* Reinitialization size for the burst parameter */
     u_char burst;              /* Number of packets that can be transmitted right now, without pausing */
     struct clock burstWait;    /* Delay until new burst is allowed */
     struct rx_queue congestionQueue;   /* Calls that are waiting for non-zero burst value */
-    int rtt;                   /* Round trip time, measured in milliseconds/8 */
-    int rtt_dev;               /* rtt smoothed error, in milliseconds/4 */
+    int rtt;                   /* Smoothed round trip time, measured in milliseconds/8 */
+    int rtt_dev;               /* Smoothed rtt mean difference, in milliseconds/4 */
     struct clock timeout;      /* Current retransmission delay */
     int nSent;                 /* Total number of distinct data packets sent, not including retransmissions */
     int reSends;               /* Total number of retransmissions for this peer, since this structure was created */
@@ -419,7 +419,6 @@ struct rx_peer {
     int lastReachTime;         /* Last time we verified reachability */
 };
 
-
 #ifndef KDUMP_RX_LOCK
 /* Flag bits for connection structure */
 #define        RX_CONN_MAKECALL_WAITING    1   /* rx_MakeCall is waiting for a channel */

diff --git a/src/rx/rx_clock.h b/src/rx/rx_clock.h
index b0f1175..e375106 100644 (file)
--- a/src/rx/rx_clock.h
+++ b/src/rx/rx_clock.h
@@ -133,7 +133,10 @@ extern int clock_nUpdates;
        (c1)->sec += (c2)->sec;                                 \
     END
 
+#define USEC(cp)        ((cp->sec * 1000000) + cp->usec)
 #define MSEC(cp)       ((cp->sec * 1000) + (cp->usec / 1000))
+#define _4THMSEC(cp)    ((cp->sec * 4000) + (cp->usec / 250))
+#define _8THMSEC(cp)    ((cp->sec * 8000) + (cp->usec / 125))
 
 /* Add ms milliseconds to time c1.  Both ms and c1 must be positive */
 #define        clock_Addmsec(c1, ms)                                    \