Pipelined heap (priority queue) management for advanced scheduling in high-speed networks

ABSTRACT

Per-flow queueing with sophisticated scheduling is one of the methods for providing advanced quality of service (QoS) guarantees. The hardest and most interesting scheduling algorithms rely on a common computational primitive, implemented via priority queues. To support such scheduling for a large number of flows at OC-192 (10 Gb/s) rates and beyond, pipelined management of the priority queue is needed. Large priority queues can be built using either calendar queues or heap data structures; heaps feature smaller silicon area than calendar queues. We present heap management algorithms that can be gracefully pipelined; they constitute modifications of the traditional ones. We discuss how to use pipelined heap managers in switches and routers and their cost-performance tradeoffs. The design can be configured to any heap size, and, using 2-port 4-wide SRAMs, it can support initiating a new operation on every clock cycle, except that an insert operation or one idle (bubble) cycle is needed between two successive delete operations. We present a pipelined heap manager implemented in synthesizable Verilog form, as a core integratable into ASICs, along with cost and performance analysis information. For a 16 K entry example in 0.13-µm CMOS technology, silicon area is below 10 mm² (less than 8% of a typical ASIC chip) and performance is a few hundred million operations per second. We have verified our design by simulating it against three heap models of varying abstraction.

REFERENCES

• 1: Jon C. R. Bennett , Hui Zhang, Hierarchical packet fair queueing algorithms, IEEE/ACM Transactions on Networking (TON), v.5 n.5, p.675-689, Oct. 1997 [doi>10.1109/90.649568]
• 2: [2] R. Bhagwan and B. Lin, "Fast and scalable priority queue architecture for high-speed network switches," in Proc. IEEE INFOCOM 2000, Tel Aviv, Israel, Mar. 2000, vol. 2, pp. 538-547 [Online]. Available: http:// www.ieee-infocom.org/2000/papers/565.ps.
• 3: R. Brown, Calendar queues: a fast 0(1) priority queue implementation for the simulation event set problem, Communications of the ACM, v.31 n.10, p.1220-1227, Oct. 1988 [doi>10.1145/63039.63045]
• 4: [4] H. J. Chao, "A novel architecture for queue management in the ATM network," IEEE J. Sel. Areas Commun., vol. 9, no. 7, pp. 1110-1118, Sep. 1991.
• 5: [5] H. J. Chao, H. Cheng, Y. Jeng, and D. Jeong, "Design of a generalized priority queue manager for ATM switches," IEEE J. Sel. Areas Commun., vol. 15, no. 5, pp. 867-880, Jun. 1997.
• 6: [6] H. J. Chao, Y. Jeng, X. Guo, and C. Lam, "Design of packet-fair queueing schedulers using a RAM-based searching engine," IEEE J. Sel. Areas Commun., vol. 17, no. 6, pp. 1105-1126, Jun. 1999.
• 7: [7] K. Harteros, "Fast parallel comparison circuits for scheduling," M.S. thesis, Dept. of Comput. Sci., Univ. of Crete, Crete, Greece, Mar. 2002, and Tech. Rep. FORTH-ICS/TR-304, Inst. of Comput. Sci., FORTH, Heraklio, Crete, Greece.
• 8: [8] A. D. Ioannou, "An ASIC core for pipelined heap management to support scheduling in high speed networks," M.S. thesis, Dept. of Computer Sci., Univ. of Crete, Crete, Greece, Nov. 2000, and Tech. Rep. FORTH-ICS/TR-278, Inst. of Comput. Sci., FORTH, Heraklio, Crete, Greece.
• 9: [9] A. Ioannou and M. Katevenis, "Pipelined heap (priority queue) management for advanced scheduling in high-speed networks," in Proc. IEEE Int. Conf. Communications (ICC'2001), Helsinki, Finland, Jun. 2001, pp. 2043-2047 [Online]. Available: http://archvlsi.ics.forth.gr/ muqpro/queueMgt.html.
• 10: Douglas W. Jones, An empirical comparison of priority-queue and event-set implementations, Communications of the ACM, v.29 n.4, p.300-311, April 1986 [doi>10.1145/5684.5686]
• 11: [11] M. Katevenis, "Fast switching and fair control of congested flow in broadband networks," IEEE J. Sel. Areas Commun., vol. 5, no. 8, pp. 1315-1326, Oct. 1987.
• 12: [12] M. Katevenis, S. Sidiropoulos, and C. Courcoubetis, "Weighted round-robin cell multiplexing in a general-purpose ATM switch chip," IEEE J. Sel. Areas Commun., vol. 9, no. 8, pp. 1265-1279, Oct. 1991.
• 13: [13] M. Katevenis, D. Serpanos, and E. Markatos, "Multi-queue management and scheduling for improved QoS in communication networks," in Proc. EMMSEC'97, Florence, Italy, Nov. 1997, pp. 906-913 [On-line]. Available: http://archvlsi.ics.forth.gr/html_papers/EMMSEC97/ paper.html.
• 14: S. Keshav, An engineering approach to computer networking: ATM networks, the Internet, and the telephone network, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 15: [15] A. Nikologiannis and M. Katevenis, "Efficient per-flow queueing in DRAM at OC-192 line rate using out-of-order execution techniques," in IEEE Int. Conf. Communications (ICC'2001), Helsinki, Finland, Jun. 2001, pp. 2048-2052 [Online]. Available: http://archvlsi.ics.forth.gr/muqpro/queueMgt.html
• 16: George Kornaros , Christoforos Kozyrakis , Panagiota Vatsolaki , Manolis Katevenis, Pipelined Multi-Queue Management in a VLSI ATM Switch Chip with Credit-Based Flow-Control, Proceedings of the 17th Conference on Advanced Research in VLSI (ARVLSI '97), p.127, September 15-16, 1997
• 17: [17] V. Kumar, T. Lakshman, and D. Stiliadis, "Beyond best effort: router architectures for the differentiated services of tomorrow's Internet," IEEE Commun. Mag., vol. 36, no. 5, pp. 152-164, May 1998.
• 18: [18] I. Mavroidis, "Heap management in hardware" Inst. Comput. Sci., Crete, Greece, Tech. Rep. FORTH-ICS/TR-222 [Online]. Available: http://archvlsi.ics.forth.gr/muqpro/heapMgt.html, FORTH.
• 19: [19] D. Stephens, J. Bennett, and H. Zhang, "Implementing scheduling algorithms in high-speed networks," IEEE J. Sel. Areas Commun. vol. 17, no. 6, pp. 1145-1158, Jun. 1999.
• 20: [20] H. Zhang, "Service disciplines for guaranteed performance in packet switching networks," Proc. IEEE, vol. 83, no. 10, pp. 1374-1396, Oct. 1995.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.3 Network Operations
          Subjects: Network management

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.5 Local and Wide-Area Networks
          Subjects: High-speed (e.g., FDDI, fiber channel, ATM)

  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, Design, Management

Keywords:
high-speed network scheduling, pipelined hard-ware heap, priority queue, synthesizable core, weighted fair queueing, weighted round robin