Strategies for replica placement in tree networks

(eng) 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. (fre) Dans ce rapport nous présentons et comparons plusieurs politiques de placement de ré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'emplacement des 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ées par un seul serveur, à savoir le plus proche du client dans l'arbre. Nous introduisons deux nouvelles politiques de placement. Dans la première, chaque client a toujours un serveur unique, mais ce dernier peut être situé n'importe où sur le chemin qui mène du client à la racine dans l'arbre. Avec la deuxième politique, les requêtes d'un même client 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éduire fortement le coût total de la réplication. Un autre objectif de ce travail est l'analyse de l'impact de l'hétérogénéité de la plate-forme, à la fois d'un point de vue théorique et 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 nouvelles politiques. Sur le plan pratique, nous concevons des heuristiques polynomiales pour les instances combinatoires du problème. Nous comparons les performances de ces heuristiques en les rapportant à une borne inférieure absolue sur le coût total de la réplication; cette borne est obtenue par relaxation d'un programme linéaire en nombre entiers qui caractérise la solution optimale du problème.36 pages, figures, graphiques, 13 références bibliographique