Multi-Constrained Shortest Disjoint Paths for Reliable QoS Routing

Date Added: Oct 2009
Format: PDF

Finding link-disjoint or node-disjoint paths under multiple constraints is an effective way to improve network QoS ability, reliability, and so on. However, existing algorithms for such scheme cannot ensure a feasible solution for arbitrary networks. The authors propose design principles of an algorithm to fill this gap, which they arrive at by analyzing the properties of optimal solutions for the multi-constrained link-disjoint path pair problem. Based on this, they propose the LInk-Disjoint Optimal Multi-constrained Paths Algorithm (LIDOMPA), to find the shortest link-disjoint path pair for any network. Three concepts, namely, the candidate optimal solution, the contractive constraint vector, and structure-aware non-dominance, are introduced to reduce its search space without loss of exactness.