LOP: a novel SRAM-based architecture for low power and high throughput packet classification

ABSTRACT

Packet classification has become an important problem to solve in modern network processors used in networking embedded systems such as routers. Algorithms for matching incoming packets from the network to pre-defined rules, have been proposed by a number of researchers. Current software-based packet classification techniques have low performance, prompting many researchers to move their focus to new architectures encompassing both software and hardware components. Some of the newer hardware architectures exclusively utilize Ternary Content Addressable Memory (TCAM) to improve the performance of rule matching. However, this results in systems with high power consumption. TCAM consumes a high amount of power due to the fact that it reads the entire memory array during every access, much of which is unnecessary. In this paper, we propose LOP, a novel SRAM-based architecture where incoming packets are compared against parts of all rules simultaneously until a single matching rule is found for the compared bits in the packets. This method LOP significantly reduces power consumption as only a segment of the memory is compared against the incoming packet. Despite the additional time penalty to match a single packet, parallel comparison of multiple packets can improve throughput beyond that of the TCAMapproaches, while consuming significantly low power. Nine different benchmarks were tested in two classification systems, with results showing that LOP architectures provide high lookup rates and high throughput, and low power consumption. Compared with a state-of-the-art TCAM implementation (throughput of 495 Million Search per Second (Msps)) in 65nm CMOS technology, on average, LOP saves 43% of energy consumption with a throughput of 590Msps.

REFERENCES

• 1: Analog bits technologies, 2008. Available at: http://www.analogbits.com/.
• 2: Classbench tools, 2008. Available at: http://www.arl.wustl.edu/det3/ClassBench/.
• 3: Modelsim -- a comprehensive simulation and debug environment for complex asic and fpga designs, 2008. Avalibale at: http://www.model.com/.
• 4: Sibercore technologies, 2008. Available at: http://www.sibercore.com/.
• 5: Synopsys, 2008. Available at: http://www.synopsys.com/home.aspx/.
• 6: F. Basci and T. Kocak. Statistically partitioned, low power tcam. In The 2nd Annual IEEE Northeast Workshop on Circuits and Systems, 2004.
• 7: H. Che, Z. Wang, K. Zheng, and B. Liu. Dres: Dynamic range encoding scheme for tcam coprocessors. IEEE Transactions on Computers, pages 902--915, 2008.
• 8: P. Gupta and N. McKeown. Packet classification on multiple fields. In SIGCOMM '99, 1999.
• 9: P. Gupta and N. Mckeown. Classifying packets with hierarchical intelligent cuttings. Micro,IEEE, 20:34--41, 2000.
• 10: P. Gupta and N. Mckeown. Algorithms for packet classification. IEEE Networks, 15:24--32, 2001.
• 11: S. Kaxiras and G. Keramidas. Ipstash: a power-efficient memory architeture for ip-lookup. In the 36th International Symposium on Microarchitecture (MICRO-36 2003), 2003.
• 12: S. Kaxiras and G. Keramidas. Ipstash: a set-associative memory approach for efficient ip-lookup. In INFOCOM'05), 2005.
• 13: A. Kennedy, X. Wang, Z. Liu, and B. Liu. Low power architecture for high speed packet classification. In ANCS'08, 2008.
• 14: K. Lakshminarayanan, A. Rangarajan, and S. Venkatachary. Algorithms for advanced packet classification with ternary cams. In SIGCOMM, 2005.
• 15: M. Lin, J. Luo, and Y. Ma. A low--power monolithically stacked 3d-tcam. In ISCAS, 2008.
• 16: H. Liu. Efficient mapping of range classifier into ternary-cam. In 10th Symposium on High Performance Interconnects Hot Interconnects, 2002.
• 17: N. Mohan. Low-Power High-Performance Ternary Content Addressable Memory Circuits. PhD in electrical and computer engineering, Electrical and Computer Engineering, University of Waterloo, Canada, 2006.
• 18: M. Nourani and M. Faezipour. A single-cycle multi-match packet classification engine using tcams. In the 14th IEEE Symposium on High--Performance Interconnects (HOTI'06), 2006.
• 19: K. Pagiamtzis and A. Sheikholeslami. Pipelined match-lines and hierarchical search-lines for low-power content-addressable memories. In the IEEE 2003 Custom Integrated Circuits Conference, 2003.
• 20: K. Pagiamtzis and A. Sheikholeslami. A low-power content-addressable memory (cam) using pipelind hierarchical search scheme. IEEE Journal of Solid-State Circuits, pages 1512-- 1519, 2004.
• 21: S. Singh, F. Baboescu, G. Varghese, and J.Wang. Packet classification using multidimensional cutting. In ACM SIGCOMM'03, 2003.
• 22: H. Song and J.W. Lockwood. Efficient packet classification for network intrusion detection using fpga. In FPGA, 2005.
• 23: H. Song and J. Turner. Fast filter updates for packet classification using tcam. In GLOBECOM, 2006.
• 24: E. Spitznagel, D. Taylor, and J. Turner. Packet classification using extended tcams. In 11th IEEE International Conference on Network Protocols, 2003.
• 25: V. Srinivasan, S. Suri, and G. Varghese. Packet classification using tuple space search. In SIGCOMM 99, 1999.
• 26: D. E. Taylor. Survey and taxonomy of packet classification techniques. ACM Computing Surveys, 37:238--375, 2005.
• 27: D. E. Taylor and J. S. Turner. Classbench: A packet classification benchmark. In IEEE 24th INFOCOM, 2005.
• 28: B.-D. Yang and L.-S. Kim. A low-power cam using pulsed nand-nor match-line and charge-recycling search-line driver. IEEE Journal of Solid-State Circuits, pages 1736--1744, 2005.
• 29: F. Yu, T. V. Lakshman, M. A. Motoyama, and R. H. Katz. Efficient multimatch packet classification for network security application. IEEE Journal on Selected Areas in Communications, 24:1805--1816, 2006.
• 30: F. Zane, G. Narlikar, and A. Basu. Coolcams: Power-efficient tcams for forwarding engines. In IEEE INFOCOM'03, 2003.

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.0 General
          Subjects: Security and protection (e.g., firewalls)

General Terms:
Algorithms, Design, Performance

Keywords:
hardware design, low-power, packet classification