Efficient and Consistent Flow Update for Software Defined Networks

Software defined network (SDN) provides flexible and scalable routing by separating control plane and data plane. With centralized control, SDN has been widely used in traffic engineering, link failure recovery, and load balancing. This work considers the flow update problem, where a set of flows need to be migrated or rearranged due to change of network status. During flow update, efficiency and consistency are two main challenges. Efficiency refers to how fast these updates are completed, while consistency refers to prevention of blackholes, loops, and network congestions during updates. This paper proposes a scheme that maintains all these properties. It works in four phases. The first phase partitions flows into shorter routing segments to increase update parallelism. The second phase generates a global dependency graph of these segments to be updated. The third phase conducts actual updates and then adjusts dependency graphs accordingly. The last phase deals with deadlocks, if any, and then loops back to phase three if necessary. Through simulations, we validate that our scheme not only ensures freedom of blackholes, loops, congestions, and deadlocks during flow updates, but is also faster than existing schemes.