viewgraphs on revisions to RFC 2001

[Sally Floyd <[e-mail]>]

My viewgraphs on Reno, NewReno, and the bugfix to
avoid multiple fast retransmits, from the Friday tcpimpl
meeting in Chicago, are available as follows:

  ftp://ftp.ee.lbl.gov/talks/sf-tcpimpl-aug98.ps
and:
  ftp://ftp.ee.lbl.gov/talks/sf-tcpimpl-aug98.pdf

The description of the NewReno and avoiding-multiple-fast-retransmit
changes illustrated in those viewgraphs is given below.

These tests can be run with "./test-all-newreno" in directory
tcl/test in the ns simulator (starting with the daily snapshop
that will be available tonight).

- Sally
--------------------------------
http://www-nrg.ee.lbl.gov/floyd/
--------------------------------

Draft text for revising the five steps in Section 3.3 on Fast
Retransmit/Fast Recovery in "TCP Congestion Control",
draft-ietf-tcpimpl-cong-control-00.txt, URL
"http://www.ietf.org/internet-drafts/draft-ietf-tcpimpl-cong-control-00.txt".

    Implementing fast retransmit/fast recovery in this manner (often
    referred to as Reno congestion control) allows the fast retransmit
    algorithm to repair multiple dropped segments from a single
    window of data in some cases [FF96].  However, Reno congestion
    control has several well-documented problems.  First, for *most*
    cases of multiple dropped segments from a single window of
    data, Reno congestion control is unable to recover without a
    retransmit timeout [H96, FF96].  A second well-documented
    problem with both Tahoe and Reno congestion control algorithms
    is that multiple segment losses from a single window of data
    can sometimes result in unnecessary multiple fast retransmits
    (and multiple reductions of the congestion window) [Flo94].

    The following two changes (sometimes referred to as NewReno
    and "avoiding multiple fast retransmits") MAY be taken to
    address the first and second problems listed above.  These two
    changes are orthogonal - one could implement one without the
    other.  For simplicity, the steps below illustrate the two
    changes implemented together.

    1A.  After the third duplicate ACK is received, check to see
	 if those duplicate ACKs cover send_high.  If they do, then
	 follow steps 1 and 2 above, and also record the highest
	 sequence number transmitted (send_high and recover).  If
	 the duplicate ACKs don't cover send_high, then do nothing.
	 (This is "avoiding multiple fast retransmits".) That is,
	 do not change ssthresh or cwnd, and do not retransmit the
	 "lost" segment.

	 Steps 3 and 4 remain unchanged.

    5A.  When a non-duplicate ACK arrives that covers "recover",
	 follow step 5 above.  When a non-duplicate ACK arrives
	 that does not cover "recover" (i.e., a "partial ack"),
	 retransmit the first unacknowledged segment.  (This is
	 "NewReno".) Do not change cwnd or ssthresh, but deflate
	 the congestion window by removing the additive term with
	 the count of duplicate acknowledgements.  For the first
	 partial ACK that arrives, also reset the retransmit timer.

    6.  After a retransmit timeout, record the highest sequence number
        transmitted (send_high).

----------------------------------------------------------------

    This is the NewReno change by itself:

    1A.  After the third duplicate ACK is received, follow steps
	 1 and 2 above, and also record the highest sequence number
	 transmitted ("recover").

	 Steps 3 and 4 remain unchanged.

    5A.  This is the same as step 5A above.

----------------------------------------------------------------

    This is the "avoiding multiple fast retransmits" change by itself,
    *without* NewReno:

    1A.  After the third duplicate ACK is received, check to see
	 if those duplicate ACKs cover send_high.  If they do, then
	 follow steps 1 and 2 above.  (If this was implemented *with*
	 NewReno, this step would also include recording the highest
	 sequence number transmitted in send_high.)  If the duplicate
	 ACKs don't cover send_high, then do nothing.  That is, do not
	 change ssthresh or cwnd, and do not retransmit the "lost"
	 segment.

	 Steps 3, 4, and 5 remain unchanged.

    6.  After a retransmit timeout, record the highest sequence number
        transmitted (send_high).

--------------------------------------------------------------------

New References:

    [H96] J. Hoe, "Improving the Start-up Behavior of a Congestion
    Control Scheme for TCP", SIGCOMM 96, August 1996.  URL
    "http://www.acm.org/sigcomm/sigcomm96/papers/hoe.html".