A scalable multithreaded L7-filter design for multi-core servers

ABSTRACT

L7-filter is a significant component in Linux's QoS framework that classifies network traffic based on application layer data. It enables subsequent distribution of network resources in respect to the priority of applications. Considerable research has been reported to deploy multi-core architectures for computationally intensive applications. Unfortunately, the proliferation of multi-core architectures has not helped fast packet processing due to: 1) the lack of efficient parallelism in legacy network programs, and 2) the non-trivial configuration for scalable utilization on multi-core servers.

In this paper, we propose a highly scalable parallelized L7-filter system architecture with affinity-based scheduling on a multi-core server. We start with an analytical study of the system architecture based on an offline design. Similar to Receive Side Scaling (RSS) in the NIC, we develop a model to explore the connection level parallelism in L7-filter and propose an affinity-based scheduler to optimize system scalability. Performance results show that our optimized L7-filter has superior scalability over the naive multithreaded version. It improves system performance by about 50% when all the cores are deployed.

REFERENCES

• 1: Cosimo Anglano, A Comparative Evaluation of Implicit Coscheduling Strategies for Networks of Workstations, Proceedings of the 9th IEEE International Symposium on High Performance Distributed Computing, p.221, August 01-04, 2000
• 2: Application Layer Packet Classifier for Linux (L7-filter), http://17-filter.sourceforge.net/.
• 3: Cisco Internetworking Operating System (IOS) IPS Deployment Guide, http://www.cisco.com.
• 4: Cisco Systems, Inc., "Application-Oriented Networking: Products and Services", http://www.cisco.com/en/US/products/ps6692/Products_Sub_Category_Home.html.
• 5: Andrea C. Dusseau , Remzi H. Arpaci , David E. Culler, Effective distributed scheduling of parallel workloads, ACM SIGMETRICS Performance Evaluation Review, v.24 n.1, p.25-36, May 1996
• 6: A. P. Foong, et al., "An In-depth Analysis of the Impact of Processor Affinity on Network Performance", IEEE International Conference on Networks (ICON), 2004.
• 7: 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]
• 8: L. Kencl, et al., "Adaptive load sharing for network processors". INFOCOM 2002.
• 9: Sailesh Kumar , Jonathan Turner , John Williams, Advanced algorithms for fast and scalable 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.1185359]
• 10: Libnids, http://libnids.sourceforge.net/.
• 11: MIT DARPA Intrusion Detection Data Sets, http://www.ll.mit.edu/IST/ideval/data/2000/2000_data_index.html.
• 12: Abhishek Mitra , Walid Najjar , Laxmi Bhuyan, Compiling PCRE to FPGA for accelerating SNORT IDS, 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.1323571]
• 13: I. Molnar, "Goals, Design and Implementation of the New Ultra-Scalable O(1) Scheduler", Linux Kernel, April 2002. Docomentation/sched-design.txt.
• 14: Shailabh Nagar , Ajit Banerjee , Anand Sivasubramaniam , Chita R. Das, A closer look at coscheduling approaches for a network of workstations, Proceedings of the eleventh annual ACM symposium on Parallel algorithms and architectures, p.96-105, June 27-30, 1999, Saint Malo, France [doi>10.1145/305619.305630]
• 15: G. Narayanaswamy , P. Balaji , W. Feng, An Analysis of 10-Gigabit Ethernet Protocol Stacks in Multicore Environments, Proceedings of the 15th Annual IEEE Symposium on High-Performance Interconnects, p.109-116, August 22-24, 2007 [doi>10.1109/HOTI.2007.7]
• 16: O(1) scheduler, http://www.ibm.com/developerworks/linux/library/l-scheduler/.
• 17: Performance Application Programming Interface (PAPI), http://icl.cs.utk.edu/papi/.
• 18: Piti Piyachon , Yan Luo, Compact state machines for high performance pattern matching, Proceedings of the 44th annual conference on Design automation, June 04-08, 2007, San Diego, California [doi>10.1145/1278480.1278607]
• 19: 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]
• 20: Receive Side Scaling (RSS), http://www.microsoft.com/whdc/device/network/NDIS_RSS.mspx/.
• 21: G. Regnier et al, "ETA: Experience with An Intel Xeon Processor As A Packet Processing Engine", HOT Interconnects 2003.
• 22: Greg Regnier , Srihari Makineni , Ramesh Illikkal , Ravi Iyer , Dave Minturn , Ram Huggahalli , Don Newell , Linda Cline , Annie Foong, TCP Onloading for Data Center Servers, Computer, v.37 n.11, p.48-58, November 2004 [doi>10.1109/MC.2004.223]
• 23: Weiguang Shi , M. H. MacGregor , Pawel Gburzynski, Load balancing for parallel forwarding, IEEE/ACM Transactions on Networking (TON), v.13 n.4, p.790-801, August 2005 [doi>10.1109/TNET.2005.852881]
• 24: Weiguang Shi , Lukas Kencl, Sequence-preserving adaptive load balancers, 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.1185367]
• 25: Bryan Veal , Annie Foong, Performance scalability of a multi-core web server, 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.1323562]
• 26: Fang Yu , Zhifeng Chen , Yanlei Diao , T. V. Lakshman , Randy H. Katz, Fast and memory-efficient regular expression matching 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.1185360]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Multiple-instruction-stream, multiple-data-stream processors (MIMD)

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

General Terms:
Design, Measurement, Performance

Keywords:
L7-filter, QoS, affinity, multi-core, packet classification, parallelism, scalability, scheduling