Traffic evolution in Software Defined Networks

Software Defined Networking (SDN) offers unprecedented traffic engineering possibilities due to optimal centralized decision making. However, network traffic evolves over time and changes the underlying optimization problem. Frequent application of the model to reflect traffic evolution causes flooding of control messages, traffic re-routing and synchronization problems. This paper addresses the problem of graceful traffic evolution in SDNs (Software Defined Networks) minimizing rule installations and modifications, optimizing the global objectives of minimization of Maximum Link Utilization (MLU) and minimization of the Maximum Switch Table Space Utilization (MSTU). The problem is formulated as multi-objective optimization using Mixed Integer Linear Programming (MILP). Proof of NP-Hardness is provided. Then, we re-formulate the problem as a single-objective problem and propose two greedy algorithms to solve the single-objective problem, namely MIRA-Im and MIRA-Im with Conflict Detection, and experiments are performed to show the effectiveness of the algorithms in comparison to previous state of the art proposals. Simulation results show significant improvements of MIRA-Im with Conflict Detection, especially in terms of number of installed rules (with a gain till 80% with the highest number of flows) and flow table space utilization (with a gain till 55% with the highest number of flows), compared to MIRA-Im and other algorithms available in the literature, while the other metrics are essentially stable.