[Iccrg] Flow Rate Fairness: Dismantling a Religion

[Bob Briscoe]

Doan,

My responses inline - probably about as long as your original, I'm afraid.

At 03:14 27/10/2006, Doan B. Hoang wrote:
>My comment on Bob's paper. It is a bit long (about 2 pages)
>
>Overall, I believe this “cost-base fairness’ approach is refreshing 
>because it enlarges the scope of congestion/fairness and potentially opens 
>up a better class of solutions for both network operators and network users.
>Solutions from this approach may allow a network operator to operate its 
>network effectively by separating its internal concerns from its external 
>concerns. Internally, it may manage its network in any way it sees fit 
>(flow rate, implicit, explicit, etc.). Externally, it has more freedom in 
>providing new classes of solutions to satisfy its customers from the 
>network edge (cost-based, fairness, security, mobility, etc)

This isn't the intention at all. Knowledge of congestion is of utmost 
importance for both external and internal management, because it represents 
the primary of the two factors that any business is concerned with: cost 
(the other being benefit).

>Solutions from this approach may deliver network users (customers) proper 
>means to deploy better strategies (in using the network) to deliver the 
>required performance for their applications.
>I believe that this approach deserves further exploration.

This appraoch has had intensive exploration for the last decade.

>However, to make effective the argument for cost-base fairness, the paper 
>should define its scope more clearly. In particular, it should point out that
>1) Congestion and Fairness are two distinct issues.

They are different but not distinct. When a resource is congested, those 
wanting to use it must be given (or take) some share each, which determines 
fairness. No-one can avoid making this choice. Therefore, the two issues 
cannot be separated.

>2) One can provide a perfect solution to congestion problem without being fair

One can provide *a* solution to congestion without being fair, but not a 
perfect solution. And certainly a solution that doesn't deal with fairness 
would be of absoutely no interest for production networks.

Although a solution doesn't have to be fair, any solution does have to take 
a position on the *degree* of fairness it provides. Because it has to make 
a choice on the allocations.

>3) Solving “fairness” problem might have noting to do with network congestion.

(see 1)

During periods when there is no congestion, fairness has nothing to do with 
congestion. But when there is congestion, it has to.

>4) The users constitute only one part of the network congestion problem. 
>Congestion occurs when the network operator do no provision network 
>resources adequately, or manage their resources properly. It may occur 
>when users exploit the network aggressively. It may occur as a result of 
>some random events such as unpredictable traffic patterns.

Yes. But when congestion happens, you have to know what to do (ie what the 
fair shares are).

>5) When congestion is not caused by users, should they be penalized?

Congestion is always caused by two things: users's traffic being too large 
AND network capacity being too small. There's never an occaision where any 
other apportionment of blame makes sense.

But a network has to make a choice on how much capacity to provision. Then, 
users get what they can out of it. If, collectively, users demand more than 
is provisioned, that should be a signal that more capacity was needed. But 
if users aren't held accountable for making such demands, one can never 
know whether the demands were serious (rather than just idle attempts to do 
things of little value just because there was no cost to the individual 
user). Demand that survives the deterrent of accountability can be counted 
as real demand.

There is a duality here: making users accountable protects other users from 
idle demands. It also serves as a signal to the network that it should be 
upgrading capacity. In fact, the congestion volume I talk about in the 
paper is proportional to the *monetary* cost of upgrading capacity in order 
to remove the congestion (this has been proved assuming a competitive 
environment - see the ref to MacKieMason & Varian (1995) in the paper). 
That calibrates the "cost to other users" of congestion in monetary terms.



