Loading ...
Sorry, an error occurred while loading the content.

viewgraphs on revisions to RFC 2001

Expand Messages
  • Sally Floyd
    My viewgraphs on Reno, NewReno, and the bugfix to avoid multiple fast retransmits, from the Friday tcpimpl meeting in Chicago, are available as follows:
    Message 1 of 6 , Aug 29 6:30 PM
    • 0 Attachment
      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".
    • eewechta@swansea.ac.uk
      Hi, RFC 1016 has not been obsoleted by any other RFC. I have been told few times that Source Quench is defunct and that it is not implemented in many
      Message 2 of 6 , Aug 31 5:36 AM
      • 0 Attachment
        Hi,

        RFC 1016 has not been obsoleted by any other RFC. I have been told few times
        that Source Quench is "defunct" and that it is not implemented in many routers.
        However, could someone comment on the oficial status of Source Quench, please.

        Thank you,

        Jerzy Wechta


        __________________________________
        Jerzy Wechta
        Communication Research Group
        University of Wales, Swansea
        Singleton Park SA2 8BB
        Swanesa, UK

        e-mail eewechta@...
        j.wechta@...
        tel (+44) 1792 295541
        fax (+44) 1792 295686
      • eewechta@swansea.ac.uk
        Hi, RFC 1016 has not been obsoleted by any other RFC. I have been told few times that Source Quench is defunct and that it is not implemented in many
        Message 3 of 6 , Aug 31 5:54 AM
        • 0 Attachment
          Hi,

          RFC 1016 has not been obsoleted by any other RFC. I have been told few times
          that Source Quench is "defunct" and that it is not implemented in many routers.
          However, could someone comment on the oficial status of Source Quench, please.

          Thank you,

          Jerzy Wechta

          PS. I tried to send this e-mail to tcp-impl@... but I receive
          an Undeliverable Message.

          __________________________________
          Jerzy Wechta
          Communication Research Group
          University of Wales, Swansea
          Singleton Park SA2 8BB
          Swanesa, UK

          e-mail eewechta@...
          j.wechta@...
          tel (+44) 1792 295541
          fax (+44) 1792 295686
        • braden@ISI.EDU
          * From owner-tcp-impl@cthulhu.engr.sgi.com Mon Aug 31 05:26:57 1998 * From: eewechta@swansea.ac.uk * Date: Mon, 31 Aug 1998 13:36:33 +0100 (BST) *
          Message 4 of 6 , Aug 31 10:51 AM
          • 0 Attachment
            *> From owner-tcp-impl@... Mon Aug 31 05:26:57 1998
            *> From: eewechta@...
            *> Date: Mon, 31 Aug 1998 13:36:33 +0100 (BST)
            *> Reply-To: eewechta@...
            *> Subject: RFC 1016 - source quench
            *> To: tcp-impl@...
            *> cc: eewechta@...
            *> In-Reply-To: <199808300130.SAA19711@...>
            *> MIME-Version: 1.0
            *> Content-Type *> : *> text/PLAIN *> ; *> CHARSET="US-ASCII" *>
            *> Sender: owner-tcp-impl@...
            *> Precedence: bulk
            *> Content-Length: 544
            *> X-Lines: 23
            *>
            *> Hi,
            *>
            *> RFC 1016 has not been obsoleted by any other RFC. I have been told few times
            *> that Source Quench is "defunct" and that it is not implemented in many routers.
            *> However, could someone comment on the oficial status of Source Quench, please.
            *>
            *> Thank you,
            *>
            *> Jerzy Wechta
            *>
            *>

            AFAIK, the latest official word is 3.2.2.3 of RFC 1122.

            Bob Braden

            *> __________________________________
            *> Jerzy Wechta
            *> Communication Research Group
            *> University of Wales, Swansea
            *> Singleton Park SA2 8BB
            *> Swanesa, UK
            *>
            *> e-mail eewechta@...
            *> j.wechta@...
            *> tel (+44) 1792 295541
            *> fax (+44) 1792 295686
            *>
            *>
          • Thomas Narten
            Message 5 of 6 , Aug 31 11:21 AM
            • 0 Attachment
              >> RFC 1016 has not been obsoleted by any other RFC. I have been told few times
              >> that Source Quench is "defunct" and that it is not implemented in many routers.
              >> However, could someone comment on the oficial status of Source Quench, please.

              > AFAIK, the latest official word is 3.2.2.3 of RFC 1122.

              RFC 1812 (Requirements for IP Version 4 Routers) says:

              > 4.3.3.3 Source Quench
              >
              > A router SHOULD NOT originate ICMP Source Quench messages. As
              > specified in Section [4.3.2], a router that does originate Source
              > Quench messages MUST be able to limit the rate at which they are
              > generated.
              >
              > DISCUSSION
              > Research seems to suggest that Source Quench consumes network
              > bandwidth but is an ineffective (and unfair) antidote to
              > congestion. See, for example, [INTERNET:9] and [INTERNET:10].
              > Section [5.3.6] discusses the current thinking on how routers
              > ought to deal with overload and network congestion.
            • Kacheong Poon
              ... A very late reply... Just to repeat what I mentioned in the IETF meeting. The reason to reset the retransmit timer only for the first partial ACK is to
              Message 6 of 6 , Sep 23, 1998
              • 0 Attachment
                > 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.

                A very late reply... Just to repeat what I mentioned in the IETF meeting. The
                reason to reset the retransmit timer only for the first partial ACK is to
                avoid a stop and go behaviour. But this also limits the number of segments
                NewReno can recover. An implementation with a coarse grain timer, like in BSD
                RTO is in the order of 500ms, can recover more segments than an implementation
                with a finer grain timer. The number of segments which can be recovered also
                depends on the RTT. For a satellite link, RTT is ~520ms. Say with BSD, RTO
                may be 1.5s for such link. That means NewReno can only recover 2 additional
                segments before a timeout happens. And for such LFN, TCP window is usually
                very large. It is likely that more than 3 segments can be dropped in a window.
                In [H96], the algorithm suggested is a little bit different from the above.
                During the fast retransmit phase, a slow start like mechanism is used. That
                means for one RTT, more than one segment can be recovered. NewReno can only
                recover one segment. This reduces the impact of stop and go behaviour. This
                is more aggressive and can potentially retransmit quite a few duplicate
                segments. But for LFN, this can be a big help. For relatively small window
                and short RTT, the gain is small compared to NewReno.

                K. Poon.
                kcpoon@...
              Your message has been successfully submitted and would be delivered to recipients shortly.