Power-aware replica placement in tree networks with multiple servers per client

Abstract : In this paper, we revisit the well-studied problem of replica placement in tree networks. Rather than minimizing the number of servers needed to serve all client requests, we aim at minimizing the total power consumed by these servers. In addition, we use the most general (and powerful) server assignment policy, where the requests of a client can be served by multiple servers located in the (unique) path from this client to the root of the tree. We consider multi-modal servers that can operate at a set of discrete speeds, using the dynamic voltage and frequency scaling (DVFS) technique. The optimization problem is to determine an optimal location of the servers in the tree, as well as the speed at which each server is operated. A major result is the NP-completeness of this problem, to be contrasted with the minimization of the number of servers, which has polynomial complexity. Another important contribution is the formulation of a Mixed Integer Linear Program (MILP) for the problem, together with the design of several polynomial-time heuristics. We assess the efficiency of these heuristics by simulation. For mid-size instances (up to 30 nodes in the tree), we evaluate their absolute performance by comparison with the optimal solution (obtained via the MILP). The most efficient heuristics provide satisfactory results, within 20% of the optimal solution.
Type de document :
Communication dans un congrès
EuroPar - 20th International European Conference on Parallel Processing, Aug 2014, Porto, Portugal. 8632, pp.11, 2014, 〈10.1007/978-3-319-09873-9_51〉
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01059365
Contributeur : Equipe Roma <>
Soumis le : jeudi 16 octobre 2014 - 15:43:03
Dernière modification le : vendredi 20 avril 2018 - 15:44:27
Document(s) archivé(s) le : samedi 17 janvier 2015 - 10:46:27

Fichier

europar.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Guillaume Aupy, Anne Benoit, Matthieu Journault, Yves Robert. Power-aware replica placement in tree networks with multiple servers per client. EuroPar - 20th International European Conference on Parallel Processing, Aug 2014, Porto, Portugal. 8632, pp.11, 2014, 〈10.1007/978-3-319-09873-9_51〉. 〈hal-01059365〉

Partager

Métriques

Consultations de la notice

278

Téléchargements de fichiers

82