TY - GEN
T1 - Availability-based path selection
AU - Yang, Song
AU - Trajanovski, Stojan
AU - Kuipers, Fernando A.
N1 - Publisher Copyright:
© 2014 IEEE.
PY - 2014/1/19
Y1 - 2014/1/19
N2 - 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.
AB - 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.
KW - Availability
KW - Routing
KW - SRLG
KW - Survivability
UR - http://www.scopus.com/inward/record.url?scp=84988226829&partnerID=8YFLogxK
U2 - 10.1109/RNDM.2014.7014929
DO - 10.1109/RNDM.2014.7014929
M3 - Conference contribution
AN - SCOPUS:84988226829
T3 - Proceedings of 2014 6th International Workshop on Reliable Networks Design and Modeling, RNDM 2014
SP - 39
EP - 46
BT - Proceedings of 2014 6th International Workshop on Reliable Networks Design and Modeling, RNDM 2014
A2 - Rak, Jacek
A2 - Sterbenz, James P.G.
A2 - Sterbenz, James P.G.
A2 - Shen, Gangxiang
A2 - Walkowiak, Krzysztof
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 6th International Workshop on Reliable Networks Design and Modeling, RNDM 2014
Y2 - 17 November 2014 through 19 November 2014
ER -