Re: [re-ECN] RE-ECN without ECN.

[Bob Briscoe <[e-mail]>]

Matt,

At 23:42 02/10/2009, Matt Mathis wrote:
>2009/10/2 Bob Briscoe <[e-mail]>uk>:
> > At 22:37 01/10/2009, João Taveira Araújo wrote:
> >> Matt Mathis wrote:
[snip]

>[MM]>>>  More polite would be to pass the retransmission, but then discard the
> >>> next in-order packet on the same flow, normally causing it to slow
> >>> down.  There are some details to be worked out...
>
>[MM] BTW Discarding excessive retransmissions clearly can enforce a hard
>policy on an aggregate: e.g. no more than x% duplicate data.  However,
>from the users point of view, this is a bad thing because losing the
>same segment twice most often causes timeouts, and has the effect of
>greatly increasing the variance of the application performance, as
>seen by the user.    One would expect that discarding a future segment
>to be better behaved from the users perspective, but it requires flow
>state (or at least flow matching) at the point where the dropping is
>happening.

[BB] Like Joao said, first off we're just 
treating all the user's traffic together, so if 
the user as a whole is causing too much 
congestion, the policer shoots their packets 
randomly, not per flow. Then it can hit later 
packets without flow state. In the reArch paper 
Joao referred to, we show this gives the user an 
incentive to run a shadow policer to keep out of trouble.
<http://www.bobbriscoe.net/projects/refb/#polfree>

We just wanted to show that a really simple bulk 
congestion policer was sufficient (perhaps to 
deploy in a street cabinet in front of the 
upstream of a PoN or cable network at L2). The 
idea is if you done bad enough to get locked up 
in the cells overnight, you don't expect a 
gift-wrapped mint on your pillow. But we have a 
less harsh design with flow state too.

>[MM] My sense is that this also has a RED-like tuning problem
>(the dropper has to guess what loss rate is required to attain a
>particular data rate or congestion rate).

[BB] We've added a ramp (increasing) drop 
probability at the bottom of the bucket, rather 
than a hard threshold, and it seems to find a 
stable level. Obviously more tests will be needed.

There were papers in the past describing how rate 
policing tended to make TCP oscillate. So far 
we're finding that congestion policing seems to 
be a lot nicer to TCP. I think it's because 
policing is done on markings which are introduced 
randomly by congestion elsewhere, whereas a rate 
policer is locally deterministic.

Rather than describe it all here tho, it's 
probably best to wait for us to finish the 
experiments & write up the results, which should be in the next months.

>[MM] If the duplicate data
>detection and enforcement are separated, then there is the additional
>problem that you would like to exclude the enforcement drops and
>subsequent retransmissions from the down stream statistics being
>monitored by the enforcement.
>
>I still don't understand the RE-ECN analogue of this latter problem.
>If some aggregate is causing too much congestion, how can the network
>throttle it, without causing it to exhibit even more congestion?

[BB] Our latest policer design includes a way for 
the transport to re-echo congestion drops but not 
policer drops. We've added a subtle way for the 
policer to signal in-band that any drops are 
probably due to policing, not congestion. Also 
the policer doesn't drop the packet carrying the 
marking that first empties the bucket, so there's 
no bias against the packets that happen to carry the markings.

We haven't added this to the protocol draft 
(re-ecn-tcp) yet, or to the implementation. 
Before putting this in the draft, I'm currently 
working out whether this signalling can be used 
generically for any policy drop, not just by congestion policers.

Here's an outline: If a re-echo (aka black or 
positive marking) empties the policer bucket, the 
policer removes the re-echo marking and forwards 
the packet, *then* it increases the drop 
probability ready for the next packet.

