An Improved Approximation Algorithm for Computing Disjoint QoS Paths

The survivability of a network has assumed great importance in against of losing huge volumes of data due to a link cut or node failure. Recently some scholars have proposed some path restoration schemes which used two disjoint paths with multiple constraints to satisfy both the survivability and the QoS requirements. In this paper we will study the issue of how to identify two paths that satisfy the multiple QoS constraints imposed by network applications. More specifically, we will focus on finding two link-disjoint paths that satisfy the delay constraints at a reasonable total cost. We present two efficient approximation algorithms with provable performance guarantees for this problem.