Modeling and Practical Evaluation of a Service Location Problem in Large Scale Networks

Abstract

Nous considérons une généralisation d'un problème d'optimisation classique lié au placement de serveurs et de réplicats dans les réseaux. Plus précisément, nous supposons qu'un ensemble d'utilisateurs au sein d'un réseau souhaite accéder à un service particulier proposé par un ensemble de fournisseurs de ce service. L'objectif est alors d'identifier un ensemble de fournisseurs de service capable d'offrir suffisamment de ressources pour répondre aux requêtes des clients. Par ailleurs, une certaine qualité de service relativement aux temps de communications est désirable. Une répartition judicieuse des serveurs dans le réseau offrirait également de bonnes propriétés de tolérance aux pannes. Nous modélisons ce problème comme une variante de Bin Packing, le Bin Packing avec Contrainte de Distance (BPDC en anglais) où le but est de construire un minimum de groupes (i.e. de choisir un nombre minimal de serveurs) de telle sorte que (i) chaque client est associé à exactement un serveur, (ii) la capacité dudit serveur est suffisante pour répondre aux requêtes des clients qui lui sont associés et (iii) la distance entre deux clients associés au même serveur est minimisée. Nous prouvons que ce problème est inapproximable même en utilisant des techniques d'augmentation de ressources : le nombre de groupes obtenus en utilisant des algorithmes s'exécutant en temps polynomial et autorisés à construire des groupes de diamètre au plus b*dmax, avec b>1, est comparé au nombre de groupes d'une solution optimale construisant des groupes de diamètre au plus dmax. D'un côté, nous prouvons que (i) si b=(2-e), BPDC est inapproximable à facteur constant, pour tout e>0; et que (ii) BPDC est inapproximableà un facteur inférieur à 3/2 même en utilisant de l'augmentation de ressources. D'un autre côté, si b=2, nous proposons un algorithme s'exécutant en temps polynomial pour BPDC assurant un facteur d'approximation de 7/3 dans le cas général. Nous montrons également comment transformer un algorithme d'approximation pour BPDC en un algorithme d'approximation pour le K-centre non uniforme avec capacités, et vice-versa. Enfin, nous présentons une comparaison qualitative de nos résultats pour BPDC en utilisant plusieurs outils de plongement de l'espace des latences d'Internet, comme Sequoia et Vivaldi.