Protection trees have been used in the past for restoring multicast and unicast traffic in networks in various failure scenarios. In this paper we focus on shared self-repairing trees for link protection in unicast mesh networks. Shared protection trees have been proposed as a relatively simple approach that is easy to reconfigure and could provide sub-second restoration times with sub-optimal redundancy requirement. The self-repairing nature of this class of protection trees may make them an attractive option for cases where dynamic changes in network topology or demand may occur. In this paper, we present heuristic algorithms to design a self-repairing protection tree for a given network. We study the restorability performance of shared trees and examine the limitations of such schemes in specific topologies, such as cases where long node chains exist. Using extensive simulations with thousands of randomly generated network graphs. We compare redundancy and average backup path length of shared protection trees with optimal tree designs and non-tree designs. We also apply our algorithms to the problem of designing the protection tree in a pre-designed fixed-capacity network, and study the performance of shared protection trees in this scenario under different network loads and link utilization levels.
Network failure recovery has been an important subject of research in the field of network design and service reliability for more than two decades. The large volume of traffic (data, voice, video on demand, etc.) carried by backbone networks draws special attention to the issue of network recovery and protection against node and link failures, because interruption of such huge traffic flow (and, consequently, the offered user services) could cripple businesses and cost millions of dollars. Fast restoration of traffic after failure is essential, whether the failure is caused by a fiber cut, node failure or higher layer service point failure. At the physical layer ring-shaped designs for optical backbone networks, e.g. SONET UPSR and BLSR rings [1] are used commonly. However more recently, particular attention has been paid to mesh networks, by which we refer to networks in which at least one node is connected to three or more other nodes. Mesh networks in particular address the scalability issues of ring-based architectures, because in mesh networks links and nodes can be added or upgraded solely based on traffic demand without imposing a certain physical topology.
Failure recovery schemes in mesh networks are generally categorized as Path restoration schemes and Link protection schemes [2]. In path restoration schemes, failed connections are restored individually by their source nodes through new end-to-end routes. In link protection schemes, an alternative local path between the end nodes of the failed link is found through the network, and all connections on the failed link are switched in bundle to the local detour. The term link is used in a broad sense here; it could refer to a multi-fiber span, a single fiber, a single wavelength on a fiber, or even a higher layer logical connection. As such, different wavelengths on a fiber may be re-routed on different paths. Path and link protection schemes could use dedicated spare capacity for each backup path, or share the spare capacity on each link among all backup paths that traverse it.
In general, link protection could potentially provide faster recovery service than path restoration because there is no need to inform the source node of each individual connection, or to re-compute the end-to-end path from the source node. This factor could become even more important in backbone networks where each fiber might carry thousands of connections between different source-destination pairs. On the other hand, studies have shown that end-to-end path restoration could provide more capacity efficiency and reduce the required redundancy in the network [3]. In practice, link protection schemes are preferable for quick restoration of physical layer communication in backbone networks, while path restorations can be deployed at the internetworking layer of the network.
We presented an algorithm to design self-repairing hierarchical protection trees for protection of unicast traffic in mesh networks. Such protection trees provide the flexibility of simple, dynamic reconfiguration for sub-second restoration while providing a sub-optimal redundancy requirement. We studied different node placement methods for construction of the tree and showed the benefits and drawbacks of each method in terms of complexity and restorability performance in different scenarios. We computed the complexity of our design heuristics and showed that it had scalable execution time. Our simulation results with more than 12000 random graphs showed that the scheme could provide full restorability in over 99% of the cases if no 3-node chain existed in the network. However when node chains exist, only partial restorability could be achieved. The restorability performance of the algorithm was particularly poor in near-ring networks with average nodal degrees near 2. Our analysis of redundancy results indicates that the heuristics presented here could achieve redundancy results within 20% of optimal tree design, but it the required spare capacity is higher than optimal mesh and protection cycle designs. That would present a tradeoff between the complexity and capacity efficiency of the design. The average and maximum backup paths reported by our design showed dependency on network radius, which increases logarithmically with network size in a random mesh network. We furthermore applied our algorithm to the case of a pre-designed network with fixed-capacity to show how the available spare capacity of the network could be utilized for better restorability of the protection tree.
