Subject: [tcpm] New I-D posted : draft-moncaster-tcpm-rcv-cheat-00

From: <[email-masked]>
Date: Tue, 20 Feb 2007 17:27:03 -0000

All, 

As you will shortly see we have just posted a new ID called "A  TCP Test
To Allow Senders to Identify Receiver Cheating"
draft-moncaster-tcpm-rcv-cheat-00. This draft was written as a result of
a request made to Bob Briscoe at IETF 67. There he mentioned to TVWG
that we would be happy to produce a transport layer nonce to protect
against receivers concealing lost packets. This suggestion was broadly
welcomed by the WG and this draft is our response. Initially we intended
to submit this to TSVWG as they requested it. However after checking
with the co-chairs of both TCPM and TSVWG it was agreed that TCPM would
be the best forum for the draft. The draft is available in various
formats at
http://www.cs.ucl.ac.uk/staff/B.Briscoe/pubs.html#tcp-rcv-cheat.

After some background research we decided that an actual nonce would
probably be impractical since it would require modifications to both
sender and receiver. This would make it very hard to enforce as the
receiver could simply pretend to be a legacy one that didn't support the
new nonce. We were keen that our system should be robust and should
require the receiver simply to behave as mandated by the existing TCP
protocols. Indeed the idea was that the solution should actually
leverage the existing TCP behaviours in order to test the honesty of the
receiver. We decided to base our new solution on a solution by Rob
Sherwood et al presented in "Misbehaving TCP receivers can cause
Internet-wide congestion collapse". Their solution, called the randomly
skipped segments solution, suggests purposely removing a segment from
the transmitted data stream and only transmitting it after the receiver
sends a NACK for that segment. If in the meantime the receiver sends an
ACK for a later segment then they are deemed to be behaving dishonestly.

A recent thread on the TCPM mailing list (starting 11th January 2007
"DoS attack from misbehaving receivers") has been discussing the
randomly skipped segments solution in some detail and reveals that there
is a lot of unease about such a test. Our solution is hopefully more
palatable and consists of 2 stages. In the first stage we
probabilistically test the honesty of a receiver. To do this we select a
segment N and a displacement D. Instead of transmitting segments N-1, N,
N+1, N+2, etc we transmit N-1, N+1, N+2, ..., N+D, N, ... An honest TCP
receiver should respond to this missing data by generating a stream of
duplicate ACKs for segment N-1. Any receiver that doesn't do so is
probably behaving dishonestly but, because TCP doesn't guarantee
reliable delivery of ACKs we can't state this for certain. We therefore
state that any receiver that fails this test should be subjected to a
further test that is essentially the same as the Sherwood test. It is
felt that the first test causes minimal damage to an honest receiver and
is essentially compliant with the TCP protocol. The second test is then
reserved for those receivers that we are pretty certain are behaving
dishonestly. We have currently left it up to the community to decide how
to sanction any receiver that fails the second test. We suggest the
appropriate response might be to terminate the connection but others
might instead feel that other sanctions such as reducing the congestion
window and slow start threshold to 1 would be more appropriate.

Both our tests force accurate reporting of losses which was our initial
aim. They also both make it much harder for a receiver to optimistically
ACK data which is an added benefit given the possible harm such
optimistic ACKs might cause.

We will be presenting this at IETF 68 in Prague and would welcome any
comments from people as to the utility of our solution and any
improvements that could be made.

Toby Moncaster 
Future Communications Architecture
Networks Research Centre
BT Group Chief Technology Office
_________________________________________________
t: (+44) (0) 1473 648734
m: (+44) (0) 7764 185416 
________________________________________________________________________
___

Notice: This contribution is the personal view of the author and does
not necessarily reflect the technical nor commercial direction of BT
plc.

_______________________________________________
tcpm mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/tcpm

---

From: Rob Sherwood <[email-masked]>
Date: Tue, 20 Feb 2007 14:36:52 -0500

> http://www.cs.ucl.ac.uk/staff/B.Briscoe/pubs.html#tcp-rcv-cheat.

Hi Toby,

I gave a quick read through the draft on your website, and have a few
comments.

Section 5.1) 

I think there might be some confusion here, but the skipped segment
solution that we proposed in our paper does not require the receiver
supports SACK.  Trivially, our paper presents performance results for
receivers that do and do not support SACK.  If the sender skips segment
N, any ACK > N indicates misbehavior; SACK is simply not involved
for correctness.  If SACK is not supported in the connection, then the
standard performance penalties for not implementing SACK apply, i.e.,
the receiver has to duplicate ACK each loss in turn.  Am I missing
something here?

Section 6.2.4)

"Periodically and randomly, any heavily loaded TCP sender SHOULD check
the honesty of its receivers using the probabilistic test."

I don't think it is sufficient that only heavily loaded TCP senders
perform this test.  Attackers can simply draw a small amount of traffic
from many ("jillions" to quote Mark :-) of servers, not loading any one,
but still have a large aggregate amount of traffic.  In other words,
if the solution is only applied to loaded servers, then the attack
still exists.

