Primary and secondary route selection in backbone computer networks

This paper addresses the problem of selecting primary and secondary routes for every pair of communicating nodes in a backbone computer network. A primary route and a secondary route constitute a route pair. The secondary route is node-disjoint (and hence also link-disjoint) from the primary route. A mathematical programming model is developed whose objective is to select routes to minimize the mean delay faced by messages. The model captures situations where a single link or node failure would divert traffic to the appropriate secondary routes. A solution procedure based on a relaxation of the problem is presented. Computational results indicate the effectiveness of the solution procedure.