Description
Date depot: 1 janvier 1900
Titre: Localisation et affectation : application aux réseaux de contenus
Directeur de thèse:
Philippe CHRÉTIENNE (LIP6)
Directeur de thèse:
Pierre FOUILHOUX (LIPN)
Domaine scientifique: Sciences et technologies de l'information et de la communication
Thématique CNRS : Non defini
Resumé:
Depuis quelques années, Internet est devenu un outil incontournable pour les entreprises et les particuliers. Pour les premières, c'est un vecteur de croissance important, et le support pour l'invention de nouveaux services. Pour les seconds, c'est l'occasion de profiter de contenus nouveaux sur les nombreux équipements connectés du foyer, depuis le traditionnel ordinateur jusqu'aux consoles de jeux et télévisions.
Les réseaux de télécommunications sont la structure qui permet à tous ces acteurs de s'échanger l'information. Déployés à travers le monde, ils sont chargés d'acheminer les fichiers depuis les sites des compagnies jusqu'aux utilisateurs. Or on assiste aujourd'hui à l'explosion de services de distribution de vidéos, que cela soient les bandes annonces ou les films des studios de cinéma, les clips proposés par les artistes, et plus généralement n'importe quelle création qu'un particulier souhaite partager avec le plus grand nombre. De plus, la qualité de ces contenus est en constante augmentation afin de proposer des films en plus haute définition ou intégrant de nouvelles technologies comme la 3D.
En pratique, cela se traduit par une taille de fichiers de plus en plus importante, ce qui conduit à des congestion sur le réseau. Les fournisseurs d'accès à internet doivent en conséquence adapter leurs infrastructures pour satisfaire les nouveaux usages de leurs utilisateurs.
La solution a pendant longtemps consisté en l'augmentation des débits des accès internet et la pose de nouveaux câbles, mais cela se révèle aujourd'hui techniquement plus difficile et très cher, en plus de répondre de manière incomplète au problème. Une alternative prometteuse propose de répliquer le contenu sur des équipements, appelés caches, que l'on déploierait dans le réseau au plus proche des utilisateurs. Beaucoup de questions se posent néanmoins : où placer ces caches ? Combien faut-il en acheter sachant qu'ils peuvent être très couteux ? Quel contenu faut-il y répliquer, et en quelle proportion ? L'objet de cette thèse est d'apporter une réponse à ces questions en se basant sur un cas spécifique qui est le service de Vidéo à la Demande, ou VoD.
Nous présentons dans un premier temps les outils de recherche opérationnelle utilisés, donnons les concepts et les définitions utiles pour la suite du manuscrit.
Nous faisons ensuite un état de l'art des problèmes proches de celui auquel on fait face, et des réponses et méthodes proposées pour les résoudre.
Par la suite, nous explicitons les caractéristiques d'un service de VoD, et étudions plus particulièrement les questions que se pose un fournisseur d'accès à internet lorsqu'il souhaite déployer des caches sur son réseau.
Nous traitons ensuite un premier problème issu de ces questions, appelé 2-p-médian, consistant à décider l'ouverture de sites dans un réseau et affecter des clients à deux sites ouverts. Nous proposons un algorithme polynomial utilisant la programmation dynamique pour résoudre le problème dans le cas où le réseau considéré est un arbre.
Nous introduisons un problème nouveau que l'on appelle Location-Dispatching, consistant à placer des équipements dans un réseau, y disposer des répliques d'objets et affecter les clients de manière à ce qu'ils aient un accès à tous les objets. Nous donnons une formulation sous forme de programme linéaire en nombre entiers, et proposons une étude polyédrale du polytope associé.
Nous proposons ensuite de nouvelles inégalités valides appelées Integrity Hop Cost pour ce problème, et étudions leurs propriétés polyédrales. Nous concevons un algorithme de coupes et branchements et conduisons des expérimentations numériques.
Nous proposons par la suite de nouvelles formulations pour les problèmes présentés plus tôt, et comparons expérimentalement leurs efficacités à l'aide de solveur de programme linéaire en nombres entiers.
Enfin, nous construisons et étudions des instances proches de la réalité, et donnons des réponses aux questions que se posent le décideur qui souhaite déployer des caches sur un réseau afin d'améliorer les performances d'un service de distribution de fichiers.
Doctorant.e: Segura Jean-Mathieu