L’augmentation et le renforcement des usages d’Internet rend nécessaire l’évolution des réseaux existants. Cependant, on constate de fortes inégalités entre les zones urbaines, bien desservies et qui concentrent l’essentiel des investissements, et les zones rurales, mal desservies etdélaissées. Face à cette situation, les utilisateurs de ces zones se tournent vers d’autres moyensd’accès, et notamment vers les accès Internet par satellite. Cependant, ces derniers souffrentd’une limitation qui est le délai important induit par le temps de propagation du signal entre la terre et l’orbite géostationnaire. Dans cette thèse, nous nous intéressons à l’utilisation simultanée d’un réseau d’accès terrestre, caractérisé par un faible débit et un faible délai, et d’un réseau d’accès satellite, caractérisé par une forte latence et un débit plus important. D’autre part, les réseaux dediffusion de contenus ou CDNs, constitués d’un grand nombre de serveurs de cache, apportentune réponse à l’augmentation du trafic et des besoins en termes de latence et de débit.Cependant, localisés dans les réseaux de cœur, les caches restent éloignés des utilisateurs etn’atteignent pas les réseaux d’accès. Ainsi, les fournisseurs d’accès Internet (FAI) se sontintéressés au déploiement de ces serveurs au sein de leur propre réseau, que l’on appelle alorsTelCo CDN. La diffusion des contenus nécessite idéalement l’interconnexion des opérateurs CDNavec les TelCo CDNs, permettant ainsi la délégation de la diffusion à ces derniers. Ils sont alorsen mesure d’optimiser la diffusion des contenus sur leur réseau dont ils ont une meilleureconnaissance. Ainsi, nous nous intéresserons à l’optimisation de la livraison de contenus sur unréseau hybride satellite / terrestre intégré à une chaîne de livraison CDN. Nous nous attacheronsdans un premier temps à décrire une architecture permettant, grâce à l’interconnexion de CDNs,de prendre en charge la diffusion des contenus sur le réseau hybride. Dans un second temps,nous étudierons l’intérêt de la connaissance des informations apportées par le contexte CDN pour le routage sur une telle architecture. Dans ce cadre, nous proposerons un mécanisme de routage fondé sur la taille des contenus. Finalement, nous montrerons la supériorité de notre approche sur l’utilisation du protocole de transport multichemin MP-TCP

L’augmentation et le renforcement des usages d’Internet rend nécessaire l’évolution des réseaux existants. Cependant, on constate de fortes inégalités entre les zones urbaines, bien desservies et qui concentrent l’essentiel des investissements, et les zones rurales, mal desservies etdélaissées. Face à cette situation, les utilisateurs de ces zones se tournent vers d’autres moyensd’accès, et notamment vers les accès Internet par satellite. Cependant, ces derniers souffrentd’une limitation qui est le délai important induit par le temps de propagation du signal entre la terre et l’orbite géostationnaire. Dans cette thèse, nous nous intéressons à l’utilisation simultanée d’un réseau d’accès terrestre, caractérisé par un faible débit et un faible délai, et d’un réseau d’accès satellite, caractérisé par une forte latence et un débit plus important. D’autre part, les réseaux dediffusion de contenus ou CDNs, constitués d’un grand nombre de serveurs de cache, apportentune réponse à l’augmentation du trafic et des besoins en termes de latence et de débit.Cependant, localisés dans les réseaux de cœur, les caches restent éloignés des utilisateurs etn’atteignent pas les réseaux d’accès. Ainsi, les fournisseurs d’accès Internet (FAI) se sontintéressés au déploiement de ces serveurs au sein de leur propre réseau, que l’on appelle alorsTelCo CDN. La diffusion des contenus nécessite idéalement l’interconnexion des opérateurs CDNavec les TelCo CDNs, permettant ainsi la délégation de la diffusion à ces derniers. Ils sont alorsen mesure d’optimiser la diffusion des contenus sur leur réseau dont ils ont une meilleureconnaissance. Ainsi, nous nous intéresserons à l’optimisation de la livraison de contenus sur unréseau hybride satellite / terrestre intégré à une chaîne de livraison CDN. Nous nous attacheronsdans un premier temps à décrire une architecture permettant, grâce à l’interconnexion de CDNs,de prendre en charge la diffusion des contenus sur le réseau hybride. Dans un second temps,nous étudierons l’intérêt de la connaissance des informations apportées par le contexte CDN pour le routage sur une telle architecture. Dans ce cadre, nous proposerons un mécanisme de routage fondé sur la taille des contenus. Finalement, nous montrerons la supériorité de notre approche sur l’utilisation du protocole de transport multichemin MP-TCP / The increase and reinforcement of Internet uses make necessary to improve existing networks.However, we observe strong inequalities between urban areas, well served and which concentratethe major part of investments, and rural areas, underserved and forkasen. To face this situation,users in underserved areas are moving to others Internet access, and in particular satellite Internetaccess. However, the latter suffer from a limitation which is the long delay induced by thepropagation time between the earth and the geostationnary orbit. In this thesis, we are interresedin the simultaneous use of a terrestrial access network, characterized by a low delay and a lowthroughput, and a satellite access network, characterized by a high throughput and an long delay.Elsewhere, Content Delivery Networks (CDNs), consisting of a large number of cache servers,bring an answer to the increase in trafic and needs in terms of latency and throughput. However,located in core networks, cache servers stay far from end users and do not reach accessnetworks. Thus, Internet Service Providers (ISPs) have taken an interest in deploying their ownCDNs, which will be referred to as TelCo CDNs. The content delivery ideally needs theinterconnection between CDN operators and TelCo CDNS, allowing the delegation of the contentdelivery to the TelCo CDNs. The latter are then able to optimize the content delivery on theirnetwork, for which they have a better knowledge. Thus, we will study the optimization of thecontents delivery on a hybrid satellite / terrestrial network, integrated in a CDN delivery chain. Wewill initially focus on the description of a architecture allowing, thanks to a CDN interconnection,handling contents delivery on the hybrid network. In a second stage, we will study the value of theinformation provided by the CDN context in the routing on such architecture. In this framework, wewill propose a routing mechanism based on contents size. Finally, we will show the superiority ofour approach over the multipath transport protocol MP-TCP