At a high level, I like the proposed two phase test in that it is
slightly more efficient then the randomly skipped segment test alone,
i.e., instead of honest receivers being penalized 1 RTT every test,
they are only penalized the buffer time and 1 RTT if network reordering
(pathologically?) undoes the reordering test.  It is not clear, to
me at least, how the efficiency gain weighs against the additional
complexity of code, but presumably others can comment on that.  However,
my understanding of the concern raised on this list (if I can summarize
other's opinions) was that there was a philosophical objection to mucking
up[1] the TCP code for an attack which is not being actively exploited.
In other words, it wasn't the efficiency of the solution that was at
issue, but whether is should be applied at all.

Should people decide that this two phases approach is preferable, it
might be possible to simplify the first phase test as follows.  Rather
then reordering segments N-1,N,N+1,..,N+D to N-1,N+1,..,N+D,N as Toby
et. al suggest, it might be better to more frequently perform this test
with D=1, (i.e., simply swap the order of two sequential segments) and
after some threshold number K failures, apply the second phase randomly
skipped segment test.   I only suggest this as the analysis is probably
slightly simpler in that the reordering rate of pairs of packets have been
previously measured, where as the probability that the N-1,N,N+1,..,N+D
to N-1,N+1,..,N+D,N reordering would be undone is less well studied.

- Rob
.

[1] "mucking up" is clearly a technical term :-)

---

From: Michael Welzl <[email-masked]>
Date: Wed, 21 Feb 2007 08:55:59 +0100

On Tue, 2007-02-20 at 17:27 +0000, [email-masked] wrote:
> (..)

If you're referring to the ECN nonce, I think that it's not fair to
compare this with it (as you also do in the draft), as it additionally
tackles a different problem: concealing the reception of an ECN mark
is much easier to do / less problematic than optimistic acking /
concealing packet loss, and this is what the ECN nonce does but your
scheme doesn't.

On a side note, the following statement in the draft:

> The proposed solution depends, like the skipped segments solution, on
> the strict requirement that all TCP receivers have to send a
> duplicate acknowledgement as soon as they receive an out-of-order
> segment.

is at odds with RFC 2581, which says:

> Out-of-order data segments SHOULD be acknowledged immediately, in
> order to accelerate loss recovery. 

...although I wonder why this is only a SHOULD, and not a MUST,
and herewith suggest to change this in 2581bis, unless there's
a good reason not to do so.

Cheers,
Michael

---

From: Gavin McCullagh <[email-masked]>
Date: Wed, 21 Feb 2007 10:23:17 +0000

Hi,

On Tue, 20 Feb 2007, Rob Sherwood wrote:

> skipped segment test.

Perhaps I misunderstand, but is it not necessary to have variation in D of
at least 
        0 < D < 4
for the attack to be definitively prevented?

The "lazy ack" form of the attack just omits duplicate acks in order that a
loss is never detected.  If the above were implemented with D=1 it appears
that an attacker could always send the first duplicate ack in response to a
missing packet but omit the second or third duplicate ack.  This would seem
to allow the attack to continue but also pass the N-1,N+1,N test.

I guess if lots of packets are being lost as part of the attack this kind
of precision may be impossible on the part of the attacker so maybe the
above is not so important.

Gavin

---

From: <[email-masked]>
Date: Wed, 21 Feb 2007 15:27:11 -0000

Hi Michael.

Just to clarify, I was not talking about the ECN nonce which, as you
rightly say, is intended to address a different problem (the concealing
of ECN marks). I was actually referring to a solution presented by
Stefan Savage et al in the paper "TCP Congestion Control with a
Misbehaving Receiver". In this paper they present two versions of a
transport layer nonce which they call the "Singular Nonce" and
"Cumulative Nonce". We do look at the ECN nonce in the actual draft
since that claims to protect against the two attacks our test is
designed to identify.

Thanks for the pointer as to the slightly surprising wording in RFC2581.
As far as I can tell everyone seems to assume this was a MUST anyway...!

Toby

________________________________________________________________________
____
Toby Moncaster, <[email-masked]> Networks Research Centre, BT
Research
B54/70 Adastral Park, Martlesham Heath, Ipswich, IP53RE, UK.  +44 1473
648734 

-----Original Message-----
From: Michael Welzl [mailto:[email-masked]] 
Sent: 21 February 2007 07:56
To: [email-masked]; Moncaster,T,Toby,CXR9 R
Subject: Re: [tcpm] New I-D posted : draft-moncaster-tcpm-rcv-cheat-00

On Tue, 2007-02-20 at 17:27 +0000, [email-masked] wrote:
> All,
> 
> As you will shortly see we have just posted a new ID called "A  TCP 
> Test To Allow Senders to Identify Receiver Cheating"

If you're referring to the ECN nonce, I think that it's not fair to
compare this with it (as you also do in the draft), as it additionally
tackles a different problem: concealing the reception of an ECN mark is
much easier to do / less problematic than optimistic acking / concealing
packet loss, and this is what the ECN nonce does but your scheme
doesn't.

On a side note, the following statement in the draft:

> the strict requirement that all TCP receivers have to send a duplicate

> acknowledgement as soon as they receive an out-of-order segment.

> order to accelerate loss recovery.

...although I wonder why this is only a SHOULD, and not a MUST, and
herewith suggest to change this in 2581bis, unless there's a good reason
not to do so.

Cheers,
Michael

---

From: <[email-masked]>
Date: Wed, 21 Feb 2007 15:46:10 -0000

Hi Rob,

We were under the impression that you were keen that the skipped
segments solution be implemented with SACK enabled as otherwise there is
a risk that it could delay the notification of congestion by up to 1 RTT
more. Apologies if we have got this wrong.

The condition we give in 6.2.4 that "Periodically and randomly, any
heavily loaded TCP sender SHOULD check the honesty of its receivers
using the probabilistic test." wasn't meant to imply that this was the
ONLY time a sender should test its receivers. It might be better in a
future draft to change it to something wider like: 

"Any TCP sender SHOULD check the honesty 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
taken advantage of by an attack by a dishonest receiver".

We would hope that senders would check at other times as well, hence the
second bullet point in section 6.2.4.

Final point, as Gavin McCullagh has already pointed out, apart from
legacy Tahoe TCP implementations a receiver can be reasonably safe if it
sends less than 3 duplicate ACKs for a missing segment as this will not
trigger fast re-transmit. Consequently we have specified that the
displacement should be at least this large.

Toby

-----Original Message-----
From: Rob Sherwood [mailto:[email-masked]] 
Sent: 20 February 2007 19:37
To: Moncaster,T,Toby,CXR9 R
Cc: [email-masked]
Subject: Re: [tcpm] New I-D posted : draft-moncaster-tcpm-rcv-cheat-00

On Tue, Feb 20, 2007 at 05:27:03PM -0000, [email-masked] wrote:
> draft-moncaster-tcpm-rcv-cheat-00. This draft was written as a result 
> of a request made to Bob Briscoe at IETF 67. There he mentioned to 
> TVWG that we would be happy to produce a transport layer nonce to 
> protect against receivers concealing lost packets. This suggestion was

> broadly welcomed by the WG and this draft is our response. Initially 
> we intended to submit this to TSVWG as they requested it. However 
> after checking with the co-chairs of both TCPM and TSVWG it was agreed

> that TCPM would be the best forum for the draft. The draft is 
> available in various formats at 

Hi Toby,

Section 5.1) 

I think there might be some confusion here, but the skipped segment
solution that we proposed in our paper does not require the receiver
supports SACK.  Trivially, our paper presents performance results for
receivers that do and do not support SACK.  If the sender skips segment
N, any ACK > N indicates misbehavior; SACK is simply not involved for
correctness.  If SACK is not supported in the connection, then the
standard performance penalties for not implementing SACK apply, i.e.,
the receiver has to duplicate ACK each loss in turn.  Am I missing
something here?

Section 6.2.4)

I don't think it is sufficient that only heavily loaded TCP senders
perform this test.  Attackers can simply draw a small amount of traffic
from many ("jillions" to quote Mark :-) of servers, not loading any one,
but still have a large aggregate amount of traffic.  In other words, if
the solution is only applied to loaded servers, then the attack still
exists.

At a high level, I like the proposed two phase test in that it is
slightly more efficient then the randomly skipped segment test alone,
i.e., instead of honest receivers being penalized 1 RTT every test, they
are only penalized the buffer time and 1 RTT if network reordering
(pathologically?) undoes the reordering test.  It is not clear, to me at
least, how the efficiency gain weighs against the additional complexity
of code, but presumably others can comment on that.  However, my
understanding of the concern raised on this list (if I can summarize
other's opinions) was that there was a philosophical objection to
mucking up[1] the TCP code for an attack which is not being actively
exploited.
In other words, it wasn't the efficiency of the solution that was at
issue, but whether is should be applied at all.

Should people decide that this two phases approach is preferable, it
might be possible to simplify the first phase test as follows.  Rather
then reordering segments N-1,N,N+1,..,N+D to N-1,N+1,..,N+D,N as Toby
et. al suggest, it might be better to more frequently perform this test
with D=1, (i.e., simply swap the order of two sequential segments) and
after some threshold number K failures, apply the second phase randomly
skipped segment test.   I only suggest this as the analysis is probably
slightly simpler in that the reordering rate of pairs of packets have
been previously measured, where as the probability that the
N-1,N,N+1,..,N+D to N-1,N+1,..,N+D,N reordering would be undone is less
well studied.

- Rob
.

---

From: Michael Welzl <[email-masked]>
Date: Wed, 21 Feb 2007 16:47:42 +0100

> since that claims to protect against the two attacks our test is

Hm, I always thought that the nonce in this paper by Stefan Savage
is the ancestor of the ECN nonce, but maybe there's a small
but significant difference there

> As far as I can tell everyone seems to assume this was a MUST anyway...!

...and I would expect most implementations to conform with this
interpretation - so it would be interesting to learn the reasoning
behind the SHOULD. This is not the first time that I'm surprised
by something in RFC 2581, and so far, it always turned out that
there was a good reason for everything. It's just full of
such intricacies  :)

