High-performance packet classification algorithm for many-core and multithreaded network processor

ABSTRACT

Packet classification is crucial for the Internet to provide more value-added services and guaranteed quality of service. Besides hardware-based solutions, many software-based classification algorithms have been proposed. However, classifying at 10Gbps speed or higher is a challenging problem and it is still one of the performance bottlenecks in core routers. In general, classification algorithms face the same challenge of balancing between high classification speed and low memory requirements. This paper proposes a modified Recursive Flow Classification (RFC) algorithm, Bitmap-RFC, which significantly reduces the memory requirements of RFC by applying a bitmap compression technique. To speed up classifying speed, we experiment on exploiting the architectural features of a many-core and multithreaded architecture from algorithm design to algorithm implementation. As a result, Bitmap-RFC strikes a good balance between speed and space. It can not only keep high classification speed but also reduce memory space significantly.This paper investigates the main NPU software design aspects that have dramatic performance impacts on any NPU-based implementations: memory space reduction, instruction selection, data allocation, task partitioning, and latency hiding. We experiment with an architecture-aware design principle to guarantee the high performance of the classification algorithm on an NPU implementation. The experimental results show that the Bitmap-RFC algorithm achieves 10Gbps speed or higher and has a good scalability on Intel IXP2800 NP.

REFERENCES

• 1: Agere, "Network Processors", http://www.agere.com/telecom/network_processors.html.
• 2: J. R. Allen , B. M. Bass , C. Basso , R. H. Boivie , J. L. Calvignac , G. T. Davis , L. Frelechoux , M. Heddes , A. Herkersdorf , A. Kind , J. F. Logan , M. Peyravian , M. A. Rinaldi , R. K. Sabhikhi , M. S. Siegel , M. Waldvogel, IBM PowerNP network processor: Hardware, software, and applications, IBM Journal of Research and Development, v.47 n.2-3, p.177-193, March 2003
• 3: AMCC, "Network Processors", https://www.amcc.com/MyAMCC/jsp/public/browse/controller.jsp?networkLevel=COMM&superFamily=NETP.
• 4: Avici, "Avici Intros Multiservice Line Cards", http://www.lightreading.com/document.asp?doc_id=34665&site=supercomm
• 5: F. Baboescu, S. Singh, and G. Varghese, "Packet Classification for Core Routers: Is there an alternative to CAMs", Technical Report, University of California, San Diego, 2003.
• 6: Florin Baboescu , George Varghese, Scalable packet classification, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.199-210, August 2001, San Diego, California, United States
• 7: Cisco Systems, "Cisco CRS-1 Carrier Routing System", http://www.cisco.com/en/US/products/ps5763/
• 8: Mikael Degermark , Andrej Brodnik , Svante Carlsson , Stephen Pink, Small forwarding tables for fast routing lookups, Proceedings of the ACM SIGCOMM '97 conference on Applications, technologies, architectures, and protocols for computer communication, p.3-14, September 14-18, 1997, Cannes, France
• 9: Will Eatherton , George Varghese , Zubin Dittia, Tree bitmap: hardware/software IP lookups with incremental updates, ACM SIGCOMM Computer Communication Review, v.34 n.2, April 2004 [doi>10.1145/997150.997160]
• 10: Freescale, "C-Port Network Processors", http://www.freescale.com/webapp/sps/site/homepage.jsp?nodeId=02VS0lDFTQ3126.
• 11: 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 ]
• 12: Pankaj Gupta , Nick McKeown, Packet classification on multiple fields, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.147-160, August 30-September 03, 1999, Cambridge, Massachusetts, United States
• 13: Xianghui Hu , Xinan Tang , Bei Hua, High-performance IPv6 forwarding algorithm for multi-core and multithreaded network processor, Proceedings of the eleventh ACM SIGPLAN symposium on Principles and practice of parallel programming, March 29-31, 2006, New York, New York, USA [doi>10.1145/1122971.1122998]
• 14: Huawei, "Huawei Launches NetEngine80 Core Router At Networld Interop 2001 Exhibition in US", http://www.huawei.com/news/view.do?id=88&cid=-1001
• 15: Intel, "IXP2XXX Network Processors", http://www.intel.com/design/network/products/npfamily/ixp2xxx.htm.
• 16: M. Kounavis et al., "Directions in Packet Classification for Network Processors", in Proc. of Second Workshop on Network Processors (NP2), Feb. 2003.
• 17: Chidamber Kulkarni , Matthias Gries , Christian Sauer , Kurt Keutzer, Programming challenges in network processor deployment, Proceedings of the 2003 international conference on Compilers, architecture and synthesis for embedded systems, October 30-November 01, 2003, San Jose, California, USA [doi>10.1145/951710.951735]
• 18: T. V. Lakshman , D. Stiliadis, High-speed policy-based packet forwarding using efficient multi-dimensional range matching, Proceedings of the ACM SIGCOMM '98 conference on Applications, technologies, architectures, and protocols for computer communication, p.203-214, August 31-September 04, 1998, Vancouver, British Columbia, Canada
• 19: Timothy Sherwood , George Varghese , Brad Calder, A pipelined memory architecture for high throughput network processors, Proceedings of the 30th annual international symposium on Computer architecture, June 09-11, 2003, San Diego, California
• 20: 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]
• 21: E. Spitznagel. "Compressed Data Structures for Recursive Flow Classification", Technical Report, WUCSE-2003-65, May 2003.
• 22: V. Srinivasan , G. Varghese , S. Suri , M. Waldvogel, Fast and scalable layer four switching, Proceedings of the ACM SIGCOMM '98 conference on Applications, technologies, architectures, and protocols for computer communication, p.191-202, August 31-September 04, 1998, Vancouver, British Columbia, Canada
• 23: Xinan Tang , Guang R. Gao, Automatically partitioning threads for multithreaded architectures, Journal of Parallel and Distributed Computing, v.58 n.2, p.159-189, Aug. 1999 [doi>10.1006/jpdc.1999.1551 ]
• 24: Xinan Tang , Guang R. Gao, How “hard” is thread partitioning and how “bad” is a list scheduling based partitioning algorithm?, Proceedings of the tenth annual ACM symposium on Parallel algorithms and architectures, p.130-139, June 28-July 02, 1998, Puerto Vallarta, Mexico [doi>10.1145/277651.277679]
• 25: Xinan Tang , J. Wang , Kevin B. Theobald , Guang R. Gao, Thread partitioning and scheduling based on cost model, Proceedings of the ninth annual ACM symposium on Parallel algorithms and architectures, p.272-281, June 23-25, 1997, Newport, Rhode Island, United States [doi>10.1145/258492.258519]
• 26: D. E. Taylor and J. S. Turner, "ClassBench: A Packet Classification Benchmark", Technical Report, WUCSE-2004-28, Department of Computer Science & Engineering, Washington University in Saint Louis, May 2004.
• 27: Yaxuan Qi and Jun Li, "Towards Effective Packet Classification", in Proc. of IASTED Conference on Communication, Network, and Information Security (CNIS), 2006.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.4 Parallel Architectures

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

  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
          Subjects: Parallel programming
  D.2 SOFTWARE ENGINEERING
      D.2.2 Design Tools and Techniques

General Terms:
Algorithms, Design, Experimentation, Performance

Keywords:
architecture, embedded system design, multithreading, network processor, packet classification, thread-level parallelism