Le caching de réseau peut aider àgérer l'explosion du trafic sur Internet et àsatisfaire la Qualité d'Expérience (QoE)croissante demandée par les usagers.Néanmoins, les techniques proposées jusqu'àprésent par la littérature scientifique n'arriventpas à exploiter tous les avantages potentiels. Lestravaux de recherche précédents cherchent àoptimiser le hit ratio ou d'autres métriques deréseau, tandis que les opérateurs de réseau(ISPs) sont plus intéressés à des métriques plusconcrètes, par exemple le coût et la qualitéd'expérience (QoE). Pour cela, nous visonsdirectement l'optimisation des métriquesconcrètes et montrons que, ce faisant, on obtientdes meilleures performances.Plus en détail, d'abord nous proposons desnouvelles techniques de caching pour réduire lecoût pour les ISPs en préférant stocker lesobjets qui sont les plus chères à repérer.Nous montrons qu'un compromis existe entre lamaximisation classique du hit ratio et laréduction du coût.Ensuite, nous étudions la distribution vidéo,comme elle est la plus sensible à la QoE etconstitue la plus part du trafic Internet. Lestechniques de caching classiques ignorent sescaractéristiques particulières, par exemple le faitqu'une vidéo est représentée par différentesreprésentations, encodées en différents bit-rateset résolutions. Nous introduisons des techniquesqui prennent en compte cela.Enfin, nous remarquons que les techniquescourantes assument la connaissance parfaite desobjets qui traversent le réseau. Toutefois, laplupart du trafic est chiffrée et du coup toutetechnique de caching ne peut pas fonctionner.Nous proposons un mécanisme qui permet auxISPs de faire du caching, bien qu’ils ne puissentobserver les objets envoyés. / Network caching can help copewith today Internet traffic explosion and sustainthe demand for an increasing user Quality ofExperience. Nonetheless, the techniquesproposed in the literature do not exploit all thepotential benefits. Indeed, they usually aim tooptimize hit ratio or other network-centricmetrics, e.g. path length, latency, etc., whilenetwork operators are more focused on moremore practical metrics, like cost and quality ofexperience. We devise caching techniques thatdirectly target the latter objectives and showthat this allows to gain better performance.More specifically, we first propose novelstrategies that reduce the Internet ServiceProvider (ISP) operational cost, bypreferentially caching the objects whose cost ofretrieval is the largest.We then focus on video delivery, since it is themost sensitive to QoE and represents most ofthe Internet traffic. Classic techniques ignorethat each video is represented by differentrepresentations, encoded at different bit-ratesand resolutions. We devise techniques that takethis into account.Finally, we point out that the techniquespresented in the literature assume the perfectknowledge of the objects that are crossing thenetwork. Nonetheless, most of the traffic todayis encrypted and thus caching techniques areinapplicable. To overcome this limit, Wepropose a mechanism which allows the ISPs tocache, even without knowing the objects being

