Fast heuristics for protection networks for dynamic routing

Traffic volatility and network reliability are important issues in the prov ision of high speed network services. We consider the construction of a sec ond network, the protection network which can carry overload traffic due to the failure or congestion of any two links in the original network. The le vel of protection against such contingencies can be specified by a traffic requirement matrix. We construct a fully connected protection network, for an n node network, using an O(n(2)) heuristic based on the largest two traf fic requirements for each node. This procedure is then modified to generate a more effective O(n(4)) heuristic, both methods facilitate fast processin g for two-hop dynamic routing. We compare the performance of the heuristics with the O(n(15)) optimal solution.