Subject: [tsv-area] Re: draft-briscoe-tsvarea-fair-00

From: Bob Briscoe <[email-masked]>
Date: Thu, 08 Feb 2007 20:53:01 +0000

Vladimir,

At 17:14 08/02/2007, [email-masked] wrote:
>Hi All,
>
>In my opinion, the draft "Flow Rate Fairness: Dismantling a Religion" 
>(draft-briscoe-tsvarea-fair-00)  by B. Briscoe is timely, well thought 
>out, and clearly written.

Thanks for your kind comments.

>While the draft makes an appealing case that standardization activities 
>can benefit from the latest research on "fairness", it appears that the 
>research community should be challenged by practical and standardization 
>needs to define concept of "fairness" in a situation of flows with 
>different QoS preferences.
>
>It appears that in this, more general situation, the "fairness" should be 
>defined with respect to bits, but with flow specific bit costs, since not 
>all bits "are created equal".  For example bits (packets) with higher 
>scheduling priority impose higher cost on other bits (packets) and thus 
>should have higher cost than lower priority bits (packets).

The relative congestion cost of higher priority delivery (or other forms of 
QoS, e.g. isolated capacity) is indeed necessary to understand fairness.

Some results already exist on this. For instance, for two queues with one 
having strict priority over the other (ok, not a common configuration, but 
bear with me), fairness can be brought within the same framework, where the 
cost of certain bits is revealed by the amount of drop or ECN marking they 
suffer. [From here on, let's only consider ECN]

Let's assume we have a marking algorithm that converts queue length to 
probability of marking (like RED does).

The idea is to ECN mark the higher priority traffic based on the sum of its 
own queue length and that of the lower priority traffic. The logic here is 
that the ECN marking on any one packet represents the probability of it 
congesting /other/ packets. The probability of congestion for a low 
priority packet depends on the sum of both queues. The prob of congestion 
for a high priority packet depends only on its own queue length.

It seems counter-intuitive to ECN mark high priority packets more than low 
priority. But that's only if you think in a TCP-only mindset, where the 
flow would have to go slower if it suffered more marking. QoS can either be 
achieved by priority scheduling or by reacting less to congestion than 
other transports, or both.

To achieve higher rate, a transport could just use the low priority class 
but respond less to congestion. In the process it would cause more 
congestion marking, so it could still be made accountable for the cost of 
its action on others.

If this app also requests a higher priority scheduling class, the queue 
still has to get the marking right to ensure fairness, then a separate 
issue is how the transport reacts to the marks. If it also reacts less than 
other transports it will have achieved higher rate.

But because it has also used priority scheduling it becomes accountable for 
even higher costs on others. This is because, not only is it achieving a 
higher rate, but it's also reduced its risk of suffering delay or drop, 
while the others - those using the low priority class - still suffer this risk.

This approach is proposed and analysed in
"On Packet Marking at Priority Queues" Richard J.Gibbens and Frank P.Kelly
<http://www.statslab.cam.ac.uk/~frank/PAPERS/tac.html>

>On the one hand, fair QoS assignment may be an important issue due to 
>increase in the aggregate utility as a result of the "market segmentation" 
>effect.  On the other hand, fair QoS assignment is a challenging problem 
>for a variety of reasons, including non-additive nature of the "QoS cost" 
>due to statistical multiplexing gain.

The above approach (just imagining the lengths of the two queues are added 
together as an input to the markging algorithm) handles all the stat mux 
issues, because the queues represent the outcome after stat muxing.

>If the issue of fair QoS assignments worth pursuing, I am not sure if IETF 
>or IRTF (or neither) is the appropriate venue for this pursuit.

The case of a strict priority queue is relatively straightforward. Other 
queueing algorithms (probably) get complicated, although it should be 
possible to adopt a principled approach to working out what to do. This 
would certainly be worthwhile work for some research body (IRTF?) to work 
towards consensus on.

>A possible argument for pursuing this issue within (e2e) IRTF is lack of 
>clear understanding if fair QoS assignments is compatible with e2e principle.

Ah, I can answer that one - e2e principle was the whole motivation for this 
work! Creating QoS on the end system by the response to dumb marking on the 
router is definitely in keeping with the e2e principle (though even ECN 
marking on a router is too much for some purists). While various levels of 
router scheduling is one of those things the e2e principle would advise 
"think really hard how you might do this another way first."

However,
i) a router cannot know what traffic changes applications have just fired 
towards it until they hit and
ii) the endpoint transports cannot know what congestion their traffic has 
caused until they get the feedback.
Both processes are separated by finite propagation delays.

