[Search] [txt|pdf|bibtex] [Tracker] [Email] [Nits]

Versions: 00 01 02                                                      
Transport Area Working Group                                  B. Briscoe
Internet-Draft                                                  BT & UCL
Expires: April 18, 2007                                 October 15, 2006


               Flow Rate Fairness: Dismantling a Religion
                   draft-briscoe-tsvarea-fair-00.pdf

Status of this Memo

   By submitting this Internet-Draft, each author represents that any
   applicable patent or other IPR claims of which he or she is aware
   have been or will be disclosed, and any of which he or she becomes
   aware will be disclosed, in accordance with Section 6 of BCP 79.

   Internet-Drafts are working documents of the Internet Engineering
   Task Force (IETF), its areas, and its working groups.  Note that
   other groups may also distribute working documents as Internet-
   Drafts.

   Internet-Drafts are draft documents valid for a maximum of six months
   and may be updated, replaced, or obsoleted by other documents at any
   time.  It is inappropriate to use Internet-Drafts as reference
   material or to cite them other than as "work in progress."

   The list of current Internet-Drafts can be accessed at
   http://www.ietf.org/ietf/1id-abstracts.txt.

   The list of Internet-Draft Shadow Directories can be accessed at
   http://www.ietf.org/shadow.html.

   This Internet-Draft will expire on April 18, 2007.

Copyright Notice

   Copyright (C) The Internet Society (2006).

Abstract

   We were moved to write this memo because the applied research and
   standards communities in networking are using completely unrealistic
   and impractical fairness criteria.  The issue is not whether they
   should use this or that allocation scheme; they don't even allocate
   the right thing and they don't allocate it between the right
   entities.  We explain as bluntly as we can that sharing out flow
   rates (as TCP and many other popular fairness mechanisms do) has no
   intellectual heritage from any concept of fairness in philosophy or
   social science, or indeed real life.  Comparing and controlling flow



Briscoe                  Expires April 18, 2007                 [Page 1]


Internet-Draft  Flow Rate Fairness:Dismantling a Religion   October 2006


   rates alone will never achieve fairness and should never again be
   claimed as a fairness mechanism for production networks.  Instead, a
   realistic fairness mechanism must share out the `cost' of each users
   actions on others.

Status

   This memo is posted as an Internet-Draft with an intent to eventually
   progress to informational status.


Table of Contents

   1.  Introduction . . . . . . . . . . . . . . . . . . . . . . . . .  3
   2.  Requirements notation  . . . . . . . . . . . . . . . . . . . .  5
   3.  Fair Allocation of What Among What?  . . . . . . . . . . . . .  5
     3.1.  Structure of Memo  . . . . . . . . . . . . . . . . . . . .  6
   4.  Cost, not Benefit  . . . . . . . . . . . . . . . . . . . . . .  6
     4.1.  TCP-Fairness Equalises Flow Rates Not Costs  . . . . . . . 10
   5.  Economic Entities not Flows  . . . . . . . . . . . . . . . . . 12
     5.1.  Something to Integrate the Allocations . . . . . . . . . . 12
     5.2.  Enforcement of Fairness  . . . . . . . . . . . . . . . . . 15
       5.2.1.  Cheating with Whitewashed or Split Flow Identities . . 15
       5.2.2.  Enforcing Cost Fairness  . . . . . . . . . . . . . . . 17
   6.  Fairness between Fairnesses  . . . . . . . . . . . . . . . . . 18
   7.  The Seminal Literature . . . . . . . . . . . . . . . . . . . . 20
   8.  IANA Considerations  . . . . . . . . . . . . . . . . . . . . . 22
   9.  Security Considerations  . . . . . . . . . . . . . . . . . . . 23
   10. Concluding Remarks . . . . . . . . . . . . . . . . . . . . . . 23
     10.1. A Cautionary Note  . . . . . . . . . . . . . . . . . . . . 23
     10.2. Conclusions  . . . . . . . . . . . . . . . . . . . . . . . 23
     10.3. Further Work . . . . . . . . . . . . . . . . . . . . . . . 25
   11. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 25
   12. Comments Solicited . . . . . . . . . . . . . . . . . . . . . . 25
   13. References . . . . . . . . . . . . . . . . . . . . . . . . . . 26
     13.1. Normative References . . . . . . . . . . . . . . . . . . . 26
     13.2. Informative References . . . . . . . . . . . . . . . . . . 26
   Author's Address . . . . . . . . . . . . . . . . . . . . . . . . . 31
   Intellectual Property and Copyright Statements . . . . . . . . . . 32












Briscoe                  Expires April 18, 2007                 [Page 2]


Internet-Draft  Flow Rate Fairness:Dismantling a Religion   October 2006


1.  Introduction

      "But he has nothing on at all."

         _The Emperor's New Clothes, Hans Christian Anderson_

   With a few notable exceptions, Internet applied research and
   standards seem to be afflicted by a collective delusion that fairness
   between traffic competing for network resources can be achieved by
   controlling relative flow rates alone.  It cannot.  To be absolutely
   clear, this accusation covers widely deployed algorithms such as TCP
   congestion control and all the variants of fair queuing.

   Controlling relative flow rates _alone_ is a completely impractical
   way of going about the problem.  To be realistic for large-scale
   Internet deployment, relative flow rates should be the _outcome_ of
   another fairness mechanism, not the mechanism itself.  That other
   mechanism should share out the `cost' of one user's actions on
   others---how much each user's transfers restrict other transfers,
   given capacity constraints.  Then flow rates will depend on a deeper
   level of fairness that has so far remained unnamed in the literature,
   but is best termed `cost 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.  In engineering terms, for each user it
   can be measured very easily as the amount of data sent that the
   system fails to serve.  Or with explicit congestion notification
   (ECN [RFC3168]) the amount of each user's data to have been
   congestion marked.  Importantly, unlike flow rates, this metric
   integrates correctly across different flows on different paths and
   across time.

   What we call cost fairness has been in the literature for nearly a
   decade, but it hasn't been put so bluntly before.  We were moved to
   spell it out unambiguously, because this isn't just some dry academic
   fairness debate that might change allocation percentages somewhere in
   the third decimal place.  The outcomes due to flow rate fairness that
   we see on the Internet today are hopelessly unlike the outcomes that
   would result from cost fairness.

   Not that the outcomes we see are the deliberate intent of flow rate
   fairness.  They are the random result of an absence of fairness
   control, 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, "What rate is fair for a
   flow that has been running longer than another?".




Briscoe                  Expires April 18, 2007                 [Page 3]


Internet-Draft  Flow Rate Fairness:Dismantling a Religion   October 2006


   Resource allocation and accountability are two issues that reappear
   on every list of requirements for a new Internet
   architecture [NewArchReq].  We could have started filling this
   architectural vacuum a decade ago, but architecture not only requires
   foundational ideas, it also requires consensus.  In 1997, the basis
   of the dominant consensus was completely undermined, but it didn't
   even notice.

   While everyone prevaricates, novel p2p applications have started to
   thoroughly exploit this vacuum with no guilt or shame, by just
   running more flows for longer (after all, they are using TCP, which
   is fair isn't it?).  In response, ISPs are introducing kludges like
   volume caps or throttling specific applications using deep packet
   inspection.  Innocent experimental probing has turned into an arms
   race.  The p2p community's early concern for the good of the Internet
   is being set aside, aided and abetted by large commercial concerns,
   in pursuit of a more pressing battle against the ISPs that are
   fighting back.  The rest of the Internet is suffering heavy
   collateral damage.  This trend has spread beyond the p2p community.
   There is now no shame in opening multiple TCP connections, or
   offering VoIP or video streaming software without any congestion
   control.

   Whether the prevailing notion of flow rate fairness has been the root
   cause or not, there will certainly be no solution until the
   networking community gets its head out of the sand and understands
   how unrealistic its view is.  Only then will there be a climate in
   which solutions can be adopted.

   But isn't it a basic article of faith that multiple views of fairness
   should be able to co-exist, the choice depending on policy?
   Absolutely correct---and we shall return to how this can be done
   later.  But that doesn't mean we have to give the time of day to any
   random idea of fairness.

   Fair allocation of rates between flows isn't based on any respected
   definition of fairness from philosophy or the social sciences.  It
   has just gradually become the way things are done in networking.  But
   it's actually self-referential dogma.  Or put more bluntly, bonkers.

   We expect to be fair to people, groups of people, institutions,
   companies---things the security community would call `principals'.
   But a flow is merely an information transfer between two
   applications.  Where does the argument come from that information
   transfers should have equal rights with each other?  It's equivalent
   to claiming food rations are fair because the boxes are all the same
   size, irrespective of how many boxes each person gets or how often
   they get them.



Briscoe                  Expires April 18, 2007                 [Page 4]


Internet-Draft  Flow Rate Fairness:Dismantling a Religion   October 2006


   Because flows don't deserve rights in real life, it is not surprising
   that trying to allocate rate fairly to flows has two inherent
   loopholes the size of barn doors when it is attempted in a non-co-
   operative environment.  If at every instant a resource is shared
   among the flows competing for a share, any real-world entity can gain
   by i) creating more flows than anyone else, and ii) keeping them
   going longer than anyone else.

   We appeal to the networking community to quietly set aside fairness
   between flow rates.  It had its time, but now it has been shown to be
   unfounded, unrealistic and impractical.  Papers and standards
   proposals using it should be rejected.  And no-one should ever have
   to cater for it in future Internet protocols---it places stupid
   arbitrary requirements on the system that are impossible to meet and
   wouldn't achieve any meaningful sort of fairness even if they could
   be met.

   Alternatively, someone should write a defence of flow rate fairness.
   Continuing to use flow rate fairness as the dominant ideology,
   without rebutting Kelly's seminal 1997 paper that undermined it, just
   leaves the Internet community divided into religious sects, making a
   mockery of the scientific process towards consensus.


2.  Requirements notation

   The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
   "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
   document are to be interpreted as described in [RFC2119].


3.  Fair Allocation of What Among What?

   The issue with flow rate fairness is far more basic than whether
   allocations should be max-min, proportional or whatever.  Flow rate
   fairness doesn't even allocate the correct thing.  And it doesn't
   allocate it among the correct entities either.  At this most basic
   level we will contrast the two main contending views:

   o  Allocate rate among flows (flow rate fairness)

   o  Allocate congestion cost among the bits sent by economic entities
      (cost fairness)

   When cost fairness was proposed, it stated its case in terms of the
   dominant belief system---flow rate fairness.  Unfortunately, this
   meant that the dominant belief system didn't notice it had been
   struck an intellectual death blow.  Its believers carried on



Briscoe                  Expires April 18, 2007                 [Page 5]


Internet-Draft  Flow Rate Fairness:Dismantling a Religion   October 2006


   regardless and it remains dominant today.

   As a result, one sees talk of weighted proportional fairness in the
   same context as proportional, max-min (or min-max) fairness as if
   they are all members of the same set.  They are not.  Weighted
   proportional fairness has an extra weight parameter w that all the
   others lack.  With weighted proportional fairness, the interesting
   bit is what regulates users in their choice of w.  Otherwise, it
   would hardly be a useful definition of fairness to say it is fair for
   flow A to go w times as fast as flow B, if the user behind flow A has
   free choice of w.

   In fact, it turns out that the interesting bit is nothing to do with
   flows, or their weights.  For internetworking the _only_ interesting
   definition of fairness depends on the allocation of cost among the
   bits sent by economic entities, regardless of which flows the bits
   are in.  A user's choice of w then depends on that.

3.1.  Structure of Memo

   The body of this memo is structured around our question, "Fair
   allocation of what among what?":

   o  Section 4 answers the "...of what...?" question, explaining why
      fair allocation of costs is a sufficient and realistic form of
      fairness, and allocation of rate is not.  A sub-section also
      explains why TCP fair rate control (TFRC) causes greater
      congestion costs than TCP, because it wrongly tries to achieve
      equality of flow rate.

   o  Section 5 answers the "...among what?" question, explaining why
      fairness among flows can only be myopic whereas fairness among
      economic entities naturally brings history into the reckoning.
      Also fairness among flows is shown to be hard, if not impossible
      to enforce, while enforcing fairness among economic entities is
      practical.

   Having debunked the dominant ideology of flow rate fairness, and
   replaced it with cost fairness, in Section 6 we discuss how other
   forms of fairness can be asserted locally.  Then, before we draw
   conclusions, Section 7 maps the progression of seminal ideas in the
   literature on which this memo is based.  A FAQ Web page [FairFAQ] is
   planned to answer some frequently asked questions that didn't fit
   easily into the main flow of the memo.


4.  Cost, not Benefit




Briscoe                  Expires April 18, 2007                 [Page 6]


Internet-Draft  Flow Rate Fairness:Dismantling a Religion   October 2006


   The issues of fair allocation of resources comes under the domain of
   political economy (or philosophy).  In Section 6 we will discuss how
   different fairness policies can co-exist.  But to answer our
   question, "Fair allocation of what?" we start from the premise used
   in economics (and life) that fairness concerns comparing benefits,
   costs or both.

   The benefit of a data transfer can be assumed to increase with flow
   rate, but the shape and size of the function relating the two (the
   utility function) is unknown, subjective and private to each user.
   Flow rate itself is an extremely inadequate measure for comparing
   benefits: user benefit per bit rate might be ten orders of magnitude
   different for different types of flow (e.g. SMS and video).  So
   different applications might derive completely different benefits
   from equal flow rates and equal benefits might be derived from very
   different flow rates.

   Turning to the cost of a data transfer across a network, flow rate
   alone is not the measure of that either.  Cost is also dependent on
   the level of congestion on the path.  This is counter-intuitive for
   some people so we shall explain a little further.  Once a network has
   been provisioned at a certain size, it doesn't cost a network
   operator any more whether a user sends more data or not.  But if the
   network becomes congested, each user restricts every other user,
   which can be interpreted as a cost _to all_---an externality in
   economic terms.  For any level of congestion, Kelly
   showed [wPropFair] that the system is optimal if the blame for
   congestion is attributed among all the users causing it, in
   proportion to their bit rates.  That's exactly what routers are
   designed to do anyway.  During congestion, a queue randomly
   distributes the losses so all flows see about the same loss rate (or
   ECN marking rate); if a flow has twice the bit rate of another it
   should see twice the losses.  In this respect random early detection
   (RED [RFC2309]) is slightly fairer than drop tail, but to a first
   order approximation they both meet this criterion.

   So in networking, the cost of one flow's behaviour depends on the
   congestion volume it causes which is the product of its instantaneous
   flow rate and congestion on its path, integrated over time.  For
   instance, if two users are sending at 200kbps and 300kbps into a
   450kbps line for 0.5s, congestion is (200+300-450)/(200+300) = 10% so
   the congestion volume each causes is 200kx 10%x 0.5 = 10kb and 15kb
   respectively.

   So cost depends not only on flow rate, but on congestion as well.
   Typically congestion might be in the fractions of a percent but it
   varies from zero to tens of percent.  So, flow rate can never alone
   serve as a measure of cost.



Briscoe                  Expires April 18, 2007                 [Page 7]


Internet-Draft  Flow Rate Fairness:Dismantling a Religion   October 2006


   To summarise so far, flow rate is a hopelessly incorrect proxy both
   for benefit and for cost.  Even if the intent was to equalise
   benefits, equalising flow-rates wouldn't achieve it.  Even if the
   intent was to equalise costs, equalising flow-rates wouldn't achieve
   it.

   But actually a realistic resource allocation mechanism only needs to
   concern itself with costs, because normally we use the market economy
   to handle the benefits side, as we shall now explain.

   In life, as long as people cover the cost of their actions, it is
   generally considered fair enough.  If one person enjoys a hot shower
   more than their neighbour enjoys the toast they made with equal units
   of electricity, no-one expects the one who enjoyed the shower to have
   to pay more.  If someone makes more of their lot in life than
   another, some complain it's not fair, but most call this envy, not
   unfairness.

   Market economics works on the same premise (unsurprisingly given life
   and market economics are closely related).  In fact, a market adjusts
   supply to meet demand so that benefits are as fairly distributed as
   is consistent with the pre-existing inequalities in life.  But this
   fairness between benefits is an _outcome_ and it is only met as long
   as there is a market mechanism to make people accountable for the
   costs of their actions (as long as various market failures are
   avoided).

   We deliberately say `make people accountable' to avoid the phrase
   `make people pay', because users tend to prefer to pay a flat rate
   subscription for Internet access in which case their ISP is likely to
   limit the congestion they are able to cause to what they have paid
   for (Section 5.2.2).

   If we do make users truly accountable for the cost of the congestion
   they cause, a form of fairness between flow rates emerges
   automatically.  As everyone increases the rate of each of their
   flows, congestion rises.  As congestion rises, everyone pays due
   regard to the share of the cost attributed to them.  So, each
   individual will want their congestion control algorithm to
   continuously adjust its rate to maximise their net utility---benefit
   minus cost.  Kelly [wPropFair] shows that even if each user keeps
   their utility function private but we _model_ all the different users
   by an arbitrary weight that scales their utility function relative to
   the others, users will allocate themselves flow rates in proportion
   to the share of the cost that they cause---weighted proportional
   fairness.

   But such a flow rate allocation is not the measure of fairness, it is



Briscoe                  Expires April 18, 2007                 [Page 8]


Internet-Draft  Flow Rate Fairness:Dismantling a Religion   October 2006


   merely a possible _outcome_ caused by cost fairness, given some
   assumptions about how to model the shape of users' private utility
   functions.  Enforcing underlying cost fairness is in itself a
   sufficient form of fairness.  We repeat: _the resulting relative flow
   rates are not the measure of fairness_.

   Most importantly, but perhaps tangentially to our focus on fairness,
   Kelly proved cost fairness would maximise the aggregate of everyone's
   utility across the whole Internet.  This is why cost fairness is so
   important, as other forms of fairness cannot be better, unless some
   major flaw is found in the assumptions.  Kelly _et al_ also proved
   that, even though relative flow rates would likely be very different
   from those seen today, the Internet would remain stable given
   reasonable constraints and assumptions [wPropStab].

   While on the subject of assumptions, we should add that the benefit
   of a real-time application depends on jitter, not just transfer rate.
   But simple scaling arguments show that it will be possible for
   network operators to minimise congestion delay as networks increase
   in capacity ([SelfMan] S.2), an argument supported by recent research
   showing that router buffers are often significantly
   oversized [BufSizUp].

   Proponents of flow-rate fairness might be forgiven for aiming for an
   `unrealistic' form of fairness if a `realistic' form was difficult to
   implement in practice.  However this is not the case at all, because
   congestion costs are already used by Internet congestion control---
   only minor changes are needed.  In fact, it is flow rate fairness
   that is completely impractical to enforce---see Section 5.1.

   But how would users "allocate themselves flow rates in proportion to
   the share of the cost that they cause"?  If they were made
   accountable for congestion, they would install a version of TCP with
   a weight parameter (for example MulTCP [MulTCP]), at least for TCP-
   based applications.  Of course, most users wouldn't want the fuss of
   weighting each individual flow.  But if they chose to set policies on
   average for large classes of flows (or to accept the defaults set by
   application developers), the resulting suboptimal outcome for
   themselves would be their own private choice to trade optimality
   against hassle.  The underlying fairness criterion would still be
   met: that people should be accountable for the costs they cause to
   others.

   In contrast, with flow-rate fairness, two flows may cause orders of
   magnitude different costs to others (for instance if one has been
   running orders of magnitude longer) by running at equal rates.
   Nowhere do we find any justification for the dogma that flow rates
   must be equal to be fair.  Nowhere do we find any rebuttal of Kelly's



Briscoe                  Expires April 18, 2007                 [Page 9]


Internet-Draft  Flow Rate Fairness:Dismantling a Religion   October 2006


   destruction of flow rate fairness, even after nine years.

4.1.  TCP-Fairness Equalises Flow Rates Not Costs

   An algorithm that controls flow rate in response to congestion is
   defined as TCP-compatible if it complies with the specification for
   TCP congestion control [RFC2581].  An algorithm that converges on the
   same flow rate as TCP at equilibrium but with different dynamics is
   called TCP-friendly, but not TCP-compatible.  Certain streaming
   applications won't work unless they are allowed a more sluggish
   response to congestion than TCP's, so researchers invented the
   concept of `TCP-fairness' to define fair use of the network in
   competition with TCP-compatible flows.

   `TCP-fair' congestion control currently has proposed standard status
   in the IETF [RFC3448], and it is incorporated into one of the
   congestion control profiles of the new datagram congestion control
   protocol (DCCP [RFC4342]) that is also a proposed standard.
   Unfortunately `TCP-fairness' was defined as equality of flow rates
   without regard to costs.  Consequently, as we shall explain, `TCP-
   fair' flows with a sluggish response to congestion cause more
   congestion than TCP-compatible flows on the same path.

   To be clear, the extra congestion caused by `TCP-fair' flows,
   relative to TCP-compatible ones, is not our major concern.  We merely
   use this case to illustrate the broken logic of flow rate fairness.
   The fairness problems outlined in the next section (`Economic
   Entities not Flows') afflict _both_ TCP-compatibility and `TCP-
   fairness' and have far greater impact on Internet users than this
   minor extra problem with TCP-fair flows.





















Briscoe                  Expires April 18, 2007                [Page 10]


Internet-Draft  Flow Rate Fairness:Dismantling a Religion   October 2006


         |
         |
         |
         |
         |
         |
         |
         |
         |
         |
         |
         |
         |
         |
         |
         |See draft-briscoe-tsvarea-fair-00.pdf version for figure here
         |
         |
         |

    Figure 1: Schematic showing `TCP-fair' flows cause more congestion
    than TCP. A TCP-fair flow is smoother than a TCP-compatible one but
   with the same mean rate if measured over long enough time. Therefore
     at times of high congestion (t_2) it uses more bandwidth than TCP
           while at times of low congestion (t_1) it uses less.

   In order to fairly allocate network resources, all TCP-compatible and
   TCP-fair congestion control algorithms communicate with each other
   through the congestion signals coming from network resources.  So
   they actually all have the information necessary for cost-based
   fairness.  But the goal of TCP-fairness was chosen to be equalisation
   of flow-rate not of flow-rate x congestion.  If a flow needs a
   sluggish response to congestion, TCP-fair rate control keeps it to
   the same equilibrium rate that a TCP-compatible flow would achieve
   across the same path.  This complex reverse engineering results in a
   flow that causes more volume of congestion than TCP would in similar
   circumstances.  In terms of rate, it _seems_ fair, but in terms of
   cost it is not.  If a flow with a more sluggish rate response is to
   cause an equal volume of congestion relative to a TCP flow on the
   same path, on average it will have to go slower.

   To explain, we need to remember that both congestion and flow rate
   vary over time.  A more nimble congestion response like TCP's can
   mirror changing congestion fairly faithfully.  It reduces its rate
   quickly during periods of higher congestion and increase again more
   quickly whenever congestion falls.  In Figure 1 the resulting
   schematic plots of congestion and flow rate are shown as mirror
   images of each other.  A more sluggish rate response is not as good



Briscoe                  Expires April 18, 2007                [Page 11]


Internet-Draft  Flow Rate Fairness:Dismantling a Religion   October 2006


   at tracking the fast-changing congestion process.  So the sluggish
   flow more often uses higher bandwidth when congestion is high, and
   more often uses lower bandwidth when congestion is low, causing more
   volume of congestion on average.  Giving more during times of plenty
   doesn't compensate for taking it back during times of scarcity.

   Incidentally, during the standardisation of TCP-fairness, all sorts
   of other issues arose when trying to equate a real-time flow to a TCP
   flow.  Unlike typical TCP streams, some real-time applications have
   variable packet sizes and many have a maximum _required_ rate,
   sometimes also varying rapidly.  In contrast, TCP streams have no
   maximum desired rate.  Cost fairness is capable of encompassing all
   these issues, whereas flow-rate fairness required (and still
   requires) continual patching with new arbitrary ideas about fairness
   for each new circumstance.

   We are not saying it is easy for a sluggish flow to infer what
   congestion volume a TCP flow would have experienced.  However, as
   long as congestion costs are accounted for, we don't have to equalise
   costs _per flow_ anyway---as we are about to explain.


5.  Economic Entities not Flows

5.1.  Something to Integrate the Allocations

   Imagine loaves of bread are regularly delivered to a famine-struck
   refugee camp.  Each time a loaf is brought out, a queue forms and the
   loaf is divided equally among those in the queue.  If the individuals
   who appear in each queue are always different, except for one who
   always appears in every queue, would it still be fair to share each
   loaf equally among those in each queue?

   Of course not---commercially realistic fairness policies must depend
   on an individual's history.  But if that isn't a convincing argument,
   it doesn't have to be.  We don't have to show that fairness policies
   _should_ depend on history, only that realistic ones _probably will_.
   So a fairness mechanism that claims to support commercially realistic
   fairness policies needs to be structured so that individual history
   can be added without destroying scalability.  And here, `individual'
   means some real-world entity with an economic existence, not a flow.

   Router-based flow rate fairness mechanisms tend to have to be myopic.
   To be otherwise would seem to require holding the history of most
   Internet connected individuals on most routers.  Because, at most
   routers, a flow from nearly any individual in the world might appear.
   So instead, router-based schemes tend to share out flow rate at each
   instant without regard to individual history---and hence without



Briscoe                  Expires April 18, 2007                [Page 12]


