MultiLayer processing - an execution model for parallel stateful packet processing

ABSTRACT

Mostly emerging network applications comprise deep packet inspection and/or stateful capabilities. Stateful workloads present limitations that reduce the exploitation of parallelism, unlike other network applications that show marginal dependencies among packets. In addition, differences among packet processing lead to significant negative interaction between threads, especially in the memory hierarchy.

We propose MultiLayer Processing (MLP) as an execution model to properly exploit the levels of parallelism of stateful applications. The goal of MLP is to increase the system throughput by increasing the synergy among threads in the memory hierarchy, and alleviating the contention in critical sections of parallel workloads. We show that MLP presents about 2.4x higher throughput than other execution models with large processor architectures.

REFERENCES

• 1: Netra Data Plane Software Suite 2.0 Reference Manual, 2007.
• 2: Eduard Ayguade , Xavier Martorell , Jesus Labarta , Marc Gonzalez , Nacho Navarro, Exploiting Multiple Levels of Parallelism in OpenMP: A Case Study, Proceedings of the 1999 International Conference on Parallel Processing, p.172, September 21-24, 1999
• 3: M. Baron. Tilera's cores communicate better. Microprocessor Report, Nov 2007.
• 4: Cavium Networks Inc. http://www.caviumnetworks.com.
• 5: M. Colajanni and M. Marchetti. A parallel architecture for stateful intrusion detection in high traffic networks. In IEEE / IST Workshop on Monitoring, Attack Detection and Mitigation, Tuebingen, Germany, Sept. 2006.
• 6: Network Security: 128-core processor is designed for secure LAN. http://www.eetimes.com.
• 7: Theofanis Constantinou , Yiannakis Sazeides , Pierre Michaud , Damien Fetis , Andre Seznec, Performance implications of single thread migration on a chip multi-core, ACM SIGARCH Computer Architecture News, v.33 n.4, November 2005 [doi>10.1145/1105734.1105745]
• 8: M. Franklin and S. Datar. Pipeline task scheduling on network processors. In Procs. of Workshop NP3, Madrid, Spain, 2004.
• 9: R. Golla. Niagara2: A highly threaded Server-on-a-Chip. http://www.opensparc.net/pubs/preszo/06/04-Sun-Golla.pdf.
• 10: B. Haagdorens, T. Vermeiren, and M. Goossens. Improving the performance of signature-based network intrusion detection sensors by multi-threading. In Procs. of WISA-5, August 2004.
• 11: Christopher L. Hayes , Yan Luo, DPICO: a high speed deep packet inspection engine using compact finite automata, Proceedings of the 3rd ACM/IEEE Symposium on Architecture for networking and communications systems, December 03-04, 2007, Orlando, Florida, USA [doi>10.1145/1323548.1323579]
• 12: Sunil Kim , Jun-yong Lee, A system architecture for high-speed deep packet inspection in signature-based network intrusion prevention, Journal of Systems Architecture: the EUROMICRO Journal, v.53 n.5-6, p.310-320, May, 2007 [doi>10.1016/j.sysarc.2006.10.005]
• 13: Christopher Kruegel , Fredrik Valeur , Giovanni Vigna , Richard Kemmerer, Stateful Intrusion Detection for High-Speed Networks, Proceedings of the 2002 IEEE Symposium on Security and Privacy, p.285, May 12-15, 2002
• 14: Arindam Mallik , Yu Zhang , Gokhan Memik, Automated task distribution in multicore network processors using statistical analysis, Proceedings of the 3rd ACM/IEEE Symposium on Architecture for networking and communications systems, December 03-04, 2007, Orlando, Florida, USA [doi>10.1145/1323548.1323563]
• 15: Michael R. Marty , Mark D. Hill, Virtual Hierarchies, IEEE Micro, v.28 n.1, p.99-109, January 2008 [doi>10.1109/MM.2008.19]
• 16: S. Melvin, M. Nemirovsky, E. Musoll, J. Huynh, R. Milito, H. Urdaneta, and K. Saraf. A massively multithreaded packet processor. In Procs. of Workshop NP2, CA, USA, Feb 2003.
• 17: Jose Eduardo Moreira, On the implementation and effectiveness of autoscheduling for shared-memory multiprocessors, University of Illinois at Urbana-Champaign, Champaign, IL, 1996
• 18: National Lab of Applied Network Research. http://pma.nlanr.net/Traces.
• 19: V. Paxson, R. Sommer, and N. Weaver. An architecture for exploiting multi-core processors to parallelize network intrusion prevention. In Proc. IEEE Sarnoff Symposium, May 2007.
• 20: W. Plishker. Automated task allocation for network processors, October 2004.
• 21: Raza Microelectronics Inc. http://www.razamicroelectronics.com.
• 22: J. Renau, B. Fraguela, J. Tuck, W. Liu, M. Prvulovic, L. Ceze, S. Sarangi, P. Sack, K. Strauss, and P. Montesinos. SESC simulator, January 2005. http://sesc.sourceforge.net.
• 23: Derek L. Schuff , Yung Ryn Choe , Vijay S. Pai, Conservative vs. optimistic parallelization of stateful network intrusion detection, Proceedings of the 12th ACM SIGPLAN symposium on Principles and practice of parallel programming, March 14-17, 2007, San Jose, California, USA [doi>10.1145/1229428.1229455]
• 24: D. L. Schuff and V. S. Pai. Design alternatives for a high-performance self-securing ethernet network interface. In Procs. of 21th IPDPS, pages 1--10. IEEE, March 2007.
• 25: The open source network intrusion detection system. http://www.snort.org.
• 26: A. Srinivasan, P. Holman, J. Anderson, S. Baruah, and J. Kaur. Multiprocessor scheduling in processor-based router platforms: Issues and ideas. In Network Processor Design: Issues and Practices, November 2003.
• 27: Sun Microsystems. UltraSPARC T1 Supplement to the UltraSPARC Architecture 2005, 2006.
• 28: M. Vallentin, R. Sommer, J. Lee, C. Leres, V. Paxson, and B. Tierney. The NIDS Cluster: Scalable, Stateful Network Intrusion Detection on Commodity Hardware. In Procs. of 10th RAID, pages 107--126, Sept 2007.
• 29: Javier Verdú , Jorge Garcí , Mario Nemirovsky , Mateo Valero, Architectural impact of stateful networking applications, Proceedings of the 2005 ACM symposium on Architecture for networking and communications systems, October 26-28, 2005, Princeton, NJ, USA [doi>10.1145/1095890.1095893]
• 30: T. Vermeiren, E. Borghs, and B. Haagdorens. Evaluation of software techniques for parallel packet processing on multi-core processors. In Procs. of IEEE CCNC, NV, USA, Jan. 2004.
• 31: N. Weng and T. Wolf. Pipelining vs. multiprocessors - choosing the right network processor system topology. In Procs. of Workshop ANCHOR, Munich, Germany, June 2004.
• 32: Ning Weng , Tilman Wolf, Profiling and mapping of parallel workloads on network processors, Proceedings of the 2005 ACM symposium on Applied computing, March 13-17, 2005, Santa Fe, New Mexico [doi>10.1145/1066677.1066879]
• 33: Tilman Wolf , Prashanth Pappu , Mark A. Franklin, Predictive scheduling of network processors, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.41 n.5, p.601-621, 5 April 2003 [doi>10.1016/S1389-1286(02)00452-8]
• 34: Fang Yu , Randy H. Katz, High speed deep packet inspection with hardware support, University of California at Berkeley, Berkeley, CA, 2006

INDEX TERMS

Primary Classification:
  B. Hardware
  B.8 Performance and Reliability
      B.8.2 Performance Analysis and Design Aids

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.0 General
          Subjects: Security and protection (e.g., firewalls)

General Terms:
Algorithms, Design, Performance

Keywords:
Snort, deep packet inspection, massively multithreaded architectures, multilayer processing, stateful