P4Visor: lightweight virtualization and composition primitives for building and testing modular programs

ABSTRACT

Programmable data planes, PDPs, enable an unprecedented level of flexibility and have emerged as a promising alternative to existing data planes. Despite the rapid development and prototyping cycles that PDPs promote, the existing PDP ecosystem lacks appropriate abstractions and algorithms to support these rapid testing and deployment life-cycles. In this paper, we propose P4Visor, a lightweight virtualization abstraction that provides testing primitives as a first-order citizen of the PDP ecosystem. P4Visor can efficiently support multiple PDP programs through a combination of compiler optimizations and program analysis-based algorithms. P4Visor s algorithm improves over state-of-the-art techniques by significantly reducing the resource overheads associated with embedding numerous versions of a PDP program into hardware. To demonstrate the efficiency and viability of P4Visor, we implemented and evaluated P4Visor on both a software switch and an FPGA-based hardware switch using fourteen different PDP programs. Our results demonstrate that P4Visor introduces minimal overheads (less than 1%) and is one order of magnitude more efficient than existing PDPs primitives for concurrently supporting multiple programs.

References

1. Emile Aarts and Jan Korst. 1989. Simulated Annealing and Boltzmann Machines: A Stochastic Approach to Combinatorial Optimization and Neural Computing. John Wiley & Sons, Inc., New York, NY, USA.
2. Ali Al-Shabibi, Marc De Leenheer, Matteo Gerola, Ayaka Koshibe, Guru Parulkar, Elio Salvadori, and Bill Snow. 2014. OpenVirteX: Make Your Virtual SDNs Programmable. In Proceedings of the Third Workshop on Hot Topics in Software Defined Networking (HotSDN '14). ACM, New York, NY, USA, 25--30.
3. Richard Alimi, Ye Wang, and Y. Richard Yang. 2008. Shadow Configuration As a Network Management Primitive. In Proceedings of the ACM SIGCOMM 2008 Conference on Data Communication (SIGCOMM '08). ACM, New York, NY, USA, 111--122.
4. Diogo V. Andrade, Mauricio G. C. Resende, and Renato F. Werneck. 2012. Fast local search for the maximum independent set problem. Journal of Heuristics 18, 4 (01 Aug 2012), 525--547.
5. The Authors. 2018. The P4 Router Programs. https://github.com/Brown-NSG/P4Visor/tree/master/FPGAtarget/p4program. (2018).
6. The Authors. 2018. The P4Visor Compiler for BMV2 target. https://github.com/Brown-NSG/P4Visor. (2018).
7. Pat Bosshart, Glen Gibb, Hun-Seok Kim, George Varghese, Nick McKeown, Martin Izzard, Fernando Mujica, and Mark Horowitz. 2013. Forwarding Metamorphosis: Fast Programmable Match-action Processing in Hardware for SDN. SIGCOMM Comput. Commun. Rev. 43, 4 (Aug. 2013), 99--110.
8. Anat Bremler-Barr, Yotam Harchol, and David Hay. 2016. OpenBox: A Software-Defined Framework for Developing, Deploying, and Managing Network Functions. In Proceedings of the 2016 ACM SIGCOMM Conference (SIGCOMM '16). ACM, New York, NY, USA, 511--524.
9. Marco Canini, Daniele De Cicco, Petr Kuznetsov, Dan Levin, Stefan Schmid, Stefano Vissicchio, et al. 2014. STN: A robust and distributed SDN control plane. Open Networking Summit 490 (2014).
10. Inc. Cavium. 2018. XPliant Ethernet Switch Product Family. (2018). http://www.cavium.com/XPliant-Ethernet-Switch-ProductFamily.html
11. Ed Doe Changhoon Kim, Parag Bhide. 2016. In-band Network Telemetry (INT). http://p4.org/wp-content/uploads/fixed/INT/INT-current-spec.pdf. (2016).
12. Huan Chen and Theophilus Benson. 2017. Switch-visor: Towards Infrastructure-level Virtualization of SDN Switches. In Proceedings of the 2Nd Workshop on Cloud-Assisted Networking (CAN '17). ACM, New York, NY, USA, 25--30.
13. P4 Language Consortium. 2017. P4 software switch (behavioral model) P4-bmv2. (2017). https://github.com/p4lang/behavioral-model
14. P4 Language Consortium. 2017. The reference P4 program switch.p4. (2017). https://github.com/p4lang/switch
15. P4 Language Consortium. 2017. The sample P4 programs. (2017). https://github.com/p4lang/p4c-bm/tree/master/tests/p4_programs
16. Huynh Tu Dang, Daniele Sciascia, Marco Canini, Fernando Pedone, and Robert Soulé. 2015. NetPaxos: Consensus at Network Speed. In Proceedings of the 1st ACM SIGCOMM Symposium on Software Defined Networking Research (SOSR '15). ACM, New York, NY, USA, Article 5, 7 pages.
17. Nate Foster, Rob Harrison, Michael J. Freedman, Christopher Monsanto, Jennifer Rexford, Alec Story, and David Walker. 2011. Frenetic: A Network Programming Language. In Proceedings of the 16th ACM SIGPLAN International Conference on Functional Programming (ICFP '11). ACM, New York, NY, USA, 279--291.
18. Michael R. Garey and David S. Johnson. 1990. Computers and Intractability; A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York, NY, USA.
19. Glen Gibb, George Varghese, Mark Horowitz, and Nick McKeown. 2013. Design Principles for Packet Parsers. In Proceedings of the Ninth ACM/IEEE Symposium on Architectures for Networking and Communications Systems (ANCS '13). IEEE Press, Piscataway, NJ, USA, 13--24. http://dl.acm.org/citation.cfm?id=2537857.2537860
20. Ramesh Govindan, Ina Minei, Mahesh Kallahalla, Bikash Koley, and Amin Vahdat. 2016. Evolve or Die: High-Availability Design Principles Drawn from Googles Network Infrastructure. In Proceedings of the 2016 ACM SIGCOMM Conference (SIGCOMM '16). ACM, New York, NY, USA, 58--72.
21. Arpit Gupta, Laurent Vanbever, Muhammad Shahbaz, Sean P. Donovan, Brandon Schlinker, Nick Feamster, Jennifer Rexford, Scott Shenker, Russ Clark, and Ethan Katz-Bassett. 2014. SDX: A Software Defined Internet Exchange. In Proceedings of the 2014 ACM Conference on SIGCOMM (SIGCOMM '14). ACM, New York, NY, USA, 551--562.
22. David Hancock and Jacobus van der Merwe. 2016. HyPer4: Using P4 to Virtualize the Programmable Data Plane. In Proceedings of the 12th International on Conference on Emerging Networking EXperiments and Technologies (CoNEXT '16). ACM, New York, NY, USA, 35--49.
23. Chengchen Hu, Ji Yang, Hongbo Zhao, and Jiahua Lu. 2014. Design of All Programable Innovation Platform for Software Defined Networking. In Presented as part of the Open Networking Summit 2014 (ONS 2014). USENIX, Santa Clara, CA. https://www.usenix.org/conference/ons2014/technical-sessions/presentation/hu-chengchen
24. Brijnesh J. Jain and Klaus Obermayer. 2011. Extending Bron Kerbosch for Solving the Maximum Weight Clique Problem. CoRR abs/1101.1266 (2011). arXiv:1101.1266 http://arxiv.org/abs/1101.1266
25. Mikel Jimenez and Henry Kwok. 2017. Building Express Backbone: Facebook's new long-haul network. https://code.facebook.com/posts/1782709872057497/building-express-backbone-facebook-s-new-long-haul-network/. (2017).
26. Xin Jin, Jennifer Gossels, Jennifer Rexford, and David Walker. 2015. CoVisor: A Compositional Hypervisor for Software-defined Networks. In Proceedings of the 12th USENIX Conference on Networked Systems Design and Implementation (NSDI'15). USENIX Association, Berkeley, CA, USA, 87--101. http://dl.acm.org/citation.cfm?id=2789770.2789777
27. Lavanya Jose, Lisa Yan, George Varghese, and Nick McKeown. 2015. Compiling Packet Programs to Reconfigurable Switches. In Proceedings of the 12th USENIX Conference on Networked Systems Design and Implementation (NSDI'15). USENIX Association, Berkeley, CA, USA, 103--115. http://dl.acm.org/citation.cfm?id=2789770.2789778
28. Georgios P. Katsikas, Marcel Enguehard, Maciej Kuźniar, Gerald Q. Maguire Jr, and Dejan Kostić. 2016. SNF: synthesizing high performance NFV service chains. PeerJ Computer Science 2 (Nov. 2016), e98.
29. Naga Praveen Katta, Jennifer Rexford, and David Walker. 2013. Incremental Consistent Updates. In Proceedings of the Second ACM SIGCOMM Workshop on Hot Topics in Software Defined Networking (HotSDN '13). ACM, New York, NY, USA, 49--54.
30. Eric Keller and Evan Green. 2008. Virtualizing the Data Plane Through Source Code Merging. In Proceedings of the ACM Workshop on Programmable Routers for Extensible Services of Tomorrow (PRESTO '08). ACM, New York, NY, USA, 9--14.
31. Eric Keller, Minlan Yu, Matthew Caesar, and Jennifer Rexford. 2009. Virtually Eliminating Router Bugs. In Proceedings of the 5th International Conference on Emerging Networking Experiments and Technologies (CoNEXT '09). ACM, New York, NY, USA, 13--24.
32. Bojie Li, Zhenyuan Ruan, Wencong Xiao, Yuanwei Lu, Yongqiang Xiong, Andrew Putnam, Enhong Chen, and Lintao Zhang. 2017. KV-Direct: High-Performance In-Memory Key-Value Store with Programmable NIC. In Proceedings of the 26th Symposium on Operating Systems Principles (SOSP '17). ACM, New York, NY, USA, 137--152.
33. Hongqiang Harry Liu, Xin Wu, Ming Zhang, Lihua Yuan, Roger Wattenhofer, and David Maltz. 2013. zUpdate: Updating Data Center Networks with Zero Loss. In Proceedings of the ACM SIGCOMM 2013 Conference on SIGCOMM (SIGCOMM '13). ACM, New York, NY, USA, 411--422.
34. Shouxi Luo, Hongfang Yu, and Laurent Vanbever. 2017. Swing State: Consistent Updates for Stateful and Programmable Data Planes. In Proceedings of the Symposium on SDNResearch (SOSR '17). ACM, New York, NY, USA, 115--121.
35. Ratul Mahajan and Roger Wattenhofer. 2013. On Consistent Updates in Software Defined Networks. In Proceedings of the Twelfth ACM Workshop on Hot Topics in Networks (HotNets-XII). ACM, New York, NY, USA, Article 20, 7 pages.
36. Rui Miao, Hongyi Zeng, Changhoon Kim, Jeongkeun Lee, and Minlan Yu. 2017. SilkRoad: Making Stateful Layer-4 Load Balancing Fast and Cheap Using Switching ASICs. In Proceedings of the Conference of the ACM Special Interest Group on Data Communication (SIGCOMM '17). ACM, New York, NY, USA, 15--28.
37. Tal Mizrahi, Efi Saat, and Yoram Moses. 2015. Timed Consistent Network Updates. In Proceedings of the 1st ACM SIGCOMM Symposium on Software Defined Networking Research (SOSR '15). ACM, New York, NY, USA, Article 21, 14 pages.
38. Christopher Monsanto, Joshua Reich, Nate Foster, Jennifer Rexford, and David Walker. 2013. Composing Software Defined Networks. In 10th USENIX Symposium on Networked Systems Design and Implementation (NSDI '13). USENIX Association, Lombard, IL, 1--13. https://www.usenix.org/conference/nsdi13/technical-sessions/presentation/monsanto
39. Barefoot Networks. 2016. Barefoot Whitepaper: The World's Fastest and Most Programmable Networks. (2016). https://barefootnetworks.com/resources/worlds-fastest-most-programmable-networks/
40. Bruno Nogueira, Rian G. S. Pinheiro, and Anand Subramanian. 2018. A hybrid iterated local search heuristic for the maximum weight independent set problem. Optimization Letters 12, 3 (01 May 2018).
41. Recep Ozdag. 2012. Intel® Ethernet Switch FM6000 Series-Software Defined Networking. (2012).
42. D. L. Parnas. 1972. On the Criteria to Be Used in Decomposing Systems into Modules. Commun. ACM 15, 12 (Dec. 1972), 1053--1058.
43. Dhrubajyoti Saha, Abhishek Samanta, and Smruti R Sarangi. 2009. Theoretical framework for eliminating redundancy in workflows. In Services Computing, 2009. SCC'09. IEEE International Conference on. IEEE, 41--48.
44. Shuichi Sakai, Mitsunori Togasaki, and Koichi Yamazaki. 2003. A note on greedy algorithms for the maximum weighted independent set problem. Discrete Applied Mathematics 126, 2 (2003), 313 -- 322.
45. Rob Sherwood, Glen Gibb, Kok-Kiong Yap, Guido Appenzeller, Martin Casado, Nick McKeown, and Guru Parulkar. 2010. Can the Production Network Be the Testbed?. In Proceedings of the 9th USENIX Conference on Operating Systems Design and Implementation (OSDI'10). USENIX Association, Berkeley, CA, USA, 365--378. http://dl.acm.org/citation.cfm?id=1924943.1924969
46. Arjun Singh, Joon Ong, Amit Agarwal, Glen Anderson, Ashby Armistead, Roy Bannon, Seb Boving, Gaurav Desai, Bob Felderman, Paulie Germano, Anand Kanagala, Jeff Provost, Jason Simmons, Eiichi Tanda, Jim Wanderer, Urs Hölzle, Stephen Stuart, and Amin Vahdat. 2015. Jupiter Rising: A Decade of Clos Topologies and Centralized Control in Google's Datacenter Network. In Proceedings of the 2015 ACM Conference on Special Interest Groupon Data Communication (SIGCOMM '15). ACM, New York, NY, USA, 183--197.
47. Anirudh Sivaraman, Alvin Cheung, Mihai Budiu, Changhoon Kim, Mohammad Alizadeh, Hari Balakrishnan, George Varghese, Nick McKeown, and Steve Licking. 2016. Packet Transactions: High-Level Programming for Line-Rate Switches. In Proceedings of the 2016 ACM SIGCOMM Conference (SIGCOMM '16). ACM, New York, NY, USA, 15--28.
48. Vibhaalakshmi Sivaraman, Srinivas Narayana, Ori Rottenstreich, S. Muthukrishnan, and Jennifer Rexford. 2017. Heavy-Hitter Detection Entirely in the Data Plane. In Proceedings of the Symposium on SDN Research (SOSR '17). ACM, New York, NY, USA, 164--176.
49. Hardik Soni, Thierry Turletti, and Walid Dabbous. 2018. P4Bricks: Enabling multiprocessing using Linker-based network data plane architecture. (Feb. 2018). https://hal.inria.fr/hal-01632431 working paper.
50. Peng Sun, Ratul Mahajan, Jennifer Rexford, Lihua Yuan, Ming Zhang, and Ahsan Arefin. 2014. A Network-state Management Service. SIGCOMM Comput. Commun. Rev. 44, 4 (Aug. 2014), 563--574.
51. Yu-Wei Eric Sung, Xiaozheng Tie, Starsky H.Y. Wong, and Hongyi Zeng. 2016. Robotron: Top-down Network Management at Facebook Scale. In Proceedings of the 2016 ACM SIGCOMM Conference (SIGCOMM '16). ACM, New York, NY, USA, 426--439.
52. Kaushik Veeraraghavan, Justin Meza, David Chou, Wonho Kim, Sonia Margulis, Scott Michelson, Rajesh Nishtala, Daniel Obenshain, Dmitri Perelman, and Yee Jiun Song. 2016. Kraken: Leveraging Live Traffic Tests to Identify and Resolve Resource Utilization Bottlenecks in Large Scale Web Services. In 12th USENIX Symposium on Operating Systems Design and Implementation (OSDI 16). USENIX Association, Savannah, GA, 635--651. https://www.usenix.org/conference/osdi16/technical-sessions/presentation/veeraraghavan
53. Han Wang, Robert Soulé, Huynh Tu Dang, Ki Suh Lee, Vishal Shrivastav, Nate Foster, and Hakim Weatherspoon. 2017. P4FPGA: A Rapid Prototyping Framework for P4. In Proceedings of the Symposium on SDN Research (SOSR '17). ACM, New York, NY, USA, 122--135.
54. Xilinx. 2014. SDNet. (2014). http://www.xilinx.com/products/design-tools/software-zone/sdnet.html
55. Xilinx. 2017. Ternary Content Addressable Memory (TCAM) Search IP for SDNet SmartCORE IP Product Guide. (2017).
56. Cheng Zhang, Jun Bi, Yu Zhou, Abdul Basit Dogar, and Jianping Wu. 2017. HyperV: A High Performance Hypervisor for Virtualization of the Programmable Data Plane. In 2017 26th International Conference on Computer Communication and Networks (ICCCN). 1--9.
57. Cheng Zhang, Jun Bi, Yu Zhou, Abdul Basit Dogar, and Jianping Wu. 2017. MPVisor: A Modular Programmable Data Plane Hypervisor. In Proceedings of the Symposium on SDN Research (SOSR '17). ACM, New York, NY, USA, 179--180.
58. Ying Zhang, Neda Beheshti, and Ravi Manghirmalani. 2014. NetRevert: Rollback Recovery in SDN. In Proceedings of the Third Workshop on Hot Topics in Software Defined Networking (HotSDN '14). ACM, New York, NY, USA, 231--232.
59. Danyang Zhuo, Qiao Zhang, Xin Yang, and Vincent Liu. 2016. Canaries in the Network. In Proceedings of the 15th ACM Workshop on Hot Topics in Networks (HotNets '16). ACM, New York, NY, USA, 36--42.

Index Terms

• Networks

  • Network services

    • Programmable networks

• Software and its engineering

  • Software creation and management

    • Software verification and validation

      • Software defect analysis

        • Software testing and debugging