Internet DRAFT - draft-erblich-tcp-no-karn-alg
draft-erblich-tcp-no-karn-alg
Network Working Group
Internet draft Mitchell Erblich August 2006
Category: Experimental
Alteration of Karn's Algorithm for
High Bandwidth / Delay Environments
<draft-erblich-tcp-no-karn-alg-00.txt>
Status of this Memo
By submitting this Internet-Draft, each author represents that any
applicable patent or other IPR claims of which he or she is aware
have been or will be disclosed, and any of which he or she becomes
aware will be disclosed, in accordance with Section 6 of BCP 79.
Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF), its areas, and its working groups. Note that
other groups may also distribute working documents as Internet-
Drafts.
Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress."
The list of current Internet-Drafts can be accessed at
http://www.ietf.org/ietf/1id-abstracts.txt.
The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html.
Copyright Notice
Copyright (C) The Internet Society (2006). All Rights Reserved.
ABSTRACT
Karn's algorithm specifies acknowledgements that are the
result of segment retransmits should be ignored, not timed,
and should not contribute to the smoothed round-trip-time
(SRTT) because they are considered "ambiguous". It is also
stated in Karn's paper that "If an acknowledgement arrives
after the RTO has expired, it is highly likely to come very
shortly after wards." In time, we have added the "fast retransmit"
functionality, so we are not solely dependent on RTO for
retransmits. Common sense dictates that if we receive an
acknowledgement "very shortly after wards", that those
acknowledgments should not be considered "ambiguous". These
non-ambiguous acknowledgments should be added to the SRTT and
trigger us to return to our previous non-congestion behavior.
Table of Contents
1. Motivation ................ 2
2. Introduction ................ 2
3. Implementation .............. 3
4. Conclusion ................ 4
5. References ................ 4
6. Security Considerations ..... 4
7. Author's Address 5
1. Motivation
An ISP measured that at certain times of day, that the amount of
transmitted data through a number of TCP connections far exceeded
the amount of data thought to be generated by a specified set of
applications. It was theorized that either a large number of
segments were being dropped and/or that some segments had a large
RTT and were being retransmitted needlessly.
A major unseen item was a resulting drop in useable throughput
of a TCP flow when congestion was not present. This is not believed
to have been an issue possibly due to application limited TCP flows
Out-of-order (ooo) segments are more likely to appear in high
bandwidth / delay environments. It is these environments that can
consume a receiver's buffer, such that the receiver can reneg and
discard data that has been selectively acknowledged (SACK).
However, we are more concerned about ooo segments arriving arriving
at the receiver that latter results in fast-retransmits. These
fast-retransmits forces us into congestion avoidance (CA), and
it is the recovery time resulting and lost bandwidth that we
are addressing here.
In addition, [RFC3522] requires the use of TCP timestamps. This
document attempts to justify that the same results can occur
when TCP timestamps are not used in high-bandwidth / delay
environments and quickly recovers from the false CA.
2. Introduction
[KARN] specifies that segment retransmission should not be
timed because the ack can not be determined to be resulting
from the original or the later retransmitted segment.
In Karn's original paper ONLY course grained RTO timeouts were
triggers for retransmits. Thus the paper concentrated on the
determination of a proper SRTT, given a set of segment RTTs.
[RFC2525] specifies that "when the initial RTO < RTT, it can
take a long time for the TCP to correct the problem by
adapting the RTT estimate, because of the use of the Karn's
algorithm". This is from section 2.7.
[PAX97] introduces the concept that a large number of
environments can or do re-order more than a minimal number
of segments.
Spurious retransmissions are the result of segment
retransmissions, that are later determined to be unnecessary. These
unnecessary added segment transmissions / retransmissions consume
link bandwidth and decrease the actual application throughput.
RFC3522 introduces multiple events that can lead to false
congestion avoidance and a detection algorithm. This RFC
requires the use of the segment timestamp.
This document attempts to take extra steps to detect false
congestion without the use of the Timestamp option and suggest
parameters that could be used to restore the pre-congestion
bandwidth throughput as-soon-as-possible without creating
a local congestion event.
2.1 Timestamp Issues
* Not all implementations enable the Timestamps option.
* A receiver may forge a echoed Timestamp
* The granularity for the timestamp clock for a high
bandwidth link to a low delay receiver may be too
fine grained, than to a high delay receiver over
the same link.
Only the third item is reviewed in this document. To attempt
to resolve the granularity issue, we attempt to adjust the
timestamp granularity based on the number of inflight segments
on a per connection basis.
3. Implementation
A R&D environment with interfaces up to 10Gb Ethernet was highly
instrumented for a number of days. The number of inflight segments
per major aggregated flow periodiclly exceeded 100k. Because of the
number of possible inflight segments, it was deemed that
Selective-ACKs would only complicate the implementation. We
later re-enabled Timestamp option and SACK support for validation
of our results.
We added and used these parameters: number of inflight segments,
the average size of each inflight segment, the approximate number
of inflight acks, the number of un-ambiguous acks, the number of
ambiguous acks within each RTT interval, a set of pre-congestion
metrics, the number of current duplicate acks, etc. We used these
values to identify a point that the ACK was highly likely for the
original segment. Otherwise we consider this ACK without timestamp
support, a ambiguous ACK.
If we identified that the ack was for the original segment then
the goal of this project was to attempt to implement a fast
recovery scheme to pre-congestion status because of this
false-congestion event. Adjusting the number of duplicate acks
before a fast-retransmit was not in the scope of this project.
This implementation resulted in the equivalent of a non-slow-start
restart, but while we are in congestion avoidance.
The specifics of the TCP modifications and the testing environment
was deemed Intellectual Property (IP) by the legal staff at
the client's site. Thus, those specifics have been removed from
this document.
4. Conclusion
The ability to identify whether a ACK is for a original or
re-transmitted segment should be common sense without SACK or
timestamp option if the number of in-flight segments was large
enough and the ACK came shortly after the fast retransmit.
However, given a large enough in-flight ACK reduction, and
decreasing the number of in-flight ACKs, an implementation
needs to support a segment burst methodology and the ability
to determine that their the ACK is still ambiguous. It is
highly likely that if the implementation uses an aggressive
method, that some ACKs really are ambiguous (retransmit ACK)
but are treated as non-ambiguous.
Significant bandwidth recovery up to 50% can result depending
on the now non-ambiguous ACKs. The amount of recovery is based
partially on the amount of aggressiveness of the segment burst
method used. It is also based on the quantity of ooo segments
and the amount of drift of those segments. Some experimental
TCP RFCs have suggested methods to decrease the likeness to
generate localized congestion when restoring or generating a
number of in-flight segments.
5. References
KARN, P. [Aug 1987] Improving Round-Trip Times Estimates in
Reliable Transport Protocols, Proceedings of the ACM SIGCOMM '87.
[RFC2525] Paxson, Allman, etc. "Known TCP Implementation Problems", RFC 2525, March 1999.
[RFC3522] Ludwig, R. and M. Meyer, "The Eifel Detection Algorithm for TCP", RFC 3522, April 2003.
6. Security Considerations
This memo does not create any new security issues for the
TCP protocol.
7. Author's Address
Mitchell Erblich erblichs@earthlink.net
Intellectual Property Statement
The IETF takes no position regarding the validity or scope of any
Intellectual Property Rights or other rights that might be claimed to
pertain to the implementation or use of the technology described in
this document or the extent to which any license under such rights
might or might not be available; nor does it represent that it has
made any independent effort to identify any such rights. Information
on the procedures with respect to rights in RFC documents can be
found in BCP 78 and BCP 79.
Copies of IPR disclosures made to the IETF Secretariat and any
assurances of licenses to be made available, or the result of an
attempt made to obtain a general license or permission for the use of
such proprietary rights by implementers or users of this
specification can be obtained from the IETF on-line IPR repository at
http://www.ietf.org/ipr.
The IETF invites any interested party to bring to its attention any
copyrights, patents or patent applications, or other proprietary
rights that may cover technology that may be required to implement
this standard. Please address the information to the IETF at
ietf-ipr@ietf.org.
Disclaimer of Validity
This document and the information contained herein are provided on an
"AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS
OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET
ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED,
INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE
INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED
WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
Copyright Statement
Copyright (C) The Internet Society (2006). This document is subject
to the rights, licenses and restrictions contained in BCP 78, and
except as set forth therein, the authors retain all their rights.
