Towards high-performance flow-level packet processing on multi-core network processors

ABSTRACT

There is a growing interest in designing high-performance network devices to perform packet processing at flow level. Applications such as stateful access control, deep inspection and flow-based load balancing all require efficient flow-level packet processing. In this paper, we present a design of high-performance flow-level packet processing system based on multi-core network processors. Main contribution of this paper includes: a) A high performance flow classification algorithm optimized for network processors; b) An efficient flow state management scheme leveraging memory hierarchy to support large number of concurrent flows; c) Two hardware-optimized order-preserving strategies that preserve internal and external per-flow packet order. Experimental results show that: a) The proposed flow classification algorithm, AggreCuts, outperforms the well-known HiCuts algorithm in terms of classification rate and memory usage; b) The presented SigHash scheme can manage over 10M concurrent flow states on the Intel IXP2850 NP with extremely low collision rate; c) The performance of internal packet order-preserving scheme using SRAM queue-array is about 70% of that of external packet order-preserving scheme realized by ordered-thread execution.

REFERENCES

• 1: U. R. Naik and P. R. Chandra, "Designing High-performance Networking Applications", Intel Press, 2004.
• 2: 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
• 3: P. Gupta and N. McKeown, "Packet Classification Using Hierarchical Intelligent Cuttings", Proc. Hot Interconnects, 1999.
• 4: P. Gupta and N. McKewon, "Algorithms for Packet Classification", IEEE Network, March/April, 2001.
• 5: Mark H. Overmars , A. Frank van der Stappen, Range searching and point location among fat objects, Journal of Algorithms, v.21 n.3, p.629-656, Nov. 1996 [doi>10.1006/jagm.1996.0063]
• 6: Y. Qi, B. Xu and J. Li, "Evaluation and Improvement of Packet Classification Algorithms", Proc. of the 1 st International Conference on Network and Services (ICNS), 2005.
• 7: 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
• 8: Bo Xu , Dongyi Jiang , Jun Li, HSM: A Fast Packet Classification Algorithm, Proceedings of the 19th International Conference on Advanced Information Networking and Applications, p.987-992, March 25-30, 2005 [doi>10.1109/AINA.2005.200]
• 9: 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]
• 10: M. E. Kounavis, A. Kumar, H. Vin, R. Yavatkar and A. T. Campbell, "Directions in Packet Classification for Network Processors", Proc. of the 2nd Workshop on Network Processors (NP2), 2003.
• 11: J. van Lunteren and T. Engbersen, "Dynamic Multi-Field Packet Classification", Proc. of IEEE GLOBECOM, 2002.
• 12: D. E. Taylor, "Survey & Taxonomy of Packet Classification Techniques", Technical Report, Washington University in Saint-Louis, USA, 2004.
• 13: Duo Liu , Bei Hua , Xianghui Hu , Xinan Tang, High-performance packet classification algorithm for many-core and multithreaded network processor, Proceedings of the 2006 international conference on Compilers, architecture and synthesis for embedded systems, October 22-25, 2006, Seoul, Korea [doi>10.1145/1176760.1176801]
• 14: Piti Piyachon , Yan Luo, Efficient memory utilization on network processors for deep packet inspection, Proceedings of the 2006 ACM/IEEE symposium on Architecture for networking and communications systems, December 03-05, 2006, San Jose, California, USA [doi>10.1145/1185347.1185358]
• 15: Li Zhao , Yan Luo , Laxmi Bhuyan , Ravi Iyer, SpliceNP: a TCP splicer using a network processor, Proceedings of the 2005 ACM symposium on Architecture for networking and communications systems, October 26-28, 2005, Princeton, NJ, USA [doi>10.1145/1095890.1095909]
• 16: 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]
• 17: Intel Corporation, "Intel IXP2850 Network Processor Hardware Reference Manual", 2004.
• 18: Intel Corporation, "Intel IXDP2850 Advanced Development Platform System User's Manual", 2004.
• 19: Bill Carlson, Intel Internet Exchange Architecture and Applications: A Practical Guide to Intel's Network Processors, Intel Press, 2003
• 20: E. J. Johnson and A. R. Kunze, "IXP2400/2850 Programming", Intel Press, 2003.
• 21: Muthu Venkatachalam , Prashant Chandra , Raj Yavatkar, A highly flexible, distributed multiprocessor architecture for network processing, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.41 n.5, p.563-586, 5 April 2003 [doi>10.1016/S1389-1286(02)00450-4]
• 22: Y. Qi and J. Li, "Towards Effective Packet Classification", Proc. of the Conference on Communication, Network, and Information Security (CNIS 2006), 2006.
• 23: Deepa Srinivasan , Wu-chang Feng, Performance Analysis of Multi-dimensional Packet Classification on Programmable Network Processors, Proceedings of the 29th Annual IEEE International Conference on Local Computer Networks, p.360-367, November 16-18, 2004 [doi>10.1109/LCN.2004.94]
• 24: Intel Corporation, "Intel IXP2400 and IXP2800 Network Processor Programmer's Reference Manual", 2004.
• 25: http://www.intel.com/design/network/products/npfamily/ixp2xxx.htm
• 26: Sarang Dharmapurikar , Vern Paxson, Robust TCP stream reassembly in the presence of adversaries, Proceedings of the 14th conference on USENIX Security Symposium, p.5-5, July 31-August 05, 2005, Baltimore, MD
• 27: George Varghese , J. Andrew Fingerhut , Flavio Bonomi, Detecting evasion attacks at high speeds without reassembly, Proceedings of the 2006 conference on Applications, technologies, architectures, and protocols for computer communications, September 11-15, 2006, Pisa, Italy
• 28: G. Varghese, "Network Algorithmics", Elsevier Press, 2005.
• 29: Yaxuan Qi , Bo Xu , Fei He , Xin Zhou , Jianming Yu , Jun Li, Towards Optimized Packet Classification Algorithms for Multi-Core Network Processors, Proceedings of the 2007 International Conference on Parallel Processing, p.2, September 10-14, 2007 [doi>10.1109/ICPP.2007.82]
• 30: http://www.arl.wustl.edu/~hs1/PClassEval.html
• 31: Z. Cao, Z. Wang, E. Zegura, "Performance of Hashing-Based Schemes for Internet Load Balancing", Proc. IEEE INFOCOM, 2000.
• 32: Weiguang Shi , Mike H. MacGregor , Pawel Gburzynski, A scalable load balancer for forwarding internet traffic: exploiting flow-level burstiness, Proceedings of the 2005 ACM symposium on Architecture for networking and communications systems, October 26-28, 2005, Princeton, NJ, USA [doi>10.1145/1095890.1095911]
• 33: T. L. Riché, J. Mudigonda, and H. M. Vin, "Experimental Evaluation of Load Balancers in Packet Processing Systems", Proc. of the 1 st Workshop on Building Block Engine Architectures for Computers and Networks (BEACON-1), 2004.
• 34: http://pma.nlanr.net/Special/
• 35: Andrew W. Moore , Denis Zuev, Internet traffic classification using bayesian analysis techniques, Proceedings of the 2005 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 06-10, 2005, Banff, Alberta, Canada
• 36: Thomas Karagiannis , Konstantina Papagiannaki , Michalis Faloutsos, BLINC: multilevel traffic classification in the dark, Proceedings of the 2005 conference on Applications, technologies, architectures, and protocols for computer communications, August 22-26, 2005, Philadelphia, Pennsylvania, USA
• 37: Subhabrata Sen , Oliver Spatscheck , Dongmei Wang, Accurate, scalable in-network identification of p2p traffic using application signatures, Proceedings of the 13th international conference on World Wide Web, May 17-20, 2004, New York, NY, USA [doi>10.1145/988672.988742]

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Design studies

General Terms:
Algorithms, Experimentation, Performance

Keywords:
classification, hashing, network processor, packet order