TITLE:  Failure Localization in Optical Networks: A Study of
Capacity-Efficient Restoration Algorithms

AUTHOR:  Sun-il Kim

ABSTRACT: Protection against failures of links or nodes in high-speed optical
networks can be achieved using path/link protection, covers of rings, or
generalized loopback. We focus on node recovery using generalized loopback,
which provides full robustness to single failures of links or nodes in a
capacity-efficient manner. We study the connectivity between nodes with
protection against any single link or node failure, and also consider the
increase in routing path lengths as a result of providing link and node
protection. We provide a failure model for node recovery based on this
investigation and introduce metrics that capture a notion of
failure localization. Using these measures, we quantify the generalized
loopback algorithm's ability to perform node recovery by comparing it to
that of double cycle cover. We also study the tradeoff between capacity
and robustness to multiple failures for five sample networks.

On average for the five sample networks, generalized loopback provide full
connectivity with guaranteed protection from single node failures, while
double cycle covers provide 61.2% connectivity. Generalized
loopback incurs a 5.8% increase in routing path lengths, whereas double
cycle cover has an increase of about 24.6%. Comparison with double cycle
cover for the five different networks shows that generalized loopback
provides the same level of failure localization while using 16% less
capacity on average. With equal capacity, generalized loopback improves
failure localization by an average of 22%.

We apply genetic algorithm to find sets of digraphs that allow generalized
loopback to achieve good failure localization. For the NJ LATA network and
the ARPANET network, optimal sets of directions were found.