Cette thèse porte principalement sur l'équilibrage de charge dans de grands graphes aléatoires. En informatique, un problème d'équilibrage de charge survient lorsque différentes tâches ont besoin d'accéder à un même ensemble de points de ressources. Il faut alors décider quelles ressources spécifiques seront allouées à quelles tâches. Suivant le contexte, les notions de "tâche" et de "ressource" peuvent avoir différentes interprétations. Afin de prendre des exemples concrets, on se concentrera sur deux applications en particulier: - un système de hachage à choix multiples (plus précisément, le "cuckoo hashing"). L'objectif est ici d'allouer des cellules d'un tableau à des objets, afin de pouvoir ensuite vérifier facilement la présence d'un objet et récupérer les données associées. Les tâches sont liées aux objets à stocker, et les ressources sont les cellules du tableau. - un réseau de distribution de contenu distribué, au sens où les contenus peuvent être stockés sur une multitude de petits serveurs aux capacités individuelles très limitées. Ici, les tâches sont des demandes de téléchargement (ou requêtes) pour un contenu et les ressources sont liées aux serveurs et à la façon dont leurs espaces de stockage sont utilisés. Le problème d'équilibrage de charge consiste à décider quel serveur va servir quelle requête. Les contraintes locales portant sur chaque ressource (en quelle quantité est-elle disponible et pour quelles tâches est-elle convenable?) ainsi que la charge de travail associée avec chaque tâche peuvent être représentées efficacement sur un graphe biparti, avec des contraintes de capacité sur ses sommets et ses arêtes. De plus, en pratique, les systèmes considérés sont souvent de très grande taille (avec parfois des milliers de tâches et de points de ressources différents) et relativement aléatoires (que ce soit par choix ou une conséquence de leur grande taille). Une modélisation à l'aide de grands graphes aléatoires est donc souvent pertinente. L'ensemble des solutions envisageables pour un problème d'équilibrage de charge donné étant vaste, il est primordial de commencer par déterminer des bornes sur les performances que l'on peut espérer. Ainsi, on considérera dans un premier temps une solution optimale du problème (même si elle ne serait pas réalisable avec des contraintes pratiques). Les performances d'une telle solution peuvent être obtenues en étudiant les appariements de taille maximum dans un grand graphe aléatoire, ce que l'on réalisera à l'aide de la méthode de la cavité. Cette méthode vient de l'étude des systèmes désordonnés en physique statistique, et on s'attachera ici à l'appliquer de manière rigoureuse dans le cadre que l'on considère. Dans le contexte du cuckoo hashing, les résultats obtenus permettent de calculer le seuil sur la charge du système (le nombre d'objets à insérer par rapport à la taille du tableau) en-dessous duquel on peut construire une table de hachage correcte avec grande probabilité dans un grand système, et également de traiter de manière similaire de variantes de la méthode de hachage basique qui tentent de diminuer la quantité d'aléa nécessaire au système. Au-delà du problème d'équilibrage de charge, dans le cadre des réseaux de distributions de contenu distribués, un second problème se pose: comment décider quel contenu stocker et en quelle quantité, autrement dit comment répliquer les contenus? On appelle ce second problème un problème d'allocation de ressources. A nouveau, l'étude déjà réalisée permet de quantifier l'efficacité d'une politique de réplication fixée en supposant que la politique d'équilibrage de charge fonctionne de manière optimale. Il reste cependant à optimiser la politique de réplication de contenus utilisée, ce que l'on effectue dans un régime où l'espace de stockage disponible au niveau de chaque serveur est important par rapport à la taille d'un contenu. Finalement, afin de quantifier maintenant les performances minimales atteignables en pratique, on s'intéressera aux mêmes questions lorsque la politique d'équilibrage de charge utilisée est un simple algorithme glouton. Cette étude est réalisée à l'aide d'approximations de champs moyen. On utilisera également les résultats obtenus afin de concevoir des politiques de réplication de contenus adaptatives.