One document matched: draft-ietf-tsvwg-newreno-01.ps
%!PS-Adobe-3.0
%%BoundingBox: 24 24 588 768
%%Title: Enscript Output
%%For: Sally Floyd
%%Creator: GNU enscript 1.6.1
%%CreationDate: Wed Oct 1 13:47:50 2003
%%Orientation: Portrait
%%Pages: (atend)
%%DocumentMedia: Letter 612 792 0 () ()
%%DocumentNeededResources: (atend)
%%EndComments
%%BeginProlog
%%BeginResource: procset Enscript-Prolog 1.6 1
%
% Procedures.
%
/_S { % save current state
/_s save def
} def
/_R { % restore from saved state
_s restore
} def
/S { % showpage protecting gstate
gsave
showpage
grestore
} bind def
/MF { % fontname newfontname -> - make a new encoded font
/newfontname exch def
/fontname exch def
/fontdict fontname findfont def
/newfont fontdict maxlength dict def
fontdict {
exch
dup /FID eq {
% skip FID pair
pop pop
} {
% copy to the new font dictionary
exch newfont 3 1 roll put
} ifelse
} forall
newfont /FontName newfontname put
% insert only valid encoding vectors
encoding_vector length 256 eq {
newfont /Encoding encoding_vector put
} if
newfontname newfont definefont pop
} def
/SF { % fontname width height -> - set a new font
/height exch def
/width exch def
findfont
[width 0 0 height 0 0] makefont setfont
} def
/SUF { % fontname width height -> - set a new user font
/height exch def
/width exch def
/F-gs-user-font MF
/F-gs-user-font width height SF
} def
/M {moveto} bind def
/s {show} bind def
/Box { % x y w h -> - define box path
/d_h exch def /d_w exch def /d_y exch def /d_x exch def
d_x d_y moveto
d_w 0 rlineto
0 d_h rlineto
d_w neg 0 rlineto
closepath
} def
/bgs { % x y height blskip gray str -> - show string with bg color
/str exch def
/gray exch def
/blskip exch def
/height exch def
/y exch def
/x exch def
gsave
x y blskip sub str stringwidth pop height Box
gray setgray
fill
grestore
x y M str s
} def
% Highlight bars.
/highlight_bars { % nlines lineheight output_y_margin gray -> -
gsave
setgray
/ymarg exch def
/lineheight exch def
/nlines exch def
% This 2 is just a magic number to sync highlight lines to text.
0 d_header_y ymarg sub 2 sub translate
/cw d_output_w cols div def
/nrows d_output_h ymarg 2 mul sub lineheight div cvi def
% for each column
0 1 cols 1 sub {
cw mul /xp exch def
% for each rows
0 1 nrows 1 sub {
/rn exch def
rn lineheight mul neg /yp exch def
rn nlines idiv 2 mod 0 eq {
% Draw highlight bar. 4 is just a magic indentation.
xp 4 add yp cw 8 sub lineheight neg Box fill
} if
} for
} for
grestore
} def
% Line highlight bar.
/line_highlight { % x y width height gray -> -
gsave
/gray exch def
Box gray setgray fill
grestore
} def
% Column separator lines.
/column_lines {
gsave
.1 setlinewidth
0 d_footer_h translate
/cw d_output_w cols div def
1 1 cols 1 sub {
cw mul 0 moveto
0 d_output_h rlineto stroke
} for
grestore
} def
% Column borders.
/column_borders {
gsave
.1 setlinewidth
0 d_footer_h moveto
0 d_output_h rlineto
d_output_w 0 rlineto
0 d_output_h neg rlineto
closepath stroke
grestore
} def
% Do the actual underlay drawing
/draw_underlay {
ul_style 0 eq {
ul_str true charpath stroke
} {
ul_str show
} ifelse
} def
% Underlay
/underlay { % - -> -
gsave
0 d_page_h translate
d_page_h neg d_page_w atan rotate
ul_gray setgray
ul_font setfont
/dw d_page_h dup mul d_page_w dup mul add sqrt def
ul_str stringwidth pop dw exch sub 2 div ul_h_ptsize -2 div moveto
draw_underlay
grestore
} def
/user_underlay { % - -> -
gsave
ul_x ul_y translate
ul_angle rotate
ul_gray setgray
ul_font setfont
0 0 ul_h_ptsize 2 div sub moveto
draw_underlay
grestore
} def
% Page prefeed
/page_prefeed { % bool -> -
statusdict /prefeed known {
statusdict exch /prefeed exch put
} {
pop
} ifelse
} def
% Wrapped line markers
/wrapped_line_mark { % x y charwith charheight type -> -
/type exch def
/h exch def
/w exch def
/y exch def
/x exch def
type 2 eq {
% Black boxes (like TeX does)
gsave
0 setlinewidth
x w 4 div add y M
0 h rlineto w 2 div 0 rlineto 0 h neg rlineto
closepath fill
grestore
} {
type 3 eq {
% Small arrows
gsave
.2 setlinewidth
x w 2 div add y h 2 div add M
w 4 div 0 rlineto
x w 4 div add y lineto stroke
x w 4 div add w 8 div add y h 4 div add M
x w 4 div add y lineto
w 4 div h 8 div rlineto stroke
grestore
} {
% do nothing
} ifelse
} ifelse
} def
% EPSF import.
/BeginEPSF {
/b4_Inc_state save def % Save state for cleanup
/dict_count countdictstack def % Count objects on dict stack
/op_count count 1 sub def % Count objects on operand stack
userdict begin
/showpage { } def
0 setgray 0 setlinecap
1 setlinewidth 0 setlinejoin
10 setmiterlimit [ ] 0 setdash newpath
/languagelevel where {
pop languagelevel
1 ne {
false setstrokeadjust false setoverprint
} if
} if
} bind def
/EndEPSF {
count op_count sub { pos } repeat % Clean up stacks
countdictstack dict_count sub { end } repeat
b4_Inc_state restore
} bind def
% Check PostScript language level.
/languagelevel where {
pop /gs_languagelevel languagelevel def
} {
/gs_languagelevel 1 def
} ifelse
%%EndResource
%%BeginResource: procset Enscript-Encoding-88591 1.6 1
/encoding_vector [
/.notdef /.notdef /.notdef /.notdef
/.notdef /.notdef /.notdef /.notdef
/.notdef /.notdef /.notdef /.notdef
/.notdef /.notdef /.notdef /.notdef
/.notdef /.notdef /.notdef /.notdef
/.notdef /.notdef /.notdef /.notdef
/.notdef /.notdef /.notdef /.notdef
/.notdef /.notdef /.notdef /.notdef
/space /exclam /quotedbl /numbersign
/dollar /percent /ampersand /quoteright
/parenleft /parenright /asterisk /plus
/comma /hyphen /period /slash
/zero /one /two /three
/four /five /six /seven
/eight /nine /colon /semicolon
/less /equal /greater /question
/at /A /B /C
/D /E /F /G
/H /I /J /K
/L /M /N /O
/P /Q /R /S
/T /U /V /W
/X /Y /Z /bracketleft
/backslash /bracketright /asciicircum /underscore
/quoteleft /a /b /c
/d /e /f /g
/h /i /j /k
/l /m /n /o
/p /q /r /s
/t /u /v /w
/x /y /z /braceleft
/bar /braceright /tilde /.notdef
/.notdef /.notdef /.notdef /.notdef
/.notdef /.notdef /.notdef /.notdef
/.notdef /.notdef /.notdef /.notdef
/.notdef /.notdef /.notdef /.notdef
/.notdef /.notdef /.notdef /.notdef
/.notdef /.notdef /.notdef /.notdef
/.notdef /.notdef /.notdef /.notdef
/.notdef /.notdef /.notdef /.notdef
/space /exclamdown /cent /sterling
/currency /yen /brokenbar /section
/dieresis /copyright /ordfeminine /guillemotleft
/logicalnot /hyphen /registered /macron
/degree /plusminus /twosuperior /threesuperior
/acute /mu /paragraph /bullet
/cedilla /onesuperior /ordmasculine /guillemotright
/onequarter /onehalf /threequarters /questiondown
/Agrave /Aacute /Acircumflex /Atilde
/Adieresis /Aring /AE /Ccedilla
/Egrave /Eacute /Ecircumflex /Edieresis
/Igrave /Iacute /Icircumflex /Idieresis
/Eth /Ntilde /Ograve /Oacute
/Ocircumflex /Otilde /Odieresis /multiply
/Oslash /Ugrave /Uacute /Ucircumflex
/Udieresis /Yacute /Thorn /germandbls
/agrave /aacute /acircumflex /atilde
/adieresis /aring /ae /ccedilla
/egrave /eacute /ecircumflex /edieresis
/igrave /iacute /icircumflex /idieresis
/eth /ntilde /ograve /oacute
/ocircumflex /otilde /odieresis /divide
/oslash /ugrave /uacute /ucircumflex
/udieresis /yacute /thorn /ydieresis
] def
%%EndResource
%%EndProlog
%%BeginSetup
%%IncludeResource: font Courier-Bold
%%IncludeResource: font Courier
/HFpt_w 10 def
/HFpt_h 10 def
/Courier-Bold /HF-gs-font MF
/HF /HF-gs-font findfont [HFpt_w 0 0 HFpt_h 0 0] makefont def
/Courier /F-gs-font MF
/F-gs-font 10 10 SF
/#copies 1 def
% Pagedevice definitions:
gs_languagelevel 1 gt {
<<
/PageSize [612 792]
>> setpagedevice
} if
/d_page_w 564 def
/d_page_h 744 def
/d_header_x 0 def
/d_header_y 744 def
/d_header_w 564 def
/d_header_h 0 def
/d_footer_x 0 def
/d_footer_y 0 def
/d_footer_w 564 def
/d_footer_h 0 def
/d_output_w 564 def
/d_output_h 744 def
/cols 1 def
%%EndSetup
%%Page: (1) 1
%%BeginPageSetup
_S
24 24 translate
/pagenum 1 def
/fname (draft-ietf-tsvwg-newreno-01.txt) def
/fdir () def
/ftail (draft-ietf-tsvwg-newreno-01.txt) def
/user_header_p false def
%%EndPageSetup
5 665 M
(Internet Engineering Task Force S. Floyd) s
5 654 M
(INTERNET DRAFT ICSI) s
5 643 M
(draft-ietf-tsvwg-newreno-01.txt T. Henderson) s
5 632 M
( Boeing) s
5 621 M
( A. Gurtov) s
5 610 M
( U. Helsinki) s
5 599 M
( September 2003) s
5 566 M
( The NewReno Modification to TCP's Fast Recovery Algorithm) s
5 522 M
( Status of this Memo) s
5 489 M
( This document is an Internet-Draft and is in full conformance with) s
5 478 M
( all provisions of Section 10 of RFC2026.) s
5 456 M
( Internet-Drafts are working documents of the Internet Engineering) s
5 445 M
( Task Force \(IETF\), its areas, and its working groups. Note that) s
5 434 M
( other groups may also distribute working documents as Internet-) s
5 423 M
( Drafts.) s
5 401 M
( Internet-Drafts are draft documents valid for a maximum of six months) s
5 390 M
( and may be updated, replaced, or obsoleted by other documents at any) s
5 379 M
( time. It is inappropriate to use Internet-Drafts as reference) s
5 368 M
( material or to cite them other than as "work in progress.") s
5 346 M
( The list of current Internet-Drafts can be accessed at) s
5 335 M
( http://www.ietf.org/ietf/1id-abstracts.txt) s
5 313 M
( The list of Internet-Draft Shadow Directories can be accessed at) s
5 302 M
( http://www.ietf.org/shadow.html.) s
5 280 M
(Abstract) s
5 258 M
( RFC 2581 [RFC2581] documents the following four intertwined TCP) s
5 247 M
( congestion control algorithms: Slow Start, Congestion Avoidance, Fast) s
5 236 M
( Retransmit, and Fast Recovery. RFC 2581 [RFC2581] explicitly allows) s
5 225 M
( certain modifications of these algorithms, including modifications) s
5 214 M
( that use the TCP Selective Acknowledgement \(SACK\) option [RFC2018],) s
5 203 M
( and modifications that respond to "partial acknowledgments" \(ACKs) s
5 192 M
( which cover new data, but not all the data outstanding when loss was) s
5 181 M
( detected\) in the absence of SACK. The NewReno mechanism uses an) s
5 170 M
( algorithm for responding to partial acknowledgments that was first) s
5 159 M
( proposed by Janey Hoe in [Hoe95].) s
5 104 M
(Floyd et al. [Page 1]) s
_R
S
%%Page: (2) 2
%%BeginPageSetup
_S
24 24 translate
/pagenum 2 def
/fname (draft-ietf-tsvwg-newreno-01.txt) def
/fdir () def
/ftail (draft-ietf-tsvwg-newreno-01.txt) def
/user_header_p false def
%%EndPageSetup
5 698 M
(draft-ietf-tsvwg-newreno September 2003) s
5 665 M
( RFC 2582 [RFC2582] specified the NewReno mechanisms as Experimental) s
5 654 M
( in 1999. This document is a small revision of RFC 2582 intended to) s
5 643 M
( advance the NewReno mechanisms to Proposed Standard. RFC 2581 notes) s
5 632 M
( that the Fast Retransmit/Fast Recovery algorithm specified in that) s
5 621 M
( document does not recover very efficiently from multiple losses in a) s
5 610 M
( single flight of packets, and that RFC 2582 contains one set of) s
5 599 M
( modifications to address this problem.) s
5 577 M
( NOTE TO THE RFC EDITOR: PLEASE REMOVE THIS SECTION UPON PUBLICATION.) s
5 555 M
( Changes from draft-ietf-tsvwg-newreno-00.txt:) s
5 533 M
( * In Section 8, added a cautionary note about using the duplicate) s
5 522 M
( acknowledgment counter as a flag for whether Fast Recovery is in) s
5 511 M
( effect.) s
5 489 M
( * In Section 8, added a note about pulling along "recover" with) s
5 478 M
( "snd_una" when Fast Recovery is not in effect.) s
5 456 M
( * Added a discussion in Section 6 about heuristics for distinguishing) s
5 445 M
( between a retransmitted packet that was dropped, and three duplicate) s
5 434 M
( acknowledgements simply from the unnecessary retransmission of three) s
5 423 M
( packets.) s
5 401 M
( * Added more text and examples for comparing the Impatient and the) s
5 390 M
( Slow-but-Steady variants.) s
5 368 M
( * In Section 8, added a cautionary note saying that when the sender) s
5 357 M
( is not in Fast Retransmit, the sender should not use the Fast) s
5 346 M
( Recovery response to multiple duplicate acknowledgements.) s
5 324 M
( Changes from draft-floyd-newreno-00.txt:) s
5 302 M
( * In Section 8 on "Implementation issues for the data sender",) s
5 291 M
( mentioned alternate methods for limiting bursts when exiting Fast) s
5 280 M
( Recovery.) s
5 258 M
( * Changed draft from draft-floyd-newreno to draft-ietf-tsvwg-newreno) s
5 236 M
( Changes from RFC 2582:) s
5 214 M
( * Rephrasing and rearrangements of the text.) s
5 192 M
( * RFC 2582 described the Careful and Less Careful variants of) s
5 181 M
( NewReno, along with a default version that was neither Careful nor) s
5 170 M
( Less Careful, and recommended the Careful variant. This document) s
5 159 M
( only specifies the Careful version.) s
5 104 M
(Floyd et al. [Page 2]) s
_R
S
%%Page: (3) 3
%%BeginPageSetup
_S
24 24 translate
/pagenum 3 def
/fname (draft-ietf-tsvwg-newreno-01.txt) def
/fdir () def
/ftail (draft-ietf-tsvwg-newreno-01.txt) def
/user_header_p false def
%%EndPageSetup
5 698 M
(draft-ietf-tsvwg-newreno September 2003) s
5 665 M
( * RFC 2582 used two separate variables, "send_high" and "recover",) s
5 654 M
( and this document has merged them into a single variable "recover".) s
5 632 M
( * Added sections on "Comparisons between Reno and NewReno TCP", and) s
5 621 M
( on "Changes relative to RFC 2582". The section on "Comparisons) s
5 610 M
( between Reno and NewReno TCP" includes a discussion of the one area) s
5 599 M
( where NewReno is known to perform worse than Reno or SACK, and that) s
5 588 M
( is in the response to reordering.) s
5 566 M
( * Moved all of the discussions of the Impatient and Slow-but-Steady) s
5 555 M
( variants to one place, and recommended the Impatient variant \(as in) s
5 544 M
( the default version in RFC 2582\).) s
5 522 M
( * Added a section on Implementation issues for the data sender,) s
5 511 M
( mentioning maxburst_.) s
5 489 M
( * Added a paragraph about differences between RFC 2582 and [FF96].) s
5 467 M
( END OF NOTE TO RFC EDITOR) s
5 445 M
(1. Introduction) s
5 423 M
( For the typical implementation of the TCP Fast Recovery algorithm) s
5 412 M
( described in [RFC2581] \(first implemented in the 1990 BSD Reno) s
5 401 M
( release, and referred to as the Reno algorithm in [FF96]\), the TCP) s
5 390 M
( data sender only retransmits a packet after a retransmit timeout has) s
5 379 M
( occurred, or after three duplicate acknowledgements have arrived) s
5 368 M
( triggering the Fast Retransmit algorithm. A single retransmit) s
5 357 M
( timeout might result in the retransmission of several data packets,) s
5 346 M
( but each invocation of the Fast Retransmit algorithm in RFC 2581) s
5 335 M
( leads to the retransmission of only a single data packet.) s
5 313 M
( Problems can arise, therefore, when multiple packets have been) s
5 302 M
( dropped from a single window of data and the Fast Retransmit and Fast) s
5 291 M
( Recovery algorithms are invoked. In this case, if the SACK option is) s
5 280 M
( available, the TCP sender has the information to make intelligent) s
5 269 M
( decisions about which packets to retransmit and which packets not to) s
5 258 M
( retransmit during Fast Recovery. This document applies only for TCP) s
5 247 M
( connections that are unable to use the TCP Selective Acknowledgement) s
5 236 M
( \(SACK\) option, either because the option is not locally supported or) s
5 225 M
( because the TCP peer did not indicate a willingness to use SACK.) s
5 203 M
( In the absence of SACK, there is little information available to the) s
5 192 M
( TCP sender in making retransmission decisions during Fast Recovery.) s
5 181 M
( From the three duplicate acknowledgements, the sender infers a packet) s
5 170 M
( loss, and retransmits the indicated packet. After this, the data) s
5 159 M
( sender could receive additional duplicate acknowledgements, as the) s
5 148 M
( data receiver acknowledges additional data packets that were already) s
5 104 M
(Floyd et al. [Page 3]) s
_R
S
%%Page: (4) 4
%%BeginPageSetup
_S
24 24 translate
/pagenum 4 def
/fname (draft-ietf-tsvwg-newreno-01.txt) def
/fdir () def
/ftail (draft-ietf-tsvwg-newreno-01.txt) def
/user_header_p false def
%%EndPageSetup
5 698 M
(draft-ietf-tsvwg-newreno September 2003) s
5 665 M
( in flight when the sender entered Fast Retransmit.) s
5 643 M
( In the case of multiple packets dropped from a single window of data,) s
5 632 M
( the first new information available to the sender comes when the) s
5 621 M
( sender receives an acknowledgement for the retransmitted packet \(that) s
5 610 M
( is, the packet retransmitted when Fast Retransmit was first entered\).) s
5 599 M
( If there had been a single packet drop and no reordering, then the) s
5 588 M
( acknowledgement for this packet will acknowledge all of the packets) s
5 577 M
( transmitted before Fast Retransmit was entered. However, when there) s
5 566 M
( were multiple packet drops, then the acknowledgement for the) s
5 555 M
( retransmitted packet will acknowledge some but not all of the packets) s
5 544 M
( transmitted before the Fast Retransmit. We call this acknowledgement) s
5 533 M
( a partial acknowledgment.) s
5 511 M
( Along with several other suggestions, [Hoe95] suggested that during) s
5 500 M
( Fast Recovery the TCP data sender responds to a partial) s
5 489 M
( acknowledgment by inferring that the next in-sequence packet has been) s
5 478 M
( lost, and retransmitting that packet. This document describes a) s
5 467 M
( modification to the Fast Recovery algorithm in RFC 2581 that) s
5 456 M
( incorporates a response to partial acknowledgements received during) s
5 445 M
( Fast Recovery. We call this modified Fast Recovery algorithm) s
5 434 M
( NewReno, because it is a slight but significant variation of the) s
5 423 M
( basic Reno algorithm in RFC 2581. This document does not discuss the) s
5 412 M
( other suggestions in [Hoe95] and [Hoe96], such as a change to the) s
5 401 M
( ssthresh parameter during Slow-Start, or the proposal to send a new) s
5 390 M
( packet for every two duplicate acknowledgements during Fast Recovery.) s
5 379 M
( The version of NewReno in this document also draws on other) s
5 368 M
( discussions of NewReno in the literature [LM97].) s
5 346 M
( We do not claim that the NewReno version of Fast Recovery described) s
5 335 M
( here is an optimal modification of Fast Recovery for responding to) s
5 324 M
( partial acknowledgements, for TCP connections that are unable to use) s
5 313 M
( SACK. Based on our experiences with the NewReno modification in the) s
5 302 M
( NS simulator [NS] and with numerous implementations of NewReno, we) s
5 291 M
( believe that this modification improves the performance of the Fast) s
5 280 M
( Retransmit and Fast Recovery algorithms in a wide variety of) s
5 269 M
( scenarios.) s
5 247 M
(2. Terminology and Definitions) s
5 225 M
( In this document, the key words "MUST", "MUST NOT", "REQUIRED",) s
5 214 M
( "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY",) s
5 203 M
( and "OPTIONAL" are to be interpreted as described in BCP 14, RFC 2119) s
5 192 M
( and indicate requirement levels for compliant TCP implementations) s
5 181 M
( implementing the NewReno Fast Retransmit and Fast Recovery algorithms) s
5 170 M
( described in this document.) s
5 148 M
( This document assumes that the reader is familiar with the terms) s
5 104 M
(Floyd et al. [Page 4]) s
_R
S
%%Page: (5) 5
%%BeginPageSetup
_S
24 24 translate
/pagenum 5 def
/fname (draft-ietf-tsvwg-newreno-01.txt) def
/fdir () def
/ftail (draft-ietf-tsvwg-newreno-01.txt) def
/user_header_p false def
%%EndPageSetup
5 698 M
(draft-ietf-tsvwg-newreno September 2003) s
5 665 M
( SENDER MAXIMUM SEGMENT SIZE \(SMSS\), CONGESTION WINDOW \(cwnd\), and) s
5 654 M
( FLIGHT SIZE \(FlightSize\) defined in [RFC2581]. FLIGHT SIZE is) s
5 643 M
( defined as in [RFC2581] as follows:) s
5 621 M
( FLIGHT SIZE:) s
5 610 M
( The amount of data that has been sent but not yet acknowledged.) s
5 588 M
(3. The Fast Retransmit and Fast Recovery Algorithms in NewReno) s
5 566 M
( The standard implementation of the Fast Retransmit and Fast Recovery) s
5 555 M
( algorithms is given in [RFC2581]. This section specifies the basic) s
5 544 M
( NewReno algorithm. Sections 4 through 6 describe some optional) s
5 533 M
( variants, and the motivations behind them, that an implementor may) s
5 522 M
( want to consider when tuning performance for certain network) s
5 511 M
( scenarios. Sections 7 and 8 provide some guidance to implementors) s
5 500 M
( based on experience with NewReno implementations.) s
5 478 M
( The NewReno modification concerns the Fast Recovery procedure that) s
5 467 M
( begins when three duplicate ACKs are received and ends when either a) s
5 456 M
( retransmission timeout occurs or an ACK arrives that acknowledges all) s
5 445 M
( of the data up to and including the data that was outstanding when) s
5 434 M
( the Fast Recovery procedure began.) s
5 412 M
( The NewReno algorithm specified in this document differs from the) s
5 401 M
( implementation in [RFC2581] in the introduction of the variable) s
5 390 M
( "recover" in step 1, in the response to a partial or new) s
5 379 M
( acknowledgement in step 5, and in modifications to step 1 and the) s
5 368 M
( addition of step 6 for avoiding multiple Fast Retransmits caused by) s
5 357 M
( the retransmission of packets already received by the receiver.) s
5 335 M
( The algorithm specified in this document uses a variable "recover",) s
5 324 M
( whose initial value is the initial send sequence number.) s
5 302 M
( 1\) Three duplicate ACKs:) s
5 291 M
( When the third duplicate ACK is received and the sender is not) s
5 280 M
( already in the Fast Recovery procedure, check to see if the) s
5 269 M
( Cumulative Acknowledgement field covers more than "recover".) s
5 258 M
( If so, go to Step 1A. Otherwise, go to Step 1B.) s
5 236 M
( 1A\) Invoking Fast Retransmit:) s
5 225 M
( If so, then set ssthresh to no more than the value given in) s
5 214 M
( equation 1 below. \(This is equation 3 from [RFC2581]\).) s
5 192 M
( ssthresh = max \(FlightSize / 2, 2*SMSS\) \(1\)) s
5 170 M
( In addition, record the highest sequence number transmitted in) s
5 159 M
( the variable "recover", and go to Step 2.) s
5 104 M
(Floyd et al. [Page 5]) s
_R
S
%%Page: (6) 6
%%BeginPageSetup
_S
24 24 translate
/pagenum 6 def
/fname (draft-ietf-tsvwg-newreno-01.txt) def
/fdir () def
/ftail (draft-ietf-tsvwg-newreno-01.txt) def
/user_header_p false def
%%EndPageSetup
5 698 M
(draft-ietf-tsvwg-newreno September 2003) s
5 665 M
( 1B\) Not invoking Fast Retransmit:) s
5 654 M
( Do not enter the Fast Retransmit and Fast Recovery procedure.) s
5 643 M
( In particular, do not change ssthresh, do not go to Step 2 to) s
5 632 M
( retransmit the "lost" segment, and do not execute Step 3 upon) s
5 621 M
( subsequent duplicate ACKs.) s
5 599 M
( 2\) Entering Fast Retransmit:) s
5 588 M
( Retransmit the lost segment and set cwnd to ssthresh plus 3*SMSS.) s
5 577 M
( This artificially "inflates" the congestion window by the number) s
5 566 M
( of segments \(three\) that have left the network and which the) s
5 555 M
( receiver has buffered.) s
5 533 M
( 3\) Fast Recovery:) s
5 522 M
( For each additional duplicate ACK received while in Fast) s
5 511 M
( Recovery, increment cwnd by SMSS. This artificially inflates) s
5 500 M
( the congestion window in order to reflect the additional segment) s
5 489 M
( that has left the network.) s
5 467 M
( 4\) Fast Recovery, continued:) s
5 456 M
( Transmit a segment, if allowed by the new value of cwnd and the) s
5 445 M
( receiver's advertised window.) s
5 423 M
( 5\) When an ACK arrives that acknowledges new data, this ACK could be) s
5 412 M
( the acknowledgment elicited by the retransmission from step 2, or) s
5 401 M
( elicited by a later retransmission.) s
5 379 M
( Full acknowledgements:) s
5 368 M
( If this ACK acknowledges all of the data up to and including) s
5 357 M
( "recover", then the ACK acknowledges all the intermediate) s
5 346 M
( segments sent between the original transmission of the lost) s
5 335 M
( segment and the receipt of the third duplicate ACK. Set cwnd to) s
5 324 M
( either \(1\) min \(ssthresh, FlightSize + SMSS\); or \(2\) ssthresh,) s
5 313 M
( where ssthresh is the value set in step 1; this is termed) s
5 302 M
( "deflating" the window. \(We note that "FlightSize" in step 1) s
5 291 M
( referred to the amount of data outstanding in step 1, when Fast) s
5 280 M
( Recovery was entered, while "FlightSize" in step 5 refers to the) s
5 269 M
( amount of data outstanding in step 5, when Fast Recovery is) s
5 258 M
( exited.\) If the second option is selected, the implementation) s
5 247 M
( should take measures to avoid a possible burst of data, in case) s
5 236 M
( the amount of data outstanding in the network was much less than) s
5 225 M
( the new congestion window allows. A simple mechanism is to limit) s
5 214 M
( the number of data packets that can be sent in response to a) s
5 203 M
( single acknowledgement. \(This is known as "maxburst_" in the NS) s
5 192 M
( simulator\). Exit the Fast Recovery procedure.) s
5 170 M
( Partial acknowledgements:) s
5 159 M
( If this ACK does *not* acknowledge all of the data up to and) s
5 148 M
( including "recover", then this is a partial ACK. In this case,) s
5 104 M
(Floyd et al. [Page 6]) s
_R
S
%%Page: (7) 7
%%BeginPageSetup
_S
24 24 translate
/pagenum 7 def
/fname (draft-ietf-tsvwg-newreno-01.txt) def
/fdir () def
/ftail (draft-ietf-tsvwg-newreno-01.txt) def
/user_header_p false def
%%EndPageSetup
5 698 M
(draft-ietf-tsvwg-newreno September 2003) s
5 665 M
( retransmit the first unacknowledged segment. Deflate the) s
5 654 M
( congestion window by the amount of new data acknowledged, then) s
5 643 M
( add back one SMSS \(if the partial ACK acknowledges at least one) s
5 632 M
( SMSS of new data\) and send a new segment if permitted by the new) s
5 621 M
( value of cwnd. This "partial window deflation" attempts to) s
5 610 M
( ensure that, when Fast Recovery eventually ends, approximately) s
5 599 M
( ssthresh amount of data will be outstanding in the network. Do) s
5 588 M
( not exit the Fast Recovery procedure \(i.e., if any duplicate ACKs) s
5 577 M
( subsequently arrive, execute Steps 3 and 4 above\).) s
5 555 M
( For the first partial ACK that arrives during Fast Recovery, also) s
5 544 M
( reset the retransmit timer.) s
5 522 M
( 6\) Retransmit timeouts:) s
5 511 M
( After a retransmit timeout, record the highest sequence number) s
5 500 M
( transmitted in the variable "recover" and exit the Fast) s
5 489 M
( Recovery procedure if applicable.) s
5 467 M
( Step 1 specifies a check that the Cumulative Acknowledgement field) s
5 456 M
( covers more than "recover". Because the acknowledgement field) s
5 445 M
( contains the sequence number that the sender next expects to receive,) s
5 434 M
( the acknowledgement "ack_number" covers more than "recover" when:) s
5 412 M
( ack_number - one > recover.) s
5 390 M
( Note that in Step 5, the congestion window is deflated after a) s
5 379 M
( partial acknowledgement is received. The congestion window was) s
5 368 M
( likely to have been inflated considerably when the partial) s
5 357 M
( acknowledgement was received. In addition, depending on the original) s
5 346 M
( pattern of packet losses, the partial acknowledgement might) s
5 335 M
( acknowledge nearly a window of data. In this case, if the congestion) s
5 324 M
( window was not deflated, the data sender might be able to send nearly) s
5 313 M
( a window of data back-to-back.) s
5 291 M
( This document does not specify the sender's response to duplicate) s
5 280 M
( ACKs when the Fast Retransmit/Fast Recovery algorithm is not invoked.) s
5 269 M
( This is addressed in other documents, such as those describing the) s
5 258 M
( Limited Transmit procedure [RFC3042]. This document also does not) s
5 247 M
( address issues of adjusting the duplicate acknowledgement threshold,) s
5 236 M
( but assumes the threshold of three duplicate acknowledgements) s
5 225 M
( currently specified in RFC 2581.) s
5 203 M
( As a final note, we would observe that in the absence of the SACK) s
5 192 M
( option, the data sender is working from limited information. When) s
5 181 M
( the issue of recovery from multiple dropped packets from a single) s
5 170 M
( window of data is of particular importance, the best alternative) s
5 159 M
( would be to use the SACK option.) s
5 104 M
(Floyd et al. [Page 7]) s
_R
S
%%Page: (8) 8
%%BeginPageSetup
_S
24 24 translate
/pagenum 8 def
/fname (draft-ietf-tsvwg-newreno-01.txt) def
/fdir () def
/ftail (draft-ietf-tsvwg-newreno-01.txt) def
/user_header_p false def
%%EndPageSetup
5 698 M
(draft-ietf-tsvwg-newreno September 2003) s
5 665 M
(4. Resetting the Retransmit Timer in Response to Partial) s
5 654 M
(Acknowledgements.) s
5 632 M
( One possible variant to the response to partial acknowledgements) s
5 621 M
( specified in Section 3 concerns when to reset the retransmit timer) s
5 610 M
( after a partial acknowledgement. The algorithm in Section 3, Step 5,) s
5 599 M
( resets the retransmit timer only after the first partial ACK. In) s
5 588 M
( this case, if a large number of packets were dropped from a window of) s
5 577 M
( data, the TCP data sender's retransmit timer will ultimately expire,) s
5 566 M
( and the TCP data sender will invoke Slow-Start. \(This is illustrated) s
5 555 M
( on page 12 of [F98].\) We call this the Impatient variant of NewReno.) s
5 544 M
( We note that the Impatient variant in Section 3 doesn't follow the) s
5 533 M
( recommended algorithm in RFC 2988 of restarting the retransmit timer) s
5 522 M
( after every packet transmission or retransmission [RFC2988, Step) s
5 511 M
( 5.1].) s
5 489 M
( In contrast, the NewReno simulations in [FF96] illustrate the) s
5 478 M
( algorithm described above with the modification that the retransmit) s
5 467 M
( timer is reset after each partial acknowledgement. We call this the) s
5 456 M
( Slow-but-Steady variant of NewReno. In this case, for a window with) s
5 445 M
( a large number of packet drops, the TCP data sender retransmits at) s
5 434 M
( most one packet per roundtrip time. \(This behavior is illustrated in) s
5 423 M
( the New-Reno TCP simulation of Figure 5 in [FF96], and on page 11 of) s
5 412 M
( [F98].) s
5 390 M
( When N packets have been dropped from a window of data for a large) s
5 379 M
( value of N, the Slow-but-Steady variant can remain in Fast Recovery) s
5 368 M
( for N round-trip times, retransmitting one more dropped packet each) s
5 357 M
( round-trip time; for these scenarios, the Impatient variant gives a) s
5 346 M
( faster recovery and better performance. The tests "ns test-suite-) s
5 335 M
( newreno.tcl impatient1" and "ns test-suite-newreno.tcl slow1" in the) s
5 324 M
( NS simulator illustrate such a scenario, where the Impatient variant) s
5 313 M
( performs better than the Slow-but-Steady variant. The Impatient) s
5 302 M
( variant can be particularly important for TCP connections with large) s
5 291 M
( congestion windows, as illustrated by the tests "ns test-suite-) s
5 280 M
( newreno.tcl impatient4" and "ns test-suite-newreno.tcl slow4" in the) s
5 269 M
( NS simulator.) s
5 247 M
( One can also construct scenarios where the Slow-but-Steady variant) s
5 236 M
( gives better performance than the Impatient variant. As an example,) s
5 225 M
( this occurs then only a small number of packets are dropped, the RTO) s
5 214 M
( is sufficiently small that the retransmit timer expires, and) s
5 203 M
( performance would have been better without a retransmit timeout. The) s
5 192 M
( tests "ns test-suite-newreno.tcl impatient2" and "ns test-suite-) s
5 181 M
( newreno.tcl slow2" in the NS simulator illustrate such a scenario.) s
5 159 M
( The Slow-but-Steady variant can also achieve higher goodput than the) s
5 148 M
( Impatient variant, by avoiding unnecessary retransmissions. This) s
5 104 M
(Floyd et al. [Page 8]) s
_R
S
%%Page: (9) 9
%%BeginPageSetup
_S
24 24 translate
/pagenum 9 def
/fname (draft-ietf-tsvwg-newreno-01.txt) def
/fdir () def
/ftail (draft-ietf-tsvwg-newreno-01.txt) def
/user_header_p false def
%%EndPageSetup
5 698 M
(draft-ietf-tsvwg-newreno September 2003) s
5 665 M
( could be of special interest for cellular links, where every) s
5 654 M
( transmission costs battery power and money. The tests "ns test-) s
5 643 M
( suite-newreno.tcl impatient3" and "ns test-suite-newreno.tcl slow3") s
5 632 M
( in the NS simulator illustrate such a scenario. The Slow-but-Steady) s
5 621 M
( variant can also be more robust to delay variation in the network,) s
5 610 M
( where a delay spike might force the Impatient variant into a timeout) s
5 599 M
( and go-back-N recovery.) s
5 577 M
( Neither of the two variants discussed above are optimal. Our) s
5 566 M
( recommendation is for the Impatient variant, as specified in Section) s
5 555 M
( 3 of this document, because of the poor performance of the Slow-but-) s
5 544 M
( Steady variant for TCP connections with large congestion windows.) s
5 522 M
( One possibility for a more optimal algorithm would be one that) s
5 511 M
( recovered from multiple packet drops as quickly as does slow-start,) s
5 500 M
( while resetting the retransmit timers after each partial) s
5 489 M
( acknowledgement, as described in the section below. We note,) s
5 478 M
( however, that there is a limitation to the potential performance in) s
5 467 M
( this case in the absence of the SACK option.) s
5 445 M
(5. Retransmissions after a Partial Acknowledgement) s
5 423 M
( One possible variant to the response to partial acknowledgements) s
5 412 M
( specified in Section 3 would be to retransmit more than one packet) s
5 401 M
( after each partial acknowledgement, and to reset the retransmit timer) s
5 390 M
( after each retransmission. The algorithm specified in Section 3) s
5 379 M
( retransmits a single packet after each partial acknowledgement. This) s
5 368 M
( is the most conservative alternative, in that it is the least likely) s
5 357 M
( to result in an unnecessarily-retransmitted packet. A variant that) s
5 346 M
( would recover faster from a window with many packet drops would be to) s
5 335 M
( effectively Slow-Start, retransmitting two packets after each partial) s
5 324 M
( acknowledgement. Such an approach would take less than N roundtrip) s
5 313 M
( times to recover from N losses [Hoe96]. However, in the absence of) s
5 302 M
( SACK, recovering as quickly as slow-start introduces the likelihood) s
5 291 M
( of unnecessarily retransmitting packets, and this could significantly) s
5 280 M
( complicate the recovery mechanisms.) s
5 258 M
( We note that the response to partial acknowledgements specified in) s
5 247 M
( Section 3 of this document and in RFC 2582 differs from the response) s
5 236 M
( in [FF96], even though both approaches only retransmit one packet in) s
5 225 M
( response to a partial acknowledgement. Step 5 of Section 3 specifies) s
5 214 M
( that the TCP sender responds to a partial ACK by deflating the) s
5 203 M
( congestion window by the amount of new data acknowledged, then adding) s
5 192 M
( back one SMSS if the partial ACK acknowledges at least one SMSS of) s
5 181 M
( new data, and sending a new segment if permitted by the new value of) s
5 170 M
( cwnd. Thus, only one previously-sent packet is retransmitted in) s
5 159 M
( response to each partial acknowledgement, but additional new packets) s
5 148 M
( might be transmitted as well, depending on the amount of new data) s
5 104 M
(Floyd et al. [Page 9]) s
_R
S
%%Page: (10) 10
%%BeginPageSetup
_S
24 24 translate
/pagenum 10 def
/fname (draft-ietf-tsvwg-newreno-01.txt) def
/fdir () def
/ftail (draft-ietf-tsvwg-newreno-01.txt) def
/user_header_p false def
%%EndPageSetup
5 698 M
(draft-ietf-tsvwg-newreno September 2003) s
5 665 M
( acknowledged by the partial acknowledgement. In contrast, the) s
5 654 M
( variant of NewReno illustrated in [FF96] simply set the congestion) s
5 643 M
( window to ssthresh when a partial acknowledgement was received. The) s
5 632 M
( approach in [FF96] is more conservative, and does not attempt to) s
5 621 M
( accurately track the actual number of outstanding packets after a) s
5 610 M
( partial acknowledgement is received. While either of these) s
5 599 M
( approaches gives acceptable performance, the variant specified in) s
5 588 M
( Section 3 recovers more smoothly when multiple packets are dropped) s
5 577 M
( from a window of data. \(The [FF96] behavior can be seen in the NS) s
5 566 M
( simulator by setting the variable "partial_window_deflation_" for) s
5 555 M
( "Agent/TCP/Newreno" to 0, and the behavior specified in Section 3 is) s
5 544 M
( achieved by setting "partial_window_deflation_" to 1.\)) s
5 522 M
(6. Avoiding Multiple Fast Retransmits) s
5 500 M
( This section describes the motivation for the sender's state variable) s
5 489 M
( "recover", and discusses possible heuristics for distinguishing) s
5 478 M
( between a retransmitted packet that was dropped, and three duplicate) s
5 467 M
( acknowledgements simply from the unnecessary retransmission of three) s
5 456 M
( packets.) s
5 434 M
( In the absence of the SACK option or timestamps, a duplicate) s
5 423 M
( acknowledgement carries no information to identify the data packet or) s
5 412 M
( packets at the TCP data receiver that triggered that duplicate) s
5 401 M
( acknowledgement. In this case, the TCP data sender is unable to) s
5 390 M
( distinguish between a duplicate acknowledgement that results from a) s
5 379 M
( lost or delayed data packet, and a duplicate acknowledgement that) s
5 368 M
( results from the sender's unnecessary retransmission of a data packet) s
5 357 M
( that had already been received at the TCP data receiver. Because of) s
5 346 M
( this, with the Retransmit and Fast Recovery algorithms in Reno TCP,) s
5 335 M
( multiple segment losses from a single window of data can sometimes) s
5 324 M
( result in unnecessary multiple Fast Retransmits \(and multiple) s
5 313 M
( reductions of the congestion window\) [F94].) s
5 291 M
( With the Fast Retransmit and Fast Recovery algorithms in Reno TCP,) s
5 280 M
( the performance problems caused by multiple Fast Retransmits are) s
5 269 M
( relatively minor compared to the potential problems with Tahoe TCP,) s
5 258 M
( which does not implement Fast Recovery. Nevertheless, unnecessary) s
5 247 M
( Fast Retransmits can occur with Reno TCP unless some explicit) s
5 236 M
( mechanism is added to avoid this, such as the use of the "recover") s
5 225 M
( variable. \(This modification is called "bugfix" in [F98], and is) s
5 214 M
( illustrated on pages 7 and 9 of that document. Unnecessary Fast) s
5 203 M
( Retransmits for Reno without "bugfix" is illustrated on page 6 of) s
5 192 M
( [F98].\)) s
5 170 M
( Section 3 of RFC 2582 defined a default variant of NewReno TCP that) s
5 159 M
( did not use the variable "recover", and did not check if duplicate) s
5 148 M
( ACKs cover the variable "recover" before invoking Fast Retransmit.) s
5 104 M
(Floyd et al. [Page 10]) s
_R
S
%%Page: (11) 11
%%BeginPageSetup
_S
24 24 translate
/pagenum 11 def
/fname (draft-ietf-tsvwg-newreno-01.txt) def
/fdir () def
/ftail (draft-ietf-tsvwg-newreno-01.txt) def
/user_header_p false def
%%EndPageSetup
5 698 M
(draft-ietf-tsvwg-newreno September 2003) s
5 665 M
( With this default variant from RFC 2582, the problem of multiple Fast) s
5 654 M
( Retransmits from a single window of data can occur after a Retransmit) s
5 643 M
( Timeout \(as in page 8 of [F98]\) or in scenarios with reordering \(as) s
5 632 M
( in the validation test "./test-all-newreno newreno5_noBF" in) s
5 621 M
( directory "tcl/test" of the NS simulator. This gives performance) s
5 610 M
( similar to that on page 8 of [F03].\) RFC 2582 also defined Careful) s
5 599 M
( and Less Careful variants of the NewReno algorithm, and recommended) s
5 588 M
( the Careful variant.) s
5 566 M
( The algorithm specified in Section 3 of this document corresponds to) s
5 555 M
( the Careful variant of NewReno TCP from RFC 2582, and eliminates the) s
5 544 M
( problem of multiple Fast Retransmits. This algorithm uses the) s
5 533 M
( variable "recover", whose initial value is the initial send sequence) s
5 522 M
( number. After each retransmit timeout, the highest sequence number) s
5 511 M
( transmitted so far is recorded in the variable "recover".) s
5 489 M
( If, after a retransmit timeout, the TCP data sender retransmits three) s
5 478 M
( consecutive packets that have already been received by the data) s
5 467 M
( receiver, then the TCP data sender will receive three duplicate) s
5 456 M
( acknowledgements that do not cover more than "recover". In this) s
5 445 M
( case, the duplicate acknowledgements are not an indication of a new) s
5 434 M
( instance of congestion. They are simply an indication that the) s
5 423 M
( sender has unnecessarily retransmitted at least three packets.) s
5 401 M
( However, when a retransmitted packet is itself dropped, the sender) s
5 390 M
( can also receive three duplicate acknowledgements that do not cover) s
5 379 M
( more than "recover", and in this case the sender would have been) s
5 368 M
( better off if it had initiated Fast Retransmit. For a TCP that) s
5 357 M
( implements the algorithm specified in Section 3 of this document, the) s
5 346 M
( sender does not infer a packet drop from duplicate acknowledgements) s
5 335 M
( in this scenario. As always, the retransmit timer is the backup) s
5 324 M
( mechanism for inferring packet loss in this case.) s
5 302 M
( There are several heuristics, based on timestamps or on the amount of) s
5 291 M
( advancement of the cumulative acknowledgement field, that allow the) s
5 280 M
( sender to distinguish in some cases between three duplicate) s
5 269 M
( acknowledgements following a retransmitted packet that was dropped,) s
5 258 M
( and three duplicate acknowledgements simply from the unnecessary) s
5 247 M
( retransmission of three packets [Gur03]. The TCP sender MAY use such) s
5 236 M
( a heuristic to decide to invoke a Fast Retransmit in some cases even) s
5 225 M
( when the three duplicate acknowledgements do not cover more than) s
5 214 M
( "recover".) s
5 192 M
( For example, when three duplicate acknowledgements are caused by the) s
5 181 M
( unnecessary retransmission of three packets, this is likely to be) s
5 170 M
( accompanied by the cumulative acknowledgement field advancing by at) s
5 159 M
( least four segments. Similarly, a heuristic based on timestamps uses) s
5 148 M
( the fact that when there is a hole in the sequence space, the) s
5 104 M
(Floyd et al. [Page 11]) s
_R
S
%%Page: (12) 12
%%BeginPageSetup
_S
24 24 translate
/pagenum 12 def
/fname (draft-ietf-tsvwg-newreno-01.txt) def
/fdir () def
/ftail (draft-ietf-tsvwg-newreno-01.txt) def
/user_header_p false def
%%EndPageSetup
5 698 M
(draft-ietf-tsvwg-newreno September 2003) s
5 665 M
( timestamp echoed in the duplicate acknowledgement is the timestamp of) s
5 654 M
( the most recent data packet that advanced the cumulative) s
5 643 M
( acknowledgement field [RFC1323]. If timestamps are used, and the) s
5 632 M
( sender stores the timestamp of the last acknowledged segment, then) s
5 621 M
( the timestamp echoed by duplicate acknowledgements can be used to) s
5 610 M
( distinguish between a retransmitted packet that was dropped, and) s
5 599 M
( three duplicate acknowledgements simply from the unnecessary) s
5 588 M
( retransmission of three packets. The heuristics are illustrated in) s
5 577 M
( the NS simulator in the validation test "./test-all-newreno".) s
5 555 M
(6.1. ACK Heuristic.) s
5 533 M
( If the ACK-based heuristic is used, then following the advancement of) s
5 522 M
( the cumulative acknowledgement field, the sender stores the value of) s
5 511 M
( previous cumulative acknowledgement as prev_highest_ack and stores) s
5 500 M
( the latest cumulative ACK as highest_ack. In addition, the following) s
5 489 M
( step is performed if Step 1 in Section 3 fails, before proceeding to) s
5 478 M
( Step 1B.) s
5 456 M
( 1*\) If the Cumulative Acknowledgement field didn't cover more than) s
5 445 M
( "recover", check to see if the congestion window is greater) s
5 434 M
( than one SMSS and the difference between highest_ack and) s
5 423 M
( prev_highest_ack is at most four SMSS. If true, duplicate) s
5 412 M
( ACKs indicate a lost segment \(proceed to Step 1A in Section) s
5 401 M
( 3\). Otherwise, duplicate ACKs likely result from unnecessary) s
5 390 M
( retransmissions \(proceed to Step 1B in Section 3\).) s
5 368 M
( The congestion window check serves to protect against fast retransmit) s
5 357 M
( immediately after a retransmit timeout, similar to the) s
5 346 M
( "exitFastRetrans_" variable in NS. Examples of applying the ACK) s
5 335 M
( heuristic are in validation tests "./test-all-newreno) s
5 324 M
( newreno_rto_loss_ack" and "./test-all-newreno newreno_rto_dup_ack" in) s
5 313 M
( directory "tcl/test" of the NS simulator.) s
5 291 M
( If several ACKs are lost, the sender can see a jump in the cumulative) s
5 280 M
( ACK of more than three segments and the heuristic can fail. A) s
5 269 M
( validation test for this scenario is "./test-all-newreno) s
5 258 M
( newreno_rto_loss_ackf". The ACK heuristic is more likely to fail if) s
5 247 M
( the receiver uses delayed ACKs, because then a smaller number of ACK) s
5 236 M
( losses are needed to produce a sufficient jump in the cumulative ACK.) s
5 214 M
(6.2. Timestamp Heuristic.) s
5 192 M
( If this heuristic is used, the sender stores the timestamp of the) s
5 181 M
( last acknowledged segment. In addition, the second paragraph of step) s
5 170 M
( 1 in Section 3 is replaced as follows:) s
5 148 M
( 1**\) If the Cumulative Acknowledgement field didn't cover more than) s
5 104 M
(Floyd et al. [Page 12]) s
_R
S
%%Page: (13) 13
%%BeginPageSetup
_S
24 24 translate
/pagenum 13 def
/fname (draft-ietf-tsvwg-newreno-01.txt) def
/fdir () def
/ftail (draft-ietf-tsvwg-newreno-01.txt) def
/user_header_p false def
%%EndPageSetup
5 698 M
(draft-ietf-tsvwg-newreno September 2003) s
5 665 M
( "recover", check to see if the echoed timestamp equals the) s
5 654 M
( stored timestamp. If true, duplicate ACKs indicate a lost) s
5 643 M
( segment \(proceed to Step 1A in Section 3\). Otherwise, duplicate) s
5 632 M
( ACKs likely result from unnecessary retransmissions \(proceed) s
5 621 M
( to Step 1B in Section 3\).) s
5 599 M
( Examples of applying the timestamp heuristic are in validation tests) s
5 588 M
( "./test-all-newreno newreno_rto_loss_tsh" and "./test-all-newreno) s
5 577 M
( newreno_rto_dup_tsh". The timestamp heuristic works correctly both) s
5 566 M
( when the receiver echoes timestamps as specified by [RFC1323] or by) s
5 555 M
( its revision attempts. However, if the receiver arbitrarily echos) s
5 544 M
( timestamps, the heuristic can fail. The heuristic can also fail if a) s
5 533 M
( timeout was spurious and returning ACKs are not from retransmitted) s
5 522 M
( segments. This can be prevented by detection algorithms such as) s
5 511 M
( [RFC3522].) s
5 489 M
(7. Implementation Issues for the Data Receiver) s
5 467 M
( [RFC2581] specifies that "Out-of-order data segments SHOULD be) s
5 456 M
( acknowledged immediately, in order to accelerate loss recovery.") s
5 445 M
( Neal Cardwell has noted that some data receivers do not send an) s
5 434 M
( immediate acknowledgement when they send a partial acknowledgment,) s
5 423 M
( but instead wait first for their delayed acknowledgement timer to) s
5 412 M
( expire [C98]. As [C98] notes, this severely limits the potential) s
5 401 M
( benefit from NewReno by delaying the receipt of the partial) s
5 390 M
( acknowledgement at the data sender. Our recommendation is that the) s
5 379 M
( data receiver send an immediate acknowledgement for an out-of-order) s
5 368 M
( segment, even when that out-of-order segment fills a hole in the) s
5 357 M
( buffer.) s
5 335 M
(8. Implementation Issues for the Data Sender) s
5 313 M
( In Section 3, Step 5 above, it is noted that implementations should) s
5 302 M
( take measures to avoid a possible burst of data when leaving Fast) s
5 291 M
( Recovery, in case the amount of new data that the sender is eligible) s
5 280 M
( to send due to the new value of the congestion window is large. This) s
5 269 M
( can arise during NewReno when ACKs are lost or treated as pure window) s
5 258 M
( updates, thereby causing the sender to underestimate the number of) s
5 247 M
( new segments that can be sent during the recovery procedure.) s
5 236 M
( Specifically, bursts can occur when the FlightSize is much less than) s
5 225 M
( the new congestion window when exiting from Fast Recovery. One) s
5 214 M
( simple mechanism to avoid a burst of data when leaving Fast Recovery) s
5 203 M
( is to limit the number of data packets that can be sent in response) s
5 192 M
( to a single acknowledgment. \(This is known as "maxburst_" in the ns) s
5 181 M
( simulator.\) Other possible mechanisms for avoiding bursts include) s
5 170 M
( rate-based pacing, or setting the slow-start threshold to the) s
5 159 M
( resultant congestion window and then resetting the congestion window) s
5 148 M
( to FlightSize. A recommendation on the general mechanism to avoid) s
5 104 M
(Floyd et al. [Page 13]) s
_R
S
%%Page: (14) 14
%%BeginPageSetup
_S
24 24 translate
/pagenum 14 def
/fname (draft-ietf-tsvwg-newreno-01.txt) def
/fdir () def
/ftail (draft-ietf-tsvwg-newreno-01.txt) def
/user_header_p false def
%%EndPageSetup
5 698 M
(draft-ietf-tsvwg-newreno September 2003) s
5 665 M
( excessively bursty sending patterns is outside the scope of this) s
5 654 M
( document.) s
5 632 M
( An implementation may want to use a separate flag to record whether) s
5 621 M
( or not it is presently in the Fast Recovery procedure. The use of) s
5 610 M
( the value of the duplicate acknowledgment counter as such a flag is) s
5 599 M
( not reliable because it can be reset upon window updates and out-of-) s
5 588 M
( order acknowledgments.) s
5 566 M
( When not in Fast Recovery, the value of the state variable "recover") s
5 555 M
( should be pulled along with the value of the state variable for) s
5 544 M
( acknowledgments \(typically, "snd_una"\) so that, when large amounts of) s
5 533 M
( data has been sent and acked, the sequence space does not wrap and) s
5 522 M
( falsely indicate that Fast Recovery should not be entered \(Section 3,) s
5 511 M
( step 1, last paragraph\).) s
5 489 M
( It is important for the sender to respond correctly to duplicate ACKs) s
5 478 M
( received when the sender is no longer in Fast Recovery \(e.g., because) s
5 467 M
( of a Retransmit Timeout\). The Limited Transmit procedure [RFC3042]) s
5 456 M
( describes possible responses to the first and second duplicate) s
5 445 M
( acknowledgements. When three or more duplicate acknowledgements are) s
5 434 M
( received, the Cumulative Acknowledgement field doesn't cover more) s
5 423 M
( than "recover", and a new Fast Recovery is not invoked, it is) s
5 412 M
( important that the sender not execute the Fast Recovery steps \(3\) and) s
5 401 M
( \(4\) in Section 3. Otherwise, the sender could end up in a chain of) s
5 390 M
( spurious timeouts. We mention this only because several NewReno) s
5 379 M
( implementations had this bug, including the implementation in the NS) s
5 368 M
( simulator. \(This bug in the NS simulator was fixed in July 2003,) s
5 357 M
( with the variable "exitFastRetrans_".\)) s
5 335 M
(9. Simulations) s
5 313 M
( Simulations with NewReno are illustrated with the validation test) s
5 302 M
( "tcl/test/test-all-newreno" in the NS simulator. The command) s
5 291 M
( "../../ns test-suite-newreno.tcl reno" shows a simulation with Reno) s
5 280 M
( TCP, illustrating the data sender's lack of response to a partial) s
5 269 M
( acknowledgement. In contrast, the command "../../ns test-suite-) s
5 258 M
( newreno.tcl newreno_B" shows a simulation with the same scenario) s
5 247 M
( using the NewReno algorithms described in this paper.) s
5 225 M
(10. Comparisons between Reno and NewReno TCP) s
5 203 M
( As we stated in the introduction, we believe that the NewReno) s
5 192 M
( modification described in this document improves the performance of) s
5 181 M
( the Fast Retransmit and Fast Recovery algorithms of Reno TCP in a) s
5 170 M
( wide variety of scenarios. This has been discussed in some depth in) s
5 159 M
( [FF96], which illustrates Reno TCP's poor performance when multiple) s
5 148 M
( packets are dropped from a window of data and also illustrates) s
5 104 M
(Floyd et al. [Page 14]) s
_R
S
%%Page: (15) 15
%%BeginPageSetup
_S
24 24 translate
/pagenum 15 def
/fname (draft-ietf-tsvwg-newreno-01.txt) def
/fdir () def
/ftail (draft-ietf-tsvwg-newreno-01.txt) def
/user_header_p false def
%%EndPageSetup
5 698 M
(draft-ietf-tsvwg-newreno September 2003) s
5 665 M
( NewReno TCP's good performance in that scenario.) s
5 643 M
( We do, however, know of one scenario where Reno TCP gives better) s
5 632 M
( performance than NewReno TCP, that we describe here for the sake of) s
5 621 M
( completeness. Consider a scenario with no packet loss, but with) s
5 610 M
( sufficient reordering that the TCP sender receives three duplicate) s
5 599 M
( acknowledgements. This will trigger the Fast Retransmit and Fast) s
5 588 M
( Recovery algorithms. With Reno TCP or with Sack TCP, this will) s
5 577 M
( result in the unnecessary retransmission of a single packet, combined) s
5 566 M
( with a halving of the congestion window \(shown on pages 4 and 6 of) s
5 555 M
( [F03]\). With NewReno TCP, however, this reordering will also result) s
5 544 M
( in the unnecessary retransmission of an entire window of data \(shown) s
5 533 M
( on page 5 of [F03]\).) s
5 511 M
( While Reno TCP performs better than NewReno TCP in the presence of) s
5 500 M
( reordering, NewReno's superior performance in the presence of) s
5 489 M
( multiple packet drops generally outweighs its less optimal) s
5 478 M
( performance in the presence of reordering. \(Sack TCP is the) s
5 467 M
( preferred solution, with good performance in both scenarios.\) This) s
5 456 M
( document recommends the Fast Retransmit and Fast Recovery algorithms) s
5 445 M
( of NewReno TCP instead of those of Reno TCP for those TCP connections) s
5 434 M
( that do not support SACK. We would also note that NewReno's Fast) s
5 423 M
( Retransmit and Fast Recovery mechanisms are widely deployed in TCP) s
5 412 M
( implementations in the Internet today, as documented in [PF01]. For) s
5 401 M
( example, tests of TCP implementations in several thousand web servers) s
5 390 M
( in 2001 showed that for those TCP connections where the web browser) s
5 379 M
( was not SACK-capable, more web servers used the Fast Retransmit and) s
5 368 M
( Fast Recovery algorithms of NewReno than those of Reno or Tahoe TCP) s
5 357 M
( [PF01].) s
5 335 M
(11. Changes Relative to RFC 2582) s
5 313 M
( The purpose of this document is to advance the NewReno's Fast) s
5 302 M
( Retransmit and Fast Recovery algorithms in RFC 2582 to Proposed) s
5 291 M
( Standard.) s
5 269 M
( The main change in this document relative to RFC 2582 is to specify) s
5 258 M
( the Careful variant of NewReno's Fast Retransmit and Fast Recovery) s
5 247 M
( algorithms. The base algorithm described in RFC 2582 did not attempt) s
5 236 M
( to avoid unnecessary multiple Fast Retransmits that can occur after a) s
5 225 M
( timeout \(described in more detail in the section above\). However,) s
5 214 M
( RFC 2582 also defined "Careful" and "Less Careful" variants that) s
5 203 M
( avoid these unnecessary Fast Retransmits, and recommended the Careful) s
5 192 M
( variant. This document specifies the previously-named "Careful") s
5 181 M
( variant as the basic version of NewReno. As described below, this) s
5 170 M
( algorithm uses a variable "recover", whose initial value is the send) s
5 159 M
( sequence number.) s
5 104 M
(Floyd et al. [Page 15]) s
_R
S
%%Page: (16) 16
%%BeginPageSetup
_S
24 24 translate
/pagenum 16 def
/fname (draft-ietf-tsvwg-newreno-01.txt) def
/fdir () def
/ftail (draft-ietf-tsvwg-newreno-01.txt) def
/user_header_p false def
%%EndPageSetup
5 698 M
(draft-ietf-tsvwg-newreno September 2003) s
5 665 M
( The algorithm specified in Section 3 checks whether the) s
5 654 M
( acknowledgement field of a partial acknowledgement covers *more* than) s
5 643 M
( "recover". Another possible variant would be to require simply that) s
5 632 M
( the acknowledgement field *cover* "recover" before initiating another) s
5 621 M
( Fast Retransmit. We called this the Less Careful variant in RFC) s
5 610 M
( 2582.) s
5 588 M
( There are two separate scenarios in which the TCP sender could) s
5 577 M
( receive three duplicate acknowledgements acknowledging "recover" but) s
5 566 M
( no more than "recover". One scenario would be that the data sender) s
5 555 M
( transmitted four packets with sequence numbers higher than "recover",) s
5 544 M
( that the first packet was dropped in the network, and the following) s
5 533 M
( three packets triggered three duplicate acknowledgements) s
5 522 M
( acknowledging "recover". The second scenario would be that the) s
5 511 M
( sender unnecessarily retransmitted three packets below "recover", and) s
5 500 M
( that these three packets triggered three duplicate acknowledgements) s
5 489 M
( acknowledging "recover". In the absence of SACK, the TCP sender in) s
5 478 M
( unable to distinguish between these two scenarios.) s
5 456 M
( For the Careful variant of Fast Retransmit, the data sender would) s
5 445 M
( have to wait for a retransmit timeout in the first scenario, but) s
5 434 M
( would not have an unnecessary Fast Retransmit in the second scenario.) s
5 423 M
( For the Less Careful variant to Fast Retransmit, the data sender) s
5 412 M
( would Fast Retransmit as desired in the first scenario, and would) s
5 401 M
( unnecessarily Fast Retransmit in the second scenario. This document) s
5 390 M
( only specifies the Careful variant in Section 3. Unnecessary Fast) s
5 379 M
( Retransmits with the Less Careful variant in scenarios with) s
5 368 M
( reordering are illustrated in page 8 of [F03].) s
5 346 M
( The document also specifies two heuristics that the TCP sender MAY) s
5 335 M
( use to decide to invoke Fast Retransmit even when the three duplicate) s
5 324 M
( acknowledgements do not cover more than "recover". These heuristics,) s
5 313 M
( an ACK-based heuristic and a timestamp heuristic, are described in) s
5 302 M
( Sections 6.1 and 6.2 respectively.) s
5 280 M
(12. Conclusions) s
5 258 M
( This document specifies the NewReno Fast Retransmit and Fast Recovery) s
5 247 M
( algorithms for TCP. This NewReno modification to TCP can be) s
5 236 M
( important even for TCP implementations that support the SACK option,) s
5 225 M
( because the SACK option can only be used for TCP connections when) s
5 214 M
( both TCP end-nodes support the SACK option. NewReno performs better) s
5 203 M
( than Reno \(RFC 2581\) in a number of scenarios discussed herein.) s
5 181 M
( A number of options to the basic algorithm presented in Section 3 are) s
5 170 M
( also described. These include the handling of the retransmission) s
5 159 M
( timer \(Section 4\), the response to partial acknowledgments \(Section) s
5 148 M
( 5\), and the value of the congestion window when leaving Fast Recovery) s
5 104 M
(Floyd et al. [Page 16]) s
_R
S
%%Page: (17) 17
%%BeginPageSetup
_S
24 24 translate
/pagenum 17 def
/fname (draft-ietf-tsvwg-newreno-01.txt) def
/fdir () def
/ftail (draft-ietf-tsvwg-newreno-01.txt) def
/user_header_p false def
%%EndPageSetup
5 698 M
(draft-ietf-tsvwg-newreno September 2003) s
5 665 M
( \(section 3, step 5\). Our belief is that the differences between) s
5 654 M
( these variants of NewReno are small compared to the differences) s
5 643 M
( between Reno and NewReno. That is, the important thing is to) s
5 632 M
( implement NewReno instead of Reno, for a TCP connection without SACK;) s
5 621 M
( it is less important exactly which of the variants of NewReno is) s
5 610 M
( implemented.) s
5 588 M
(13. Acknowledgements) s
5 566 M
( Many thanks to Anil Agarwal, Mark Allman, Armando Caro, Jeffrey Hsu,) s
5 555 M
( Vern Paxson, Kacheong Poon, Keyur Shah, and Bernie Volz for detailed) s
5 544 M
( feedback on this document or on its precursor RFC 2582.) s
5 104 M
(Floyd et al. [Page 17]) s
_R
S
%%Page: (18) 18
%%BeginPageSetup
_S
24 24 translate
/pagenum 18 def
/fname (draft-ietf-tsvwg-newreno-01.txt) def
/fdir () def
/ftail (draft-ietf-tsvwg-newreno-01.txt) def
/user_header_p false def
%%EndPageSetup
5 698 M
(draft-ietf-tsvwg-newreno September 2003) s
5 665 M
(14. References) s
5 643 M
( Normative References) s
5 621 M
( [RFC2018] M. Mathis, J. Mahdavi, S. Floyd, A. Romanow, "TCP Selective) s
5 610 M
( Acknowledgement Options", RFC 2018, October 1996.) s
5 588 M
( [RFC2581] W. Stevens, M. Allman, and V. Paxson, "TCP Congestion) s
5 577 M
( Control", RFC 2581, April 1999.) s
5 555 M
( [RFC2582] S. Floyd and T. Henderson, The NewReno Modification to) s
5 544 M
( TCP's Fast Recovery Algorithm, RFC 2582, April 1999.) s
5 522 M
( [RFC2988] V. Paxson and M. Allman, Computing TCP's Retransmission) s
5 511 M
( Timer, RFC 2988, November 2000.) s
5 489 M
( [RFC3042] M. Allman, H. Balakrishnan, and S. Floyd, Enhancing TCP's) s
5 478 M
( Loss Recovery Using Limited Transmit, RFC 3042, January 2001.) s
5 456 M
( Informative References) s
5 434 M
( [C98] N. Cardwell, "delayed ACKs for retransmitted packets: ouch!".) s
5 423 M
( November 1998, Email to the tcpimpl mailing list, Message-ID) s
5 412 M
( "Pine.LNX.4.02A.9811021421340.26785-100000@sake.cs.washington.edu",) s
5 401 M
( archived at "http://tcp-impl.lerc.nasa.gov/tcp-impl".) s
5 379 M
( [F98] S. Floyd, Revisions to RFC 2001, "Presentation to the TCPIMPL) s
5 368 M
( Working Group", August 1998. URLs "ftp://ftp.ee.lbl.gov/talks/sf-) s
5 357 M
( tcpimpl-aug98.ps" and "ftp://ftp.ee.lbl.gov/talks/sf-tcpimpl-) s
5 346 M
( aug98.pdf".) s
5 324 M
( [F03] S. Floyd, "Moving NewReno from Experimental to Proposed) s
5 313 M
( Standard? Presentation to the TSVWG Working Group", March 2003.) s
5 302 M
( URLs "http://www.icir.org/floyd/talks/newreno-Mar03.ps" and) s
5 291 M
( "http://www.icir.org/floyd/talks/newreno-Mar03.pdf".) s
5 269 M
( [FF96] K. Fall and S. Floyd, "Simulation-based Comparisons of Tahoe,) s
5 258 M
( Reno and SACK TCP", Computer Communication Review, July 1996. URL) s
5 247 M
( "ftp://ftp.ee.lbl.gov/papers/sacks.ps.Z".) s
5 225 M
( [F94] S. Floyd, "TCP and Successive Fast Retransmits", Technical) s
5 214 M
( report, October 1994. URL) s
5 203 M
( "ftp://ftp.ee.lbl.gov/papers/fastretrans.ps".) s
5 181 M
( [Gur03] A. Gurtov, "[Tsvwg] resolving the problem of unnecessary fast) s
5 170 M
( retransmits in go-back-N", email to the tsvwg mailing list, message) s
5 159 M
( ID <3F25B467.9020609@cs.helsinki.fi>, July 28, 2003. URL) s
5 148 M
( "http://www1.ietf.org/mail-archive/working-) s
5 104 M
(Floyd et al. [Page 18]) s
_R
S
%%Page: (19) 19
%%BeginPageSetup
_S
24 24 translate
/pagenum 19 def
/fname (draft-ietf-tsvwg-newreno-01.txt) def
/fdir () def
/ftail (draft-ietf-tsvwg-newreno-01.txt) def
/user_header_p false def
%%EndPageSetup
5 698 M
(draft-ietf-tsvwg-newreno September 2003) s
5 665 M
( groups/tsvwg/current/msg04334.html".) s
5 643 M
( [Hen98] T. Henderson, Re: NewReno and the 2001 Revision. September) s
5 632 M
( 1998. Email to the tcpimpl mailing list, Message ID) s
5 621 M
( "Pine.BSI.3.95.980923224136.26134A-100000@raptor.CS.Berkeley.EDU",) s
5 610 M
( archived at "http://tcp-impl.lerc.nasa.gov/tcp-impl".) s
5 588 M
( [Hoe95] J. Hoe, "Startup Dynamics of TCP's Congestion Control and) s
5 577 M
( Avoidance Schemes", Master's Thesis, MIT, 1995. URL "http://ana-) s
5 566 M
( www.lcs.mit.edu/anaweb/ps-papers/hoe-thesis.ps".) s
5 544 M
( [Hoe96] J. Hoe, "Improving the Start-up Behavior of a Congestion) s
5 533 M
( Control Scheme for TCP", ACM SIGCOMM, August 1996. URL) s
5 522 M
( "http://www.acm.org/sigcomm/sigcomm96/program.html".) s
5 500 M
( [LM97] D. Lin and R. Morris, "Dynamics of Random Early Detection",) s
5 489 M
( SIGCOMM 97, September 1997. URL) s
5 478 M
( "http://www.acm.org/sigcomm/sigcomm97/program.html".) s
5 456 M
( [NS] The Network Simulator \(NS\). URL "http://www.isi.edu/nsnam/ns/".) s
5 434 M
( [PF01] J. Padhye and S. Floyd, "Identifying the TCP Behavior of Web) s
5 423 M
( Servers", June 2001, SIGCOMM 2001.) s
5 401 M
( [RFC1323] V. Jacobson, R. Braden, and D. Borman, "TCP Extensions for) s
5 390 M
( High Performance,", RFC 1323, May 1992.) s
5 368 M
( [RFC3522] R. Ludwig and M. Meyer, The Eifel Detection Algorithm for) s
5 357 M
( TCP, RFC 3522, April 2003.) s
5 335 M
(15. Security Considerations) s
5 313 M
( RFC 2581 discusses general security considerations concerning TCP) s
5 302 M
( congestion control. This document describes a specific algorithm) s
5 291 M
( that conforms with the congestion control requirements of RFC 2581,) s
5 280 M
( and so those considerations apply to this algorithm, too. There are) s
5 269 M
( no known additional security concerns for this specific algorithm.) s
5 247 M
(AUTHORS' ADDRESSES) s
5 214 M
( Sally Floyd) s
5 203 M
( International Computer Science Institute) s
5 181 M
( Phone: +1 \(510\) 666-2989) s
5 170 M
( Email: floyd@acm.org) s
5 159 M
( URL: http://www.icir.org/floyd/) s
5 104 M
(Floyd et al. [Page 19]) s
_R
S
%%Page: (20) 20
%%BeginPageSetup
_S
24 24 translate
/pagenum 20 def
/fname (draft-ietf-tsvwg-newreno-01.txt) def
/fdir () def
/ftail (draft-ietf-tsvwg-newreno-01.txt) def
/user_header_p false def
%%EndPageSetup
5 698 M
(draft-ietf-tsvwg-newreno September 2003) s
5 665 M
( Tom Henderson) s
5 654 M
( The Boeing Company) s
5 632 M
( Email: thomas.r.henderson@boeing.com) s
5 610 M
( Andrei Gurtov) s
5 599 M
( U. Helsinki) s
5 577 M
( Email: gurtov@cs.helsinki.fi) s
5 104 M
(Floyd et al. [Page 20]) s
_R
S
%%Trailer
%%Pages: 20
%%DocumentNeededResources: font Courier-Bold Courier
%%EOF
| PAFTECH AB 2003-2026 | 2026-04-23 06:50:58 |