Fast heuristics for protection networks for dynamic routing

Traffic volatility and network reliability are important issues in the provision of high speed network services. We consider the construction of a second network, the protection network, which can carry overload traffic due to the failure or congestion of any two links in the original network. The level 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²) heuristic based on the largest two traffic requirements for each node. This procedure is then modified to generate a more effective O(n⁴) heuristic, both methods facilitate fast processing for two-hop dynamic routing. We compare the performance of the heuristics with the O(n¹⁵) optimal solution.