Computer networks such as the Internet or datacenter networks have become a crucial infrastructure for many criticial services. Accordingly, it is important that such networks preserve correctness criteria, even during transitions from one correct configuration to a new correct configuration. This paper initiates the study of how to simultaneously update, i.e., reroute multiple policies (i.e., flows) in a Software-Defined Network (SDN) in a transiently consistent and efficient manner. In particular, we consider the problem of minimizing the number of controllerswitch interactions, henceforth called “touches”, while preserving fundamental properties, in particular loop-freedom, at any time. Indeed, we empirically show that the number of such interactions affects the resource consumption at the switches. Our main result is a negative one: we rigorously prove that jointly optimizing multiple route updates in a consistent and efficient manner is N P-hard, already for two routing policies. However, we also present an efficient polynomial-time algorithm that, given a fixed number of correct update schedules for independent policies, computes an optimal global schedule with minimal touches. This algorithm applies to any per-flow independent consistency property, not only loop-freedom.

Top