Cheers,
Michael

---

From: "Anantha Ramaiah \(ananth\)" <[email-masked]>
Date: Wed, 21 Feb 2007 09:32:19 -0800

> ...although I wonder why this is only a SHOULD, and not a 
> MUST, and herewith suggest to change this in 2581bis, unless 
> there's a good reason not to do so.

Although the RFC says SHOULD, in reality it is treated as a MUST, I
think the majority of stacks will send a ack for a out-of-order segment.
It probably makes sense to make this a MUST in RFC 2581bis if we want to
enforce some basic congestion control stuff like fast-retransmissions
(which is worded as a MUST by the way).

The only reason which I can think off why it was worded as a SHOULD
instead of a MUST is when the basic cong.control on TCP was written long
time back, "putting" many packets (even if they serve some useful
purpose) was probably considered aggressive, in the current context pure
ACK's. I am sure there are folks in the list who may have better
answers. 

OTOH, recently, we were discussing about rate-limiting the no. of
duplicate ACK's from mis-behaving receivers in the context of RFC
2581bis, now there is a mention about
"some-receivers-that-may-exist-who-don't-send-duplicate-acks-for-out-of-
order-segments-received" 

:-)

-Anantha

---

From: Rob Sherwood <[email-masked]>
Date: Wed, 21 Feb 2007 13:33:23 -0500

> above is not so important.

Your last paragraph sums it up correctly, IMHO.  If the receiver is
actually receiving all packets, then of course it can defeat any test
-- but then there is no attack.  With Lazy ack, if the receiver were
dropping some constant percentage of packets p, then over n tests,
we can expect the receiver to fail p*n tests, and this solution can
be engineered so that k (the number of failed tests before phase 2)
is chosen to prevent the amplification rate from being too high.

In an alternate attack, the attacker could duplicate ack all packets,
but then the amplication factor suffers (1 data packet/(D+1) acks ==
1500/(D+1)*40 == 37.5x/(D+1)).   Maybe it does make sense to consider
D>1 such that the amplification factor suffers more.  Obviously, D>37,
i.e., the value the prevents *any* amplification, is too large for
practical considerations, but it does make the case for a larger value
of D (contrary to what I was suggesting earlier).

- Rob
.

---

From: "Caitlin Bestler" <[email-masked]>
Date: Wed, 21 Feb 2007 11:16:14 -0800

I am very skeptical that there is a transport layer problem here,
as opposed to an application layer problem.

Basically, I do not accept the following premise:

	A large server relies 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 misbehaving receivers, it may well hit its own
	resource limits and have to starve other half-connections even
	if their network path has spare capacity.

I would rather contend:

	A large server does not rely on network congestion feedback
alone
	to efficiently apportion its own resources between receivers. If
	such a large receiver devotes an excessive fraction of its own
	resources to any receiver (whether misbehaving, malicious or 
	merely greedy) it may well hit its own resource limits and
	have to starve other half-connections even if their network
	path has spare capacity.

A server application that is willing to transmit multi-megabit flows
to an anonymous client based solely on the alleged receive capacity
of the receiver is so gullible it almost qualifies as a "willing
accomplice".

My understanding of this problem assumes the following:

	DoS attacks that seek to cause a server to send very large
streams,
	and thereby cause local congestion at the server end, require
establishing
	actual connections. Therefore the source of the attack is
traceable.
	An attacker is unlikely to use their own machine for a traceable
attack.
	Therefore these attacks would be launched from compromised
machines, from
	a botnet.

	A compromised machine can already be used to "honestly" receive
a stream
	at the compromised machine's capacity rate. The installed
malware can
	simply throw the traffic away with very low CPU overhead. If
clever, it
	can limit the rate to a fraction of the local bandwidth to avoid
arousing
	suspicion of the machine's legitimate owner.

	Therefore the proposed test is intended as a countermeasure
against attackers
	seeking to use optimistic acking to get a multiplier effect. By
committing
	virtually all of the local machines receive bandwidth it can get
the server
	to commit several times that on the server's local network.

	The fake receiver will ack packets that are actually reeived as
though all
	prior packets had been received. An optimal attacker would
probably simulate
	a long NAPI poll cycle of 100 HZ and ack the highest TCP
sequence received
	ignoring all gaps. It would thereby simulate the behavior of an
honest
	receiver that consolidated ACKs on a 100 HZ collection cycle.

An important constraint is that the attacker wants to generate no fewer
acks than
an honest receiver actually receiving the packets would have. The
greatest ACK to
receive ratio that I can think of, this is also legitimate, occurs when
an honest
receiver generates a single ACK for all traffic received in a collection
period.

A receiver that is generating ACKs less frequently than every other sent
packet
or 100HZ AND is claiming that the connection is experiencing no
congestion is
inherently suspicious. Even if it manages to be RFC compliant, the
sender is
under no obligation to continue sending traffic to this client at higher
and
higher rates.

