home *** CD-ROM | disk | FTP | other *** search
/ Internet Info 1997 December / Internet_Info_CD-ROM_Walnut_Creek_December_1997.iso / drafts / draft_ietf_q_t / draft-ietf-tcpimpl-prob-00.txt < prev    next >
Text File  |  1997-05-27  |  34KB  |  899 lines
  1.  
  2.  
  3.  
  4.  
  5. Network Working Group                                  V. Paxson, Editor
  6. Internet Draft
  7. Expiration Date: September 1997                               March 1997
  8.  
  9.  
  10.                    Known TCP Implementation Problems
  11.                     <draft-ietf-tcpimpl-prob-00.txt>
  12.  
  13.  
  14. 1. Status of this Memo
  15.  
  16.    This document is an Internet  Draft.   Internet  Drafts  are  working
  17.    documents  of  the Internet Engineering Task Force (IETF), its areas,
  18.    and its working groups.  Note that other groups may  also  distribute
  19.    working documents as Internet Drafts.
  20.  
  21.    Internet Drafts are draft  documents  valid  for  a  maximum  of  six
  22.    months, and may be updated, replaced, or obsoleted by other documents
  23.    at any time.  It is inappropriate to use Internet Drafts as reference
  24.    material or to cite them other than as ``work in progress''.
  25.  
  26.    To learn the current status of any Internet Draft, please  check  the
  27.    ``1id-abstracts.txt'' listing contained in the Internet Drafts shadow
  28.    directories  on  ftp.is.co.za   (Africa),   nic.nordu.net   (Europe),
  29.    munnari.oz.au  (Pacific  Rim),  ds.internic.net  (US  East Coast), or
  30.    ftp.isi.edu (US West Coast).
  31.  
  32.    This memo provides information for the Internet community.  This memo
  33.    does  not  specify an Internet standard of any kind.  Distribution of
  34.    this memo is unlimited.
  35.  
  36.  
  37. 2. Introduction
  38.  
  39.    This memo catalogs a number of  known  TCP  implementation  problems.
  40.    The  goal  in  doing  so  is  to  improve  conditions in the existing
  41.    Internet by enhancing the quality of current TCP/IP  implementations.
  42.    It  is  hoped  that  both  performance  and correctness issues can be
  43.    resolved by making implementors  aware  of  the  problems  and  their
  44.    solutions.   In  the  long term, it is hoped that this will provide a
  45.    reduction  in  unnecessary  traffic  on  the  network,  the  rate  of
  46.    connection  failures  due  to  protocol  errors,  and load on network
  47.    servers due to time spent processing  both  unsuccessful  connections
  48.    and  retransmitted  data.   This will help to ensure the stability of
  49.    the global Internet.
  50.  
  51.    Each problem is defined as follows:
  52.  
  53.  
  54.  
  55.  
  56. Paxson, Editor                                                  [Page 1]
  57.  
  58.  
  59.  
  60.  
  61.  
  62. ID                 Known TCP Implementation Problems          March 1997
  63.  
  64.  
  65.    Name The name associated with the problem.  In this memo, the name is
  66.         given as a subsection heading.
  67.  
  68.    Category
  69.         One or more problem categories for which the problem is  classi-
  70.         fied.   Categories  used  so far: "congestion control", "perfor-
  71.         mance", "reliability".  Others anticipated: "security", "intero-
  72.         perability", "configuration".
  73.  
  74.    Description
  75.         A definition of the problem, succinct  but  including  necessary
  76.         background material.
  77.  
  78.    Significance
  79.         A quanitification as to how serious the problem  is  considered.
  80.         Categories are "Non-critical", "Serious", and "Critical".
  81.  
  82.    Implications
  83.         Why the problem is viewed as a problem.
  84.  
  85.    Relevant RFCs
  86.         Brief discussion of the RFCs with respect to which  the  problem
  87.         is viewed as an implementation error.
  88.  
  89.    Trace file demonstrating the problem
  90.         One or more ASCII trace  files  demonstrating  the  problem,  if
  91.         applicable.   These  may  in the future be replaced with URLs to
  92.         on-line traces.
  93.  
  94.    Trace file demonstrating correct behavior
  95.         One or more examples of how correct behavior appears in a trace,
  96.         if applicable.  These may in the future be replaced with URLs to
  97.         on-line traces.
  98.  
  99.    References
  100.         References that further discuss the problem.
  101.  
  102.    How to detect
  103.         How to test an implementation to see if it exhibits the problem.
  104.         This  discussion may include difficulties and subtleties associ-
  105.         ated with causing the  problem  to  manifest  itself,  and  with
  106.         interpreting  traces  to  detect the presence of the problem (if
  107.         applicable).  In the future, this may include URLs for  diagnos-
  108.         tic tools.
  109.  
  110.    How to fix
  111.         For known causes of the problem, how to correct the  implementa-
  112.         tion.
  113.  
  114.  
  115.  
  116. Paxson, Editor                                                  [Page 2]
  117.  
  118.  
  119.  
  120.  
  121.  
  122. ID                 Known TCP Implementation Problems          March 1997
  123.  
  124.  
  125.    Implementation specifics
  126.         If it is viewed as beneficial to document particular implementa-
  127.         tions exhibiting the problem, and if the corresponding implemen-
  128.         tors approve, then this section gives  the  specifics  of  those
  129.         implementations,  along with a contact address for the implemen-
  130.         tors.
  131.  
  132.  
  133. 3. Known implementation problems
  134.  
  135.  
  136. 3.1. No initial slow start
  137.  
  138. Category
  139.      Congestion control
  140.  
  141. Description
  142.      When a TCP begins transmitting data, it is required  by  RFC  1122,
  143.      4.2.2.15,  to  engage in a "slow start" by initializing its conges-
  144.      tion window, cwnd, to one packet (one segment of the maximum size).
  145.      It  subsequently  increases  cwnd  by  one  packet  for each ack it
  146.      receives for new data.  The minimum  of  cwnd  and  the  receiver's
  147.      advertised  window  bounds  the highest sequence number the TCP can
  148.      transmit.  A TCP that fails to initialize  and  increment  cwnd  in
  149.      this fashion exhibits "No initial slow start".
  150.  
  151. Significance
  152.      Serious.
  153.  
  154. Implications
  155.      A TCP failing to slow start when beginning a connection results  in
  156.      traffic  bursts  that  can stress the network, leading to excessive
  157.      queueing delays and packet loss.
  158.  
  159.      Implementations exhibiting this problem might do  so  because  they
  160.      suffer  from  the  general  problem  of  not including the required
  161.      congestion window.  These implementations will also suffer from "No
  162.      slow start after retransmission timeout".
  163.  
  164.      There are different shades of "No initial slow  start".   From  the
  165.      perspective  of  stressing  the  network, the worst is a connection
  166.      that simply always sends based on the receiver's advertised window,
  167.      with  no  notion of a separate congestion window.  Some other forms
  168.      are described in "Uninitialized CWND" and "Initial CWND of 2  pack-
  169.      ets".
  170.  
  171.  
  172. Relevant RFCs' 5
  173.  
  174.  
  175.  
  176. Paxson, Editor                                                  [Page 3]
  177.  
  178.  
  179.  
  180.  
  181.  
  182. ID                 Known TCP Implementation Problems          March 1997
  183.  
  184.  
  185.      RFC 1122 requires use of slow start.  RFC 2001 gives the  specifics
  186.      of slow start.
  187.  
  188. Trace file demonstrating it
  189.      Made using tcpdump/BPF recording at the connection  responder.   No
  190.      losses reported.
  191.  
  192.      10:40:42.244503 B > A: S 1168512000:1168512000(0) win 32768
  193.                              <mss 1460,nop,wscale 0> (DF) [tos 0x8]
  194.      10:40:42.259908 A > B: S 3688169472:3688169472(0)
  195.                              ack 1168512001 win 32768 <mss 1460>
  196.      10:40:42.389992 B > A: . ack 1 win 33580 (DF) [tos 0x8]
  197.      10:40:42.664975 A > B: P 1:513(512) ack 1 win 32768
  198.      10:40:42.700185 A > B: . 513:1973(1460) ack 1 win 32768
  199.      10:40:42.718017 A > B: . 1973:3433(1460) ack 1 win 32768
  200.      10:40:42.762945 A > B: . 3433:4893(1460) ack 1 win 32768
  201.      10:40:42.811273 A > B: . 4893:6353(1460) ack 1 win 32768
  202.      10:40:42.829149 A > B: . 6353:7813(1460) ack 1 win 32768
  203.      10:40:42.853687 B > A: . ack 1973 win 33580 (DF) [tos 0x8]
  204.      10:40:42.864031 B > A: . ack 3433 win 33580 (DF) [tos 0x8]
  205.  
  206.      After the third packet, the connection is established.  A, the con-
  207.      nection responder, begins transmitting to B, the connection initia-
  208.      tor.  Host A quickly sends 6 packets comprising  7812  bytes,  even
  209.      though  the SYN exchange agreed upon an MSS of 1460 bytes (implying
  210.      an initial congestion window  of  1  segment  corresponds  to  1460
  211.      bytes), and so A should have sent at most 1460 bytes.
  212.  
  213.      The acks sent by B to A in the last two lines  indicate  that  this
  214.      trace  is  not a measurement error (slow start really occurring but
  215.      the corresponding acks having been dropped by the packet filter).
  216.  
  217.      A second trace confirmed that the problem is repeatable.
  218.  
  219.  
  220. Trace file demonstrating correct behavior
  221.  
  222.      Made using tcpdump/BPF recording at the connection originator.   No
  223.      losses reported.
  224.  
  225.      12:35:31.914050 C > D: S 1448571845:1448571845(0) win 4380 <mss 1460>
  226.      12:35:32.068819 D > C: S 1755712000:1755712000(0) ack 1448571846 win 4096
  227.      12:35:32.069341 C > D: . ack 1 win 4608
  228.      12:35:32.075213 C > D: P 1:513(512) ack 1 win 4608
  229.      12:35:32.286073 D > C: . ack 513 win 4096
  230.      12:35:32.287032 C > D: . 513:1025(512) ack 1 win 4608
  231.      12:35:32.287506 C > D: . 1025:1537(512) ack 1 win 4608
  232.      12:35:32.432712 D > C: . ack 1537 win 4096
  233.  
  234.  
  235.  
  236. Paxson, Editor                                                  [Page 4]
  237.  
  238.  
  239.  
  240.  
  241.  
  242. ID                 Known TCP Implementation Problems          March 1997
  243.  
  244.  
  245.      12:35:32.433690 C > D: . 1537:2049(512) ack 1 win 4608
  246.      12:35:32.434481 C > D: . 2049:2561(512) ack 1 win 4608
  247.      12:35:32.435032 C > D: . 2561:3073(512) ack 1 win 4608
  248.      12:35:32.594526 D > C: . ack 3073 win 4096
  249.      12:35:32.595465 C > D: . 3073:3585(512) ack 1 win 4608
  250.      12:35:32.595947 C > D: . 3585:4097(512) ack 1 win 4608
  251.      12:35:32.596414 C > D: . 4097:4609(512) ack 1 win 4608
  252.      12:35:32.596888 C > D: . 4609:5121(512) ack 1 win 4608
  253.      12:35:32.733453 D > C: . ack 4097 win 4096
  254.  
  255.  
  256. References
  257.      This problem is documented in [Paxson97].
  258.  
  259. How to detect
  260.      For implementations always manifesting this problem,  it  shows  up
  261.      immediately  in  a  packet trace or a sequence plot, as illustrated
  262.      above.
  263.  
  264. How to fix
  265.      If the root problem is that the implementation lacks a notion of  a
  266.      congestion  window,  then  unfortunately  this requires significant
  267.      work to fix.  However, doing so is critical,  as  such  implementa-
  268.      tions  exhibit  "No slow start after retransmission timeout", which
  269.      has a significance of "Critical".
  270.  
  271.  
  272. 3.2. No slow start after retransmission timeout
  273.  
  274. Category
  275.      Congestion control
  276.  
  277. Description
  278.      When a TCP experiences a retransmission timeout, it is required  by
  279.      RFC  1122,  4.2.2.15, to engage in "slow start" by initializing its
  280.      congestion window, cwnd, to one packet (one segment of the  maximum
  281.      size).   It  subsequently increases cwnd by one packet for each ack
  282.      it  receives  for  new  data  until  it  reaches  the   "congestion
  283.      avoidance"  threshold,  ssthresh,  at  which  point  the congestion
  284.      avoidance algorithm for updating the window takes over.  A TCP that
  285.      fails  to  enter  slow start upon a timeout exhibits "No slow start
  286.      after retransmission timeout".
  287.  
  288. Significance
  289.      Critical.
  290.  
  291. Implications
  292.      Entering slow start upon timeout forms one of the  cornerstones  of
  293.  
  294.  
  295.  
  296. Paxson, Editor                                                  [Page 5]
  297.  
  298.  
  299.  
  300.  
  301.  
  302. ID                 Known TCP Implementation Problems          March 1997
  303.  
  304.  
  305.      Internet  congestion  stability,  as  outlined in [Jacobson88].  If
  306.      TCPs fail to do so,  the  network  becomes  at  risk  of  suffering
  307.      "congestion collapse" [RFC896].
  308.  
  309. Relevant RFCs
  310.      RFC 1122 requires use of slow start after loss.  RFC 2001 gives the
  311.      specifics  of  how  to  implement  slow  start.   RFC 896 describes
  312.      congestion collapse.
  313.  
  314.      The retransmission timeout discussed here should  not  be  confused
  315.      with  the  separate  "fast  recovery" retransmission mechanism dis-
  316.      cussed in RFC 2001.
  317.  
  318.  
  319. Trace file demonstrating it
  320.      Made using tcpdump/BPF recording at the sending TCP (A).  No losses
  321.      reported.
  322.  
  323.      10:40:59.090612 B > A: . ack 357125 win 33580 (DF) [tos 0x8]
  324.      10:40:59.222025 A > B: . 357125:358585(1460) ack 1 win 32768
  325.      10:40:59.868871 A > B: . 357125:358585(1460) ack 1 win 32768
  326.      10:41:00.016641 B > A: . ack 364425 win 33580 (DF) [tos 0x8]
  327.      10:41:00.036709 A > B: . 364425:365885(1460) ack 1 win 32768
  328.      10:41:00.045231 A > B: . 365885:367345(1460) ack 1 win 32768
  329.      10:41:00.053785 A > B: . 367345:368805(1460) ack 1 win 32768
  330.      10:41:00.062426 A > B: . 368805:370265(1460) ack 1 win 32768
  331.      10:41:00.071074 A > B: . 370265:371725(1460) ack 1 win 32768
  332.      10:41:00.079794 A > B: . 371725:373185(1460) ack 1 win 32768
  333.      10:41:00.089304 A > B: . 373185:374645(1460) ack 1 win 32768
  334.      10:41:00.097738 A > B: . 374645:376105(1460) ack 1 win 32768
  335.      10:41:00.106409 A > B: . 376105:377565(1460) ack 1 win 32768
  336.      10:41:00.115024 A > B: . 377565:379025(1460) ack 1 win 32768
  337.      10:41:00.123576 A > B: . 379025:380485(1460) ack 1 win 32768
  338.      10:41:00.132016 A > B: . 380485:381945(1460) ack 1 win 32768
  339.      10:41:00.141635 A > B: . 381945:383405(1460) ack 1 win 32768
  340.      10:41:00.150094 A > B: . 383405:384865(1460) ack 1 win 32768
  341.      10:41:00.158552 A > B: . 384865:386325(1460) ack 1 win 32768
  342.      10:41:00.167053 A > B: . 386325:387785(1460) ack 1 win 32768
  343.      10:41:00.175518 A > B: . 387785:389245(1460) ack 1 win 32768
  344.      10:41:00.210835 A > B: . 389245:390705(1460) ack 1 win 32768
  345.      10:41:00.226108 A > B: . 390705:392165(1460) ack 1 win 32768
  346.      10:41:00.241524 B > A: . ack 389245 win 8760 (DF) [tos 0x8]
  347.  
  348.      The first packet indicates the ack point is 357125.  130 msec after
  349.      receiving  the  ack,  A  transmits  the packet after the ack point,
  350.      357125:358585.  640 msec after this  transmission,  it  retransmits
  351.      357125:358585,  in  an  apparent  retransmission  timeout.  At this
  352.      point, A's cwnd should be one MSS,  or  1460  bytes,  as  A  enters
  353.  
  354.  
  355.  
  356. Paxson, Editor                                                  [Page 6]
  357.  
  358.  
  359.  
  360.  
  361.  
  362. ID                 Known TCP Implementation Problems          March 1997
  363.  
  364.  
  365.      slow-start.  The trace is consistent with this possibility.
  366.  
  367.      B replies with an ack of 364425, indicating that  A  has  filled  a
  368.      sequence  hole.   At  this  point, A's cwnd should be 1460*2 = 2920
  369.      bytes, since in slow start receiving an ack advances cwnd  by  MSS.
  370.      However,  A  then  launches 19 consecutive packets, which is incon-
  371.      sistent with slow start.
  372.  
  373.      A second trace confirmed that the problem is repeatable.
  374.  
  375.  
  376. Trace file demonstrating correct behavior
  377.      Made using tcpdump/BPF recording at the sending TCP (C).  No losses
  378.      reported.
  379.  
  380.      12:35:48.442538 C > D: P 465409:465921(512) ack 1 win 4608
  381.      12:35:48.544483 D > C: . ack 461825 win 4096
  382.      12:35:48.703496 D > C: . ack 461825 win 4096
  383.      12:35:49.044613 C > D: . 461825:462337(512) ack 1 win 4608
  384.      12:35:49.192282 D > C: . ack 465921 win 2048
  385.      12:35:49.192538 D > C: . ack 465921 win 4096
  386.      12:35:49.193392 C > D: P 465921:466433(512) ack 1 win 4608
  387.      12:35:49.194726 C > D: P 466433:466945(512) ack 1 win 4608
  388.      12:35:49.350665 D > C: . ack 466945 win 4096
  389.      12:35:49.351694 C > D: . 466945:467457(512) ack 1 win 4608
  390.      12:35:49.352168 C > D: . 467457:467969(512) ack 1 win 4608
  391.      12:35:49.352643 C > D: . 467969:468481(512) ack 1 win 4608
  392.      12:35:49.506000 D > C: . ack 467969 win 3584
  393.  
  394.      After C transmits the first packet shown to D, it takes  no  action
  395.      in  response  to  D's  acks  for  461825,  because the first packet
  396.      already reached the advertised window limit  of  4096  bytes  above
  397.      461825.    600   msec   after  transmitting  the  first  packet,  C
  398.      retransmits  461825:462337,  presumably  due  to  a  timeout.   Its
  399.      congestion window is now MSS (512 bytes).
  400.  
  401.      D acks 465921, indicating that C's retransmission filled a sequence
  402.      hole.   This  ack advances C's cwnd from 512 to 1024.  Very shortly
  403.      after, D acks 465921 again in order to update  the  offered  window
  404.      from  2048 to 4096.  This ack does not advance cwnd since it is not
  405.      for new data.  Very shortly after, C responds to the newly enlarged
  406.      window  by  transmitting  two packets.  D acks both, advancing cwnd
  407.      from 1024 to 1536.  C in turn transmits three packets.
  408.  
  409.  
  410. References
  411.      This problem is documented in [Paxson97].
  412.  
  413.  
  414.  
  415.  
  416. Paxson, Editor                                                  [Page 7]
  417.  
  418.  
  419.  
  420.  
  421.  
  422. ID                 Known TCP Implementation Problems          March 1997
  423.  
  424.  
  425. How to detect
  426.      Packet loss is common enough in the Internet that generally  it  is
  427.      not  difficult to find an Internet path that will force retransmis-
  428.      sion due to packet loss.
  429.  
  430.      If the effective window prior to loss  is  large  enough,  however,
  431.      then  the  TCP  may  retransmit using the "fast recovery" mechanism
  432.      described in RFC 2001.  In a packet trace, the  signature  of  fast
  433.      recovery  is  that  the packet retransmission occurs in response to
  434.      the receipt of three duplicate acks, and subsequent duplicate  acks
  435.      may  lead to the transmission of new data, above both the ack point
  436.      and the highest sequence transmitted so far.  An absence  of  three
  437.      duplicate  acks  prior  to  retransmission  suffices to distinguish
  438.      between timeout and fast recovery retransmissions.  In the face  of
  439.      only  observing  fast recovery retransmissions, generally it is not
  440.      difficult to repeat the data transfer  until  observing  a  timeout
  441.      retransmission.
  442.  
  443.      Once armed with a trace exhibiting a timeout retransmission, deter-
  444.      mining  whether the TCP follows slow start is done by computing the
  445.      correct progression of cwnd and comparing it to the amount of  data
  446.      transmited by the TCP subsequent to the timeout rtransmission.
  447.  
  448.  
  449. How to fix
  450.      If the root problem is that the implementation lacks a notion of  a
  451.      congestion  window,  then  unfortunately  this requires significant
  452.      work to fix.  However, doing so is critical, for  reasons  outlined
  453.      above.
  454.  
  455.  
  456. 3.3. Inconsistent retransmission
  457.  
  458. Category
  459.      Reliability
  460.  
  461. Description
  462.      If, for a given sequence number, a  sending  TCP  retransmits  dif-
  463.      ferent  data  than previously sent for that sequence number, then a
  464.      strong possibility arises that the receiving TCP will reconstruct a
  465.      different  byte  stream  than that sent by the sending application,
  466.      depending on which instance of  the  sequence  number  it  accepts.
  467.      Such a sending TCP exhibits "Inconsistent retransmission".
  468.  
  469. Significance
  470.      Critical.
  471.  
  472. Implications
  473.  
  474.  
  475.  
  476. Paxson, Editor                                                  [Page 8]
  477.  
  478.  
  479.  
  480.  
  481.  
  482. ID                 Known TCP Implementation Problems          March 1997
  483.  
  484.  
  485.      Reliable delivery of data is a fundamental property of TCP.
  486.  
  487. Relevant RFCs
  488.      RFC 793, section 1.5, discusses the central role of reliability  in
  489.      TCP operation.
  490.  
  491. Trace file demonstrating it
  492.      Made using tcpdump/BPF recording at  the  receiving  TCP  (B).   No
  493.      losses reported.
  494.  
  495.      12:35:53.145503 A > B: FP 90048435:90048461(26) ack 393464682 win 4096
  496.                                           4500 0042 9644 0000
  497.                       3006 e4c2 86b1 0401 83f3 010a b2a4 0015
  498.                       055e 07b3 1773 cb6a 5019 1000 68a9 0000
  499.      data starts here>504f 5254 2031 3334 2c31 3737*2c34 2c31
  500.                       2c31 3738 2c31 3635 0d0a
  501.      12:35:53.146479 B > A: R 393464682:393464682(0) win 8192
  502.      12:35:53.851714 A > B: FP 90048429:90048463(34) ack 393464682 win 4096
  503.                                           4500 004a 965b 0000
  504.                       3006 e4a3 86b1 0401 83f3 010a b2a4 0015
  505.                       055e 07ad 1773 cb6a 5019 1000 8bd3 0000
  506.      data starts here>5041 5356 0d0a 504f 5254 2031 3334 2c31
  507.                       3737*2c31 3035 2c31 3431 2c34 2c31 3539
  508.                       0d0a
  509.  
  510.      The sequence numbers shown in  this  trace  are  absolute  and  not
  511.      adjusted to reflect the ISN.  The 4-digit hex values show a dump of
  512.      the packet's IP and TCP headers, as well as payload.  A first sends
  513.      to  B  data  for  90048435:90048461.  The corresponding data begins
  514.      with hex words 504f, 5254, etc.
  515.  
  516.      B responds with a RST.  Since the recording location was  local  to
  517.      B, it is unknown whether A received the RST.
  518.  
  519.      A then sends 90048429:90048463, which includes six  sequence  posi-
  520.      tions  below the earlier transmission, all 26 positions of the ear-
  521.      lier transmission, and two additional sequence positions.
  522.  
  523.      The retransmission disagrees starting just after sequence 90048447,
  524.      annotated  above  with  a leading '*'.  These two bytes were origi-
  525.      nally transmitted as hex 2c34 but retransmitted as hex 2c31.   Sub-
  526.      sequent positions disagree as well.
  527.  
  528.      This behavior has been observed in other traces involving different
  529.      hosts.  It is unknown how to repeat it.
  530.  
  531.      In this instance, no corruption would occur, since  B  has  already
  532.      indicated it will not accept further packets from A.
  533.  
  534.  
  535.  
  536. Paxson, Editor                                                  [Page 9]
  537.  
  538.  
  539.  
  540.  
  541.  
  542. ID                 Known TCP Implementation Problems          March 1997
  543.  
  544.  
  545.      A second example illustrates a slightly different instance  of  the
  546.      problem.   The  tracing  again  was  made  with  tcpdump/BPF at the
  547.      receiving TCP (D).
  548.  
  549.      22:23:58.645829 C > D: P 185:212(27) ack 565 win 4096
  550.                                           4500 0043 90a3 0000
  551.                       3306 0734 cbf1 9eef 83f3 010a 0525 0015
  552.                       a3a2 faba 578c 70a4 5018 1000 9a53 0000
  553.      data starts here>504f 5254 2032 3033 2c32 3431 2c31 3538
  554.                       2c32 3339 2c35 2c34 330d 0a
  555.      22:23:58.646805 D > C: . ack 184 win 8192
  556.                                           4500 0028 beeb 0000
  557.                       3e06 ce06 83f3 010a cbf1 9eef 0015 0525
  558.                       578c 70a4 a3a2 fab9 5010 2000 342f 0000
  559.      22:31:36.532244 C > D: FP 186:213(27) ack 565 win 4096
  560.                                           4500 0043 9435 0000
  561.                       3306 03a2 cbf1 9eef 83f3 010a 0525 0015
  562.                       a3a2 fabb 578c 70a4 5019 1000 9a51 0000
  563.      data starts here>504f 5254 2032 3033 2c32 3431 2c31 3538
  564.                       2c32 3339 2c35 2c34 330d 0a
  565.  
  566.      In this trace, sequence numbers are relative.  C sends 185:212, but
  567.      D only sends an ack for 184 (so sequence number 184 is missing).  C
  568.      then sends 186:213.  The packet payload is identical to the  previ-
  569.      ous  payload, but the base sequence number is one higher, resulting
  570.      in an inconsistent retransmission.
  571.  
  572.      Neither trace exhibits checksum errors.
  573.  
  574.  
  575. Trace file demonstrating correct behavior
  576.      (Omitted, as presumably correct behavior is obvious.)
  577.  
  578. References
  579.      None known.
  580.  
  581. How to detect
  582.      This problem unfortunately can be very difficult to  detect,  since
  583.      available  experience  indicates  it is quite rare that it is mani-
  584.      fested.  No "trigger" has been  identified  that  can  be  used  to
  585.      reproduce the problem.
  586.  
  587. How to fix
  588.      In the absence of a known "trigger", we cannot always assess how to
  589.      fix the problem.
  590.  
  591.      In one implementation (not the one illustrated above), the  problem
  592.      manifested  itself  when  (1) the sender received a zero window and
  593.  
  594.  
  595.  
  596. Paxson, Editor                                                 [Page 10]
  597.  
  598.  
  599.  
  600.  
  601.  
  602. ID                 Known TCP Implementation Problems          March 1997
  603.  
  604.  
  605.      stalled; (2) eventually an ack arrived that offered a window larger
  606.      than  that  in  effect  at  the  time  of the stall; (3) the sender
  607.      transmitted out of the buffer of data it held at the  time  of  the
  608.      stall,  but (4) failed to limit this transfer to the buffer length,
  609.      instead using the newly advertised  (and  larger)  offered  window.
  610.      Consequently,  in  addition  to  the valid buffer contents, it sent
  611.      whatever garbage values followed the end of the buffer.  If it then
  612.      retransmitted  the corresponding sequence numbers, at that point it
  613.      sent the correct data, resulting in an inconsistent retransmission.
  614.      Note  that  this  instance  of  the problem reflects a more general
  615.      problem, that of initially transmitting incorrect data.
  616.  
  617.  
  618. 3.4. Failure to retain above-sequence data
  619.  
  620. Category
  621.      Congestion control, performance
  622.  
  623. Description
  624.      When a TCP receives an "above sequence" segment, meaning one with a
  625.      sequence  number  exceeding  RCV.NXT  but below RCV.NXT+RCV.WND, it
  626.      SHOULD queue the segment for later delivery (RFC  1122,  4.2.2.20).
  627.      A  TCP  that  fails  to do so is said to exhibit "Failure to retain
  628.      above-sequence data".
  629.  
  630.      It may sometimes be appropriate for a TCP to discard above-sequence
  631.      data  to  reclaim memory.  If they do so only rarely, then we would
  632.      not consider them to exhibit this problem.  Instead, the particular
  633.      concern is with TCPs that always discard above-sequence data.
  634.  
  635.  
  636. Significance
  637.      Serious.
  638.  
  639. Implications
  640.      In times of congestion, a failure  to  retain  above-sequence  data
  641.      will lead to numerous otherwise-unnecessary retransmissions, aggra-
  642.      vating the congestion and potentially  reducing  performance  by  a
  643.      large factor.
  644.  
  645. Relevant RFCs
  646.      RFC 1122 revises RFC 793 by upgrading the latter's MAY to a  SHOULD
  647.      on this issue.
  648.  
  649. Trace file demonstrating it
  650.      Made using tcpdump/BPF recording at the receiving TCP.   No  losses
  651.      reported.
  652.  
  653.  
  654.  
  655.  
  656. Paxson, Editor                                                 [Page 11]
  657.  
  658.  
  659.  
  660.  
  661.  
  662. ID                 Known TCP Implementation Problems          March 1997
  663.  
  664.  
  665.      B is the TCP sender, A the receiver.  A exhibits failure to  retain
  666.      above sequence data:
  667.  
  668.      10:38:10.164860 B > A: . 221078:221614(536) ack 1 win 33232 [tos 0x8]
  669.      10:38:10.170809 B > A: . 221614:222150(536) ack 1 win 33232 [tos 0x8]
  670.      10:38:10.177183 B > A: . 222150:222686(536) ack 1 win 33232 [tos 0x8]
  671.      10:38:10.225039 A > B: . ack 222686 win 25800
  672.  
  673.      Here B has sent up to (relative) sequence 222676 in-sequence, and A
  674.      accordingly acknowledges.
  675.  
  676.      10:38:10.268131 B > A: . 223222:223758(536) ack 1 win 33232 [tos 0x8]
  677.      10:38:10.337995 B > A: . 223758:224294(536) ack 1 win 33232 [tos 0x8]
  678.      10:38:10.344065 B > A: . 224294:224830(536) ack 1 win 33232 [tos 0x8]
  679.      10:38:10.350169 B > A: . 224830:225366(536) ack 1 win 33232 [tos 0x8]
  680.      10:38:10.356362 B > A: . 225366:225902(536) ack 1 win 33232 [tos 0x8]
  681.      10:38:10.362445 B > A: . 225902:226438(536) ack 1 win 33232 [tos 0x8]
  682.      10:38:10.368579 B > A: . 226438:226974(536) ack 1 win 33232 [tos 0x8]
  683.      10:38:10.374732 B > A: . 226974:227510(536) ack 1 win 33232 [tos 0x8]
  684.      10:38:10.380825 B > A: . 227510:228046(536) ack 1 win 33232 [tos 0x8]
  685.      10:38:10.387027 B > A: . 228046:228582(536) ack 1 win 33232 [tos 0x8]
  686.      10:38:10.393053 B > A: . 228582:229118(536) ack 1 win 33232 [tos 0x8]
  687.      10:38:10.399193 B > A: . 229118:229654(536) ack 1 win 33232 [tos 0x8]
  688.      10:38:10.405356 B > A: . 229654:230190(536) ack 1 win 33232 [tos 0x8]
  689.  
  690.      A now receives 13 additional packets  from  B.   These  are  above-
  691.      sequence because 222686:223222 was dropped.  The packets do however
  692.      fit within the offered window of 25800.  A does  not  generate  any
  693.      duplicate acks for them.
  694.  
  695.      The trace contributor (V. Paxson) verified that  these  13  packets
  696.      had valid IP and TCP checksums.
  697.  
  698.      10:38:11.917728 B > A: . 222686:223222(536) ack 1  win  33232  [tos
  699.      0x8] 10:38:11.930925 A > B: . ack 223222 win 32232
  700.  
  701.      B times out for 222686:223222 and retransmits it.   Upon  receiving
  702.      it,  A  only acknowledges 223222.  Had it retained the valid above-
  703.      sequence packets, it would instead have ack'd 230190.
  704.  
  705.      10:38:12.048438 B > A: . 223222:223758(536) ack 1  win  33232  [tos
  706.      0x8]  10:38:12.054397  B  > A: . 223758:224294(536) ack 1 win 33232
  707.      [tos 0x8] 10:38:12.068029 A > B: . ack 224294 win 31696
  708.  
  709.      B retransmits two more packets, and A only acknowledges them.  This
  710.      pattern  continues  as  B retransmits the entire set of previously-
  711.      received packets.
  712.  
  713.  
  714.  
  715.  
  716. Paxson, Editor                                                 [Page 12]
  717.  
  718.  
  719.  
  720.  
  721.  
  722. ID                 Known TCP Implementation Problems          March 1997
  723.  
  724.  
  725.      A second trace confirmed that the problem is repeatable.
  726.  
  727.  
  728. Trace file demonstrating correct behavior
  729.      Made using tcpdump/BPF recording at  the  receiving  TCP  (C).   No
  730.      losses reported.
  731.  
  732.      09:11:25.790417 D > C: . 33793:34305(512) ack 1 win 61440
  733.      09:11:25.791393 D > C: . 34305:34817(512) ack 1 win 61440
  734.      09:11:25.792369 D > C: . 34817:35329(512) ack 1 win 61440
  735.      09:11:25.792369 D > C: . 35329:35841(512) ack 1 win 61440
  736.      09:11:25.793345 D > C: . 36353:36865(512) ack 1 win 61440
  737.      09:11:25.794321 C > D: . ack 35841 win 59904
  738.  
  739.      A sequence hole occurs because 35841:36353 has been dropped.
  740.  
  741.      09:11:25.794321 D > C: . 36865:37377(512) ack 1 win 61440
  742.      09:11:25.794321 C > D: . ack 35841 win 59904
  743.      09:11:25.795297 D > C: . 37377:37889(512) ack 1 win 61440
  744.      09:11:25.795297 C > D: . ack 35841 win 59904
  745.      09:11:25.796273 C > D: . ack 35841 win 61440
  746.      09:11:25.798225 D > C: . 37889:38401(512) ack 1 win 61440
  747.      09:11:25.799201 C > D: . ack 35841 win 61440
  748.      09:11:25.807009 D > C: . 38401:38913(512) ack 1 win 61440
  749.      09:11:25.807009 C > D: . ack 35841 win 61440
  750.      09:11:25.884113 D > C: . 52737:53249(512) ack 1 win 61440
  751.      09:11:25.884113 C > D: . ack 35841 win 61440
  752.  
  753.      Each additional, above-sequence packet C receives from D elicits  a
  754.      duplicate ack for 35841.
  755.  
  756.      09:11:25.887041 D > C: . 35841:36353(512) ack 1 win 61440
  757.      09:11:25.887041 C > D: . ack 53249 win 44032
  758.  
  759.      D retransmits 35841:36353 and C acknowledges receipt  of  data  all
  760.      the way up to 53249.
  761.  
  762.  
  763. References
  764.      This problem is documented in [Paxson97].
  765.  
  766.  
  767. How to detect
  768.      Packet loss is common enough in the Internet that generally  it  is
  769.      not  difficult  to  find  an Internet path that will result in some
  770.      above-sequence packets arriving.  A TCP that exhibits  "Failure  to
  771.      retain  ..."  may  not  generate  duplicate acks for these packets.
  772.      However, some TCPs that do retain above-sequence data also  do  not
  773.  
  774.  
  775.  
  776. Paxson, Editor                                                 [Page 13]
  777.  
  778.  
  779.  
  780.  
  781.  
  782. ID                 Known TCP Implementation Problems          March 1997
  783.  
  784.  
  785.      generate  duplicate acks, so failure to do so does not definitively
  786.      identify the problem.  Instead, the key observation is whether upon
  787.      retransmission  of  the  dropped  packet,  data that was previously
  788.      above-sequence is acknowledged.
  789.  
  790.      Two considerations in detecting this problem using a  packet  trace
  791.      are  that  it  is  easiest  to  do  so with a trace made at the TCP
  792.      receiver, in order to unambiguously determine which packets arrived
  793.      successfully,  and  that  such  packets may still be correctly dis-
  794.      carded if they arrive with checksum  errors.   The  latter  can  be
  795.      tested  by  capturing the entire packet contents and performing the
  796.      IP and TCP checksum algorithms to verify  their  integrity;  or  by
  797.      confirming  that the packets arrive with the same checksum and con-
  798.      tents as that with which they were sent, with  a  presumption  that
  799.      the  sending  TCP correctly calculates checksums for the packets it
  800.      transmits.
  801.  
  802.      It is considerably easier to verify that an implementation does NOT
  803.      exhibit this problem.  This can be done by recording a trace at the
  804.      data sender, and observing that sometimes  after  a  retransmission
  805.      the  receiver  acknowledges a higher sequence number than just that
  806.      which was retransmitted.
  807.  
  808.  
  809. How to fix
  810.      If the root problem is that the implementation lacks  buffer,  then
  811.      then unfortunately this requires significant work to fix.  However,
  812.      doing so is important, for reasons outlined above.
  813.  
  814.  
  815. 4. Security Considerations
  816.  
  817.    This version of this  memo  does  not  discuss  any  security-related
  818.    implementation problems.  Futures versions most likely will, so secu-
  819.    rity considerations will require revisiting.
  820.  
  821.  
  822. 5. Acknowledgements
  823.  
  824.    Thanks to numerous correspondents on the tcp-impl  mailing  list  for
  825.    their  input: Steve Alexander, Mark Allman, Larry Backman, Jerry Chu,
  826.    Alan Cox, Kevin Fall, Richard Fox, Jim Gettys,  Rick  Jones,  Allison
  827.    Mankin,  Perry  Metzger, der Mouse, Thomas Narten, Andras Olah, Steve
  828.    Parker, Francesco Potorti`, Luigi Rizzo,  Allyn  Romanow,  Al  Smith,
  829.    Jerry Toporek, Joe Touch, and Curtis Villamizar.
  830.  
  831.  
  832.  
  833.  
  834.  
  835.  
  836. Paxson, Editor                                                 [Page 14]
  837.  
  838.  
  839.  
  840.  
  841.  
  842. ID                 Known TCP Implementation Problems          March 1997
  843.  
  844.  
  845. 6. References
  846.  
  847.  
  848. [Jacobson88]
  849.      V. Jacobson, "Congestion Avoidance and Control," Proc. SIGCOMM '88.
  850.      ftp://ftp.ee.lbl.gov/papers/congavoid.ps.Z
  851.  
  852. [Paxson97]
  853.      V. Paxson, "Automated Packet  Trace  Analysis  of  TCP  Implementa-
  854.      tions," available in draft form from vern@ee.lbl.gov, Feb. 1997.
  855.  
  856. [RFC896]
  857.      J. Nagle, "Congestion Control in IP/TCP Internetworks," Jan. 1984.
  858.  
  859. [RFC1122]
  860.      R. Braden, Editor, "Requirements for Internet Hosts  --  Communica-
  861.      tion Layers," Oct. 1989.
  862.  
  863. [RFC2001]
  864.      W. Stevens, "TCP Slow Start, Congestion Avoidance, Fast Retransmit,
  865.      and Fast Recovery Algorithms," Jan. 1997.
  866.  
  867.  
  868. 7. Author's Address
  869.  
  870.    Vern Paxson <vern@ee.lbl.gov>
  871.    Network Research Group
  872.    Lawrence Berkeley National Laboratory
  873.    Berkeley, CA 94720
  874.    USA
  875.    Phone: +1 510/486-7504
  876.  
  877.  
  878.  
  879.  
  880.  
  881.  
  882.  
  883.  
  884.  
  885.  
  886.  
  887.  
  888.  
  889.  
  890.  
  891.  
  892.  
  893.  
  894.  
  895.  
  896. Paxson, Editor                                                 [Page 15]
  897.  
  898.  
  899.