Resource Placement With Maximal Vertex-Disjoint Path Connectivity

Abstract

Resource placement is a problem with several applications in communications networks, from the placement of caches, proxies, or even servers to the allocation of controllers in software-defined networks, among others. This work introduces the problem of placing the minimum number of resources that maximizes the number of vertex-disjoint paths between clients and a resource. In this way, in case of node failures, clients have the largest number of alternative paths to reach the resource. We call the problem resource placement with maximum connectivity (RP-MaxC). One of the contributions of this article is the proof that the problem is NP-complete. Nevertheless, an exact solution was implemented and presented reasonable execution times for experiments using network topologies from the Internet Topology Zoo (which are all sparse). We also present variations of the problem taking into account the sum of distances between clients and resources. RP-MaxC and variations were implemented, and experiments were executed, including comparisons with the classical $p$-median problem and variations. Results show both the benefits of placing resources with maximum connectivity and the impact on the sum of the distances when the proposed solution is applied to real Internet topologies.