This is especially true since even with the proposed test, an attacker
can 
always recruit compromised attackers to act as a bit bucket drain at
typical
home broadband rates. Since the goal of optimistic acking is to get a
multiplier
effect, the rates in question would be several times higher than typical
home
broadband capacities.

So wouldn't having the application layer merely cap individual flows to
anonymous
clients be just as effective a counter-measure as fiddling with TCP?

And wouldn't it be less harmful?

The proposed test *is* harmful. It artifically increases the amount of
packet
re-ordering in the network. Receivers may already have engineered
resources
to provide resilient responses to re-ordered packets. Artificially
caused
packet reordering as a routine test eats away at those safety margins.
And
the duplicate acks generated ARE excess traffic.

As an *administrative* test done when a flow already appears suspicious
there would be no real problem. But as a routine test to determine when
a flow is suspicious there is an inherent problem. Either the test is
performed too seldom to be effective, or it is performed frequently
enough to have a measurable impact on the performance of at least
some receivers.

---

From: Rob Sherwood <[email-masked]>
Date: Wed, 21 Feb 2007 17:30:17 -0500

> more. Apologies if we have got this wrong.

I'm not sure that I see that risk.  I think both this point and
the point below rely on the same aspect of TCP: when an out of order
segment arrives, the receiver immediately sends a duplicate ACK for the
previously acknowledged segment.  Thus, as long as the receiver sends
a single duplicate ack for the skipped segment, then the sender know
it is honest.  Because there is no delay in the dup ack generation,
the penalty for receiving the skipped segment is at most 1 RTT.

> taken advantage of by an attack by a dishonest receiver".

This wording is definitely clearer.

> displacement should be at least this large.

Maybe I'm the one who is confused, but as I understand it, a single
duplicate ACK (for the correct segment) is enough to differentiate
an honest receiver from a malicious one, so why do you need multiple
duplicate acks?   Fast retransmit should never be an issue, because 
the sender should not perform congestion control in response to a
malicious receiver test.  

- Rob
.

---

From: John Heffner <[email-masked]>
Date: Wed, 21 Feb 2007 18:19:56 -0500

> "some-receivers-that-may-exist-who-don't-send-duplicate-acks-for-out-of-

I would be reluctant to change this to a MUST.  A few things that come 
to mind:

As you mention, some receivers might want to adopt a slightly different 
ACK strategy if there's persistent reordering, to avoid having to ACK 
every packet in steady state, and to prevent triggering fast retransmit 
on senders that don't do NCR (RFC4653) or similar.

In CPU- or interrupt-bound senders, suddenly doubling the rate of ACKs 
it must process can have adverse effects on performance.  It might make 
sense for some high-performance flows with large windows to do delayed 
ACK all the time.  (With large windows and a low loss rate, there's 
little risk.)

Paths with severe asymmetry may want to thin ACKs.  There were some 
papers on this in the mid to late 90's coming out of work with 
satellites and ADSL.

There's been some talk lately about reverse path congestion control. 
(This would be much harder with TCP than DCCP, but maybe someone can 
figure it out?)

Some of this stuff might be hair-brained or not, but we don't want to 
restrict flexibility unless it's really necessary.

   -John

---

From: "Anantha Ramaiah \(ananth\)" <[email-masked]>
Date: Wed, 21 Feb 2007 17:13:14 -0800

> From: John Heffner [mailto:[email-masked]] 
> Sent: Wednesday, February 21, 2007 3:20 PM
> To: [email-masked]
> Cc: Anantha Ramaiah (ananth); Michael Welzl; [email-masked]
> MUST, and 
> >> herewith suggest to change this in 2581bis, unless there's a good 
> >> reason not to do so.
> > 
> > It probably makes sense to make this a MUST in RFC 2581bis 
> if we want 
> > to enforce some basic congestion control stuff like 
> > fast-retransmissions (which is worded as a MUST by the way).
> > 
> > instead of a MUST is when the basic cong.control on TCP was written 
> > long time back, "putting" many packets (even if they serve 
> some useful
> > purpose) was probably considered aggressive, in the current context 
> > pure ACK's. I am sure there are folks in the list who may 
> have better 
> > answers.
> > 
> I would be reluctant to change this to a MUST.  A few things 
> that come to mind:
> 
> 

I am not aware of receivers that rate limit the ACK's due to the fact
that there was persistent re-ordering in the network. YMMV.

> it must process can have adverse effects on performance.  It

Well, I would classify this as the problem of the receiver which isn't
able to process these ACK's. So, if I understand what you are saying
correctly, if the peer to that receiver isn't sending a duplicate ACK
for every out-of-order packet received, things would work well in this
particular case, in cases if it peers with a box (host/router any TCP
device) which follws the SHOULD clause seriously and ack's every other
out-of-order-packet, then the receiver is in trouble? After all the
receiver can chose to drop the ACK, when it detects conditions that
effect performance. It is not rocket-sicence to implement performance
monitors and take corrective actions.

<snip>

> papers on this in the mid to late 90's coming out of work with 

