The Robust Node Selection Problem aiming to Minimize the Connectivity Impact of any Set of p Node Failures

Conference: DRCN 2017 – Design of Reliable Communication Networks - 13th International Conference
03/08/2017 - 03/10/2017 at München, Deutschland

Proceedings: 13th International Conference DRCN 2017

Pages: 8Language: englishTyp: PDF

Personal VDE Members are entitled to a 10% discount on this title

Sousa, Amaro de (Instituto de Telecomunicações, Universidade de Aveiro, Aveiro, Portugal)
Mehta, Deepak (United Technologies Research Centre, Cork, Ireland)
Santos, Dorabella (Instituto de Telecomunicações, Aveiro, Portugal)

Consider a network defined by an undirected graph and a positive weight assigned to each pair of nodes of a given network. For a positive integer parameter p, the critical node detection (CND) problem aims to identify a set of p nodes that minimizes the network weighted connectivity, i.e., the total weight of the node pairs that remain connected if p nodes fail. The minimum weighted connectivity provided by CND is used as the network vulnerability metric since it represents the lowest network weighted connectivity guaranteed for any set of p node failures. Also consider that any node can be made robust such that it never fails. For a positive integer parameter r, we define the robust node selection (RNS) problem as the selection of a set of r nodes that, if made robust, minimizes the connectivity impact of any set of p node failures by maximizing the minimum weighted connectivity provided by CND. We propose both an exact and a heuristic method to solve RNS and present computational results based on networks with up to 75 nodes. The computational results demonstrate the limits up to where the exact method can compute optimal solutions and the efficiency of the proposed heuristic for finding good quality solutions when the exact method is computationally expensive.