Heuristic Algorithms for Shared Protection of Virtual Private Networks

Optimal routing in backbone networks with capacity constraints is a known problem. The task could be solved e.g. by integer programming or by heuristic algorithms. In the authors' paper, they analyzed heuristic algorithms that solve the above-mentioned problem including protection. Furthermore they investigated a special case when multiple full mesh demand sets (forming VPNs) have to be built. VPNs connect multiple sites on a backbone network. To provide service reliability a resilience scheme is required. They examined the pro-active path based shared protection scheme and investigated heuristic algorithms to calculate the paths.