research-article

Normal forms for match-action programs

Authors:

Felicián Németh,

Gábor RétváriAuthors Info & Claims

CoNEXT '19: Proceedings of the 15th International Conference on Emerging Networking Experiments And Technologies

Pages 44 - 50

https://doi.org/10.1145/3359989.3365417

Published: 03 December 2019 Publication History

Abstract

Packet processing programs may have multiple semantically equivalent representations in terms of the match-action abstraction exposed by the underlying data plane. Some representations may encode the entire packet processing program into one large table allowing packets to be matched in a single lookup, while others may encode the same functionality decomposed into a pipeline of smaller match-action tables, maximizing modularity at the cost of increased lookup latency. In this paper, we provide the first systematic study of match-action program representations in order to assist network programmers in navigating this vast design space. Borrowing from relational database and formal language theory, we define a framework for the equivalent transformation of match-action programs to obtain certain irredundant representations that we call "normal forms". We find that normalization generally improves the capacity of the control plane to program the data-plane and to observe its state, at the same time having negligible, or positive, performance impact.

References

[1]

C. J. Anderson, N. Foster, A. Guha, J.-B. Jeannin, D. Kozen, C. Schlesinger, and D. Walker. NetKAT: Semantic foundations for networks. Technical report, Cornell University, 2013. available online: https://ecommons.cornell.edu/bitstream/handle/1813/34445/netkat-tech-report.pdf.

[2]

T. Barbette, C. Soldani, and L. Mathy. Fast userspace packet processing. In Proceedings of the Eleventh ACM/IEEE Symposium on Architectures for Networking and Communications Systems, ANCS '15, pages 5--16, Washington, DC, USA, 2015. IEEE Computer Society.

[3]

R. Bifulco and G. Rétvári. A survey on the programmable data plane: Abstractions, architectures, and open problems. In IEEE HPSR, 2018.

[4]

O. Bonaventure, C. Filsfils, and P. François. Achieving Sub-50 Milliseconds Recovery Upon BGP Peering Link Failures. In Proceedings of the 2005 ACM Conference on Emerging Network Experiment and Technology, CoNEXT 2005, Toulouse, France, October 24--27, 2005, pages 31--42, 2005.

Digital Library

[5]

P. Bosshart, D. Daly, G. Gibb, M. Izzard, N. McKeown, J. Rexford, C. Schlesinger, D. Talayco, A. Vahdat, G. Varghese, and D. Walker. P4: Programming protocol-independent packet processors. SIGCOMM Comput. Commun. Rev., 44(3):87--95, 2014.

Digital Library

[6]

P. Bosshart, G. Gibb, H. Kim, G. Varghese, N. McKeown, M. Izzard, F. A. Mujica, and M. Horowitz. Forwarding metamorphosis: Fast programmable match-action processing in hardware for SDN. In ACM SIGCOMM, 2013.

Digital Library

[7]

A. Bremler-Barr, Y. Harchol, and D. Hay. OpenBox: A software-defined framework for developing, deploying, and managing network functions. In SIGCOMM, 2016.

Digital Library

[8]

A. Elmokashfi and A. Dhamdhere. Revisiting BGP churn growth. SIGCOMM Comput. Commun. Rev., 44(1):5--12, Dec. 2013.

Digital Library

[9]

S. Feldman. Rocker: switchdev prototyping vehicle. Proceedings of Netdev 0.1, 2015.

[10]

A. Gupta, R. MacDavid, R. Birkner, M. Canini, N. Feamster, J. Rexford, and L. Vanbever. An industrial-scale software defined Internet exchange point. In USENIX NSDI, 2016.

Digital Library

[11]

A. Gupta, M. Shahbaz, L. Vanbever, H. Kim, R. Clark, N. Feamster, J. Rexford, and S. Shenker. SDX: a software defined Internet Exchange. In SIGCOMM, pages 551--562, 2014.

[12]

J. Han, P. Mundkur, C. Rotsos, G. Antichi, N. Dave, A. Moore, and P. Neumann. Blueswitch: Enabling provably consistent configuration of network switches. In Architectures for Networking and Communications Systems (ANCS), 2015 ACM/IEEE Symposium on, pages 17--27, 5 2015.

Digital Library

[13]

S. Han, K. Jang, A. Panda, S. Palkar, D. Han, and S. Ratnasamy. SoftNIC: a software NIC to augment hardware. available online: http://www.eecs.berkeley.edu/Pubs/TechRpts/2015/EECS-2015-155.pdf.

[14]

I. T. Hawryszkiewycz. Database Analysis and Design. Macmillan Press Ltd., 1991.

[15]

