research-article

Open access

Efficient and Safe Network Updates with Suffix Causal Consistency

Authors:

Theophilus A. Benson,

Michael K. ReiterAuthors Info & Claims

EuroSys '19: Proceedings of the Fourteenth EuroSys Conference 2019

Article No.: 23, Pages 1 - 15

https://doi.org/10.1145/3302424.3303965

Published: 25 March 2019 Publication History

Abstract

Though centrally managed by a controller, a software-defined network (SDN) can still encounter routing inconsistencies among its switches due to the non-atomic updates to their forwarding tables. In this paper, we propose a new method to rectify these inconsistencies that is inspired by causal consistency, a consistency model for shared-memory systems. Applied to SDNs, causal consistency would imply that once a packet is matched to ("reads") a forwarding rule in a switch, it can be matched in downstream switches only to rules that are equally or more up-to-date. We propose and analyze a relaxed but functionally equivalent version of this property called suffix causal consistency (SCC) and evaluate an implementation of SCC in Open vSwitch and P4 switches, in conjunction with the Ryu and P4Runtime controllers. Our results show that SCC provides greater efficiency than competing consistent-update alternatives while offering consistency that is strong enough to ensure high-level routing properties (black-hole freedom, bounded looping, etc.).

References

[1]

M. Ahamad, G. Neiger, J. E. Burns, P. Kohli, and P. W. Hutto. 1995. Causal Memory: Definitions, Implementation and Programming. Dist. Comp. (1995).

Digital Library

[2]

M. Al-Fares, A. Loukissas, and A. Vahdat. 2008. A Scalable, Commodity Data Center Network Architecture. In ACM SIGCOMM. 63--74.

Digital Library

[3]

B. Anwer, T. Benson, N. Feamster, and D. Levin. 2015. Programming Slick Network Functions. In 1st ACM SOSR. 1--13.

Digital Library

[4]

P. Bailis, A. Ghodsi, J. Hellerstein, and I. Stoica. 2013. Bolt-on Causal Consistency. In ACM SIGMOD/PODS. 761--772.

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. 2014. P4: Programming Protocol-independent Packet Processors. ACM SIGCOMM Comp. Comm. Rev. (July 2014), 87--95.

Digital Library

[6]

H. Chen and T. Benson. 2017. Hermes: Providing Tight Control over High-Performance SDN Switches. In 13th ACM CoNEXT. 283--295.

Digital Library

[7]

C. J. Fidge. 1988. Timestamps in Message-Passing Systems that Preserve the Partial Ordering. In 11th Australian Computer Science Conference. 56--66.

[8]

K. Foerster, A. Ludwig, J. Marcinkowski, and S. Schmid. 2018. Loop-Free Route Updates for Software-Defined Networks. IEEE/ACM Trans. Netw. 26, 1 (Feb. 2018), 328--341.

Digital Library

[9]

A. Gember-Jacobson, R. Viswanathan, C. Prakash, R. Grandl, J. Khalid, S. Das, and A. Akella. 2014. OpenNF: Enabling Innovation in Network Function Control. In ACM SIGCOMM. 163--174.

Digital Library

[10]

S. Ghorbani and P. Godfrey. 2017. COCONUT: Seamless Scale-out of Network Elements. In 12th ACM EuroSys.

Digital Library

[11]

J. Han, H.Jong Hun, P. Mundkur, R. Prashanth, C. Rotsos, G. Antichi, N. Dave, A. Moore, and P. Neumann. 2015. Blueswitch: Enabling Provably Consistent Configuration of Network Switches. In 11th ACNS.

Digital Library

[12]

C. Hong, S. Kandula, R. Mahajan, M. Zhang, V. Gill, M. Nanduri, and R. Wattenhofer. 2013. Achieving High Utilization with Software-driven WAN. In ACM SIGCOMM. 15--26.

Digital Library

[13]

D. Huang, K. Yocum, and A. Snoeren. 2013. High-Fidelity Switch Models for Software-defined Network Emulation. In ACM HotSDN.

Digital Library

[14]

X. Jin, H. Liu, R. Gandhi, S. Kandula, R. Mahajan, M. Zhang, J. Rexford, and R. Wattenhofer. 2014. Dynamic Scheduling of Network Updates. In ACM SIGCOMM. 539--550.

Digital Library

[15]

N. Kang, Z. Liu, J. Rexford, and D. Walker. 2013. Optimizing the "One Big Switch" Abstraction in Software-defined Networks. In 9th ACM CoNEXT.

Digital Library

[16]

N. Katta, J. Rexford, and D. Walker. 2013. Incremental Consistent Updates. In 2nd ACM HotSDN.

Digital Library

[17]

F. Klaus-Tycho, M. Ratul, and W. Roger. 2016. Consistent Updates in Software Defined Networks: On Dependencies, Loop Freedom, and Blackholes. In IFIP Netw.

[18]

L. Lamport. 1978. Time, Clocks, and the Ordering of Events in a Distributed System. CACM 21, 7 (July 1978), 558--565.

Digital Library

[19]