Ok.

> (This would be much harder with TCP than DCCP, but maybe someone can 

By reverse path, you mean ACK congestion control? Data transfer can be
bi-directional.

> restrict flexibility unless it's really necessary.

I agree. My point ( I haven't surveyed the whole internet/intranets
obviously) is :-

- since it is believed that most of the stacks existing today, ACKs
every out-of-order segment it received, "SHOULD" clause has been in the
experimental stage for a while..

- The internet has changed a long way what it was 20+ years back when
the original TCP specs were written and some of the assumptions that
were made are no longer commonplace. In other words the assumptions
which were common has become rare today.

Hence my thinking ( I know some folks wouldn't like it) is we don't lose
much by changing it. May be we don't lose much by not changing ( except
that we would be in a situation of not refelecting the common practice
in the standards) as well :-)

-Anantha

---

From: Michael Welzl <[email-masked]>
Date: Thu, 22 Feb 2007 08:27:06 +0100

> By reverse path, you mean ACK congestion control? Data transfer can be

Funny enough, I stumbled over this SHOULD when thinking about ACK
congestion control, where it could be useful for the sender to be
able to count the number of ACKs that the receiver would normally
have to send during a loss period.

In any case, it's the concern of a new mechanism, yet to be specified,
how to do ACK congestion control, and not the concern of RFC 2581 -
using a SHOULD instead of a MUST for sending ACKs to out-of-order
segments doesn't implement or even help ACK congestion control,
but it actually seems to be a hindrance.

Cheers,
Michael

---

From: <[email-masked]>
Date: Thu, 22 Feb 2007 16:17:37 -0000

Hi Rob,

The rationale behind our mechanism is that the latency in receiving the
skipped segment matters far less than any latency caused in the
potential signalling of a congestion event occurring during the honesty
test. This aspect is never significant with TCP SACK because there can
be enough information in a single acknowledgment to signal both that a
segment is missing, and that a later segment has experienced congestion.

The mechanism you have presented in [Sherwood05] defers sending the
skipped segment until TCP-SACK or a dup ack signals it is missing ,
which will take about one RTT. It will take another RTT for the skipped
segment to be duly acknowledged.

If SACK is not used, the problem is that the receiver cannot signal any
congestion event for about one RTT, from the time when it detects the
skipped segment is missing until the time it receives it. TCP can only
advance the acknowledgement number when it receives in-order data
(strictly data which advances the receive window). In other words your
test will generate a stream of dup acks all for the segment before the
skipped segment until such time as the skipped segment is actually
received.  

The advantage of the mechanism in [draft-moncaster-tcpm-rcv-cheat-00] is
that it reduces the time it takes for the source to send the skipped
segment to a (random) fraction of the congestion window, which on
average will be less than half an RTT.

Forcing a receiver to send a single duplicate ack does partially show
their honesty in that it makes it hard for them to send optimistic acks.
However it still allows them to conceal actual segment losses as they
will generally not suffer any penalty (fast retransmit) until they have
sent three duplicate acknowledgements.

Toby

-----Original Message-----
From: Rob Sherwood [mailto:[email-masked]] 
Sent: 21 February 2007 22:30
To: Moncaster,T,Toby,CXR9 R
Cc: [email-masked]; [email-masked]
Subject: Re: [tcpm] New I-D posted : draft-moncaster-tcpm-rcv-cheat-00

On Wed, Feb 21, 2007 at 03:46:10PM -0000, [email-masked] wrote:
> segments solution be implemented with SACK enabled as otherwise there 
> is a risk that it could delay the notification of congestion by up to 
> 1 RTT more. Apologies if we have got this wrong.

I'm not sure that I see that risk.  I think both this point and the
point below rely on the same aspect of TCP: when an out of order segment
arrives, the receiver immediately sends a duplicate ACK for the
previously acknowledged segment.  Thus, as long as the receiver sends a
single duplicate ack for the skipped segment, then the sender know it is
honest.  Because there is no delay in the dup ack generation, the
penalty for receiving the skipped segment is at most 1 RTT.

> probabilistic test periodically and randomly. In particular, it would 
> be advantageous for any sender that is heavily loaded to identify if 
> it is taken advantage of by an attack by a dishonest receiver".

> legacy Tahoe TCP implementations a receiver can be reasonably safe if 
> it sends less than 3 duplicate ACKs for a missing segment as this will

> not trigger fast re-transmit. Consequently we have specified that the 

Maybe I'm the one who is confused, but as I understand it, a single
duplicate ACK (for the correct segment) is enough to differentiate an
honest receiver from a malicious one, so why do you need multiple
duplicate acks?   Fast retransmit should never be an issue, because 
the sender should not perform congestion control in response to a
malicious receiver test.  

- Rob
.

---

From: John Heffner <[email-masked]>
Date: Thu, 22 Feb 2007 14:25:07 -0500

> but it actually seems to be a hindrance.

On the other hand, I don't know how you could possibly hope to do ACK 
congestion control when congestion on the forward path MUST cause you to 
suddenly double your rate of sending ACKs.

