Establishing Alternate Routes in Networks and Routes Between Polygons in 2D Space
Amit M. Bhosle
Doctor of Philosophy
December 10th, 2008
Department of Computer Science
University of California, Santa Barbara
Committee:
Professor Teofilo F. Gonzalez (Chair)
Professor Peter Cappello
Professor Ömer Egecioglu
A recent study characterizing failures in computer networks shows that transient single element (node/link) failures are the dominant failures in today's large communication networks, like the Internet. Thus, having the routing paths globally recomputed on a failure does not pay off since the failed element recovers fairly quickly, and the recomputed routing paths need to be discarded. A popular approach for tackling the issues related to transient failures of network elements is that of using proactive recovery schemes. These schemes typically work by precomputing alternate paths at the network setup time for the failure scenarios, and then using these alternate paths to re-route the traffic when the failure actually occurs.
In this thesis, we present our algorithms for finding alternate paths that are required by some existing proactive recovery schemes, and propose a new proactive recovery scheme that makes use of these alternate paths. We primarily focus on single link and single node failures in communication networks, and study some specific scenarios of multiple links and/or node failures. We also discuss some related graph theoretic problems that deal with finding alternate edges and/or paths when certain network elements fail. In addition to centralized algorithms, we also present the first fully decentralized and distributed algorithm that computes alternate paths that avoid failed nodes or links.
A related problem in computational geometry deals with the problem of finding a bridge between two simple polygons that minimizes the maximum distance from any point in one polygon to any point in the other polygon. We present exact and approximation algorithms, and a fully polynomial time approximation scheme for these problems. While variations of these problems have been extensively studied and optimally solved for the cases where the input polygons are convex, there are no known polynomial time algorithms for the case where the input polygons can be simple. Previous results related to simple polygons imposed an artificial restriction that the end points of the bridges be mutually visible. We study the problems in a more general context where no such restriction is imposed on the end points of an optimal bridge. The variants of this problem that we study include finding Euclidean and geodesic bridges connecting two simple polygons. Our algorithms are the first polynomial time algorithms for these problems. To put the problem in perspective, the Euclidean version of the problem is applicable in the case where one wants to build a bridge connecting the two polygons. For the geodesic version of the problem, the intention is to find a ferry route that can be followed by a ferry boat between a port on one island to a port on the other.