Optimal Consistent Network Updates in Polynomial Time | SpringerLink
Skip to main content

Optimal Consistent Network Updates in Polynomial Time

  • Conference paper
  • First Online:
Distributed Computing (DISC 2016)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 9888))

Included in the following conference series:

Abstract

Software-defined networking (SDN) enables controlling the behavior of a network in software, by managing the forwarding rules installed on switches. However, it can be difficult to ensure that certain properties are preserved during periods of reconfiguration. The widely-accepted notion of per-packet consistency requires every packet to be forwarded using the new configuration or the old configuration, but not a mixture of the two. A (partial) order on switches is a consistent order update if updating the switches in that order guarantees per-packet consistency. A consistent order update is optimal if it allows maximal parallelism, where switches may be updated in parallel if they are incomparable in the order. This paper presents a polynomial-time algorithm for computing optimal consistent order updates. This contrasts with other recent results, which show that for other properties (e.g., loop-freedom and waypoint enforcement), the optimal update problem is np-complete.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 5719
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 7149
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

References

  1. Amiri, S.A., Ludwig, A., Marcinkowski, J., Schmid, S.: Transiently consistent SDN updates: being greedy is hard. In: SIROCCO (2016)

    Google Scholar 

  2. Brandt, S., Förster, K.-T., Wattenhofer, R.: On consistent migration of flows in SDNs. In: INFOCOM (2016)

    Google Scholar 

  3. Černý, P., Foster, N., Jagnik, N., McClurg, J.: Updates, optimal consistent network in polynomial time (extended version). arXiv:1607.05159 (2016)

  4. Dudycz, S., Ludwig, A., Schmid, S.: This, can’t touch: consistent network updates for multiple policies. In: DSN (2016)

    Google Scholar 

  5. Förster, K.-T., Wattenhofer, R.: The power of two in consistent network updates: hard loop freedom, easy flow migration. In: ICCCN (2016)

    Google Scholar 

  6. Förster, K.-T., Mahajan, R., Wattenhofer, R.: Consistent updates in software defined networks: on dependencies, loop freedom, and blackholes. In: IFIP (2016)

    Google Scholar 

  7. Jin, X., Liu, H.H., Gandhi, R., Kandula, S., Mahajan, R., Zhang, M., Rexford, J., Wattenhofer, R.: Dynamic scheduling of network updates. In: SIGCOMM (2014)

    Google Scholar 

  8. Liu, H.H., Xin, W., Zhang, M., Yuan, L., Wattenhofer, R., Maltz, D.: zUpdate: updating data center networks with zero loss. In: SIGCOMM (2013)

    Google Scholar 

  9. Ludwig, A., Rost, M., Foucard, D., Schmid. S.: Good network updates for bad packets: waypoint enforcement beyond destination-based routing policies. In: HotNets (2014)

    Google Scholar 

  10. Ludwig, A., Marcinkowski, J., Schmid, S.: Updates, scheduling loop-free network: it’s good to relax! In: PODC (2015)

    Google Scholar 

  11. Ludwig, A., Dudycz, S., Rost, M., Schmid, S.: Transiently secure network updates. In: SIGMETRICS (2016)

    Google Scholar 

  12. Luo, S., Yu, H., Luo, L., Li, L.M.: Arrange your network updates as you wish. In: IFIP (2016)

    Google Scholar 

  13. Mahajan, R., Wattenhofer, R.: On consistent updates in software defined networks. In: HotNets (2013)

    Google Scholar 

  14. Mattos, D.M.F., Duarte, O.C.M.B., Pujolle, G.: Reverse update: a consistent policy update scheme for software defined networking. IEEE Commun. Lett. 20(5), 886–889 (2016)

    Article  Google Scholar 

  15. McClurg, J., Hojjat, H., Černý, P., Foster, N.: Efficient synthesis of network updates. In: PLDI (2015)

    Google Scholar 

  16. Reitblatt, M., Foster, N., Rexford, J., Schlesinger, C., Walker, D.: Abstractions for network update. In: SIGCOMM (2012)

    Google Scholar 

  17. Vissicchio, S., Cittadini, L.: FLIP the (Flow) table: Fast LIghtweight Policy-preserving SDN updates. In: INFOCOM (2016)

    Google Scholar 

  18. Yuan, Y., Ivančić, F., Lumezanu, C., Zhang, S., Gupta, A.: Generating consistent updates for software-defined network configurations. In: HotSDN (2014)

    Google Scholar 

  19. Zhou, W., Jin, D., Croft, J., Caesar, M., Brighten Godfrey, P.: Enforcing customizable consistency properties in software-defined networks. In: NSDI, May 2015

    Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Corresponding author

Correspondence to Nilesh Jagnik .

Editor information

Editors and Affiliations

Rights and permissions

Reprints and permissions

Copyright information

© 2016 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Černý, P., Foster, N., Jagnik, N., McClurg, J. (2016). Optimal Consistent Network Updates in Polynomial Time. In: Gavoille, C., Ilcinkas, D. (eds) Distributed Computing. DISC 2016. Lecture Notes in Computer Science(), vol 9888. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-53426-7_9

Download citation

  • DOI: https://doi.org/10.1007/978-3-662-53426-7_9

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-662-53425-0

  • Online ISBN: 978-3-662-53426-7

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics