Request for Comments: 2525 Editor
Category: Informational ACIRI / ICSI
M. Allman
NASA Glenn Research Center/Sterling Software
S. Dawson
Real-Time Computing Laboratory
W. Fenner
Xerox PARC
J. Griner
NASA Glenn Research Center
I. Heavens
Spider Software Ltd.
K. Lahey
NASA Ames Research Center/MRJ
J. Semke
Pittsburgh Supercomputing Center
B. Volz
Process Software Corporation
March 1999
Known TCP Implementation Problems
Status of this Memo
This memo provides information for the Internet community. It does
not specify an Internet standard of any kind. Distribution of this
memo is unlimited.
Copyright Notice
Copyright (C) The Internet Society (1999). All Rights Reserved.
Table of Contents
1. INTRODUCTION....................................................2
2. KNOWN IMPLEMENTATION PROBLEMS...................................3
2.1 No initial slow start........................................3
2.2 No slow start after retransmission timeout...................6
2.3 Uninitialized CWND...........................................9
2.4 Inconsistent retransmission.................................11
2.5 Failure to retain above-sequence data.......................13
2.6 Extra additive constant in congestion avoidance.............17
2.7 Initial RTO too low.........................................23
2.8 Failure of window deflation after loss recovery.............26
2.9 Excessively short keepalive connection timeout..............28
2.10 Failure to back off retransmission timeout..................31
2.11 Insufficient interval between keepalives....................34
2.12 Window probe deadlock.......................................36
2.13 Stretch ACK violation.......................................40
2.14 Retransmission sends multiple packets.......................43
2.15 Failure to send FIN notification promptly...................45
2.16 Failure to send a RST after Half Duplex Close...............47
2.17 Failure to RST on close with data pending...................50
2.18 Options missing from TCP MSS calculation....................54
3. SECURITY CONSIDERATIONS........................................56
4. ACKNOWLEDGEMENTS...............................................56
5. REFERENCES.....................................................57
6. AUTHORS' ADDRESSES.............................................58
7. FULL COPYRIGHT STATEMENT.......................................60
1. Introduction
This memo catalogs a number of known TCP implementation problems.
The goal in doing so is to improve conditions in the existing
Internet by enhancing the quality of current TCP/IP implementations.
It is hoped that both performance and correctness issues can be
resolved by making implementors aware of the problems and their
solutions. In the long term, it is hoped that this will provide a
reduction in unnecessary traffic on the network, the rate of
connection failures due to protocol errors, and load on network
servers due to time spent processing both unsuccessful connections
and retransmitted data. This will help to ensure the stability of
the global Internet.
Each problem is defined as follows:
Name of Problem
The name associated with the problem. In this memo, the name is
given as a subsection heading.
Classification
One or more problem categories for which the problem is
classified: "congestion control", "performance", "reliability",
"resource management".
Description
A definition of the problem, succinct but including necessary
background material.
Significance
A brief summary of the sorts of environments for which the problem
is significant.
Implications
Why the problem is viewed as a problem.
Relevant RFCs
The RFCs defining the TCP specification with which the problem
conflicts. These RFCs often qualify behavior using terms such as
MUST, SHOULD, MAY, and others written capitalized. See RFC2119
for the exact interpretation of these terms.
Trace file demonstrating the problem
One or more ASCII trace files demonstrating the problem, if
applicable.
Trace file demonstrating correct behavior
One or more examples of how correct behavior appears in a trace,
if applicable.
References
References that further discuss the problem.
How to detect
How to test an implementation to see if it exhibits the problem.
This discussion may include difficulties and subtleties associated
with causing the problem to manifest itself, and with interpreting
traces to detect the presence of the problem (if applicable).
How to fix
For known causes of the problem, how to correct the
implementation.
2. Known implementation problems
2.1.
Name of Problem
No initial slow start
Classification
Congestion control
Description
When a TCP begins transmitting data, it is required by RFC1122,
4.2.2.15, to engage in a "slow start" by initializing its
congestion window, cwnd, to one packet (one segment of the maximum
size). (Note that an experimental change to TCP, documented in
[RFC2414], allows an initial value somewhat larger than one
packet.) It subsequently increases cwnd by one packet for each
ACK it receives for new data. The minimum of cwnd and the
receiver's advertised window bounds the highest sequence number
the TCP can transmit. A TCP that fails to initialize and
increment cwnd in this fashion exhibits "No initial slow start".
Significance
In congested environments, detrimental to the performance of other
connections, and possibly to the connection itself.
Implications
A TCP failing to slow start when beginning a connection results in
traffic bursts that can stress the network, leading to excessive
queueing delays and packet loss.
Implementations exhibiting this problem might do so because they
suffer from the general problem of not including the required
congestion window. These implementations will also suffer from
"No slow start after retransmission timeout".
There are different shades of "No initial slow start". From the
perspective of stressing the network, the worst is a connection
that simply always sends based on the receiver's advertised
window, with no notion of a separate congestion window. Another
form is described in "Uninitialized CWND" below.
Relevant RFCs
RFC1122 requires use of slow start. RFC2001 gives the specifics
of slow start.
Trace file demonstrating it
Made using tcpdump [Jacobson89] recording at the connection
responder. No losses reported by the packet filter.
10:40:42.244503 B > A: S 1168512000:1168512000(0) win 32768
<mss 1460,nop,wscale 0> (DF) [tos 0x8]
10:40:42.259908 A > B: S 3688169472:3688169472(0)
ack 1168512001 win 32768 <mss 1460>
10:40:42.389992 B > A: . ack 1 win 33580 (DF) [tos 0x8]
10:40:42.664975 A > B: P 1:513(512) ack 1 win 32768
10:40:42.700185 A > B: . 513:1973(1460) ack 1 win 32768
10:40:42.718017 A > B: . 1973:3433(1460) ack 1 win 32768
10:40:42.762945 A > B: . 3433:4893(1460) ack 1 win 32768
10:40:42.811273 A > B: . 4893:6353(1460) ack 1 win 32768
10:40:42.829149 A > B: . 6353:7813(1460) ack 1 win 32768
10:40:42.853687 B > A: . ack 1973 win 33580 (DF) [tos 0x8]
10:40:42.864031 B > A: . ack 3433 win 33580 (DF) [tos 0x8]
After the third packet, the connection is established. A, the
connection responder, begins transmitting to B, the connection
initiator. Host A quickly sends 6 packets comprising 7812 bytes,
even though the SYN exchange agreed upon an MSS of 1460 bytes
(implying an initial congestion window of 1 segment corresponds to
1460 bytes), and so A should have sent at most 1460 bytes.
The ACKs sent by B to A in the last two lines indicate that this
trace is not a measurement error (slow start really occurring but
the corresponding ACKs having been dropped by the packet filter).
A second trace confirmed that the problem is repeatable.
Trace file demonstrating correct behavior
Made using tcpdump recording at the connection originator. No
losses reported by the packet filter.
12:35:31.914050 C > D: S 1448571845:1448571845(0)
win 4380 <mss 1460>
12:35:32.068819 D > C: S 1755712000:1755712000(0)
ack 1448571846 win 4096
12:35:32.069341 C > D: . ack 1 win 4608
12:35:32.075213 C > D: P 1:513(512) ack 1 win 4608
12:35:32.286073 D > C: . ack 513 win 4096
12:35:32.287032 C > D: . 513:1025(512) ack 1 win 4608
12:35:32.287506 C > D: . 1025:1537(512) ack 1 win 4608
12:35:32.432712 D > C: . ack 1537 win 4096
12:35:32.433690 C > D: . 1537:2049(512) ack 1 win 4608
12:35:32.434481 C > D: . 2049:2561(512) ack 1 win 4608
12:35:32.435032 C > D: . 2561:3073(512) ack 1 win 4608
12:35:32.594526 D > C: . ack 3073 win 4096
12:35:32.595465 C > D: . 3073:3585(512) ack 1 win 4608
12:35:32.595947 C > D: . 3585:4097(512) ack 1 win 4608
12:35:32.596414 C > D: . 4097:4609(512) ack 1 win 4608
12:35:32.596888 C > D: . 4609:5121(512) ack 1 win 4608
12:35:32.733453 D > C: . ack 4097 win 4096
References
This problem is documented in [Paxson97].
How to detect
For implementations always manifesting this problem, it shows up
immediately in a packet trace or a sequence plot, as illustrated
above.
How to fix
If the root problem is that the implementation lacks a notion of a
congestion window, then unfortunately this requires significant
work to fix. However, doing so is important, as such
implementations also exhibit "No slow start after retransmission
timeout".
2.2.
Name of Problem
No slow start after retransmission timeout
Classification
Congestion control
Description
When a TCP experiences a retransmission timeout, it is required by
RFC1122, 4.2.2.15, to engage in "slow start" by initializing its
congestion window, cwnd, to one packet (one segment of the maximum
size). It subsequently increases cwnd by one packet for each ACK
it receives for new data until it reaches the "congestion
avoidance" threshold, ssthresh, at which point the congestion
avoidance algorithm for updating the window takes over. A TCP
that fails to enter slow start upon a timeout exhibits "No slow
start after retransmission timeout".
Significance
In congested environments, severely detrimental to the performance
of other connections, and also the connection itself.
Implications
Entering slow start upon timeout forms one of the cornerstones of
Internet congestion stability, as outlined in [Jacobson88]. If
TCPs fail to do so, the network becomes at risk of suffering
"congestion collapse" [RFC896].
Relevant RFCs
RFC1122 requires use of slow start after loss. RFC2001 gives
the specifics of how to implement slow start. RFC896 describes
congestion collapse.
The retransmission timeout discussed here should not be confused
with the separate "fast recovery" retransmission mechanism
discussed in RFC2001.
Trace file demonstrating it
Made using tcpdump recording at the sending TCP (A). No losses
reported by the packet filter.
10:40:59.090612 B > A: . ack 357125 win 33580 (DF) [tos 0x8]
10:40:59.222025 A > B: . 357125:358585(1460) ack 1 win 32768
10:40:59.868871 A > B: . 357125:358585(1460) ack 1 win 32768
10:41:00.016641 B > A: . ack 364425 win 33580 (DF) [tos 0x8]
10:41:00.036709 A > B: . 364425:365885(1460) ack 1 win 32768
10:41:00.045231 A > B: . 365885:367345(1460) ack 1 win 32768
10:41:00.053785 A > B: . 367345:368805(1460) ack 1 win 32768
10:41:00.062426 A > B: . 368805:370265(1460) ack 1 win 32768
10:41:00.071074 A > B: . 370265:371725(1460) ack 1 win 32768
10:41:00.079794 A > B: . 371725:373185(1460) ack 1 win 32768
10:41:00.089304 A > B: . 373185:374645(1460) ack 1 win 32768
10:41:00.097738 A > B: . 374645:376105(1460) ack 1 win 32768
10:41:00.106409 A > B: . 376105:377565(1460) ack 1 win 32768
10:41:00.115024 A > B: . 377565:379025(1460) ack 1 win 32768
10:41:00.123576 A > B: . 379025:380485(1460) ack 1 win 32768
10:41:00.132016 A > B: . 380485:381945(1460) ack 1 win 32768
10:41:00.141635 A > B: . 381945:383405(1460) ack 1 win 32768
10:41:00.150094 A > B: . 383405:384865(1460) ack 1 win 32768
10:41:00.158552 A > B: . 384865:386325(1460) ack 1 win 32768
10:41:00.167053 A > B: . 386325:387785(1460) ack 1 win 32768
10:41:00.175518 A > B: . 387785:389245(1460) ack 1 win 32768
10:41:00.210835 A > B: . 389245:390705(1460) ack 1 win 32768
10:41:00.226108 A > B: . 390705:392165(1460) ack 1 win 32768
10:41:00.241524 B > A: . ack 389245 win 8760 (DF) [tos 0x8]
The first packet indicates the ack point is 357125. 130 msec
after receiving the ACK, A transmits the packet after the ACK
point, 357125:358585. 640 msec after this transmission, it
retransmits 357125:358585, in an apparent retransmission timeout.
At this point, A's cwnd should be one MSS, or 1460 bytes, as A
enters slow start. The trace is consistent with this possibility.
B replies with an ACK of 364425, indicating that A has filled a
sequence hole. At this point, A's cwnd should be 1460*2 = 2920
bytes, since in slow start receiving an ACK advances cwnd by MSS.
However, A then launches 19 consecutive packets, which is
inconsistent with slow start.
A second trace confirmed that the problem is repeatable.
Trace file demonstrating correct behavior
Made using tcpdump recording at the sending TCP (C). No losses
reported by the packet filter.
12:35:48.442538 C > D: P 465409:465921(512) ack 1 win 4608
12:35:48.544483 D > C: . ack 461825 win 4096
12:35:48.703496 D > C: . ack 461825 win 4096
12:35:49.044613 C > D: . 461825:462337(512) ack 1 win 4608
12:35:49.192282 D > C: . ack 465921 win 2048
12:35:49.192538 D > C: . ack 465921 win 4096
12:35:49.193392 C > D: P 465921:466433(512) ack 1 win 4608
12:35:49.194726 C > D: P 466433:466945(512) ack 1 win 4608
12:35:49.350665 D > C: . ack 466945 win 4096
12:35:49.351694 C > D: . 466945:467457(512) ack 1 win 4608
12:35:49.352168 C > D: . 467457:467969(512) ack 1 win 4608
12:35:49.352643 C > D: . 467969:468481(512) ack 1 win 4608
12:35:49.506000 D > C: . ack 467969 win 3584
After C transmits the first packet shown to D, it takes no action
in response to D's ACKs for 461825, because the first packet
already reached the advertised window limit of 4096 bytes above
461825. 600 msec after transmitting the first packet, C
retransmits 461825:462337, presumably due to a timeout. Its
congestion window is now MSS (512 bytes).
D acks 465921, indicating that C's retransmission filled a
sequence hole. This ACK advances C's cwnd from 512 to 1024. Very
shortly after, D acks 465921 again in order to update the offered
window from 2048 to 4096. This ACK does not advance cwnd since it
is not for new data. Very shortly after, C responds to the newly
enlarged window by transmitting two packets. D acks both,
advancing cwnd from 1024 to 1536. C in turn transmits three
packets.
References
This problem is documented in [Paxson97].
How to detect
Packet loss is common enough in the Internet that generally it is
not difficult to find an Internet path that will force
retransmission due to packet loss.
If the effective window prior to loss is large enough, however,
then the TCP may retransmit using the "fast recovery" mechanism
described in RFC2001. In a packet trace, the signature of fast
recovery is that the packet retransmission occurs in response to
the receipt of three duplicate ACKs, and subsequent duplicate ACKs
may lead to the transmission of new data, above both the ack point
and the highest sequence transmitted so far. An absence of three
duplicate ACKs prior to retransmission suffices to distinguish
between timeout and fast recovery retransmissions. In the face of
only observing fast recovery retransmissions, generally it is not
difficult to repeat the data transfer until observing a timeout
retransmission.
Once armed with a trace exhibiting a timeout retransmission,
determining whether the TCP follows slow start is done by
computing the correct progression of cwnd and comparing it to the
amount of data transmitted by the TCP subsequent to the timeout
retransmission.
How to fix
If the root problem is that the implementation lacks a notion of a
congestion window, then unfortunately this requires significant
work to fix. However, doing so is critical, for reasons outlined
above.
2.3.
Name of Problem
Uninitialized CWND
Classification
Congestion control
Description
As described above for "No initial slow start", when a TCP
connection begins cwnd is initialized to one segment (or perhaps a
few segments, if experimenting with [RFC2414]). One particular
form of "No initial slow start", worth separate mention as the bug
is fairly widely deployed, is "Uninitialized CWND". That is,
while the TCP implements the proper slow start mechanism, it fails
to initialize cwnd properly, so slow start in fact fails to occur.
One way the bug can occur is if, during the connection
establishment handshake, the SYN ACK packet arrives without an MSS
option. The faulty implementation uses receipt of the MSS option
to initialize cwnd to one segment; if the option fails to arrive,
then cwnd is instead initialized to a very large value.
Significance
In congested environments, detrimental to the performance of other
connections, and likely to the connection itself. The burst can
be so large (see below) that it has deleterious effects even in
uncongested environments.
Implications
A TCP exhibiting this behavior is stressing the network with a
large burst of packets, which can cause loss in the network.
Relevant RFCs
RFC1122 requires use of slow start. RFC2001 gives the specifics
of slow start.
Trace file demonstrating it
This trace was made using tcpdump running on host A. Host A is
the sender and host B is the receiver. The advertised window and
timestamp options have been omitted for clarity, except for the
first segment sent by host A. Note that A sends an MSS option in
its initial SYN but B does not include one in its reply.
16:56:02.226937 A > B: S 237585307:237585307(0) win 8192
<mss 536,nop,wscale 0,nop,nop,timestamp[|tcp]>
16:56:02.557135 B > A: S 1617216000:1617216000(0)
ack 237585308 win 16384
16:56:02.557788 A > B: . ack 1 win 8192
16:56:02.566014 A > B: . 1:537(536) ack 1
16:56:02.566557 A > B: . 537:1073(536) ack 1
16:56:02.567120 A > B: . 1073:1609(536) ack 1
16:56:02.567662 A > B: P 1609:2049(440) ack 1
16:56:02.568349 A > B: . 2049:2585(536) ack 1
16:56:02.568909 A > B: . 2585:3121(536) ack 1
[54 additional burst segments deleted for brevity]
16:56:02.936638 A > B: . 32065:32601(536) ack 1
16:56:03.018685 B > A: . ack 1
After the three-way handshake, host A bursts 61 segments into the
network, before duplicate ACKs on the first segment cause a
retransmission to occur. Since host A did not wait for the ACK on
the first segment before sending additional segments, it is
exhibiting "Uninitialized CWND"
Trace file demonstrating correct behavior
See the example for "No initial slow start".
References
This problem is documented in [Paxson97].
How to detect
This problem can be detected by examining a packet trace recorded
at either the sender or the receiver. However, the bug can be
difficult to induce because it requires finding a remote TCP peer
that does not send an MSS option in its SYN ACK.
How to fix
This problem can be fixed by ensuring that cwnd is initialized
upon receipt of a SYN ACK, even if the SYN ACK does not contain an
MSS option.
2.4.
Name of Problem
Inconsistent retransmission
Classification
Reliability
Description
If, for a given sequence number, a sending TCP retransmits
different data than previously sent for that sequence number, then
a strong possibility arises that the receiving TCP will
reconstruct a different byte stream than that sent by the sending
application, depending on which instance of the sequence number it
accepts.
Such a sending TCP exhibits "Inconsistent retransmission".
Significance
Critical for all environments.
Implications
Reliable delivery of data is a fundamental property of TCP.
Relevant RFCs
RFC793, section 1.5, discusses the central role of reliability in
TCP operation.
Trace file demonstrating it
Made using tcpdump recording at the receiving TCP (B). No losses
reported by the packet filter.
12:35:53.145503 A > B: FP 90048435:90048461(26)
ack 393464682 win 4096
4500 0042 9644 0000
3006 e4c2 86b1 0401 83f3 010a b2a4 0015
055e 07b3 1773 cb6a 5019 1000 68a9 0000
data starts here>504f 5254 2031 3334 2c31 3737*2c34 2c31
2c31 3738 2c31 3635 0d0a
12:35:53.146479 B > A: R 393464682:393464682(0) win 8192
12:35:53.851714 A > B: FP 90048429:90048463(34)
ack 393464682 win 4096
4500 004a 965b 0000
3006 e4a3 86b1 0401 83f3 010a b2a4 0015
055e 07ad 1773 cb6a 5019 1000 8bd3 0000
data starts here>5041 5356 0d0a 504f 5254 2031 3334 2c31
3737*2c31 3035 2c31 3431 2c34 2c31 3539
0d0a
The sequence numbers shown in this trace are absolute and not
adjusted to reflect the ISN. The 4-digit hex values show a dump
of the packet's IP and TCP headers, as well as payload. A first
sends to B data for 90048435:90048461. The corresponding data
begins with hex words 504f, 5254, etc.
B responds with a RST. Since the recording location was local to
B, it is unknown whether A received the RST.
A then sends 90048429:90048463, which includes six sequence
positions below the earlier transmission, all 26 positions of the
earlier transmission, and two additional sequence positions.
The retransmission disagrees starting just after sequence
90048447, annotated above with a leading '*'. These two bytes
were originally transmitted as hex 2c34 but retransmitted as hex
2c31. Subsequent positions disagree as well.
This behavior has been observed in other traces involving
different hosts. It is unknown how to repeat it.
In this instance, no corruption would occur, since B has already
indicated it will not accept further packets from A.
A second example illustrates a slightly different instance of the
problem. The tracing again was made with tcpdump at the receiving
TCP (D).
22:23:58.645829 C > D: P 185:212(27) ack 565 win 4096
4500 0043 90a3 0000
3306 0734 cbf1 9eef 83f3 010a 0525 0015
a3a2 faba 578c 70a4 5018 1000 9a53 0000
data starts here>504f 5254 2032 3033 2c32 3431 2c31 3538
2c32 3339 2c35 2c34 330d 0a
22:23:58.646805 D > C: . ack 184 win 8192
4500 0028 beeb 0000
3e06 ce06 83f3 010a cbf1 9eef 0015 0525
578c 70a4 a3a2 fab9 5010 2000 342f 0000
22:31:36.532244 C > D: FP 186:213(27) ack 565 win 4096
4500 0043 9435 0000
3306 03a2 cbf1 9eef 83f3 010a 0525 0015
a3a2 fabb 578c 70a4 5019 1000 9a51 0000
data starts here>504f 5254 2032 3033 2c32 3431 2c31 3538
2c32 3339 2c35 2c34 330d 0a
In this trace, sequence numbers are relative. C sends 185:212,
but D only sends an ACK for 184 (so sequence number 184 is
missing). C then sends 186:213. The packet payload is identical
to the previous payload, but the base sequence number is one
higher, resulting in an inconsistent retransmission.
Neither trace exhibits checksum errors.
Trace file demonstrating correct behavior
(Omitted, as presumably correct behavior is obvious.)
References
None known.
How to detect
This problem unfortunately can be very difficult to detect, since
available experience indicates it is quite rare that it is
manifested. No "trigger" has been identified that can be used to
reproduce the problem.
How to fix
In the absence of a known "trigger", we cannot always assess how
to fix the problem.
In one implementation (not the one illustrated above), the problem
manifested itself when (1) the sender received a zero window and
stalled; (2) eventually an ACK arrived that offered a window
larger than that in effect at the time of the stall; (3) the
sender transmitted out of the buffer of data it held at the time
of the stall, but (4) failed to limit this transfer to the buffer
length, instead using the newly advertised (and larger) offered
window. Consequently, in addition to the valid buffer contents,
it sent whatever garbage values followed the end of the buffer.
If it then retransmitted the corresponding sequence numbers, at
that point it sent the correct data, resulting in an inconsistent
retransmission. Note that this instance of the problem reflects a
more general problem, that of initially transmitting incorrect
data.
2.5.
Name of Problem
Failure to retain above-sequence data
Classification
Congestion control, performance
Description
When a TCP receives an "above sequence" segment, meaning one with
a sequence number exceeding RCV.NXT but below RCV.NXT+RCV.WND, it
SHOULD queue the segment for later delivery (RFC1122, 4.2.2.20).
(See RFC793 for the definition of RCV.NXT and RCV.WND.) A TCP
that fails to do so is said to exhibit "Failure to retain above-
sequence data".
It may sometimes be appropriate for a TCP to discard above-
sequence data to reclaim memory. If they do so only rarely, then
we would not consider them to exhibit this problem. Instead, the
particular concern is with TCPs that always discard above-sequence
data.
Significance
In environments prone to packet loss, detrimental to the
performance of both other connections and the connection itself.
Implications
In times of congestion, a failure to retain above-sequence data
will lead to numerous otherwise-unnecessary retransmissions,
aggravating the congestion and potentially reducing performance by
a large factor.
Relevant RFCs
RFC1122 revises RFC793 by upgrading the latter's MAY to a SHOULD
on this issue.
Trace file demonstrating it
Made using tcpdump recording at the receiving TCP. No losses
reported by the packet filter.
B is the TCP sender, A the receiver. A exhibits failure to retain
above sequence-data:
10:38:10.164860 B > A: . 221078:221614(536) ack 1 win 33232 [tos 0x8]
10:38:10.170809 B > A: . 221614:222150(536) ack 1 win 33232 [tos 0x8]
10:38:10.177183 B > A: . 222150:222686(536) ack 1 win 33232 [tos 0x8]
10:38:10.225039 A > B: . ack 222686 win 25800
Here B has sent up to (relative) sequence 222686 in-sequence, and
A accordingly acknowledges.
10:38:10.268131 B > A: . 223222:223758(536) ack 1 win 33232 [tos 0x8]
10:38:10.337995 B > A: . 223758:224294(536) ack 1 win 33232 [tos 0x8]
10:38:10.344065 B > A: . 224294:224830(536) ack 1 win 33232 [tos 0x8]
10:38:10.350169 B > A: . 224830:225366(536) ack 1 win 33232 [tos 0x8]
10:38:10.356362 B > A: . 225366:225902(536) ack 1 win 33232 [tos 0x8]
10:38:10.362445 B > A: . 225902:226438(536) ack 1 win 33232 [tos 0x8]
10:38:10.368579 B > A: . 226438:226974(536) ack 1 win 33232 [tos 0x8]
10:38:10.374732 B > A: . 226974:227510(536) ack 1 win 33232 [tos 0x8]
10:38:10.380825 B > A: . 227510:228046(536) ack 1 win 33232 [tos 0x8]
10:38:10.387027 B > A: . 228046:228582(536) ack 1 win 33232 [tos 0x8]
10:38:10.393053 B > A: . 228582:229118(536) ack 1 win 33232 [tos 0x8]
10:38:10.399193 B > A: . 229118:229654(536) ack 1 win 33232 [tos 0x8]
10:38:10.405356 B > A: . 229654:230190(536) ack 1 win 33232 [tos 0x8]
A now receives 13 additional packets from B. These are above-
sequence because 222686:223222 was dropped. The packets do
however fit within the offered window of 25800. A does not
generate any duplicate ACKs for them.
The trace contributor (V. Paxson) verified that these 13 packets
had valid IP and TCP checksums.
10:38:11.917728 B > A: . 222686:223222(536) ack 1 win 33232 [tos 0x8]
10:38:11.930925 A > B: . ack 223222 win 32232
B times out for 222686:223222 and retransmits it. Upon receiving
it, A only acknowledges 223222. Had it retained the valid above-
sequence packets, it would instead have ack'd 230190.
10:38:12.048438 B > A: . 223222:223758(536) ack 1 win 33232 [tos 0x8]
10:38:12.054397 B > A: . 223758:224294(536) ack 1 win 33232 [tos 0x8]
10:38:12.068029 A > B: . ack 224294 win 31696
B retransmits two more packets, and A only acknowledges them.
This pattern continues as B retransmits the entire set of
previously-received packets.
A second trace confirmed that the problem is repeatable.
Trace file demonstrating correct behavior
Made using tcpdump recording at the receiving TCP (C). No losses
reported by the packet filter.
09:11:25.790417 D > C: . 33793:34305(512) ack 1 win 61440
09:11:25.791393 D > C: . 34305:34817(512) ack 1 win 61440
09:11:25.792369 D > C: . 34817:35329(512) ack 1 win 61440
09:11:25.792369 D > C: . 35329:35841(512) ack 1 win 61440
09:11:25.793345 D > C: . 36353:36865(512) ack 1 win 61440
09:11:25.794321 C > D: . ack 35841 win 59904
A sequence hole occurs because 35841:36353 has been dropped.
09:11:25.794321 D > C: . 36865:37377(512) ack 1 win 61440
09:11:25.794321 C > D: . ack 35841 win 59904
09:11:25.795297 D > C: . 37377:37889(512) ack 1 win 61440
09:11:25.795297 C > D: . ack 35841 win 59904
09:11:25.796273 C > D: . ack 35841 win 61440
09:11:25.798225 D > C: . 37889:38401(512) ack 1 win 61440
09:11:25.799201 C > D: . ack 35841 win 61440
09:11:25.807009 D > C: . 38401:38913(512) ack 1 win 61440
09:11:25.807009 C > D: . ack 35841 win 61440
(many additional lines omitted)
09:11:25.884113 D > C: . 52737:53249(512) ack 1 win 61440
09:11:25.884113 C > D: . ack 35841 win 61440
Each additional, above-sequence packet C receives from D elicits a
duplicate ACK for 35841.
09:11:25.887041 D > C: . 35841:36353(512) ack 1 win 61440
09:11:25.887041 C > D: . ack 53249 win 44032
D retransmits 35841:36353 and C acknowledges receipt of data all
the way up to 53249.
References
This problem is documented in [Paxson97].
How to detect
Packet loss is common enough in the Internet that generally it is
not difficult to find an Internet path that will result in some
above-sequence packets arriving. A TCP that exhibits "Failure to
retain ..." may not generate duplicate ACKs for these packets.
However, some TCPs that do retain above-sequence data also do not
generate duplicate ACKs, so failure to do so does not definitively
identify the problem. Instead, the key observation is whether
upon retransmission of the dropped packet, data that was
previously above-sequence is acknowledged.
Two considerations in detecting this problem using a packet trace
are that it is easiest to do so with a trace made at the TCP
receiver, in order to unambiguously determine which packets
arrived successfully, and that such packets may still be correctly
discarded if they arrive with checksum errors. The latter can be
tested by capturing the entire packet contents and performing the
IP and TCP checksum algorithms to verify their integrity; or by
confirming that the packets arrive with the same checksum and
contents as that with which they were sent, with a presumption
that the sending TCP correctly calculates checksums for the
packets it transmits.
It is considerably easier to verify that an implementation does
NOT exhibit this problem. This can be done by recording a trace
at the data sender, and observing that sometimes after a
retransmission the receiver acknowledges a higher sequence number
than just that which was retransmitted.
How to fix
If the root problem is that the implementation lacks buffer, then
then unfortunately this requires significant work to fix.
However, doing so is important, for reasons outlined above.
2.6.
Name of Problem
Extra additive constant in congestion avoidance
Classification
Congestion control / performance
Description
RFC1122 section 4.2.2.15 states that TCP MUST implement
Jacobson's "congestion avoidance" algorithm [Jacobson88], which
calls for increasing the congestion window, cwnd, by:
MSS * MSS / cwnd
for each ACK received for new data [RFC2001]. This has the effect
of increasing cwnd by approximately one segment in each round trip
time.
Some TCP implementations add an additional fraction of a segment
(typically MSS/8) to cwnd for each ACK received for new data
[Stevens94, Wright95]:
(MSS * MSS / cwnd) + MSS/8
These implementations exhibit "Extra additive constant in
congestion avoidance".
Significance
May be detrimental to performance even in completely uncongested
environments (see Implications).
In congested environments, may also be detrimental to the
performance of other connections.
Implications
The extra additive term allows a TCP to more aggressively open its
congestion window (quadratic rather than linear increase). For
congested networks, this can increase the loss rate experienced by
all connections sharing a bottleneck with the aggressive TCP.
However, even for completely uncongested networks, the extra
additive term can lead to diminished performance, as follows. In
congestion avoidance, a TCP sender probes the network path to
determine its available capacity, which often equates to the
number of buffers available at a bottleneck link. With linear
congestion avoidance, the TCP only probes for sufficient capacity
(buffer) to hold one extra packet per RTT.
Thus, when it exceeds the available capacity, generally only one
packet will be lost (since on the previous RTT it already found
that the path could sustain a window with one less packet in
flight). If the congestion window is sufficiently large, then the
TCP will recover from this single loss using fast retransmission
and avoid an expensive (in terms of performance) retransmission
timeout.
However, when the additional additive term is used, then cwnd can
increase by more than one packet per RTT, in which case the TCP
probes more aggressively. If in the previous RTT it had reached
the available capacity of the path, then the excess due to the
extra increase will again be lost, but now this will result in
multiple losses from the flight instead of a single loss. TCPs
that do not utilize SACK [RFC2018] generally will not recover from
multiple losses without incurring a retransmission timeout
[Fall96,Hoe96], significantly diminishing performance.
Relevant RFCs
RFC1122 requires use of the "congestion avoidance" algorithm.
RFC2001 outlines the fast retransmit/fast recovery algorithms.
RFC2018 discusses the SACK option.
Trace file demonstrating it
Recorded using tcpdump running on the same FDDI LAN as host A.
Host A is the sender and host B is the receiver. The connection
establishment specified an MSS of 4,312 bytes and a window scale
factor of 4. We omit the establishment and the first 2.5 MB of
data transfer, as the problem is best demonstrated when the window
has grown to a large value. At the beginning of the trace
excerpt, the congestion window is 31 packets. The connection is
never receiver-window limited, so we omit window advertisements
from the trace for clarity.
11:42:07.697951 B > A: . ack 2383006
11:42:07.699388 A > B: . 2508054:2512366(4312)
11:42:07.699962 A > B: . 2512366:2516678(4312)
11:42:07.700012 B > A: . ack 2391630
11:42:07.701081 A > B: . 2516678:2520990(4312)
11:42:07.701656 A > B: . 2520990:2525302(4312)
11:42:07.701739 B > A: . ack 2400254
11:42:07.702685 A > B: . 2525302:2529614(4312)
11:42:07.703257 A > B: . 2529614:2533926(4312)
11:42:07.703295 B > A: . ack 2408878
11:42:07.704414 A > B: . 2533926:2538238(4312)
11:42:07.704989 A > B: . 2538238:2542550(4312)
11:42:07.705040 B > A: . ack 2417502
11:42:07.705935 A > B: . 2542550:2546862(4312)
11:42:07.706506 A > B: . 2546862:2551174(4312)
11:42:07.706544 B > A: . ack 2426126
11:42:07.707480 A > B: . 2551174:2555486(4312)
11:42:07.708051 A > B: . 2555486:2559798(4312)
11:42:07.708088 B > A: . ack 2434750
11:42:07.709030 A > B: . 2559798:2564110(4312)
11:42:07.709604 A > B: . 2564110:2568422(4312)
11:42:07.710175 A > B: . 2568422:2572734(4312) *
11:42:07.710215 B > A: . ack 2443374
11:42:07.710799 A > B: . 2572734:2577046(4312)
11:42:07.711368 A > B: . 2577046:2581358(4312)
11:42:07.711405 B > A: . ack 2451998
11:42:07.712323 A > B: . 2581358:2585670(4312)
11:42:07.712898 A > B: . 2585670:2589982(4312)
11:42:07.712938 B > A: . ack 2460622
11:42:07.713926 A > B: . 2589982:2594294(4312)
11:42:07.714501 A > B: . 2594294:2598606(4312)
11:42:07.714547 B > A: . ack 2469246
11:42:07.715747 A > B: . 2598606:2602918(4312)
11:42:07.716287 A > B: . 2602918:2607230(4312)
11:42:07.716328 B > A: . ack 2477870
11:42:07.717146 A > B: . 2607230:2611542(4312)
11:42:07.717717 A > B: . 2611542:2615854(4312)
11:42:07.717762 B > A: . ack 2486494
11:42:07.718754 A > B: . 2615854:2620166(4312)
11:42:07.719331 A > B: . 2620166:2624478(4312)
11:42:07.719906 A > B: . 2624478:2628790(4312) **
11:42:07.719958 B > A: . ack 2495118
11:42:07.720500 A > B: . 2628790:2633102(4312)
11:42:07.721080 A > B: . 2633102:2637414(4312)
11:42:07.721739 B > A: . ack 2503742
11:42:07.722348 A > B: . 2637414:2641726(4312)
11:42:07.722918 A > B: . 2641726:2646038(4312)
11:42:07.769248 B > A: . ack 2512366
The receiver's acknowledgment policy is one ACK per two packets
received. Thus, for each ACK arriving at host A, two new packets
are sent, except when cwnd increases due to congestion avoidance,
in which case three new packets are sent.
With an ack-every-two-packets policy, cwnd should only increase
one MSS per 2 RTT. However, at the point marked "*" the window
increases after 7 ACKs have arrived, and then again at "**" after
6 more ACKs.
While we do not have space to show the effect, this trace suffered
from repeated timeout retransmissions due to multiple packet
losses during a single RTT.
Trace file demonstrating correct behavior
Made using the same host and tracing setup as above, except now
A's TCP has been modified to remove the MSS/8 additive constant.
Tcpdump reported 77 packet drops; the excerpt below is fully
self-consistent so it is unlikely that any of these occurred
during the excerpt.
We again begin when cwnd is 31 packets (this occurs significantly
later in the trace, because the congestion avoidance is now less
aggressive with opening the window).
14:22:21.236757 B > A: . ack 5194679
14:22:21.238192 A > B: . 5319727:5324039(4312)
14:22:21.238770 A > B: . 5324039:5328351(4312)
14:22:21.238821 B > A: . ack 5203303
14:22:21.240158 A > B: . 5328351:5332663(4312)
14:22:21.240738 A > B: . 5332663:5336975(4312)
14:22:21.270422 B > A: . ack 5211927
14:22:21.271883 A > B: . 5336975:5341287(4312)
14:22:21.272458 A > B: . 5341287:5345599(4312)
14:22:21.279099 B > A: . ack 5220551
14:22:21.280539 A > B: . 5345599:5349911(4312)
14:22:21.281118 A > B: . 5349911:5354223(4312)
14:22:21.281183 B > A: . ack 5229175
14:22:21.282348 A > B: . 5354223:5358535(4312)
14:22:21.283029 A > B: . 5358535:5362847(4312)
14:22:21.283089 B > A: . ack 5237799
14:22:21.284213 A > B: . 5362847:5367159(4312)
14:22:21.284779 A > B: . 5367159:5371471(4312)
14:22:21.285976 B > A: . ack 5246423
14:22:21.287465 A > B: . 5371471:5375783(4312)
14:22:21.288036 A > B: . 5375783:5380095(4312)
14:22:21.288073 B > A: . ack 5255047
14:22:21.289155 A > B: . 5380095:5384407(4312)
14:22:21.289725 A > B: . 5384407:5388719(4312)
14:22:21.289762 B > A: . ack 5263671
14:22:21.291090 A > B: . 5388719:5393031(4312)
14:22:21.291662 A > B: . 5393031:5397343(4312)
14:22:21.291701 B > A: . ack 5272295
14:22:21.292870 A > B: . 5397343:5401655(4312)
14:22:21.293441 A > B: . 5401655:5405967(4312)
14:22:21.293481 B > A: . ack 5280919
14:22:21.294476 A > B: . 5405967:5410279(4312)
14:22:21.295053 A > B: . 5410279:5414591(4312)
14:22:21.295106 B > A: . ack 5289543
14:22:21.296306 A > B: . 5414591:5418903(4312)
14:22:21.296878 A > B: . 5418903:5423215(4312)
14:22:21.296917 B > A: . ack 5298167
14:22:21.297716 A > B: . 5423215:5427527(4312)
14:22:21.298285 A > B: . 5427527:5431839(4312)
14:22:21.298324 B > A: . ack 5306791
14:22:21.299413 A > B: . 5431839:5436151(4312)
14:22:21.299986 A > B: . 5436151:5440463(4312)
14:22:21.303696 B > A: . ack 5315415
14:22:21.305177 A > B: . 5440463:5444775(4312)
14:22:21.305755 A > B: . 5444775:5449087(4312)
14:22:21.308032 B > A: . ack 5324039
14:22:21.309525 A > B: . 5449087:5453399(4312)
14:22:21.310101 A > B: . 5453399:5457711(4312)
14:22:21.310144 B > A: . ack 5332663 ***
14:22:21.311615 A > B: . 5457711:5462023(4312)
14:22:21.312198 A > B: . 5462023:5466335(4312)
14:22:21.341876 B > A: . ack 5341287
14:22:21.343451 A > B: . 5466335:5470647(4312)
14:22:21.343985 A > B: . 5470647:5474959(4312)
14:22:21.350304 B > A: . ack 5349911
14:22:21.351852 A > B: . 5474959:5479271(4312)
14:22:21.352430 A > B: . 5479271:5483583(4312)
14:22:21.352484 B > A: . ack 5358535
14:22:21.353574 A > B: . 5483583:5487895(4312)
14:22:21.354149 A > B: . 5487895:5492207(4312)
14:22:21.354205 B > A: . ack 5367159
14:22:21.355467 A > B: . 5492207:5496519(4312)
14:22:21.356039 A > B: . 5496519:5500831(4312)
14:22:21.357361 B > A: . ack 5375783
14:22:21.358855 A > B: . 5500831:5505143(4312)
14:22:21.359424 A > B: . 5505143:5509455(4312)
14:22:21.359465 B > A: . ack 5384407
14:22:21.360605 A > B: . 5509455:5513767(4312)
14:22:21.361181 A > B: . 5513767:5518079(4312)
14:22:21.361225 B > A: . ack 5393031
14:22:21.362485 A > B: . 5518079:5522391(4312)
14:22:21.363057 A > B: . 5522391:5526703(4312)
14:22:21.363096 B > A: . ack 5401655
14:22:21.364236 A > B: . 5526703:5531015(4312)
14:22:21.364810 A > B: . 5531015:5535327(4312)
14:22:21.364867 B > A: . ack 5410279
14:22:21.365819 A > B: . 5535327:5539639(4312)
14:22:21.366386 A > B: . 5539639:5543951(4312)
14:22:21.366427 B > A: . ack 5418903
14:22:21.367586 A > B: . 5543951:5548263(4312)
14:22:21.368158 A > B: . 5548263:5552575(4312)
14:22:21.368199 B > A: . ack 5427527
14:22:21.369189 A > B: . 5552575:5556887(4312)
14:22:21.369758 A > B: . 5556887:5561199(4312)
14:22:21.369803 B > A: . ack 5436151
14:22:21.370814 A > B: . 5561199:5565511(4312)
14:22:21.371398 A > B: . 5565511:5569823(4312)
14:22:21.375159 B > A: . ack 5444775
14:22:21.376658 A > B: . 5569823:5574135(4312)
14:22:21.377235 A > B: . 5574135:5578447(4312)
14:22:21.379303 B > A: . ack 5453399
14:22:21.380802 A > B: . 5578447:5582759(4312)
14:22:21.381377 A > B: . 5582759:5587071(4312)
14:22:21.381947 A > B: . 5587071:5591383(4312) ****
"***" marks the end of the first round trip. Note that cwnd did
not increase (as evidenced by each ACK eliciting two new data
packets). Only at "****", which comes near the end of the second
round trip, does cwnd increase by one packet.
This trace did not suffer any timeout retransmissions. It
transferred the same amount of data as the first trace in about
half as much time. This difference is repeatable between hosts A
and B.
References
[Stevens94] and [Wright95] discuss this problem. The problem of
Reno TCP failing to recover from multiple losses except via a
retransmission timeout is discussed in [Fall96,Hoe96].
How to detect
If source code is available, that is generally the easiest way to
detect this problem. Search for each modification to the cwnd
variable; (at least) one of these will be for congestion
avoidance, and inspection of the related code should immediately
identify the problem if present.
The problem can also be detected by closely examining packet
traces taken near the sender. During congestion avoidance, cwnd
will increase by an additional segment upon the receipt of
(typically) eight acknowledgements without a loss. This increase
is in addition to the one segment increase per round trip time (or
two round trip times if the receiver is using delayed ACKs).
Furthermore, graphs of the sequence number vs. time, taken from
packet traces, are normally linear during congestion avoidance.
When viewing packet traces of transfers from senders exhibiting
this problem, the graphs appear quadratic instead of linear.
Finally, the traces will show that, with sufficiently large
windows, nearly every loss event results in a timeout.
How to fix
This problem may be corrected by removing the "+ MSS/8" term from
the congestion avoidance code that increases cwnd each time an ACK
of new data is received.
2.7.
Name of Problem
Initial RTO too low
Classification
Performance
Description
When a TCP first begins transmitting data, it lacks the RTT
measurements necessary to have computed an adaptive retransmission
timeout (RTO). RFC1122, 4.2.3.1, states that a TCP SHOULD
initialize RTO to 3 seconds. A TCP that uses a lower value
exhibits "Initial RTO too low".
Significance
In environments with large RTTs (where "large" means any value
larger than the initial RTO), TCPs will experience very poor
performance.
Implications
Whenever RTO < RTT, very poor performance can result as packets
are unnecessarily retransmitted (because RTO will expire before an
ACK for the packet can arrive) and the connection enters slow
start and congestion avoidance. Generally, the algorithms for