8481 articles  [version française]

inria-00630292, version 1

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

Anne Benoit () a, 1, 2, Hubert Larchevêque () 3, 4, Paul Renaud-Goud () a, 1, 2

N° RR-7750 (2011)

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.

  • a –  École Normale Supérieure de Lyon
  • 1:  GRAAL (INRIA Grenoble Rhône-Alpes / LIP Laboratoire de l'Informatique du Parallélisme)
  • CNRS : UMR5668 – INRIA – École Normale Supérieure - Lyon – Université Claude Bernard - Lyon I – Laboratoire d'informatique du Parallélisme
  • 2:  Laboratoire de l'Informatique du Parallélisme (LIP)
  • Université de Lyon – CNRS : UMR5668 – INRIA – École Normale Supérieure - Lyon – Université Claude Bernard - Lyon I
  • 3:  CEPAGE (INRIA Bordeaux - Sud-Ouest)
  • INRIA – CNRS : UMR5800 – Université Sciences et Technologies - Bordeaux I – École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)
  • 4:  Laboratoire Bordelais de Recherche en Informatique (LaBRI)
  • CNRS : UMR5800 – Université Sciences et Technologies - Bordeaux I – École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB) – Université Victor Segalen - Bordeaux II
  • Domain : Computer Science/Distributed, Parallel, and Cluster Computing
  • Keywords : Replica placement – distance constraints – optimal algorithms – approximation algorithms – tree networks – binary tree – single vs multiple policy.
  • Internal note : RR-7750
  • Available versions :  v1 (2011-10-10) v2 (2012-02-03)
 
  • inria-00630292, version 1
  • http://hal.inria.fr/inria-00630292
  • oai:hal.inria.fr:inria-00630292
  • From: Anne Benoit <>
  • Submitted on: Saturday, 8 October 2011 15:13:45
  • Updated on: Tuesday, 11 October 2011 15:10:33