FlowStat: Adaptive Flow-Rule Placement for Per-Flow Statistics in SDN

In this paper, we propose an adaptive flow-rule placement scheme, FlowStat, in a software-defined network (SDN) with an aim to provide per-flow statistics to SDN controller while enhancing overall network performance. The proposed scheme consists of three phases-forwarding path selection, flow-rule placement, and rule redistribution. In the first phase, we formulate a max-flow-min-cost optimization problem to determine optimal forwarding paths while considering multi-commodity flows with heterogeneous requirements. In the second phase, an integer linear programming problem is formulated to decide forwarding rules for paths computed in the first phase, so that the total number of exact-match is minimized. As finding optimal solution to the problems is NP-hard, we propose two greedy heuristic approaches to solve the problems in polynomial time. Finally, we propose a rule redistribution scheme on detecting rule congestion at a switch, in order to accommodate new flows in the network. Extensive experimental results show that the proposed scheme, FlowStat, is capable of providing per-flow statistics to the SDN controller while enhancing the network performance compared to existing schemes-ReWiFlow and ExactMatch. In particular, FlowStat is capable of reducing end-to-end delay and QoS violation by 46% and 75% (approx.), respectively, compared with the ReWiFlow and ExactMatch schemes, while providing 85% accurate per-flow statistics to the SDN controller.