Efficient Schemes for Shared Backup Allocation in Networks with Partial Information

Modern communication networks are required to provide Quality of Service (QoS) assurance and fault resilience, while maximizing their utilization. This prompts the need for new dynamic restorable routing algorithms that exploit restoration resource sharing for achieving these goals. The best possible sharing can be obtained when the routing algorithms have complete information of all primary and restoration paths. However, representing this information can be quadratic in the number of links, making it impractical in large networks. Recently, Kodialam and Lakshman have shown that significant resource sharing is already obtained when only partial information is available. e.g., segregating between the amount of bandwidth allocated for primary paths and restoration paths, for each link. Their work inspired the development of new routing algorithms that allow for considerable resource sharing. However, these algorithms do not provide any guarantee on the quality of the solutions. In this work, we develop efficient algorithmic solutions for resource sharing that are guaranteed to be within a certain factor away from the optimum. First, we show that such a solution does not exist using a disjoint path approach for primary and restoration paths. Then, we present a new local restoration approach, called bridge set, in which a primary path is associated with a set of bridges, each protecting a portion of the primary path. This approach has several advantages over the disjoint path strategy, including higher network utilization, and it enables us to construct an efficient approximation algorithm for the partial information model. The algorithm has an O(log log N) approximation factor for networks with N nodes and bounded diameter. Moreover, our scheme utilizes a dynamic programming that performs only shortest path calculations, which makes it more attractive than most other methods that are based on solving linear programs.