Capacity-Aware Topology Resilience in Software-Defined Networks

Network resilience against failures due to natural disasters, equipment malfunction, and malicious attacks has become important for software-defined networks. The current state of the art focuses on two directions: controller redundancy and related recovery mechanisms for resilience in the control plane, and reactive or proactive strategies for resilience against failure of switches or links in the data plane. However, proactive network topology resilience against multiswitch failure by installing backup switches at key locations has been overlooked. We propose a proactive network-topology resilience scheme against worst case adversarial multiswitch failures by installing backup switches at key locations to maximize long-term traffic demands. We formulate this problem as a trilevel optimization, which helps the network operator identify the key N positions for installing backup switches. We develop mixed integer linear programming formulations to maximize aggregate demand satisfaction and maximize the minimum fair demand satisfaction while satisfying constraints such as connectivity, control-plane latency limits, and association capacity of controllers. The proposed models are NP-hard; therefore, we propose efficient heuristic-based greedy algorithms to solve large instances of the above-mentioned problems. We implement the proposed solutions and present the numerical results, which show optimality of the exact formulations and efficiency of the greedy algorithms.