On the consistent migration of unsplittable flows: Upper and lower complexity bounds

In consistent flow migration, the task is to change the paths the flows take in the network, but without inducing congestion during the update process. Even though the rise of Software Defined Networks allows for centralized control of path changes, the execution is still performed in an inherently asynchronous system, the switches distributed over the network. To this end, a multitude of scheduling systems have been proposed since the initial papers of Reitblatt et al. (Abstractions for Network Update, SIGCOMM'12) and Hong et al. (SWAN, SIGCOMM'13). While the the complexity of consistently migrating splittable flows is well understood, for the practically more relevant unsplittable flows, few non-heuristic results are known - and upper complexity bounds are missing. We give a dynamic programming algorithm for unsplittable flows, showing the containment in EXPTIME, for both computation time and schedule length. In particular, there are cases where flows must switch between paths back and forth repeatedly: as thus, flow migration is not just an ordering problem. We also study lower bounds and show NP-hardness already for two flows, via reduction from edge-disjoint path problems. Lastly, we also discuss some practical application cases for our dynamic programming algorithm, furthermore showing how it can be extended to min-max load considerations.