Scheduling Congestion-Free Updates of Multiple Flows with Chronicle in Timed SDNs

摘要

The advent of more accurate synchronization in Software-Defined Networks (SDNs) in general and the notion of timed updates in particular, enables operators to fully exploit the potential of the more fine-grained and adaptive traffic engineering, by avoiding disruptions and inconsistencies during the update. However, little is known today about how to schedule the update of multiple flows in such timed SDNs: As flows compete for limited resources, implementing a congestion-free update remains algorithmically challenging, even in timed SDNs. This paper initiates the study of the fundamental problem of how to reroute the update of multiple network flows in a synchronized SDN in a congestion-free manner. We show that that the problem is NP-hard already for flows of unit size and network links with unit delay. Our main contribution is a first solution for this problem: Chronicle. Our approach is based on a time-extended network construction and resource dependency graph, which is implemented by Openflow 1.5 using the scheduled bundles feature. Evaluation results show that Chronicle can reduce the makespan by 63% and reduce the number of changed rules by 50% compared to state-of-the-art.