T. Holterbach, S. Vissicchio, A. Dainotti, and L. Vanbever. SWIFT: Predictive Fast Reroute. In SIGCOMM, 2017.

Digital Library

[16]

L. Jose, L. Yan, G. Varghese, and N. McKeown. Compiling packet programs to reconfigurable switches. In USENIX NSDI, pages 103--115, 2015.

Digital Library

[17]

K. Kogan, S. I. Nikolenko, O. Rottenstreich, W. Culhane, and P. Eugster. SAX-PAC (scalable and expressive packet classification). In ACM SIGCOMM, 2014.

Digital Library

[18]

M. Kuźniar, P. Perešíni, and D. Kostić. What you need to know about SDN flow tables. In PAM, pages 347--359, 2015.

[19]

The Lagopus switch project. http://www.lagopus.org.

[20]

T. Lévai, G. Pongrácz, P. Megyesi, P. Vörös, S. Laki, F. Németh, and G. Rétvári. The price for programmability in the software data plane: The vendor perspective. IEEE Journal on Selected Areas in Communications, 36(12):2621--2630, 2018.

Digital Library

[21]

A. X. Liu, C. R. Meiners, and E. Torng. TCAM Razor: a systematic approach towards minimizing packet classifiers in TCAMs. IEEE/ACM Transactions on Networking, 18(2):490--500, 2010.

Digital Library

[22]

R. MacDavid, R. Birkner, O. Rottenstreich, A. Gupta, N. Feamster, and J. Rexford. Concise encoding of flow attributes in SDN switches. In ACM SOSR, pages 48--60, 2017.

Digital Library

[23]

C. R. Meiners, A. X. Liu, E. Torng, and J. Patel. Split: Optimizing space, power, and throughput for TCAM-based classification. In ACM/IEEE ANCS, pages 200--210, 2011.

Digital Library

[24]

L. Molnár, G. Pongrácz, G. Enyedi, Z. L. Kis, L. Csikor, F. Juhász, A. Kőrösi, and G. Rétvári. Dataplane specialization for high performance OpenFlow software switching. In ACM SIGCOMM, 2016.

Digital Library

[25]

NoviFlow. NoviSwitch 2128 - High Performance OpenFlow Switch, 2018. https://noviflow.com/wp-content/uploads/NoviSwitch-2128-Datasheet.pdf.

[26]

The Open Networking Foundation. OpenFlow Switch Specifications v.1.4.0, 2013.

[27]

A. Panda, S. Han, K. Jang, M. Walls, S. Ratnasamy, and S. Shenker. NetBricks: taking the V out of NFV. In USENIX OSDI, pages 203--216, 2016.

[28]

B. Pfaff, J. Pettit, T. Koponen, E. Jackson, A. Zhou, J. Rajahalme, J. Gross, A. Wang, J. Stringer, P. Shelar, K. Amidon, and M. Casado. The design and implementation of Open vSwitch. In NSDI, pages 117--130, 2015.

Digital Library

[29]

J. Reich, C. Monsanto, N. Foster, J. Rexford, and D. Walker. Modular SDN programming with Pyretic. USENIX ;login, 38(5), 2013.

[30]

R. Rosen. Linux kernel networking: Implementation and theory. Apress, 2014.

[31]

C. Schlesinger, M. Greenberg, and D. Walker. Concurrent NetCore: From policies to pipelines. In ACM ICFP, pages 11--24, 2014.

Digital Library

[32]

A. Starovoitov and T. Herbert. eXpress Data Path, 2016. available online: https://github.com/iovisor/bpf-docs/blob/master/Express_Data_Path.pdf.

[33]

Tipsy: Telco pipeline benchmarking system. https://github.com/hsnlab/tipsy.

Cited By

Caiazzi TScazzariello MChiesa M(2023)Millions of Low-latency State Insertions on ASIC SwitchesProceedings of the ACM on Networking10.1145/36291441:CoNEXT3(1-23)Online publication date: 28-Nov-2023
https://dl.acm.org/doi/10.1145/3629144
Jing LWang JChen X(2022)MSSA: Constant Time State Search through Multi-Scope State AreaApplied Sciences10.3390/app1202055912:2(559)Online publication date: 6-Jan-2022
https://doi.org/10.3390/app12020559
Barbette TWu EKostic DMaguire GPapadimitratos PChiesa M(2022)Cheetah: A High-Speed Programmable Load-Balancer Framework With Guaranteed Per-Connection-ConsistencyIEEE/ACM Transactions on Networking10.1109/TNET.2021.311337030:1(354-367)Online publication date: Feb-2022
https://doi.org/10.1109/TNET.2021.3113370
Show More Cited By

