TY - GEN
T1 - Service Placement for Detecting and Localizing Failures Using End-to-End Observations
AU - He, Ting
AU - Bartolini, Novella
AU - Khamfroush, Hana
AU - Kim, Injung
AU - Ma, Liang
AU - Porta, Tom La
N1 - Publisher Copyright:
© 2016 IEEE.
PY - 2016/8/8
Y1 - 2016/8/8
N2 - We consider the problem of placing services in a telecommunication network in the presence of failures. In contrast to existing service placement algorithms that focus on optimizing the quality of service (QoS), we consider the performance of monitoring failures from end-to-end connection states between clients and servers, and investigate service placement algorithms that optimize the monitoring performance subject to QoS constraints. Based on novel performance measures capturing the coverage, the identifiability, and the distinguishability in monitoring failures, we formulate the service placement problem as a set of combinatorial optimizations with these measures as objective functions. In particular, we show that maximizing the distinguishability is equivalent to minimizing the uncertainty in failure localization. We prove that all these optimizations are NP-hard. However, we show that the objectives of coverage and distinguishability have a desirable property that allows them to be approximated to a constant factor by a greedy algorithm. We further show that while the identifiability objective does not have this property, it can be approximated by the maximumdistinguishability placement in the high-identifiability regime. Our evaluations based on real network topologies verify the effectiveness of the proposed algorithms in improving the monitoring performance compared with QoS-based service placement.
AB - We consider the problem of placing services in a telecommunication network in the presence of failures. In contrast to existing service placement algorithms that focus on optimizing the quality of service (QoS), we consider the performance of monitoring failures from end-to-end connection states between clients and servers, and investigate service placement algorithms that optimize the monitoring performance subject to QoS constraints. Based on novel performance measures capturing the coverage, the identifiability, and the distinguishability in monitoring failures, we formulate the service placement problem as a set of combinatorial optimizations with these measures as objective functions. In particular, we show that maximizing the distinguishability is equivalent to minimizing the uncertainty in failure localization. We prove that all these optimizations are NP-hard. However, we show that the objectives of coverage and distinguishability have a desirable property that allows them to be approximated to a constant factor by a greedy algorithm. We further show that while the identifiability objective does not have this property, it can be approximated by the maximumdistinguishability placement in the high-identifiability regime. Our evaluations based on real network topologies verify the effectiveness of the proposed algorithms in improving the monitoring performance compared with QoS-based service placement.
UR - http://www.scopus.com/inward/record.url?scp=84985994552&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84985994552&partnerID=8YFLogxK
U2 - 10.1109/ICDCS.2016.21
DO - 10.1109/ICDCS.2016.21
M3 - Conference contribution
AN - SCOPUS:84985994552
T3 - Proceedings - International Conference on Distributed Computing Systems
SP - 560
EP - 569
BT - Proceedings - 2016 IEEE 36th International Conference on Distributed Computing Systems, ICDCS 2016
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 36th IEEE International Conference on Distributed Computing Systems, ICDCS 2016
Y2 - 27 June 2016 through 30 June 2016
ER -