A near optimal solution for network topology reconfigurations with limited link resources

As a promising approach to improve network survivability, reliability and flexibility, topology reconfiguration is extremely important for modern networked infrastructures. In particular, for an existing network and a limited set of newly available resources, it is valuable to determine how to optimally allocate the new resources, such that the resulting network is the most robust and efficient. In this paper, we investigate the problem of network topology reconfiguration (NTR) optimization with limited link resources. A dynamic robustness metric is developed to quantitatively characterize the network robustness and efficiency. We show that the NTR optimization with limited link resources is NP-complete. Therefore, to approximately solve the problem, we develop a preferential configuration node-protecting cycle (PCNC) scheme for sequential link additions. Analysis showed that the PCNC scheme provide an approximate optimal solution under the dynamic robustness metric. Simulation results also showed that the PCNC scheme effectively improves the network robustness and efficiency at the cost of least added link resources.