Optimal algorithms and approximation algorithms for replica placement with distance constraints in tree networks

Anne Benoit 1, 2 Hubert Larchevêque 3, 4 Paul Renaud-Goud 1, 2
1 GRAAL - Algorithms and Scheduling for Distributed Heterogeneous Platforms
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
3 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 : In this paper, we study the problem of replica placement in tree networks subject to server capacity and distance constraints. The client requests are known beforehand, while the number and location of the servers are to be determined. The Single policy enforces that all requests of a client are served by a single server in the tree, while in the Multiple policy, the requests of a given client can be processed by multiple servers, thus distributing the processing of requests over the platform. For the Single policy, we prove that all instances of the problem are NP-hard, and we propose approximation algorithms. The problem with the Multiple policy was known to be NP-hard with distance constraints, but we provide a polynomial time optimal algorithm to solve the problem in the particular case of binary trees when no request exceeds the server capacity.
Type de document :
Rapport
[Research Report] RR-7750, INRIA. 2011, pp.26
Liste complète des métadonnées

https://hal.inria.fr/inria-00630292
Contributeur : Anne Benoit <>
Soumis le : vendredi 3 février 2012 - 14:45:23
Dernière modification le : vendredi 20 avril 2018 - 15:44:24
Document(s) archivé(s) le : mercredi 14 décembre 2016 - 03:26:47

Fichier

RR-7750.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00630292, version 2

Citation

Anne Benoit, Hubert Larchevêque, Paul Renaud-Goud. Optimal algorithms and approximation algorithms for replica placement with distance constraints in tree networks. [Research Report] RR-7750, INRIA. 2011, pp.26. 〈inria-00630292v2〉

Partager

Métriques

Consultations de la notice

418

Téléchargements de fichiers

143