Lei Yan
George Candea
ABSTRACT
This paper presents NFOS, a programming model, runtime, and profiler for productively developing software network functions (NFs) that scale on multicore machines. Writing shared-state concurrent systems that are both correct and scalable is still a serious challenge, which is why NFOS insulates developers from writing concurrent code.
In the NFOS programming model, developers write their NF as a sequential program, concerning themselves with the NF logic instead of parallelism and shared-state synchronization. The NFOS abstractions are both familiar to the NF programmer and convey to the NFOS runtime crucial information that enables it to correctly execute the NF's packet processing in parallel on multiple cores. Paired with NFOS's domain-specific concurrent data structures, this parallelism scales the NF transparently, obviating the need for developers to write concurrent code. We show that serial, stateful NFs run atop NFOS achieve scalability on par with their concurrent, hand-optimized counterparts in Cisco VPP [8].
Some scalability bottlenecks are inherent to the NF's semantics, and thus cannot be resolved while preserving those semantics. NFOS identifies the root causes of such bottlenecks and provides scalability recipes that guide developers in relaxing the NF's semantics to eliminate these bottlenecks. We present examples where such NFOS-guided relaxation of NF semantics further improves scalability by 2x to 91x.
- The CAIDA UCSD Anonymized Internet Traces - 2016. https://www.caida.org/catalog/datasets/passive_dataset. [Last accessed on 2023-10-29].Google Scholar
- DPDK Release 20.11. https://doc.dpdk.org/guides-20.11/rel_notes/release_20_11.html. [Last accessed on 2023-10-29].Google Scholar
- Fix of VPP NAT Race Condition on Address Mappings. https://gerrit.fd.io/r/c/vpp/+/31174. [Last accessed on 2023-10-29].Google Scholar
- HTTP Caching. https://developer.mozilla.org/en-US/docs/Web/HTTP/Caching. [Last accessed on 2023-10-29].Google Scholar
- Juniper Networks vSRX Virtual Firewall Datasheet. https://www.juniper.net/us/en/products/security/srx-series/vsrx-virtual-firewall-datasheet.html. [Last accessed on 2023-10-29].Google Scholar
- netElastic Systems Carrier Grade NAT (CGNAT). https://netelastic.com/products/carrier-grade-nat-cgnat/. [Last accessed on 2023-10-29].Google Scholar
- NFF-Go. https://github.com/aregm/nff-go. [Last accessed on 2023-10-29].Google Scholar
- Vector Packet Processiong (VPP). https://github.com/FDio/vpp/tree/v21.01. [Last accessed on 2023-10-29].Google Scholar
- The Year of 100GbE in Data Center Networks. https://www.datacenterknowledge.com/networks/year-100gbe-data-center-networks. [Last accessed on 2023-10-29].Google Scholar
- Utpal Banerjee, Rudolf Eigenmann, Alexandra Nicolau, and David A. Padua. Automatic Program Parallelization. Proceedings of the IEEE, 81(2), 1993.Google ScholarCross Ref
- Tom Barbette, Georgios P Katsikas, Gerald Q Maguire Jr, and Dejan Kostić. RSS++: Load and State-Aware Receive Side Scaling. In Intl. Conf. on Emerging Networking Experiments and Technologies (CoNEXT), 2019.Google ScholarDigital Library
- Theophilus Benson, Aditya Akella, and David A. Maltz. Network Traffic Characteristics of Data Centers in the Wild. In ACM Internet Measurement Conf. (IMC), 2010.Google Scholar
- Lusheng Ji Bo Han, Vijay Gopalakrishnan and Seungjoon Lee. Network Function Virtualization: Challenges and Opportunities for Innovations. IEEE Communications Magazine, 53, 2015.Google Scholar
- Michael D. Bond, Katherine E. Coons, and Kathryn S. McKinley. PACER: Proportional Detection of Data Races. In Intl. Conf. on Programming Language Design and Implementation (PLDI), 2010.Google Scholar
- Kevin Borders, Jonathan Springer, and Matthew Burnside. Chimera: A Declarative Language for Streaming Network Traffic Analysis. In USENIX Security Symp., 2012.Google Scholar
- Irina Calciu, Siddhartha Sen, Mahesh Balakrishnan, and Marcos K Aguilera. Black-Box Concurrent Data Structures for NUMA Architectures. In Intl. Conf. on Architectural Support for Programming Languages and Operating Systems (ASPLOS), 2017.Google Scholar
- LAN/MAN Standards Committee. IEEE Standard for Local and Metropolitan Area Network-Bridges and Bridged Networks. IEEE Std 802.1Q-2018 (Revision of IEEE Std 802.1Q-2014), 2018.Google Scholar
- Charlie Curtsinger and Emery D Berger. Coz: Finding Code that Counts with Causal Profiling. In ACM Symp. on Operating Systems Principles (SOSP), 2015.Google ScholarDigital Library
- Arnaldo Carvalho de Melo. The New Linux Perf Tools. http://vger.kernel.org/~acme/perf/lk2010-perf-paper.pdf. [Last accessed on 2023-10-29].Google Scholar
- Mihai Dobrescu, Norbert Egi, Katerina Argyraki, Byung-Gon Chun, Kevin Fall, Gianluca Iannaccone, Allan Knies, Maziar Manesh, and Sylvia Ratnasamy. RouteBricks: Exploiting Parallelism To Scale Software Routers. In ACM Symp. on Operating Systems Principles (SOSP), 2009.Google Scholar
- DPDK: Data Plane Development Kit. https://dpdk.org. [Last accessed on 2023-10-29].Google Scholar
- Daniel E. Eisenbud, Cheng Yi, Carlo Contavalli, Cody Smith, Roman Kononov, Eric Mann-Hielscher, Ardas Cilingiroglu, Bin Cheyney, Wentao Shang, and Jinnah Dylan Hosein. Maglev: A Fast and Reliable Software Network Load Balancer. In Symp. on Networked Systems Design and Implementation (NSDI), 2016.Google Scholar
- Paul Emmerich, Sebastian Gallenmüller, Daniel Raumer, Florian Wohlfart, and Georg Carle. MoonGen: A Scriptable High-Speed Packet Generator. In ACM Internet Measurement Conf. (IMC), 2015.Google Scholar
- Aaron Gember-Jacobson, Raajay Viswanathan, Chaithan Prakash, Robert Grandl, Junaid Khalid, Sourav Das, and Aditya Akella. OpenNF: Enabling Innovation in Network Function Control. ACM SIGCOMM Computer Communication Review, 44(4), 2014.Google Scholar
- Cary G. Gray and David R. Cheriton. Leases: An Efficient Fault-Tolerant Mechanism for Distributed File Cache Consistency. In ACM Symp. on Operating Systems Principles (SOSP), 1989.Google Scholar
- Manish Gupta, Sayak Mukhopadhyay, and Navin Sinha. Automatic Parallelization of Recursive Procedures. Intl. Journal of Parallel Programming, 28, 2000.Google Scholar
- Sangjin Han, Keon Jang, Aurojit Panda, Shoumik Palkar, Dongsu Han, and Sylvia Ratnasamy. SoftNIC: A Software NIC to Augment Hardware. Technical Report UCB/EECS-2015-155, 2015.Google Scholar
- Maurice Herlihy and J. Eliot B. Moss. Transactional Memory: Architectural Support for Lock-Free Data Structures. In Intl. Symp. on Computer Architecture (ISCA), 1993.Google Scholar
- Evolved Packet Core (EPC) for Communications Service Providers. https://networkbuilders.intel.com/docs/networkbuilders/Evolved-packet-core-EPC-for-communications-service-providers-ra.pdf. [Last accessed on 2023-10-29].Google Scholar
- Muhammad Asim Jamshed, Jihyung Lee, Sangwoo Moon, Insu Yun, Deokjin Kim, Sungryoul Lee, Yung Yi, and KyoungSoo Park. Kargus: A Highly-Scalable Software-Based Intrusion Detection System. In ACM Conf. on Computer and Communications Security (CCS), 2012.Google Scholar
- Muhammad Asim Jamshed, YoungGyoun Moon, Donghwi Kim, Dongsu Han, and KyoungSoo Park. mOS: A Reusable Networking Stack for Flow Monitoring Middleboxes. In Symp. on Networked Systems Design and Implementation (NSDI), 2017.Google Scholar
- Cullen Jennings and Francois Audet. Network Address Translation (NAT) Behavioral Requirements for Unicast UDP. RFC 4787, Internet Engineering Task Force, 2007.Google Scholar
- Murad Kablan, Blake Caldwell, Richard Han, Hani Jamjoom, and Eric Keller. Stateless Network Functions. In ACM SIGCOMM Workshop on Hot Topics in Middleboxes and Network Function Virtualization, 2015.Google Scholar
- Charlie Kaufman, Paul Hoffman, Yoav Nir, Pasi Eronen, and Tero Kivinen. Internet Key Exchange Protocol Version 2 (IKEv2). RFC 7296, Internet Engineering Task Force, 2014.Google Scholar
- Junaid Khalid, Aaron Gember-Jacobson, Roney Michael, Anubhavnidhi Abhashkumar, and Aditya Akella. Paving the Way for NFV: Simplifying Middlebox Modifications Using StateAlyzr. In Symp. on Networked Systems Design and Implementation (NSDI), 2016.Google Scholar
- Jaeho Kim, Ajit Mathew, Sanidhya Kashyap, Madhava Krishnan Ramanathan, and Changwoo Min. MV-RLU: Scaling Read-Log-Update with Multi-Versioning. In Intl. Conf. on Architectural Support for Programming Languages and Operating Systems (ASPLOS), 2019.Google Scholar
- Eddie Kohler, Robert Morris, Benjie Chen, John Jannotti, and M. Frans Kaashoek. The Click Modular Router. ACM Transactions on Computer Systems (TOCS), 18(3), 2000.Google Scholar
- Bohuslav Krena, Zdenek Letko, Rachel Tzoref, Shmuel Ur, and Tomás Vojnar. Healing Data Races On-the-Fly. In Workshop on Parallel and Distributed Systems: Testing, Analysis, and Debugging (PADTAD), 2007.Google Scholar
- Zdenek Letko, Tomás Vojnar, and Bohuslav Krena. AtomRace: Data Race and Atomicity Violation Detector and Healer. In Workshop on Parallel and Distributed Systems: Testing, Analysis, and Debugging, 2008.Google Scholar
- Guangpu Li, Dongjie Chen, Shan Lu, Madanlal Musuvathi, and Suman Nath. SherLock: Unsupervised Synchronization-Operation Inference. In Intl. Conf. on Architectural Support for Programming Languages and Operating Systems (ASPLOS), 2021.Google Scholar
- Shan Lu, Soyeon Park, Eunsoo Seo, and Yuanyuan Zhou. Learning from Mistakes - A Comprehensive Study on Real World Concurrency Bug Characteristics. In Intl. Conf. on Architectural Support for Programming Languages and Operating Systems (ASPLOS), 2008.Google Scholar
- Brandon Lucia, Joseph Devietti, Karin Strauss, and Luis Ceze. Atom-Aid: Detecting and Surviving Atomicity Violations. In Intl. Symp. on Computer Architecture (ISCA), 2008.Google Scholar
- Joao Martins, Mohamed Ahmed, Costin Raiciu, Vladimir Olteanu, Michio Honda, Roberto Bifulco, and Felipe Huici. ClickOS and the Art of Network Function Virtualization. In Symp. on Networked Systems Design and Implementation (NSDI), 2014.Google Scholar
- Paul E McKenney and John D Slingwine. Read-Copy Update: Using Execution History to Solve Concurrency Problems. In Parallel and Distributed Computing and Systems, 1998.Google Scholar
- Moonpol. https://github.com/erkinkirdan/moonpol. [Last accessed on 2023-10-29].Google Scholar
- Satish Narayanasamy, Zhenghao Wang, Jordan Tigani, Andrew Edwards, and Brad Calder. Automatically Classifying Benign and Harmful Data Races Using Replay Analysis. In Intl. Conf. on Programming Language Design and Implementation (PLDI), 2007.Google Scholar
- Aurojit Panda, Sangjin Han, Keon Jang, Melvin Walls, Sylvia Ratnasamy, and Scott Shenker. NetBricks: Taking the V out of NFV. In Symp. on Operating Systems Design and Implementation (OSDI), 2016.Google Scholar
- Francisco Pereira, Fernando M. V. Ramos, and Luis Pedrosa. Automatic Parallelization of Software Network Functions. In Symp. on Networked Systems Design and Implementation (NSDI), 2024.Google Scholar
- Shriram Rajagopalan, Dan Williams, Hani Jamjoom, and Andrew Warfield. Split/Merge: System Support for Elastic Execution in Virtual Middleboxes. In Symp. on Networked Systems Design and Implementation (NSDI), 2013.Google Scholar
- Introduction to Receive Side Scaling. https://docs.microsoft.com/en-us/windows-hardware/drivers/network/introduction-to-receive-side-scaling. [Last accessed on 2023-10-29].Google Scholar
- Stuart E Schechter, Jaeyeon Jung, and Arthur W Berger. Fast Detection of Scanning Worm Infections. In Recent Advances in Intrusion Detection, 2004.Google ScholarCross Ref
- Tomer Shanny and Adam Morrison. Occualizer: Optimistic Concurrent Search Trees From Sequential Code. In Symp. on Operating Systems Design and Implementation (OSDI), 2022.Google Scholar
- Nir Shavit and Dan Touitou. Software Transactional Memory. In Symp. on Principles of Distributed Computing, 1995.Google Scholar
- Pyda Srisuresh and Kjeld B. Egevang. Traditional IP Network Address Translator. RFC 3022, Internet Engineering Task Force, 2001.Google Scholar
- Mohammad Mejbah ul Alam, Tongping Liu, Guangming Zeng, and Abdullah Muzahid. SyncPerf: Categorizing, Detecting, and Diagnosing Synchronization Performance Bugs. In ACM EuroSys European Conf. on Computer Systems (EUROSYS), 2017.Google Scholar
- Hans Vandierendonck, Sean Rul, and Koen De Bosschere. The Paralax Infrastructure: Automatic Parallelization with a Helping Hand. In Intl. Conf. on Parallel Architectures and Compilation Techniques, 2010.Google ScholarDigital Library
- Kaushik Veeraraghavan, Peter M. Chen, Jason Flinn, and Satish Narayanasamy. Detecting and Surviving Data Races Using Complementary Schedules. In ACM Symp. on Operating Systems Principles (SOSP), 2011.Google Scholar
- Haris Volos, Andres Jaan Tack, Michael M. Swift, and Shan Lu. Applying Transactional Memory to Concurrency Bugs. In Intl. Conf. on Architectural Support for Programming Languages and Operating Systems (ASPLOS), 2012.Google ScholarDigital Library
- The Vector Packet Processing (VPP) Platform. https://wiki.fd.io/view/VPP/What_is_VPP%3f. [Last accessed on 2023-10-29].Google Scholar
- Intel VTune Performance Analyzer. https://www.intel.com/content/www/us/en/developer/tools/oneapi/vtune-profiler.html. [Last accessed on 2023-10-29].Google Scholar
- Shinae Woo, Justine Sherry, Sangjin Han, Sue Moon, Sylvia Ratnasamy, and Scott Shenker. Elastic Scaling of Stateful Network Functions. In Symp. on Networked Systems Design and Implementation (NSDI), 2018.Google Scholar
- Zhengming Yi, Yiping Yao, and Kai Chen. A Universal Construction to Implement Concurrent Data Structure for NUMA-Muticore. In Intl. Conf. on Parallel Processing, 2021.Google ScholarDigital Library
- Tingting Yu and Michael Pradel. SyncProf: Detecting, Localizing, and Optimizing Synchronization Bottlenecks. In Intl. Symp. on Software Testing and Analysis (ISSTA), 2016.Google ScholarDigital Library
- Arseniy Zaostrovnykh, Solal Pirelli, Rishabh R. Iyer, Matteo Rizzo, Luis Pedrosa, Katerina J. Argyraki, and George Candea. Verifying Software Network Functions with No Verification Expertise. In ACM Symp. on Operating Systems Principles (SOSP), 2019.Google Scholar
- Minjia Zhang, Jipeng Huang, Man Cao, and Michael D Bond. Low-Overhead Software Transactional Memory with Progress Guarantees and Strong Semantics. In Symp. on Principles and Practice of Parallel Computing (PPoPP), 2015.Google Scholar
- Zhipeng Zhao, Hugo Sadok, Nirav Atre, James C Hoe, Vyas Sekar, and Justine Sherry. Achieving 100Gbps Intrusion Prevention on a Single Server. In Symp. on Operating Systems Design and Implementation (OSDI), 2020.Google Scholar
Index Terms
- Transparent Multicore Scaling of Single-Threaded Network Functions
Recommendations
A multi-threaded object-oriented programming model
This paper presents a concurrent object-oriented programming (COOP) model established around concurrent objects which may have a body. Once an object with a body is created, its body begins to run as a separate execution thread of the object. ...
A Transactional Correctness Tool for Abstract Data Types
Transactional memory simplifies multiprocessor programming by providing the guarantee that a sequential block of code in the form of a transaction will exhibit atomicity and isolation. Transactional data structures offer the same guarantee to concurrent ...
Clojure for Number Crunching on Multicore Machines
Clojure is a Lisp language designed to run on a Java Virtual Machine (JVM) and interoperate automatically with all Java libraries. However, compared to Java, Clojure has a concurrency API that encourages programmers to take advantage of multicore ...
Comments