Algorithms for Failure Protection in Large IP-over-Fiber and Wireless Ad Hoc Networks

Abstract

We address failure location and restoration in both optical and wireless ad hoc networks. First, we show how Maximum Likelihood inference can improve failure location algorithms in the presence of false and missing alarms. Next, we present two efficient algorithms for mapping an IP network on an optical network in such a way that it is protected against failures at the optical layer. The first algorithm offers a method to formally verify the existence of a solution, contrary to all other heuristics known to date. The second algorithm is a heuristic search that takes capacity constraints in account. Both algorithms are shown to be faster by orders of magnitude than existing solutions. Finally, we develop a new routing algorithm for wireless mobile ad hoc networks, adopting ideas from the Ant Colony Optimization metaheuristic. The routing scheme can adapt to network and traffic changes and uses multipath routing and an efficient local repair mechanism to improve failure resilience.