Partial flow statistics collection for load-balanced routing in software defined networks

In a software defined network (SDN), it is usually required to frequently collect state/statistics of all the flows, which may result in large overhead on control links. To reduce the flow re-routing overhead, we perform load-balanced routing using the traffic knowledge by carefully taking flow statistics collection. A key challenge for achieving effective almost-optimal load-balanced routing with less overhead relies on the quality of flow statistics collection. To address this challenge, we propose a partial flow statistics collection (PFSC) problem, in which we need to inquire statistics of flows from a subset of switches such that the flow recall ratio on every switch is at least a given value β ∈ (0, 1] while minimizing the number of queried switches. We prove that the PFSC problem is NP-Hard and present an algorithm based on primal-dual with an approximation factor fβ in most situations, where f is the maximum number of switches visited by each flow. To further reduce the overhead, we design an adaptive flow statistics collection mechanism, as a complementary scheme for PFSC, based on link load similarity measurement. We implement our partial flow statistics collection algorithm and a load-balanced routing method on a testbed platform. Our extensive experimental and simulation results show that our methods can reduce the overhead by 56% compared with the previous collection method while preserving a similar routing performance (with peak-load ratio increased by ∼3%).