Consistency analysis of software-defined networks reconfiguration

The paper studies the software-defined networks (SDN) reconfiguration problem, considering presence of consistency properties while updating the route tables. Generally, SDN is represented as an oriented graph, but consistency properties can be formulated in various ways. The SDN reconfiguration problem with respect to consistency properties is an NP-hard problem for most cases. The paper defines the SDN model as an undirected graph and formulates the reconfiguration problem for this model that satisfies the loop-free consistency property while the network updates. For the introduced model, the worst-case quadratic algorithm of building the corresponding reconfiguration sequence from one configuration to another is proposed.