Index Terms

Normal forms for match-action programs
1. Networks
  1. Network performance evaluation
  2. Network services
    1. Programmable networks
2. Theory of computation
  1. Theory and algorithms for application domains
    1. Database theory

Recommendations

High speed packet forwarding compiled from protocol independent data plane specifications
SIGCOMM '16: Proceedings of the 2016 ACM SIGCOMM Conference

P4 is a high level language for programming network switches that allows for great flexibility in the description of packet structure and processing, independent of the specifics of the underlying hardware. In this demo, we present our prototype P4 ...
P4-Compatible High-Level Synthesis of Low Latency 100 Gb/s Streaming Packet Parsers in FPGAs
FPGA '18: Proceedings of the 2018 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays

Packet parsing is a key step in SDN-aware devices. Packet parsers in SDN networks need to be both reconfigurable and fast, to support the evolving network protocols and the increasing multi-gigabit data rates. The combination of packet processing ...
Introducing P4TC - A P4 implementation on Linux Kernel using Traffic Control
EuroP4 '23: Proceedings of the 6th on European P4 Workshop

The networking industry is at an inflection point with ever increasing network link capacities coupled with the presence of programmable hardware ASICs. These set of circumstances call out for a robust approach to hardware and software co-existence for ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

CoNEXT '19: Proceedings of the 15th International Conference on Emerging Networking Experiments And Technologies

December 2019

395 pages

ISBN:9781450369985

DOI:10.1145/3359989

General Chairs:
Aziz Mohaisen
University of Central Florida
,
Zhi-Li Zhang
University of Minnesota

Copyright © 2019 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGCOMM: ACM Special Interest Group on Data Communication

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 03 December 2019

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

National Research, Development and Innovation Fund of Hungary

Conference

CoNEXT '19

Sponsor:

SIGCOMM

CoNEXT '19: The 15th International Conference on emerging Networking EXperiments and Technologies

December 9 - 12, 2019

Florida, Orlando

Acceptance Rates

Overall Acceptance Rate 198 of 789 submissions, 25%

Upcoming Conference

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
332
Total Downloads

Downloads (Last 12 months)17
Downloads (Last 6 weeks)0

Reflects downloads up to 24 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Caiazzi TScazzariello MChiesa M(2023)Millions of Low-latency State Insertions on ASIC SwitchesProceedings of the ACM on Networking10.1145/36291441:CoNEXT3(1-23)Online publication date: 28-Nov-2023
https://dl.acm.org/doi/10.1145/3629144
Jing LWang JChen X(2022)MSSA: Constant Time State Search through Multi-Scope State AreaApplied Sciences10.3390/app1202055912:2(559)Online publication date: 6-Jan-2022
https://doi.org/10.3390/app12020559
Barbette TWu EKostic DMaguire GPapadimitratos PChiesa M(2022)Cheetah: A High-Speed Programmable Load-Balancer Framework With Guaranteed Per-Connection-ConsistencyIEEE/ACM Transactions on Networking10.1109/TNET.2021.311337030:1(354-367)Online publication date: Feb-2022
https://doi.org/10.1109/TNET.2021.3113370
Wu ZZhang YFeng WZhang Z(2022)NFlow and MVT Abstractions for NFV ScalingIEEE INFOCOM 2022 - IEEE Conference on Computer Communications10.1109/INFOCOM48880.2022.9796764(180-189)Online publication date: 2-May-2022
https://doi.org/10.1109/INFOCOM48880.2022.9796764
Leet CSoule RYang YZhang Y(2021)Flow Algebra: Towards an Efficient, Unifying Framework for Network Management TasksIEEE INFOCOM 2021 - IEEE Conference on Computer Communications10.1109/INFOCOM42981.2021.9488857(1-10)Online publication date: 10-May-2021
https://doi.org/10.1109/INFOCOM42981.2021.9488857
Barbette TTang CYao HKostić DMaguire GPapadimitratos PChiesa MBhagwan RPorter G(2020)A high-speed load-balancer design with guaranteed per-connection-consistencyProceedings of the 17th Usenix Conference on Networked Systems Design and Implementation10.5555/3388242.3388291(667-684)Online publication date: 25-Feb-2020
https://dl.acm.org/doi/10.5555/3388242.3388291
Sanger RLuckie MNelson R(2020)Towards Transforming OpenFlow Rulesets to Fit Fixed-Function PipelinesProceedings of the Symposium on SDN Research10.1145/3373360.3380844(123-134)Online publication date: 3-Mar-2020
https://dl.acm.org/doi/10.1145/3373360.3380844

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents