A Simple Traffic Independent Scheme for Enabling Restoration Oblivious Routing of Resilient Connections

Fast restoration is an important feature of both MPLS and optical networks. The main mechanism for achieving fast restoration is by locally routing around failures using pre-setup detour paths. Signaling and routing protocol extensions to implement this local bypass ability are currently being standardized. To make use of this ability, dynamic schemes that jointly route primary paths and all link detours for links used by the primary paths have been previously proposed. These schemes also permit sharing of reserved restoration capacity for achieving efficiency. However, this joint computation places a significantly larger computational load on the network elements than that imposed by the shortest path computation variants typically used for unprotected network connection routing. We propose a new scheme that is operationally much simpler, shares capacity used for restoration, and permits the network to route the primary paths in a manner that is oblivious to restoration needs. Restoration of all carried traffic is guaranteed by a new link capacity partitioning scheme that maximizes the working capacity of the network without requiring any knowledge of the traffic that will be imposed on the network. Being traffic independent for a priori link capacity partitioning and being oblivious to restoration needs for on-line network routing makes this scheme operationally simple and desirable in the sense of placing no additional routing load on the constrained computing resources at the network nodes. To compute the link capacity partitions, we develop a fast combinatorial algorithm that uses only iterative shortest path computations, and is a fully polynomial time approximation scheme (FPTAS), i.e., it achieves a (1 + /spl epsi/)-factor approximation for any /spl epsi/> 0 and runs in time polynomial in the input size and 1//spl epsi/.The approximation scheme also allows link detour paths to be hop constrained if needed so as to bound restoration latency in optical networks.