Subject: Re: [Tsvwg] Does anyone have a defence in favour of flow rate fairness?

From: Bob Briscoe <[email-masked]>
Date: Tue, 07 Aug 2007 18:30:14 +0100

Joe,

Sorry I left this thread dangling 5wks ago (with an offlist promise to get 
back to it). Four short family breaks and one IETF later you might still be 
interested...

Key to postings:
> >> >> Joe
> >> > Bob
> >> Joe
> > Bob
>  Joe
Bob

At 03:02 27/06/2007, Joe Touch wrote:
>Bob,
>
>These are all good arguments for IRTF study. See below.

The IETF/IRTF debate is currently fairly moot - Because the current 
'agreed' plan (following an informal ad hoc BoF in Prague, including the 
Transport ADs and the IRTF chair) was to continue building a community of 
interest around re-ECN in parallel to the IETF (thru mailing list below). 
Much the way HIP started. In parallel, the IETF only discusses fairness 
goals, not mechanism - yet. Then when/if the re-ECN community is ready, we 
can choose whether to ask to go IRTF or IETF.

Joining instructions for the [email-masked] mailing list are here:
<https://www1.ietf.org/mailman/listinfo/re-ecn>
(not an official IETF w-g list)

Responses to all your other points follow...

>Bob Briscoe wrote:
> > Joe,
> >
> > At 05:58 26/06/2007, Joe Touch wrote:
> >
> >
> >> Bob Briscoe wrote:
> >> > Joe,
> >> >
> >> > just returned from a week off...
> >> ...
> >> >> "TCP's behavior defines a kind of fairness; staying inside the
> >> bounds of
> >> >> that fairness is what we currently defend, largely because it's
> >> deployed
> >> >> and appears to currently be reasonably sufficient"
> >> >>
> >> >> That does NOT mean we all consider TCP's behavior "flow rate fair",
> >> but
> >> >> rather that TCPs sharing a bottleneck will get some proportion of
> >> >> resources and both make progress, and that new CC mechanisms should
> >> not
> >> >> upend that 'balance' - whatever it currently is.
> >> >
> >> > Hmmm. TCPs each 'make progress' is rather clutching at straws, isn't
> >> it?
> >>
> >> It's a straw that is already firmly in our grasp. You're current
> >> proposal asks us to take a few things on faith:
> >>
> >> 1) that information about the remaining path is more important than
> >> information about the investment thus far
> >
> > I think there's a confusion here. The re-feedback protocol is designed
> > to reveal (D) downstream and (E) e2e path info to network elements, as
> > well as (U) upstream info already visible. They can then use whichever
> > is appropriate for different purposes...
>
>How do you reveal all that information in a single existing field? You
>only get one of upstream or downstream; either you start with a known or
>you end with a known. You can't have both.

