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.
 We study complexity and algorithms for network updates in the setting of Software Defined Networks. Our focus lies on consistent updates for the case of updating forwarding rules in a loop free manner and the migration of flows without congestion. In both cases, we study how the power of two affects the respective problem setting. For loop freedom, we show that scheduling consistent updates for two destinations is NP-hard for a sublinear number of rounds. We also consider the dynamic case, and show that this problem is NP-hard as well via a reduction from Feedback Arc Set. While the power of two increases the complexity for loop freedom, the converse is true when allowing to split flows twice. For the NP-hard problem of consistently migrating unsplittable flows to new routes while respecting waypointing and service chains, we prove that two-splittability allows the problem to be tractable again. Datacenter networks (DCNs) are constantly evolving due to various updates such as switch upgrades and VM migrations. Each update must be carefully planned and executed in order to avoid disrupting many of the mission-critical, interactive applications hosted in DCNs. The key challenge arises from the inherent difficulty in synchronizing the changes to many devices, which may result in unforeseen transient link load spikes or even congestions. We present one primitive, zUpdate, to perform congestion-free network updates under asynchronous switch and traffic matrix changes. We formulate the update problem using a network model and apply our model to a variety of representative update scenarios in DCNs. We develop novel techniques to handle several practical challenges in realizing zUpdate as well as implement the zUpdate prototype on OpenFlow switches and deploy it on a testbed that resembles real DCN topology. Our results, from both real-world experiments and large-scale trace-driven simulations, show that zUpdate can effectively perform congestion-free updates in production DCNs. We present Dionysus, a system for fast, consistent network updates in software-defined networks. Dionysus encodes as a graph the consistency-related dependencies among updates at individual switches, and it then dynamically schedules these updates based on runtime differences in the update speeds of different switches. This dynamic scheduling is the key to its speed; prior update methods are slow because they pre-determine a schedule, which does not adapt to runtime conditions. Testbed experiments and data-driven simulations show that Dionysus improves the median update speed by 53--88 in both wide area and data center networks compared to prior methods.