Techniques for finding ring covers in survivable networks

摘要

Given an arbitrary telecommunications network N our goal is to find the minimum cost for equipment which will enable N to survive an arbitrary link fault. We consider uni-directional and bi-directional ring technologies. Basically, our goal is to find minimum cost ring covers for any network N, where a ring cover is a set C of rings such that every link in N is covered by (i.e. part of) at least one ring in C. If a network N is augmented with enough equipment to support a given ring cover C, it can respond to a link failure immediately (and automatically) by routing the disrupted traffic through surviving links in the ring that covers the failed link. We describe an efficient algorithm to find a minimum cost ring cover for uni-directional transmission rings under simplifying assumptions. This algorithm offers a useful heuristic for computing low cost ring covers for existing networks and actual cost functions. We also provide efficient heuristics to find nearly minimum cost ring covers for bi-directional transmission rings. We show that certain versions of the bi-directional problem are NP-complete, hence (presumably) no efficient algorithm exists that always finds a minimum cost ring cover. However, our heuristics perform well in practice.