Self-repairing hierarchical tree-based link restoration scheme for mesh networks

Abstract

In this thesis we propose and study a self-repairing tree-based pre-planned link protection scheme for backbone mesh survivable networks. We introduce the concept of hierarchical protection trees for unicast traffic protection on network links. The design of the protection tree is formulated and heuristic algorithms are provided for two separate scenarios: (1) the unrestricted spare capacity assignment where the minimization of spare capacity is the objective, and (2) the pre-designed network scenario where the objective of design is to maximize the total network restorability. Using various models for computation, we apply our design techniques to construct the protection tree in each sample network in each scenario, and compute various restoration performance measures of restorability, redundancy, and average backup path length. We conduct extensive studies of the performance trends of the hierarchical protection trees on a database that we built from thousands of randomly generated mesh networks with varying topology parameters such as network size, number of nodes, average nodal degree, network radius, and variation in network load. We have also extended our study to the multiple (double and triple) failure scenarios. We present computational methods to calculate the multiple failure restorability and redundancy requirements for the sample networks from our database. Finally, we provide a comprehensive scheme that covers the signalling, message formats, algorithms and recovery mechanisms for construction of a hierarchical tree in a distributed manner. The advantages and limitations of this new approach are also discussed.