AbstractWe consider off-line versions of path provisioning and path protection problems for general circuit switched networks. Both problems deal with a given network topology and a list of integral demand flows. The objective is to route the flows and to allocate the bandwidth in a way that minimizes the total amount of bandwidth used for working and protection paths. We consider path-based protection where, in case of a single link failure, all the flows utilizing the failed link can be rerouted to a precomputed set of paths. We demonstrate that flow splitting can bring significant advantages for both provisioning and protection problems. Since the problem is NP-complete, we propose and analyze two simple heuristics. We show that one of these heuristics performs almost as well as the optimal solution.
RightsThis Item is protected by copyright and/or related rights.You are free to use this Item in any way that is permitted by the copyright and related rights legislation that applies to your use.For other uses you need to obtain permission from the rights-holder(s).