Optimal consistent network updates in polynomial time

DOI10.1007/978-3-662-53426-7_9MaRDI QIDQ1660929zbMATH OpenOpenAlexFDO

Authors Pavol Černý, Nate Foster, Nilesh Jagnik, Jedidiah McClurg

Publication date 16 August 2018

Full work available at URL https://arxiv.org/abs/1607.05159

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10)

Abstract: Software-defined networking (SDN) allows operators to control the behavior of a network by programatically managing the forwarding rules installed on switches. However, as is common in distributed systems, it can be difficult to ensure that certain consistency 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. If switches can be updated in some (partial) order which guarantees that per-packet consistency is preserved, we call this order a CONSISTENT ORDER UPDATE. In particular, switches that are incomparable in this order can be updated in parallel. We call a consistent order update OPTIMAL if it allows maximal parallelism. This paper presents a polynomial-time algorithm for finding an optimal consistent order update. This contrasts with other recent results in the literature, which show that for other classes of properties (e.g., loop-freedom and waypoint enforcement), the optimal update problem is NP-complete.

Recommendations

• Incremental network optimization: theory and algorithms
• scientific article; zbMATH DE number 4058842
• Optimal Sampling and Scheduling for Timely Status Updates in Multi-Source Networks
• Deciding the FIFO Stability of Networks in Polynomial Time
• Fully dynamic connectivity oracles under general vertex updates
• Link scheduling in polynomial time
• Approximation algorithms for certain network improvement problems
• Optimal upgrading schemes for effective shortest paths in networks
• Optimal broadcast for fully connected processor-node networks
• On the computational behavior of a polynomial-time network flow algorithm

Cited in

(13)

• Scheduling loop-free network updates: it's good to relax!
• Model checking data flows in concurrent network updates
• Optimal Sampling and Scheduling for Timely Status Updates in Multi-Source Networks
• scientific article; zbMATH DE number 4058842 (Why is no real title available?)
• Decentralizing SDN policies
• Kaki: efficient concurrent update synthesis for SDN
• DyNetKAT: an algebra of dynamic networks
• Concurrent NetCore: from policies to pipelines
• Kaki: concurrent update synthesis for regular policies via Petri games
• Perfect sets of paths in the full graph of SDN switches
• Local checkability, no strings attached: (a)cyclicity, reachability, loop free updates in SDNs
• Optimizing incremental SDN upgrades for load balancing in ISP networks
• Transiently consistent SDN updates: being greedy is hard

This page was built for publication: Optimal consistent network updates in polynomial time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1660929)