Impact of QoS on Replica Placement in Tree Networks

Anne Benoit 1, 2 Veronika Rehn 1, 2 Yves Robert 1, 2
1 GRAAL - Algorithms and Scheduling for Distributed Heterogeneous Platforms
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
Abstract : This paper discusses and compares several policies to place replicas in tree networks, subject to server capacity and QoS constraints. The client requests are known beforehand, while the number and location of the servers are to be determined. We study three strategies. The first two strategies assign each client to a unique server while the third allows requests of a client to be processed by multiple servers. The main contribution of this paper is to assess the impact of QoS constraints on the total replication cost. In this paper, we establish the NP-completeness of the problem on homogeneous networks when the requests of a given client can be processed by multiple servers. We provide several efficient polynomial heuristic algorithms for NP-complete instances of the problem. These heuristics are compared to the optimal solution provided by the formulation of the problem in terms of the solution of an integer linear program.
Type de document :
Rapport
[Research Report] RR-6065, INRIA. 2006
Liste complète des métadonnées

Littérature citée [12 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00120456
Contributeur : Rapport de Recherche Inria <>
Soumis le : lundi 18 décembre 2006 - 11:00:01
Dernière modification le : vendredi 20 avril 2018 - 15:44:24
Document(s) archivé(s) le : lundi 20 septembre 2010 - 18:05:07

Fichiers

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

Identifiants

  • HAL Id : inria-00120456, version 2

Collections

Citation

Anne Benoit, Veronika Rehn, Yves Robert. Impact of QoS on Replica Placement in Tree Networks. [Research Report] RR-6065, INRIA. 2006. 〈inria-00120456v2〉

Partager

Métriques

Consultations de la notice

286

Téléchargements de fichiers

110