A. Lazaris, D. Tahara, X. Huang, E. Li, A. Voellmy, Y. R. Yang, and M. Yu. 2014. Tango: Simplifying SDN Control with Automatic Switch Property Inference, Abstraction, and Optimization. In ACM CoNEXT.

Digital Library

[20]

H. Liu, X. Wu, M. Zhang, L. Yuan, R. Wattenhofer, and D. Maltz. 2013. zUpdate: Updating Data Center Networks with Zero Loss. In ACM SIGCOMM. 411--422.

Digital Library

[21]

W. Lloyd, M. Freedman, M. Kaminsky, and D. Andersen. 2011. Don't Settle for Eventual: Scalable Causal Consistency for Wide-area Storage with COPS. In 23rd ACM SOSP. 401--416.

Digital Library

[22]

W. Lloyd, M. Freedman, M. Kaminsky, and D. Andersen. 2013. Stronger Semantics for Low-latency Geo-replicated Storage. In 10th USENIX NSDI. 313--328.

Digital Library

[23]

A. Ludwig, S. Dudycz, M. Rost, and S. Schmid. 2016. Transiently Secure Network Updates. In ACM SIGMETRICS. 273--284.

Digital Library

[24]

A. Ludwig, M. Rost, D. Foucard, and S. Schmid. 2014. Good Network Updates for Bad Packets: Waypoint Enforcement Beyond Destination-Based Routing Policies. In 13th ACM HotNets.

Digital Library

[25]

R. Mahajan and R. Wattenhofer. 2013. On Consistent Updates in Software Defined Networks. In 12th ACM HotNets. 1--7.

Digital Library

[26]

F. Mattern. 1988. Virtual Time and Global States of Distributed Systems. In Workshop on Parallel and Distributed Algorithsm. 215--226.

[27]

J. McClurg, H. Hojjat, P. Černý, and N. Foster. 2015. Efficient Synthesis of Network Updates. In 36th ACM PLDI. 196--207.

Digital Library

[28]

T. Mizrahi, O. Rottenstreich, and Y. Moses. 2017. TimeFlip: Using Timestamp-Based TCAM Ranges to Accurately Schedule Network Updates. IEEE/ACM Trans. Netw. 25, 2 (April 2017), 849--863.

Digital Library

[29]

T. Mizrahi, E. Saat, and Y. Moses. 2015. Timed Consistent Network Updates. In 1st ACM SOSR.

Digital Library

[30]

L. Moura and N. Bjørner. 2008. Z3: An Efficient SMT Solver. In 14th TACAS/ETAPS. 337--340.

Digital Library

[31]

T. Nguyen, M. Chiesa, and M. Canini. 2017. Decentralized Consistent Updates in SDN. In ACM SOSR.

Digital Library

[32]

Open Networking Foundation. 2015. OpenFlow Switch Specification, Version 1.5.1. (26 March 2015).

[33]

P. Pereíni, M. Kuzniar, M. Canini, and D. Kostić. 2014. ESPRES: Transparent SDN Update Scheduling. In ACM HotSDN.

Digital Library

[34]

Z. Qazi, C. Tu, L. Chiang, R. Miao, V. Sekar, and M. Yu. 2013. SIMPLEfying Middlebox Policy Enforcement Using SDN. In ACM SIGCOMM. 27--38.

Digital Library

[35]

M. Reitblatt, N. Foster, J. Rexford, C. Schlesinger, and D. Walker. 2012. Abstractions for Network Update. In ACM SIGCOMM.

Digital Library

[36]

V. Stefano and C. Luca. 2016. FLIP the (Flow) table: Fast lightweight policy-preserving SDN updates. In 35th IEEE INFOCOM.

[37]

K. Zarifis, R. Miao, M. Calder, E. Katz-Bassett, M. Yu, and J. Padhye. 2014. DIBS: Justin-time Congestion Mitigation for Data Centers. In 9th ACM EuroSys. 6:1--6:14.

Digital Library

[38]

W. Zhou, D. Jin, J. Croft, M. Caesar, and P. B. Godfrey. 2015. Enforcing Customizable Consistency Properties in Software-defined Networks. In 12th USENIX NSDI. 73--85.

Digital Library

Cited By

Camilleri CVella JNezval V(2024)Horizontally Scalable Implementation of a Distributed DBMS Delivering Causal Consistency via the Actor ModelElectronics10.3390/electronics1317336713:17(3367)Online publication date: 24-Aug-2024
https://doi.org/10.3390/electronics13173367
Dogar AUllah SZhang YAlasmary HWaqas MChen S(2024)Resilient TCP Variant Enabling Smooth Network Updates for Software-Defined Data Center NetworksTsinghua Science and Technology10.26599/TST.2024.901001029:5(1615-1632)Online publication date: Oct-2024
https://doi.org/10.26599/TST.2024.9010010
Weintraub BKim JTao RNita-Rotaru COkhravi HTian DUjcich BLuo BLiao XXu JKirda ELie D(2024)Exploiting Temporal Vulnerabilities for Unauthorized Access in Intent-based NetworkingProceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security10.1145/3658644.3670301(3630-3644)Online publication date: 2-Dec-2024
https://dl.acm.org/doi/10.1145/3658644.3670301
Show More Cited By

