Establishing Alternate Routes in Networks and Routes Between Polygons in 2D Space

Amit M. Bhosle

Doctor of Philosophy
December 2008

Department of Computer Science
University of California, Santa Barbara

CURRICULUM VITÆ

2000	Bachelor of Technology (Honours)
	Department of Computer Science & Engineering
	Indian Institute of Technology, Kharagpur, India.
	IIT-JEE All India Rank 342.
2003	Masters of Science (Thesis)
	Department of Computer Science
	University of California, Santa Barbara, CA, USA.
2008	Doctor of Philosophy
	Department of Computer Science
	University of California, Santa Barbara, CA, USA.

PUBLICATIONS

1. Amit M. Bhosle, Teofilo F. Gonzalez. ``Finding Optimal Geodesic Bridges Connecting Two Simple Polygons''. Under preparation, Nov. 2008.

2. Amit M. Bhosle, Teofilo F. Gonzalez. ``Distributed Algorithms for Computing Alternate Paths Avoiding Failed Nodes and Links''. Submitted, Nov. 2008.

3. Amit M. Bhosle, Teofilo F. Gonzalez. ``Efficient Algorithms and Routing Protocols for Handling Transient Single Node Failures''. Proc. 20th IASTED International Conference on Parallel and Distributed Computing and Systems, Nov. 2008, Orlando, FL, USA.

4. John Hershberger, Subhash Suri, Amit M. Bhosle. ``On the Difficulty of Some Shortest Path Problems''. ACM Transactions on Algorithms, 3(1):5-29, 2007.

5. Amit M. Bhosle, Teofilo F. Gonzalez. ``Exact and Approximation Algorithms for Finding the Optimal Bridge Connecting Two Simple Polygons''. International Journal of Computational Geometry and Applications, 15(6):609-630, 2005.

6. Amit M. Bhosle. ``Improved Algorithms for Replacement Paths Problems in Restricted Graphs''. Operations Research Letters, 33(5):459-466, 2005.

7. Amit M. Bhosle, Teofilo F. Gonzalez. ``Algorithms for Single Link Failure Recovery and Related Problems''. Journal of Graph Algorithms and Applications, 8(3):275-294, 2004.

8. Amit M. Bhosle, Teofilo F. Gonzalez. ``Replacement Paths for Pairs of Shortest Path Edges in Directed Graphs''. Proc. 16th IASTED International Conference on Parallel and Distributed Computing and Systems, Nov. 2004, MIT, Cambridge, MA, USA.

9. Amit M. Bhosle, Teofilo F. Gonzalez. ``Efficient Algorithms for Single Link Failure Recovery and its Applications to ATM Networks''. Proc. 15th IASTED International Conference on Parallel and Distributed Computing and Systems, Nov. 2003, Marina del Rey, CA, USA.

10. John Hershberger, Subhash Suri, Amit M. Bhosle. ``On the Difficulty of Some Shortest Path Problems''. Proc. 20th International Symposium on Theoretical Aspects of Computer Science, Feb. 2003, Berlin, Germany.

11. Nikhil Tripathi, Amit M. Bhosle, Debasis Samanta, Ajit Pal. ``Optimal Assignment of High Threshold Voltage for Synthesizing Dual Threshold CMOS Circuits''. Proc. 14th IEEE International Conference on VLSI Design, Jan. 2001, Bangalore, India.

PATENTS

• Vijay Chandrasekaran, Amit M Bhosle, Rahul Gudla. ``System and method for designing effective business policies via business rules analysis''. Filed: August 2006, USPTO Applicaton No. 20060190310, Class 705007000

TECHNICAL SKILLS

• Core Competencies: Algorithms, Data Structures, Distributed Systems, Graph Theory, Computational Geometry.
• Programming Languages: Java, Ruby; Working knowledge of C, C++.
• Operating Systems: Linux, UNIX variants, Windows based systems.
• Databases Technologies: MySQL, JDBC

WORK EXPERIENCE

• May 08 - Present: Software Engineer, External Payment Systems, Amazon.com, Inc., Seattle, WA.

• Oct 04 - May 08: Software Engineer, Amazon Web Services, Amazon.com, Inc., Seattle, WA and Bangalore, India.

• Apr 03 - Sep 04: Member, Algorithms Research Group, YASU Technologies Pvt. Ltd., Hyderabad, India.

Abstract:

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.