Exploiting locality to ameliorate packet queue contention and serialization

ABSTRACT

Packet processing systems maintain high throughput despite relatively high memory latencies by exploiting the coarse-grained parallelism available between packets. In particular, multiple processors are used to overlap the processing of multiple packets. Packet queuing-the fundamental mechanism enabling packet scheduling, differentiated services, and traffic isolation-requires a read-modify-write operation on a linked list data structure to enqueue and dequeue packets; this operation represents a potential serializing bottleneck. If all packets awaiting service are destined for different queues, these read-modify-write cycles can proceed in parallel. However, if all or many of the incoming packets are destined for the same queue, or for a small number of queues, then system throughput will be serialized by these sequential external memory operations. For this reason, low latency SRAMs are used to implement the queue data structures. This reduces the absolute cost of serialization but does not eliminate it; SRAM latencies determine system throughput.In this paper we observe that the worst-case scenario for packet queuing coincides with the best-case scenario for caches: i.e., when locality exists and the majority of packets are destined for a small number of queues. The main contribution of this work is the queuing cache, which consists of a hardware cache and a closely coupled queuing engine that implements queue operations. The queuing cache improves performance dramatically by moving the bottleneck from external memory onto the packet processor, where clock rates are higher and latencies are lower. We compare the queuing cache to a number of alternatives, specifically, SRAM controllers with: no queuing support, a software-controlled cache plus a queuing engine (like that used on Intel's IXP network processor), and a hardware cache. Relative to these models, we show that a queuing cache improves worst-case throughput by factors of 3.1, 1.5, and 2.1 and the throughput of real-world traffic traces by factors of 2.6, 1.3, and 1.75, respectively. We also show that the queuing cache decreases external memory bandwidth usage, on-chip communication, and the number of queuing instructions executed under best-case, worst-case and real-world traffic workloads. Based on our VHDL models, we conclude that a queuing cache could be implemented at a low cost relative to the resulting performance and efficiency benefits.

REFERENCES

• 1: M. Adiletta, et al. "The Next Generation of Intel IXP Network Processors," Intel Technology Journal, vol. 6, no 3, pp. 6--18, Aug 2002.
• 2: Men-Chow Chiang , Gurindar S. Sohi, Evaluating Design Choices for Shared Bus Multiprocessors in a Throughput-Oriented Environment, IEEE Transactions on Computers, v.41 n.3, p.297-317, March 1992 [doi>10.1109/12.127442 ]
• 3: C. Scheurich , M. Dubois, Lockup-free caches in high-performance multiprocessors, Journal of Parallel and Distributed Computing, v.11 n.1, p.25-36, Jan. 1991 [doi>10.1016/0743-7315(91)90068-K]
• 4: Jahangir Hasan , Satish Chandra , T. N. Vijaykumar, Efficient use of memory bandwidth to improve network processor throughput, Proceedings of the 30th annual international symposium on Computer architecture, June 09-11, 2003, San Diego, California
• 5: S. Iyer, R. R. Compella, and N. McKeown, "Designing Buffers for Router Line Cards," Stanford University Technical Report - TR02-HPNG-031001, Stanford, CA, 2002.
• 6: S. Iyer, R. R. Kompella, and N. McKeown, "Analysis of a Memory Architecture for Fast Packet Buffers," IEEE HPSR'02, Dallas, May 2001.
• 7: G. Shrimali and N. McKeown, "Statistical Guarantees for Packet Buffers: The Monolithic DRAM Case," Stanford University HPNG Technical Report - TR04-HPNG-020603, Stanford, CA, 2004.
• 8: Scott Rixner , William J. Dally , Ujval J. Kapasi , Peter Mattson , John D. Owens, Memory access scheduling, Proceedings of the 27th annual international symposium on Computer architecture, p.128-138, June 2000, Vancouver, British Columbia, Canada
• 9: Wi-fen Lin, Reducing DRAM Latencies with an Integrated Memory Hierarchy Design, Proceedings of the 7th International Symposium on High-Performance Computer Architecture, p.301, January 20-24, 2001
• 10: Y. Joo and N. McKeown, "Doubling Memory Bandwidth for Network Buffers," Proc. IEEE Infocom 1998, vol. 2, pp. 808--815, San Francisco.
• 11: Sally A. McKee , William A. Wulf , James H. Aylor , Maximo H. Salinas , Robert H. Klenke , Sung I. Hong , Dee A. B. Weikle, Dynamic Access Ordering for Streamed Computations, IEEE Transactions on Computers, v.49 n.11, p.1255-1271, November 2000 [doi>10.1109/12.895941 ]
• 12: R. L. Lee , P. C. Yew , D. H. Lawrie, Multiprocessor cache design considerations, Proceedings of the 14th annual international symposium on Computer architecture, p.253-262, June 02-05, 1987, Pittsburgh, Pennsylvania, United States [doi>10.1145/30350.30379]
• 13: A. Nikologiannis, M. Katevenis, "Efficient Per-Flow Queuing in DRAM at OC-192 Line Rate using Out-of-Order Execution Techniques," Proc. IEEE International Conference on Communications (ICC'2001), Helsinki, pp. 2048--2052, June 2001.
• 14: S.-T. Chuang, A. Goel, N. McKeown, B. Prabhakar, "Matching output queuing with a combined input and output queued switch," in Proc. IEEE INFOCOM, 1999.
• 15: M.G. Hluchyj, M.J. Karol, "Queuing in high-performance packet switching," IEEE J. Sel. Areas Commun. 6 (9), 1587--1597, 1988.
• 16: Saleem N. Bhatti , Jon Crowcroft, QoS-Sensitive Flows: Issues in IP Packet Handling, IEEE Internet Computing, v.4 n.4, p.48-57, July 2000 [doi>10.1109/4236.865087 ]
• 17: J-G Chen, et al. Chapter 14-Implementing High-Performance, High-Value Traffic Management Using Agere Network Processor Solutions, in Network Processor Design, volume 2, Morgan Kaufmann, 2004.
• 18: M. Shreedhar , George Varghese, Efficient fair queueing using deficit round-robin, IEEE/ACM Transactions on Networking (TON), v.4 n.3, p.375-385, June 1996 [doi>10.1109/90.502236]
• 19: V. Frost and B. Melamed, "Traffic Modeling for Telecommunications Networks," IEEE Communications Magazine, 32(3), pp. 70--80, March, 1994.
• 20: Alan Jay Smith, Cache Memories, ACM Computing Surveys (CSUR), v.14 n.3, p.473-530, Sept. 1982 [doi>10.1145/356887.356892]
• 21: Backbone packet header traces at OC192 and OC48, collected at Cooperative Association for Internet Data Analysis (CAIDA), http://www.caida.org/projects/trends/data/
• 22: Backbone and edge packet header traces collected from the Internet Measurement, Internet Analysis, National Laboratory for Applied Network Research (NLANR), http://moat.nlanr.net/

INDEX TERMS

Primary Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.m Miscellaneous

General Terms:
Design, Performance

Keywords:
buffering, cache, packet queuing