It's in the re-ECN I-D
(apologies for the expiry when you tried to access - I fixed with an 
up-issue just before the Chicago IETF 
<http://www.ietf.org/internet-drafts/draft-briscoe-tsvwg-re-ecn-tcp-04.txt>)

I generally rely on colours to explain this. Consider ECN CE marking as 
colouring red. The sender has to colour as many bytes black as arrive red 
at the receiver, otherwise it risks packets being dropped. So each time the 
sender gets feedback of a red mark, it is worth colouring the next packet 
black. Black colouring remains unchanged e2e. Imagine on average there's 3% 
congestion by the end of a flow's path. With the above sender approach, 
looking at this flow anywhere along its length you will see a fraction of 
black bytes that is always 3% on average and a fraction of red bytes 
representing upstream congestion so far.

So in the diag below, if red U(pstream) = 2% of bytes and black E(2e) = 3%, 
you will know that D(ownstream) = E - U = 1%.

> >
> > <---------E-------------->
> > <--U--><------D---------->
> >

When I explained this at the ad hoc BoF in Prague (repeated in Chicago) I 
used a slide that allows you to grasp it quickly (Slide 10):
<http://www.cs.ucl.ac.uk/staff/B.Briscoe/present.html#0703re-ecn_arch>

[BTW, we're not using a "single existing field". Originally, we did manage 
to fit it within the ECN field (described in the original SIGCOMM paper), 
but my colleague worked out an attack on that one, so we had to resort to 
using the evil bit in the IP header. We just had a good ad hoc BoF session 
in Chicago trying to work round having to use the evil bit, to no avail so 
far.]

> > If a network wanted to police each flow's rate response to congestion
> > (which is possible but not necessary), it would use (E) e2e-path congestion
> >
> > If a network wanted to limit the bulk volume of congestion a user was
> > dumping into it, it would use (D) downstream congestion, simply to avoid
> > accounting for congestion that the user was causing in its own network.
> >
> > Neither need to be taken on faith:
> > (E) is what senders use for congestion response today, so the network
> > ingress seeing the same info a fraction of a RTT later allows it to
> > mirror the algo of the sender.
>
>Agreed.
>
> > (D) is the same as (E) at the ingress to a public internetwork if we
> > assume that congestion of the user's own local network is their concern.
>
>That would be a specific protocol for the ingress to public
>internetworks with that assumption. That would be one proposed protocol.

Strictly it would be a specific _use_ of a general protocol.

> > (D) allows a flat priced emulation of the congestion pricing that Kelly
> > proved optimises global utility under reasonable assumptions using tried
> > and tested methodology. Others have relaxed the assumptions and found
> > congestion volume is still the useful metric in all cases.
>
>That would be a case to be made to the IETF as a whole, to get everyone
>on board with your assumption of a goal for this work. I don't think it
>can be assumed, regardless of what has been studied to date.

Yes, I'm well aware that I have to push a rock up a hill, then another, 
then another. But more persuasion is not the same as more research.

Starting the persuasion game was the motivation for the I-D on flow-rate 
fairness vs. cost fairness. And that's why we're planning another more 
forward looking draft (with more skeptical co-authors) on why 
accountability for congestion is all the IETF needs to standardise.

> > Kelly showed that, once sources are accountable for the congestion they
> > cause they will want to prioritise (weight) their individual flows to
> > fit within the overall bulk envelope they choose. So we won't need
> > per-flow policing.
>
>The above statement appears to assume that per-source policing is in
>effect - i.e., that sources are accountable. That's still fairly
>fine-grained, isn't it?

When dealing with accountability, the graininess of the entities that are 
held to account have to match their autonomy.

This fine level of graininess would only be a problem if it had to be done 
remotely from the interface with the fine-grained entity. But we can do 
accountability and enforce it solely locally at the physical interface with 
the entity (trust boundary). And it's recursive, so an entity can be:
- a large ISP (at the interfaces with others at its border routers)
- or a large enterprise or campus (at the interfaces with its ISP/s)
- or a user within an enterprise/campus (interfacing with its site network)
- or a home network (at the interface with its access network ISP)
- or a mobile user (at the interface with its access network ISP)

In all cases accountability only requires a bulk measure of congestion 
volume (the diff between two bulk byte counters - equivalent complexity to 
subtracting two of the bulk byte counters displayed by netstat, once a month).

> > (D) also enables inter-domain accountability to propagate recursively,
> > by simple linear additivity.
> >
> > When we are talking about policing at the ingress to an internetwork,
> > the jump from (E) to (D) isn't a leap of faith, it's just saying let's
> > assume the user's machines all sit at her interface with her public
> > provider. She can 'unfairly' share her own resources as much as she wants.
>
>Right, but under current nets she can basically emulate as many "she"s
>as she wants; that's how we get HTTP opening multiple connections. Won't
>this just encourage multiple IP addresses to get around per-source policing?

No. It's not based on any identifiers. It's based on measurement of all 
traffic physically crossing the interface at a trust boundary.

If you're worried it will break if resources are virtualised, it won't. 
Some entity has to be responsible for the whole bundle of traffic crossing 
an interface (even if the entity is merely the group of users joint and 
severally responsible). Then that entity is responsible for dividing down 
the accountability within the bundle - further upstream where the entities 
separate (e.g. within the OS of a multi-user hosting server).

> > From then on the jump from policing single flows to only policing bulk
> > response to congestion is theory, but certainly not faith. And the
> > theory and its assumptions have been extended and checked ad infinitum
> > by other researchers over the past decade without particular cause for
> > concern. And we/others have built prototypes, built simulations etc.
> >
> > Anyway, you also have (E) to police individual flows if you don't
> > believe the theory-based jump to bulk policing. Spoilt for choice.
>
>(agreed that RTT is a red herring)
>
>...
> >> 2) that information about how resources are used along a path is useful
> >> in a multiparty congestion control system
> >>         vs., e.g., the fact that all component connections react
> >>         the same way, and that congestion relief occurs more rapidly
> >>         than congestion exploration
> >
> > "Info about how resources are used along a path" is exactly what
> > Internet senders use today to do multiparty congestion control
>
>Endpoints know what resources are available between those endpoints;
>that could include multipath. Nothing about today's (ubiquitous)
>congestion control is dependent on a particular path per se. The
>exception would be RSVP and/or XCP which touch routers on a path, but
>they're not exactly widespread (and that's part of the problem we're
>grappling with).

Because it's based on measuring congestion crossing a phys interface, not 
on identifiers, multipath just isn't any more of a problem than single path.

