Strategies for Replica Placement in Tree Networks

In this paper, we discuss and compare 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. The standard approach in the literature is to enforce that all requests of a client be served by the closest server in the tree. We introduce and study two new policies. In the first policy, all requests from a given client are still processed by the same server, but this server can be located anywhere in the path from the client to the root. In the second policy, the requests of a given client can be processed by multiple servers. One major contribution of this paper is to assess the impact of these new policies on the total replication cost. Another important goal is to assess the impact of server heterogeneity, both from a theoretical and a practical perspective. In this paper, we establish several new complexity results, and provide several efficient polynomial heuristics for NP-complete instances of the problem. These heuristics are compared to an absolute lower bound provided by the formulation of the problem in terms of the solution of an integer linear program.Dans ce rapport nous présentons et comparons plusieurs politiques de placement derépliques sur des arbres, prenant en compte à la fois des contraintes liées à la capacitéde traitement de chaque serveur et des contraintes de type QoS (qualité de service).Les requêtes des clients sont connues avant exécution, alors que le nombre et l'emplacementdes répliques (serveurs) sont à déterminer par l'algorithme de placement.L'approche classique impose que toutes les requêtes d'un client donné soient traitéespar un seul serveur, à savoir le plus proche du client dans l'arbre. Nous introduisonsdeux nouvelles politiques de placement. Dans la première, chaque client a toujours unserveur unique, mais ce dernier peut être situé n'importe où sur le chemin qui mènedu client à la racine dans l'arbre. Avec la deuxième politique, les requêtes d'un mêmeclient peuvent être traitées par plusieurs serveurs sur ce même chemin.Nous montrons que ces deux nouvelles politiques de placement sont à même de réduirefortement le coût total de la réplication. Un autre objectif de ce travail est l'analysede l'impact de l'hétérogénéité de la plate-forme, à la fois d'un point de vue théoriqueet pratique. Sur le plan théorique, nous établissons plusieurs résultats de complexité,dans les cadres homogène et hétérogène, pour l'approche classique et les nouvellespolitiques. Sur le plan pratique, nous concevons des heuristiques polynomiales pourles instances combinatoires du problème. Nous comparons les performances de cesheuristiques en les rapportant à une borne inférieure absolue sur le coût total de laréplication; cette borne est obtenue par relaxation d'un programme linéaire en nombre entiers qui caractérise la solution optimale du problème