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.

I. Introduction

There has been a growing interest in understanding the robustness of practical networked systems such as the Internet, transportation networks, and other cyber-physical systems [1]–[2]. These systems are important infrastructures in modern society and are expected to possess sufficient robustness against the unpredictable breakdown in order to maintain the expected function constantly [3]. Scale-free network (SFN) is known to be effective in terms of both the average path length and the robustness against random breakdown, but vulnerable under intentional attack on the hub nodes [1]. It is thus important to configure and reconfigure a network structure according to the various types of breakdown or intentional attack while maintaining the functionality of the networked system.