draft-ietf-tsvwg-tcp-nonce-00.txt   draft-ietf-tsvwg-tcp-nonce-01.txt 
Internet Engineering Task Force David Wetherall Internet Engineering Task Force Neil Spring
INTERNET DRAFT David Ely INTERNET DRAFT David Wetherall
draft-ietf-tsvwg-tcp-nonce-00.txt Neil Spring draft-ietf-tsvwg-tcp-nonce-01.txt David Ely
University of Washington University of Washington
January, 2001 July, 2001
Expires: July, 2001 Expires: January, 2001
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 a simple modification to ECN that protects This note describes the ECN-nonce, a modification to ECN that
against accidental or malicious concealment of marked packets from protects against accidental or malicious concealment of marked
the TCP sender. This is valuable because it improves the robustness packets from the TCP sender. It improves the robustness of
of congestion control by preventing receivers from exploiting ECN to congestion control by preventing receivers from exploiting ECN to
gaining an unfair share of the bandwidth. The mechanism uses a gain an unfair share of network bandwidth. The ECN-nonce uses the
slightly different encoding than the existing two ECN bits in the IP two ECT codepoints in the ECN field of the IP header, and requires a
header, and also requires one additional bit in the TCP header. It is new flag in the TCP header. It is computationally efficient for both
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 in turn would give the receivers a performance to the sender. This would give the receiver a performance advantage
advantage at the expense of competing connections that behave at the expense of competing connections that behave properly. More
properly. More generally, any device along the path (NAT box, generally, any device along the path (NAT box, firewall, QOS
firewall, QOS bandwidth shapers, and so forth) could remove bandwidth shapers, and so forth) could remove congestion marks with
congestion marks with impunity. impunity.
The above behaviors may or may not constitute a threat to the The above behaviors may or may not constitute a threat to the
operation of congestion control in the Internet. However, given of operation of congestion control in the Internet. However, given the
the central role of congestion control, we feel it is prudent to central role of congestion control, it is prudent to design the ECN
design the ECN signaling loop to be robust against as many threats as signaling loop to be robust against as many threats as possible. In
possible. In this way ECN can provide a clear incentive for this way, ECN can provide a clear incentive for improvement over the
improvement over the prior state-of-the-art without potential prior state-of-the-art without potential incentives for abuse. The
incentives for abuse. In this note, we show how this can be achieved ECN-nonce is a simple, efficient mechanism to eliminate the potential
while at the same time keeping the protocol simple and efficient. abuse of ECN.
Our signaling mechanism uses random one bit quantities to allow the
sender to verify that the receiver has implemented ECN signaling
correctly and that there is no other interference that conceals
marked (or dropped) packets in the signaling path. This provides
protection against both implementation errors and deliberate abuse.
In developing the nonce signaling mechanism we met the following
goals:
- It provides an additional check but does not change other aspects The ECN-nonce enables the sender to verify the correct behavior of
of ECN, and nor does it reduce the benefits of ECN for behaving the ECN receiver and that there is no other interference that
receivers. conceals marked (or dropped) packets in the signaling path. The ECN-
nonce protects against both implementation errors and deliberate
abuse. The ECN-nonce:
- It catches a misbehaving receiver with a high probability, and - catches a misbehaving receiver with a high probability, and never
never convicts an innocent receiver implicates an innocent receiver.
- It is cheap in terms of per-packet overhead (one TCP header bit - does not change other aspects of ECN, nor does it reduce the
more than the existing ECN mechanism) and processing benefits of ECN for behaving receivers.
requirements.
- It is simple and, to the best of our knowledge, not prone to - is cheap in both per-packet overhead (one TCP header flag) and
other attacks processing requirements.
The rest of this note describes the mechanism, first with an overview - is simple and, to the best of our knowledge, not prone to other
and then in terms of more detailed behavior at senders, routers and attacks.
receivers.
2. Overview of Solution We also note that use of the ECN-nonce has two additional benefits,
even when only drop-tail routers are used. First, packet drops
cannot be concealed from the sender. Second, it prevents optimistic
acknowledgements [Savage], in which TCP segments are acknowledged
before they have been received. These benefits also serve to
increase the robustness of congestion control from attacks. We do
not elaborate on these benefits in this draft.
Our scheme builds on the existing ECN-Echo and CWR signaling The rest of this draft describes the ECN-nonce. We present an
mechanism. Familiarity with ECN is assumed in this note. Also, for overview followed by detailed behavior at senders and receivers.
simplicity, we describe our scheme in one direction only, though it
is run in both directions in parallel.
In a nutshell, our approach is to detect misbehavior by attaching a The keywords MUST, MUST NOT, REQUIRED, SHALL, SHALL NOT, SHOULD,
random one bit nonce value to packets at the sender and having SHOULD NOT, RECOMMENDED, MAY, and OPTIONAL, when they appear in this
acknowledgments from the receiver echo the nonce information that is document, are to be interpreted as described in [RFC2119].
received. At routers, packet marking becomes the process of erasing
the nonce value. Therefore, once a packet has been marked by a
router, it cannot be unmarked by any party without successfully
guessing the value of the erased nonce. Thus receipt of correct nonce
information from the receiver provides the sender with a
probabilistic proof-of- receipt check for unmarked packets. The check
is used by the TCP sender to verify that the ECN-Echo bit is being
set correctly and that congestion indications in the form of marked
(or dropped) packets are not being concealed. Because one bit of
information is returned with each acknowledgement, senders have a
50-50 chance of catching a lying receiver every time they perform a
check. Because the check for each acknowledgement is an independent
trial it is highly likely that cheaters will be caught quickly if
there are repeated packet marks.
There are several areas of detail missing from the preceding high- 2. Overview
level description. We mention those areas to complete the overview.
First, the nonce values are echoed in the form of nonce sums. Each The ECN-nonce builds on the existing ECN-Echo and CWR signaling
nonce sum is carried in an acknowledgement, and represents the one mechanism. Familiarity with ECN [ECN] is assumed. For simplicity,
bit sum (XOR or parity) of nonces over the byte range represented by we describe the ECN-nonce in one direction only, though it is run in
the acknowledgement. To understand why the sum is used, rather than both directions in parallel.
individual echoes, consider the following argument. If every packet
were reliably ACKed, then the nonce carried in the unmarked packet
could simply be echoed. This would probabilistically prove to the
sender that the receiver received the packet and the packet was
unmarked. However, ACKs are not carried across the network reliably,
and not every packet is ACKed. In this case, the sender cannot
distinguish a lost ACK from one that was never sent in order to
conceal a marked packet. It would require additional mechanism,
beyond that used in TCP, to convey the nonce bits reliably. Instead,
we send the nonce sum that corresponds to the cumulative ACK. This
sum prevents individual marked packets from being concealed by not
acknowledging them. Note that because they are both one bit
quantities, the sum is no easier to guess than the individual nonces.
Second, resynchronization of the sender and receiver sums is needed The ECN protocol for TCP remains unchanged, except for the definition
after congestion has occurred and packets have been marked. When of a new field in the TCP header. As in [ECN], ECT(0) or ECT(1)
packets are marked, the nonce is cleared, and the sum of the nonces (ECN-Capable Transport) is set in the ECN field of the IP header on
at the receiver will no longer reflect the sum at the sender. While outgoing packets. Congested routers change this field to CE
this is conceptually fixed by having the receiver send a series of (Congestion Experienced). When TCP receivers notice CE, the ECE
partial sums for the ranges of unmarked packets that it has received, (ECN-Echo) flag is set in subsequent acknowledgements until receiving
this solution is clumsy because the required range information is not a CWR (Congestion Window Reduced) flag. The CWR flag is sent on new
already being sent. Fortunately, there is a simple solution that data whenever the sender reacts to congestion.
does not require range information because ECN congestion indications
do not need to indicate the particular packets that were marked. We
observe that once nonces have been lost, the difference between
sender and receiver nonce sums will be fixed until there is further
loss. This means that it is possible to resynchronize the sender and
receiver after congestion by having the sender set its nonce sum to
that of the receiver. Because congestion indications do not need to
be conveyed more frequently than once per round trip, we suspend
checking while the CWR signal is being delivered and acknowledged by
the receiver. We reset the sender nonce sum to the receiver sum when
new data is acknowledged. This scheme is simple and has the benefit
that the receiver is not explicitly involved in the re-
synchronization process.
Third, we need to reconcile the nonces that are sent with packet with The ECN-nonce adds to this protocol, and enables the receiver to
acknowledgements that cover byte ranges. Acknowledged byte boundaries demonstrate to the sender that segments being acknowledged were
need not match the transmitted boundaries, and during retransmissions received unmarked. A random one-bit value (a nonce) is encoded in
information can be resent with different byte boundaries. To handle the two ECT codepoints. The one-bit sum of these nonces is returned
these factors, we compute nonces and nonce sums using an underlying in a TCP header flag, the nonce sum (NS) bit. Packet marking erases
mapping of byte ranges to nonce values. Both sender and receiver the nonce value in the ECT codepoints because CE overwrites both ECN
understand this mapping, and can convert to and from the nonces IP header bits. Since each nonce is required to calculate the sum,
carried on individual packets. the correct nonce sum implies receipt of only unmarked packets. Not
only are receivers prevented from concealing marked packets, middle-
boxes along the network path cannot unmark a packet without
successfully guessing the value of the original nonce.
The next sections describe the detailed behavior of senders, routers The sender can verify the nonce sum returned by the receiver to
and receivers. We start with sender transmit behavior, and work our ensure that congestion indications in the form of marked (or dropped)
way around the ECN signaling loop until we arrive back at sender packets are not being concealed. Because the nonce sum is only one
receive behavior. Comments in parenthesis highlight the changes bit long, senders have a 50-50 chance of catching a lying receiver
between the nonce mechanism and the existing ECN specification. whenever an acknowledgement conceals a mark. Because each
acknowledgement is an independent trial, cheaters will be caught
quickly if there are repeated congestion signals.
3. Sender Behavior (Transmit) The following paragraphs describe aspects of the ECN-nonce protocol
in greater detail.
Senders in our scheme manage CWR and ECN-Echo as before. In addition Each acknowledgement carries a nonce sum, which is the one bit sum
they must place nonces on packets as they are transmitted and check (exclusive-or, or parity) of nonces over the byte range represented
the validity of the nonce sums on packets as they are received. This by the acknowledgement. The sum is used because not every packet is
section describes the transmit process. acknowledged individually, nor are packets acknowledged reliably. If
a sum were not used, the nonce in an unmarked packet could be echoed
to prove to the sender that the individual packet arrived unmarked.
However, since these acks are not reliably delivered, the sender
could not distinguish a lost ACK from one that was never sent in
order to conceal a marked packet. The nonce sum prevents individual
marked packets from being concealed by not acknowledging them.
Because the nonce and nonce sum are both one bit quantities, the sum
is no easier to guess than the individual nonces. We show the nonce
sum calculation below in Figure 1.
To place a one bit nonce value on every IP packet requires first of Sender Receiver
all a way to encode these bits in IP packets. We use the following initial sum = 1
encoding of the ECN bits to identify different packet states. This -- 1:4 ECT(0) --> NS = 1 + 0(1:4) = 1(:4)
encoding must be understood by all ECN capable senders, routers, and <- ACK 4, NS=1 ---
receivers in our scheme. (The second state below is currently unused -- 4:8 ECT(1) --> NS = 1(:4) + 1(4:8) = 0(:8)
in the existing ECN specification, while the other states retain <- ACK 8, NS=0 ---
their existing meanings.) -- 8:12 ECT(1) -> NS = 0(:8) + 1(8:12) = 1(:12)
<- ACK 12, NS=1 --
-- 12:16 ECT(1) -> NS = 1(:12) + 1(12:16) = 0(:16)
<- ACK 16, NS=0 --
Figure 1: The calculation of nonce sums at the receiver.
00 = ECN incapable After congestion has occurred and packets have been marked or lost,
resynchronization of the sender and receiver nonce sums is needed.
When packets are marked, the nonce is cleared, and the sum of the
nonces at the receiver will no longer match the sum at the sender.
Once nonces have been lost, the difference between sender and
receiver nonce sums is constant until there is further loss. This
means that it is possible to resynchronize the sender and receiver
after congestion by having the sender set its nonce sum to that of
the receiver. Because congestion indications do not need to be
conveyed more frequently than once per round trip, the sender
suspends checking while the CWR signal is being delivered and resets
its nonce sum to the receiver's when new data is acknowledged. This
has the benefit that the receiver is not explicitly involved in the
re-synchronization process. The resynchronization process is shown
in Figure 2 below. Note that the nonce sum returned in ACK 12 (NS=0)
differs from that in the previous example (NS=1), and it continues to
differ for ACK 16.
10 = ECN capable, unmarked (nonce = 0) Sender Receiver
initial sum = 1
-- 1:4 ECT(0) -> NS = 1 + 0(1:4) = 1(:4)
<- ACK 4, NS=1 --
-- 4:8 ECT(1) -> CE -> NS = 1(:4) + ?(4:8) = 1(:8)
<- ACK 8, ECE NS=1 --
-- 8:12 ECT(1), CWR -> NS = 1(:8) + 1(8:12) = 0(:12)
<- ACK 12, NS=0 --
-- 12:16 ECT(1) -> NS = 0(:12) + 1(12:16) = 1(:16)
<- ACK 16, NS=1 --
Figure 2: The calculation of nonce sums at the receiver when a
packet (4:8) is marked. The receiver may calculate the wrong
nonce sum when the original nonce information is lost after a
packet is marked.
01 = ECN capable, unmarked (nonce = 1) Third, we need to reconcile that nonces are sent with packets but
acknowledgements cover byte ranges. Acknowledged byte boundaries
need not match the transmitted boundaries, and information can be
retransmitted in packets with different byte boundaries. However,
ECN is disabled for retransmissions, so can carry no nonce. Since
retransmissions are associated with congestion events, nonce checking
is suspended until after CWR is acknowledged and the congestion event
is over.
11 = ECN capable, marked (nonce lost) The next sections describe the detailed behavior of senders, routers
and receivers, starting with sender transmit behavior, then around
the ECN signaling loop, and finish with sender acknowledgement
processing.
Next, we require a simple way to map nonces to transmitted TCP 3. Sender Behavior (Transmit)
packets in a manner that is compatible with checking the nonce sum on
received TCP acknowledgements. This is complicated by several
factors. Nonces are sent per packet but acknowledgements cover byte
ranges that do not necessarily correspond to the original packet
ranges; this can depend on implementation buffering strategies. In
the case of retransmissions, the boundary of retransmitted packets
need not correspond to the original transmissions either (because of
path MTU changes, retransmission batching, and so forth). Finally,
there is ambiguity at the sender as to whether the original or
retransmitted packet was received. It is important that our
implementation behave correctly even in these rare cases so that a
receiver is never incorrectly labeled as misbehaving.
We associate nonce values with byte ranges instead of individual Senders manage CWR and ECN-Echo as before. In addition, they must
packets to avoid these difficulties. Starting from the initial place nonces on packets as they are transmitted and check the
sequence number, each block of SMSS bytes (the maximum segment size) validity of the nonce sums in acknowledgments as they are received.
in the TCP byte stream is associated with a single pseudorandom nonce This section describes the transmit process.
bit. The byte range of the packet determines what nonce value it
will carry. If the packet, either original or a retransmission, spans
multiple blocks, we use the block in which the final byte of the
packet resides to determine which nonce value to transmit with the
packet. A series of small packets will carry the same nonce value
until an entire block's worth of SMSS bytes has been transmitted.
This is a useful tradeoff because sending partial packets makes a
flow less likely to cause congestion. Since no packet can carry more
than SMSS bytes, each block's nonce bit will be carried in at least
one packet.
The following table provides an example of how we decompose a byte To place a one bit nonce value on every ECN-capable IP packet, the
stream into blocks and how we assign nonce values to each block sender uses the two ECT codepoints: ECT(0) represents a nonce of 0,
(assuming a block size of 1460 bytes): and ECT(1) a nonce of 1. As in ECN, retransmissions are not ECN-
capable, so carry no nonce.
------------------------------------------------------- The sender maintains a mapping from each packet's end sequence number
| Bytes: | 1...1460 | 1461...2920 | 2921 ... 4380 | to the expected nonce sum (not the nonce placed in the original
------------------------------------------------------- transmission) in the acknowledgement bearing that sequence number.
| Nonce: | 1 | 1 | 0 |
-------------------------------------------------------
| Nonce Sum: | 1 | 0 | 1 |
-------------------------------------------------------
4. Router Behavior 4. Router Behavior
Routers must be able to identify packets sent by ECN capable Routers behave as specified in [ECN-draft]. By marking packets to
transports and mark them if indicated by active queue management. To signal congestion, the original value of the nonce, in ECT(0) or
mark packets, routers change either of the unmarked states to the ECT(1), is removed. Neither the receiver nor any other party can
single marked state. (The operation of marking has changed only in unmark the packet without successfully guessing the value of the
that routers now need to recognize two states as meaning not marked original nonce.
and so is still straightforward.) This erases the state of the
original nonce carried with the packet, which is key to our scheme.
Neither the receiver nor any other party can now unmark the packet
without successfully guessing the value of the original nonce.
5. Receiver Behavior (Receive and Transmit) 5. Receiver Behavior (Receive and Transmit)
In addition to distinguishing marked and unmarked packets and setting ECN-nonce receivers maintain the nonce sum as in-order packets arrive
the ECN- Echo flag as before, receivers in our scheme maintain a and return the current nonce sum in each acknowledgement. Receiver
nonce sum as packets arrive, and return the sum that corresponds to a behavior is otherwise unchanged from [ECN-draft].
particular acknowledgment with the acknowledgment.
To maintain the nonce sum, receivers use the same mapping as the As packets are removed from the queue of out-of-order packets to be
sender to convert the nonces carried in unmarked packets to the acknowledged, the nonce is recovered from the IP header. The nonce
nonces of the underlying blocks. These nonce values are summed over is added to the current nonce sum as the acknowledgement sequence
the byte range covered by the acknowledgement. Computing this sum number is advanced for the recent packet.
correctly when packets of size SMSS are sent requires that all
packets up to the one acknowledged be received. New sums are computed
by taking the old value and XORing it with a new nonce. That is, the
sum is also a one bit quantity, and old nonce state does not need to
be maintained.
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.
Returning the nonce sum corresponding to a given acknowledgement is Returning the nonce sum corresponding to a given acknowledgement is
straightforward. It is carried in a single bit in the TCP header. straightforward. It is carried in a single "NS" (Nonce Sum) bit in
(This bit is in addition the CWR and ECN-Echo bits and would require the TCP header. This bit is adjacent to the CWR and ECN-Echo bits,
one of the reserved bits to be allocated.) set as Bit 7 in the Reserved field of the TCP header, as shown below:
These nonce sums are checked for validity at the sender, as described
below. 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| | | C | E | U | A | P | R | S | F |
| Header Length | Reserved | W | C | R | C | S | S | Y | I |
| | | R | E | G | K | H | T | N | N |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
Figure 3: The old definition of bytes 13 and 14 of the TCP Header.
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| | | N | C | E | U | A | P | R | S | F |
| Header Length | Reserved | S | W | C | R | C | S | S | Y | I |
| | | | R | E | G | K | H | T | N | N |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
Figure 4: The new definition of bytes 13 and 14 of the TCP Header.
The initial nonce sum is 1, and is included in the SYN/ACK and ACK of
the three way TCP handshake. This allows the other endpoint to infer
nonce support, but is not a negotiation, in that the receiver of the
SYN/ACK need not check if NS is set to decide whether to set NS in
the subsequent ACK.
6. Sender Behavior (Receive) 6. Sender Behavior (Receive)
This section completes the description of sender behavior by This section completes the description of sender behavior by
describing how senders check the validity of the nonce sums. describing how senders check the validity of the nonce sums.
Checking is straightforward and is performed every time an The nonce sum is checked when an acknowledgement of new data is
acknowledgement is received, except during congestion recovery. Given received, except during congestion recovery when additional ECN-Echo
the byte range covered by an acknowledgement and the mapping between signals would be ignored. Checking consists of comparing the correct
bytes and nonces, the sender is able to compute the correct nonce nonce sum stored in a buffer to that carried in the acknowledgement,
sum. Minimal sender state is needed to do this because old nonce with a correction described in the following subsection.
values can be discarded as acknowledgments and the sum advance.
Checking consists of simply comparing the correct nonce sum and that
carried in the acknowledgement.
If ECN-Echo is not set, the receiver claims to have received no If ECN-Echo is not set, the receiver claims to have received no
marked packets, and can therefore compute the correct nonce sum. To marked packets, and can therefore compute and return the correct
cheat, the receiver must successfully guess the sum of the nonces nonce sum. To conceal a mark, the receiver must successfully guess
that it did not receive (because at least one packet was marked and the sum of the nonces that it did not receive, because at least one
the corresponding nonce was erased). Provided the individual nonces packet was marked and the corresponding nonce was erased. Provided
are equally likely to be 0 or 1, their sum is equally likely to be 0 the individual nonces are equally likely to be 0 or 1, their sum is
or 1. In other words, any guess is equally likely to be wrong and equally likely to be 0 or 1. In other words, any guess is equally
has a 50-50 chance of being caught by the sender. Because each likely to be wrong and has a 50-50 chance of being caught by the
acknowledgement (that covers a new block) is an independent trial, a sender. Because each new acknowledgement is an independent trial, a
cheating receiver is highly likely to be caught after a small number cheating receiver is likely to be caught after a small number of
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,
During this recovery process, the sum may be incorrect because one or as in [ECN-draft]. During this recovery process, the sum may be
more nonces were not received. This does not matter during recovery, incorrect because one or more nonces were not received. This does
because TCP invokes congestion mechanisms at most once per RTT, not matter during recovery, because TCP invokes congestion mechanisms
whether there are one or more losses during that period. However, at most once per RTT, whether there are one or more losses during
after recovery, it is necessary to re-synchronize the sender and that period.
6.1 Resynchronization After Loss or Mark
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.
If might be possible to send the missing nonces to the receiver, but When the receiver's sum is incorrect, it will remain incorrect until
this would be cumbersome because TCP lacks the mechanism to do so further loss.
conveniently. Instead, we observe that if there are no more marked This leads to a simple re-synchronization mechanism where the sender
packets, the sender and receiver sums should differ by a constant resets its nonce sum to that of the receiver when it receives an
amount. This leads to a simple re-synchronization mechanism where the acknowledgment for new data sent after the congestion window was
sender resets its nonce sum to that of the receiver when it receives reduced. When responding to explicit congestion signals, this will
an acknowledgment for new data sent after the congestion window was be the first acknowledgement without the ECN-Echo flag set: the
reduced. In most instances, this will be the first acknowledgement acknowledgement of the packet containing the CWR flag.
without the ECN-Echo flag set.
A separate issue is the penalty for misbehavior that is caught by Sender Receiver
checking. During normal operation, both with and without packet initial sum = 1
marks and drops, no misbehavior will be uncovered unless some party -- 1:4 ECT(0) -> NS = 1 + 0(1:4) = 1(:4)
after the marking router is behaving incorrectly. A simple remedy in <- ACK 4, NS=1 --
this case would be to disable ECN at the sender, that is, not mark -- 4:8 ECT(1) -> LOST
packets as ECN capable. This simultaneously deprives the receiver of -- 8:12 ECT(1) -> nonce sum calculation deferred
the benefits of ECN and relieves the sender of the need to monitor until in-order data received
the receiver. However, an additional consideration is that the nonce <- ACK 4, NS=0 --
checking mechanism provides robustness beyond checking that marked -- 12:16 ECT(1) -> nonce sum calculation deferred
<- ACK 4, NS=0 --
-- 4:8 retransmit -> NS = 1(:4) + ?(4:8) +
1(8:12) + 1(12:16) = 1(:16)
<- ACK 16, NS=1 --
-- 16:20 ECT(1) CWR ->
<- ACK 20, NS=0 -- NS = 1(:16) + 1(16:20) = 0(:20)
Figure 5: The calculation of nonce sums at the receiver when a
packet is lost, and resynchronization after loss. The nonce sum
is not changed until the cumulative acknowledgement is advanced.
In practice, resynchronization can be accomplished by storing a bit
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
zero otherwise. This synchronization offset bit can then be used in
the comparison between expected nonce sum and received nonce sum.
The sender should ignore the nonce sum returned on any
acknowledgements bearing the ECN-echo flag.
Finally, in ECN, senders can choose not to indicate ECN capability on
some packets for any reason. An ECN-nonce sender must resynchronize
after sending such ECN-incapable packets, as though a CWR had been
sent with the first new data after the ECN-incapable packets. The
sender loses protection for any unacknowledged packets until
resynchronization occurs.
6.2 Sender Behavior - Incorrect Nonce Received
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
handled uniformly by senders.
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
the connection, place it in a lower-priority queue, or cease setting
ECT in outgoing segments.
If the received nonce sum has been set in a previous acknowledgement,
the sender might infer that a network device has interfered with
correct ECN signaling between ECN-nonce supporting endpoints. The
minimum response to an incorrect nonce is the same as the response to
a received ECE. However, to compensate for hidden congestion
signals, the sender might reduce the congestion window to one segment
and cease setting ECT in outgoing segments. An incorrect nonce sum is
a sign of misbehavior or error between ECN-nonce supporting
endpoints.
6.2.1 Using the ECN-nonce to Protect Against Other Misbehaviors
The ECN-nonce can provide robustness beyond checking that marked
packets are signaled to the sender. It also ensures that dropped packets are signaled to the sender. It also ensures that dropped
packets cannot be concealed from the sender (because their nonces packets cannot be concealed from the sender (because their nonces
have been lost). Drops could potentially be concealed by a faulty TCP have been lost). Drops could potentially be concealed by a faulty
implementation, certain attacks, or even a hypothetical a TCP TCP implementation, certain attacks, or even a hypothetical TCP
accelerator willing to gamble that it can either successfully ``fast accelerator. Such an accelerator could gamble that it can either
start'' to a preset bandwidth quickly, retry with another connection, successfully ``fast start'' to a preset bandwidth quickly, retry with
or provide reliability at the application level. If robustness another connection, or provide reliability at the application level.
against these faults is considered valuable (as opposed to simply If robustness against these faults is also desired, then the ECN-
detecting a faulty ECN implementation) then it is not clear that the nonce should not be disabled. Instead, reducing the congestion
nonce mechanism should be turned off. Instead, a penalty such as window to one, or using a low-priority queue, would penalize faulty
reducing the congestion window by a factor of 4 may be preferable. operation while providing continued checking.
This would provide continued checking while punishing faulty
operation. Luckily, this issue is separate from the checking
mechanism and does not need to be handled uniformly by senders.
7. Conclusion The ECN-nonce can also detect misbehavior in Eifel [Eifel-draft], a
recently proposed mechanism for removing the retransmission ambiguity
to improve TCP performance. A misbehaving receiver might claim to
have received only original transmissions to convince the sender to
undo congestion actions. Since retransmissions are sent without ECT,
and thus no nonce, returning the correct nonce sum confirms that only
original transmissions were received.
We have described a simple modification to the ECN signaling 7. Interactions
mechanism that improves its robustness by preventing receivers from 7.1 Path MTU Discovery
concealing marked (or dropped) packets. The intent of this work is to
help improve the robustness of congestion control in the Internet. Because a receiver could reconstruct the original nonce from unmarked
The modification is retains the character and simplicity of existing fragments to conceal a mark on a fragment, senders SHOULD set the
ECN signaling. It is also practical for deployment in the Internet. Don't Fragment bit and use Path MTU discovery. This contrasts with
It requires two bits in the IP header (ECT and CE with a slightly [ECN-draft], which says that ECN-capable packets MAY have the DF bit
different encoding) and one additional bit in the TCP header (as well set. Some senders may not be able to use Path MTU discovery
as CWR and ECN-Echo) and has simple processing rules. successfully because ICMP messages are blocked by middle-boxes on the
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
smaller frame in place of a larger one. Since these smaller packets
are retransmissions, they will be ECN-incapable and bear no nonce.
The sender should resynchronize on the first newly transmitted
packet.
7.2 SACK
Selective acknowledgements allow receivers to acknowledge out of
order segments as an optimization. It is not necessary to modify the
selective acknowledgment option to fit per-range nonce sums, because
SACKs cannot be used by a receiver to hide a congestion signal. The
nonce sum corresponds only to the data acknowledged by the cumulative
acknowledgement.
7.3 IPv6
Although the IPv4 header is protected by a checksum, this is not the
case with IPv6, making undetected bit errors in the IPv6 header more
likely. Bit errors that compromise the integrity of the congestion
notification fields may cause an incorrect nonce to be received, and
an incorrect nonce sum to be returned.
8. Security Considerations
The random one-bit nonces need not be from a cryptographic-quality
pseudo-random number generator. A strong random number generator
would compromise performance. Consequently, the sequence of random
nonces should not be used for any other purpose.
Conversely, the pseudo-random bit sequence should not be generated by
a linear feedback shift register [Schneier], or similar scheme that
would allow an adversary who has seen several previous bits to infer
the generation function and thus its future output.
Although the ECN-nonce protects against concealment of congestion
signals and optimistic acknowledgement, it provides no additional
protection for the integrity of the connection.
9. IANA Considerations
The Nonce Sum (NS) is carried in a reserved TCP header bit that must
be allocated. This document describes the use of Bit 7, adjacent to
the other header bits used by ECN.
The codepoint for the NS flag in the TCP header is specified by the
Standards Action of this RFC, as is required by RFC 2780. When this
draft is published as an RFC, IANA should add the following to the
registry for "TCP Header Flags":
RFC xxx defines bit 7 from the Reserved field to be used for the
Nonce Sum, as follows:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| | | N | C | E | U | A | P | R | S | F |
| Header Length | Reserved | S | W | C | R | C | S | S | Y | I |
| | | | R | E | G | K | H | T | N | N |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
TCP Header Flags
Bit Name Reference
--- ---- ---------
7 NS (Nonce Sum) [RFC xxx]
10. Conclusion
The ECN-nonce is a simple modification to the ECN signaling mechanism
that improves ECN's robustness by preventing receivers from
concealing marked (or dropped) packets. The intent of this work is
to help improve the robustness of congestion control in the Internet.
The modification retains the character and simplicity of existing ECN
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
well as CWR and ECN-Echo) and has simple processing rules.
10. References
[ECN] "The ECN Web Page", URL "http://www-
nrg.ee.lbl.gov/floyd/ecn.html".
[ECN-draft] K. Ramakrishnan, S. Floyd, and D. Black. The addition of
explicit congestion notification (ECN) to IP. draft-ietf-tsvwg-
ecn-04.txt
[Eifel-draft] R. Ludwig. The Eifel Algorithm for TCP. draft-ietf-
tsvwg-tcp-eifel-alg-00.txt
[B97] Bradner, S., "Key words for use in RFCs to Indicate Requirement
Levels", BCP 14, RFC 2119, March 1997.
[Savage] S. Savage, N. Cardwell, D. Wetherall, T. Anderson. TCP
congestion control with a misbehaving receiver. SIGCOMM CCR, October
1999.
[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,
David Wetherall, Tom Anderson and Neil Spring. We are grateful for David Wetherall, Tom Anderson and Neil Spring. We are very grateful
feedback from Sally Floyd. for feedback and assistance from Sally Floyd.
Authors' Addresses Authors' Addresses
Neil Spring
Email: nspring@cs.washington.edu
David Wetherall David Wetherall
Email: djw@cs.washington.edu Email: djw@cs.washington.edu
Phone +1 (206) 616 4367 Phone +1 (206) 616 4367
David Ely David Ely
Email: ely@cs.washington.edu Email: ely@cs.washington.edu
Neil Spring
Email: nspring@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 January 2001. This draft was created in July 2001.
It expires July 2001. It expires January 2002.
 End of changes. 

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