Internet-Draft  Flow Rate Fairness:Dismantling a Religion   October 2006


   regard to commercial reality.

   One reason for our frustration with the networking community's focus
   on flow rate fairness is that the TCP/IP-based architecture of the
   Internet already has a structure very close to that required to
   arbitrate fairness based on the costs that individuals cause, rather
   than on flow rates.  Instead of arbitrating fairness on routers,
   fairness is already arbitrated scalably at the endpoints where the
   congestion costs of each individual are already collected together.

   Congested routers generate cost signals (losses or ECN marks) that
   are carried to the transport causing the congestion, piggy-backed in
   the packet stream either as gaps in the transport stream or as ECN
   marks.  These congestion signals are already fed back to the sending
   transport by nearly all transport protocols.  And congestion control
   algorithms like TCP already adapt their flow rates in response to
   congestion.  So all we would need to change would be to use a
   weighted TCP algorithm [MulTCP] (or equivalent for inelastic
   applications) that could weight itself under the control of a process
   overarching all the flows of one user, which would take into account
   the user's cost history across all flows.

   Of course, there is no incentive for anyone to voluntarily subject
   themselves to such fairness (nonetheless, they already subject
   themselves to TCP which voluntarily halves its rate whenever it
   senses congestion).  But as we shall see in Section 5.2.1, policing
   fairness between individuals (and between networks) at their point of
   attachment to the Internet has already been solved, whereas getting
   every router to police fairness between every individual connected to
   the Internet is a pipedream, because it would be really complicated
   for routers to have to know about individuals.

   So, how come one attachment point can arbitrate fairness between
   everyone on the Internet when it only knows about locally attached
   individuals?  Do we have to add some fully connected mesh of co-
   ordination messages between every end-point in the world?  The answer
   is no, because, in a very subtle sense, we already have such a mesh.
   The thing that keeps fairness at one end-point in line with all the
   others is the commonly aligned understanding of _cost_ throughout the
   globe.  Cost in any part of the world has an exchange value with cost
   in any other part, because, wherever there's an Internet attachment,
   there's a connection with the global economy.  Even if some localised
   authority asserts a non-economic variant of fairness between some
   sub-set of users (e.g. in a university or corporation), the authority
   as a whole will still align its understanding of cost with that of
   the global economy (see Section 6).

   So far we have talked of volume of congestion as a cost to other



Briscoe                  Expires April 18, 2007                [Page 13]


Internet-Draft  Flow Rate Fairness:Dismantling a Religion   October 2006


   users without calibrating it---specifying how it relates to monetary
   cost.  In fact, in a competitive market, the monetary cost assigned
   to congestion volume turns out to be the same as the marginal cost of
   the capacity needed to alleviate the congestion [PrCong] (see
   FAQ [FairFAQ] for details).  The user would be unlikely to see this
   as a direct charge, instead a flat subscription fee would be
   considered to include it, in which case the ability to cause
   congestion would have to be limited by a policer.

   Once we have a connection between Internet fairness and economic
   fairness, the problem of myopia just melts away.  The cost that one
   individual causes is integrated over time for all her flows, by that
   individual herself.  The more cost she causes to others over time and
   over flows, the more cost she is made to suffer herself.  No system
   has to guess how quickly different people discount benefits and costs
   experienced in the past, because both are discounted privately by the
   user just like all the other benefits and costs everyone assimilates
   in their daily lives.

   To manage a system the size of the Internet as a whole, flow rate
   fairness comes nowhere near being up to the job.  It just isn't
   realistic to create a system the size of the Internet and define
   fairness within the system without reference to fairness outside the
   system---in the real world where everyone grudgingly accepts that
   fairness usually means "you get what you pay for".

   Of course, there will be no need to be too precise about that rule.
   Perhaps some people will get more than they pay for and others less.
   Perhaps some people will pay for what they get (pay as you go), while
   others will prefer to be limited to getting what they have paid for
   (fixed contract).  Perhaps some people will be prepared to pay for
   what others get, and so on.  And, as we shall see (Section 6),
   pockets that may be the size of whole countries can define fairness
   their own way, within the constraint that the whole pocket pays for
   what it gets.

   But whatever `business model' is used, if individuals run up massive
   volumes of congestion in small increments over a long time, the
   balance can be stored in that ingenious invention, the customer
   account, because we have a technical metric that can be equated to a
   financial metric: cost.  And that other ingenious invention, the
   networking business is well versed in the art of taking deposits,
   limiting spending within a credit limit, managing the rate at which
   credit can be built up and so on.  And, of course, the concept of a
   customer account also naturally ensures that a user cannot escape
   accountability merely by roaming or mobility.  Finally, note well
   that this `business' and `account' terminology doesn't preclude peer-
   to-peer creations that arbitrate the resources of a self-provided



Briscoe                  Expires April 18, 2007                [Page 14]


Internet-Draft  Flow Rate Fairness:Dismantling a Religion   October 2006


   community network [ArchP2pEcon].

   Of course, the details of all this dirty commercial reality don't
   have to concern the research or the networking standards communities.
   It is sufficient to design protocols so that congestion costs _can_
   be integrated together at some higher layer across different flows
   and across time, so that senders _can_ be made accountable for the
   congestion they cause.  Systems and protocols intended for Internet
   deployment do not have to _always_ realise the sort of fairness over
   time that we find around us in the real world, but they must _be
   able_ to.

5.2.  Enforcement of Fairness

   This section drives the final nail into the coffin of flow rate
   fairness, exposing flaws that even those within the box have to turn
   a blind eye to, in order to convince themselves that the world within
   the box is perfectly consistent.

5.2.1.  Cheating with Whitewashed or Split Flow Identities

   In the real world of deployed networks, if it is easy to cheat the
   fairness mechanism to get an unfair allocation, it's hardly a useful
   fairness mechanism.  All known flow rate fairness mechanisms are wide
   open to cheating.

   For instance, if I am the customer of a system giving max-min flow
   rate allocations, it is in my interest to split the identities of my
   flows into lots of little flows until they are all less than the
   minimum allocation.  Then the system will dance to my tune and reduce
   the allocations of everyone else in order to increase all the little
   allocations of my flows.  The more I split my traffic down across
   more and more identifiers, the larger share of the resource all my
   flows taken together will get.

   If a history-based fairness mechanism (Section 5.1) believes it
   should allocate fewer resource to one flow identifier that it
   considers has already been given enough, it is trivially easy for the
   source behind that identifier to create a new identifier for its
   traffic with a whitewashed reputation.

   And it's no good imagining that a router will be able to tell which
   flow IDs are actually all from the same entity (either in the
   security sense or the economic sense), because routers have to
   arbitrate between flows emanating from networks many domains away.
   They cannot be expected to know which sets of flow identifiers should
   be treated as a single entity.  Flows between a pair of IP addresses
   may even be attributable to more than one entity, for instance, an IP



Briscoe                  Expires April 18, 2007                [Page 15]


Internet-Draft  Flow Rate Fairness:Dismantling a Religion   October 2006


   address may be shared by many hundreds of people on a Web or e-mail
   hosting site.

         |
         |
         |
         |
         |
         |
         |
         |
         |
         |
         |
         |
         |
         |
         |
         |See draft-briscoe-tsvarea-fair-00.pdf version for figure here
         |
         |
         |

      Figure 2: Splitting flow identifiers to cheat against flow rate
                                 fairness.

   Bottleneck policers [pBox],[XCHOKe],[AFD], suffer from the same
   inherent problem.  They look for a flow ID at a bottleneck that is
   consuming much more bit rate than other flows in order to police use
   of TCP.  But anyone can cheat by simply running multiple TCP flows.
   If the policer looks for cheating pairs of source-destination IP
   addresses, without regard to port numbers, a pair of corresponding
   nodes can still cheat by creating extra flows from spoofed source
   addresses after telling each other out of band where to send
   acknowledgements (or just not using acks).  Alternatively, pairs of
   corresponding nodes can collude to share a portion of each other's
   flows.

   For instance, if the three pairs of nodes in Figure 2 are trying to
   communicate, the senders can act as stepping stones for each other so
   that their three (n) flows appear as nine (n^2) across the bottleneck
   link in the middle.  In effect, they have created a routing overlay,
   much like BitTorrent file-sharing software does.  If one pair of
   naive nodes competes for this bottleneck against n pairs of nodes
   adopting this strategy, it will get about n times smaller share than
   each of the other pairs, assuming n is large.

   Given identifiers can generally be freely created in cyberspace, it



Briscoe                  Expires April 18, 2007                [Page 16]


Internet-Draft  Flow Rate Fairness:Dismantling a Religion   October 2006


   is well-known that they shouldn't be relied on for resource
   allocation (or more generally for negative
   reputation) [FrRideP2p],[CheapPseud].  Kelly [wPropFair] chose cost-
   based fairness (his term was `pricing per unit share') because it was
   immune to this problem---it allocates cost to bits not to flows and
   hence doesn't rely on any cyber-identifiers.

   In summary, once one accepts that fairness should be based on
   concepts from social science, fairness can only be meaningful between
   entities with real-world identities---humans, organisations,
   institutions, businesses.  Otherwise two entities can claim to have
   arbitrarily many flows between them, making fairness between flows
   completely meaningless.

5.2.2.  Enforcing Cost Fairness

   If enforcing flow rate fairness is impractical, is enforcing cost
   fairness any more achievable?  Happily, the Internet's architecture
   is already suited to carrying the right cost information for cost
   fairness mechanisms to be enforced in a non-co-operative environment.

   Kelly's stated motivation for his focus on pricing was so that the
   system would be applicable to a non-co-operative environment.  In
   1999, Gibbens and Kelly went further, pointing out [Evol_cc] that
   ECN [RFC3168] provided an ideal basis on which to base cost fairness.
   The idea was simply for network operators to ECN mark traffic at
   congested routers without regard to flows, then to apply a price to
   the volume of traffic carrying ECN marks, which would make the
   transport endpoints accountable for the congestion they caused.

   However, understandably, the idea of Internet retailers charging
   their end-customers directly for congestion met strong resistance.
   Customers are known to be highly averse to unpredictable charges for
   services ([PMP] S.5) so duration charging for each Internet flow was
   unlikely to replace flat monthly charging.

   Many threw out the baby with the bath water, associating Kelly's
   theoretical work solely with its suggested implementation.  But over
   the ensuing years, an active research community has sought to keep
   the underlying theory but wrapped around with a more realistic
   incarnation.

   Indeed the recent proposal called re-ECN [Re-TCP] does just that.  It
   requires no change to typical flat rate Internet contracts, but it
   enables addition of a per-source policer that can limit the volume of
   congestion a customer causes over, say, a month, thus enforcing cost
   fairness.  Although Gibbens & Kelly rightly identified that standard
   ECN reveals the necessary information for cost-based fairness, it



Briscoe                  Expires April 18, 2007                [Page 17]


Internet-Draft  Flow Rate Fairness:Dismantling a Religion   October 2006


   doesn't reveal it in the right place for network layer policing---
   where the _sender_ attaches to the network.  In the current TCP/IP
   architecture, congestion information emerges from the end of a
   forward data path, which is the last point in the feedback loop that
   a network operator can reliably intercept it---the wrong end for
   policing the sender.

   Re-ECN is based on a pattern of feedback called re-feedback [Re-fb],
   which overloads the standard structure of congestion signalling in IP
   datagrams, by forcing the sender to honestly declare path congestion
   in packets it sends on the forward data path (hoping to use the last
   undefined bit of the IPv4 header).  Then it is possible to enforce
   cost fairness in a per-user policer.  Of course, the policer would
   act as a deterrent, encouraging the end-user to use a weight-based
   congestion control such as MulTCP [MulTCP], as already described.

   Re-ECN congestion information aggregates naturally, giving downstream
   networks the necessary bulk information to enforce cost-based
   fairness at their borders with their neighbouring upstream networks.
   Whether a network asserts cost-based fairness or some other fairness
   policy between its own upstream users is its own choice---indeed it
   can choose not to intervene at all.  But the re-ECN information it
   has to forward through its border router allows its downstream
   neighbour to penalise the whole upstream network for the costs it has
   allowed its users to cause to downstream users.  This enables a
   variety of fairness policies to co-exist (including absence of
   policy, which ensures incremental deployment).  But each network has
   an incentive to limit the costs that its users cause to others on the
   Internet.  So, on the grander scale, networks have to be fair to each
   other, which is the subject of the next section.


6.  Fairness between Fairnesses

   A social anthropologist would be able to give numerous examples of
   tribes and societies holding differing opinions on fairness.  But,
   just as gravity pre-dated Newton, the invisible hand of the
   (maturing) market had been allocating resources in society long
   before Adam Smith noticed, particularly where the larger picture of
   trade between societies was concerned.  However, monarchs,
   governments, charities and so on have also been stamping their own
   view of fairness on this backdrop, sometimes less equal sometimes
   more.

   But, we must also recognise that society's view of fairness is
   heavily influenced by the fairness that a market would
   produce [SovJstce].  In terms of alpha-fairness [aFair], flow rate
   equality (alpha=infinity) is defined as extremely fair.  But in life



Briscoe                  Expires April 18, 2007                [Page 18]


Internet-Draft  Flow Rate Fairness:Dismantling a Religion   October 2006


   few expect to get an equal share of the cake for nothing.  As a
   society, we accept that a reasonably competitive market mechanism
   does produce a `realistic' form of fairness; a form of fairness that
   people grudgingly accept they have to live with, where the buyer gets
   no more than she pays for, at a competitive price that reflects the
   effort expended by the seller.

   Even if different allocation schemes are chosen locally, perhaps
   taking account of social inequality, on a global scale arbitration
   between local views on fairness is largely through market
   economics---we are not asking anyone to judge whether this is good or
   bad, it just is.  This doesn't imply we believe that economic forces
   are somehow above policy control.  Rather, we observe that market
   forces (aside from wars) have been the default _global_ resource
   allocation mechanism over many centuries.  In the Greco-Roman
   civilisations, in the Buddhist and Confucian worlds, and later in the
   Islamic world, trade was a necessary, but not the primary, aspect of
   life.  Over the last two decades, Western civilisations have been
   going through a phase of `economics imperialism', where attempting to
   exert policy control over economics has been viewed as counter-
   productive.  However, we must not assume the current globalisation
   trend [Saul05] heralds the end of history.

   The Internet should be able to reflect this pattern as societal
   forces shift and different local fairness regimes come and go---
   `design for tussle' [Tussle].  On the whole, interworking between
   most parts of the Internet must _be able_ to be based on market
   economics, while other fairness criteria can be applied locally.  For
   instance, a University might choose to allocate resources to each
   student equally rather than by how much their parents can afford.
   But the resources one whole University gets relative to another
   institution depend on how much each pays their service provider.
   Whole countries might arrange to subsidise a minimum universal
   service obligation for Internet _usage_, but still, the country as a
   whole would be expected to pay its way in the world.  On the other
   hand, in market-led countries, commercial ISPs might solely allocate
   resources proportionate to customer subscriptions.  Local pockets of
   heterogeneity will exist, from computer clubs to NATO, but the
   overall fabric of resource allocation that glues all these pockets
   together at the (inter)network layer is likely to be based on market
   economics.

   This is what we mean by `realistic'---fitting the commercial reality
   of a global market economy.  We are fully aware that the power of
   market economics can be stretched too far; controlling aspects of
   society where economic assumptions break down (prompting Samuelson to
   describe Friedman as "...somebody who had learned how to spell banana
   but didn't know where to stop" [Swed90]).  But we are not advocating



Briscoe                  Expires April 18, 2007                [Page 19]


Internet-Draft  Flow Rate Fairness:Dismantling a Religion   October 2006


   that one religion should replace another---market economics replacing
   flow rate fairness.  However, in the case of Internet resource
   allocation, it must at least _be possible_ to use market economics,
   despite its known failings, given it is currently the most
   appropriate tool for managing the large-scale interactions.

   A market is meant to optimise allocations in the face of conflicts of
   self-interest.  If we want to assert other fairness regimes, we must
   recognise this acts against how a market would work.  If we don't
   understand how to overcome self-interest, its invisible hand will
   force its will on us some other way, distorting our attempts to work
   against it.  This is why the loop holes in flow rate fairness are
   being so thoroughly exploited.

   And this is our point.  A market _mechanism_ has to be _designed_.  A
   weak design will be exploited mercilessly.  The designs behind flow
   rate fairness are worse than weak.  They are not even aware that, as
   resource allocation mechanisms, they _should_ be able to meet the
   stringent requirements of a good market mechanism, such as forgery-
   resistant `currency', information symmetry, internalisation of
   externalities and so forth.

   If we did wish to promote the cause of equality, equalising flow
   rates would in no way achieve our ends.  In fact, it would only
   promote the cause of selfishness and malice, because flows don't
   equate to people, so its broken logic can be thoroughly exploited.
   Only by providing a bullet-proof mechanism for the market to express
   itself, can we then move on to allocate resources locally in other
   ways.


7.  The Seminal Literature

   For a rigourous tutorial on the various form of fairness, the reader
   is referred to Le Boudec [ccFairTut].

   Max-min flow rate fairness has a long history in networking, with
   research to find distributed (router-based) max-min algorithms
   starting in 1980 [DeMaxMin] and Nagle proposing a novel approach in
   1985 [RFC0970].  All these early `fair queuing' algorithms gave equal
   rights to each source.  In 1989, to solve the problem of some sources
   deserving more rate than others, the authors of `weighted fair
   queuing' (WFQ) proposed that per-source destination pair would be a
   better model of the size of different sources.  It was admitted that
   a source could deny service to other sources by faking transfers with
   numerous destinations, but a reasonable tradeoff between efficiency
   and security was required [WFQ].  Recently, an approach called
   Justice [Jstce] has proposed a return to (weighted) per source fair



Briscoe                  Expires April 18, 2007                [Page 20]


Internet-Draft  Flow Rate Fairness:Dismantling a Religion   October 2006


   queuing, but with configurable link weights throughout the network.
   However, all these `fair queuing' approaches allocate bit rate as
   their measure of fairness.

   TCP congestion control was also introduced in the late 1980s [TCPcc],
   based on the assumption that it would be fair if flow rates through a
   single bottleneck converged on equality.

   In 1991, Mazumdar _et al_ [UtilFair] pointed out that there was
   nothing special about max-min fair rate allocation, and that other
   _ad hoc_ definitions of fairness perhaps based on ratios of
   individual demands would be no less valid.  Instead Mazumdar _et al_
   advocated that it would be precise to base a definition of fairness
   on game theory, specifically the Nash bargaining solution.  This
   resulted in proportional fairness, but still using the rate allocated
   to flows as the measure of fairness.

   In 1997, Kelly considered that Mazumdar's use of co-operative game
   theory was unlikely to be relevant to public networks where fairness
   would have to be enforced.  Instead he introduced _weighted_
   proportional fairness [wPropFair], which finally broke the link
   between fairness and flow rates.  However, the break in tradition
   wasn't obvious because the new form of fairness could easily be
   expressed in terms of flow rates, essentially using the weight of a
   flow as a `fiddle-factor'.

   Kelly showed that all a network had to do to achieve fairness in its
   economic sense (cost fairness) was to share the cost of congestion
   among bits (not flows).  Then, as long as the network made users
   experience the cost of their bits, users could choose any size flows
   they wished.  But their choice would be regulated by their own trade
   off between how much they valued bit rate and the charge for
   congestion.

   Kelly's fairness with respect to bit rate per unit charge could also
   be (and was) framed in terms of fairness between flows by allowing
   the user an arbitrary choice of weight per flow.  But Kelly pointed
   out that a flow could be divided into sub-flows without changing the
   overall rate allocation to all the sub-flows taken together; the user
   merely had to imagine that the weight she assigned to one flow could
   be subdivided proportionately into its sub-flows.

   Kelly's work built on MacKie-Mason & Varian's seminal paper on the
   economics of networks from 1995, "Pricing Congestible Network
   Resources" [PrCong].  This work explained the dual role of congestion
   costs in controlling demand and regulating supply, in welfare
   maximising, competitive and monopoly markets.




Briscoe                  Expires April 18, 2007                [Page 21]


Internet-Draft  Flow Rate Fairness:Dismantling a Religion   October 2006


   In his 1997 paper, Kelly framed cost fairness in terms of weighted
   proportional fairness of flow rates in order to relate to an ATM
   technology context.  With ATM's flow-based user-network interface,
   users had to declare the weight they chose for their flows to the
   network.  But by 1998 Kelly _et al_ applied this work [wPropStab] to
   an Internet setting where flows were not part of the user's interface
   with the network, so flow weights could become a purely private
   device, internal to the user's rate control algorithm.  Nonetheless,
   the _outcome_ at the flow level was still weighted proportional
   fairness, and the underlying fairness that produced this outcome was
   still based solely on sharing the cost of congestion among bits.

   Back in 1995, Shenker had identified two main types of network
   traffic: elastic and inelastic, distinguished respectively by their
   concave and sigmoid utility functions [FundUtil].  Whatever the
   utility function, Kelly teaches us that covering congestion costs is
   sufficient to achieve fairness.  But then the outcome (in terms of
   flow rates) depends on the type of utility function:

   o  Weighted proportionally fair flow rates will be the outcome for
      elastic traffic streaming;

   o  Inelastic traffic flows hit a discontinuity once congestion rises
      beyond a certain level, at which point each is better off with
      zero rate, leading to a need for some form of admission control,
      whether self-admission control or arbitrated by the
      network [DCAC].

   o  Key & Massoulie identified a third major class of network traffic
      where utility is derived solely from the duration required to
      complete transfer of a fixed volume of data [UtilFile].  They
      showed that, if cost fairness applied, self-interested congestion
      control would toggle between full line rate and zero (with
      occasional probes).  Such behaviour alone destabilises the
      network, but it can be stabilised by mixing with streaming
      traffic [FairIntgr].  Research on the second order incentives
      necessary to encourage stability continues.

   Since these seminal papers in the late 1990s, theoretical refinement
   has continued, but the main thrust of research has been to find more
   realistic and practical ways of applying the insights, a process
   which is now bearing fruit (see Section 5.2.2).


8.  IANA Considerations

   This memo includes no request to IANA.




Briscoe                  Expires April 18, 2007                [Page 22]


Internet-Draft  Flow Rate Fairness:Dismantling a Religion   October 2006


9.  Security Considerations

   The whole of Section 5.2 discusses how there are no known ways of
   enforcing flow rate fairness securely in a non-co-operative
   environment like the current Internet, whereas practical, secure
   solutions have been proposed for enforcing cost-fairness.


10.  Concluding Remarks

10.1.  A Cautionary Note

   In 1997, Kelly showed [wPropFair] that, assuming everyone covered
   their costs, max-min flow rate fairness could be contrived by
   supposing users all valued bit rate with an unrealistically extreme
   set of utility functions that were all identical and that all valued
   low bit rate infinitesimally less than high bit rate.  But, despite
   this damning evidence, we have continued to see schemes with routers
   doing max-min fair rate allocation.

   To spell Kelly's result out even more bluntly, max-min fair rate
   allocation satisfies the policy goal, "To all equally without regard
   to their wants or needs, from all [others] without regard to cost."
   Such a view might be the motto of the revolutionary monster raving
   wacko party, but it should have no place in large-scale networking.
   Knowing this, what reason would anyone have to take max-min flow rate
   fairness seriously, ever again?

   Further, once the idea of fairness based on integrating costs over
   time is understood, what reason would anyone have to take any form of
   instantaneous per-flow rate fairness (whether max-min or TCP)
   seriously, ever again?

   Even if a system is being designed somehow isolated from the economy,
   where costs will never have to relate to real economic costs, what
   possible reason could there be for adopting these forms of fairness
   that so badly relate to real life fairness?

10.2.  Conclusions

   In much of the networking community you have to put fairness in terms
   of flow rates, otherwise your work is `obviously' irrelevant.  At
   minimum, you are an outcast, if not a heretic.  But actually it is
   flow rate fairness itself that has no basis in philosophy or science,
   let alone `commercial reality'.  It is a classic case of a hegemony
   where those living within the box don't recognise the existence of
   the box, let alone that there is a world outside the box.




Briscoe                  Expires April 18, 2007                [Page 23]


Internet-Draft  Flow Rate Fairness:Dismantling a Religion   October 2006


   Outside the box, cost fairness was derived from economic concepts of
   fairness back in 1997.  When flow rate fairness is seen through the
   wider eyes of this economic analysis it is clearly broken, even on
   its own terms.  The criticism is far more damning than merely whether
   allocations are fair.  Both the thing being allocated (rate) and what
   it is allocated among (flows) are completely daft---both unrealistic
   and impractical.  However, the Internet community continues to judge
   fairness using flow rates, apparently unaware that this approach has
   been shown to have no intellectual basis.

   And to be clear, this accusation applies to the so-called `fairness'
   that emerges from the TCP algorithm and the various fair queuing
   algorithms used in production networks.  In fact, these flow rate
   fairness algorithms are myopic in both space and time---they are
   completely unable to control fairness at all, because they don't
   adjust depending on how many flows users create and for how long.

   In real life, fairness generally concerns costs or benefits.  Flow
   rate doesn't come anywhere near being a good model of either.  User
   benefit per bit rate might be ten orders of magnitude different for
   different types of flow.  And cost depends on the product of bit rate
   with congestion, which is very variable and nothing like bit rate
   alone.

   But even worse, there is no evidence whatsoever that fairness between
   flows relates in any way to fairness between any real-world entities
   that one would expect to treat fairly, such as people or
   organisations.  If fairness is defined between flows, users can just
   create more flows to get a larger allocation.  Worse still, fairness
   between flows is only defined instantaneously, which bears no
   relation to real-world fairness over time.  In contrast, cost
   fairness has realistic answers to all these questions.

   Further, cost fairness is practical to enforce, unlike flow rate
   fairness, which seems inherently broken in this respect.  We believe
   cost fairness is a coherent way forward with all the technical
   barriers overcome, or close to being overcome.

   The only outstanding barrier is a religious one.  This memo has been
   written from frustration that no-one in the box believes that the
   voices that seem to be coming from outside the box should be listened
   to.  It seemed the only way forward was to force the issue, by making
   the box look ridiculous in its own terms.  The applied networking
   community must justify its preposterous position on fairness with
   reference to some previously respected notions in philosophy or
   social science.  In this memo, we have shown how the whole house of
   cards is unlikely to be up to such rigour.




Briscoe                  Expires April 18, 2007                [Page 24]


Internet-Draft  Flow Rate Fairness:Dismantling a Religion   October 2006


10.3.  Further Work

   This memo has focused on the fairness ideas we see in the production
   networks around us today.  However, our real concern is that these
   broken ideas also pervade the community working on replacing the
   Internet architecture.  It is well-known that TCP congestion control
   is running out of dynamic range and many proposals for hi-speed
   replacements have been put forward.  But these replacements must also
   simultaneously meet the much harder requirement of encompassing a
   range of realistic fairness criteria, as outlined in Section 6.

   XCP is a router-based hi-speed congestion control mechanism that
   claims to allow different fairness criteria to be configured.
   However, XCP fairness is based on the myopic flow-rate-based view
   that we have so roundly criticised in this memo.  For instance, XCP
   claims to be able to achieve a weighted proportional fair rate
   allocation ([XCP] S.6), but it glosses over how it regulates each
   user's choice of the weight---there is no direct congestion
   information in the XCP protocol that could be used to make each user
   accountable for their choice.  Further research is needed to
   establish whether a combination of XCP's protocol fields could yield
   this information, and if so, whether such an approach would be immune
   to cheating.

   We also believe it will be necessary to be able to apply different
   fairness criteria to different subsets of users of a network, and
   subsets across an internetwork.  We cannot immediately see how this
   would be feasible with router-based approaches like XCP, but it would
   be straightforward with end-to-end approaches like
   re-feedback [Re-fb].  Therefore we plan to focus on achieving hi-
   speed congestion control in an edge-policed end-to-end control
   architecture.


11.  Acknowledgements

   Thanks are due to Scott Shenker for persuading me to write this,
   Louise Burness for insight into why people think the way they do, Ben
   Strulo for giving a better way of expressing it and Marc Wennink for
   challenging the ideas.  Also thanks to Arnaud Jacquet, Jon Crowcroft,
   Frank Kelly and Peter Key for their useful reviews.  However, the
   author alone shoulders the blame for any offence caused by the
   bluntness of style.


12.  Comments Solicited

   Comments and questions are encouraged and very welcome.  They can be



Briscoe                  Expires April 18, 2007                [Page 25]


Internet-Draft  Flow Rate Fairness:Dismantling a Religion   October 2006


   addressed to the IETF Transport Area mailing list
   <tsv-area@ietf.org>, and/or to the authors.


13.  References

13.1.  Normative References

   [RFC2119]  Bradner, S., "Key words for use in RFCs to Indicate
              Requirement Levels", BCP 14, RFC 2119, March 1997.

   [RFC2309]  Braden, B., Clark, D., Crowcroft, J., Davie, B., Deering,
              S., Estrin, D., Floyd, S., Jacobson, V., Minshall, G.,
              Partridge, C., Peterson, L., Ramakrishnan, K., Shenker,
              S., Wroclawski, J., and L. Zhang, "Recommendations on
              Queue Management and Congestion Avoidance in the
              Internet", RFC 2309, April 1998.

   [RFC3168]  Ramakrishnan, K., Floyd, S., and D. Black, "The Addition
              of Explicit Congestion Notification (ECN) to IP",
              RFC 3168, September 2001.

   [Re-TCP]   Briscoe, B., Jacquet, A., Salvatori, A., and M. Koyabi,
              "Re-ECN: Adding Accountability for Causing Congestion to
              TCP/IP", draft-briscoe-tsvwg-re-ecn-tcp-02 (work in
              progress), June 2006.

13.2.  Informative References

   [AFD]      Pan, R., Breslau, L., Prabhaker, B., and S. Shenker,
              "Approximate Fairness Through Differential Dropping",
              CCR 33(2)23--40, April 2003.

   [ArchP2pEcon]
              Strulo, B., Smith, A., and J. Farr, "An Architecture for
              Peer-to-Peer Economies", Proc. 3rd Int'l Conf. On Peer-to-
              Peer Computing (P2P 2003) pp208--209, 2003, <http://
              csdl.computer.org/comp/proceedings/p2p/2003/2023/00/
              20230208.pdf>.

   [BufSizUp]
              Ganjali, Y. and N. McKeown, "Update on Buffer Sizing in
              Internet Routers", ACM SIGCOMM CCR 36, October 2006,
              <http://www.sigcomm.org/ccr/drupal/?q=node/72>.

   [CheapPseud]
              Friedman, E. and P. Resnick, "The Social Cost of Cheap
              Pseudonyms", Journal of Economics and Management



Briscoe                  Expires April 18, 2007                [Page 26]


Internet-Draft  Flow Rate Fairness:Dismantling a Religion   October 2006


              Strategy 10(2)173--199, 1998.

   [DCAC]     Gibbens, R. and F. Kelly, "Distributed connection
              acceptance control for a connectionless network", Proc.
              International Teletraffic Congress (ITC16) pp941--952,
              1999, <http://www.statslab.cam.ac.uk/~frank/dcac.html>.

   [DeMaxMin]
              Jaffe, J., "A Decentralized, "Optimal", Multiple-User,
              Flow Control Algorithm", Proc. Fifth Int'l. Conf. On
              Computer Communications pp839--844, October 1980.

   [Evol_cc]  Gibbens, R. and F. Kelly, "Resource pricing and the
              evolution of congestion control", Automatica 35(12)1969--
              1985, December 1999,
              <http://www.statslab.cam.ac.uk/~frank/evol.html>.

   [FairFAQ]  Briscoe, B., "Cost Fairness FAQ", Web page , October 2006,
              <http://www.cs.ucl.ac.uk/staff/B.Briscoe/projects/
              2020comms/fairfaq.html>.

   [FairIntgr]
              Key, P., Massoulie, L., Bain, A., and F. Kelly, "Fair
              Internet traffic integration: network flow models and
              analysis", Annales des Telecommunications 59 pp1338--1352,
              2004, <http://citeseer.ist.psu.edu/641158.html>.

   [FrRideP2p]
              Feldman, M., Papadimitriou, C., Chuang, J., and I. Stoica,
              "FreeRiding and Whitewashing in Peer-to-Peer Systems",
              Proc. Workshop on Practice and Theory of Incentives in
              Networked Systems (PINS'04) pp228--236, 2004,
              <http://doi.acm.org/10.1145/1016527.1016539>.

   [FundUtil]
              Shenker, S., "Fundamental Design Issues for the Future
              Internet", IEEE Journal on Selected Areas in
              Communications 13(7)1176--1188, 1995,
              <http://citeseer.ist.psu.edu/shenker95fundamental.html>.

   [Jstce]    Eriksson, J., Faloutsos, M., and S. Krishnamurthy,
              "Justice: Flexible and Enforceable Per-Source Bandwidth
              Allocation", Proc. Networking pp1206--1218, 2005,
              <http://www.cs.ucr.edu/~krish/jakob_networking05.pdf>.

   [MulTCP]   Crowcroft, J. and Ph. Oechslin, "Differentiated End to End
              Internet Services using a Weighted Proportional Fair
              Sharing TCP", CCR 28(3) 53--69, July 1998, <http://



Briscoe                  Expires April 18, 2007                [Page 27]


Internet-Draft  Flow Rate Fairness:Dismantling a Religion   October 2006


              www.cs.ucl.ac.uk/staff/J.Crowcroft/hipparch/pricing.html>.

   [NewArchReq]
              Braden, R., Clark, D., Shenker, S., and J. Wroclawski,
              "Developing a Next-Generation Internet Architecture",
              DARPA white paper , July 2000,
              <http://www.isi.edu/newarch/DOCUMENTS/WhitePaper.pdf>.

   [PMP]      Odlyzko, A., "A modest proposal for preventing Internet
              congestion", AT&T technical report TR 97.35.1,
              September 1997,
              <http://www.dtc.umn.edu/~odlyzko/doc/modest.proposal.pdf>.

   [PrCong]   MacKie-Mason, J. and H. Varian, "Pricing Congestible
              Network Resources", IEEE Journal on Selected Areas in
              Communications, `Advances in the Fundamentals of
              Networking' 13(7)1141--1149, 1995, <http://
              www.sims.berkeley.edu/~hal/Papers/
              pricing-congestible.pdf>.

   [RFC0970]  Nagle, J., "On packet switches with infinite storage",
              RFC 970, December 1985.

   [RFC2581]  Allman, M., Paxson, V., and W. Stevens, "TCP Congestion
              Control", RFC 2581, April 1999.

   [RFC3448]  Handley, M., Floyd, S., Padhye, J., and J. Widmer, "TCP
              Friendly Rate Control (TFRC): Protocol Specification",
              RFC 3448, January 2003.

   [RFC4342]  Floyd, S., Kohler, E., and J. Padhye, "Profile for
              Datagram Congestion Control Protocol (DCCP) Congestion
              Control ID 3: TCP-Friendly Rate Control (TFRC)", RFC 4342,
              March 2006.

   [Re-fb]    Briscoe, B., Jacquet, A., Di Cairano-Gilfedder, C.,
              Salvatori, A., Soppera, A., and M. Koyabe, "Policing
              Congestion Response in an Internetwork Using Re-Feedback",
              ACM SIGCOMM CCR 35(4)277--288, August 2005, <http://
              www.acm.org/sigs/sigcomm/sigcomm2005/
              techprog.html#session8>.

   [Saul05]   Saul, J., "The Collapse of Globalism and the Reinvention
              of the World", Pub: Viking, Canada ISBN: 0-670-06367-3,
              2005.

   [SelfMan]  Kelly, F., "Models for a Self-Managed Internet",
              Philosophical Transactions of the Royal



Briscoe                  Expires April 18, 2007                [Page 28]


Internet-Draft  Flow Rate Fairness:Dismantling a Religion   October 2006


              Society 358(1773)2335--2348, August 2000,
              <http://www.statslab.cam.ac.uk/~frank/smi.html>.

   [SovJstce]
              Siderenko, S., "Characteristics of Perceptions of Social
              Justice in the Contemporary USSR", Chapter in:
              Transitional Agendas: Working Papers from the Summer
              School for Soviet Sociologists Ch3 pp41--45, 1991,
              <http://lucy.ukc.ac.uk/csacpub/russian/siderenko.html>.

   [Swed90]   Swedberg, R., "Economics and Sociology. Redefining their
              Boundaries: Conversations with Economists and
              Sociologists", Pub: Princeton University Press , 1990.

   [TCPcc]    Jacobson, V., "Congestion Avoidance and Control", Proc.
              ACM SIGCOMM'88 Symposium, Computer Communication
              Review 18(4)314--329, August 1988,
              <ftp://ftp.ee.lbl.gov/papers/congavoid.ps.Z>.

   [Tussle]   Clark, D., Sollins, K., Wroclawski, J., and R. Braden,
              "Tussle in Cyberspace: Defining Tomorrow's Internet", ACM
              SIGCOMM CCR 32(4)347--356, October 2002,
              <http://www.acm.org/sigcomm/sigcomm2002/papers/
              tussle.pdf>.

   [UtilFair]
              Mazumdar, R., Mason, L., and C. Douligeris, "Fairness in
              Network Optimal Flow Control: Optimality of Product
              Forms", IEEE Transactions on Communications 39(5)775--782,
              May 1991, <http://dionysos.cs.unipi.gr/~cdoulig/
              Fairness%20in%20network%20optimal%20flow%20control%
              20optimality%20of%20product%20forms.pdf>.

   [UtilFile]
              Key, P. and L. Massoulie, "User policies in a network
              implementing congestion pricing", Proc. Workshop on
              Internet Service Quality and Economics , December 1999,
              <http://www.marengoresearch.com/isqe/index.htm>.

   [WFQ]      Demers, A., Keshav, S., and S. Shenker, "Analysis and
              Simulation of a Fair-Queueing Algorithm", ACM SIGCOMM
              CCR 19(4)1--12, September 1989,
              <http://portal.acm.org/citation.cfm?id=75248>.

   [XCHOKe]   Chhabra, P., Chuig, S., Goel, A., John, A., Kumar, A.,
              Saran, H., and R. Shorey, "XCHOKe: Malicious Source
              Control for Congestion Avoidance at Internet Gateways",
              Proceedings of IEEE International Conference on Network



Briscoe                  Expires April 18, 2007                [Page 29]


Internet-Draft  Flow Rate Fairness:Dismantling a Religion   October 2006


              Protocols (ICNP-02) , November 2002,
              <http://www.cc.gatech.edu/~akumar/xchoke.pdf>.

   [XCP]      Katabi, D., Handley, M., and C. Rohrs, "Congestion Control
              for High Bandwidth-Delay Product Networks", ACM SIGCOMM
              CCR 32(4)89--102, October 2002,
              <http://www.ana.lcs.mit.edu/dina/XCP/>.

   [aFair]    Tang, A., Wang, J., and S. Low, "Is Fair Allocation Always
              Inefficient", Proc. IEEE Conference on Computer
              Communications (Infocom'04) , March 2004, <http://
              netlab.caltech.edu/pub/papers/fairness-infocom2004.pdf>.

   [ccFairTut]
              Le Boudec, J-Y., "Rate Adaptation, Congestion Control and
              Fairness: A Tutorial", Web page , November 2005,
              <http://ica1www.epfl.ch/PS_files/LEB3132.pdf>.

   [pBox]     Floyd, S. and K. Fall, "Promoting the Use of End-to-End
              Congestion Control in the Internet", IEEE/ACM Transactions
              on Networking 7(4) 458--472, August 1999,
              <http://www.aciri.org/floyd/end2end-paper.html>.

   [wPropFair]
              Kelly, F., "Charging and Rate Control for Elastic
              Traffic", European Transactions on Telecommunications 8
              pp33--37, 1997,
              <http://www.statslab.cam.ac.uk/~frank/elastic.html>.

   [wPropStab]
              Kelly, F., Maulloo, A., and D. Tan, "Rate control for
              communication networks: shadow prices, proportional
              fairness and stability", Journal of the Operational
              Research Society 49(3) 237--252, 1998,
              <http://www.statslab.cam.ac.uk/~frank/rate.html>.
















Briscoe                  Expires April 18, 2007                [Page 30]


Internet-Draft  Flow Rate Fairness:Dismantling a Religion   October 2006


Author's Address

   Bob Briscoe
   BT & UCL
   B54/77, Adastral Park
   Martlesham Heath
   Ipswich  IP5 3RE
   UK

   Phone: +44 1473 645196
   Email: bob.briscoe@bt.com
   URI:   http://www.cs.ucl.ac.uk/staff/B.Briscoe/







































Briscoe                  Expires April 18, 2007                [Page 31]


Internet-Draft  Flow Rate Fairness:Dismantling a Religion   October 2006


Intellectual Property Statement

   The IETF takes no position regarding the validity or scope of any
   Intellectual Property Rights or other rights that might be claimed to
   pertain to the implementation or use of the technology described in
   this document or the extent to which any license under such rights
   might or might not be available; nor does it represent that it has
   made any independent effort to identify any such rights.  Information
   on the procedures with respect to rights in RFC documents can be
   found in BCP 78 and BCP 79.

   Copies of IPR disclosures made to the IETF Secretariat and any
   assurances of licenses to be made available, or the result of an
   attempt made to obtain a general license or permission for the use of
   such proprietary rights by implementers or users of this
   specification can be obtained from the IETF on-line IPR repository at
   http://www.ietf.org/ipr.

   The IETF invites any interested party to bring to its attention any
   copyrights, patents or patent applications, or other proprietary
   rights that may cover technology that may be required to implement
   this standard.  Please address the information to the IETF at
   ietf-ipr@ietf.org.


Disclaimer of Validity

   This document and the information contained herein are provided on an
   "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS
   OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET
   ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED,
   INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE
   INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED
   WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.


Copyright Statement

   Copyright (C) The Internet Society (2006).  This document is subject
   to the rights, licenses and restrictions contained in BCP 78, and
   except as set forth therein, the authors retain all their rights.


Acknowledgment

   Funding for the RFC Editor function is currently provided by the
   Internet Society.




Briscoe                  Expires April 18, 2007                [Page 32]