>Most of the arguments for “cost-based fairness” appear in the introduction 
>of the paper hence, I mainly comment on this section. Further comments 
>will be provided if necessary. Bob’s words are in quotes.
>
>Introduction
>
>“Relative flow rates should be the outcome of another fairness mechanism, 
>not the mechanism itself”
>You can say this about the outcome of everything if you stand above the 
>problem and see it from a larger perspective. However, doing so is not 
>always appropriate as from this enlarged problem scope, undesirable 
>complexities may entail.
>In this case (cost-based), it is a good position to take as we need better 
>solutions for congestion control and fairness.
>
>“The metric required to arbitrate cost fairness is simply volume of 
>congestion, that is congestion times the bit rate of each user causing it, 
>taken over time.”
>Very reasonable metric provided that information can be collected 
>accurately and timely, otherwise it can be useless.

As long as ECN marking is used, it is the volume of traffic that each user 
sends that is marked. This is certainly accurate to measure and timely.

If ECN is NOT used, it is NOT easy to collect together information about 
drop, because drop is only measurable as gaps in the transport sequence 
space, so not generically visible at the network layer.


>“this isn’t just some dry academic fairness debate”
>Great. Many of us academic are not dry and quite “fair”.
>
>“because flow rate fairness isn’t even capable of reasoning about 
>questions like, “How many flows is it fair to start between two endpoints? 
>or over different routes?” or, 
..”
>
>Flow rate fairness does not have to answer to these questions as they are 
>outside of its scope.

Any approach that cannot bring this question within its scope, is not a 
useful approach. That is my whole point. We cannot base fairness on a 
myopic system that isn't capable of seeing a big enough picture to cope 
with the issue at hand: fairness.

>Let me explain this. From the network operator view point, it will 
>optimize its operational cost and maximize thee return for the use of its 
>resources. The operation can be divided in two components: internal and 
>external. Internally, it can use whatever congestion control mechanisms 
>and fairness measure to maximize its performance. Externally, this is the 
>job of edge devices that interface with the customers.
>The operator may monitor its customers, performs policing their traffic 
>according to their SLA, or it may even play along with the customers, 
>taking their welfare into account if it chooses to do so. For example, the 
>network operator may take fairness among customers (or economic entities) 
>into account if it thinks that would help in keeping its customers and 
>raising its revenue and minimizing the cost of internal operation.

The point is, that in a competitive market, the operator that 'plays along 
with its customers' most accurately wins. But, normally, a business does 
this in two steps. It knows how much its products cost to produce, and it 
tries to find out what its customers value. It doesn't sell at lower than 
cost (unless it has some strategic reason), and it tries to sell below what 
the customer values. My paper is purely about the cost side - which is the 
only relevant part for standardisation.

At the moment, the Internet doesn't even have an easily accessible metric 
(congestion) to be able to know how much usage costs. Very few businesses 
are in such an uninformed position about their day to day operations. So 
the operators are all over the place. They can't determine whether a 
customer is costing a lot more than they have paid. Or a lot less.

>Here, your “cost-based” fairness may play an interesting role. It is a 
>game between network operator (edge devices) and its customers. Network 
>operator tries to satisfy its customers based on its current resources AND 
>prevent customers from exploit its resources unfairly. The customers try 
>everything to get at least what they pay for, even to get more than their 
>“fair share” (regardless of how fairshare is defined). They may want to 
>spit their flow, mark their packet favorably, etc.

Exactly

>Cost-based fairshare may be effective here, providing one can define the 
>“cost” and its “atomic unit cost” on which “fairness” can be defined.

Which is what Kelly did. He showed that sharing out the cost of congestion 
proportionately with rate (what I call 'cost fairness') led to maximisation 
of the sum of everyone's utility (he showed this only for one set of 
possible utilities, but it is still a strong result as the set was fairly 
general). This is what cost-charging should do in a competitive market, 
which lends strong weight to the idea that these proportionate shares *are* 
the right cost to use.


>Furthermore, there must be some rules by which customers and their network 
>operator both agree upon; otherwise “cost-based fairness” will encounter 
>the same problem that “flow-rate fairness” encountered.

Flow rate fairness had no scientific basis. At least cost-based fairness 
has that.

