Flow Update Model Based on Probability Distribution of Migration Time in Software-Defined Networks

In a software-defined network (SDN), routes of packet flows need to be updated in situations such as maintenance and router replacement. Each flow is migrated from its old path to new path. The SDN update has an asynchronous nature; the time when the switches process commands by the controller varies depending on flows. Therefore, it is difficult to control an order of flow migrations, and packets can be lost by congestion. Existing models divide the time axis into rounds and assign migrations to these rounds. However, congestion caused by multiple migrations in the same round is uncontrollable. Based on the probability distribution of time required for each migration, congestion can occur. This paper proposes a flow update model which minimizes the expected amount of excessive traffic by shifting the probability distributions. The time axis is divided into time slots which are fine-grained than rounds, so that each probability distribution is shifted. The proposed model assigns the time when the controller injects a command of flow migration to time slots. The proposed model is formulated as an optimization problem to determine the command times to minimize the expected amount. This paper introduces two methods to compute the expected amount. This paper also introduces a two-stage scheduling scheme (2SS) that divides the optimization problem into two stages. 2SS suppresses the computation time from <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\mathcal {O}(|T|^{|F|-1})$ </tex-math></inline-formula> to <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\mathcal {O}\left ({{|T|^{{}\frac {|F|-1}{2}}}}\right)$ </tex-math></inline-formula> at the cost of including at most 0.12% error. 2SS suppresses the amount of excessive traffic than an existing model by at most 71.2%.