draft-moncaster-tcpm-rcv-cheat-00.txt   draft-moncaster-tcpm-rcv-cheat-01.txt 
TCP Maintenance and Minor T. Moncaster TCP Maintenance and Minor T. Moncaster
Extensions BT Extensions BT
Internet-Draft B. Briscoe Internet-Draft B. Briscoe
Intended status: Standards Track BT & UCL Intended status: Standards Track BT & UCL
Expires: August 24, 2007 A. Jacquet Expires: December 7, 2007 A. Jacquet
BT BT
February 20, 2007 June 5, 2007
A TCP Test to Allow Senders to Identify Receiver Cheating A TCP Test to Allow Senders to Identify Receiver Non-Compliance
draft-moncaster-tcpm-rcv-cheat-00 draft-moncaster-tcpm-rcv-cheat-01
Status of this Memo Status of this Memo
By submitting this Internet-Draft, each author represents that any By submitting this Internet-Draft, each author represents that any
applicable patent or other IPR claims of which he or she is aware 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 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. aware will be disclosed, in accordance with Section 6 of BCP 79.
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 37 skipping to change at page 1, line 37
and may be updated, replaced, or obsoleted by other documents at any and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference time. It is inappropriate to use Internet-Drafts as reference
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.
This Internet-Draft will expire on August 24, 2007. This Internet-Draft will expire on December 7, 2007.
Copyright Notice Copyright Notice
Copyright (C) The IETF Trust (2007). Copyright (C) The IETF Trust (2007).
Abstract Abstract
The honesty of TCP senders and receivers has become a major concern The TCP protocol relies on receivers sending accurate and timely
to the Internet community. Currently, TCP senders rely on receiver feedback to the sender. Currently the sender has no means to verify
honesty so they can correctly react to network congestion. Such that a receiver is correctly sending this feedback according to the
honesty cannot be taken for granted. Receivers may conceal dropped protocol. A receiver that is non-compliant has the potential to
packets to prevent their flow being subject to a congestion response disrupt a sender's resource allocation, increasing its transmission
or may acknowledge data optimistically to get a higher bandwidth. rate on that connection which in turn could adversely affect the
This document introduces a simple two-stage test of receiver honesty. network itself. This document presents a two stage test process that
Once a receiver fails the first stage it can be subjected to the can be used to identify whether a receiver is non-compliant. The
second stage test that conclusively proves cheating. The performance tests enshrine the principle that one shouldn't attribute to malice
hit of the first stage is very slight compared to the second. So, that which may be accidental. The first stage test causes minimum
although the first stage is not decisive, it selects which receivers impact to the receiver but raises a suspicion of non-compliance. The
are acting suspiciously enough to warrant the second stage. This second stage test can then be used to verify that the receiver is
specification does not modify the TCP protocol - the tests only non-compliant. This specification does not modify the core TCP
require a change to sender implementations. protocol - the tests can either be implemented as a test suite or as
a stand-alone test through a simple modification to the sender
implementation.
Status Status
By submitting this Internet-Draft, each author represents that any By submitting this Internet-Draft, each author represents that any
applicable patent or other IPR claims of which he or she is aware 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 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. aware will be disclosed, in accordance with Section 6 of BCP 79.
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
other groups may also distribute working documents as Internet- other groups may also distribute working documents as Internet-
Drafts. Internet-Drafts are draft documents valid for a maximum of Drafts. Internet-Drafts are draft documents valid for a maximum of
six months and may be updated, replaced, or obsoleted by other six months and may be updated, replaced, or obsoleted by other
documents at any time. It is inappropriate to use Internet-Drafts as documents at any time. It is inappropriate to use Internet-Drafts as
reference material or to cite them other than as "work in progress." reference 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. The list of Internet- http://www.ietf.org/ietf/1id-abstracts.txt. The list of Internet-
Draft Shadow Directories can be accessed at Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html. http://www.ietf.org/shadow.html.
Changes from previous drafts (to be removed by the RFC Editor)
From -00 to -01:
Draft rewritten to emphasise testing for non-compliance. Some
changes to protocol to remove possible unwanted interactions with
other TCP variants. Sections added on comparison of solutions and
alternative uses of test.
Table of Contents Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 4 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 5
2. Requirements notation . . . . . . . . . . . . . . . . . . . . 5 2. Requirements notation . . . . . . . . . . . . . . . . . . . . 7
3. The Problems . . . . . . . . . . . . . . . . . . . . . . . . . 6 3. The Problems . . . . . . . . . . . . . . . . . . . . . . . . . 7
3.1. Concealing Lost Segments . . . . . . . . . . . . . . . . . 6 3.1. Concealing Lost Segments . . . . . . . . . . . . . . . . . 7
3.2. Optimistic Acknowledgements . . . . . . . . . . . . . . . 7 3.2. Optimistic Acknowledgements . . . . . . . . . . . . . . . 9
4. Requirements for a robust solution . . . . . . . . . . . . . . 9 4. Requirements for a robust solution . . . . . . . . . . . . . . 11
5. Existing Proposals . . . . . . . . . . . . . . . . . . . . . . 10 5. Existing Proposals . . . . . . . . . . . . . . . . . . . . . . 12
5.1. Randomly Skipped Segments . . . . . . . . . . . . . . . . 10 5.1. Randomly Skipped Segments . . . . . . . . . . . . . . . . 12
5.2. The ECN nonce . . . . . . . . . . . . . . . . . . . . . . 10 5.2. The ECN nonce . . . . . . . . . . . . . . . . . . . . . . 12
5.3. A transport layer nonce . . . . . . . . . . . . . . . . . 11 5.3. A transport layer nonce . . . . . . . . . . . . . . . . . 13
6. The Test for Receiver Cheating . . . . . . . . . . . . . . . . 12 6. The Test for Receiver Cheating . . . . . . . . . . . . . . . . 14
6.1. Solution Overview . . . . . . . . . . . . . . . . . . . . 12 6.1. Solution Overview . . . . . . . . . . . . . . . . . . . . 14
6.2. Probabilistic Testing . . . . . . . . . . . . . . . . . . 12 6.2. Probabilistic Testing . . . . . . . . . . . . . . . . . . 14
6.2.1. Performing the Probabilistic Test . . . . . . . . . . 13 6.2.1. Performing the Probabilistic Test . . . . . . . . . . 15
6.2.2. Assessing the Probabilistic Test . . . . . . . . . . . 15 6.2.2. Assessing the Probabilistic Test . . . . . . . . . . . 17
6.2.3. RTT Measurement Considerations . . . . . . . . . . . . 15 6.2.3. RTT Measurement Considerations . . . . . . . . . . . . 17
6.2.4. Protocol Details for the Probabilistic Test . . . . . 17 6.2.4. Negative Impacts of the Test . . . . . . . . . . . . . 19
6.3. Deterministic Testing . . . . . . . . . . . . . . . . . . 18 6.2.5. Protocol Details for the Probabilistic Test . . . . . 19
6.3.1. Performing the Deterministic Test . . . . . . . . . . 18 6.3. Deterministic Testing . . . . . . . . . . . . . . . . . . 21
6.3.2. Assessing the Deterministic Test . . . . . . . . . . . 19 6.3.1. Performing the Deterministic Test . . . . . . . . . . 21
6.3.3. Protocol Details for the Deterministic Test . . . . . 19 6.3.2. Assessing the Deterministic Test . . . . . . . . . . . 21
6.4. Responding to Cheating . . . . . . . . . . . . . . . . . . 20 6.3.3. Protocol Details for the Deterministic Test . . . . . 22
6.4. Responding to Non-Compliance . . . . . . . . . . . . . . . 22
6.5. Possible Interactions With Other TCP Features . . . . . . 23
6.5.1. TCP Secure . . . . . . . . . . . . . . . . . . . . . . 23
6.5.2. Nagle Algorithm . . . . . . . . . . . . . . . . . . . 23
6.5.3. Delayed Acknowledgements . . . . . . . . . . . . . . . 23
6.6. Possible Consequences of the Tests . . . . . . . . . . . . 23
7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 20 7. Comparison of the Different Solutions . . . . . . . . . . . . 24
8. Security Considerations . . . . . . . . . . . . . . . . . . . 20 8. Alternative Uses of the Test . . . . . . . . . . . . . . . . . 25
9. Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . 21 9. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 26
10. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 22 10. Security Considerations . . . . . . . . . . . . . . . . . . . 26
11. Comments Solicited . . . . . . . . . . . . . . . . . . . . . . 22 11. Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . 27
12. References . . . . . . . . . . . . . . . . . . . . . . . . . . 22 12. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 28
12.1. Normative References . . . . . . . . . . . . . . . . . . . 22 13. Comments Solicited . . . . . . . . . . . . . . . . . . . . . . 28
12.2. Informative References . . . . . . . . . . . . . . . . . . 22
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 23 14. References . . . . . . . . . . . . . . . . . . . . . . . . . . 28
Intellectual Property and Copyright Statements . . . . . . . . . . 25 14.1. Normative References . . . . . . . . . . . . . . . . . . . 28
14.2. Informative References . . . . . . . . . . . . . . . . . . 28
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 29
Intellectual Property and Copyright Statements . . . . . . . . . . 31
1. Introduction 1. Introduction
This document specifies how a TCP sender implementation can be This document specifies how a TCP sender implementation can be
modified to detect a cheating receiver. It uses the standard wire modified to detect a non-compliant receiver. It uses the standard
protocol and protocol semantics of basic TCP [RFC0793] without wire protocol and protocol semantics of basic TCP [RFC0793] without
modification. modification.
When any network resource (e.g. a link) becomes congested, the When any network resource (e.g. a link) becomes congested, the
congestion control protocol [RFC2581] within TCP/IP relies on the congestion control protocol [RFC2581] within TCP/IP relies on the
voluntary compliance of all senders and all receivers that are using voluntary compliance of all senders and all receivers that are using
paths through the resource. The protocol expects all receivers to paths through the resource. The protocol expects all receivers to
correctly feed back congestion information and it expects each sender correctly feed back congestion information and it expects each sender
to respond by backing off its rate. to respond by backing off its rate in response to this information.
Over the past several years the Internet has become increasingly Over the past several years the Internet has become increasingly
adversarial. Self-interested or malicious parties may produce non- adversarial. Self-interested or malicious parties may produce non-
compliant protocol implementations if it is to their advantage, or to compliant protocol implementations if it is to their advantage, or to
the disadvantage of their chosen victims. To enforce congestion the disadvantage of their chosen victims. To enforce congestion
control when no-one can be trusted is extremely hard within the control when trust can not be taken for granted is extremely hard
current Internet architecture. This specification deals with one within the current Internet architecture. This specification deals
specific case: where a TCP sender is well-behaved and wants to ensure with one specific case: where a TCP sender is TCP compliant and wants
its receivers behave as well. to ensure its receivers are compliant as well.
Simple attacks have been published showing that TCP receivers can Simple attacks have been published showing that TCP receivers can
manipulate feedback to fool TCP senders into massively exceeding the manipulate feedback to fool TCP senders into massively exceeding the
compliant rate [Savage]. Such receivers might want to make senders compliant rate [Savage]. Such receivers might want to make senders
unwittingly launch a denial of service attack on other flows sharing unwittingly launch a denial of service attack on other flows sharing
part of the path between them [Sherwood]. But a more likely part of the path between them [Sherwood]. But a more likely
motivation is simple self-interest---a receiver can hugely improve motivation is simple self-interest---a receiver can improve its own
its own download speed, without any need for the sender to be a download speed, without any need for the sender to be a willing
willing accomplice. accomplice. [Savage] quotes results that show this attack can reduce
the time taken to download an HTTP file over a real network by half,
even with a relatively cautious optimisitic acknowledgemnt strategy.
To be clear, the measures in this specification are intended for There is currently no evidence that any TCP implementations are
senders that can be trusted to behave. Unless all senders are exploiting any of the attacks mentioned above. However this may be
trusted, this scheme alone cannot prevent other misbehaving senders simply a result of the fact that there is no widely available test to
from causing congestion collapse of the Internet. But the more identify such attacks. This document describes a test process that
trustworthy senders that deploy these measures, the less likely that can identify such non-compliance by receivers should it start to
misbehaving receivers will be able to find senders that can be fooled become an issue. The test can be deployed as a separate test suite,
into causing congestion collapse. or in existing senders, but this document does not mandate that it
should be implemented by senders. The aim of the authors is to
provide a test that is safe to implement and that can be recommended
by the IETF.
However, senders do not have to be motivated solely by "the common The measures in this specification are intended for senders that can
good" to deploy these changes. It is directly in their own interest be trusted to behave. As all senders can not be trusted, this scheme
for senders serving multiple receivers (e.g. large file servers and can not prevent misbehaving senders from causing congestion collapse
certain file-sharing peers) to detect cheating receivers. A large of the Internet. However the very existence of a test scheme such as
server relies on honest network congestion feedback to efficiently this should act as a disincentive against non-compliant receivers.
apportion its own resources between receivers. If such a large
server devotes an excessive fraction of its own resources to Senders do not have to be motivated solely by "the common good" to
misbehaving receivers, it may well hit its own resource limits and deploy these changes. It is directly in their own interest for
senders serving multiple receivers (e.g. large file servers and
certain file-sharing peers) to detect non-compliant receivers. A
large server relies in part on honest network congestion feedback to
efficiently apportion its own resources between receivers. If such a
large server devotes an excessive fraction of its own resources to
non-compliant receivers, it may well hit its own resource limits and
have to starve other half-connections even if their network path has have to starve other half-connections even if their network path has
spare capacity. spare capacity.
In order for a sender to test a receiver, we avoid requiring the In order for a sender to test a receiver, we avoid requiring the
receiver to have deployed any new or optional protocol features, as receiver to have deployed any new or optional protocol features, as
any misbehaving receiver could simply circumvent the test by claiming any misbehaving receiver could simply circumvent the test by claiming
it did not support the optional feature. Instead, the sender it did not support the optional feature. Instead, the sender
emulates network re-ordering then loss to test that the receiver emulates network re-ordering then network loss to test that the
behaves as it should within the basic TCP protocol. receiver reacts as it should as defined within the basic TCP
protocol. It is important that the level of emulated re-ordering
that such a test introduces should not adversely impact compliant
receivers.
This document specifies a two-stage test in which the sender This document specifies a two-stage test in which the sender
deliberately re-orders some data segments so as to check if the deliberately re-orders some data segments so as to check if the
destination honestly acknowledges out-of-order segments. The first destination correctly acknowledges out-of-order segments. The first
stage test introduces a small reordering which will have a related stage test introduces a small reordering which will have a related
very minor performance hit. It is not a conclusive test. However, very minor performance hit. It is not a conclusive test of
failing it raises sufficient suspicion to warrant the more intrusive compliance. However, failing it strongly suggests the receiver is
but conclusive second stage. The second stage proves beyond doubt non-compliant. This raises sufficient suspicion to warrant the more
whether the receiver is cheating but it also requires significant re- intrusive but conclusive second stage if this non-compliance is going
to be sanctioned. The second stage proves beyond doubt whether the
receiver is non-compliant but it also requires significant re-
ordering, which harms performance. Therefore it should not be used ordering, which harms performance. Therefore it should not be used
unless a receiver is already strongly suspected of cheating (through unless a receiver is already strongly suspected of non-compliance
failing the first stage). (through failing the first stage).
The technique is designed to work with all known variants of TCP, The technique is designed to work with all known variants of TCP,
with or without ECN [RFC3168], with or without SACK [RFC2018], and so with or without ECN [RFC3168], with or without SACK [RFC2018], and so
on. The technique is probably transferable to derivatives of TCP, on. The technique is probably transferable to derivatives of TCP,
such as SCTP [RFC2960], but separate specifications will be required such as SCTP [RFC2960], but separate specifications will be required
for such related transports. The requirements for a robust solution for such related transports. The requirements for a robust solution
in Section 4 serve as guidelines for these separate specifications. in Section 4 serve as guidelines for these separate specifications.
The document is structured as follows. It begins with a detailed The document is structured as follows. It begins with a detailed
description of the problems outlined above. It cites some published description of the problems outlined above. It cites some published
skipping to change at page 6, line 33 skipping to change at page 7, line 46
A strategising receiver can take advantage of the congestion and flow A strategising receiver can take advantage of the congestion and flow
control mechanisms to increase its data throughput. The three known control mechanisms to increase its data throughput. The three known
ways in which it can do this are: optimistic acknowledgements, ways in which it can do this are: optimistic acknowledgements,
concealing segment losses and dividing acknowledgements into smaller concealing segment losses and dividing acknowledgements into smaller
parts. The first two are examined in more detail below and details parts. The first two are examined in more detail below and details
of the third can be found in [Savage]. of the third can be found in [Savage].
3.1. Concealing Lost Segments 3.1. Concealing Lost Segments
TCP is designed to view a lost segment as an indication of congestion TCP is designed to view a lost segment as an indication of congestion
on the channel. This is because TCP makes the assumption that on the channel. This is because TCP makes the reasonable assumption
packets are most likely to be lost through deliberately being dropped that packets are most likely to be lost through deliberately being
by a congested node rather than through transmission losses or dropped by a congested node rather than through transmission losses
errors. or errors.
In order to avoid congestion collapse [RFC3714], whichever TCP In order to avoid congestion collapse [RFC3714], whichever TCP
connection detects the congestion (through detecting that a packet connection detects the congestion (through detecting that a packet
has been dropped) is expected to respond to it either by reducing its has been dropped) is expected to respond to it either by reducing its
congestion window to 1 segment after a timeout or by halving it on congestion window to 1 segment after a timeout or by halving it on
receipt of three duplicate acks (the precise rules are in [RFC2581]). receipt of three duplicate acks (the precise rules are set out in
[RFC2581]).
For applications where missing data is not an issue, it is in the For applications where missing data is not an issue, it is in the
interest of a receiver to maximise the data rate it gets from the interest of a receiver to maximise the data rate it gets from the
sender. If it conceals lost segments by falsely generating sender. If it conceals lost segments by falsely generating
acknowledgements for them it will not suffer a reduction in data acknowledgements for them it will not suffer a reduction in data
rate. There are a number of ways to make an application loss- rate. There are a number of ways to make an application loss-
insensitive. Some applications such as streaming media are insensitive. Some applications such as streaming media are
inherently insensitive anyway, as a loss will just be seen as a inherently insensitive anyway, as a loss will just be seen as a
transient error. TCP is widely used to transmit media files, either transient error. TCP is widely used to transmit media files, either
audio or video, which are relatively insensitive to data loss audio or video, which are relatively insensitive to data loss
skipping to change at page 8, line 4 skipping to change at page 9, line 47
3.2. Optimistic Acknowledgements 3.2. Optimistic Acknowledgements
Optimistic acknowledgements were identified as a possible attack in Optimistic acknowledgements were identified as a possible attack in
[Savage]. If a receiver is downloading a file from a server, it is [Savage]. If a receiver is downloading a file from a server, it is
probably in its interest to acquire as high a bandwidth as possible probably in its interest to acquire as high a bandwidth as possible
for this. One way of increasing the bandwidth is to encourage the for this. One way of increasing the bandwidth is to encourage the
sender to believe the round trip time is shorter than it actually is. sender to believe the round trip time is shorter than it actually is.
This means the sender will open up its transmission window faster and This means the sender will open up its transmission window faster and
thus will send data faster. Of course any lost segments will also be thus will send data faster. Of course any lost segments will also be
concealed during such an attack. concealed during this attack.
The receiver can achieve this by sending acknowledgements for data it The receiver can achieve this by sending acknowledgements for data it
hasn't actually received yet. As long as the acknowledgement is for hasn't actually received yet. As long as the acknowledgement is for
a packet that has already been transmitted, the sender will assume a packet that has already been transmitted, the sender will assume
the RTT has become shorter. This will cause it to increase its the RTT has become shorter. This will cause it to increase its
transmission window more rapidly and thus send more data. Optimistic transmission window more rapidly and thus send more data. Optimistic
acknowledgements are particularly damaging since they can also be acknowledgements are particularly damaging since they can also be
used to significantly amplify the effect of a denial of service (DoS) used to significantly amplify the effect of a denial of service (DoS)
attack on a network. This form of attack is explained in more detail attack on a network. This form of attack is explained in more detail
in [Sherwood]. in [Sherwood].
skipping to change at page 9, line 5 skipping to change at page 10, line 47
flow on the right acknowledges data before it is received and flow on the right acknowledges data before it is received and
consequently the apparent RTT is reduced. consequently the apparent RTT is reduced.
Figure 2: Optimistic acknowledgements Figure 2: Optimistic acknowledgements
In 2005 US-CERT (the United States Computer Emergency Readiness Team) In 2005 US-CERT (the United States Computer Emergency Readiness Team)
issued a vulnerability notice [VU102014] specifically addressed to 80 issued a vulnerability notice [VU102014] specifically addressed to 80
major network equipment manufacturers and vendors who could be major network equipment manufacturers and vendors who could be
affected if someone maliciously exploited optimistic acknowledgements affected if someone maliciously exploited optimistic acknowledgements
to cause a denial of service. This highlights the potential severity to cause a denial of service. This highlights the potential severity
of such an attack were one to be launched. of such an attack were one to be launched. It should be noted
however that the primary motivation for using optimistic
acknowledgement is likely to be the performance gain it gives rather
than the possible negative impact on the network. Application
writers may well produce "Download Accelerators" that use optimistic
acknowledgements to achieve the performance increase rather than the
current parallel connection approach most use. Users of such
software would be effectively innocent parties to the potential harm
that such a non-compliant TCP could cause.
4. Requirements for a robust solution 4. Requirements for a robust solution
Since the above problems come about through the inherent behaviour of Since the above problems come about through the inherent behaviour of
the TCP protocol, there is no gain in introducing a new protocol as the TCP protocol, there is no gain in introducing a new protocol as
misbehaving receivers can claim to only support the old protocol. misbehaving receivers can claim to only support the old protocol.
The best approach is to provide a mechanism within the existing The best approach is to provide a mechanism within the existing
protocol to test whether a receiver is cheating. The following protocol to test whether a receiver is cheating. The following
requirements should be met by any such test in TCP and are likely to requirements should be met by any such test in TCP and are likely to
be applicable for similar tests in other transport protocols: be applicable for similar tests in other transport protocols:
1. The honesty test MUST NOT adversely affect the existing 1. The compliance test must not adversely affect the existing
congestion control and avoidance algorithms since one of the congestion control and avoidance algorithms since one of the
primary aims of any honesty test is to reinforce the integrity of primary aims of any compliance test is to reinforce the integrity
congestion control. of congestion control.
2. Any test SHOULD utilise existing features of the TCP protocol. 2. Any test should utilise existing features of the TCP protocol.
If it can be implemented without altering the existing protocol If it can be implemented without altering the existing protocol
then implementation and deployment are easier. then implementation and deployment are easier.
3. The receiver SHOULD NOT play an active role in the process. It 3. The receiver should not play an active role in the process. It
is much more secure to have a check for honesty that only is much more secure to have a check for compliance that only
requires the receiver to behave as it should anyway. requires the receiver to behave as it should anyway.
4. It SHOULD NOT require the use of any negotiable TCP options. 4. It should not require the use of any negotiable TCP options.
Since the use of such options is by definition optional, any Since the use of such options is by definition optional, any
misbehaving receiver could just choose not to use the appropriate misbehaving receiver could just choose not to use the appropriate
option. option.
5. If this is a periodic test, the receiver MUST NOT be aware that 5. If this is a periodic test, the receiver must not be aware that
it is being tested for honesty. If the receiver can tell that it it is being tested for compliance. If the receiver can tell that
is being tested (by identifying the pattern of testing) it can it is being tested (by identifying the pattern of testing) it can
choose to respond honestly only whilst it is being tested. If choose to respond honestly only whilst it is being tested. If
the test is always performed this clearly doesn't apply. the test is always performed this clearly doesn't apply.
6. If the sender actively sanctions any dishonesty it identifies, it 6. If the sender actively sanctions any non-compliance it
SHOULD be certain of the receiver's dishonesty before taking identifies, it should be certain of the receiver's non-compliance
action against it. Any false positives might lead to inefficient before taking action against it. Any false positives might lead
use of network resources and could damage end-user confidence in to inefficient use of network resources and could damage end-user
the network. confidence in the network.
7. The testing should not significantly reduce the performance of an
innocent receiver.
5. Existing Proposals 5. Existing Proposals
5.1. Randomly Skipped Segments 5.1. Randomly Skipped Segments
[Sherwood] suggests a simple approach to test a receiver's honesty. [Sherwood] suggests a simple approach to test a receiver's
The test involves randomly dropping segments at the sender before compliance. The test involves randomly dropping segments at the
they are transmitted. All TCP "flavours" require that a receiver sender before they are transmitted. All TCP "flavours" require that
should generate duplicate acknowledgements for all subsequent a receiver should generate duplicate acknowledgements for all
segments until a missing segment is received. This system requires subsequent segments until a missing segment is received. This system
that SACK be enabled so the sender can reliably tell that the requires that SACK be enabled so the sender can reliably tell that
duplicate acknowledgements are generated by the segment that is meant the duplicate acknowledgements are generated by the segment that is
to be missing and are not concealing other congestion. Once the meant to be missing and are not concealing other congestion. Once
first duplicate acknowledgement arrives, the missing segment can then the first duplicate acknowledgement arrives, the missing segment can
be re-transmitted. Because this loss has been deliberately then be re-transmitted. Because this loss has been deliberately
introduced, the sender doesn't treat it as a sign of congestion. If introduced, the sender doesn't treat it as a sign of congestion. If
a receiver sends an acknowledgement for a segment that was sent after a receiver sends an acknowledgement for a segment that was sent after
the gap, it proves it is behaving dishonestly and can thus be the gap, it proves it is behaving dishonestly and can thus be
sanctioned. As soon as the first duplicate acknowledgement is sanctioned. As soon as the first duplicate acknowledgement is
received the missing segment is re-transmitted. This will introduce received the missing segment is re-transmitted. This will introduce
a 1 RTT delay for some segments which could adversely affect some a 1 RTT delay for some segments which could adversely affect some
low-latency applications. low-latency applications.
This scheme does work perfectly well in principle and does allow the This scheme does work perfectly well in principle and does allow the
sender to clearly identify dishonest behaviour. However it fails to sender to clearly identify dishonest behaviour. However it fails to
skipping to change at page 10, line 46 skipping to change at page 12, line 46
stating that senders are entitled to discriminate against receivers stating that senders are entitled to discriminate against receivers
that don't support it. Given that SACK is now widely implemented that don't support it. Given that SACK is now widely implemented
across the Internet this might be a feasible, but controversial, across the Internet this might be a feasible, but controversial,
deployment strategy. However the solution in Section 6 builds on deployment strategy. However the solution in Section 6 builds on
Sherwood's scheme but avoids the need for SACK. Sherwood's scheme but avoids the need for SACK.
5.2. The ECN nonce 5.2. The ECN nonce
The authors of the ECN scheme [RFC3168] identified the failure to The authors of the ECN scheme [RFC3168] identified the failure to
echo ECN marks as a potential attack on ECN. The ECN nonce was echo ECN marks as a potential attack on ECN. The ECN nonce was
proposed as a possible solution to this in [RFC3540]. It uses a 1 proposed as a possible solution to this in experimental [RFC3540].
bit nonce in every IP header. The nonce works by randomly setting It uses a 1 bit nonce in every IP header. The nonce works by
the ECN field to ECN(0) or ECN(1). It then maintains the least randomly setting the ECN field to ECN(0) or ECN(1). It then
significant bit of the sum of this value and stores the expected sum maintains the least significant bit of the sum of this value and
for each segment boundary. At the receiver end, the same 1-bit sum stores the expected sum for each segment boundary. At the receiver
is calculated and is echoed back in the NS (nonce sum) flag added to end, the same 1-bit sum is calculated and is echoed back in the NS
the TCP header. If a packet has been congestion marked then it loses (nonce sum) flag added to the TCP header. If a packet has been
the information of which ECT codepoint it was carrying. A receiver congestion marked then it loses the information of which ECT
wishing to conceal the ECN mark will have to guess whether to codepoint it was carrying. A receiver wishing to conceal the ECN
increment NS or not. Once congestion has been echoed back and the mark will have to guess whether to increment NS or not. Once
source has started a congestion response the nonce sum in the TCP congestion has been echoed back and the source has started a
header is not checked. Once congestion recovery is over the source congestion response the nonce sum in the TCP header is not checked.
resets its NS to that of the destination and starts checking again. Once congestion recovery is over the source resets its NS to that of
the destination and starts checking again.
On the face of it this solution also fully covers the two problems On the face of it this solution also fully covers the two problems
identified in Section 3. If a receiver conceals a lost segment it identified in Section 3. If a receiver conceals a lost segment it
has to guess what mark was there and, over several guesses, is very has to guess what mark was there and, over several guesses, is very
likely to be found out. If a receiver tries to use optimistic likely to be found out. If a receiver tries to use optimistic
acknowledgements it has to guess what nonce was set on all the acknowledgements it has to guess what nonce was set on all the
packets it acknowledges but hasn't received yet. However there are packets it acknowledges but hasn't received yet. However there are
some key weaknesses to this system. Firstly, it assumes that ECN some key weaknesses to this system. Firstly, it assumes that ECN
will be widely deployed (not currently true). Secondly, it relies on will be widely deployed (not currently true). Secondly, it relies on
the receiver honestly declaring support for both ECN and the ECN the receiver honestly declaring support for both ECN and the ECN
nonce - a strategising receiver can simply declare it is neither ECN nonce - a strategising receiver can simply declare it is neither ECN
nor ECN nonce capable and thus avoid the nonce. Thirdly, the nor ECN nonce capable and thus avoid the nonce. Thirdly, the
mechanism is suspended during any congestion response. Comparing it mechanism is suspended during any congestion response. Comparing it
against the requirements in Section 4 above, it is clear that the ECN against the requirements in Section 4 above, it is clear that the ECN
nonce fails to meet requirements 3 and 4 and arguably fails to meet nonce fails to meet requirements 3 and 4 and arguably fails to meet
requirement 2 as [RFC3540] is experimental. The authors do state requirement 2 as [RFC3540] is experimental. The authors do state
that any sender that implements the ECN nonce is entitled to that any sender that implements the ECN nonce is entitled to
discriminate against any receiver that doesn't support it. Given discriminate against any receiver that doesn't support it. Given
there are currently no implementations of the ECN nonce, there are currently no implementations of the ECN nonce,
discriminating against the large majority of receivers that don't discriminating against the overwhelming majority of receivers that
support it is not a feasible deployment strategy. don't support it is not a feasible deployment strategy.
5.3. A transport layer nonce 5.3. A transport layer nonce
One possible solution to the above issues is a multi-bit transport One possible solution to the above issues is a multi-bit transport
layer nonce. Two versions of this are proposed in [Savage]. The layer nonce. Two versions of this are proposed in [Savage]. The
first is the so called "Singular Nonce" where each segment is first is the so called "Singular Nonce" where each segment is
assigned a unique random number. This value is then echoed back to assigned a unique random number. This value is then echoed back to
the receiver with the ack for that segment. The second version is the receiver with the ack for that segment. The second version is
the "Cumulative Nonce" where the nonce is set as before, but the the "Cumulative Nonce" where the nonce is set as before, but the
cumulative sum of all nonces is echoed back. Whilst such a system is cumulative sum of all nonces is echoed back. Whilst such a system is
skipping to change at page 12, line 20 skipping to change at page 14, line 21
The ideal solution to the above problems should fully meet the The ideal solution to the above problems should fully meet the
requirements set out in Section 4. The most important of these is requirements set out in Section 4. The most important of these is
that the solution should leverage existing TCP behaviours rather than that the solution should leverage existing TCP behaviours rather than
mandating new behaviours and options. The proposed solution utilises mandating new behaviours and options. The proposed solution utilises
TCP's receiver behaviour on detecting missing data. To test a TCP's receiver behaviour on detecting missing data. To test a
receiver the sender delays a segment during transmission by D receiver the sender delays a segment during transmission by D
segments. There is a trade off because increasing D increases the segments. There is a trade off because increasing D increases the
probability of detecting cheating but also increases the probability probability of detecting cheating but also increases the probability
of masking a congestion event during the test. The completely safe of masking a congestion event during the test. The completely safe
strategy for the sender would be to reduce its rate pessimistically strategy for the sender would be to reduce its rate pessimistically
as if there were congestion during the test however this will hurt as if there were congestion during the test however this will impact
honest receivers thus breaching requirement 6. To overcome this the performance of honest receivers, thus breaching requirement 7.
dilemma, the test consists of two stages. In the first stage, the To overcome this dilemma, the test consists of two stages. In the
sender uses small displacements without the pessimistic congestion first stage, the sender uses small displacements without the
response to determine which receivers are probably cheating. The pessimistic congestion response to determine which receivers appear
sender can then prove the dishonesty of these receivers by subjecting to be non-compliant. The sender can then prove the non-compliance of
them to a deterministic test. This test uses a longer displacement these receivers by subjecting them to a deterministic test. This
but given the receiver is already under suspicion, it can risk test uses a longer displacement but given the receiver is already
harming performance by pessimistically reducing its rate as if the under suspicion, it can risk harming performance by pessimistically
segment it held back was really lost by the network. reducing its rate as if the segment it held back was really lost by
the network. The tests can either be implemented as part of a test
suite or as a stand-alone modification to the TCP sender
implementation. References to the TCP sender in the rest of the
document should be taken to include either type of implementation.
6.2. Probabilistic Testing 6.2. Probabilistic Testing
The first requirement for a sender is to decide when to test a The first requirement for a sender is to decide when to test a
receiver. This document doesn't specify when the test should be receiver. This document doesn't specify when the test should be
performed but the following guidance may be helpful. The simplest performed but the following guidance may be helpful. The simplest
option is for a sender to perform the test at frequent random option is for a sender to perform the test at frequent random
intervals for all its half-connections. There are also some intervals for all its half-connections. There are also some
heuristic triggers that might indicate the need for a test. Firstly, heuristic triggers that might indicate the need for a test. Firstly,
if a sender is itself too busy, it would be sensible for it to test if a sender is itself too busy, it would be sensible for it to test
skipping to change at page 13, line 16 skipping to change at page 15, line 20
the strict requirement that all TCP receivers have to send a the strict requirement that all TCP receivers have to send a
duplicate acknowledgement as soon as they receive an out-of-order duplicate acknowledgement as soon as they receive an out-of-order
segment. This acknowledges that some data has been received, however segment. This acknowledges that some data has been received, however
the acknowledgement is for the last in order segment that was the acknowledgement is for the last in order segment that was
received (hence duplicating an acknowledgment already made). SACK received (hence duplicating an acknowledgment already made). SACK
extends this behaviour to allow the sender to infer exactly which extends this behaviour to allow the sender to infer exactly which
segments are missing. This leads to a simple statement: if a segments are missing. This leads to a simple statement: if a
receiver is behaving honestly it must respond to an out-of-order receiver is behaving honestly it must respond to an out-of-order
packet by generating a duplicate acknowledgement. packet by generating a duplicate acknowledgement.
Following from the above statement, a sender can test the honesty of Following from the above statement, a sender can test the compliance
a given receiver by simply delaying transmission of a given segment of a given receiver by simply delaying transmission of a given
by several places. An honest receiver will respond to this by segment by several places. An honest receiver will respond to this
generating a number of duplicate acknowledgements. The sender would by generating a number of duplicate acknowledgements. The sender
strongly suspect a receiver of cheating if it received no duplicate would strongly suspect a receiver of cheating if it received no
acknowledgements as a result of the test. A dishonest receiver can duplicate acknowledgements as a result of the test. A dishonest
only conceal its actions by waiting until the delayed segment arrives receiver can only conceal its actions by waiting until the delayed
and then generating an appropriate stream of duplicate segment arrives and then generating an appropriate stream of
acknowledgements to appear to be honest. duplicate acknowledgements to appear to be honest.
6.2.1. Performing the Probabilistic Test 6.2.1. Performing the Probabilistic Test
The actual mechanism for conducting the test is extremely simple. The actual mechanism for conducting the test is extremely simple.
Having decided to conduct a test the sender selects a segment, N. It Having decided to conduct a test the sender selects a segment, N. It
then chooses a displacement, D (in segments) for this segment where then chooses a displacement, D (in segments) for this segment where
strictly 2 < D < K - 2 where K is the current window size. In strictly 2 < D < K - 2 where K is the current window size. In
practice only low values of D should be chosen to conceal the test practice only low values of D should be chosen to conceal the test
among the background reordering and limit the chance of masking among the background reordering and limit the chance of masking
congestion. Typically D might be less than 6. If K is less than 5, congestion. D SHOULD be less than 6 for an initial test. If K is
the sender can proceed straight to the deterministic test. To less than 5, the sender can proceed straight to the deterministic
conduct the probabilistic test, instead of transmitting segment N, it test. To conduct the probabilistic test, instead of transmitting
transmits N+1, N+2, etc. as shown in the figure below. Once it has segment N, it transmits N+1, N+2, etc. as shown in the figure below.
transmitted N+D it can transmit segment N. The sender needs to record Once it has transmitted N+D it can transmit segment N. The sender
the sequence number, N as well as the displacement, D. needs to record the sequence number, N as well as the displacement,
D.
According to data in [Piratla], as much as 15% of segments in the According to data in [Piratla], as much as 15% of segments in the
Internet arrive out of order though this claim may not be accurate. Internet arrive out of order though this claim may not be accurate.
Whatever the actual degree of re-ordering, receivers always expect Whatever the actual degree of re-ordering, receivers always expect
occasional losses of packets which they cannot distinguish from re- occasional losses of packets which they cannot distinguish from re-
ordering without waiting for the re-ordered packet to arrive. ordering without waiting for the re-ordered packet to arrive.
Consequently a misbehaving receiver is unsure how to react to any Consequently a misbehaving receiver is unsure how to react to any
out-of-order packets it receives. It should be noted that the out-of-order packets it receives. It should be noted that the
natural reordering may reduce the displacement deliberately natural reordering may reduce the displacement deliberately
introduced by the test so the sender should conduct the test more introduced by the test so the sender should conduct the test more
skipping to change at page 15, line 7 skipping to change at page 17, line 11
congestion avoidance. The reason for this is in case there is any congestion avoidance. The reason for this is in case there is any
congestion that is concealed during the test. If there is congestion that is concealed during the test. If there is
congestion, and the sender's window is still increasing congestion, and the sender's window is still increasing
exponentially, this might significantly exacerbate the situation. exponentially, this might significantly exacerbate the situation.
This does mean that any receiver being tested during this period will This does mean that any receiver being tested during this period will
suffer reduced throughput, but such testing should only be triggered suffer reduced throughput, but such testing should only be triggered
by the sender being overloaded. by the sender being overloaded.
6.2.2. Assessing the Probabilistic Test 6.2.2. Assessing the Probabilistic Test
This approach to testing receiver honesty appears to meet all the This approach to testing receiver compliance appears to meet all the
requirements set out in Section 4. The most attractive feature is requirements set out in Section 4. The most attractive feature is
that it enforces equivalence with honest behaviour. That is to say, that it enforces equivalence with honest behaviour. That is to say,
a receiver can either honestly report the missing packets or it can a receiver can either honestly report the missing packets or it can
suffer a reduced throughput by delaying segments and increasing the suffer a reduced throughput by delaying segments and increasing the
RTT. The only significant drawback is that during a test it RTT. The only significant drawback is that during a test it
introduces some delay to the reporting of actual congestion. Given introduces some delay to the reporting of actual congestion. Given
that TCP only reacts once to congestion in each RTT the delay doesn't that TCP only reacts once to congestion in each RTT the delay doesn't
significantly adversely affect the overall response to severe significantly adversely affect the overall response to severe
congestion. congestion.
skipping to change at page 16, line 43 skipping to change at page 19, line 4
| e | _,--' `--N-->| | e | _,--' `--N-->|
| a | _,--' ,| +----------------------------+ | a | _,--' ,| +----------------------------+
| t |<-N-1' _,--',| | Once N arrives it has to | | t |<-N-1' _,--',| | Once N arrives it has to |
| e | | _,--'_,--',| | send a couple of duplicate | | e | | _,--'_,--',| | send a couple of duplicate |
| r | GAP _,--'_,--'_,--',| | acknowledgements so it | | r | GAP _,--'_,--'_,--',| | acknowledgements so it |
| | | _,--'_,--'_,--' | | appears to be honest. This | | | | _,--'_,--'_,--' | | appears to be honest. This |
`--|<-N-1'_,--'_,--' | | will increase the RTT that | `--|<-N-1'_,--'_,--' | | will increase the RTT that |
|<-N-1'_,--' | | the sender is measuring. | |<-N-1'_,--' | | the sender is measuring. |
|<-N+3' | +----------------------------+ |<-N+3' | +----------------------------+
| | | |
Figure 4: Measuring the RTT during a test Figure 4: Measuring the RTT during a test
6.2.4. Protocol Details for the Probabilistic Test 6.2.4. Negative Impacts of the Test
o Periodically and randomly, any heavily loaded TCP sender SHOULD It is important to be aware that keeping track of out-of-order data
check the honesty of its receivers using the probabilistic test. segments uses some memory resources at the receiver. Clearly this
test introduces additional re-ordering to the network and
consequently will lead to receivers using additional resources. In
order to mitigate against this, any sender that implements the test
should only conduct the test at relatively long intervals (of the
order of several RTTs).
6.2.5. Protocol Details for the Probabilistic Test
o Any TCP sender MAY check the compliance of its receivers using the
probabilistic test periodically and randomly. In particular, it
would be advantageous for any sender that is heavily loaded to
identify if it is being taken advantage of by a non-compliant
receiver(s).
o The decision to test MUST be randomised and MAY be based on: the o The decision to test MUST be randomised and MAY be based on: the
current load on the sender; whether the receiver is undergoing a current load on the sender; whether the receiver is undergoing a
congestion response; whether the receiver appears to have congestion response; whether the receiver appears to have
different flow characteristics to the others; when the receiver different flow characteristics to the others; when the receiver
was last tested. was last tested. The interval between tests SHOULD be relatively
long (order of several RTTs).
o To perform the test, the sender MUST select a segment N. The o To perform the test, the sender MUST select a segment N. The
transmission of this segment MUST be delayed by D places. D MUST transmission of this segment MUST be delayed by D places. D MUST
lie between 2 and K-2 exclusively where K is the current size of lie between 2 and K-2 exclusively where K is the current size of
the transmit window. D MUST be generated pseudo-randomly and the transmit window. D SHOULD lie between 2 and 6 exclusively
unpredictably. The actual delay SHOULD be such that the receiver except in those circumstances when a receiver has failed to
can't distinguish the test segment from the background traffic. respond as expected to an earlier test but the sender chooses not
Therefore, the distribution of selections of D is likely to be to proceed to the deterministic test. D MUST be generated pseudo-
skewed towards lower values. randomly and unpredictably. The actual delay SHOULD be such that
the receiver can't distinguish the test segment from the
background traffic. If there are less than D segments worth of
data in the send buffer then the test should be aborted.
o If K < 5, the sender should move straight to the deterministic o If K < 5, the sender should move straight to the deterministic
test Section 6.3.3. test Section 6.3.3.
o The sequence number N of the delayed segment MUST be recorded by o The sequence number N of the delayed segment MUST be recorded by
the sender as must the amount of delay D. the sender as must the amount of delay D.
o The senders enters the test phase when it transmits segment N+1 o The senders enters the test phase when it transmits segment N+1
instead of N. instead of N.
skipping to change at page 18, line 23 skipping to change at page 20, line 43
o If the sender is in the slow start phase it MUST move to o If the sender is in the slow start phase it MUST move to
congestion avoidance as soon as it begins a test. It MAY choose congestion avoidance as soon as it begins a test. It MAY choose
to return to slow start once the test is completed. to return to slow start once the test is completed.
o If a sender is in a test phase and receives no duplicate o If a sender is in a test phase and receives no duplicate
acknowledgements from the receiver it MUST treat this as acknowledgements from the receiver it MUST treat this as
suspicious and SHOULD perform the more rigorous deterministic test suspicious and SHOULD perform the more rigorous deterministic test
set out in Section 6.3.3. set out in Section 6.3.3.
o If a sender is in a test phase and the next segment to be
transmitted has either the SYN or RST bits set, then it must
immediately stop the test, and transmit segment N before
transmitting the SYN or RST segment.
o A sender MAY choose to monitor the pattern of acknowledgements o A sender MAY choose to monitor the pattern of acknowledgements
generated by a receiver. A dishonest receiver is likely to send a generated by a receiver. A dishonest receiver is likely to send a
distinctive pattern of duplicate acknowledgments during a test distinctive pattern of duplicate acknowledgments during a test
phase. As they are unable to detect whether it is a test or not phase. As they are unable to detect whether it is a test or not
they are also forced to behave the same in the presence of any they are also forced to behave the same in the presence of any
segment reordering caused by the network. segment reordering caused by the network.
6.3. Deterministic Testing 6.3. Deterministic Testing
If after one or more probabilistic tests the sender deems that a If after one or more probabilistic tests the sender deems that a
skipping to change at page 19, line 16 skipping to change at page 21, line 40
A dishonest receiver that is concealing segment losses will establish A dishonest receiver that is concealing segment losses will establish
that this isn't a probabilistic test once the missing segment fails that this isn't a probabilistic test once the missing segment fails
to arrive within the space of 1 congestion window. In order to to arrive within the space of 1 congestion window. In order to
conceal the loss the receiver will simply carry on acknowledging all conceal the loss the receiver will simply carry on acknowledging all
subsequent data. The sender can therefore state that if it receives subsequent data. The sender can therefore state that if it receives
an acknowledgement for a segment with a sequence number greater than an acknowledgement for a segment with a sequence number greater than
M before it has actually sent segment M then the receiver must be M before it has actually sent segment M then the receiver must be
cheating. A sender would be expected to close a connection with any cheating. A sender would be expected to close a connection with any
receiver that had failed the deterministic test, but this draft was receiver that had failed the deterministic test, but this draft was
only written to document a test procedure to establish dishonesty, not written to specify what a sender should or must do if a receiver
not what the sender should or must do if the receiver fails the test. fails the test, only how to establish such non-compliance.
It is important to be aware that a third party who is able to It is important to be aware that a third party who is able to
correctly guess the initial sequence number of a connection might be correctly guess the initial sequence number of a connection might be
able to masquerade as a receiver and send acknowledgements on their able to masquerade as a receiver and send acknowledgements on their
behalf to make them appear dishonest. Such an attack can be behalf to make them appear dishonest. Such an attack can be
identified because an honest receiver will also be generating a identified because an honest receiver will also be generating a
stream of duplicate acknowledgements until such time as it receives stream of duplicate acknowledgements until such time as it receives
the missing segment. the missing segment.
6.3.3. Protocol Details for the Deterministic Test 6.3.3. Protocol Details for the Deterministic Test
o If a sender has reason to suspect that a receiver is reacting o If a sender has reason to suspect that a receiver is reacting
dishonestly to the probabilistic test it SHOULD perform the more dishonestly to the probabilistic test it SHOULD perform the more
thorough deterministic test. thorough deterministic test.
o To perform the deterministic test the sender MUST select a segment o To perform the deterministic test the sender MUST select a segment
M at random. The sender MUST store this segment in the buffer of M at random. The sender MUST store this segment in the buffer of
unacknowledged data without sending it and MUST record the unacknowledged data without sending it and MUST record the
sequence number. sequence number.
o If SACK is not being used, the receiver MUST pessimistically o If SACK is not being used, the receiver must pessimistically
perform a congestion response folloiwng the arrival of the first 3 perform a congestion response following the arrival of the first 3
dupliacte acknowledgments for segment M-1 as mandated in duplicate acknowledgments for segment M-1 as mandated in
[RFC2581]. [RFC2581].
o If the receiver sends an acknowledgement for a segment that was o If the receiver sends an acknowledgement for a segment that was
sent after segment M should have been sent, but before segment M sent after segment M should have been sent, but before segment M
is actually sent, then the receiver has proved its dishonesty. is actually sent, then the receiver has proved its non-compliance.
The only possible exception to this is if the receiver is also The only possible exception to this is if the receiver is also
sending a correct stream of duplicate acknowledgements as this sending a correct stream of duplicate acknowledgements as this
implies that a third party is interfering with the connection. implies that a third party is interfering with the connection.
o As soon as the first duplicate acknowledgement for segment M-1 o As soon as the first duplicate acknowledgement for segment M-1
arrives, segment M MUST be transmitted. The effective delay, D, arrives, segment M MUST be transmitted. The effective delay, D,
of segment M MUST be calculated and stored. of segment M MUST be calculated and stored.
o If a sender is in a test phase and the next segment to be
transmitted has either the SYN or RST bits set, then it must
immediately stop the test, and transmit segment N before
transmitting the SYN or RST segment.
o Any subsequent acknowledgement for a segment between M and M+D o Any subsequent acknowledgement for a segment between M and M+D
MUST be treated as an indication of congestion and responded to MUST be treated as an indication of congestion and responded to
appropriately as specified in [RFC2581]. appropriately as specified in [RFC2581].
6.4. Responding to Cheating 6.4. Responding to Non-Compliance
Having identified that a receiver is actually being dishonest, the Having identified that a receiver is actually being dishonest, the
appropriate response is to terminate the connection with that appropriate response is to terminate the connection with that
receiver. If a sender is under severe attack it might also choose to receiver. If a sender is under severe attack it might also choose to
ignore all subsequent requests to connect by that receiver. However ignore all subsequent requests to connect by that receiver. However
this is a risky strategy as it might give an increased incentive to this is a risky strategy as it might give an increased incentive to
launch an attack against someone by making them appear to be behaving launch an attack against someone by making them appear to be behaving
dishonestly. It also is risky in the current network where many dishonestly. It also is risky in the current network where many
users might share a quite small bank of IP addresses assigned users might share a quite small bank of IP addresses assigned
dynamically to them by their ISP's DHCP server. A safer alternative dynamically to them by their ISP's DHCP server. A safer alternative
to blacklisting a given IP address might be to simply test future to blacklisting a given IP address might be to simply test future
connections more rigorously. connections more rigorously.
7. IANA Considerations 6.5. Possible Interactions With Other TCP Features
In order to be safe to deploy, this test must not cause any
unforeseen interactions with other existing TCP features. This
section looks at some of the possible interactions that might happen
and seeks to show that they are not harmful.
6.5.1. TCP Secure
[I-D.ietf-tcpm-tcpsecure] is a WG Internet Draft that provides a
solution to some security issues around the injection of spoofed TCP
packets into a TCP connection. The mitigations to these attacks
revolve round limiting the acceptable sequence numbers for RST and
SYN segments. In order to ensure there is no unforeseen interaction
between TCP Secure and this test the test protocol has been specified
such that a test will be aborted if a SYN or RST segment is sent.
6.5.2. Nagle Algorithm
The Nagle algorithm allows a TCP sender to have one small segment
waiting to be acknowledged at a time. This is designed for
interactive applications where the data needs to be echoed back to
the sender and is intended to reduce the number of small packets that
are generated. The protocol definition for the probabilistic test
only allows the test to proceed if there are D or more segments
waiting to be sent. This should remove any possible adverse
interactions with the Nagle algorithm. However this assertion will
need to be checked and the safe strategy may prove to be to ensure
that partial segments are never delayed if Nagle is in operation or
even to suspend testing altogether.
6.5.3. Delayed Acknowledgements
[RFC2581] allows for the generation of delayed acknowledgements for
data segments. However the tests in this document rely on triggering
the generation of duplicate acknowledgements. These must be
generated for every out of order packet that is received and should
be generated immediately the packet is received. Consequently these
mechanisms have no effect on the tests set out in this document.
6.6. Possible Consequences of the Tests
Earlier in this document we asserted that these tests don't change
the TCP protocol. We make this assertion for two reasons. Firstly
the protocol can be implemented as a shim that sits between the TCP
and IP layers. Secondly the network and receiver are unable to
differentiate between a sender that implements these tests and a
sender where the IP layer re-orders packets before transmission.
However the tests might have some impact on the debugging of a TCP
implementation. It will also have an impact on debugging traces as
it creates additional reordering. The authors feel that these
effects are sufficiently minor to be safely ignored. If an author of
a new TCP implementation wishes to be certain that they won't be
affected by the tests during debugging they simply need to ensure
that the sender they are connecting to is not undertaking the tests.
A potentially more problematic consequence is the potential increase
in packet reordering that this test might introduce. However the
degree of reordering introduced in the probabilistic test is strictly
limited. This should have minimal impact on the network as a whole
although this assertion would benefit from testing by the wider
Internet Community.
7. Comparison of the Different Solutions
The following table shows how all the approaches described in this
document compare against the requirements set out in Section 4.
+----------------+------+------+--------+---------+---------+
| Requirement | Rand | ECN |Transp. | Stage 1 | Stage 2 |
| | skip |nonce | nonce | test | test |
| | segs | | | | |
+----------------+------+------+--------+---------+---------+
| Congestion | | | | | |
| Control | Yes | Yes | Yes | Yes | Yes |
| unaffected | | | | | |
+----------------+------+------+--------+---------+---------+
| Utilise | | | | | |
| existing | Yes | No** | No | Yes | Yes |
| features | | | | | |
+----------------+------+------+--------+---------+---------+
| Receiver | Yes | No | No | Yes | Yes |
| passive role | | | | | |
+----------------+------+------+--------+---------+---------+
| No negotiable |Yes * | No | No | Yes | Yes |
| TCP options | | | | | |
+----------------+------+------+--------+---------+---------+
| Receiver | Yes | N/A | N/A | Yes | Yes |
| unaware | | | | | |
+----------------+------+------+--------+---------+---------+
| Certain of | Yes | Yes | Yes | strong | Yes |
| non-compliance | | | |suspicion| |
+----------------+------+------+--------+---------+---------+
| Innocent rcvr. | | | | | |
| not adversely | No | Yes | Yes | Yes | No |
| affected | | | | | |
+----------------+------+------+--------+---------+---------+
* Safer when SACK is used
** Currently Experimental RFC with no known available implementation
Table 1 Comparing different solutions against the requirements
The table highlights that the three existing schemes looked at in
detail in Section 5 all fail on at least two of these requirements.
Whilst this doesn't necessarily make them bad solutions it does mean
that they are harder to implement than the new tests presented in
this document.
8. Alternative Uses of the Test
Thus far, the two stage test process described in this document has
been examined in terms of being a test for compliance by a receiver
to the TCP protocol, specifically in terms of the protocol's reaction
to segment reordering. The probabilistic test however could also be
used for other test purposes. For instance the test can be used to
confirm that a receiver has correctly implemented TCP SACK. Because
the sender knows exactly which segments have been reordered, it can
confirm that the gaps in the data as reported by SACK are indeed
correct. The test could also be incorporated as part of a test suite
to test the overall compliance of new TCP implementations.
9. IANA Considerations
This memo includes no request to IANA. This memo includes no request to IANA.
8. Security Considerations 10. Security Considerations
The two tests described in this document provide a solution to two of The two tests described in this document provide a solution to two of
the significant security problems that were outlined in [Savage]. the significant security problems that were outlined in [Savage].
Both these attacks could potentially cause major congestion of Both these attacks could potentially cause major congestion of
senders own resources (by making them transmit at too high a rate) senders own resources (by making them transmit at too high a rate)
and could lead to network congestion collapse through subverting the and could lead to network congestion collapse through subverting the
correct reporting of congestion or by amplifying any DoS attack correct reporting of congestion or by amplifying any DoS attack
[Sherwood]. The proposed solution cannot alone prevent misbehaving [Sherwood]. The proposed solution cannot alone prevent misbehaving
senders from causing congestion collapse of the Internet. However, senders from causing congestion collapse of the Internet. However,
the more widely it is deployed by trustworthy senders, the more these the more widely it is deployed by trustworthy senders, the more these
skipping to change at page 21, line 11 skipping to change at page 26, line 45
Due to the wording of [RFC2581] a receiver wishing to establish Due to the wording of [RFC2581] a receiver wishing to establish
whether a probabilistic test is happening can keep their whether a probabilistic test is happening can keep their
acknowledgement clock running (thus maintaining transmission rate) by acknowledgement clock running (thus maintaining transmission rate) by
generating pairs of duplicate acknowledgements for segments it generating pairs of duplicate acknowledgements for segments it
received prior to the gap in the data stream caused by the test. received prior to the gap in the data stream caused by the test.
This would allow a receiver to subsequently send any additional This would allow a receiver to subsequently send any additional
duplicate acknowledgements that would be necessary to make it appear duplicate acknowledgements that would be necessary to make it appear
honest. Such behaviour by a receiver would be readily apparent by honest. Such behaviour by a receiver would be readily apparent by
examining the pattern of the acknowledgements. Should receivers examining the pattern of the acknowledgements. Should receivers
prove able to exploit this to their advantage, there might be a need prove able to exploit this to their advantage, there might be a need
to change some of the musts and shoulds laid out in Section 6.2.4. to change some of the musts and shoulds laid out in Section 6.2.5.
[Savage] also identified a further attack involving splitting [Savage] also identified a further attack involving splitting
acknowledgements into smaller parts. TCP is designed such that acknowledgements into smaller parts. TCP is designed such that
increases in the congestion window are driven by the arrival of a increases in the congestion window are driven by the arrival of a
valid acknowledgement. It doesn't matter if this acknowledgement valid acknowledgement. It doesn't matter if this acknowledgement
covers all of a transmitted segment or not. This means a receiver covers all of a transmitted segment or not. This means a receiver
that divides all its acknowledgements into two will cause the that divides all its acknowledgements into two will cause the
congestion window to open at twice the rate it would do otherwise. congestion window to open at twice the rate it would do otherwise.
The tests described above can't protect against that attack. However The tests described above can't protect against that attack. However
there is a straightforward solution to this - every time the sender there is a straightforward solution to this - every time the sender
transmits a new segment it increments a counter; every acknowledgment transmits a new segment it increments a counter; every acknowledgment
it receives decrements that counter; if the counter reaches zero, the it receives decrements that counter; if the counter reaches zero, the
sender won't increase its congestion window in response to a new sender won't increase its congestion window in response to a new
acknowledgement arriving. To comply with this document, senders MUST acknowledgement arriving. To comply with this document, senders MUST
implement a solution to this problem. implement a solution to this problem.
9. Conclusions 11. Conclusions
The issue of mutual trust between TCP senders and receivers is a The issue of mutual trust between TCP senders and receivers is a
significant one in the current Internet. This document has significant one in the current Internet. This document has
introduced a mechanism by which honest senders can verify that their introduced a mechanism by which honest senders can verify that their
receivers are not cheating. The whole process is robust, receivers are compliant with the current TCP protocol. The whole
lightweight, elegant and efficient. The probabilistic test might process is robust, lightweight, elegant and efficient. The
delay a congestion notification by a fraction of a RTT, however this probabilistic test might delay a congestion notification by a
is compensated for by the protocol reacting more rapidly to any such fraction of a RTT, however this is compensated for by the protocol
indication. The deterministic test carries a greater risk of reacting more rapidly to any such indication. The deterministic test
delaying congestion notification and consequently the protocol carries a greater risk of delaying congestion notification and
mandates that a congestion response should happen whilst performing consequently the protocol mandates that a congestion response should
the test. The two tests combine to provide a mechanism to allow the happen whilst performing the test. The two tests combine to provide
sender to judge the honesty of a receiver in a manner that both a mechanism to allow the sender to judge the compliance of a receiver
encourages honest behaviour and proves dishonesty in a robust manner. in a manner that both encourages compliant behaviour and proves non-
The most attractive feature of this scheme is that it requires no compliance in a robust manner. The most attractive feature of this
active participation by the receiver as it utilises the standard scheme is that it requires no active participation by the receiver as
behaviour of TCP in the presence of missing data. The only changes it utilises the standard behaviour of TCP in the presence of missing
required are at the sender. data. The only changes required are at the sender.
10. Acknowledgements As mentioned in the introduction, the tests described in this
document aren't intended to become a necessary feature for compliant
TCP stacks. Rather, the intention is to provide a safe testing
mechanism that a sender could choose to implement were it to decide
there is a need. If optimistic acknowledgements do start to become
widely exploited the authors of this draft feel it would be valuable
to have an IETF-approved test that can be used to identify non-
compliant receivers. In the mean-time these tests can be used for a
number of alternative purposes such as testing that a new receiver
stack is indeed compliant with the protocol and testing if a receiver
has correctly implemented SACK.
{ToDo:} In the longer term it would be hoped that the TCP protocol could be
modified to make it robust against such non-compliant behaviour,
possibly through the incorporation of a cumulative transport layer
nonce as described in Section 5.3.
11. Comments Solicited 12. Acknowledgements
The authors would like to acknowledge the assistance and comments
they received from contributors to the TCPM mailing list. In
particular we would like to thank Mark Allman, Caitlin Bestler, Lars
Eggert, Gorry Fairhurst, John Heffner, David Mallone, Gavin
McCullagh, Anantha Ramaiah, Rob sherwood, Joe Touch and Michael
Welzl.
13. Comments Solicited
Comments and questions are encouraged and very welcome. They can be Comments and questions are encouraged and very welcome. They can be
addressed to the IETF TCP Maintenance and Minor Extensions working addressed to the IETF TCP Maintenance and Minor Extensions working
group mailing list <tcpm@ietf.org>, and/or to the authors. group mailing list <tcpm@ietf.org>, and/or to the authors.
12. References 14. References
12.1. Normative References 14.1. Normative References
[RFC0793] Postel, J., "Transmission Control Protocol", STD 7, [RFC0793] Postel, J., "Transmission Control Protocol", STD 7,
RFC 793, September 1981. RFC 793, September 1981.
[RFC0813] Clark, D., "Window and Acknowledgement Strategy in TCP", [RFC0813] Clark, D., "Window and Acknowledgement Strategy in TCP",
RFC 813, July 1982. RFC 813, July 1982.
[RFC2018] Mathis, M., Mahdavi, J., Floyd, S., and A. Romanow, "TCP [RFC2018] Mathis, M., Mahdavi, J., Floyd, S., and A. Romanow, "TCP
Selective Acknowledgment Options", RFC 2018, October 1996. Selective Acknowledgment Options", RFC 2018, October 1996.
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119, March 1997. Requirement Levels", BCP 14, RFC 2119, March 1997.
[RFC2581] Allman, M., Paxson, V., and W. Stevens, "TCP Congestion [RFC2581] Allman, M., Paxson, V., and W. Stevens, "TCP Congestion
Control", RFC 2581, April 1999. Control", RFC 2581, April 1999.
12.2. Informative References 14.2. Informative References
[I-D.ietf-tcpm-tcpsecure]
Ramaiah, A., "Improving TCP's Robustness to Blind In-
Window Attacks", draft-ietf-tcpm-tcpsecure-07 (work in
progress), February 2007.
[Piratla] Piratla, N., Jayasumana, A., and T. Banka, "On Reorder [Piratla] Piratla, N., Jayasumana, A., and T. Banka, "On Reorder
Density and its Application to Characterization of Packet Density and its Application to Characterization of Packet
Reordering", 2005. Reordering", 2005.
[RFC2616] Fielding, R., Gettys, J., Mogul, J., Frystyk, H., [RFC2616] Fielding, R., Gettys, J., Mogul, J., Frystyk, H.,
Masinter, L., Leach, P., and T. Berners-Lee, "Hypertext Masinter, L., Leach, P., and T. Berners-Lee, "Hypertext
Transfer Protocol -- HTTP/1.1", RFC 2616, June 1999. Transfer Protocol -- HTTP/1.1", RFC 2616, June 1999.
[RFC2960] Stewart, R., Xie, Q., Morneault, K., Sharp, C., [RFC2960] Stewart, R., Xie, Q., Morneault, K., Sharp, C.,
 End of changes. 69 change blocks. 
199 lines changed or deleted 427 lines changed or added

This html diff was produced by rfcdiff 1.33. The latest version is available from http://tools.ietf.org/tools/rfcdiff/