Availability-based path selection

In data communication networks, connection availability, which is defined as the probability that the corresponding connection will be found in the operating state, is a key element of many Service Level Agreements (SLA). The path over which a connection is to be established should obey the agreed-upon availability, otherwise the service provider may face revenue loss as stipulated in the SLA. In this paper, we study the problem of establishing a connection over at most k (partially) link-disjoint paths for which the availability is no less than δ (0 <; δ ≤ 1). We consider networks with and without Shared-Risk Link Groups (SRLGs). We prove that this problem, in general, cannot be approximated in polynomial time, unless P=NP. We subsequently propose a polynomial-time heuristic algorithm and an exact Integer Nonlinear Programming (INLP) formulation for availability-based path selection. Finally, the proposed algorithms and two existing heuristic algorithms are compared in terms of acceptance ratio and running time.