Direction de recherche : Philippe CHRÉTIENNE

Co-encadrement : GOURDIN Eric, FOUILHOUX Pierre

Localisation et affectation : application aux réseaux de contenus

Sur le réseau Internet, les usagers demandent un accès de plus en plus rapide à des contenus de plus en plus volumineux. Notamment, le service de Vidéo à la Demande (VoD) voit la taille des données échangées augmenter fortement avec l'arrivée de la haute définition et des vidéos en 3D. Les réseaux physiques des fournisseurs d’accès à Internet doivent ainsi sans cesse s'adapter à l'augmentation des demandes de téléchargements. La solution qui a pendant longtemps consisté à augmenter les débits en posant de nouveaux câbles connaît aujourd'hui ses limites. Une nouvelle approche efficace consiste à déployer des réseaux de distribution de contenus (CDN) qui peuvent être décrits comme un ensemble d'équipements, appelés caches, où les données sont dupliquées et stockées au plus proche des utilisateurs. Lors de la conception d'un CDN, plusieurs questions se posent quant au nombre, à la dimension et la localisation des caches, de manière à servir au mieux l'usager. En nous plaçant du point de vue d'un fournisseur d'accès à Internet, nous montrons que la conception d'un service de VoD s'inscrit dans la problématique de localisation et d'affectation de ressources en recherche opérationnelle. En particulier, nous nous intéressons à deux problèmes mêlant localisation et affectation: le problème du 2-p-Médian et le problème de Location-Dispatching. Nous montrons que, dans le cas où le réseau considéré est un arbre, le premier problème est polynomial. Nous formulons le second problème comme un programme linéaire en nombre entiers et nous proposons une étude polyédrale du polytope associé, ainsi que de nouvelles inégalités valides. A partir de cette étude, nous déduisons un algorithme de coupes et branchements pour résoudre le problème. Nous proposons également de nouvelles formulations entières des problèmes de localisation et d'affectation et nous comparons expérimentalement leurs efficacités. En conclusion nous tentons de répondre aux questions posées par la conception de CDN à partir des différentes approches étudiées dans ce document.

Publications 2009-2014

• 2014
  • Ph. Chrétienne, P. Fouilhoux, E. GOURDIN, J. Segura : “The Location-Dispatching Problem: polyhedral results and Content Delivery Network Design”, Discrete Applied Mathematics, vol. 164 (1), pp. 68-85, (Elsevier) (2014)
• 2011
  • J. Segura : “Localisation et affectation : application aux réseaux de contenus”, thèse, soutenance 07/02/2011, direction de recherche Chrétienne, Philippe, co-encadrement : Gourdin, Eric, Fouilhoux, Pierre (2011)
• 2010
  • Ph. Chrétienne, P. Fouilhoux, E. GOURDIN, J. Segura : “The Location-Dispatching Problem: polyhedral results and Content Delivery Network Design”, International Symposium on Combinatorial Optimization (ISCO 2010), Electronic Notes in Discrete Mathematics, Elsevier., vol. 36, Hammamet, Tunisia, pp. 867-874, (Elsevier) (2010)
• 2009
  • Ph. Chrétienne, P. Fouilhoux, E. GOURDIN, J. Segura : “Localisation de caches dans un réseau de distribution de contenu”, 10^e Congrès de la Société Française de Recherche Opérationnelle et d'Aide à la Décision (ROADEF 2009), Nancy, France, pp. 94-95 (2009)