Index Terms

Efficient and Safe Network Updates with Suffix Causal Consistency
1. Networks

Recommendations

Causal consistency: beyond memory
PPoPP '16

In distributed systems where strong consistency is costly when not impossible, causal consistency provides a valuable abstraction to represent program executions as partial orders. In addition to the sequential program order of each computing entity, ...
Causal consistency: beyond memory
PPoPP '16: Proceedings of the 21st ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming

In distributed systems where strong consistency is costly when not impossible, causal consistency provides a valuable abstraction to represent program executions as partial orders. In addition to the sequential program order of each computing entity, ...
Event-driven network programming
PLDI '16

Software-defined networking (SDN) programs must simultaneously describe static forwarding behavior and dynamic updates in response to events. Event-driven updates are critical to get right, but difficult to implement correctly due to the high degree of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

EuroSys '19: Proceedings of the Fourteenth EuroSys Conference 2019

March 2019

714 pages

ISBN:9781450362818

DOI:10.1145/3302424

Copyright © 2019 Owner/Author.

This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike International 4.0 License.

Sponsors

SIGOPS: ACM Special Interest Group on Operating Systems

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 25 March 2019

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed limited

Funding Sources

National Science Foundation

Conference

EuroSys '19

Sponsor:

SIGOPS

EuroSys '19: Fourteenth EuroSys Conference 2019

March 25 - 28, 2019

Dresden, Germany

Acceptance Rates

Overall Acceptance Rate 241 of 1,308 submissions, 18%

Upcoming Conference

EuroSys '25

Sponsor:
sigops

Twentieth European Conference on Computer Systems

March 30 - April 3, 2025

Rotterdam , Netherlands

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
614
Total Downloads

Downloads (Last 12 months)83
Downloads (Last 6 weeks)7

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Camilleri CVella JNezval V(2024)Horizontally Scalable Implementation of a Distributed DBMS Delivering Causal Consistency via the Actor ModelElectronics10.3390/electronics1317336713:17(3367)Online publication date: 24-Aug-2024
https://doi.org/10.3390/electronics13173367
Dogar AUllah SZhang YAlasmary HWaqas MChen S(2024)Resilient TCP Variant Enabling Smooth Network Updates for Software-Defined Data Center NetworksTsinghua Science and Technology10.26599/TST.2024.901001029:5(1615-1632)Online publication date: Oct-2024
https://doi.org/10.26599/TST.2024.9010010
Weintraub BKim JTao RNita-Rotaru COkhravi HTian DUjcich BLuo BLiao XXu JKirda ELie D(2024)Exploiting Temporal Vulnerabilities for Unauthorized Access in Intent-based NetworkingProceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security10.1145/3658644.3670301(3630-3644)Online publication date: 2-Dec-2024
https://dl.acm.org/doi/10.1145/3658644.3670301
Liu SReiter MBenson T(2023)Nimble: Fast and Safe Migration of Network FunctionsIEEE INFOCOM 2023 - IEEE Conference on Computer Communications10.1109/INFOCOM53939.2023.10228977(1-10)Online publication date: 17-May-2023
https://doi.org/10.1109/INFOCOM53939.2023.10228977
Gomez-Pilar JGutiérrez-Tobal GHornero R(2022)Covering the Gap Between Sleep and Cognition – Mechanisms and Clinical ExamplesAdvances in the Diagnosis and Treatment of Sleep Apnea10.1007/978-3-031-06413-5_2(17-29)Online publication date: 11-Oct-2022
https://doi.org/10.1007/978-3-031-06413-5_2
Dogar AZhang Y(2021)NUFTCP: Towards Smooth Network Updates in Software-Defined Datacenter Networks2021 17th International Conference on Network and Service Management (CNSM)10.23919/CNSM52442.2021.9615582(365-369)Online publication date: 25-Oct-2021
https://doi.org/10.23919/CNSM52442.2021.9615582
Zhou ZHe MKellerer WBlenk AFoerster KCarle GOtt J(2021)P4UpdateProceedings of the 17th International Conference on emerging Networking EXperiments and Technologies10.1145/3485983.3494845(175-190)Online publication date: 2-Dec-2021
https://dl.acm.org/doi/10.1145/3485983.3494845
Guidara APomares Hernández SRodríguez Henríquez LHadj Kacem HHadj Kacem A(2020)Towards Causal Consistent Updates in Software-Defined NetworksApplied Sciences10.3390/app1006208110:6(2081)Online publication date: 19-Mar-2020
https://doi.org/10.3390/app10062081
Zhou YXi ZZhang DWang YWang JXu MWu JMohaisen AZhang Z(2019)HyperTesterProceedings of the 15th International Conference on Emerging Networking Experiments And Technologies10.1145/3359989.3365406(30-43)Online publication date: 3-Dec-2019
https://dl.acm.org/doi/10.1145/3359989.3365406

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

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

Media

Figures

Other

Tables

View Table of Contents