Fair Bandwidth Allocation Without Per-Flow State

  • Richard M. Karp
Part of the Lecture Notes in Computer Science book series (LNCS, volume 3895)


A fundamental goal of Internet congestion control is to allocate limited bandwidth fairly to competing flows. Such flow control involves an interplay between the behavior of routers and the behavior of end hosts. Routers must decide which packets to drop when their output links become congested. End hosts must decide how to moderate their packet transmissions in response to feedback in the form of acknowledgements of packet delivery (acks). Typically this is done according to the TCP protocol, in which a host maintains a window (the number of packets that have been sent but not yet acknowledged) that is increased when an ack is received and decreased when a drop is detected.

Often the selection of packets to be dropped at a router depends on the order of their arrivals at the router but not on the flows to which the packets belong. An exception occurs when packets are stratified according to their quality of service guarantee; in this case packets at higher strata are given priority, but within a stratum the packets from different flows receive the same treatment. A number of methods have been proposed to ensure fairness by selectively dropping packets from flows that are receiving more than their fair share of bandwidth. The most effective known algorithms for detecting and selectively dropping high-rate flows at a router are based on random hashing or random sampling of packets and give only probabilistic guarantees. The known deterministic algorithms either require excessive storage, require packets to carry accurate estimates of the rates of their flows, assume some special properties of the stream of arriving packets, or fail to guarantee fairness. In a simplified theoretical setting we show that the detection and selective dropping of high-rate flows can be accomplished deterministically without any of these defects. This result belies the conventional wisdom that per-flow state is required to guarantee fairness.

Given an arriving stream of packets, each labeled with the name of its flow, our algorithm drops packets selectively upon arrival so as to guarantee that, in every consecutive subsequence of the stream of surviving packets, no flow has significantly more than its fair share of the packets. The main results of the paper are tight bounds on the worst-case storage requirement of this algorithm. The bounds demonstrate that the storage and computation required to guarantee fairness are easily within the capabilites of conventional routers.

It is important to acknowedge the limitations of this work. We have formulated the achievement of fairness at a router in terms of local information on the stream of arriving packets at that router. The implications of such a locally optimal policy on the global stability of the Internet would require analyzing the Internet as a complex dynamical system involving interactions among routers and end hosts, of which some will be TCP-compliant and some will not. In work not reported here we have made an initial simulation study of this complex process, but such a study is outside the scope of the present paper.


Storage Requirement Fair Share Output Sequence Output Link Generalize Trace 
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.


Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.


  1. 1.
    Estan, C., Varghese, G.: New directions in traffic measurement and accounting: Focusing on the elephants, ignoring the mice. ACM Transactions on Computer Systems 21(3), 270–313 (2003)CrossRefGoogle Scholar
  2. 2.
    Feng, W.-C., Kandlur, D.D., Saha, D., Shin, K.: Blue: A New Class of Active Queue Management Algorithms. Technical Report CSE-TR-387-99, University of Michigan (April 1999)Google Scholar
  3. 3.
    Ferguson, P., Huston, G.: Quality of Service: Delivering QoS on the Internet and in Corporate Networks. John Wiley and Sons, Chichester (1998)Google Scholar
  4. 4.
    Floyd, S., Fall, K.: Promoting the Use of End-to-End Congestion Control in the Internet. IEEE/ACM Transactions on Networking 7(4), 458–573 (1999)CrossRefGoogle Scholar
  5. 5.
    Floyd, S., Jacobson, V.: Random Early Detection Gateways for Congestion Avoidance. IEEE,ACM Transactions on Networking 1(4), 397–412 (1993)CrossRefGoogle Scholar
  6. 6.
    Mahajan, R., Floyd, S.: Controlling High-Bandwidth Flows at the Congested Router. Technical Report TR-01-001, International Computer Sciences InstituteGoogle Scholar
  7. 7.
    Mahajan, R., Floyd, S., Wetherall, D.: Controlling High-Bandwidth Flows at the Congested Router. In: ACM ICNP (November 2001)Google Scholar
  8. 8.
    Pan, R., Breslau, L., Prabhakar, B., Shenker, S.: Approximate Fairness through Differential Dropping. In: ACM Computer Communication Review (July 2003)Google Scholar
  9. 9.
    Pan, R., Prabhakar, B., Psounis, K.: A Stateless Active Queue Management Scheme for Approximate Fair Bandwidth Allocation. In: IEEE INFOCOM (March 2000)Google Scholar
  10. 10.
    Partridge, C.: Gigabit Networking. Addison-Wesley, Reading (1994)zbMATHGoogle Scholar
  11. 11.
    Shenker, S., Partridge, C., Guerin, R.: Specification of Guaranteed Quality of Service. IETF RFC 2212 (Septmeber 1997)Google Scholar
  12. 12.
    Stoica, I., Shenker, S., Zhang, H.: Core-Stateless Fair Queuing:Achieving Approximately Fair Bandwidth Allocations in High Speed Networks. In: ACM SIGCOMM (September 1998)Google Scholar
  13. 13.
    Tanenbaum, A.: Computer networks, 3rd edn. Prentice-Hall, Englewood Cliffs (1996)Google Scholar
  14. 14.
    Wrochalski, J.: Specification of Controlled-Load Network Element Service. IETF RFC 2211 (September 1997)Google Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2006

Authors and Affiliations

  • Richard M. Karp
    • 1
  1. 1.International Computer Science Institute and University of California at BerkeleyBerkeleyUSA

Personalised recommendations