As per Relevance of the word congestion, we have this rfc below:
Network Working Group V.
Request for Comments: 2525
Category: Informational ACIRI /
M.
NASA Glenn Research Center/Sterling
S.
Real-Time Computing
W.
Xerox
J.
NASA Glenn Research
I.
Spider Software Ltd
K.
NASA Ames Research Center/
J.
Pittsburgh Supercomputing
B.
Process Software
March 1999
Known TCP Implementation
Status of this
This memo provides information for the Internet community. It
not specify an Internet standard of any kind. Distribution of
memo is unlimited
Copyright
Copyright (C) The Internet Society (1999). All Rights Reserved
Table of
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
Paxson, et. al. Informational [Page 1]
RFC 2525 TCP Implementation Problems March 1999
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.
This memo catalogs a number of known TCP implementation problems
The goal in doing so is to improve conditions in the
Internet by enhancing the quality of current TCP/IP implementations
It is hoped that both performance and correctness issues can
resolved by making implementors aware of the problems and
solutions. In the long term, it is hoped that this will provide
reduction in unnecessary traffic on the network, the rate
connection failures due to protocol errors, and load on
servers due to time spent processing both unsuccessful
and retransmitted data. This will help to ensure the stability
the global Internet
Each problem is defined as follows
Name of
The name associated with the problem. In this memo, the name
given as a subsection heading
One or more problem categories for which the problem
classified: "congestion control", "performance", "reliability",
"resource management".
A definition of the problem, succinct but including
background material
A brief summary of the sorts of environments for which the
is significant
Paxson, et. al. Informational [Page 2]
RFC 2525 TCP Implementation Problems March 1999
Why the problem is viewed as a problem
Relevant
The RFCs defining the TCP specification with which the
conflicts. These RFCs often qualify behavior using terms such
MUST, SHOULD, MAY, and others written capitalized. See RFC 2119
for the exact interpretation of these terms
Trace file demonstrating the
One or more ASCII trace files demonstrating the problem,
applicable
Trace file demonstrating correct
One or more examples of how correct behavior appears in a trace
if applicable
References that further discuss the problem
How to
How to test an implementation to see if it exhibits the problem
This discussion may include difficulties and subtleties
with causing the problem to manifest itself, and with
traces to detect the presence of the problem (if applicable).
How to
For known causes of the problem, how to correct
implementation
2. Known implementation
2.1.
Name of
No initial slow
Congestion
When a TCP begins transmitting data, it is required by RFC 1122,
4.2.2.15, to engage in a "slow start" by initializing
congestion window, cwnd, to one packet (one segment of the
size). (Note that an experimental change to TCP, documented
[RFC2414], allows an initial value somewhat larger than
packet.) It subsequently increases cwnd by one packet for
ACK it receives for new data. The minimum of cwnd and
Paxson, et. al. Informational [Page 3]
RFC 2525 TCP Implementation Problems March 1999
receiver's advertised window bounds the highest sequence
the TCP can transmit. A TCP that fails to initialize
increment cwnd in this fashion exhibits "No initial slow start".
In congested environments, detrimental to the performance of
connections, and possibly to the connection itself
A TCP failing to slow start when beginning a connection results
traffic bursts that can stress the network, leading to
queueing delays and packet loss
Implementations exhibiting this problem might do so because
suffer from the general problem of not including the
congestion window. These implementations will also suffer
"No slow start after retransmission timeout".
There are different shades of "No initial slow start". From
perspective of stressing the network, the worst is a
that simply always sends based on the receiver's
window, with no notion of a separate congestion window.
form is described in "Uninitialized CWND" below
Relevant
RFC 1122 requires use of slow start. RFC 2001 gives the
of slow start
Trace file demonstrating
Made using tcpdump [Jacobson89] recording at the
responder. No losses reported by the packet filter
10:40:42.244503 B > A: S 1168512000:1168512000(0) win 32768
(DF) [tos 0x8]
10:40:42.259908 A > B: S 3688169472:3688169472(0)
ack 1168512001 win 32768
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]
Paxson, et. al. Informational [Page 4]
RFC 2525 TCP Implementation Problems March 1999
After the third packet, the connection is established. A,
connection responder, begins transmitting to B, the
initiator. Host A quickly sends 6 packets comprising 7812 bytes
even though the SYN exchange agreed upon an MSS of 1460
(implying an initial congestion window of 1 segment corresponds
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
trace is not a measurement error (slow start really occurring
the corresponding ACKs having been dropped by the packet filter).
A second trace confirmed that the problem is repeatable
Trace file demonstrating correct
Made using tcpdump recording at the connection originator.
losses reported by the packet filter
12:35:31.914050 C > D: S 1448571845:1448571845(0)
win 4380
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
This problem is documented in [Paxson97].
How to
For implementations always manifesting this problem, it shows
immediately in a packet trace or a sequence plot, as
above
Paxson, et. al. Informational [Page 5]
RFC 2525 TCP Implementation Problems March 1999
How to
If the root problem is that the implementation lacks a notion of
congestion window, then unfortunately this requires
work to fix. However, doing so is important, as
implementations also exhibit "No slow start after
timeout".
2.2.
Name of
No slow start after retransmission
Congestion
When a TCP experiences a retransmission timeout, it is required
RFC 1122, 4.2.2.15, to engage in "slow start" by initializing
congestion window, cwnd, to one packet (one segment of the
size). It subsequently increases cwnd by one packet for each
it receives for new data until it reaches the "
avoidance" threshold, ssthresh, at which point the
avoidance algorithm for updating the window takes over. A
that fails to enter slow start upon a timeout exhibits "No
start after retransmission timeout".
In congested environments, severely detrimental to the
of other connections, and also the connection itself
Entering slow start upon timeout forms one of the cornerstones
Internet congestion stability, as outlined in [Jacobson88].
TCPs fail to do so, the network becomes at risk of
"congestion collapse" [RFC896].
Relevant
RFC 1122 requires use of slow start after loss. RFC 2001
the specifics of how to implement slow start. RFC 896
congestion collapse
The retransmission timeout discussed here should not be
with the separate "fast recovery" retransmission
discussed in RFC 2001.
Trace file demonstrating
Made using tcpdump recording at the sending TCP (A). No
reported by the packet filter
Paxson, et. al. Informational [Page 6]
RFC 2525 TCP Implementation Problems March 1999
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
after receiving the ACK, A transmits the packet after the
point, 357125:358585. 640 msec after this transmission,
retransmits 357125:358585, in an apparent retransmission timeout
At this point, A's cwnd should be one MSS, or 1460 bytes, as
enters slow start. The trace is consistent with this possibility
B replies with an ACK of 364425, indicating that A has filled
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
inconsistent with slow start
A second trace confirmed that the problem is repeatable
Trace file demonstrating correct
Made using tcpdump recording at the sending TCP (C). No
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
Paxson, et. al. Informational [Page 7]
RFC 2525 TCP Implementation Problems March 1999
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
in response to D's ACKs for 461825, because the first
already reached the advertised window limit of 4096 bytes
461825. 600 msec after transmitting the first packet,
retransmits 461825:462337, presumably due to a timeout.
congestion window is now MSS (512 bytes).
D acks 465921, indicating that C's retransmission filled
sequence hole. This ACK advances C's cwnd from 512 to 1024.
shortly after, D acks 465921 again in order to update the
window from 2048 to 4096. This ACK does not advance cwnd since
is not for new data. Very shortly after, C responds to the
enlarged window by transmitting two packets. D acks both
advancing cwnd from 1024 to 1536. C in turn transmits
packets
This problem is documented in [Paxson97].
How to
Packet loss is common enough in the Internet that generally it
not difficult to find an Internet path that will
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"
described in RFC 2001. In a packet trace, the signature of
recovery is that the packet retransmission occurs in response
the receipt of three duplicate ACKs, and subsequent duplicate
may lead to the transmission of new data, above both the ack
and the highest sequence transmitted so far. An absence of
duplicate ACKs prior to retransmission suffices to
between timeout and fast recovery retransmissions. In the face
only observing fast recovery retransmissions, generally it is
difficult to repeat the data transfer until observing a
retransmission
Paxson, et. al. Informational [Page 8]
RFC 2525 TCP Implementation Problems March 1999
Once armed with a trace exhibiting a timeout retransmission
determining whether the TCP follows slow start is done
computing the correct progression of cwnd and comparing it to
amount of data transmitted by the TCP subsequent to the
retransmission
How to
If the root problem is that the implementation lacks a notion of
congestion window, then unfortunately this requires
work to fix. However, doing so is critical, for reasons
above
2.3.
Name of
Uninitialized
Congestion
As described above for "No initial slow start", when a
connection begins cwnd is initialized to one segment (or perhaps
few segments, if experimenting with [RFC2414]). One
form of "No initial slow start", worth separate mention as the
is fairly widely deployed, is "Uninitialized CWND". That is
while the TCP implements the proper slow start mechanism, it
to initialize cwnd properly, so slow start in fact fails to occur
One way the bug can occur is if, during the
establishment handshake, the SYN ACK packet arrives without an
option. The faulty implementation uses receipt of the MSS
to initialize cwnd to one segment; if the option fails to arrive
then cwnd is instead initialized to a very large value
In congested environments, detrimental to the performance of
connections, and likely to the connection itself. The burst
be so large (see below) that it has deleterious effects even
uncongested environments
A TCP exhibiting this behavior is stressing the network with
large burst of packets, which can cause loss in the network
Relevant
RFC 1122 requires use of slow start. RFC 2001 gives the
of slow start
Paxson, et. al. Informational [Page 9]
RFC 2525 TCP Implementation Problems March 1999
Trace file demonstrating
This trace was made using tcpdump running on host A. Host A
the sender and host B is the receiver. The advertised window
timestamp options have been omitted for clarity, except for
first segment sent by host A. Note that A sends an MSS option
its initial SYN but B does not include one in its reply
16:56:02.226937 A > B: S 237585307:237585307(0) win 8192
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
network, before duplicate ACKs on the first segment cause
retransmission to occur. Since host A did not wait for the ACK
the first segment before sending additional segments, it
exhibiting "Uninitialized CWND
Trace file demonstrating correct
See the example for "No initial slow start".
This problem is documented in [Paxson97].
How to
This problem can be detected by examining a packet trace
at either the sender or the receiver. However, the bug can
difficult to induce because it requires finding a remote TCP
that does not send an MSS option in its SYN ACK
How to
This problem can be fixed by ensuring that cwnd is
upon receipt of a SYN ACK, even if the SYN ACK does not contain
MSS option
Paxson, et. al. Informational [Page 10]
RFC 2525 TCP Implementation Problems March 1999
2.4.
Name of
Inconsistent
If, for a given sequence number, a sending TCP
different data than previously sent for that sequence number,
a strong possibility arises that the receiving TCP
reconstruct a different byte stream than that sent by the
application, depending on which instance of the sequence number
accepts
Such a sending TCP exhibits "Inconsistent retransmission".
Critical for all environments
Reliable delivery of data is a fundamental property of TCP
Relevant
RFC 793, section 1.5, discusses the central role of reliability
TCP operation
Trace file demonstrating
Made using tcpdump recording at the receiving TCP (B). No
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 0d0
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
0d0
Paxson, et. al. Informational [Page 11]
RFC 2525 TCP Implementation Problems March 1999
The sequence numbers shown in this trace are absolute and
adjusted to reflect the ISN. The 4-digit hex values show a
of the packet's IP and TCP headers, as well as payload. A
sends to B data for 90048435:90048461. The corresponding
begins with hex words 504f, 5254, etc
B responds with a RST. Since the recording location was local
B, it is unknown whether A received the RST
A then sends 90048429:90048463, which includes six
positions below the earlier transmission, all 26 positions of
earlier transmission, and two additional sequence positions
The retransmission disagrees starting just after
90048447, annotated above with a leading '*'. These two
were originally transmitted as hex 2c34 but retransmitted as
2c31. Subsequent positions disagree as well
This behavior has been observed in other traces
different hosts. It is unknown how to repeat it
In this instance, no corruption would occur, since B has
indicated it will not accept further packets from A
A second example illustrates a slightly different instance of
problem. The tracing again was made with tcpdump at the
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 0
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 0
Paxson, et. al. Informational [Page 12]
RFC 2525 TCP Implementation Problems March 1999
In this trace, sequence numbers are relative. C sends 185:212,
but D only sends an ACK for 184 (so sequence number 184
missing). C then sends 186:213. The packet payload is
to the previous payload, but the base sequence number is
higher, resulting in an inconsistent retransmission
Neither trace exhibits checksum errors
Trace file demonstrating correct
(Omitted, as presumably correct behavior is obvious.)
None known
How to
This problem unfortunately can be very difficult to detect,
available experience indicates it is quite rare that it
manifested. No "trigger" has been identified that can be used
reproduce the problem
How to
In the absence of a known "trigger", we cannot always assess
to fix the problem
In one implementation (not the one illustrated above), the
manifested itself when (1) the sender received a zero window
stalled; (2) eventually an ACK arrived that offered a
larger than that in effect at the time of the stall; (3)
sender transmitted out of the buffer of data it held at the
of the stall, but (4) failed to limit this transfer to the
length, instead using the newly advertised (and larger)
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,
that point it sent the correct data, resulting in an
retransmission. Note that this instance of the problem reflects
more general problem, that of initially transmitting
data
2.5.
Name of
Failure to retain above-sequence
Congestion control,
Paxson, et. al. Informational [Page 13]
RFC 2525 TCP Implementation Problems March 1999
When a TCP receives an "above sequence" segment, meaning one
a sequence number exceeding RCV.NXT but below RCV.NXT+RCV.WND,
SHOULD queue the segment for later delivery (RFC 1122, 4.2.2.20).
(See RFC 793 for the definition of RCV.NXT and RCV.WND.) A
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,
we would not consider them to exhibit this problem. Instead,
particular concern is with TCPs that always discard above-
data
In environments prone to packet loss, detrimental to
performance of both other connections and the connection itself
In times of congestion, a failure to retain above-sequence
will lead to numerous otherwise-unnecessary retransmissions
aggravating the congestion and potentially reducing performance
a large factor
Relevant
RFC 1122 revises RFC 793 by upgrading the latter's MAY to a
on this issue
Trace file demonstrating
Made using tcpdump recording at the receiving TCP. No
reported by the packet filter
B is the TCP sender, A the receiver. A exhibits failure to
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,
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]
Paxson, et. al. Informational [Page 14]
RFC 2525 TCP Implementation Problems March 1999
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
however fit within the offered window of 25800. A does
generate any duplicate ACKs for them
The trace contributor (V. Paxson) verified that these 13
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
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
previously-received packets
A second trace confirmed that the problem is repeatable
Trace file demonstrating correct
Made using tcpdump recording at the receiving TCP (C). No
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
Paxson, et. al. Informational [Page 15]
RFC 2525 TCP Implementation Problems March 1999
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
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
the way up to 53249.
This problem is documented in [Paxson97].
How to
Packet loss is common enough in the Internet that generally it
not difficult to find an Internet path that will result in
above-sequence packets arriving. A TCP that exhibits "Failure
retain ..." may not generate duplicate ACKs for these packets
However, some TCPs that do retain above-sequence data also do
generate duplicate ACKs, so failure to do so does not
identify the problem. Instead, the key observation is
upon retransmission of the dropped packet, data that
previously above-sequence is acknowledged
Two considerations in detecting this problem using a packet
are that it is easiest to do so with a trace made at the
receiver, in order to unambiguously determine which
arrived successfully, and that such packets may still be
discarded if they arrive with checksum errors. The latter can
tested by capturing the entire packet contents and performing
IP and TCP checksum algorithms to verify their integrity; or
confirming that the packets arrive with the same checksum
contents as that with which they were sent, with a
that the sending TCP correctly calculates checksums for
packets it transmits
Paxson, et. al. Informational [Page 16]
RFC 2525 TCP Implementation Problems March 1999
It is considerably easier to verify that an implementation
NOT exhibit this problem. This can be done by recording a
at the data sender, and observing that sometimes after
retransmission the receiver acknowledges a higher sequence
than just that which was retransmitted
How to
If the root problem is that the implementation lacks buffer,
then unfortunately this requires significant work to fix
However, doing so is important, for reasons outlined above
2.6.
Name of
Extra additive constant in congestion
Congestion control /
RFC 1122 section 4.2.2.15 states that TCP MUST
Jacobson's "congestion avoidance" algorithm [Jacobson88],
calls for increasing the congestion window, cwnd, by
MSS * MSS /
for each ACK received for new data [RFC2001]. This has the
of increasing cwnd by approximately one segment in each round
time
Some TCP implementations add an additional fraction of a
(typically MSS/8) to cwnd for each ACK received for new
[Stevens94, Wright95]:
(MSS * MSS / cwnd) + MSS/8
These implementations exhibit "Extra additive constant
congestion avoidance".
May be detrimental to performance even in completely
environments (see Implications).
In congested environments, may also be detrimental to
performance of other connections
Paxson, et. al. Informational [Page 17]
RFC 2525 TCP Implementation Problems March 1999
The extra additive term allows a TCP to more aggressively open
congestion window (quadratic rather than linear increase).
congested networks, this can increase the loss rate experienced
all connections sharing a bottleneck with the aggressive TCP
However, even for completely uncongested networks, the
additive term can lead to diminished performance, as follows.
congestion avoidance, a TCP sender probes the network path
determine its available capacity, which often equates to
number of buffers available at a bottleneck link. With
congestion avoidance, the TCP only probes for sufficient
(buffer) to hold one extra packet per RTT
Thus, when it exceeds the available capacity, generally only
packet will be lost (since on the previous RTT it already
that the path could sustain a window with one less packet
flight). If the congestion window is sufficiently large, then
TCP will recover from this single loss using fast
and avoid an expensive (in terms of performance)
timeout
However, when the additional additive term is used, then cwnd
increase by more than one packet per RTT, in which case the
probes more aggressively. If in the previous RTT it had
the available capacity of the path, then the excess due to
extra increase will again be lost, but now this will result
multiple losses from the flight instead of a single loss.
that do not utilize SACK [RFC2018] generally will not recover
multiple losses without incurring a retransmission
[Fall96,Hoe96], significantly diminishing performance
Relevant
RFC 1122 requires use of the "congestion avoidance" algorithm
RFC 2001 outlines the fast retransmit/fast recovery algorithms
RFC 2018 discusses the SACK option
Trace file demonstrating
Recorded using tcpdump running on the same FDDI LAN as host A
Host A is the sender and host B is the receiver. The
establishment specified an MSS of 4,312 bytes and a window
factor of 4. We omit the establishment and the first 2.5 MB
data transfer, as the problem is best demonstrated when the
has grown to a large value. At the beginning of the
excerpt, the congestion window is 31 packets. The connection
never receiver-window limited, so we omit window
from the trace for clarity
Paxson, et. al. Informational [Page 18]
RFC 2525 TCP Implementation Problems March 1999
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)
Paxson, et. al. Informational [Page 19]
RFC 2525 TCP Implementation Problems March 1999
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
received. Thus, for each ACK arriving at host A, two new
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
one MSS per 2 RTT. However, at the point marked "*" the
increases after 7 ACKs have arrived, and then again at "**"
6 more ACKs
While we do not have space to show the effect, this trace
from repeated timeout retransmissions due to multiple
losses during a single RTT
Trace file demonstrating correct
Made using the same host and tracing setup as above, except
A's TCP has been modified to remove the MSS/8 additive constant
Tcpdump reported 77 packet drops; the excerpt below is
self-consistent so it is unlikely that any of these
during the excerpt
We again begin when cwnd is 31 packets (this occurs
later in the trace, because the congestion avoidance is now
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)
Paxson, et. al. Informational [Page 20]
RFC 2525 TCP Implementation Problems March 1999
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
Paxson, et. al. Informational [Page 21]
RFC 2525 TCP Implementation Problems March 1999
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
not increase (as evidenced by each ACK eliciting two new
packets). Only at "****", which comes near the end of the
round trip, does cwnd increase by one packet
This trace did not suffer any timeout retransmissions.
transferred the same amount of data as the first trace in
half as much time. This difference is repeatable between hosts
and B
[Stevens94] and [Wright95] discuss this problem. The problem
Reno TCP failing to recover from multiple losses except via
retransmission timeout is discussed in [Fall96,Hoe96].
Paxson, et. al. Informational [Page 22]
RFC 2525 TCP Implementation Problems March 1999
How to
If source code is available, that is generally the easiest way
detect this problem. Search for each modification to the
variable; (at least) one of these will be for
avoidance, and inspection of the related code should
identify the problem if present
The problem can also be detected by closely examining
traces taken near the sender. During congestion avoidance,
will increase by an additional segment upon the receipt
(typically) eight acknowledgements without a loss. This
is in addition to the one segment increase per round trip time (
two round trip times if the receiver is using delayed ACKs).
Furthermore, graphs of the sequence number vs. time, taken
packet traces, are normally linear during congestion avoidance
When viewing packet traces of transfers from senders
this problem, the graphs appear quadratic instead of linear
Finally, the traces will show that, with sufficiently
windows, nearly every loss event results in a timeout
How to
This problem may be corrected by removing the "+ MSS/8" term
the congestion avoidance code that increases cwnd each time an
of new data is received
2.7.
Name of
Initial RTO too
When a TCP first begins transmitting data, it lacks the
measurements necessary to have computed an adaptive
timeout (RTO). RFC 1122, 4.2.3.1, states that a TCP
initialize RTO to 3 seconds. A TCP that uses a lower
exhibits "Initial RTO too low".
In environments with large RTTs (where "large" means any
larger than the initial RTO), TCPs will experience very
performance
Paxson, et. al. Informational [Page 23]
RFC 2525 TCP Implementation Problems March 1999
Whenever RTO < RTT, very poor performance can result as
are unnecessarily retransmitted (because RTO will expire before
ACK for the packet can arrive) and the connection enters
start and congestion avoidance. Generally, the algorithms
computing RTO avoid this problem by adding a positive term to
estimated RTT. However, when a connection first begins it
use some estimate for RTO, and if it picks a value less than RTT
the above problems will arise
Furthermore, when the initial RTO < RTT, it can take a long
for the TCP to correct the problem by adapting the RTT estimate
because the use of Karn's algorithm (mandated by RFC 1122,
4.2.3.1) will discard many of the candidate RTT measurements
after the first timeout, since they will be measurements
retransmitted segments
Relevant
RFC 1122 states that TCPs SHOULD initialize RTO to 3 seconds
MUST implement Karn's algorithm
Trace file demonstrating
The following trace file was taken using tcpdump at host A,
data sender. The advertised window and SYN options have
omitted for clarity
07:52:39.870301 A > B: S 2786333696:2786333696(0)
07:52:40.548170 B > A: S 130240000:130240000(0) ack 2786333697
07:52:40.561287 A > B: P 1:513(512) ack 1
07:52:40.753466 A > B: . 1:513(512) ack 1
07:52:41.133687 A > B: . 1:513(512) ack 1
07:52:41.458529 B > A: . ack 513
07:52:41.458686 A > B: . 513:1025(512) ack 1
07:52:41.458797 A > B: P 1025:1537(512) ack 1
07:52:41.541633 B > A: . ack 513
07:52:41.703732 A > B: . 513:1025(512) ack 1
07:52:42.044875 B > A: . ack 513
07:52:42.173728 A > B: . 513:1025(512) ack 1
07:52:42.330861 B > A: . ack 1537
07:52:42.331129 A > B: . 1537:2049(512) ack 1
07:52:42.331262 A > B: P 2049:2561(512) ack 1
07:52:42.623673 A > B: . 1537:2049(512) ack 1
07:52:42.683203 B > A: . ack 1537
07:52:43.044029 B > A: . ack 1537
07:52:43.193812 A > B: . 1537:2049(512) ack 1
Paxson, et. al. Informational [Page 24]
RFC 2525 TCP Implementation Problems March 1999
Note from the SYN/SYN-ACK exchange, the RTT is over 600 msec
However, from the elapsed time between the third and fourth
(the first packet being sent and then retransmitted), it
apparent the RTO was initialized to under 200 msec. The next
shows that this value has doubled to 400 msec (correct
backoff of RTO), but that still does not suffice to avoid
unnecessary retransmission
Finally, an ACK from B arrives for the first segment. Later
more duplicate ACKs for 513 arrive, indicating that both
original and the two retransmissions arrived at B. (Indeed,
concurrent trace at B showed that no packets were lost during
entire connection). This ACK opens the congestion window to
packets, which are sent back-to-back, but at 07:52:41.703732
again expires after a little over 200 msec, leading to
unnecessary retransmission, and the pattern repeats. By the
of the trace excerpt above, 1536 bytes have been
transmitted from A to B, over an interval of more than 2 seconds
reflecting terrible performance
Trace file demonstrating correct
The following trace file was taken using tcpdump at host C,
data sender. The advertised window and SYN options have
omitted for clarity
17:30:32.090299 C > D: S 2031744000:2031744000(0)
17:30:32.900325 D > C: S 262737964:262737964(0) ack 2031744001
17:30:32.900326 C > D: . ack 1
17:30:32.910326 C > D: . 1:513(512) ack 1
17:30:34.150355 D > C: . ack 513
17:30:34.150356 C > D: . 513:1025(512) ack 1
17:30:34.150357 C > D: . 1025:1537(512) ack 1
17:30:35.170384 D > C: . ack 1025
17:30:35.170385 C > D: . 1537:2049(512) ack 1
17:30:35.170386 C > D: . 2049:2561(512) ack 1
17:30:35.320385 D > C: . ack 1537
17:30:35.320386 C > D: . 2561:3073(512) ack 1
17:30:35.320387 C > D: . 3073:3585(512) ack 1
17:30:35.730384 D > C: . ack 2049
The initial SYN/SYN-ACK exchange shows that RTT is more than 800
msec, and for some subsequent packets it rises above 1 second,
C's retransmit timer does not ever expire
This problem is documented in [Paxson97].
Paxson, et. al. Informational [Page 25]
RFC 2525 TCP Implementation Problems March 1999
How to
This problem is readily detected by inspecting a packet trace
the startup of a TCP connection made over a long-delay path.
can be diagnosed from either a sender-side or receiver-side trace
Long-delay paths can often be found by locating remote sites
other continents
How to
As this problem arises from a faulty initialization, one
fixing it requires a one-line change to the TCP source code
2.8.
Name of
Failure of window deflation after loss
Congestion control /
The fast recovery algorithm allows TCP senders to continue
transmit new segments during loss recovery. First,
retransmission is initiated after a TCP sender receives
duplicate ACKs. At this point, a retransmission is sent and
is halved. The fast recovery algorithm then allows
segments to be sent when sufficient additional duplicate
arrive. Some implementations of fast recovery compute when
send additional segments by artificially incrementing cwnd,
by three segments to account for the three duplicate ACKs
triggered fast retransmission, and subsequently by 1 MSS for
new duplicate ACK that arrives. When cwnd allows, the
transmits new data segments
When an ACK arrives that covers new data, cwnd is to be reduced
the amount by which it was artificially increased. However,
TCP implementations fail to "deflate" the window, causing
inappropriate amount of data to be sent into the network
recovery. One cause of this problem is the "header prediction
code, which is used to handle incoming segments that
little work. In some implementations of TCP, the
prediction code does not check to make sure cwnd has not
artificially inflated, and therefore does not reduce
artificially increased cwnd when appropriate
TCP senders that exhibit this problem will transmit a burst
data immediately after recovery, which can degrade performance,
well as network stability. Effectively, the sender does
Paxson, et. al. Informational [Page 26]
RFC 2525 TCP Implementation Problems March 1999
reduce the size of cwnd as much as it should (to half its
when loss was detected), if at all. This can harm the
of the TCP connection itself, as well as competing TCP flows
A TCP sender exhibiting this problem does not reduce
appropriately in times of congestion, and therefore may
to congestive collapse
Relevant
RFC 2001 outlines the fast retransmit/fast recovery algorithms
[Brakmo95] outlines this implementation problem and offers a fix
Trace file demonstrating
The following trace file was taken using tcpdump at host A,
data sender. The advertised window (which never changed) has
omitted for clarity, except for the first packet sent by
host
08:22:56.825635 A.7505 > B.7505: . 29697:30209(512) ack 1 win 4608
08:22:57.038794 B.7505 > A.7505: . ack 27649 win 4096
08:22:57.039279 A.7505 > B.7505: . 30209:30721(512) ack 1
08:22:57.321876 B.7505 > A.7505: . ack 28161
08:22:57.322356 A.7505 > B.7505: . 30721:31233(512) ack 1
08:22:57.347128 B.7505 > A.7505: . ack 28673
08:22:57.347572 A.7505 > B.7505: . 31233:31745(512) ack 1
08:22:57.347782 A.7505 > B.7505: . 31745:32257(512) ack 1
08:22:57.936393 B.7505 > A.7505: . ack 29185
08:22:57.936864 A.7505 > B.7505: . 32257:32769(512) ack 1
08:22:57.950802 B.7505 > A.7505: . ack 29697 win 4096
08:22:57.951246 A.7505 > B.7505: . 32769:33281(512) ack 1
08:22:58.169422 B.7505 > A.7505: . ack 29697
08:22:58.638222 B.7505 > A.7505: . ack 29697
08:22:58.643312 B.7505 > A.7505: . ack 29697
08:22:58.643669 A.7505 > B.7505: . 29697:30209(512) ack 1
08:22:58.936436 B.7505 > A.7505: . ack 29697
08:22:59.002614 B.7505 > A.7505: . ack 29697
08:22:59.003026 A.7505 > B.7505: . 33281:33793(512) ack 1
08:22:59.682902 B.7505 > A.7505: . ack 33281
08:22:59.683391 A.7505 > B.7505: P 33793:34305(512) ack 1
08:22:59.683748 A.7505 > B.7505: P 34305:34817(512) ack 1 ***
08:22:59.684043 A.7505 > B.7505: P 34817:35329(512) ack 1
08:22:59.684266 A.7505 > B.7505: P 35329:35841(512) ack 1
08:22:59.684567 A.7505 > B.7505: P 35841:36353(512) ack 1
08:22:59.684810 A.7505 > B.7505: P 36353:36865(512) ack 1
08:22:59.685094 A.7505 > B.7505: P 36865:37377(512) ack 1
Paxson, et. al. Informational [Page 27]
RFC 2525 TCP Implementation Problems March 1999
The first 12 lines of the trace show incoming ACKs clocking out
window of data segments. At this point in the transfer, cwnd is 7
segments. The next 4 lines of the trace show 3 duplicate
arriving from the receiver, followed by a retransmission from
sender. At this point, cwnd is halved (to 3 segments)
artificially incremented by the three duplicate ACKs that
arrived, making cwnd 6 segments. The next two lines show 2
duplicate ACKs arriving, each of which increases cwnd by 1
segment. So, after these two duplicate ACKs arrive the cwnd is 8
segments and the sender has permission to send 1 new
(since there are 7 segments outstanding). The next line in
trace shows this new segment being transmitted. The next
shown in the trace is an ACK from host B that covers the first 7
outstanding segments (all but the new segment sent
recovery). This should cause cwnd to be reduced to 3 segments
2 segments to be transmitted (since there is already 1
segment in the network). However, as shown by the last 7 lines
the trace, cwnd is not reduced, causing a line-rate burst of 7
segments
Trace file demonstrating correct
The trace would appear identical to the one above, only it
stop after the line marked "***", because at this point host
would correctly reduce cwnd after recovery, allowing only 2
segments to be transmitted, rather than producing a burst of 7
segments
This problem is documented and the performance
analyzed in [Brakmo95].
How to
Failure of window deflation after loss recovery can be found
examining sender-side packet traces recorded during periods
moderate loss (so cwnd can grow large enough to allow for
recovery when loss occurs).
How to
When this bug is caused by incorrect header prediction, the fix
to add a predicate to the header prediction test that checks
see whether cwnd is inflated; if so, the header prediction
fails and the usual ACK processing occurs, which (in this case
takes care to deflate the window. See [Brakmo95] for details
2.9.
Name of
Excessively short keepalive connection
Paxson, et. al. Informational [Page 28]
RFC 2525 TCP Implementation Problems March 1999
Keep-alive is a mechanism for checking whether an idle
is still alive. According to RFC 1122, keepalive should only
invoked in server applications that might otherwise
indefinitely and consume resources unnecessarily if a
crashes or aborts a connection during a network failure
RFC 1122 also specifies that if a keep-alive mechanism
implemented it MUST NOT interpret failure to respond to
specific probe as a dead connection. The RFC does not specify
particular mechanism for timing out a connection when no
is received for keepalive probes. However, if the mechanism
not allow ample time for recovery from network congestion
delay, connections may be timed out unnecessarily
In congested networks, can lead to unwarranted termination
connections
It is possible for the network connection between two
machines to become congested or to exhibit packet loss at the
that a keep-alive probe is sent on a connection. If the keep
alive mechanism does not allow sufficient time before
connections in the face of unacknowledged probes, connections
be dropped even when both peers of a connection are still alive
Relevant
RFC 1122 specifies that the keep-alive mechanism may be provided
It does not specify a mechanism for determining dead
when keepalive probes are not acknowledged
Trace file demonstrating
Made using the Orchestra tool at the peer of the machine
keep-alive. After connection establishment, incoming keep-
were dropped by Orchestra to simulate a dead connection
22:11:12.040000 A > B: 22666019:0 win 8192 datasz 4
22:11:12.060000 B > A: 2496001:22666020 win 4096 datasz 4 SYN
22:11:12.130000 A > B: 22666020:2496002 win 8760 datasz 0
(more than two hours elapse
00:23:00.680000 A > B: 22666019:2496002 win 8760 datasz 1
00:23:01.770000 A > B: 22666019:2496002 win 8760 datasz 1
00:23:02.870000 A > B: 22666019:2496002 win 8760 datasz 1
00:23.03.970000 A > B: 22666019:2496002 win 8760 datasz 1
Paxson, et. al. Informational [Page 29]
RFC 2525 TCP Implementation Problems March 1999
00:23.05.070000 A > B: 22666019:2496002 win 8760 datasz 1
The initial three packets are the SYN exchange for
setup. About two hours later, the keepalive timer fires
the connection has been idle. Keepalive probes are transmitted
total of 5 times, with a 1 second spacing between probes,
which the connection is dropped. This is problematic because a 5
second network outage at the time of the first probe results
the connection being killed
Trace file demonstrating correct
Made using the Orchestra tool at the peer of the machine
keep-alive. After connection establishment, incoming keep-
were dropped by Orchestra to simulate a dead connection
16:01:52.130000 A > B: 1804412929:0 win 4096 datasz 4
16:01:52.360000 B > A: 16512001:1804412930 win 4096 datasz 4 SYN
16:01:52.410000 A > B: 1804412930:16512002 win 4096 datasz 0
(two hours elapse
18:01:57.170000 A > B: 1804412929:16512002 win 4096 datasz 0
18:03:12.220000 A > B: 1804412929:16512002 win 4096 datasz 0
18:04:27.270000 A > B: 1804412929:16512002 win 4096 datasz 0
18:05:42.320000 A > B: 1804412929:16512002 win 4096 datasz 0
18:06:57.370000 A > B: 1804412929:16512002 win 4096 datasz 0
18:08:12.420000 A > B: 1804412929:16512002 win 4096 datasz 0
18:09:27.480000 A > B: 1804412929:16512002 win 4096 datasz 0
18:10:43.290000 A > B: 1804412929:16512002 win 4096 datasz 0
18:11:57.580000 A > B: 1804412929:16512002 win 4096 datasz 0
18:13:12.630000 A > B: 1804412929:16512002 win 4096 datasz 0 RST
In this trace, when the keep-alive timer expires, 9
probes are sent at 75 second intervals. 75 seconds after the
probe is sent, a final RST segment is sent indicating that
connection has been closed. This implementation waits about 11
minutes before timing out the connection, while the
implementation shown allows only 5 seconds
This problem is documented in [Dawson97].
How to
For implementations manifesting this problem, it shows up on
packet trace after the keepalive timer fires if the peer
receiving the keepalive does not respond. Usually the
timer will fire at least two hours after keepalive is turned on
but it may be sooner if the timer value has been configured lower
or if the keepalive mechanism violates the specification (
Insufficient interval between keepalives problem). In
Paxson, et. al. Informational [Page 30]
RFC 2525 TCP Implementation Problems March 1999
example, suppressing the response of the peer to keepalive
was accomplished using the Orchestra toolkit, which can
configured to drop packets. It could also have been done
creating a connection, turning on keepalive, and disconnecting
network connection at the receiver machine
How to
This problem can be fixed by using a different method for
out keepalives that allows a longer period of time to
before dropping the connection. For example, the algorithm
timing out on dropped data could be used. Another possibility
an algorithm such as the one shown in the trace above, which
9 probes at 75 second intervals and then waits an additional 75
seconds for a response before closing the connection
2.10.
Name of
Failure to back off retransmission
Congestion control /
The retransmission timeout is used to determine when a packet
been dropped in the network. When this timeout has
without the arrival of an ACK, the segment is retransmitted.
time a segment is retransmitted, the timeout is adjusted
to an exponential backoff algorithm, doubling each time. If a
fails to receive an ACK after numerous attempts at
the same segment, it terminates the connection. A TCP that
to double its retransmission timeout upon repeated timeouts
said to exhibit "Failure to back off retransmission timeout".
Backing off the retransmission timer is a cornerstone of
stability in the presence of congestion. Consequently, this
can have severe adverse affects in congested networks. It
affects TCP reliability in congested networks, as discussed in
next section
It is possible for the network connection between two TCP peers
become congested or to exhibit packet loss at the time that
retransmission is sent on a connection. If the
mechanism does not allow sufficient time before
Paxson, et. al. Informational [Page 31]
RFC 2525 TCP Implementation Problems March 1999
connections in the face of unacknowledged segments,
may be dropped even when, by waiting longer, the connection
have continued
Relevant
RFC 1122 specifies mandatory exponential backoff of
retransmission timeout, and the termination of connections
some period of time (at least 100 seconds).
Trace file demonstrating
Made using tcpdump on an intermediate host
16:51:12.671727 A > B: S 510878852:510878852(0) win 16384
16:51:12.672479 B > A: S 2392143687:2392143687(0)
ack 510878853 win 16384
16:51:12.672581 A > B: . ack 1 win 16384
16:51:15.244171 A > B: P 1:3(2) ack 1 win 16384
16:51:15.244933 B > A: . ack 3 win 17518 (DF
<receiving host disconnected
16:51:19.381176 A > B: P 3:5(2) ack 1 win 16384
16:51:20.162016 A > B: P 3:5(2) ack 1 win 16384
16:51:21.161936 A > B: P 3:5(2) ack 1 win 16384
16:51:22.161914 A > B: P 3:5(2) ack 1 win 16384
16:51:23.161914 A > B: P 3:5(2) ack 1 win 16384
16:51:24.161879 A > B: P 3:5(2) ack 1 win 16384
16:51:25.161857 A > B: P 3:5(2) ack 1 win 16384
16:51:26.161836 A > B: P 3:5(2) ack 1 win 16384
16:51:27.161814 A > B: P 3:5(2) ack 1 win 16384
16:51:28.161791 A > B: P 3:5(2) ack 1 win 16384
16:51:29.161769 A > B: P 3:5(2) ack 1 win 16384
16:51:30.161750 A > B: P 3:5(2) ack 1 win 16384
16:51:31.161727 A > B: P 3:5(2) ack 1 win 16384
16:51:32.161701 A > B: R 5:5(0) ack 1 win 16384
The initial three packets are the SYN exchange for
setup, then a single data packet, to verify that data can
transferred. Then the connection to the destination host
disconnected, and more data sent. Retransmissions occur
second for 12 seconds, and then the connection is terminated
a RST. This is problematic because a 12 second pause
connectivity could result in the termination of a connection
Trace file demonstrating correct
Again, a tcpdump taken from a third host
Paxson, et. al. Informational [Page 32]
RFC 2525 TCP Implementation Problems March 1999
16:59:05.398301 A > B: S 2503324757:2503324757(0) win 16384
16:59:05.399673 B > A: S 2492674648:2492674648(0)
ack 2503324758 win 16384
16:59:05.399866 A > B: . ack 1 win 17520
16:59:06.538107 A > B: P 1:3(2) ack 1 win 17520
16:59:06.540977 B > A: . ack 3 win 17518 (DF
<receiving host disconnected
16:59:13.121542 A > B: P 3:5(2) ack 1 win 17520
16:59:14.010928 A > B: P 3:5(2) ack 1 win 17520
16:59:16.010979 A > B: P 3:5(2) ack 1 win 17520
16:59:20.011229 A > B: P 3:5(2) ack 1 win 17520
16:59:28.011896 A > B: P 3:5(2) ack 1 win 17520
16:59:44.013200 A > B: P 3:5(2) ack 1 win 17520
17:00:16.015766 A > B: P 3:5(2) ack 1 win 17520
17:01:20.021308 A > B: P 3:5(2) ack 1 win 17520
17:02:24.027752 A > B: P 3:5(2) ack 1 win 17520
17:03:28.034569 A > B: P 3:5(2) ack 1 win 17520
17:04:32.041567 A > B: P 3:5(2) ack 1 win 17520
17:05:36.048264 A > B: P 3:5(2) ack 1 win 17520
17:06:40.054900 A > B: P 3:5(2) ack 1 win 17520
17:07:44.061306 A > B: R 5:5(0) ack 1 win 17520
In this trace, when the retransmission timer expires, 12
retransmissions are sent at exponentially-increasing intervals
until the interval value reaches 64 seconds, at which time
interval stops growing. 64 seconds after the last retransmission
a final RST segment is sent indicating that the connection
been closed. This implementation waits about 9 minutes
timing out the connection, while the first implementation
allows only 12 seconds
None known
How to
A simple transfer can be easily interrupted by disconnecting
receiving host from the network. tcpdump or another
tool should show the retransmissions being sent. Several
in a low-rtt environment may be required to demonstrate the bug
How to
For one of the implementations studied, this problem seemed to
the result of an error introduced with the addition of
Brakmo-Peterson RTO algorithm [Brakmo95], which can return a
of zero where the older Jacobson algorithm always returns
Paxson, et. al. Informational [Page 33]
RFC 2525 TCP Implementation Problems March 1999
positive value. Brakmo and Peterson specified an additional
of min(rtt + 2, RTO) to avoid problems with this. Unfortunately
in the implementation this step was omitted when calculating
exponential backoff for the RTO. This results in an RTO of 0
seconds being multiplied by the backoff, yielding again zero,
then being subjected to a later MAX operation that increases it
1 second, regardless of the backoff factor
A similar TCP persist failure has the same cause
2.11.
Name of
Insufficient interval between
Keep-alive is a mechanism for checking whether an idle
is still alive. According to RFC 1122, keep-alive may be
in an implementation. If it is included, the interval
keep-alive packets MUST be configurable, and MUST default to
less than two hours
In congested networks, can lead to unwarranted termination
connections
According to RFC 1122, keep-alive is not required
implementations because it could: (1) cause perfectly
connections to break during transient Internet failures; (2)
consume unnecessary bandwidth ("if no one is using the connection
who cares if it is still good?"); and (3) cost money for
Internet path that charges for packets. Regarding this
point, we note that in addition the presence of dial-on-
links in the route can greatly magnify the cost penalty of
keepalives, potentially forcing a full-time connection on a
that would otherwise only be connected a few minutes a day
If keepalive is provided the RFC states that the required inter
keepalive distance MUST default to no less than two hours. If
does not, the probability of connections breaking increases,
bandwidth used due to keepalives increases, and cost
over paths which charge per packet
Paxson, et. al. Informational [Page 34]
RFC 2525 TCP Implementation Problems March 1999
Relevant
RFC 1122 specifies that the keep-alive mechanism may be provided
It also specifies the two hour minimum for the default
between keepalive probes
Trace file demonstrating
Made using the Orchestra tool at the peer of the machine
keep-alive. Machine A was configured to use default settings
the keepalive timer
11:36:32.910000 A > B: 3288354305:0 win 28672 datasz 4
11:36:32.930000 B > A: 896001:3288354306 win 4096 datasz 4 SYN
11:36:32.950000 A > B: 3288354306:896002 win 28672 datasz 0
11:50:01.190000 A > B: 3288354305:896002 win 28672 datasz 0
11:50:01.210000 B > A: 896002:3288354306 win 4096 datasz 0
12:03:29.410000 A > B: 3288354305:896002 win 28672 datasz 0
12:03:29.430000 B > A: 896002:3288354306 win 4096 datasz 0
12:16:57.630000 A > B: 3288354305:896002 win 28672 datasz 0
12:16:57.650000 B > A: 896002:3288354306 win 4096 datasz 0
12:30:25.850000 A > B: 3288354305:896002 win 28672 datasz 0
12:30:25.870000 B > A: 896002:3288354306 win 4096 datasz 0
12:43:54.070000 A > B: 3288354305:896002 win 28672 datasz 0
12:43:54.090000 B > A: 896002:3288354306 win 4096 datasz 0
The initial three packets are the SYN exchange for
setup. About 13 minutes later, the keepalive timer fires
the connection is idle. The keepalive is acknowledged, and
timer fires again in about 13 more minutes. This
continues indefinitely until the connection is closed, and is
violation of the specification
Trace file demonstrating correct
Made using the Orchestra tool at the peer of the machine
keep-alive. Machine A was configured to use default settings
the keepalive timer
17:37:20.500000 A > B: 34155521:0 win 4096 datasz 4
17:37:20.520000 B > A: 6272001:34155522 win 4096 datasz 4 SYN
17:37:20.540000 A > B: 34155522:6272002 win 4096 datasz 0
19:37:25.43000