Network Mass Destruction After Gradual Recovery Mechanism Research

In recent years, with the continuous development of network technologies and the increasing of network applications, the Internet has become a necessary part in our study, work and life. Studying and communication, online shopping, government management, company operations, and even emergency relief can not be separated from the network. Along with the increasing demand of the network, the size and complexity of the network is also growing, therefore, when natural disasters, system crash or malicious attacks occurr, the potential for large-scale failures is gradually increasing. In order to ensure the safety of people’s lives, maintain the social stability and reduce economic losses, it is critical to recover the network effectively and quickly after large-scale failures. In addition, limited of manpower, material and financial resources in the recovery process, the recovery resources can not be fully provided in one-step, so the recovery process must be completed progressively in multi-stages.This thesis does research on the progressive network recovery after massive failures, mainly to solve the following two cases of network restoration problem.(1) Progressive Network Recovery in Single-Stage (PNRSS) after large-scale failures. Because of the limited recovery resources after massive failures, the network can not be completely recovered, so our problem is how to select a subset of the failed components to repair so as to maximize to meet users’traffic demand. In PNRSS problem, this thesis first formulates the PNRSS problem as a Mixed Integer Linear Programming (MILP) model, and then proposes the Shadow Price and Knapsack Problem based PNRSS Algorithm (SPKP-PNRSS) and the K Shortest Path based PNRSS Algorithm (KSP-PNRSS). Simulations show the proposed algorithms both have great performance and are suitable for large-scale network. The results of SPKP-PNRSS are very close to the optimal objective funcation value of the PNRSS MILP model and KSP-PNRSS greatly improves the time efficiency, the results are also good.(2) Progressive Network Recovery in Multi-Stage (PNRMS) after large-scale failures. After massive failures occurring, with the limited of time and distance, the recovery resources can only be delivered in bathches, so the network must be rebuilt in multi-stages. For PNRMS problem, this thesis does research on two sub-problems:the one is minimizing the stages of recovery resources to repair damaged components of the network, in order to meet all of users’traffic demand in the partially recovery network, and the other one is deciding the link recovery order in the given recovery stages, in order to maximize the sum of traffic flow at each stage of the recovery process. For the first sub-problem, this thesis formulates the Minimizing Recovery Stage based PNRMS (MRS-PNRMS) problem as a MILP model, and proposes the Flow Proportion based MRS Algorithm (FP-MRS). Simulations show that the results of FP-MRS are very close to the optimal objective funcation value of the MRS-PNRMS model. For the second sub-problem, this thesis formulates the Maximizing Traffic Demand based PNRMS (MTD-PNRMS) problem as another MILP model, and proposes the Decided Link Recovery Order for MTD Algorithm (DLRO-MTD). Simulations show that FP-MRS and DLRO-MTD associated algotithm greatly improves the time efficiency and the results are very good.