From 7cc62c26d645736708f4d4e7e309108691195a33 Mon Sep 17 00:00:00 2001 From: Mike Karels Date: Wed, 1 Jul 1987 06:15:43 -0800 Subject: [PATCH] redo retransmit calculations as srtt + 2*smoothed variance (from Van Jacobson) SCCS-vsn: sys/netinet/tcp_input.c 7.6 SCCS-vsn: sys/netinet/tcp_output.c 7.7 SCCS-vsn: sys/netinet/tcp_subr.c 7.7 SCCS-vsn: sys/netinet/tcp_timer.c 7.6 SCCS-vsn: sys/netinet/tcp_timer.h 7.3 SCCS-vsn: sys/netinet/tcp_var.h 7.3 --- usr/src/sys/netinet/tcp_input.c | 67 ++++++++++++++++++++++++-------- usr/src/sys/netinet/tcp_output.c | 12 +++--- usr/src/sys/netinet/tcp_subr.c | 12 ++++-- usr/src/sys/netinet/tcp_timer.c | 24 +++++------- usr/src/sys/netinet/tcp_timer.h | 33 +++++----------- usr/src/sys/netinet/tcp_var.h | 11 ++++-- 6 files changed, 92 insertions(+), 67 deletions(-) diff --git a/usr/src/sys/netinet/tcp_input.c b/usr/src/sys/netinet/tcp_input.c index eb002d6055..e8613e4ecf 100644 --- a/usr/src/sys/netinet/tcp_input.c +++ b/usr/src/sys/netinet/tcp_input.c @@ -3,7 +3,7 @@ * All rights reserved. The Berkeley software License Agreement * specifies the terms and conditions for redistribution. * - * @(#)tcp_input.c 7.5 (Berkeley) %G% + * @(#)tcp_input.c 7.6 (Berkeley) %G% */ #include "param.h" @@ -681,12 +681,46 @@ trimthenstep6: */ if (tp->t_rtt && SEQ_GT(ti->ti_ack, tp->t_rtseq)) { tcpstat.tcps_rttupdated++; - if (tp->t_srtt == 0) - tp->t_srtt = tp->t_rtt; - else - tp->t_srtt = - tcp_alpha * tp->t_srtt + - (1 - tcp_alpha) * tp->t_rtt; + if (tp->t_srtt != 0) { + register short delta; + + /* + * 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). + */ + delta = tp->t_rtt - (tp->t_srtt >> 3); + if ((tp->t_srtt += delta) <= 0) + tp->t_srtt = 1; + /* + * We accumulate a smoothed rtt variance, + * then set the retransmit timer to smoothed + * rtt + 2 times the smoothed variance. + * rttvar is strored 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. + */ + if (delta < 0) + delta = -delta; + delta -= (tp->t_rttvar >> 2); + if ((tp->t_rttvar += delta) <= 0) + tp->t_rttvar = 1; + } else { + /* + * No rtt measurement yet - use the + * unsmoothed rtt. Set the variance + * to half the rtt (so our first + * retransmit happens at 2*rtt) + */ + tp->t_srtt = tp->t_rtt << 3; + tp->t_rttvar = tp->t_rtt << 1; + } tp->t_rtt = 0; } @@ -694,14 +728,15 @@ trimthenstep6: * If all outstanding data is acked, stop retransmit * timer and remember to restart (more output or persist). * If there is more data to be acked, restart retransmit - * timer. + * timer; set to smoothed rtt + 2*rttvar. */ if (ti->ti_ack == tp->snd_max) { tp->t_timer[TCPT_REXMT] = 0; needoutput = 1; } else if (tp->t_timer[TCPT_PERSIST] == 0) { TCPT_RANGESET(tp->t_timer[TCPT_REXMT], - tcp_beta * tp->t_srtt, TCPTV_MIN, TCPTV_MAX); + ((tp->t_srtt >> 2) + tp->t_rttvar) >> 1, + TCPTV_MIN, TCPTV_REXMTMAX); tp->t_rxtshift = 0; } /* @@ -1083,8 +1118,8 @@ tcp_pulloutofband(so, ti) * Determine a reasonable value for maxseg size. * If the route is known, use one that can be handled * on the given interface without forcing IP to fragment. - * If bigger than a page (CLBYTES), round down to nearest pagesize - * to utilize pagesize mbufs. + * If bigger than an mbuf cluster (MCLBYTES), round down to nearest size + * to utilize large mbufs. * If interface pointer is unavailable, or the destination isn't local, * use a conservative size (512 or the default IP max size, but no more * than the mtu of the interface through which we route), @@ -1116,12 +1151,12 @@ tcp_mss(tp) } mss = ifp->if_mtu - sizeof(struct tcpiphdr); -#if (CLBYTES & (CLBYTES - 1)) == 0 - if (mss > CLBYTES) - mss &= ~(CLBYTES-1); +#if (MCLBYTES & (MCLBYTES - 1)) == 0 + if (mss > MCLBYTES) + mss &= ~(MCLBYTES-1); #else - if (mss > CLBYTES) - mss = mss / CLBYTES * CLBYTES; + if (mss > MCLBYTES) + mss = mss / MCLBYTES * MCLBYTES; #endif if (in_localaddr(inp->inp_faddr)) return (mss); diff --git a/usr/src/sys/netinet/tcp_output.c b/usr/src/sys/netinet/tcp_output.c index 241fbd8aca..7c3f009561 100644 --- a/usr/src/sys/netinet/tcp_output.c +++ b/usr/src/sys/netinet/tcp_output.c @@ -3,7 +3,7 @@ * All rights reserved. The Berkeley software License Agreement * specifies the terms and conditions for redistribution. * - * @(#)tcp_output.c 7.6 (Berkeley) %G% + * @(#)tcp_output.c 7.7 (Berkeley) %G% */ #include "param.h" @@ -353,15 +353,16 @@ send: /* * Set retransmit timer if not currently set, * and not doing an ack or a keep-alive probe. - * Initial value for retransmit timer is tcp_beta*tp->t_srtt. + * Initial value for retransmit timer is smoothed + * round-trip time + 2 * round-trip time variance. * Initialize shift counter which is used for backoff * of retransmit time. */ if (tp->t_timer[TCPT_REXMT] == 0 && tp->snd_nxt != tp->snd_una) { TCPT_RANGESET(tp->t_timer[TCPT_REXMT], - tcp_beta * (tp->t_srtt ? tp->t_srtt : TCPTV_SRTTDFLT), - TCPTV_MIN, TCPTV_MAX); + ((tp->t_srtt >> 2) + tp->t_rttvar) >> 1, + TCPTV_MIN, TCPTV_REXMTMAX); tp->t_rxtshift = 0; tp->t_timer[TCPT_PERSIST] = 0; } @@ -404,6 +405,7 @@ send: tcp_setpersist(tp) register struct tcpcb *tp; { + register t = ((tp->t_srtt >> 2) + tp->t_rttvar) >> 1; if (tp->t_timer[TCPT_REXMT]) panic("tcp_output REXMT"); @@ -411,7 +413,7 @@ tcp_setpersist(tp) * Start/restart persistance timer. */ TCPT_RANGESET(tp->t_timer[TCPT_PERSIST], - ((int)(tcp_beta * tp->t_srtt)) << tp->t_rxtshift, + t * tcp_backoff[tp->t_rxtshift], TCPTV_PERSMIN, TCPTV_PERSMAX); if (tp->t_rxtshift < TCP_MAXRXTSHIFT) tp->t_rxtshift++; diff --git a/usr/src/sys/netinet/tcp_subr.c b/usr/src/sys/netinet/tcp_subr.c index 415968211f..8e900e1e7b 100644 --- a/usr/src/sys/netinet/tcp_subr.c +++ b/usr/src/sys/netinet/tcp_subr.c @@ -3,7 +3,7 @@ * All rights reserved. The Berkeley software License Agreement * specifies the terms and conditions for redistribution. * - * @(#)tcp_subr.c 7.6 (Berkeley) %G% + * @(#)tcp_subr.c 7.7 (Berkeley) %G% */ #include "param.h" @@ -31,8 +31,6 @@ #include "tcpip.h" int tcp_ttl = TCP_TTL; -float tcp_alpha = TCP_ALPHA; -float tcp_beta = TCP_BETA; /* * Tcp initialization @@ -169,7 +167,13 @@ tcp_newtcpcb(inp) tp->t_maxseg = TCP_MSS; tp->t_flags = 0; /* sends options! */ tp->t_inpcb = inp; - tp->t_srtt = TCPTV_SRTTBASE; + /* + * Init srtt to 0, so we can tell that we have no rtt estimate. + * Set rttvar so that srtt + 2 * rttvar gives reasonable initial + * retransmit time. + */ + tp->t_srtt = 0; + tp->t_rttvar = TCPTV_SRTTBASE << 2; tp->snd_cwnd = sbspace(&inp->inp_socket->so_snd); inp->inp_ppcb = (caddr_t)tp; return (tp); diff --git a/usr/src/sys/netinet/tcp_timer.c b/usr/src/sys/netinet/tcp_timer.c index f0bf78b285..3318bf00fd 100644 --- a/usr/src/sys/netinet/tcp_timer.c +++ b/usr/src/sys/netinet/tcp_timer.c @@ -3,7 +3,7 @@ * All rights reserved. The Berkeley software License Agreement * specifies the terms and conditions for redistribution. * - * @(#)tcp_timer.c 7.5 (Berkeley) %G% + * @(#)tcp_timer.c 7.6 (Berkeley) %G% */ #include "param.h" @@ -112,8 +112,8 @@ tcp_canceltimers(tp) tp->t_timer[i] = 0; } -int tcp_backoff[TCP_MAXRXTSHIFT+1] = - { 1, 2, 4, 6, 8, 10, 15, 20, 30, 30, 30, 30, 30 }; +int tcp_backoff[TCP_MAXRXTSHIFT] = + { 2, 4, 8, 16, 32, 64, 64, 64, 64, 64, 64, 64 }; int tcp_keeplen = 1; /* must be nonzero for 4.2 compat- XXX */ @@ -149,18 +149,15 @@ tcp_timers(tp, timer) * to a longer retransmit interval and retransmit one segment. */ case TCPT_REXMT: - tp->t_rxtshift++; - if (tp->t_rxtshift > TCP_MAXRXTSHIFT) { + if (tp->t_rxtshift >= TCP_MAXRXTSHIFT) { tcpstat.tcps_timeoutdrop++; tp = tcp_drop(tp, ETIMEDOUT); break; } tcpstat.tcps_rexmttimeo++; - if (tp->t_srtt == 0) - rexmt = tcp_beta * TCPTV_SRTTDFLT; - else - rexmt = (int)(tcp_beta * tp->t_srtt); - rexmt *= tcp_backoff[tp->t_rxtshift - 1]; + rexmt = ((tp->t_srtt >> 2) + tp->t_rttvar) >> 1; + rexmt *= tcp_backoff[tp->t_rxtshift]; + tp->t_rxtshift++; TCPT_RANGESET(tp->t_timer[TCPT_REXMT], rexmt, TCPTV_MIN, TCPTV_MAX); /* @@ -172,12 +169,9 @@ tcp_timers(tp, timer) in_losing(tp->t_inpcb); tp->snd_nxt = tp->snd_una; /* - * If timing a segment in this window, - * and we have already gotten some timing estimate, - * stop the timer. + * If timing a segment in this window, stop the timer. */ - if (tp->t_rtt && tp->t_srtt) - tp->t_rtt = 0; + tp->t_rtt = 0; /* * Close the congestion window down to one segment * (we'll open it by one segment for each ack we get). diff --git a/usr/src/sys/netinet/tcp_timer.h b/usr/src/sys/netinet/tcp_timer.h index 293bfba384..d6d49741fc 100644 --- a/usr/src/sys/netinet/tcp_timer.h +++ b/usr/src/sys/netinet/tcp_timer.h @@ -3,7 +3,7 @@ * All rights reserved. The Berkeley software License Agreement * specifies the terms and conditions for redistribution. * - * @(#)tcp_timer.h 7.2 (Berkeley) %G% + * @(#)tcp_timer.h 7.3 (Berkeley) %G% */ /* @@ -61,14 +61,15 @@ int tcp_ttl; /* time to live for TCP segs */ if 0, no idea yet */ #define TCPTV_SRTTDFLT ( 3*PR_SLOWHZ) /* assumed RTT if no info */ -#define TCPTV_KEEP ( 45*PR_SLOWHZ) /* keep alive - 45 secs */ #define TCPTV_PERSMIN ( 5*PR_SLOWHZ) /* retransmit persistance */ +#define TCPTV_PERSMAX ( 60*PR_SLOWHZ) /* maximum persist interval */ +#define TCPTV_KEEP ( 75*PR_SLOWHZ) /* keep alive - 75 secs */ #define TCPTV_MAXIDLE ( 8*TCPTV_KEEP) /* maximum allowable idle time before drop conn */ #define TCPTV_MIN ( 1*PR_SLOWHZ) /* minimum allowable value */ -#define TCPTV_MAX ( 30*PR_SLOWHZ) /* maximum allowable value */ +#define TCPTV_REXMTMAX ( 64*PR_SLOWHZ) /* max allowable REXMT value */ #define TCP_LINGERTIME 120 /* linger at most 2 minutes */ @@ -79,26 +80,6 @@ char *tcptimers[] = { "REXMT", "PERSIST", "KEEP", "2MSL" }; #endif -/* - * Retransmission smoothing constants. - * Smoothed round trip time is updated by - * tp->t_srtt = (tcp_alpha * tp->t_srtt) + ((1 - tcp_alpha) * tp->t_rtt) - * each time a new value of tp->t_rtt is available. The initial - * retransmit timeout is then based on - * tp->t_timer[TCPT_REXMT] = tcp_beta * tp->t_srtt; - * limited, however to be at least TCPTV_MIN and at most TCPTV_MAX. - */ -float tcp_alpha, tcp_beta; - -/* - * Initial values of tcp_alpha and tcp_beta. - * These are conservative: averaging over a long - * period of time, and allowing for large individual deviations from - * tp->t_srtt. - */ -#define TCP_ALPHA 0.9 -#define TCP_BETA 2.0 - /* * Force a time value to be in a certain range. */ @@ -106,6 +87,10 @@ float tcp_alpha, tcp_beta; (tv) = (value); \ if ((tv) < (tvmin)) \ (tv) = (tvmin); \ - if ((tv) > (tvmax)) \ + else if ((tv) > (tvmax)) \ (tv) = (tvmax); \ } + +#ifdef KERNEL +extern int tcp_backoff[]; +#endif diff --git a/usr/src/sys/netinet/tcp_var.h b/usr/src/sys/netinet/tcp_var.h index 44c3672f2f..20dcd774e2 100644 --- a/usr/src/sys/netinet/tcp_var.h +++ b/usr/src/sys/netinet/tcp_var.h @@ -3,7 +3,7 @@ * All rights reserved. The Berkeley software License Agreement * specifies the terms and conditions for redistribution. * - * @(#)tcp_var.h 7.2 (Berkeley) %G% + * @(#)tcp_var.h 7.3 (Berkeley) %G% */ /* @@ -58,12 +58,17 @@ struct tcpcb { */ /* congestion control (for source quench) */ u_short snd_cwnd; /* congestion-controlled window */ -/* transmit timing stuff */ +/* + * transmit timing stuff. + * srtt and rttvar are stored as fixed point; for convenience in smoothing, + * srtt has 3 bits to the right of the binary point, rttvar has 2. + */ short t_idle; /* inactivity time */ short t_rtt; /* round trip time */ u_short max_rcvd; /* most peer has sent into window */ tcp_seq t_rtseq; /* sequence number being timed */ - float t_srtt; /* smoothed round-trip time */ + short t_srtt; /* smoothed round-trip time */ + short t_rttvar; /* variance in round-trip time */ u_short max_sndwnd; /* largest window peer has offered */ /* out-of-band data */ char t_oobflags; /* have some */ -- 2.20.1