Chronus: Consistent Data Plane Updates in Timed SDNs

Software-Defined Networks (SDNs) introduce interesting new opportunitiesin how network routes can be defined, verified, and changed over time. Yet despite the logically-centralized perspective offered,an SDN still needs to be considered a distributed system:rule updates communicated from the controller to the individualswitches traverse an asynchronous networkand may arrive out-of-order, and hence lead to (temporary or permanent) inconsistencies. Accordingly, the consistent network update problemhas recently received much attention. Motivated by the advent of tightly synchronized SDNs,we in this paper initiate the study of algorithms for consistent networkupdatesin 'timed SDNs'-SDNs in which individual node updates can bescheduled at specific times. This paper presentsChronus, which isbased on provablycongestion-and loop-free updatescheduling algorithms, andavoids the flow table spaceheadroom required by existing two-phase updateapproaches. We formulate the Minimum Update Time Problem (MUTP) asan optimization program. We propose a tree algorithm to check the feasibility and a greedy algorithmto find a update sequence in polynomial time. Extensive experiments on Mininet and numericalsimulations show that Chronus can substantially reduce transient congestion by 75\% and save over 60\%of the rules compared to the state of the art.