Reduced state fair queuing for edge and core routers

ABSTRACT

Despite many years of research, fair queuing still faces a number of implementation challenges in high speed routers. In particular, in spite of proposals such as DiffServ, the state needs for even simple schedulers are still large for heavily channelized core routers and for edge routers. An earlier proposal, Stochastic Fair Queuing, reduces state but at the expense of added unfairness between certain flows. Another earlier scheme, Core Stateless Fair Queuing, requires header changes and does not address the state needs of edge routers. By contrast, our paper proposes a randomization technique that removes the need to store deficit counters per flow in Deficit Round Robin and its variants. Even without the counters, we show, using both analysis and simulation, that randomized technique preserves throughput fairness properties of DRR. This randomization technique introduced in this paper can be used to considerably reduce the state requirements of high speed schedulers in edge and core routers, making hardware designs feasible. The randomization idea in this paper can also be applied to other round robin schedulers as well as potentially in entirely different scenarios wherever deficits need to be tracked over time explicitly.

REFERENCES

• 1: A. Demers , S. Keshav , S. Shenker, Analysis and simulation of a fair queueing algorithm, Symposium proceedings on Communications architectures & protocols, p.1-12, September 25-27, 1989, Austin, Texas, United States
• 2: A. Parekh, A Generalized Processor Sharing Approach to Flow Control in Integrated Services Network", Ph.D. thesis, Masschusetts Institute of Technology, Feb. 1992.
• 3: 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]
• 4: Norival R. Figueira , Joseph Pasquale, An upper bound on delay for the VirtualClock service discipline, IEEE/ACM Transactions on Networking (TON), v.3 n.4, p.399-408, Aug. 1995 [doi>10.1109/90.413214]
• 5: Dimitrios Stiliadis , Anujan Varma, Rate-proportional servers: a design methodology for fair queueing algorithms, IEEE/ACM Transactions on Networking (TON), v.6 n.2, p.164-174, April 1998 [doi>10.1109/90.664265]
• 6: Dimitrios Stiliadis , Anujan Varma, Efficient fair queueing algorithms for packet-switched networks, IEEE/ACM Transactions on Networking (TON), v.6 n.2, p.175-185, April 1998 [doi>10.1109/90.664266]
• 7: Jon C. R. Bennett and Hui Zhang, "WF 2 q: Worst-case fair weighted fair queueing," in INFOCOM (1), 1996, pp. 120--128.
• 8: Pawan Goyal , Harrick M. Vin , Haichen Cheng, Start-time fair queueing: a scheduling algorithm for integrated services packet switching networks, IEEE/ACM Transactions on Networking (TON), v.5 n.5, p.690-704, Oct. 1997 [doi>10.1109/90.649569]
• 9: J. Nagle, "On packet siwtches with infinite storage," in IEEE Transactions on Communications, Apr. 1987, pp. 35(4):435--438.
• 10: M. Shreedhar , George Varghese, Efficient fair queueing using deficit round robin, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.231-242, August 28-September 01, 1995, Cambridge, Massachusetts, United States
• 11: Debanjan Saha , Sarit Mukherjee , Satish K. Tripathi, Carry-over round robin: a simple cell scheduling mechanism for ATM networks, IEEE/ACM Transactions on Networking (TON), v.6 n.6, p.779-796, Dec. 1998 [doi>10.1109/90.748089]
• 12: Cisco Systems, Inc., "GSR 1200 Router Series, http://www.cisco.com/warp/public/cc/pd/rt/12000/prodlit/gsrlc ov.htm.
• 13: Sriram Ramabhadran , Joseph Pasquale, Stratified round Robin: a low complexity packet scheduler with bandwidth fairness and bounded delay, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863983]
• 14: K. Thompson, G. Miller, and R. Wilder, "Wide-area traffic patterns and characterizations," in IEEE Network, December 1997.
• 15: S. Blake et.al, "An architecture for differentiated services," RFC 2475, Dec. 1998.
• 16: P. McKenney, "Stochastic fairness queuing," in IEEE INFOCOM, June 1990.
• 17: Ion Stoica , Scott Shenker , Hui Zhang, Core-stateless fair queueing: achieving approximately fair bandwidth allocations in high speed networks, Proceedings of the ACM SIGCOMM '98 conference on Applications, technologies, architectures, and protocols for computer communication, p.118-130, August 31-September 04, 1998, Vancouver, British Columbia, Canada
• 18: Salil Kanhere and Harish Sethu, "Low-latency guaranteed-rate scheduling using elastic round robin," in Computer Networks 25 (14), 2001, pp. 1315--1322.
• 19: Shih-Chiang Tsao , Ying-Dar Lin, Pre-order deficit round robin: a new scheduling algorithm for packet-switched networks, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.35 n.2-3, p.287-305, Feb. 2001 [doi>10.1016/S1389-1286(00)00172-9]
• 20: Salil S. Kanhere , Harish Sethu , Apha B. Parekh, Fair and Efficient Packet Scheduling Using Elastic Round Robin, IEEE Transactions on Parallel and Distributed Systems, v.13 n.3, p.324-336, March 2002 [doi>10.1109/71.993210]
• 21: Guo Chuanxiong, SRR: An O(1) time complexity packet scheduler for flows in multi-service packet networks, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.211-222, August 2001, San Diego, California, United States

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.6 Internetworking
          Subjects: Routers

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

General Terms:
Algorithms, Performance

Keywords:
fair queuing, quality of service, scheduling