Efficient Algorithm and Infrastructure for Managing Protection Paths in a Network

Rajarshi Gupta and Eric Chi
(Professor Jean Walrand)
(DARPA) IPTO N66001-00-C-8062 and Extreme Networks

In many network routing situations, it is necessary to calculate a protection path in addition to a normal path. Applications like MPLS networks and optical networks require backup paths that satisfy various constraints of bandwidth, link or node selection, and ease of configuration.

In this research, we first demonstrate the premise that algorithmic treatments of normal and backup path calculation, configuration, and maintenance should be different from those accorded to normal paths. We demonstrate this through a new hysteresis-based scheme to handle dynamic demands in a network, where the different parameters accorded to normal and backup paths enable better utilization of network resources.

The chief contribution of this work is to present an infrastructure for managing normal and protection paths in a network through a modular suite of algorithms. We present several novel mechanisms to enhance the overall performance. (1) A distributed method of separately calculating normal and backup paths in the network, using link state information. (2) A sophisticated per-link state maintained at each node, which allows optimal sharing of backup bandwidth. (3) Piggybacking the link state information on the reservation ack/nack packets, to implement a very low intensity link state update mechanism. This may be deployed in cases where global link state updates are too costly to use. (4) Asynchronous dynamic reorganization of backup paths to reduce congestion in the network. We apply Markov decision process analysis to quantitatively determine the reduction in blocking probability under various network loads.

We have also developed a simulation model which may be used to verify and evaluate the algorithms developed. The modular simulation model allows specific components to be plugged in or out, and has hooks to capture statistics. It enables us to quantify the gains achieved by adopting the mechanisms listed above, e.g. reduction in blocking probability and specific link loads under fixed total loads applied across source destination pairs in the network.

More information (http://www.eecs.berkeley.edu/~guptar) or

Send mail to the author : (guptar@eecs.berkeley.edu)

Edit this abstract