LAUSR

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 $\Omega (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 $\omega (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 $\Omega (\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 \lfloor \log _{2}\,\,n \rfloor - 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.