An approach to QoS-constrained path protection in MANETs using segment-backup paths

Abstract

In the context of mobile ad hoc networks (MANETs), we consider the problem of identifying (a) an optimal primary path which satisfies the required QoS constraints, and (b) a set of alternate paths that may be used in case a link or a node on the primary path fails. The alternate paths are also required to satisfy the same set of QoS constraints as is the case with the primary path. In the paper, we have proposed that the traffic be re-routed along a subpath that bypasses a segment of the primary path that contains the failed link or node. The segments are determined based on (a) availability of alternate paths, so that (b) QoS constraints are met. This flexibility in identifying the segments can also be used to ensure that the delay in switching traffic over to an alternate path, and the resulting packet loss, are bounded. This paper is focused on proving that for a given (a) source-destination pair of nodes in a network, and (b) any primary path between them, the nodes on the primary path can be divided into a collection of segments such that for each segment there exists an alternate path which completely bypasses the segment if and only if there exist two or more node-disjoint paths between the source and destination nodes. This implies that if there exists a solution consisting of a set of alternate backup paths for a given primary path then such a solution can always be found for any primary path. We describe an algorithm to identify (a) a primary path, (b) the collections of segments, and (c) the corresponding set of alternate paths, one for each segment, each of which satisfies specified QoS constraints, so that the delay in switching traffic over to an alternate path is
bounded.