This also leads to another possible reason why you might want to 
continue delayed ACK during reordering/loss: on half-duplex links, 
especially wireless which may have a high per-packet cost, doubling your 
ACK rate in response to congestion actually makes the congestion worse.

I don't really want to get into defending specifics of any of these 
general ideas, but I'm just trying to say I wouldn't want to entirely 
rule out any of these ideas from future TCP, unless a strong case is 
made to do so.

   -John

---

From: "Michael Welzl" <[email-masked]>
Date: Thu, 22 Feb 2007 22:01:31 +0100

> suddenly double your rate of sending ACKs.

What I meant with "new mechanism, yet to be specified" is that
we could, at some point, decide to specify an ACK congestion
control mechanism which would, under controlled conditions,
reduce the ACK rate, and override this MUST with something
else (i.e. update RFC 2581bis) - but since such a mechanism
does not (yet) exist, 2581bis isn't the right place for this.

> rule out any of these ideas from future TCP, unless a strong case is 

It wouldn't rule this out from future RFCs on TCP, and TCP
implementations that are based on them. It merely rules it
out of future TCP implementations (and here, I would argue
that a larger step is needed for proper ACK congestion
control than the flexibility that is granted by the SHOULD
in RFC 2581).

Cheers,
Michael

---

From: John Heffner <[email-masked]>
Date: Thu, 22 Feb 2007 16:20:00 -0500

I guess I'm not quite sure what you mean (maybe we are using language 
that's too indirect).

To get to the heart of the matter: do you advocate changing the first 
SHOULD in Section 3.2 of RFC2581 to a MUST in 2581bis?

This is not a trivial change.

Thanks,
   -John

> control than the flexibility that is granted by the SHOULD

______From [email-masked] Thu Feb 22 16:25:06 2007
Date: Thu, 22 Feb 2007 16:20:00 -0500
From: John Heffner <[email-masked]>
To: Michael Welzl <[email-masked]>
Cc: [email-masked], "Anantha Ramaiah \(ananth\)" <[email-masked]>
Subject: [tcpm] Re: RFC2581bis ooo acking WAS: New I-D posted :
	draft-moncaster-tcpm-rcv-cheat-00

I guess I'm not quite sure what you mean (maybe we are using language 
that's too indirect).

To get to the heart of the matter: do you advocate changing the first 
SHOULD in Section 3.2 of RFC2581 to a MUST in 2581bis?

This is not a trivial change.

Thanks,
   -John

---

From: "Michael Welzl" <[email-masked]>
Date: Thu, 22 Feb 2007 22:23:19 +0100

> SHOULD in Section 3.2 of RFC2581 to a MUST in 2581bis?

Yes,
 
> This is not a trivial change.

but I think it's a good one (and I don't see why it would
be *that* problematic).

Cheers,
Michael

_________________________________________
tcpm mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/tcpm

---

From: "Michael Welzl" <[email-masked]>
Date: Thu, 22 Feb 2007 22:23:19 +0100

Yes,

Cheers,
Michael

---

From: Ted Faber <[email-masked]>
Date: Fri, 23 Feb 2007 15:14:29 -0800

> but I think it's a good one (and I don't see why it would

My thinking is that the SHOULD in question should reamin as it stands.
The advantages of the receiver behavior are obvious, but it's also
perfectly clear that this behavior is not imperative to the correct
function of the TCP protocol, nor will disobeying the SHOULD impair
other users of the network (the source will enter fast retransmit
somewhat later than it optimally could have, but there are plenty of
other possible causes of that delay).

I don't think anyone argues that a good implementation will send the
ACKs.  I don't understand the argument that the system must be
constrained to do it or be non-conformant.  Optimizations are at most
SHOULDs almost by definition.

That's all IMHO, w/o a chair hat.

-- 
Ted Faber
http://www.isi.edu/~faber           PGP: http://www.isi.edu/~faber/pubkeys.asc
Unexpected attachment on this mail? See http://www.isi.edu/~faber/FAQ.html#SIG
_______________________________________________
tcpm mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/tcpm

---

From: Ted Faber <[email-masked]>
Date: Fri, 23 Feb 2007 15:48:04 -0800

On Fri, Feb 23, 2007 at 03:14:29PM -0800, Ted Faber wrote:
> ACKs. 

Strike that; reverse it.

We agree a good implementation will send the ACKs.

---

From: "Caitlin Bestler" <[email-masked]>
Date: Fri, 23 Feb 2007 15:59:33 -0800

> We agree a good implementation will send the ACKs.

I agree with that as long as "send" is understood to 
be inclusive of piggy-backing the "send" on a TCP
segment that is already scheduled for transmit.

That is, when the draft says "immediately send" it
means "do not delay, in fact use a pure ack if
necessary."

---

From: Ted Faber <[email-masked]>
Date: Fri, 23 Feb 2007 17:47:39 -0800

> means "do not delay, in fact use a pure ack if

We agree.

