Low power architecture for high speed packet classification

ABSTRACT

Today's routers need to perform packet classification at wire speed in order to provide critical services such as traffic billing, priority routing and blocking unwanted Internet traffic. With everincreasing ruleset size and line speed, the task of implementing wire speed packet classification with reduced power consumption remains difficult. Software approaches are unable to classify packets at wire speed as line rates reach OC-768, while state of the art hardware approaches such as TCAM still consume large amounts of power.

This paper presents a low power architecture for a high speed packet classifier which can meet OC-768 line rate. The architecture consists of an adaptive clocking unit which dynamically changes the clock speed of an energy efficient packet classifier to match fluctuations in traffic on a router line card. It achieves this with the help of a scheme developed to keep clock frequencies at the lowest speed capable of servicing the line card while reducing frequency switches. The low power architecture has been tested on OC-48, OC-192 and OC-768 packet traces created from real life network traces obtained from NLANR while classifying packets using synthetic rulesets containing up to 25,000 rules. Simulation results of our classifier implemented on a Cyclone 3 and Stratix 3 FPGA, and as an ASIC show that power savings of between 17--88% can be achieved, using our adaptive clocking unit rather than a fixed clock speed.

REFERENCES

• 1: Pankaj Gupta , Nick McKeown, Packet classification on multiple fields, ACM SIGCOMM Computer Communication Review, v.29 n.4, p.147-160, Oct. 1999
• 2: Pankaj Gupta , Nick McKeown, Classifying Packets with Hierarchical Intelligent Cuttings, IEEE Micro, v.20 n.1, p.34-41, January 2000 [doi>10.1109/40.820051]
• 3: Sumeet Singh , Florin Baboescu , George Varghese , Jia Wang, Packet classification using multidimensional cutting, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863980]
• 4: Florin Baboescu , George Varghese, Scalable packet classification, IEEE/ACM Transactions on Networking (TON), v.13 n.1, p.2-14, February 2005 [doi>10.1109/TNET.2004.842232]
• 5: F. Baboescu, S. Singh, and G. Varghese, "Packet classification for core routers: Is there an alternative to CAMs?" in IEEE INFOCOM, 2003, pp. 53--63.
• 6: V. Srinivasan , S. Suri , G. Varghese, Packet classification using tuple space search, ACM SIGCOMM Computer Communication Review, v.29 n.4, p.135-146, Oct. 1999
• 7: P. Gupta and N. McKeown, "Algorithms for packet classification," IEEE Network Mag., vol. 15, no. 2, pp. 24--32, 2001.
• 8: T. Woo, "A modular approach to packet classification: algorithms and results," in IEEE INFOCOM, Mar. 2000, pp. 1213--1222.
• 9: P. C. Wang, C. T. Chan, C. L. Lee and H. Y. Chang "Scalable Packet Classification for Enabling Internet Differentiated Services" IEEE Trans. on Multimedia, vol. 8, no. 6, pp. 1239--1249, 2006.
• 10: A. Kennedy, D. Bermingham, X. Wang, B. Liu. "Power Analysis of Packet Classification on Programmable Network Processors". 2007 IEEE Intl Conf on Signal Processing and Communications, Dubai, 24--27 Nov, pp. 1231--1234.
• 11: Cypress Ayama 10000 Network Search Engine, http://download.cypress.com.edgesuite.net/design_resources/datasheets/contents/cynse10256_8.pdf
• 12: Kai Zheng , Hao Che , Zhijun Wang , Bin Liu , Xin Zhang, DPPC-RE: TCAM-Based Distributed Parallel Packet Classification with Range Encoding, IEEE Transactions on Computers, v.55 n.8, p.947-961, August 2006 [doi>10.1109/TC.2006.123]
• 13: Ed Spitznagel , David Taylor , Jonathan Turner, Packet Classification Using Extended TCAMs, Proceedings of the 11th IEEE International Conference on Network Protocols, p.120, November 04-07, 2003
• 14: D. Pao, Y Keung Li, P Zhou, "An encoding scheme for TCAM-based packet classification" Advanced Communication Technology, Feb. 2006.
• 15: Passive Measurement and Analysis Project, National Labority for Applied Network Research. http://pma.nlanr.net
• 16: Corporation for Education Network Initiatives in California trace ftp://pma.nlanr.net/traces/long/cnic/1/
• 17: Yan Luo , Jia Yu , Jun Yang , Laxmi N. Bhuyan, Conserving network processor power consumption by exploiting traffic variability, ACM Transactions on Architecture and Code Optimization (TACO), v.4 n.1, p.4-es, March 2007 [doi>10.1145/1216544.1216547]
• 18: Ravi Kokku, Upendra B. Shevade, Nishit S. Shah, Mike Dahlin, Harrick M. Vin "Energy-Efficient Packet Processing", www.cs.utexas.edu/users/dahlin/papers/packet-power-feb2004.pdf
• 19: Yan Luo , Jun Yang , Laxmi N. Bhuyan , Li Zhao, NePSim: A Network Processor Simulator with a Power Evaluation Framework, IEEE Micro, v.24 n.5, p.34-44, September 2004 [doi>10.1109/MM.2004.52]
• 20: C. T. Chow, L. S. M. Tsui, P. H. W. Leong, W. Luk, S. Wilton, "Dynamic voltage scaling for commercial FPGAs", IEEE International Conference on Field Programmable Technology, December, 2005
• 21: Daniel Hoffman , Paul Strooper, ClassBench: a framework for automated class testing, Software—Practice & Experience, v.27 n.5, p.573-597, May 1997 [doi>10.1002/(SICI)1097-024X(199705)27:5<573::AID-SPE98>3.3.CO;2-V]
• 22: A. Kinane, "Energy Efficient Hardware Acceleration of Multimedia Processing Tools" PhD thesis, Dublin City University, May 2006.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.0 General

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.6 Internetworking

General Terms:
Experimentation, Measurement, Performance, Security

Keywords:
energy efficient, frequency scaling, hardware accelerator, packet classification