Reducing controller response time with hybrid routing in software defined networks
Abstract In a typical software defined network (SDN), switches report the Packet-In messages of newly arrived flows to the controllers. With more and more flows arriving at a network, the controller load significantly increases, which may lead to long (or even unacceptable) controller response time. Though previous solutions, such as dynamic controller assignment, help to reduce the controller response time, they still lead to various disadvantages, such as an unacceptable controller re-assignment delay, massive communication overhead between controllers, or poor routing performance. To address this issue, our intention is to trade data plane resource for better control plane performance. Specifically, we propose to pre-install wildcard entries for some aggregated flows to reduce controller response time, and perform dynamic routing for new-arrival flows to optimize the network performance. We define the problem of reducing controller response time with minimum data plane resource cost, and prove its NP-hardness. We then present an efficient algorithm based on randomized rounding, and analyze that our algorithm can achieve constant bicriteria approximation under most practical situations. Some practical issues are discussed to enhance our algorithm. We have implemented the proposed algorithm on a real SDN testbed. The experimental results and the extensive simulation results show that our method can reduce the controller response time by 47%, or improve the network throughput by 56% compared with the previous solutions, even with significant traffic dynamics.