Different Algorithms for Normal and Protection Paths
R. Gupta
Department of Electrical Engineering and Computer Sciences
the University of California Berkeley,
Cory Hall #1772,
Berkeley, CA 94720-1772 USA
Email: guptar_AT_eecs.berkeley.edu
E. Chi
Department of Electrical Engineering and Computer Sciences
University of California Berkeley,
Cory Hall #1772,
Berkeley, CA 94720-1772 USA
Email: echi_AT_eecs.berkeley.edu
J. Walrand
Department of Electrical Engineering and Computer Sciences
University of California Berkeley,
Cory Hall #1772,
Berkeley, CA 94720-1772 USA
Email: wlr_AT_eecs.berkeley.edu
Abstract
Many network routing situations commonly require backup paths that satisfy various constraints on bandwidth, link or node selection, and ease of configuration. In this paper, we attempt to validate whether it is beneficial to have distinct algorithmic treatments of normal and backup path calculation, configuration and maintenance. We present a modular suite of algorithms that enable us to manage normal and protection paths differently. In the process, we develop a simple extension of Minimum Interference Routing Algorithm for shared protection paths. We incorporate a distributed algorithm to separately calculate normal and backup paths in the network, using link state information, and present an evaluation of asynchronous dynamic reorganization of backup paths to reduce congestion in the network. Simulations demonstrate non-trivial quantitative reductions in blocking probabilities under certain conditions.
We conclude that in order to choose an optimal algorithm for a protected QoS routing application, it is recommended to also consider a combination of two different algorithms for normal and backup paths.
Keywords: Optical Networks, MPLS, Protection Paths
JNSM: Vol. 13, No. 1, 2005
Different Algorithms for Normal and Protection Paths [Vol. 13, No. 1, 2005]
NOTE: only abstract of paper available on-line; please contact your library or the authors for the full paper
Back to JNSM main page