Fast lossless traffic migration for SDN updates

Migration of traffic from one configuration to another is common in SDNs due to node/link failures, network maintenance, policy reconfiguration, intrusion detection, network upgrades, and etc. When the network devices are informed by the controller to execute the traffic migration, it's difficult even impossible to force all network devices to perform the update action in a strict synchronized way. Thus the network is likely to see transient overlapped traffic from both the new configuration and the old one. This kind of overlap may cause overload to those hot spots. This paper reveals the transient congestion problem during traffic migration in an SDN update. According to the observation, it's feasible for the controller to schedule ingress nodes to perform the migration in an order thus the transient congestion is avoided. This scheduling problem is formulated as a Mixed Integer Linear Program (MIP) model. If feasible orders exist for ingress network nodes to perform the migration, the MIP can always find the order that achieves the minimum steps in all possibilities. A heuristic method (named ATOMIP (ATOmic-MIP)) is proposed to speed-up the solving of this MIP. Evaluation based on network topologies observed from real ISPs shows that the lossless migration happens in sub-seconds.