Hierarchical packet fair queueing algorithms

ABSTRACT

Hierarchical Packet Fair Queueing (H-PFQ) algorithms have the potential to simultaneously support guaranteed real-time service, rate-adaptive best-effort, and controlled link-sharing service. In this paper, we design practical H-PFQ algorithms by using one-level Packet Fair Queueing (PFQ) servers as basic building blocks, and develop techniques to analyze delay and fairness properties of the resulted H-PFQ servers. We demonstrate that, in order to provide tight delay bounds in a H-PFQ server, it is essential for the one-level PFQ servers to have small Worst-case Fair Indices (WFI). We propose a new one-level PFQ algorithm called WF²Q+ that is the first to have all the following three properties: (a) providing the tightest delay bound among all PFQ algorithms; (b) having the smallest WFI among all PFQ algorithms; and (c) having a relatively low implementation complexity of O(log N). We show that practical H-PFQ algorithms can be implemented by using WF²Q+ as the basic building block and prove that the resulting H-WF²Q+ algorithms provide similar delay bounds and bandwidth distribution as those provided by a H-GPS server. Simulation experiments are presented to evaluate the proposed algorithm.

REFERENCES

• 1: J. Bennett and H. Zhang. Worst-case fair packet fair queueing algorithms. Technical report, 1996. Submitted for publication.
• 2: J.C.R. Bennett and H. Zhang. WFJQ: Worst-case fair weighted fair queueing. In Proceedings of IEEE IN- FOCOM'96, pages 120-128, San Francisco, CA, March 1996.
• 3: David D. Clark , Scott Shenker , Lixia Zhang, Supporting real-time applications in an Integrated Services Packet Network: architecture and mechanism, Conference proceedings on Communications architectures & protocols, p.14-26, August 17-20, 1992, Baltimore, Maryland, United States
• 4: R. Cruz. Service burstiness and dynamic burstiness measures: A framework. Journal of High Speed Networks, 1(2):105-127, 1992.
• 5: James R. Davin , Andrew T. Heybey, A simulation study of fair queueing and policy enforcement, ACM SIGCOMM Computer Communication Review, v.20 n.5, p.23-29, Oct 1 1990 [doi>10.1145/381906.381926]
• 6: 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
• 7: D. Ferrari and D. Verma. A scheme for real-time channel establishment in wide-area networks. IEEE Journal on Selected Areas in Communications, 8(3):368-379, April 1990.
• 8: Sally Floyd , Van Jacobson, Link-sharing and resource management models for packet networks, IEEE/ACM Transactions on Networking (TON), v.3 n.4, p.365-386, Aug. 1995 [doi>10.1109/90.413212]
• 9: S. Golestani. A self-clocked fair queueing scheme for broadband applications. In Proceedings of IEEE IN- FOCOM'9J, pages 636-646, Toronto, CA, June 1994.
• 10: Pawan Goyal , Simon S. Lam , Harrick M. Vin, Determining End-to-End Delay Bounds in Heterogeneous Networks, Proceedings of the 5th International Workshop on Network and Operating System Support for Digital Audio and Video, p.273-284, April 19-21, 1995
• 11: Srinivasan Keshav, A control-theoretic approach to flow control, Proceedings of the conference on Communications architecture & protocols, p.3-15, September 03-06, 1991, Zurich, Switzerland
• 12: P. McKenney. Stochastic fair queueing. In Proceedings of IEEE INFOCOM'90, San Francisco, CA, June 1990.
• 13: O. Ndiaye. An efficient implementation of a hierarchical weighted fair queue packet scheduler. Master's thesis, Massachusetts Institute of Technology, May 1994.
• 14: Abhay K. Parekh , Robert G. Gallager, A generalized processor sharing approach to flow control in integrated services networks: the single-node case, IEEE/ACM Transactions on Networking (TON), v.1 n.3, p.344-357, June 1993 [doi>10.1109/90.234856]
• 15: Scott Shenker, Making greed work in networks: a game-theoretic analysis of switch service disciplines, Proceedings of the conference on Communications architectures, protocols and applications, p.47-57, August 31-September 02, 1994, London, United Kingdom
• 16: S. Shenker, D. Clark, and L. Zhang. A scheduling service model and a scheduling architecture for an integrated services network, 1993. preprint.
• 17: 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
• 18: Dimitrios Stiliadis , Anujan Varma, FRAME-BASED FAIR QUEUEING: A NEW TRAFFIC SCHEDULING ALGORITHM FOR PACKET-SWITCHED NETWORKS, University of California at Santa Cruz, Santa Cruz, CA, 1995
• 19: J. Turner. New directions in communications(or which way to the information age?). IEEE Communication Magazine, 24(10), October 1986.
• 20: Hui Zhang , Srinivasan Keshav, Comparison of rate-based service disciplines, Proceedings of the conference on Communications architecture & protocols, p.113-121, September 03-06, 1991, Zurich, Switzerland

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:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees

General Terms:
Algorithms, Measurement, Performance, Theory, Verification