Scheduling Relaxed Loop-Free Updates Within Tight Lower Bounds in SDNs

We consider a fundamental update problem of avoiding forwarding loops based on the node-ordering protocol in Software Defined Networks (SDNs). Due to the distributed data plane, forwarding loops may occur during the updates and influence the network performance. The node-ordering protocol can avoid such forwarding loops by controlling the update orders of the switches and does not consume extra flow table space overhead. However, an Ω(n) lower bound on the number of rounds required by any algorithm using this protocol with loop-free constraint has been proved, where n is the number of switches in the network. To accelerate the updates, a weaker notion of loop-freedom - relaxed loop-freedom - has been introduced. Despite that, the theoretical bound of the node-ordering protocol with relaxed loop-free constraint remains unknown yet. In this article, we solve a long-standing open problem: how to derive ω(1) -round lower bound or to show that O(1)-round schedules always exist for the relaxed loop-free update problem. Specifically, we prove that any algorithm needs Ω(log n) rounds to guarantee relaxed loop freedom in the worst case. In addition, we develop a fast relaxed loop-free update algorithm named Savitar that touches the tight lower bound. For any update instance, Savitar can use at most 2⌊log
₂
n⌋ - 1 rounds to schedule relaxed loop-free updates. Extensive experiments on Mininet using a Floodlight controller show that Savitar can significantly decrease the update time, achieve near optimal performance and save over 30% of the rounds compared with the state of the art.