It's my interpretation that TCP should always piggyback an ACK when
possible.  That's how I read P. 74 of RFC 793, anyway: 

      ESTABLISHED STATE
      FIN-WAIT-1 STATE
      FIN-WAIT-2 STATE

	Once in the ESTABLISHED state, it is possible to deliver segment
	text to user RECEIVE buffers.   [...]

	When the TCP takes responsibility for delivering the data to the
	user it must also acknowledge the receipt of the data.

	[...]

	Send an acknowledgment of the form:

          <SEQ=SND.NXT><ACK=RCV.NXT><CTL=ACK>

	This acknowledgment should be piggybacked on a segment being
	transmitted if possible without incurring undue delay.

To my eyes that's a SHOULD in the last paragraph, but (loosely) because 
793 < 2119 that typography wasn't in use.

---

From: Michael Welzl <[email-masked]>
Date: Sat, 24 Feb 2007 09:19:38 +0100

> SHOULDs almost by definition.

What confuses me is this discrepance that, on the one hand,
a lot of effort was made to avoid entering slow start by
reasonably using DupACKs (NewReno, the SACK scoreboard)
and getting enough of them (Limited Transmit), while on
the other, we simply leave it up to the receiver to send
less than it should.

Does it make sense to allow a receiver to do something which
has no obvious benefit, but clearly leads to undesirable
behavior?

Cheers,
Michael

---

From: Ethan Blanton <[email-masked]>
Date: Sat, 24 Feb 2007 11:04:28 -0500

[The "something" below being delaying a dup ACK for a segment received
 out-of-order using delayed ACKs.]

> has no obvious benefit, but clearly leads to undesirable

Yes, if it does not break the protocol.  The receiver may have other
concerns than absolute rapidity of throughput; for example, power
savings, bandwidth conservation, local processing time, etc. etc.
This, in my mind, simply falls into the realm of dictating
implementation details.  The point is that a receiver delaying that
out-of-order ACK will still perform correctly with respect to protocol
semantics, it may just take a little bit longer.

I am inclined to not change this in 2581bis.  I don't see any major
benefit in doing so, and it does constrain implementors' choices,
while not fixing any serious misinteraction.  Anyone violating that
SHOULD already SHOULD [heh] have a very good reason to be doing so.

Ethan

-- 
The laws that forbid the carrying of arms are laws [that have no remedy
for evils].  They disarm only those who are neither inclined nor
determined to commit crimes.
		-- Cesare Beccaria, "On Crimes and Punishments", 1764
_______________________________________________
tcpm mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/tcpm

---

From: Michael Welzl <[email-masked]>
Date: Sun, 25 Feb 2007 14:01:08 +0100

Folks,

You convinced me. Thanks for the discussion!

Cheers,
Michael

---

From: "Anantha Ramaiah \(ananth\)" <[email-masked]>
Date: Sun, 25 Feb 2007 10:04:39 -0800

Actually my thinking is a bit different here. If there is choice to
pick, and I was given that choice, I would go with MUST ;-) A few
comments inline ( I may be repeating myself here)..... 

<snip>

> > > Does it make sense to allow a receiver to do something 
> which has no 
> > > obvious benefit, but clearly leads to undesirable behavior?
> >

- The question I would ask is: "Is fast retransmission considered a
MUST? Yes, according to RFC 2581. If so I would think the surrounding
mechanisms, esp the ones which has direct influence, which facilitate
the fast-retransmision, can also be considered for a MUST candidate,
like in this case the generation of Duplicate ACK's. 

- The above example on "power savings, b/w conservation etc.," can be
applied to, in theory, to any packet, not just the duplicate ACK's. I
may sound argumentative here, but my experience ( not theoretical,
coming from working on internet devices/stacks which use TCP) treats the
dupacks as a MUST. Also to my knowledge, I haven't heard of stacks which
don't send or delay ( the latter may be ok, like you point out above)
these duplicate ACKs and would be interested to know if any one of the
widely used stacks permit this either naturally or by means of knob. But
this is my opinion, OMMV.

Thanks,
-Anantha

<snip>

---

From: Ethan Blanton <[email-masked]>
Date: Sun, 25 Feb 2007 13:33:27 -0500

> like in this case the generation of Duplicate ACK's. 

I agree; however, the duplicate ACK *will* be generated; it just may
be delayed by as much as 500ms.  (Note that 1122 says that the "delay
MUST be less than 0.5 seconds".)  As several people, including myself,
have said in this thread, it is not at all an issue of *correctness*.
If we were talking about correctness, I would completely agree that
the correct solution is the only option.

Ethan

---

From: Gorry Fairhurst <[email-masked]>
Date: Mon, 26 Feb 2007 19:41:42 +0000

>>> herewith suggest to change this in 2581bis, unless there's a good 
<Snip>

> papers on this in the mid to late 90's coming out of work with 
These arguments are in RFC 3449, for reference if you wish to go there.

If you expect receivers to ALWAYS generate specific ACKs, the RFC3449 
mitigations will give you some unexpected shocks (i.e. if you try to 
read more into the ACK stream than the TCP sender needed to clock out 
the data).

<Snip>

Gorry Fairhurst