Finding Critical Regions and Region-Disjoint Paths in a Network

Finding Critical Regions and Region-Disjoint Paths in a Network

Trajanovski, S.
Kuipers, F.A.
Ili?, A.
Crowcroft, J.
Van Mieghem, P.

Electrical Engineering, Mathematics and Computer Science

Network Architectures & Services (NAS)

2014-03-20

Due to their importance to society, communication networks should be built and operated to withstand failures.However, cost considerations make network providers less inclined to take robustness measures against failures that are unlikely to manifest, like several failures coinciding simultaneously in different geographic regions of their network. Considering networks embedded in a two-dimensional plane, we study the problem of finding a critical region - a part of the network that can be enclosed by a given elementary figure of predetermined size - whose destruction would lead to the highest network disruption.We determine that only a polynomial,in the input, number of non-trivial positions for such a figure need to be considered and propose a corresponding polynomialtime algorithm. In addition, we consider region-aware network augmentation to decrease the impact of a regional failure. We subsequently address the region-disjoint paths problem, which asks for two paths with minimum total weight between a source (s) and a destination (d) that cannot both be cut by a single regional failure of diameter D (unless that failure includes s or d). We prove that deciding whether region-disjoint paths exist is NP-hard and propose a heuristic region-disjoint paths algorithm.

survivability
geographical failures
critical regions
region-disjoint paths
network augmentation

http://resolver.tudelft.nl/uuid:cf4ae9f3-262b-4673-bc5e-470f260c64bb

IEEE

1063-6692

IEEE/ACM Transactions on Networking, 23 (3), 2015; Pre-print

https://doi.org/10.1109/TNET.2014.2309253

Institutional Repository

journal article

(c) IEEE (Sponsored by ACM)