An algorithm for survivable network design employing multiple self-healing rings

The authors have developed an algorithmic approach to synthesis of restorable networks that employ several self-healing rings (SHRs). The method is near-optimal from a capacity efficiency perspective. The multi-ring design configurations that result may be used directly, or the algorithm may be used as an automated “design proposer” to complement existing ring planning analysis tools. A systematic search for an optimum multi-SHR design is structured as a greedy search for ring candidates amongst the set of cycles of the network. Novel aspects of the approach are: (i) determination and use of the cycle set of the network graph to structure a systematic search for collectively efficient ring sets that cover the network, (ii) use of several different metric functions to explore alternative search paths in the design space. Each identifies a different locally optimal network construction from which the best global candidate is easily selected. On small and medium test cases, results show that the algorithm produces good designs, strictly optimal in some cases, if assessed from the point of view of capacity efficiency. For larger networks, where the strictly optimal result is not known, the authors still show improvements over previously published results