> > All the
> > proposal adds is making this info visible to the entity (the network)
> > that has the incentive to make sure the endpoints respond appropriately
> > to it.
>
>Why is it you think that endpoints aren't already responding
>appropriately to the information they get?

Two answers:
i) Streaming video is on the increase (when we - BT - originally started 
this work we predicted that on day 1 of switching all UK PSTN traffic to 
our new all-IP network, 40% of bytes would be unresponsive VoIP, but 
streamed video is becoming a greater concern now).
ii) TCP doesn't take account of flow duration or number of flows opened by 
one user - so I'm now challenging the community to justify why even using 
TCP as it stands is considered "responding appropriately" to congestion.

>How will this new system
>handle virtual paths and multipath?

See above - non-issue.

> > I'm not proposing we change anything about the dynamics of the
> > algorithms (relief/exploration). All that is necessary is to allow
> > different transfers between apps to behave as if they are w flows, where
> > w is a weight that may be <1 or >1.
>
>That seems nice in principle, but in practice what's to stop an app from
>faking being multiple apps to get more capacity? or multiple endpoints?
>Basically, what's to stop more 'gaming the system'?

Because accountability is not based on counting apps. It's based on how 
much congestion volume an economic entity has contracted to be allowed to 
cause - with its provider network. If it's a server farm, it needs to be 
able to create more congestion, so it contracts to do so. If it's an 
occasional user, she contracts for the minimum. If it's a heavy p2p user, 
she contracts for somewhere in between.

>I agree that the current system can be gamed - we don't really have
>per-connection (it's more like per-connection with RTT weighting, but
>not exactly), and we can open multiple connections to game it. However,
>replacing one game-able system with another doesn't solve that problem.

Pls come back if you manage to game re-ECN. The lastest incarnation has 
proved resistant so far (one spoofing DoS attack remains to be dealt with - 
see security considerations in the I-D).

My colleagues found holes in the original scheme, which we fixed making the 
scheme even simpler at the same time. Steve Bauer of MIT produced a paper 
with some plausible (and some implausible) strategies. Mark Handley also 
found a hole and my colleagues found some more. Since draft-02 all these 
strategies have been closed off ...

...except one of Steve Bauer's that I consider no system should have to 
defend against - the gamer uses perfect future knowledge of the sum of 
everyone else's future actions. If anyone had such knowledge, they could 
game the stock markets, flight-booking markets, goods markets - any market.

> > But, more freedom should be possible to allow experimentation (as with
> > the slower dynamics of TFRC).
>
>That is a ringing endorsement for an IRTF effort.

Well not exactly. Certainly IRTF effort would be nice on how to use the new 
freedom. But not necessarily blocking progress on the basic accountability 
mechanism.

> > However, if in the long distant future we find that everyone must "react
> > the same way" or more likely with some bound on their dynamics to keep
> > the network stable, ingress networks will have an incentive to enforce
> > that, and the necessary info and the control.
> >
> > So revealing info to the network provides evolutionary pressure towards
> > cost-fairness /and/ away from instability.
>
>That, IMO, would be a conclusion from an experiment we have not yet
>conducted. I'd like to see the result before coming to that conclusion.

Whether the network has the info to be able to take control is a fact of 
the proposed scheme, not a question. Certainly more research could be done 
to establish whether this control might be needed for stability in the 
future, but lack of such research results surely needn't hold up a 
mechanism for networks to bound the control of 'irresponsible' users, if it 
becomes necessary.

> >> 3) that your particular system is a good way to do either of the above
> >>
> >> Just asserting that "leave it alone" isn't good enough (which would
> >> likely have strong support), doesn't mean that this particular proposal
> >> is (or is not) a better way forward.
> >
> > I totally agree that I'm saying four things:
> > 1) flow rate fairness is pants (solid argument)
> > 2) cost-fairness is ultility-optimal in theory (solid argument)
> > 3) we have a reasonable implementation for cost fairness that wouldn't
> > require changes to ISP flat pricing (to be worked over by the community)
> > 4) once you have a cost-fairness mechanism, sub-communities can arrange
> > their own different fairness regimes between themselves (arm-wavy but
> > self-evident)
> >
> > If I had just blown apart flow rate fairness, without an alternative I
> > would (rightly) have been given a few cycles of people's attention then
> > ignored.
> >
> > Methinks you do expect too much.
>
>For the IETF, no. For the IRTF, yes. ;-)

As I said, moot at the mo.

Cheers

Bob

>Joe

____________________________________________________________________________
Bob Briscoe, <[email-masked]>      Networks Research Centre, BT Research
B54/77 Adastral Park,Martlesham Heath,Ipswich,IP5 3RE,UK.    +44 1473 645196