Subject: [tcpm] Using the ECN Nonce to detect spurious loss events

From: michawe <[email-masked]>
Date: Wed, 16 Mar 2011 10:34:26 +0100

Hi all,

This is about an idea that I've been carrying around with me for a long time now. The plan was to continue the work - which is so far only based on simulations - with a real-life implementation, and then one day write a draft and suggest it to TCPM... but, having treated this as a low-priority item because of the ECN Nonce's shaky situation, time worked against me, and now I find myself wondering whether I should continue this at all or simply dump it. So I'd like to ask what the group thinks - continue or dump?

The idea is to update RFC 3540 (ECN Signaling with Nonces) to include a method for spurious loss event detection.

Here's how it works:
Say, we send a packet, and expect the nonce sum to be 1 in return. The packet is lost, we retransmit => this retransmission carries no nonce (by definition). The nonce sum in the ACK that was caused by this retransmitted packet should then be 0. So, if we get an ACK for the retransmitted packet which carries the nonce sum 1, this indicates that the loss event that led to this retransmission was spurious.

We probably can't rely on the receiver to send a 0 nonce sum on all ACKs that are caused by packets carrying no nonce; also, if the above is the only check done, a receiver would have a 50% chance of tricking a sender into believing that a loss event was spurious, thereby eliminating the very benefit that the nonce provides. We therefore have to wait for a sequence of correct nonce sums to come back - e.g. 4 would already give a reliability of around 94% (i.e. the receiver has a 6% chance of lying).

I see this mechanism as complementary to the other spurious loss event detection schemes (minus Eifel, of course) - it would sometimes kick in when the others don't. One of the nice things about it is that it seems to be easy to implement: it doesn't change anything about the nonce specification on the wire, it only adds a little more intelligence to how we interpret the nonce sums that come back.

I have a small page about this here:
http://heim.ifi.uio.no/~michawe/research/projects/spurious/index.html
where you can get the Globecom'08 paper that gives more details, and an updated implementation of the ECN Nonce for the Linux kernel (that was preparatory work towards a real-life implementation of the mechanism).

Of course, the big problem with this whole scheme is that it is based on the ECN Nonce, which is (it seems to me) probably going to be eliminated by conex (for a cause that I personally consider more valuable than the combination of the ECN nonce + my scheme). So - dump? Opinions?

Cheers,
Michael

---

From: "Scheffenegger, Richard" <[email-masked]>
Date: Wed, 16 Mar 2011 12:05:45 -0000

Hi Michael,

I believe that your goal is very worthwhile - detecting spurious retransmissions and fixing the CC reaction.