So endpoint transports can do QoS with just dumb marking on routers, and 
they can keep the system stable on timescales longer than the shortest RTTs 
through the bottleneck. But they can't avoid occasional overruns within 
sub-RTTs. So it seems the most in keeping you can get to the e2e principle 
is to have all the rate control and QoS smarts on the endpoint, with v 
simple priority scheduling on routers for those rare occaisions it's 
needed. And differential ECN marking on the routers (as described above) to 
regulate fairness.

>It appears that fair QoS assignments may require presence of what D. Clark 
>et al. called "Knowledge Plane".

KP is more about management (of failures, configuration etc). The fairness 
approach I've described is designed to work in a very simple way all the 
time. It certainly doesn't need KP in normal operation. It's continuous 
self-managed control, not management.

Perhaps more relevant is Clark et al's "Tussle in Cyberspace". Even tho the 
minimal router complexity described above is sufficient for e2e QoS, it's 
unlikely router vendors and operators will all want to make things that 
simple :) Even if it's simpler, it moves control away from those who might 
not want to lose control (given that implies losing a market opportunity). 
So simple doesn't always happen, and the Internet architecture has to be a 
broad church which allows more solutions with different control assumptions 
as well. Otherwise, if by design we disallow certian parties being able to 
take control, they will screw the architecture in order to assert control.
Result: a total mess and even more complexity than letting them do more 
complex things by design.

At the same time as Clark et al wrote 'Tussle' I was advising exactly the 
same approach, but I talked in specifics, rather than generalising. For 
instance, wrt QoS I said what I said above in this paper on Architectural 
Principles: <http://www.cs.ucl.ac.uk/staff/B.Briscoe/pubs.html#m3i_arch>
See section 2.3.3. "Control assumptions in QoS technologies"

Cheers

Bob

____________________________________________________________________________
Notice: This contribution is the personal view of the author and does not 
necessarily reflect the technical nor commercial direction of BT plc.
____________________________________________________________________________
Bob Briscoe,                           Networks Research Centre, BT Research
B54/77 Adastral Park,Martlesham Heath,Ipswich,IP5 3RE,UK.    +44 1473 645196

---

From: [email-masked]
Date: Thu, 08 Feb 2007 12:14:36 -0500

Hi All,

In my opinion, the draft "Flow Rate Fairness: Dismantling a Religion" 
(draft-briscoe-tsvarea-fair-00)  by B. Briscoe is timely, well 
thought out, and clearly written.  While the draft makes an appealing 
case that standardization activities can benefit from the latest 
research on "fairness", it appears that the research community should 
be challenged by practical and standardization needs to define 
concept of "fairness" in a situation of flows with different QoS preferences.

It appears that in this, more general situation, the "fairness" 
should be defined with respect to bits, but with flow specific bit 
costs, since not all bits "are created equal".  For example bits 
(packets) with higher scheduling priority impose higher cost on other 
bits (packets) and thus should have higher cost than lower priority 
bits (packets).

On the one hand, fair QoS assignment may be an important issue due to 
increase in the aggregate utility as a result of the "market 
segmentation" effect.  On the other hand, fair QoS assignment is a 
challenging problem for a variety of reasons, including non-additive 
nature of the "QoS cost" due to statistical multiplexing gain.

If the issue of fair QoS assignments worth pursuing, I am not sure if 
IETF or IRTF (or neither) is the appropriate venue for this 
pursuit.  A possible argument for pursuing this issue within (e2e) 
IRTF is lack of clear understanding if fair QoS assignments is 
compatible with e2e principle.  It appears that fair QoS assignments 
may require presence of what D. Clark et al. called "Knowledge Plane".

Regards,
Vladimir