We propose a new algorithm for constructing redundant trees over any edge or node-redundant network in order to perform automatic protection switching in the presence of edge or node failures. Existing redundancy schemes and their topological requirements are reviewed. We describe our algorithm and give an overview of its essential properties. The algorithm is polynomial in the number of nodes. We present an example of the construction of a lowest cost redundant topology for a given configuration and of the operation of our algorithm on that topology. The algorithm is particularly well suited to multicast networks and optical networks, where trees may be created by signal splitting.
展开▼
