A distributed link restoration algorithm with robust preplanning

Abstract

A technique that combines benefits of fast, distributed heuristics and of centralized optimal algorithms is proposed. As a form of preplanning, whenever the topology of the network is deliberately changed, new optimal rerouting plans are calculated, using a centralized or a distributed approach, for each possible total cable failure. These plans are used to calculate distance labels that are stored in the digital cross-connect systems or other switching elements. When a failure occurs, the nodes (switches) at either end of the failed cable start the execution of a distributed max-flow algorithm and communicate with their neighbors by message passing. As nodes become involved in the execution of the distributed algorithm, they imitate their state using the precalculated distance labels. An appropriate set of distance labels can be defined on a transformed version of the network such that, if no topology changes have occurred in the network since the labels were calculated, the algorithm immediately converges to the optimal solution. If, on the other hand, links and/or nodes have been removed since the labels were calculated, the algorithm will still function properly and converge to a solution that has the maximal number of restored circuits (although the restoration paths are not necessarily of shortest possible length).< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>