Research On Computational Complexity And Algorithms Of Network Protection Problems Based On Backup Strategy

With the rapid development of information technology,the network has been widely used in the field of communication,transportation,energy and military.As a result,the demand for the high quality of service in the network is growing in each field.Network survivability,which refers to the ability of the network to maintain normal operation when confronted with network failures,is one of the most important metrics for evaluating the quality of service.Therefore,protecting the network from failures and ensuring network survivability have become an important research topic in the network design.A common strategy to protect networks from failures is to provide backup resources for network components.When failures occur,backup resources can be used to maintain the normal operation of the network.Currently,many backup strategies have been proposed and widely used.However,with the variantion of real-world application scenarios and demands,new backup strategies are also emerging and attracting researchers’ interest.The research on the problem model based on backup strategy is one of the key problem in the field of network protection.Therefore,the work of this dissertation mainly focuses on backup path protection and backup link protection strategies.Based on these strategies,this dissertation proposes three problem models for different real-world applications,and systematically studies the computational complexity and algorithms of them.1.The research on the backup path protection between a pair of nodesOne of the most effective backup path protection strategy is to establish several node-disjoint paths between source and sink with one working path and several backup paths.However,the node-disjointness is too restrictive and there may not exist many node-disjoint paths in the network due to the limitation of geographical environments and network resources.On the other hand,the occurrence probability of node failures is usually much less than that of link failures in real-world applications.Motivated by these,this dissertation proposes a problem model of establishing link-disjoint paths between a pair of nodes that allows the existence of common nodes shared by multiple paths.At the same time,the problem model limits the number of common nodes to reduce the impact of node failures on the network.Previous researches only study the polynomial-time algorithms for the case that the number of paths is two,but the computational complexity for the general case is unknown.This dissertation first proves the NP-hardness of the problem for the general case,answering the question in previous research.Then,this dissertation builds an integer linear programming for the general model to optimally solve the problem.On the other hand,considering that a failure on a node passed by all paths will cause the disconnection of all paths,this dissertation also studies the special case of limiting the number of nodes passed by all paths.For this special case,this dissertation proposes a polynomial-time algorithm by using the techniques of path augmentation and node splitting.This algorithm can be also regarded as a heuristic algorithm for the general model.The experimental results demonstrate that the algorithm outperforms the integer programming algorithm in terms of running time.2.The research on the backup path protection between multiple pairs of nodesIn real-world applications,networks often carry data traffic between multiple node pairs.Motivated by this,this dissertation extends the backup path protection problem between a pair of nodes to that between multiple pairs of nodes,and studies the problem of finding link-disjoint paths between multiple pairs of nodes under the constraint that the number of common nodes is bounded.However,the algorithm for solving the problem between a pair of nodes cannot be directly applied to the problem between multiple pairs of nodes.Moreover,most of the existing research shows that problems related to finding link-disjoint paths between multiple pairs of points are NP-hard.To explore the difficulty of solving the problem,based on these NP-hard results,this dissertation systematically studies the NP-hardness of the problem for different numbers of paths,pairs of nodes,and common nodes.For problems that are hard to solve,this dissertation builds an integer linear programming to optimally solve the problem.However,it takes a long time to solve the instances on large-scale networks.Therefore,this dissertation proposes a fast heuristic algorithm which is to iteratively establish link-disjoint paths between each pair of nodes and withdraw some of the established paths between pairs of nodes when the solution is not feasible.Experimental results show that in real-world networks,the quality of the solution output by the heuristic algorithm is good,and the heuristic algorithm runs faster than the integer linear programming algorithm.3.The research on the backup link protection for regional failuresWhen regional failures caused by natural disasters or terrorist attacks occur,the working path and backup paths established by the backup path protection strategy may fail simultaneously.A more effective protection strategy is the backup link protection strategy,which is to allocate enough backup resources for links so as to fully protect these links from each regional failure.Based on these,this dissertation studies the problem of fully protecting a set of links with the minimum cost such that given node pairs remain connected after each regional failure occurs.Each regional failure is a subset of links in the network.Previous researches only consider the integer linear programming algorithm for the problem of a single node pair and all node pairs,whereas the computational complexity of the problem still remains unknown.This dissertation systematically studies the computational complexity under different settings,such as different numbers of regional failures,different numbers of node pairs,and different topologies of regional failures.For NP-hardness,this dissertation proves the NP-hardness for the problem of four cases: the first is that there is one regional failure,and the number of node pairs is input? the second is that there are two regional failures,and the number of node pairs is bounded by a constant?the third is that the size of regional failures is bounded by a constant? the fourth is that the radius of regional failures is bounded by a constant.These results imply the NP-hardness of the cases studied in the previous research.For NP-hard problems,this dissertation proposes an exact algorithm by using the techniques of integer linear programming and branch-and-cut.Furthermore,this dissertation also studies two additional common special cases and designs fast polynomial-time algorithms: one is a matroid-based algorithm for the case that there are two regional failures and all pairs of nodes remain connected,and the other is an algorithm based on biconnected decomposition technique for the case that each regional failure is a star and given node pairs remain connected.Finally,experiments on real-world networks demonstrate that the algorithms proposed in this dissertation are much faster than previously known algorithms.