Efficient fair queueing using deficit round robin

ABSTRACT

Fair queuing is a technique that allows each flow passing through a network device to have a fair share of network resources. Previous schemes for fair queuing that achieved nearly perfect fairness were expensive to implement: specifically, the work required to process a packet in these schemes was O(log(n)), where n is the number of active flows. This is expensive at high speeds. On the other hand, cheaper approximations of fair queuing that have been reported in the literature exhibit unfair behavior. In this paper, we describe a new approximation of fair queuing, that we call Deficit Round Robin. Our scheme achieves nearly perfect fairness in terms of throughput, requires only O(1) work to process a packet, and is simple enough to implement in hardware. Deficit Round Robin is also applicable to other scheduling problems where servicing cannot be broken up into smaller units, and to distributed queues.

REFERENCES

• APV95: H. Adiseshu, G. Parulkar, and G. Varghese. Reliable FIFO Load Balancing over Multiple FIFO Channels. Washington University Technical Report 95-11, available by FTP.
• CLR90: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• DKS89: A. Demers , S. Keshav , S. Shenker, Analysis and simulation of a fair queueing algorithm, ACM SIGCOMM Computer Communication Review, v.19 n.4, p.1-12, Sep. 1989
• Flo93a: S. Floyd. Notes on guaranteed service in resource management. Unpublished note. 1993.
• Flo93b: S. Floyd. Personal communication. 1993.
• GM90: A. Greenberg and N. Madras. How fair is fair queueing. In Proc. Performance '90, 1990.
• Gol94: S. Goiestani. A self clocked fair queueing scheme for broadband applications. In Proc. {EEE Infocomm '9d, 1994.
• JR86: R. Jain and S. Routhier. Packet trains measurement and a new model for computer netwoek traffic. IEEE Journal on Selected Areas ~n Communications, Sept. 1986.
• Kes91: S. Keshav. On the efficient implementation of fair queueing. In Internetworking: Research and Experzence Vol. 2, 15%173, September 1991.
• McK91: P. McKenney. Stochastic fairness queueing. In Internetworking: Research and Experience Vol.2, 113-131, January 1991.
• Nag87: John Nagle. On packet switches with infinite storage. IEEE Trans. on Comm., COM-35(4), April 1987.
• PG93: Abhay K. Parekh , Robert G. Gallager, A generalized processor sharing approach to flow control in integrated services networks—the single node case, Proceedings of the eleventh annual joint conference of the IEEE computer and communications societies on One world through communications (Vol. 2), p.915-924, May 1992, Florence, Italy
• SA94: D. Saha and M. Saksena and S. Mukherjee and S. Tripathi. On Guaranteed Delivery of Time- Critical Messages in DQDB. In Proc. IEEE Infocomm '9d.
• ST85: Daniel D. Sleator , Robert E. Tarjan, Amortized efficiency of list update and paging rules, Communications of the ACM, v.28 n.2, p.202-208, Feb. 1985 [doi>10.1145/2786.2793]
• Zha91: Lixia Zhang, VirtualClock: a new traffic control algorithm for packet-switched networks, ACM Transactions on Computer Systems (TOCS), v.9 n.2, p.101-124, May 1991 [doi>10.1145/103720.103721]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Packet-switching networks

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Scheduling
      D.4.8 Performance
          Subjects: Queueing theory

General Terms:
Algorithms, Performance