10-27

On the Computational Complexity of some Consistency Properties in SDNs

While Software Defined Networks are controlled centrally by one (logical) controller, the dissemination of updates in the network itself is an inherently asynchronous distributed process. Even though eventual consistency is easy to guarantee, many useful network properties might be violated during the update process. 

In this talk, we are going to look at the computational complexity of guaranteeing consistent updates for loop freedom and bandwidth limits. The best update schedules for loop freedom are hard to approximate, and the migration of unsplittable flows without congestion is not easy either. A different picture unfolds for splittable flows as used in, e.g., SWAN: It is possible to decide quickly if a consistent migration is possible, but the migration time can be unbounded. To this end, we show how any consistent migration can be performed in only a linear number of steps if restricted to one (logical) destination.

 

Klaus-Tycho Foerster is a PhD candidate in the Computer Engineering and Networks Laboratory at ETH Zurich, advised by Roger Wattenhofer. Prior to joining ETH as a research assistant, he earned his master degrees in mathematics and computer science, both at the Braunschweig University of Technology. Klaus' research focus lies in distributed computing and graph algorithms, and since recently, Software Defined Networking: Funded by Microsoft Research, he is studying the complexity of consistent updates in SDNs.