But I don't agree that this has to be something that customers and 
operators agree on. We don't have to standardise industry business models 
around cost-fairness - that's absolutlely the opposite of what I'm trying 
to do. All I'm saying is that, in a competitive market, price will tend 
towards cost. So we better have a usable metric for cost in the 
architecture. But actually, operators can charge whatever they can get away 
with. They don't have to charge at cost. But they do want to know what the 
cost is, so they can stop users causing more cost than they have paid for.


>“In 1997, the basis of the dominant consensus was completely undermined, 
>but it didn’t even notice”
>Even now we cannot describe congestion adequately due to the limitations 
>of mathematics as well of our understanding of the phenomenon. A paper by 
>Jean Bolot [1] deals nicely with one-bottleneck congestion and I stress 
>“one bottle-neck”. More than that, who knows!

See the carefully worded definition of congestion as a probability in the 
appendix of our paper "Policing Congestion Response in an Internetwork 
using Re-Feedback", which we extend to multiple bottlenecks naturally by 
combinatorial probability.

But, these definitions actually sound a lot more complicated than the real 
systems they model. When packets are lost, that is exactly the measure of 
congestion. When multiple bottlenecks lose packets, the probability of loss 
is combinatorial.

ECN is merely modelling loss, but virtually. So marking is just a proxy for 
discard, and therefore is just as good as drop as a measure of congestion.


>Even now we cannot describe essential characteristics of Internet traffic 
>mathematically, again partly due to the limitations of mathematics, partly 
>due to the lack of measurement data!
>Kelly brilliantly introduced some nice ideas from another domain to 
>networks with the hope that this price-based control could apply 
>effectively in the new domain. Currently, we do not even have a proper 
>model of how customers behave or react to priced-based admission control 
>in a large scale. Unless you can do so, network operator will not take it up.

I'm not proposing price-based control of anything. I'm proposing that 
operators want to keep costs within the price charged, that's similar, but 
very different. It just means they need to know the cost, which is not an 
unreasonable thing for a business to want to know!


>“novel p2p applications have started to thoroughly exploit this vacuum 
>with no guilt or shame, by just running more flows for longer”
>I would not blame P2P applications. Everyone wants to get as much as they 
>can out of the network legitimately. Is it true that network operator has 
>been squeezing as much as they can out of their customers legitimately? It 
>is here that we may provide solutions that help both sides?

I hope my words made it clear that most p2p apps have been doing "innocent 
experimental probing" - I hope it didn't sound like I was blaming them - or 
the operators. It is the lack of clear thinking that is to blame for this 
mess. That's why I come across as angry with the Internet community for not 
having provided thought-leadership, given the necessary ideas are all there 
in the literature.

However, I do so that the arms race is now becoming malicious on both sides 
(in places).


>“Fair allocation of rates between flows isn’t based on any respected 
>definition of fairness from philosophy or the social sciences.”
>Who says that our society is fair and the social sciences that go with it 
>are fair? They are not. Look at the global economic situation. It is only 
>fair to those who can push their wares but not others. Occasionally, it 
>breaks down just like any other systems with even more serious consequences.

Hang on, society doesn't have to be fair for science to be able to define 
fairness. Social science isn't the thing that *is* fair, it's merely the 
thing that reasons about fairness.


>I have done some work on congestion, DiffServ, Edge-to-Edge, and 
>End-to-End QoS. We may continue the discussion in this forum if it is 
>“fair” to other respected researchers.

Yes, I am concerned that others may not be interested - but they don't have 
to read. But, as my early answers made clear, any congestion control 
researcher that doesn't believe they need to understand about fairness 
doesn't deserve their work to be taken seriously!


>[1] Bolot, J., and Shankar, A., “Dynamic Behaviour of Rate-based Flow 
>Control Mechanisms,” ACM Computer Communication Review, 20(4): 35-49, 1990.

Thanks for your interest.


Bob

>Cheers,
>
>Doan

____________________________________________________________________________
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