Modeling and Practical Evaluation of a Service Location Problem in Large Scale Networks

Olivier Beaumont 1, 2 Nicolas Bonichon 1, 2 Hubert Larchevêque 1, 2
1 CEPAGE - Algorithmics for computationally intensive applications over wide scale distributed platforms
Université Sciences et Technologies - Bordeaux 1, Inria Bordeaux - Sud-Ouest, École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), CNRS - Centre National de la Recherche Scientifique : UMR5800
Abstract : We consider a generalization of a classical optimization problem related to server and replica location problems in networks. More precisely, we suppose that a set of users distributed over a network wish to have access to a particular service proposed by a set of providers. The aim is then to distinguish a set of service providers able to offer a sufficient amount of resources in order to satisfy the requests of the clients. Moreover, a quality of service following some requirements in terms of latencies is desirable. A smart repartition of the servers in the network may also ensure good fault tolerance properties. We model this problem as a variant of Bin Packing, namely Bin Packing under Distance Constraint (BPDC) where the goal is to build a minimal number of bins (i.e. to choose a minimal number of servers) so that (i) each client is associated to exactly one server, (ii) the capacity of the server is large enough to satisfy the requests of its clients and (iii) the distance between two clients associated to the same server is minimized. We prove that this problem is hard to approximate even when using resource augmentation techniques : we compare the number of obtained bins when using polynomial time algorithms allowed to build bins of diameter at most b*dmax, for b>1, to the optimal number of bins of diameter at most dmax. On the one hand, we prove that (i) if b=(2-e), BPDC is hard to approximate within any constant approximation ratio, for any e>0; and that (ii) BPDC is hard to approximate at a ratio lower than 3/2 even if resource augmentation is used. On the other hand, if b=2, we propose a polynomial time approximation algorithm for BPDC with approximation ratio 7/3 in the general case. We show how to turn an approximation algorithm for BPDC into an approximation algorithm for the non-uniform capacitated K-center problem and vice-versa. Then, we present a comparison of the quality of results for BPDC in the context of several Internet latency embedding tools such as Sequoia and Vivaldi, using datasets based on PlanetLab latency measurements.
Document type :
Conference papers
Complete list of metadatas

Cited literature [30 references]  Display  Hide  Download

https://hal.inria.fr/inria-00580969
Contributor : Hubert Larchevêque <>
Submitted on : Tuesday, March 29, 2011 - 6:06:53 PM
Last modification on : Thursday, January 11, 2018 - 6:22:11 AM
Long-term archiving on : Thursday, November 8, 2012 - 12:56:13 PM

File

BPDC_BeaumontBonichonLarcheveq...
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00580969, version 1

Citation

Olivier Beaumont, Nicolas Bonichon, Hubert Larchevêque. Modeling and Practical Evaluation of a Service Location Problem in Large Scale Networks. Internation Conference on Parallel Computing 2011, Sep 2011, Taipei, Taiwan. pp.10. ⟨inria-00580969⟩

Share

Metrics

Record views

278

Files downloads

185