Re-echo markings are meant to be immutable e2e, 
so the transport can check the integrity of them 
(this requires additional transport feedback that 
we would have to add to re-ECN's TCP mechanism). 
When the transport notices re-echo marks are 
being removed, it stops re-echoing on drop, and only re-echoes on ECN feedback.

We haven't worked out the details of this yet tho.


>[BB] > I'm concerned that using a feature that a protocol exhibits when it is
> > behaving (TCP retransmissions) in order to police misbehaviour of another
> > aspect of the protocol (too much congestion) 
> requires us to suspend too much
> > disbelief. If I'm going to modify the protocol to misbehave in one way, I
> > can modify the retransmission semantics too.
>
>[MM] Actually it is extracting information from TCP's mechanism to
>implement reliable data delivery.  It is a tautology that downstream
>losses cause reliable protocols send duplicate data.   My proposed
>mechanism would even work if the transport protocol was not responding
>to losses as congestion signals, as long as it continued to implement
>reliable delivery.

[BB] I didn't mean that. I'm saying TCP can do 
reliabile delivery without doing it exactly like 
now. Imagine I plan to re-code my TCP not to 
respond to congestion. If the network is 
accounting for congestion by detecting 
retransmissions, while re-coding I will just 
change both{*} ends to obfuscate sequence 
numbers. I just have to apply some reversible 
transformation keyed on a shared secret to the 
sequence numbers and I'm done. Or actually 
easier, I will be driven to use IPsec.

{*} A strength of your idea is that both ends 
have to be changed to alter TCP's reliability 
mechanism, while the sender alone can alter the congestion response.

>[BB] > Rather than per flow policing, a better 
>framing might be bulk policing over
> > time. Targeting misbehaviour of single flows presumes someone has modified
> > the code. Whereas targeting excessive congestion caused by excessive use of
> > unmodified TCP(s) is lower hanging fruit. Whether for excessive amounts of
> > data over time, or excessive numbers of flows all at once.
>
>[MM] Yea, I'd like to understand what "bulk policing over time" might mean.
>   One of the big pieces missing from "per flow fairness" schemes is a
>reasonable way to make them average over long time periods.

[BB] That's why I was happy with the big token 
bucket in the reArch paper mentioned earlier. It 
can allow a lot of leeway in the short term, but 
the user has the incentive to be friendly to 
others on average. How tight or loose all depends on the choice of parameters:
<http://www.bobbriscoe.net/projects/refb/#polfree>

>[MM] Consider pseudo-re-feedback as a possible deployment strategy for
>RE-ECN.   One ISP can implement it unilaterally, and as real RE-ECN
>gets deployed, the instrumentation and controls become more accurate.

[BB] Certainly.

I still worry it's TCP-only, so could cause a 
backlash against TCP as a whole. In trying to 
sort out fairness, we mustn't risk losing the 
dynamics of TCP that protect against congestion collapse.

Recently (prompted by Mark Handley) I've been 
thinking of re-ECN being deployed voluntarily by 
the end-points first (particularly those like 
LEDBAT that want to prove they are causing *less* 
congestion than others). Then networks deploy ECN 
to prove to their neighbours that congestion had 
already occurred before passing the traffic across a border.

Given re-ECN is trying to encourage everyone to 
co-operate more, there's merit in thinking of 
deployment strategies that start with the 
endpoints yielding, rather than networks constraining first.


>[BB] > True, there might be simpler schemes that 
>don't work, or can be bypassed.
> > But network operators don't want the complexity of deploying many schemes
> > one after the other as each one fails (they are driven to behave like this
> > for lack of good solutions, but they don't want to).
>
>[MM] Precisely the question I wanted to read for - what are the cases that
>RE-ECN covers that pseudo-re-feedback can't address.

[BB] like Joao said:
- non-reliable transports
- the ability to see how much congestion is each side of a border

And I've added:
- reliable transports that morph in response to being detected


> > Bob
> >
> >
>[JTA] >> You'd be missing one of the most important features however - that
> >> information is verifiable across borders by both parties. An ISP can
> >> throttle the duped packets, but why would it voluntarily hinder its
> >> customers when the downstream transit domain is unable to verify whether
> >> such enforcement is taking place?
>
>[MM] I was actually thinking of the last ISP, peering with many "wholesale
>ISPs" and having congested access networks feeding millions of  home
>customers.   It would greatly help such an ISP to be able to discard
>just enough traffic at it's ingresses from other ISP's to limit
>congestion on its access links to its customers.   The whole problem
>and my solution fall within a single ISP.

[BB] Oooh. This is getting close to sending TCP 
resets to off-net connections isn't it?! The 
congestion is caused as much by the whole set of 
traffic in the access network's queues - not just 
off-net traffic but on-net too.

This hilites the Internet's problem - we have an 
internetwork where off-net traffic is somehow 
perceived as less worthy. One of the aims of 
re-ECN is to ensure that this access net can 
treat incoming traffic as if it is as valuable as 
on-net traffic. Visible congestion information at 
borders can be used in contracts & settlements 
between networks so they can recompense each 
other if costs don't balance, rather than 
dropping traffic - dropping is an admission of failure to my mind.

It's not good business to throw away traffic 
without knowing whether it would be willing to pay to be spared!


>[JTA] >> Congestion may come from within the ISP 
>itself, but I'm not certain the ISP can reliably 
>infer the location of such congestion at the ingress.

[BB] I think Joao's saying:
a) that on-net traffic as well as off-net causes congestion in the access
b) that dup detection reveals e2e congestion, so 
it doesn't say whether the congestion the 
arriving packet reveals is in the access net, or off-net elsewhere.

On the other hand, re-ECN doesn't just expose e2e 
congestion, it also exposes how much congestion is downstream of the border.

>[JTA] >> Something like multipath TCP would also 
>make it very hard to figure out whether or not a 
>packet is retransmitted ... which would make a great
> >> incentive for deploying  mtcp.
>
>[MM] I'm sort of missing the point here, but I think some of the problems
>that you are concerned about are the same for RE-ECN and others are
>solved by separating  duplicate detection from enforcement.

[BB] I think Joao is conjecturing that you could 
design an MTPCP where retransmissions were sent 
on different paths to the original loss - in such 
a way they couldn't be identified as 
retransmissions. This could thwart your idea.

With re-ECN the deal the net gives is "Tell me 
how much congestion you are causing (on each 
sub-path), otherwise I'll drop your traffic (from 
each sub-path) before it gets to the destination. 
Having made you truthful, if you say you are 
causing excessive congestion (across all 
traffic), I'll drop your traffic to limit how much congestion you can cause."

With dup detection, the deal is "If I can work 
out how much congestion you're causing from the 
dups (in each sub-flow), and if it's excessive 
(across all traffic), I'll drop traffic to limit 
how much congestion you can cause."

Sorry about the long response.

HTH

Cheers



Bob



> >> Joao.
>
>Thanks,
>--MM--

________________________________________________________________
Bob Briscoe,                                BT Innovate & Design