But neither ECN nor ECN-nounce are very widely deployed (in comparison with Timestamp - Eifel; SACK - DSACK). Hopefully, the state of ECN will improve with IPv6 (and now, that a number of major OS allow enabling ECN, even though it's not enabled by default).

However, as the number of SACK (DSACK) enabled sessions is already quite high, and there is less (no) state required in the server to discriminate spurious retransmissions with very high probability. I think documenting the proper response to DSACK (only the signaling is currently documented, IIRC) may be more valuable to drive adoption with commercial stacks - often stacks actively signal DSACK, but don't process that feedback themselves...

Overall, I'm afraid I don't see that efforts to improve your scheme would see much deployment because of all these reasons.

On a related topic, I would like to hear your and the groups feedback on the (sketchy) draft around TCP timestamp negotiation - when in use with SACK, it asks for immediate, unconditional reflection of the last received timestamp on the receiver side. This allows the unwind of misdirected CC reaction to be done faster than the RTT of the retransmission (current timestamp / DSACK can only signal back the spurious retransmission 1 RTT after the spurious retransmission, but not 1 RTT (+reorder delay) after the original segment).

(The other main features this signaling would allow are one-way-delay variance measurements, and also faster lost retransmission detection (than Linux; not a IETF RFC yet) without violating packet conservation principles, plus provide a means of transparently allowing integrity checks of timestamps without breaking timestamp-based algorithms).

http://www.ietf.org/id/draft-scheffenegger-tcpm-timestamp-negotiation-01.txt

Best regards,

Richard Scheffenegger

> -----Original Message-----
> From: michawe [mailto:[email-masked]]
> Sent: Mittwoch, 16. März 2011 10:34
> To: [email-masked]
> Subject: [tcpm] Using the ECN Nonce to detect spurious loss events
> 
> Hi all,
> 
> This is about an idea that I've been carrying around with me for a long
> time now. The plan was to continue the work - which is so far only
> based on simulations - with a real-life implementation, and then one
> day write a draft and suggest it to TCPM... but, having treated this as
> a low-priority item because of the ECN Nonce's shaky situation, time
> worked against me, and now I find myself wondering whether I should
> continue this at all or simply dump it. So I'd like to ask what the
> group thinks - continue or dump?
> 
> The idea is to update RFC 3540 (ECN Signaling with Nonces) to include a
> method for spurious loss event detection.
> 
> Here's how it works:
> Say, we send a packet, and expect the nonce sum to be 1 in return. The
> packet is lost, we retransmit => this retransmission carries no nonce
> (by definition). The nonce sum in the ACK that was caused by this
> retransmitted packet should then be 0. So, if we get an ACK for the
> retransmitted packet which carries the nonce sum 1, this indicates that
> the loss event that led to this retransmission was spurious.
> 
> We probably can't rely on the receiver to send a 0 nonce sum on all
> ACKs that are caused by packets carrying no nonce; also, if the above
> is the only check done, a receiver would have a 50% chance of tricking
> a sender into believing that a loss event was spurious, thereby
> eliminating the very benefit that the nonce provides. We therefore have
> to wait for a sequence of correct nonce sums to come back - e.g. 4
> would already give a reliability of around 94% (i.e. the receiver has a
> 6% chance of lying).
> 
> I see this mechanism as complementary to the other spurious loss event
> detection schemes (minus Eifel, of course) - it would sometimes kick in
> when the others don't. One of the nice things about it is that it seems
> to be easy to implement: it doesn't change anything about the nonce
> specification on the wire, it only adds a little more intelligence to
> how we interpret the nonce sums that come back.
> 
> where you can get the Globecom'08 paper that gives more details, and an
> updated implementation of the ECN Nonce for the Linux kernel (that was
> preparatory work towards a real-life implementation of the mechanism).
> 
> Of course, the big problem with this whole scheme is that it is based
> on the ECN Nonce, which is (it seems to me) probably going to be
> eliminated by conex (for a cause that I personally consider more
> valuable than the combination of the ECN nonce + my scheme). So - dump?
> Opinions?
> 
> Cheers,
> Michael
> 
> _______________________________________________
> tcpm mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/tcpm

---

From: michawe <[email-masked]>
Date: Wed, 16 Mar 2011 13:44:40 +0100

> But neither ECN nor ECN-nounce are very widely deployed (in comparison with Timestamp - Eifel; SACK - DSACK). Hopefully, the state of ECN will improve with IPv6 (and now, that a number of major OS…

... but if conex grabs the ecn nonce, they grab it for both ipv4 and ipv6 I suppose.

> However, as the number of SACK (DSACK) enabled sessions is already quite high, and there is less (no) state required in the server to discriminate spurious retransmissions with very high probabilit…

rfc 3708 seems to take care of what you describe here. while i think that this is a good thing to implement, it has the disadvantage of having to wait for a duplicate to arrive at the receiver, which can delay the reaction.

> http://www.ietf.org/id/draft-scheffenegger-tcpm-timestamp-negotiation-01.txt

I read this now. Style wise, I think that it's tough to read, a lot of things could just be expressed in simpler ways, probably by reducing the number of hints regarding possible usage.

I like the general idea. I think it's probably useful to extend TCP's timestamp handling in this manner, but I also think that the right point in time to extend it is when you can also propose a specific usage for this extension.
Like LEDBAT: if a part of the idea is to use this for incorporating LEDBAT congestion control in TCP, why not write this in the draft, as one concrete example application (with full detail, so that it can actually be implemented) of your extended signaling?

Cheers,
Michael

---

From: "Scheffenegger, Richard" <[email-masked]>
Date: Wed, 16 Mar 2011 13:13:42 -0000

Hi Michael,

> rfc 3708 seems to take care of what you describe here. while i think
> that this is a good thing to implement, it has the disadvantage of
> having to wait for a duplicate to arrive at the receiver, which can
> delay the reaction.

Yes, somehow I seem to have missed that rfc. Unless you have some unique
signal that is conveyed in each sent segment, the best reaction time
will be 1 RTT after the (spurious) retransmission. With a unique signal
(like ECN nonce or timestamps (or packet size?), 1RTT (+reorder delay)
of the original segment is the minimum reaction time.

> 
> I read this now. Style wise, I think that it's tough to read, a lot of
> things could just be expressed in simpler ways, probably by reducing
> the number of hints regarding possible usage.

Fully agreed -  this is still a very sketchy draft at this time; the
hints on possible use cases are there to move them later into separate
sections. We didn't want to put in too much possible signaling for which
no current foreseeable use case exists (ie. moved the clock resolution
range negotiation to annex A, from the -00 version, and got rid of a
number of possible redundant/unnecessary flags - ie BIAs, MIRror).

Does the negotiable range of clock rates between ~16 sec and ~8ns (down
to 8ps with reduced precision) sound reasonable enough, and is the
precision of a binary16 float good enough? Except for the bias and the
removal of special numbers (NaN/infinity), the format is like a IEEE
binary16, so I hope conversion can be made easy (simple stacks may just
insert a fixed value and negotiate for the modified TS reflection
behavior, without using the information from the other host).

The mask is now defined with bit-precision, allowing up to 31 bits of
the timestamp to be masked (limiting the value of timestamps for PAWS
very much :); personally, I think only up to 12 bits make some sense for
integrity checking while maintaining the usefulness of timestamps to
existing algorithms, but nibble-precision was seen as being too coarse.

> 
> I like the general idea. I think it's probably useful to extend TCP's
> timestamp handling in this manner, but I also think that the right
> point in time to extend it is when you can also propose a specific
> usage for this extension.
> Like LEDBAT: if a part of the idea is to use this for incorporating
> LEDBAT congestion control in TCP, why not write this in the draft, as
> one concrete example application (with full detail, so that it can
> actually be implemented) of your extended signaling?

Actually, I had a model like RFC2018 / RFC3517 in mind - disentangle the
signaling from the algorithms making use of it. 
Putting all the already investigated algorithms making use of such an
enhancement into one draft (ie. TCP Chirp, TCP LEDBAT, [TCP CUBIC
interaction w/ timestamps], fast-LRD, (eifel-style) spurious
retransmission detection/response) would make this a very lengthy and
needlessly complex draft.
Besides, there may be other useful properties (ie, a low bitrate,
unreliable channel in the masked TS bits) which could be put to other
good use...

I would rather go with a section for use cases, referencing the
(existing) RFCs/papers, and only giving hints how the improved signaling
can help in those algorithms. However, this is currently completely
missing from the draft due to it's very early stage.

---

From: michawe <[email-masked]>
Date: Wed, 16 Mar 2011 14:35:58 +0100

> of the original segment is the minimum reaction time.

AFAIK this is only the minimum reaction time for DSACK. I think that all other schemes - Eifel, F-RTO and my scheme - can react upon receiving an ACK that was caused by the original packet, yet received after retransmitting it.

> behavior, without using the information from the other host).

(that's for someone with more knowledge about these things to answer)

> needlessly complex draft.

I also think that, among the schemes you mention here, only LEDBAT is soon going to be an RFC - so that would make it a matter of only explaining this one as an example, and mentioning the others as possible other mechanisms where your signaling could be used. One difference between this and the 2018/3517 case is that RFC 3517 is about 10 times as long as I think the "and here's how to apply this for LEDBAT" section could be (just 1-2 paragraphs perhaps?). Another reason is that such a use case might just make the document easier to understand. In RFC 2018 it's extremely clear why the specification is in fact useful; in your document this now looks like nebulous handwaving to me, which it wouldn't have to. But that's just my opinion...

> unreliable channel in the masked TS bits) which could be put to other

but saying "this is how to use this for LEDBAT" in one section doesn't exclude these possible future uses at all.

Cheers,
Michael

---

From: Yuchung Cheng <[email-masked]>
Date: Thu, 31 Mar 2011 11:38:03 +0200

On Wed, Mar 16, 2011 at 1:05 PM, Scheffenegger, Richard <[email-masked]>wrote:

> Hi Michael,
>
> I believe that your goal is very worthwhile - detecting spurious
> retransmissions and fixing the CC reaction.
>
> But neither ECN nor ECN-nounce are very widely deployed (in comparison with
> Timestamp - Eifel; SACK - DSACK). Hopefully, the state of ECN will improve
> with IPv6 (and now, that a number of major OS allow enabling ECN, even
> though it's not enabled by default).
>

AFAIK TCP-TS is supported in Microsoft Windows but not enabled by default.
Maybe TCP-TS can not considered widely-deployed?

However, as the number of SACK (DSACK) enabled sessions is already quite
> high, and there is less (no) state required in the server to discriminate
> spurious retransmissions with very high probability. I think documenting the
> proper response to DSACK (only the signaling is currently documented, IIRC)
> may be more valuable to drive adoption with commercial stacks - often stacks
> actively signal DSACK, but don't process that feedback themselves...
>
Linux already (partially) implements RFC4015?

>
> Overall, I'm afraid I don't see that efforts to improve your scheme would
> see much deployment because of all these reasons.
>

After Michael's clarification, I like the idea a lot more

In particular, I see the value in data centers:
1) receivers won't cheat (hopefully)
2) if (fast) retransmission was sent within the TS granular (e.g. 1ms), the
detection has to rely on DSACK instead (2+ RTT slower)