Joint Route Selection and Update Scheduling for Low-Latency Update in SDNs

Due to flow dynamics, a software defined network (SDN) may need to frequently update its data plane so as to optimize various performance objectives, such as load balancing. Most previous solutions first determine a new route configuration based on the current flow status, and then update the forwarding paths of existing flows. However, due to slow update operations of Ternary Content Addressable Memory-based flow tables, unacceptable update delays may occur, especially in a large or frequently changed network. According to recent studies, most flows have short duration and the workload of the entire network will vary significantly after a long duration. As a result, the new route configuration may be no longer efficient for the workload after the update, if the update duration takes too long. In this paper, we address the real-time route update, which jointly considers the optimization of flow route selection in the control plane and update scheduling in the data plane. We formulate the delay-satisfied route update problem, and prove its NP-hardness. Two algorithms with bounded approximation factors are designed to solve this problem. We implement the proposed methods on our SDN test bed. The experimental results and extensive simulation results show that our method can reduce the route update delay by about 60% compared with previous route update methods while preserving a similar routing performance (with link load ratio increased less than 3%).