Rule Minimization for Traffic Evolution in Software-Defined Networks

Abstract

This letter addresses the problem of traffic evolution in software defined networks (SDNs). SDNs achieve optimal flow distribution by using flow optimization models, but as traffic evolves, the underlying optimization model changes. Applying the online model frequently can result in a flood of control messages to switches for deleting, modifying, or installing new rules, and the resulting traffic re-routing can cause transient loops and synchronization issues. In this letter, we present minimum rule application (MIRA), a mixed integer linear programming-based model, which re-calculates flow distribution dynamically while minimizing the number of rule installations. Since the proposed model is NP-hard, we also propose an efficient heuristic-based greedy algorithm. In addition, we also propose a rule-aggregation (RA) optimization for minimizing rule installation (MIRA-RA). Finally, we propose a multi-objective optimization model, which jointly minimizes the conflicting objectives of rule installation and link utilization (PARETO) and use the ϵ-constraint method to achieve pareto-optimality. We implement MIRA, MIRA-RA, Greedy, PARETO, and an existing solution in the area and present numerical results.