draft-ietf-tsvwg-tcp-nonce-01.txt   draft-ietf-tsvwg-tcp-nonce-02.txt 
Internet Engineering Task Force Neil Spring Internet Engineering Task Force Neil Spring
INTERNET DRAFT David Wetherall INTERNET DRAFT David Wetherall
draft-ietf-tsvwg-tcp-nonce-01.txt David Ely draft-ietf-tsvwg-tcp-nonce-02.txt David Ely
University of Washington University of Washington
July, 2001 October, 2001
Expires: January, 2001 Expires: April, 2002
Robust ECN Signaling with Nonces Robust ECN Signaling with Nonces
Status of this Memo Status of this Memo
This document is an Internet-Draft and is in full conformance with This document is an Internet-Draft and is in full conformance with
all provisions of Section 10 of RFC2026. all provisions of Section 10 of RFC2026.
Internet-Drafts are working documents of the Internet Engineering Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF), its areas, and its working groups. Note that Task Force (IETF), its areas, and its working groups. Note that
skipping to change at page 1, line 35 skipping to change at page 1, line 35
material or to cite them other than as "work in progress." material or to cite them other than as "work in progress."
The list of current Internet-Drafts can be accessed at The list of current Internet-Drafts can be accessed at
http://www.ietf.org/ietf/1id-abstracts.txt http://www.ietf.org/ietf/1id-abstracts.txt
The list of Internet-Draft Shadow Directories can be accessed at The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html. http://www.ietf.org/shadow.html.
Abstract Abstract
This note describes the ECN-nonce, a modification to ECN that This note describes the ECN-nonce, an optional addition to ECN that
protects against accidental or malicious concealment of marked protects against accidental or malicious concealment of marked
packets from the TCP sender. It improves the robustness of packets from the TCP sender. It improves the robustness of
congestion control by preventing receivers from exploiting ECN to congestion control by preventing receivers from exploiting ECN to
gain an unfair share of network bandwidth. The ECN-nonce uses the gain an unfair share of network bandwidth. The ECN-nonce uses the
two ECT codepoints in the ECN field of the IP header, and requires a two ECT codepoints in the ECN field of the IP header, and requires a
new flag in the TCP header. It is computationally efficient for both flag in the TCP header. It is computationally efficient for both
routers and hosts. routers and hosts.
1. Introduction 1. Introduction
The correct operation of ECN requires the cooperation of the receiver The correct operation of ECN requires the cooperation of the receiver
to return Congestion Experienced signals to the sender, but the to return Congestion Experienced signals to the sender, but the
protocol lacks a mechanism to enforce this cooperation. This raises protocol lacks a mechanism to enforce this cooperation. This raises
the possibility that an unscrupulous or poorly implemented receiver the possibility that an unscrupulous or poorly implemented receiver
could always clear ECN-Echo and simply not return congestion signals could always clear ECN-Echo and simply not return congestion signals
to the sender. This would give the receiver a performance advantage to the sender. This would give the receiver a performance advantage
skipping to change at page 5, line 28 skipping to change at page 6, line 7
sender uses the two ECT codepoints: ECT(0) represents a nonce of 0, sender uses the two ECT codepoints: ECT(0) represents a nonce of 0,
and ECT(1) a nonce of 1. As in ECN, retransmissions are not ECN- and ECT(1) a nonce of 1. As in ECN, retransmissions are not ECN-
capable, so carry no nonce. capable, so carry no nonce.
The sender maintains a mapping from each packet's end sequence number The sender maintains a mapping from each packet's end sequence number
to the expected nonce sum (not the nonce placed in the original to the expected nonce sum (not the nonce placed in the original
transmission) in the acknowledgement bearing that sequence number. transmission) in the acknowledgement bearing that sequence number.
4. Router Behavior 4. Router Behavior
Routers behave as specified in [ECN-draft]. By marking packets to Routers behave as specified in [RFC3168]. By marking packets to
signal congestion, the original value of the nonce, in ECT(0) or signal congestion, the original value of the nonce, in ECT(0) or
ECT(1), is removed. Neither the receiver nor any other party can ECT(1), is removed. Neither the receiver nor any other party can
unmark the packet without successfully guessing the value of the unmark the packet without successfully guessing the value of the
original nonce. original nonce.
5. Receiver Behavior (Receive and Transmit) 5. Receiver Behavior (Receive and Transmit)
ECN-nonce receivers maintain the nonce sum as in-order packets arrive ECN-nonce receivers maintain the nonce sum as in-order packets arrive
and return the current nonce sum in each acknowledgement. Receiver and return the current nonce sum in each acknowledgement. Receiver
behavior is otherwise unchanged from [ECN-draft]. behavior is otherwise unchanged from [RFC3168]. Returning the nonce
sum is optional, but recommended, as senders are allowed to
discontinue sending ECN-capable packets to receivers that do not
support the ECN-nonce.
As packets are removed from the queue of out-of-order packets to be As packets are removed from the queue of out-of-order packets to be
acknowledged, the nonce is recovered from the IP header. The nonce acknowledged, the nonce is recovered from the IP header. The nonce
is added to the current nonce sum as the acknowledgement sequence is added to the current nonce sum as the acknowledgement sequence
number is advanced for the recent packet. number is advanced for the recent packet.
In the case of marked packets, one or more nonce values may be In the case of marked packets, one or more nonce values may be
unknown to the receiver. In this case the missing nonce values are unknown to the receiver. In this case the missing nonce values are
ignored when calculating the sum (or equivalently a value of zero is ignored when calculating the sum (or equivalently a value of zero is
assumed) and ECN-Echo will be set to signal congestion to the sender. assumed) and ECN-Echo will be set to signal congestion to the sender.
skipping to change at page 6, line 56 skipping to change at page 7, line 39
equally likely to be 0 or 1. In other words, any guess is equally equally likely to be 0 or 1. In other words, any guess is equally
likely to be wrong and has a 50-50 chance of being caught by the likely to be wrong and has a 50-50 chance of being caught by the
sender. Because each new acknowledgement is an independent trial, a sender. Because each new acknowledgement is an independent trial, a
cheating receiver is likely to be caught after a small number of cheating receiver is likely to be caught after a small number of
lies. lies.
If ECN-Echo is set, the receiver is sending a congestion signal and If ECN-Echo is set, the receiver is sending a congestion signal and
it is not necessary to check the nonce sum. The congestion window it is not necessary to check the nonce sum. The congestion window
will be halved, CWR will be set on the next packet with new data will be halved, CWR will be set on the next packet with new data
sent, and ECN-Echo will be cleared once the CWR signal is received, sent, and ECN-Echo will be cleared once the CWR signal is received,
as in [ECN-draft]. During this recovery process, the sum may be as in [RFC3168]. During this recovery process, the sum may be
incorrect because one or more nonces were not received. This does incorrect because one or more nonces were not received. This does
not matter during recovery, because TCP invokes congestion mechanisms not matter during recovery, because TCP invokes congestion mechanisms
at most once per RTT, whether there are one or more losses during at most once per RTT, whether there are one or more losses during
that period. that period.
6.1 Resynchronization After Loss or Mark 6.1 Resynchronization After Loss or Mark
After recovery, it is necessary to re-synchronize the sender and After recovery, it is necessary to re-synchronize the sender and
receiver nonce sums so that further acknowledgments can be checked. receiver nonce sums so that further acknowledgments can be checked.
When the receiver's sum is incorrect, it will remain incorrect until When the receiver's sum is incorrect, it will remain incorrect until
skipping to change at page 7, line 51 skipping to change at page 8, line 41
In practice, resynchronization can be accomplished by storing a bit In practice, resynchronization can be accomplished by storing a bit
that has the value one if the expected nonce sum stored by the sender that has the value one if the expected nonce sum stored by the sender
and the received nonce sum in the acknowledgement of CWR differ, and and the received nonce sum in the acknowledgement of CWR differ, and
zero otherwise. This synchronization offset bit can then be used in zero otherwise. This synchronization offset bit can then be used in
the comparison between expected nonce sum and received nonce sum. the comparison between expected nonce sum and received nonce sum.
The sender should ignore the nonce sum returned on any The sender should ignore the nonce sum returned on any
acknowledgements bearing the ECN-echo flag. acknowledgements bearing the ECN-echo flag.
When an acknowledgment covers only a portion of a segment, such as
when a middlebox resegments at the TCP layer instead of fragmenting
IP packets, the sender should accept the nonce sum expected at the
next segment boundary. In other words, an acknowledgement covering
part of an original segment will include the nonce sum expected when
the entire segment is acknowledged.
Finally, in ECN, senders can choose not to indicate ECN capability on Finally, in ECN, senders can choose not to indicate ECN capability on
some packets for any reason. An ECN-nonce sender must resynchronize some packets for any reason. An ECN-nonce sender must resynchronize
after sending such ECN-incapable packets, as though a CWR had been after sending such ECN-incapable packets, as though a CWR had been
sent with the first new data after the ECN-incapable packets. The sent with the first new data after the ECN-incapable packets. The
sender loses protection for any unacknowledged packets until sender loses protection for any unacknowledged packets until
resynchronization occurs. resynchronization occurs.
6.2 Sender Behavior - Incorrect Nonce Received 6.2 Sender Behavior - Incorrect Nonce Received
The sender's response to an incorrect nonce is a matter of policy. The sender's response to an incorrect nonce is a matter of policy.
It is separate from the checking mechanism and does not need to be It is separate from the checking mechanism and does not need to be
handled uniformly by senders. handled uniformly by senders. Further, checking received nonce sums
at all is optional, and may be disabled.
If the receiver has never sent a non-zero nonce sum, the sender can If the receiver has never sent a non-zero nonce sum, the sender can
infer that the receiver does not understand the nonce, and rate limit infer that the receiver does not understand the nonce, and rate limit
the connection, place it in a lower-priority queue, or cease setting the connection, place it in a lower-priority queue, or cease setting
ECT in outgoing segments. ECT in outgoing segments.
If the received nonce sum has been set in a previous acknowledgement, If the received nonce sum has been set in a previous acknowledgement,
the sender might infer that a network device has interfered with the sender might infer that a network device has interfered with
correct ECN signaling between ECN-nonce supporting endpoints. The correct ECN signaling between ECN-nonce supporting endpoints. The
minimum response to an incorrect nonce is the same as the response to minimum response to an incorrect nonce is the same as the response to
skipping to change at page 8, line 41 skipping to change at page 9, line 44
have been lost). Drops could potentially be concealed by a faulty have been lost). Drops could potentially be concealed by a faulty
TCP implementation, certain attacks, or even a hypothetical TCP TCP implementation, certain attacks, or even a hypothetical TCP
accelerator. Such an accelerator could gamble that it can either accelerator. Such an accelerator could gamble that it can either
successfully ``fast start'' to a preset bandwidth quickly, retry with successfully ``fast start'' to a preset bandwidth quickly, retry with
another connection, or provide reliability at the application level. another connection, or provide reliability at the application level.
If robustness against these faults is also desired, then the ECN- If robustness against these faults is also desired, then the ECN-
nonce should not be disabled. Instead, reducing the congestion nonce should not be disabled. Instead, reducing the congestion
window to one, or using a low-priority queue, would penalize faulty window to one, or using a low-priority queue, would penalize faulty
operation while providing continued checking. operation while providing continued checking.
The ECN-nonce can also detect misbehavior in Eifel [Eifel-draft], a The ECN-nonce can also detect misbehavior in Eifel [Eifel], a
recently proposed mechanism for removing the retransmission ambiguity recently proposed mechanism for removing the retransmission ambiguity
to improve TCP performance. A misbehaving receiver might claim to to improve TCP performance. A misbehaving receiver might claim to
have received only original transmissions to convince the sender to have received only original transmissions to convince the sender to
undo congestion actions. Since retransmissions are sent without ECT, undo congestion actions. Since retransmissions are sent without ECT,
and thus no nonce, returning the correct nonce sum confirms that only and thus no nonce, returning the correct nonce sum confirms that only
original transmissions were received. original transmissions were received.
7. Interactions 7. Interactions
7.1 Path MTU Discovery 7.1 Path MTU Discovery
Because a receiver could reconstruct the original nonce from unmarked As described in RFC3168, use of the Don't Fragment bit with ECN is
fragments to conceal a mark on a fragment, senders SHOULD set the recommended. Receivers that receive unmarked fragments can
Don't Fragment bit and use Path MTU discovery. This contrasts with reconstruct the original nonce to conceal a marked fragment. The
[ECN-draft], which says that ECN-capable packets MAY have the DF bit ECN-nonce cannot protect against misbehaving receivers that conceal
set. Some senders may not be able to use Path MTU discovery marked fragments, so some protection is lost in situations where Path
successfully because ICMP messages are blocked by middle-boxes on the MTU discovery is disabled.
return path. The ECN-nonce cannot protect against misbehaving
receivers that receive marked fragments, so some protection is lost
by disabling Path MTU discovery.
When responding to a small path MTU, the sender will retransmit a When responding to a small path MTU, the sender will retransmit a
smaller frame in place of a larger one. Since these smaller packets smaller frame in place of a larger one. Since these smaller packets
are retransmissions, they will be ECN-incapable and bear no nonce. are retransmissions, they will be ECN-incapable and bear no nonce.
The sender should resynchronize on the first newly transmitted The sender should resynchronize on the first newly transmitted
packet. packet.
7.2 SACK 7.2 SACK
Selective acknowledgements allow receivers to acknowledge out of Selective acknowledgements allow receivers to acknowledge out of
skipping to change at page 10, line 36 skipping to change at page 11, line 47
to help improve the robustness of congestion control in the Internet. to help improve the robustness of congestion control in the Internet.
The modification retains the character and simplicity of existing ECN The modification retains the character and simplicity of existing ECN
signaling. It is also practical for deployment in the Internet. It signaling. It is also practical for deployment in the Internet. It
uses the ECT(0) and ECT(1) codepoints and one TCP header flag (as uses the ECT(0) and ECT(1) codepoints and one TCP header flag (as
well as CWR and ECN-Echo) and has simple processing rules. well as CWR and ECN-Echo) and has simple processing rules.
10. References 10. References
[ECN] "The ECN Web Page", URL "http://www- [ECN] "The ECN Web Page", URL "http://www-
nrg.ee.lbl.gov/floyd/ecn.html". nrg.ee.lbl.gov/floyd/ecn.html".
[ECN-draft] K. Ramakrishnan, S. Floyd, and D. Black. The addition of [RFC3168] K. Ramakrishnan, S. Floyd, and D. Black. The addition of
explicit congestion notification (ECN) to IP. draft-ietf-tsvwg- explicit congestion notification (ECN) to IP. RFC 3168, September,
ecn-04.txt 2001.
[Eifel-draft] R. Ludwig. The Eifel Algorithm for TCP. draft-ietf- [Eifel] R. Ludwig and R. Katz. The Eifel Algorithm: Making TCP Robust
tsvwg-tcp-eifel-alg-00.txt Against Spurious Retransmissions. Computer Communications Review,
January, 2000.
[B97] Bradner, S., "Key words for use in RFCs to Indicate Requirement [B97] Bradner, S., "Key words for use in RFCs to Indicate Requirement
Levels", BCP 14, RFC 2119, March 1997. Levels", BCP 14, RFC 2119, March 1997.
[Savage] S. Savage, N. Cardwell, D. Wetherall, T. Anderson. TCP [Savage] S. Savage, N. Cardwell, D. Wetherall, T. Anderson. TCP
congestion control with a misbehaving receiver. SIGCOMM CCR, October congestion control with a misbehaving receiver. SIGCOMM CCR, October
1999. 1999.
[Schneier] Bruce Schneier. Applied Cryptography, 2nd ed., 1996 [Schneier] Bruce Schneier. Applied Cryptography, 2nd ed., 1996
Acknowledgements Acknowledgements
This note grew out of research done by Stefan Savage, David Ely, This note grew out of research done by Stefan Savage, David Ely,
skipping to change at page 11, line 23 skipping to change at page 12, line 36
David Ely David Ely
Email: ely@cs.washington.edu Email: ely@cs.washington.edu
Computer Science and Engineering, 352350 Computer Science and Engineering, 352350
University of Washington University of Washington
Seattle, WA 98195-2350 Seattle, WA 98195-2350
Send comments by electronic mail to all three authors. Send comments by electronic mail to all three authors.
This draft was created in July 2001. This draft was created in October 2001.
It expires January 2002. It expires April 2002.
 End of changes. 

This html diff was produced by rfcdiff 1.23, available from http://www.levkowetz.com/ietf/tools/rfcdiff/