Jiayi Liu

Thèse De Doctorat

Présentée Par

Professeur M Laurent Schumacher

Professeur M David Coudert

Professeur M Antoine Beugnard

M Juan

Pedro Munoz Gea

M Gwendal Simon

Yaning Liu

Jimmy Leblet

Fen Zhou

Eliya Buyukkaya

Yiping Chen

Zhe Li

Xu Zhang

Catherine Rosenberg

Multiple Live Videos Delivery in Underprovisioned Networks

Keywords: Live Streaming, P2P, Multioverlay, CDN, rate-adaptive streaming, DASH, Underprovisioned System

During this thesis, I have been able to work in both Brest and Rennes, where I met many brilliant scientists, colleagues

As a result, scientists have observed a formidable growth of Internet trac dominated by the videos. A consequent challenge is the bandwidth availability problem a delivery network can be insuciently provisioned under the heavy transmission burden imposed by the huge volume of video trac. Such underprovisioning problem is more severe for live videos due to its real-time requirement.

In this thesis, we focus on bandwidth ecient video delivery solutions for live streaming in underprovisioned video delivery networks. More specically, we target to capture the aforementioned trends to nd solutions for: (1) user-generated live streaming, and (2) rate-adaptive live streaming. We nally realized the following contributions:

First of all, we built an multioverlay peer-to-peer (P2P) video sharing system which allows ordinary Internet users to broadcast their own live videos. Typically, such a system consists of multiple independent P2P live video streaming systems, and faces the problem of nding a suitable allocation of peer upload bandwidth. So far, no ecient solution has been proposed for the important case when the overall system is underprovisioned, that is, when peers do not have enough upload bandwidth to ensure a diusion of videos at full quality. We designed various objective functions for this upload bandwidth allocation problem and showed how optimal solutions can be eciently computed. Simulation results demonstrated that our solutions improve on existing algorithms in terms of video quality.

Then, we studied the problem of delivering live rate-adaptive streams in the content delivery network (CDN). For live streaming in underprovisioned CDN delivery network, the goal is to maximize the throughput of the network. Previous theoretical models that deal with streaming capacity problems do not capture the emerging reality raised by rate-adaptive streaming. Thus, we identied a new discretized streaming model, which is more suitable for multiple live video channels in modern CDNs. For this model we formulated a general optimization problem through Integer Linear Programming (ILP) and showed that it is NP-complete. Further, we presented a fast, easy to implement, and near-optimal algorithm with approved approximation ratios for a specic scenario. This work is the rst step towards streaming multiple live rate-adaptive videos in CDN and provides a fundamental theoretical basis for deeper investigation.

Last, we further extended the discretized streaming model into an user-centric one which maximizes the overall satisfaction of an user population. The performance of this user-centric discretized streaming model is approved through a set of toy-CDN simulations. Further, we presented a practical system, which eciently utilizes CDN infrastructure to deliver live video streams to viewers in dynamic and large-scale CDNs. The benets of our approaches on reducing the CDN infrastructure capacity is validated through a set of realistic trace-driven large-scale simulations.

All in one, this thesis explores bandwidth ecient live video delivery solutions xiii Résumé Évolution des technologies de transmission de ux vidéo en direct Le mot streaming correspond à la technique de transfert de contenu vidéo sous forme d'un ux régulier et continu. La transmission de ux vidéo en ligne peut être classiée en deux types: vidéo à la demande (abrégée en VoD de l'anglais Video on Demand) et ux vidéo en direct (terme anglais, live streaming). Pour les services de vidéo à la demande, le service est rendu selon la demande des client, donc les contenus vidéos sont consultables à tout moment. Cependant, le service de ux vidéo en direct nécessite l'envoi de contenu vidéo en temps réel (ou en léger diéré) à un large public depuis l'Internet. À cause de l'exigence de temps réel, la transmission de ux vidéo en direct est beaucoup plus dicile que VoD.

Depuis la première émission en direct en ligne réalisée par Severe Tire Damage le 24 juin 1993, la transmission de vidéo en ligne est devenue l'un des plus grands et plus populaires domaines dans le monde de l'Internet. Il y a plusieurs types d'applications/platformes existant qui fournissent diérents types de contenus à des millions de utilisateurs à chaque seconde. A titre d'exemple, plus de 1,000,000 utilisateurs simultanés ont regardé Jeux Olympiques de Beijing depuis la platforme PPLive [ppl]. Sur justin.tv, une plateforme de vidéo en direct sur le Web, une nouvelle vidéo commence chaque seconde, et 300 millions de vidéos sont vues mensuellement [jus]. Ce sont seulement deux exemples parmi beaucoup d'autres.

Pourtant, la distribution des vidéos en direct pour des milliers d'utilisateurs via l'Internet n'est pas facile. Au début, les protocoles IP multicast ont été proposés pour réduire la charge du réseau [START_REF] Deering | Multicast routing in datagram internetworks and extended lans[END_REF]. L'idée fondamentale de ces protocoles est d'envoyer un seul ux de données à partir du fournisseur de contenu vers de multiple destinataires qui sont membres d'un groupe multicast. Par exemple, les protocoles SRM [FJL + 95] et RMTP [START_REF] Paul | Reliable multicast transport protocol (rmtp)[END_REF] sont des études réalisées dans ce domaine. Cepen- dant, à cause de sa complexité, la multicast IP est peu déployé: il a besoin de modications sur l'infrastructure, d'implementer des caractéristiques de couche supérieure (tel que le contrôle de congestion, etc.), et de maintenir l'état de chaque groupe à la couche IP. L'alternative proposée par les scientiques consiste à gérer la fonctionnalité de multicast au niveau de la couche application en construisant des réseaux superposés (réseau overlay) au niveau applicatif. A ce sujet, deux approches principales ont été proposées: les systèmes pair-à-pair (P2P, de l'anglais peer-to-peer) et les Content Delivery Networks (CDNs). xiv Résumé Pour les deux approches, la première question à régler est le problème de passage à l'échelle, en d'autres mots, la capacité de s'adapter à un changement du nombre d'utilisateurs de plusieurs ordres de grandeur. Les systèmes P2P (voir par exemple [LGL08, YV07, hCRSZ00, ppl]) sont intrinsèquement capable de passage à l'échelle, parce que les utilisateurs partagent leurs ressources avec d'autres utilisateurs, donc plus il y a des participants dans le système, plus il y a de ressources. Chaque pair joue à la fois le rôle de serveur et de client. Cette caractéristique résout le problème du passage à l'échelle et permet à un grand nombre d'utilisateurs de proter du service. Les utilisateurs organisent un réseau P2P overlay pour la diusion de la vidéo. La démocratisation de producteurs de vidéos en direct. C'est la beauté de l'Internet de changer la production de contenu de la part des quelques magnats des xv médias à des millions d'utilisateurs ordinaires. Aujourd'hui, les vidéos en direct en ligne ne sont pas générées uniquement par un petit groupe d'éditeurs bien identiés qui émettent les événements importants: comme les dernieres nouvelles, politiques et sports, etc. Maintenant, un spectateur peut diuser un match depuis un stade; un adepte des jeux vidéos peut diuser le vidéo capturée de son écran quand il joue du jeux vidéo en ligne; ou encore, une ligue sportive de jeunesse locale peut émettre les matchs pour les parents à regarder, etc. Il existe plusiere des plates-formes qui permettent de diuser les vidéos en direct généré par les utilisateurs. De plus, les applications de réseau social (abrégée en OSN de l'anglais Online Social Network) permettent à ces sources de promouvoir leur propre vidéos. Par exemple, ces platesformes comprennent le plate-forme justin.tv [jus], le plate-forme ustream [ust], et le plate-forme Xre [x]. Ces services attirent une grande population: par exemple, Xre, qui permet aux joueurs du jeu en ligne massivement multijoueur (MMOG, de l'anglais massively multiplayer online game) de capturer des vidéos en direct à partir de leur écran de jeu et de les diuser à d'autres joueurs, annonce plus de 20 millions de joueurs [START_REF] Shen | The xre online meta-gaming network: Observation and high-level analysis[END_REF].

L'hétérogénéité des consommateurs de vidéos. Aujourd'hui, les gens peuvent regarder des vidéos depuis leur terminaux de nouvelle génération (tels que les smartphones et tablettes) n'importe où et à n'importe quel moment. Typiquement, il est devenu courant pour les utilisateurs mobiles de proter des divertissements vidéos via des connexions sans l (3G et WiFi). Un rapport récent de Cisco montre que la vidéo a dépassé 50% du trac mobile à la n de l'année 2012 [cisa]. Dans le même temps, le rapport souligne la plus grande diversication des terminaux: les smartphones et les appareils plus récents représentent davantage de trac qu'avant. Une étude [nbc] a montré que pendant les Jeux Olympiques de Londres, 45% des demandes des vidéos sont réalisées à partir d'appareils mobiles (tablettes et téléphones). Ces appareils ont des tailles d'écran diérentes, donc ils acceptent des vidéo avec des résolutions diérentes. De même, ils sont connectés à l'Internet depuis des accès diérents, ainsi ils peuvent lire des vidéos ayant des débits diérents. Par conséquent, ils ont des exigences diérentes en streaming. Pour illustrer ces propos, la dernière génération de télévisions connectées est capable d'acher une vidéo avec des résolution jusqu'à 1080p, alors qu'un utilisateur de smartphone est seulement autorisé à regarder de la vidéo en 360p. L'Adaptatif Bit Rate Streaming a été conçu pour servir une population hétérogène d'utilisateurs tout en garantissant une bonne qualité d'expérience (QoE) pour tout le monde. Dans le streaming adaptatif, un ux vidéo a des multiples représentations, chacune correspondant à une certaine qualité de la vidéo avec une certaine résolution, et un certain débit. Cela permet au client de passer de façon dynamique d'une vidéo à l'autre en fonction de la variation de la qualité de sa connection réseau. Aujourd'hui, le streaming adaptatif est de plus en plus utilisé dans les architectures utilisant des CDN. Cette technique est désormais normalisée à MPEG sous le nom de DASH (Dynamic Adaptative Streaming over HTTP) [START_REF]Overview of MPEG-DASH Standard[END_REF][START_REF] Stockhammer | Dynamic adaptive streaming over http -standards and design principles[END_REF]. La standard DASH est une nouvelle étape vers une adoption plus large des technologies de streaming adaptatif Comme nous l'avons présenté, un prestataire de services doit examiner attentivement la bonne approche (soit P2P ou CDN) lors de la conception d'un système de xvi Résumé streaming en direct. Le CDN est le meilleur choix pour le streaming des vidéos adaptatif pour au moins deux raisons. D'abord, le technologie de streaming adaptatif est particulièrement ecace pour exploiter la liaison descendante disponible d'un utilisateur lorsque cet utilisateur a une connexion de réseau stable. C'est plus dicile dans les systèmes P2P où des connexions multiples et transitoires sont utilisées entre les pairs. En second lieu, les serveurs CDN peuvent orir diérentes représentations, donc il est facile de passer d'une représentation à l'autre. Le passage de représentations dans les systèmes P2P est plus dicile, car cela nécessite de réorganiser les overlays pour trouver d'autres pairs ayant le bon contenu. Dans DASH, où les morceaux de vidéos peuvent être de deux secondes seulement, le changement devient très dicile en P2P.

Au contraire, pour les vidéos en direct générés par les utilisateurs, le P2P est un meilleur choix pour les raisons suivantes. Tout d'abord, la popularité des vidéos de ces types constitue un dé majeur: (1) d'une part, un grand nombre de vidéos sont générés simultanément; (2) de l'autre côté, la plupart des vidéos sont regardés par une petite population (e.g. amis du diuseur dans les applications de réseau social).

Cette distribution de popularité est plus dicile à gérer pour un CDN, qui préfère faire du streaming avec un petit nombre de contenus à un grand nombre de n÷uds.

Deuxièmement, la limitation de système P2P pour traiter le streaming adaptatif n'a pas d'importance ici car les contenus générés par les utilisateurs peuvent rarement bénécier de l'avantage de technologie streaming adaptatif. En eet, les appareils qui capturent et initient le ux vidéo sont limitées en capacité, ainsi le ux vidéo brut est de qualité relativement médiocre et il est impossible de tirer de cette vidéo brute susamment de représentations diversiées. Par ailleurs, codage par un acteur central pour un grand nombre de vidéos provoque un coût de calcul lourd et un large délai supplémentaire.

Motivations et Dés

La motivation globale de cette thèse est de concevoir des systèmes de streaming vidéo en direct qui répondent aux tendances mentionnées ci-dessus, en particulier de vidéo en direct générée par l'utilisateur, et de vidéo en direct de streaming adaptatif. Basés sur l'observation des tendances ci-dessus, nos objectifs sont comme suit:

• Notre premier objectif est de concevoir un système qui permet aux utilisateurs de diuser leurs propres vidéos en direct en utilisant l'approche P2P.

• Le deuxième objectif est de construire un système de streaming en direct qui ore des vidéos adaptatifs depuis le réseau CDN.

Dans ces deux travaux, nous essayons de résoudre le problème de transmettre des ux vidéo en direct dans une infrastructure de livraison (l'overlay P2P et le réseau de CDN) sous la contrainte de la bande passante des n÷uds relais (des pairs et des équipements intermédiaires CDN). Comme nous l'avons dit avant, le trac vidéo occupe la première place du trac internet, et il est prévu que ce trac continue d'augmenter. En conséquence, un dé principal est la disponibilité de la bande passante dans l'infrastructure de distribution pour les deux systèmes. Donc, notre tâche xvii est de trouver les solutions ecaces en utilisant la bande passante des équipements et de concevoir des politiques de diusion pour les systèmes sous-provisionnés. Dans ce qui suit, nous discutons en détail les dés rencontrés par chaque système. Contrainte de bande passante pour le système P2P de partager les vidéos en direct générés par les utilisateurs Il y a de multiples overlay P2P dans les systèmes de partage de vidéos en direct générés par les utilisateurs. Pour chaque vidéo, un overlay P2P est formé par le diuseur et les utilisateurs (pairs) qui regardent cette vidéo en direct. Le diuseur émet sa propre vidéo en direct, les pairs participent à la diusion de la vidéo à d'autres pairs dans la même overlay P2P.

Typiquement, dans ce service, les utilisateurs peuvent regarder plusieurs vidéos en direct simultanément. Cette fonctionnalité est très appréciée par les utilisateurs.

Quelques scénarios d'exemples comprennent: (i) la TV avec multi-canal, où un utilisateur peut regarder plusieurs chaînes simultanément [START_REF] Wang | Improving multiview peer-to-peer live streaming systems with the divide-and-conquer strategy[END_REF]; (ii) le streaming multi-caméra, où un client peut regarder le même événement à partir de points de vue diérents [START_REF] Nbc | Super Bowl XLVI Live Stream Sets Trac Records[END_REF]; (iii) la coopération des joueurs MMOG, où les joueurs d'une même équipe peuvent transmettre la vidéo de leur jeu à l'autre [ABH + 11]. Cepen- dant, cette caractéristique requiert une grande disponibilité de bande passante. Dans le streaming P2P, il est largement accepté que le goulot d'étranglement des ressources provient de la bande passante montant aux pairs. La connection d'un pair à l'Internet est limité, et ce lien doit être partagé entre tous les overlays pour lesquelles le pair participe. Par conséquent, un dé majeur est le problème d'allocation de bande passante, qui consiste à trouver une allocation de bande passante (montant) de chaque pair à ses vidéos regardés (des P2P overlays).

Parfois, le système peut être sous-provisionné, c'est-à-dire que la bande passante de l'ensemble des pairs n'est pas susante pour soutenir la diusion de toutes les vidéos. En dépit de l'énorme volume de recherche sur streaming P2P, le décit des ressources a été constamment ignoré. Quand les scientiques sont confrontés à la réalité du décit de ressources [START_REF] Sweha | AngelCast: Cloud-based Peer-Assisted Live Streaming Using Optimized Multi-Tree Construction[END_REF][START_REF] Wu | On Dynamic Server Provisioning in Multichannel P2P Live Streaming[END_REF], ils ont proposé de déployer des serveurs supplémentaires comme des assistants de bande passante pour empêcher le système de devenir sous-provisionné. Cependant, cette solution n'est pas applicable à un scénario avec beaucoup d'overlays de petite taille, car il faudrait réserver et gérer un grand nombre de machines virtuelles, avec chacune générant une petite quantité de trac. Ainsi, un autre dé consiste à dénir des stratégies d'allocation de bande passante pour le système sous-provisionné, par exemple, comment partager le décit de la bande passante entre les overlays. Contrainte de bande passante pour diuser de vidéo adaptatif en direct sur CDN Le standard récent DASH résout le problème de diuser des vidéos pour un vaste ensemble d'appareils hétérogènes, cependant, il est très exigeant pour l'infrastructure de CDN: le chaîne vidéo est en eet un ensemble des ux plus petits, chacun correspondant à une représentation diérente de la vidéo. Par exemple, les vidéos HD de xviii Résumé Netix sont encodés à 14 représentations avec un taux cumulé de plus de 20 Mbps par chaîne [AGH + 12]. La conséquence est que les CDNs rencontrent un énorme problème de passage à l'échelle. Par exemple, le leader mondial de fournisseur CDN, Akamai, a récemment annoncé que son infrastructure doit être augmentée par un facteur de 100 fois dans les cinq années prochaines pour suivre à la demande de diuser des vidéos en temps-réel [START_REF] Ingram | You think the internet is big now? akamai needs to grow 100-fold[END_REF]. Le problème de passage à l'échelle est plus dicile pour les systèmes de streaming en direct que pour la VOD, pour lequel il est possible de retarder les transferts aux heures creuses [START_REF] Laoutaris | Inter-datacenter bulk transfers with netstitcher[END_REF]. Streaming en direct exige que le fournisseur de CDN dispose d'une infrastructure de distribution solide, par exemple, pour s'assurer que les équipements de l'infrastructure CDN sont capables de transmettre des ux à partir de serveurs d'origine aux serveurs edge, puis aux utilisateurs.

Des travaux réalisés précédents dans ce domaine [ASV11, AMM + 11, ZAB + 12] ont mis en évidence que la bande passante montante des équipements intermédiaires est la ressource la plus critique à gérer.

Par conséquent, le dé principal pour le CDN d'aujourd'hui est de concevoir des solutions ecaces en termes d'utilisation de la bande passante pour le système CDN malgré une infrastructure sous-provisionnée. Dans des infrastructures bien gérées, comme les CDN, les arbres sont la solution la plus ecace et robuste pour transmettre des données [START_REF] Adler | Algorithms for optimizing the bandwidth cost of content delivery[END_REF][START_REF] Andreev | Designing overlay multicast networks for streaming[END_REF]. Plus précisément, le problème est de construire un ensemble d'arbres dans le réseau de CDN pour maximiser le nombre de ux délivrés, sous les contraintes de capacité des équipements intermédiaires et la topologie de CDN.

Le streaming adaptatif est inventé pour maximiser la QoE des utilisateurs avec des appareils divers et des liens d'accès diérents. Un rapport récent sur l'expérience de l'utilisateur à regarder des vidéos en ligne révèle que les utilisateurs ont regardé des vidéos avec mauvaise qualité: 60% de tous les vidéos ont de la qualité dégradée [Con].

L'état est encore pire pour les vidéos en direct: le pourcentage de vidéos avec qualité haute (HQ de l'anglais High Quality) diminue de 60% au début de 2012 à 35% à la n pour les vidéos en direct en ligne. Cette observation illustre un autre dé qui consiste à réaliser une solution orientée sur la satisfaction des utilisateurs.

Contributions

Selon les discussions ci-dessus sur les objectifs et les dés, nous avons concentré nos eorts sur la gestion des ressources en bande passante limitées, pour le streaming vidéo en direct pour les systèmes P2P et les systèmes CDN. Nous listons les contributions de cette thèse comme suit.

Un système pair-à-pair multi-overlay pour partager les vidéos en direct • Un composant de placement de contenu décide à où placer les représentations en calculant l'utilité des représentations pour chaque serveur edge.

• Un composant de diusion de contenu crée un overlay des arbres qui exploite la capacité de l'infrastructure CDN à l'égard de l'utilité de contenu.

La performance du système est validée par des simulations basées sur traces réels à grande échelle. Les résultats montrent que le système pourrait atteindre en moyenne une satisfaction haute avec peu de coût d'infrastructure CDN dans un environnement dynamique.

Chapter 1 Introduction

In this chapter, we rst provide a brief discussion on the current status and trend of the online live video streaming services. This discussion reveals the main challenges of live video streaming for various application scenarios and types of platforms, and leads to the motivation of this thesis. Then, the main contributions of the thesis are introduced, followed by a brief outline of the organization of this dissertation at the end of this chapter. Yet, delivering live streams to thousands of users on the Internet is not trivial. At the beginning, native IP multicast was proposed [START_REF] Deering | Multicast routing in datagram internetworks and extended lans[END_REF]; for example SRM [FJL + 95] and RMTP [START_REF] Paul | Reliable multicast transport protocol (rmtp)[END_REF]. However, IP multicast is sparsely deployed due to its complexity: it requires modifying the infrastructure, implementing complex high layer features (such as congestion control and ow control) and maintaining per group state at the IP layer. As an alternative, scientists have proposed to lift the multicast functionality to the application layer by building application-level infrastructure overlays. To this end, two main classes of approaches have been proposed: peer-to-peer (P2P) systems and Content Delivery Networks (CDNs).

Status of Online Live Video Streaming

Introduction

For both approaches, scalability is the most important issue to address. Scalability is the ability of the system to deliver a video stream to an audience set as large as possible. P2P approaches (see for instance [START_REF] Liu | A survey on peer-to-peer video streaming systems[END_REF][START_REF] Yan | Peer-to-peer media streaming application survey[END_REF][START_REF] Yang Hua Chu | A case for end system multicast[END_REF]ppl]) are intrinsically scalable because each user contributes to the delivery with its own resources, so the more users, the more resources. Peers organizes into P2P overlays to assist video stream delivery. On their side, CDN providers [mKPB06, KSW + 04, AMM + 11, NSS10] are able to scale by leveraging a large set of machines (often called surrogate servers or edge servers), which are deployed at carefully selected locations in the Internet. Users are transparently re-directed to the appropriate server. P2P and CDN are two complementary solutions. CDNs can provide guaranteed services, however this comes from provisioning the CDN with sucient capacity at a non-negligible cost.

Whereas P2P solutions can provide services with statistical guarantees at a lower cost. Both P2P and CDN have special design challenges and requirements, consequently, a service provider must carefully consider the right approach when designing a live video streaming system.

During the last couple of years, the appetite for video stream consumption has signicantly grown. New generation of access technique, such as 3G and 4G, make online video services ubiquitously available. Larger broadband bandwidth leads to the popularity of High Denition (HD) videos. Camera-enabled devices allow everybody to generate live content for sharing, and new types of live video services arise consequently. All these trends impose new challenges to live streaming services. In the following, we will rst state our observations on the current status and trend of online live video streaming:

The domination of video trac. The same gures for Europe were 38% and 39% for xed and mobile network respectively. So far the growth of the video part of the overall Internet trac matches the expectations of the 2010 Cisco report [cisb], which predicts that video will represent 90% of the overall trac in 2015. Currently, online video service, including live videos, has become the main vector of online entertainment. For example, the London Olympic Games accounts for between 8-12% of network trac in the US at its peak levels [san].

The democratization of live videos producers. It is the beauty of the Internet to shift the content production from a handful of media magnates to millions of end-users. Today's online live videos are not generated only by a small set of wellidentied publishers who report global events, such as hot sports and breaking news. Now a fan can stream herself while watching a game at a stadium, a gamer can stream the screen-captured video of her game play, a local junior sport league can broadcast matches for relatives to watch, etc. Multiple platforms allow ordinary Internet users to broadcast their own user-generated live videos. Moreover, popular Online Social Network (OSN) applications enable these sources to promote their user-generated live videos. Such platforms include the justin.tv [jus] platform, the 1.1. Status of Online Live Video Streaming ustream [ust] platform, and the Xre [x] platform. These services are attracting a large population: for example, Xre, which allows players of Massively Multiplayer Online Games (MMOGs) to capture live videos from their game screen and broadcast them to other players, are reported as hosting over 20 million gamers in [START_REF] Shen | The xre online meta-gaming network: Observation and high-level analysis[END_REF].

The heterogeneity of video consumers. Last generation devices (such as smartphones and tablets) allow users to consume videos anytime and anywhere. Typically, it has become commonplace for mobile users to enjoy online video entertainment through wireless connections (3G and WiFi). A recent Cisco report shows that video exceeded 50 percent of mobile trac by the end of 2012 [cisa]. At the same time, the report emphasizes an increasing device diversication: smartphones and newer device categories such as tablets are accounting for a more signicant portion of the trac. Real statistics collected during London Olympic Games shows that 45% of video requests are released from mobile devices (tablets and phones) [nbc]. These devices have dierent screen size, so they tolerate dierent video resolution. Similarly, they are connected to the Internet through dierent types of access link, so they can accomodate dierent video bit-rates. Consequently, they have dierent streaming requirements. For example, a wired home last-generation TV is capable to watch a video with resolution up to High-Denition, whereas a smartphone user is only allowed to watch low quality video. Rate adaptive streaming technique has been designed to serve a more heterogeneous population of users with a good Quality of Experience (QoE). In rate adaptive streaming, a video stream has multiple representations, each corresponding to a certain video quality with certain resolution and bit-rate. This allows the client to adaptively switch from one video quality to another according to the quality of the network link. The recent Dynamic Adaptive Streaming over HTTP (DASH) standard [START_REF]Overview of MPEG-DASH Standard[END_REF][START_REF] Stockhammer | Dynamic adaptive streaming over http -standards and design principles[END_REF] is a new step toward a broader adoption of rate-adaptive streaming technologies.

As we stated earlier, a service provider must carefully consider the right approach (either P2P or CDN) when designing a live streaming system. Clearly, CDN is the best choice for streaming rate adaptive live videos. At least two reasons explain it.

First rate-adaptive technologies is especially ecient to exploit the available downlink capacity of an user when this user has a stable network connection. In P2P systems, the multiple and transient connections make rate-adaptive technologies less ecient.

Second CDN servers can oer dierent representations, and it is easy to switch from one representations to another. Switching from representations in P2P systems is harder because it requires a re-organization in the overlay in order to nd other peers having the right content. At the time scale of DASH, where chunks can be only two seconds, switching becomes challenging.

On the contrary, for streaming user-generated live videos, P2P is a better choice for the following reasons. First of all, the popularity distribution of videos in such services poses a major challenge: (1) a large number of videos are generated simultaneously, (2) most streams are watched by a small population (e.g. friends of the video broadcaster in OSN applications). Such popularity distribution is harder to manage for a CDN, which prefers streaming the same content to a large set of surrogates. Second, the limitations of P2P system to deal with rate-adaptive streaming does not matter here because user-generated contents can rarely use rate-adaptive technologies. Indeed, 1. Introduction the devices that capture and initiates the video streams have a limited capacity, so the raw video stream is of relatively poor quality and it is impossible to derive from this raw video a diverse enough set of representations. Moreover performing the transcoding task by some centralized actor for a large number of live videos imposes heavy computation cost and long transcoding delay.

Motivations and Challenges

The overall motivation of this thesis is to design live video streaming systems that meet the aforementioned trends, in particular both user-generated live videos, and rate-adaptive live videos. Based on the observation of above trends, our objectives are as follows.

• Our rst objective is to design a system that allows users to broadcast their own generated live videos by using the P2P approach.

• The second objective of the thesis is to build a live streaming system that provides rate adaptive videos over the CDN network.

In both works, we try to solve the problem of transmitting live streams in the delivery infrastructure (P2P overlay and CDN delivery network) under the bandwidth constraint of the relay nodes (peers and CDN intermediate equipments). As we stated in Section 1.1, the amount of video trac overwhelm the Internet, and it is expected to still increase. As a result, a major challenge is the bandwidth availability in the delivery infrastructure for both systems. Our task is to nd bandwidth-ecient solutions and design delivery policies for underprovisioned system. In the following, we discuss in detail the bandwidth challenge faced by each individual system.

Bandwidth constraint for P2P user-generated live video sharing system

User-generated live video sharing system consists of multiple P2P video streaming overlays. For each video, a P2P overlay is formed by the video broadcaster and users (peers) watching this live video. The video broadcaster emits a user-generated live video, while peers participate in diusing the video to other peers in the same overlay.

Typically, in such services, a user can watch several live videos simultaneously.

This feature is well appreciated by users. Example scenarios include: (i) multichannel TV, where a user can watch several channels simultaneously [START_REF] Wang | Improving multiview peer-to-peer live streaming systems with the divide-and-conquer strategy[END_REF], (ii) multi-camera streaming, where a client can watch the same event from dierent views [START_REF] Nbc | Super Bowl XLVI Live Stream Sets Trac Records[END_REF], and (iii) MMOG player cooperation, where players from the same team can stream the video of their game to each other [ABH + 11]. However, this feature threatens the availability of bandwidth resources. In P2P streaming, it is now widely accepted that the bandwidth resource bottleneck comes from the upload bandwidth at the peers. The connection of a peer to the Internet is limited, and this connection has to be shared among all the overlays to which this peer participates.

Consequently, a major challenge is the bandwidth allocation problem, which is to nd an upload bandwidth allocation of each peer to its watching videos (P2P overlays).

In the context of extensive video sharing, the system can be underprovisioned.

That is, the aggregate upload bandwidth of all peers is not sucient to support the diusion of all videos. Despite the vast volume of research on the topic of P2P streaming, resource decit in P2P has been constantly ignored. At some point scientists did face the reality of resource decit [START_REF] Sweha | AngelCast: Cloud-based Peer-Assisted Live Streaming Using Optimized Multi-Tree Construction[END_REF][START_REF] Wu | On Dynamic Server Provisioning in Multichannel P2P Live Streaming[END_REF], they proposed to deploy additional servers as bandwidth helpers to prevent the system from becoming underprovisioned. This solution however does not accommodate well a scenario with many small-size overlays, as it would require reserving and managing a large number of Virtual Machines, each generating a small amount of trac. Thus, another challenge is to dene bandwidth allocation strategies for underprovisioned system, for example, how to share the bandwidth decit among the overlays. In this work, we designed a multioverlay P2P live video streaming system. We focus on the bandwidth allocation problem, i.e. users who watch multiple video must decide how to share their uplink bandwidth among the concurrent overlays. Typically, we pay attention to the provisioning of overlays. An overlay is overprovisioned if the bandwidth reserved to it is higher than its streaming demand, and underprovisioned otherwise. Thus, bandwidth is said to be wasted if it was allocated to overprovisioned overlays, although it could be allocated to underprovisioned ones. Our rst contribution is the formulation of the optimum bandwidth allocation problem where the objective is to minimize the waste of bandwidth. We solve it through a maximum-ow problem in a bipartite ow network. Therefore, an optimal solution can be found in a time that is polynomial of the number of users in the system.

Our second contribution is the design of several bandwidth allocation strategies, where the objective is to share the bandwidth decit among overlays for globally underprovisioned system. We proposed several policies (e.g., prioritizing video diversity, popular videos, preferred videos, and premium users) and we showed that it is possible to nd the optimal solution through a minimum-cost maximum-ow problem in the same bipartite ow network. Solutions can be found with existing near-polynomial algorithms. A fairness-based strategy that allocates bandwidth based on the overlay streaming demands are solved by the dual decomposition method. This method leads to a distributed algorithm. At last, we also proposed mechanisms for the practical relevance of the system. The performances of our proposal have been validated by a large-scale real-trace based dynamic simulation.

Our contributions cover the gaps of the previous work [START_REF] Wu | Dynamic bandwidth auctions in multioverlay p2p streaming with network coding[END_REF][START_REF] Wang | A exible divide-andconquer protocol for multi-view peer-to-peer live streaming[END_REF][START_REF] Wang | Improving multiview peer-to-peer live streaming systems with the divide-and-conquer strategy[END_REF] in the following aspects. Firstly, previous work are oblivious to overlay provisioning.

Thus, they lead to biased results such that some overlays may suer from bandwidth decit even when the system is overprovisioned [START_REF] Wang | A exible divide-andconquer protocol for multi-view peer-to-peer live streaming[END_REF][START_REF] Wang | Improving multiview peer-to-peer live streaming systems with the divide-and-conquer strategy[END_REF]. Secondly, we dened policies for underprovisioned system. In previous work, system underprovisioning is either ignored [START_REF] Wang | A exible divide-andconquer protocol for multi-view peer-to-peer live streaming[END_REF][START_REF] Wang | Improving multiview peer-to-peer live streaming systems with the divide-and-conquer strategy[END_REF] or totally not acceptable [START_REF] Wu | Dynamic bandwidth auctions in multioverlay p2p streaming with network coding[END_REF]. At last, we compared our work to the most relevant one [WXR09, WXR11], the evaluation shows the advantages of our approaches. on peering agreements with these ISPs [net]. As a matter of fact, the bandwidth cost to make the trac transit across dierent networks has signicantly decreased [START_REF] Krogfoss | Analysis: Content peering and the internet economy[END_REF],

to a point that it is no longer the main issue. On the contrary, we believe that the major concern for current CDN providers is the bandwidth availability threatened by the rapidly increasing trac volume. Moreover, none of the previous work target rate-adaptive streaming, while rate-adaptive streaming is a severe threat for the capacity of CDN core networks.

In the meantime, a series of works have dealt with the streaming capacity of networks [SLC + 11, ZLW11, NL11, KS11]. The goal is to determine the maximum bit-rate that can be delivered to all nodes. These work are based on elastic video bit-rate and assume innitely divisible data streams. However, in the context of rate-adaptive live streaming, the video bit-rate of representations are pre-dened.

Each stream has to be either delivered in its entirety, or not delivered at all. The throughput of the network is maximized by the number of delivered streams, rather than the maximum deliverable bitrate. Thus, we have designed a new model, which aims to maximize the number of delivered streams in a network.

For this work, we have the following contributions. We rst give a formal formulation of the general problem by Integer Linear Programming (ILP) and prove that it is NP-complete. The general problem is formulated as maximizing the utility of delivered streams by a set of delivery trees. The NP-completeness claim implies that it is currently impossible to implement an optimal solution for the general case. Thus, we focus on a practical scenario, which corresponds to today's CDN implementation of live streams. We present an algorithm, which is fast, easy to implement, and near optimal. We provide formal theoretical approximation bounds, which are shown to be negligible for the regarded conguration. At last, we evaluate the approximation ratio of the algorithm by a numerical simulation. Then, the second contribution substantiates the user-centric discretized streaming model into a practical system. By revisiting the three main CDN mechanisms, the system is able to eciently utilize the CDN infrastructure to deliver live rate-adaptive video streams to viewers in dynamic and large-scale CDNs. The system contains three components. Each component targets one of the three aforementioned CDN main mechanisms:

• A user assignment component assembles users with similar demands.

• A content placement component decides where to place the representations by computing the utility of representations for each edge server.

• A content delivery component builds a multi-tree overlay that exploits the CDN infrastructure capacity with regard to the content utility.

The performance of the system is validated by large-scale real-trace based simulations.

The results show that the system could achieve high user satisfaction with limited CDN infrastructure in a dynamic environment.

Organization of Dissertation

The rest of this dissertation are organized as follows.

Chapter 2 surveys related work of live streaming for both P2P and CDN systems.

We aim to give some background to help readers to understand the technical part of the thesis. We identify several P2P video streaming techniques and we discuss the choice of the techniques that we further use in the multioverlay P2P video sharing system. We also describe current systems for the delivery of live video streams over CDN. At last, we introduce rate-adaptive mechanisms and the transmission of live rate-adaptive streams in CDN.

Organization of Dissertation

Chapter 3 is about the multioverlay P2P live video sharing system. We rst propose the system architecture and the corresponding model. Then, we formally formulate the bandwidth allocation problem. We rst show that the resource allocation with minimum resource waste is equal to the maximum ow in a bipartite ow network model. We further propose several bandwidth allocation strategies for globally underprovisioned system to share the bandwidth decit among overlays. Then, we provide implementation details to show the practical relevance of the system. Finally, the system performance is validated through a set of large-scale real-trace based simulations. The results shows that resource waste is minimized. Especially, peers could achieve better video quality for both overprovisioned and underprovisioned systems comparing to the main previous work in this topic.

Chapter 4 is about the formulation of the general discretized streaming model for delivering live rate-adaptive streams in CDN. The optimization problem is to maximize the average delivered stream utilities. We provide an ILP formulation and prove that the problem is NP-complete. Then, we focus on a practical scenario which makes sense to CDN providers. For this specic case, we present a fast near-optimum algorithm. The algorithm is analyzed through both theoretical analysis and numerical simulation. The simulation result shows that the approximation ratio is negligible for reasonable CDN congurations.

Chapter 5 proposes the user-centric discretized streaming model for delivering live rate adaptive streams in CDN. We rst specialize the general discretized streaming model into a user-centric one by dening user satisfaction based utilities. The objective of the optimization problem is to maximize the overall satisfaction for a user population, while at the same time guarantees max-min fairness on user satisfaction.

We formulate an ILP model and demonstrate the benets of the discretized streaming in a toy-CDN simulation comparing to traditional approaches. Then, we present the practical implementation of the model: a system which delivers live rate adaptive streams in large-scale and dynamic CDNs. To prove the performance of the system, a set of large-scale real-trace based simulations are conducted. The simulation results show that the system could maintain high user satisfaction with limited CDN infrastructure cost.

Chapter 6 summarizes the whole work and gives possible directions on future work.

Chapter 2 Online Live Video Streaming

This chapter presents the state-of-the-art of online live video streaming. Firstly, we discuss in Section 2.1 the requirements and challenges that are specic to online live video streaming. Then, we introduce in detail the two common technologies that are currently used to provide live streaming services: P2P and CDN.

• P2P-based live streaming techniques are discussed in Section 2.2. We rst present a taxonomy of solutions in terms of P2P overlay structure. Then, we relate a discussion to our multioverlay P2P live video sharing system.

• Then, we discuss CDN-based live streaming in Section 2.3. After an overall perspective, we introduce in detail one specic rate adaptive streaming protocol the DASH protocol. Then, we take the DASH protocol as an example to illustrate the delivery of rate adaptive live streams in the CDN infrastructure.

Live video streaming

The current online video services can be roughly classied into two classes: VoD and live videos. Some researchers have explored a third class, which is referred to as catchup TV or time-shifted streaming [LS10, LS11, HBC + 11, DN08]. The live streams is recorded on the y and is then oered in an on-demand service. Even though the demand for these services is growing, the related literature can still not be compared with VoD and live videos.

VoD corresponds to the services that allow users to re-access the same video content multiple times at any moment. Hence, in VoD, dierent users have dierent playback positions at the same time, even for the same video content. Whereas, live video streaming broadcasts real-time videos to users with the same playback position simultaneously. The two mediums have some strategic dierences. Live streaming is especially useful for videos requiring tight timeliness: breaking news, hot sports, real-time cooperation, etc. In the following, we list several characteristics of the live video streaming services.

• Real-time. The play-out delay is dened as the time between the generation of the content on the content provider (or video source) and its reproduction on receiver players. The timeliness of live video streaming requires relatively low play-out delay, ranging from few seconds to few tens of seconds. Besides, to uently play the video, the play-out delay is required to be maintained. For example, increasing the delay can result in video freezing and consequently in low user experience.

• Synchronism. The group of users watching the same video content have synchronous video play-out delay. Moreover, end users can start to watch the video, as well as stop watching the video at any moment. Consequently, the group of users may change rapidly, and system dynamics should be carefully considered.

• Bandwidth constraint. Live video streaming is demanding on resources (for example the bandwidth resource) although it is possible to delay bulk transfers at o-peak hours in VoD [START_REF] Laoutaris | Inter-datacenter bulk transfers with netstitcher[END_REF]. The timeliness of live streaming requires provisioning bandwidth. Hence, the eciency of bandwidth management is one of the rst requirements of live streaming systems.

As previously said, two categories of solutions exist for online live video streaming: P2P and CDN. Both solutions aim to enhance the scalability of the traditional client/server (C/S) architecture. In the C/S architecture, streams are directly sent from the server to each client. This model has limited capacity, and is error-prone to the single point of failure (SPOF). In P2P systems, the end-users contribute to the delivery with their own computing and networking resources, so the total system capacity scales up with the size of the system. In CDN, a large number of dedicated servers are deployed at carefully selected locations in the Internet. These servers cooperate with each other to serve content requests from end users, and increase the fan-out of the CDN origin server. These two techniques are complementary to each other. They both have pros and cons:

• P2P networks do not need any central server. Or, at most a central actor (such as the tracker) with light trac load is sucient. However, the quality of the service provided by a P2P network cannot be fully guaranteed. The main challenges of P2P systems are as follows. First, peer churn can make the network instable. Second, the system has to deal with the heterogeneity of peers. Moreover, in distributed environments, user privacy and security can be important issues and must be treated carefully. Last, there is no guarantee that peers can provide sucient aggregate resources (e.g. upload bandwidth), consequently, the delivery network can be underprovisioned.

• CDNs can provide guaranteed streaming services with low delay and jitter.

However, this comes from provisioning the CDN with sucient capacity at a non-negligible cost. The cost of the CDN operators includes placing a large number of edge servers, provisioning a delivering network, and pay for the trafc load on the peering points. Currently, the development of peering agreements between CDN and network operators has reduced the importance of transmission cost in CDN. In addition, some CDN operators (e.g. AT&T Inc. and Level

3) have built their own networks to further lower down the in-house transmission cost. But still, the cost of maintaining and operating this infrastructure is a constant concern.

Based on the above discussion, P2P-based and CDN-based live streaming service providers have dierent optimization objectives during the system design phase. Typically, for P2P, the target is to maximize the quality of the service perceived on end users by fully utilizing the resources provided by each peer. Whereas for CDN, the objective of the CDN provider would be to nd bandwidth ecient delivery scheme to provide satisfactory services to end users with limited infrastructure cost. In the following, we will fully introduce the state-of-the-art of the two techniques. We still focus on live video streaming. Moreover, after the introduction of each technique, we relate a discussion to the objectives of this thesis: (1) GnuStream [START_REF] Jiang | Gnustream: A p2p media streaming system prototype[END_REF] and the list is endless). These systems have demonstrated that P2P is a cost eective, highly scalable solution for online live streaming.

In a P2P streaming system, peers form an application layer network called overlay network. Then, content is delivered through this overlay network. P2P streaming systems can be roughly classied into two categories of overlay structures: tree-based overlays and mesh-based overlays. In the following, we will discuss each class separately.

Tree-based P2P Systems

Tree-based overlays follows the basic idea of traditional IP multicast. Peers participating to the same video streaming session are organized into a tree structure, which is rooted on the video source. Then, the video content is pushed from the root down to the leaves along the tree. This method is also referred as application layer multicast. The tree structure is optimal in terms of end-to-end delays. Therefore, many early P2P streaming systems have been designed with a tree-based overlay, including ALMI [START_REF] Pendarakis | Almi: an application level multicast infrastructure[END_REF], SALM [START_REF] Banerjee | Scalable application layer multicast[END_REF], ESM [START_REF] Chu | A case for end system multicast[END_REF], and Overcast [JGJ + 00].

We take the example of ESM [START_REF] Chu | A case for end system multicast[END_REF] to detail the construction of data delivery trees over a real underlying communication network. The basic idea of ESM is to form an overlay layer that covers the video source and all peers. Then, on top of the peer Many tree-based systems have been proposed in the literature. For example ALMI [START_REF] Pendarakis | Almi: an application level multicast infrastructure[END_REF] creates a minimum spanning tree, in which the cost of each link is an application specic metric (such as delay, or distance). However, to the best of our knowledge, no commercial large-scale P2P video streaming system utilizes the tree-based structure. The reason is mainly the high tree maintenance cost and bandwidth ineciency. Indeed, tree structure are vulnerable to system dynamics and peer churn. A peer departure will aect all its descendants. Besides, it is also vulnerable to peer bandwidth variation. Peer upload bandwidth determines the number of children in the tree. When the upload bandwidth of a peer changes, some of its children are no longer able to be connected to the tree. As a result, the tree structure has high maintenance cost. Moreover, the tree structure is also inecient in terms of bandwidth utilization. In trees, the leaf peers cannot contribute any of their upload bandwidth resource to the system. Since many peers are leaves in the tree structure, this signicantly reduces the bandwidth eciency.

To overcome the aforementioned drawbacks of the tree structure, systems based on multiple trees, such as SplitStream [CDK + 03] have been proposed. The key idea in SplitStream is to split the content into k stripes and to multicast each stripe using a separate tree. Splitting the original video into k stripes corresponds to applications using rateless coding (e.g., Raptor codes [START_REF] Shokrollahi | Raptor Codes[END_REF] and LT codes [START_REF] Luby | Lt codes[END_REF]), or multiple F . The benets of using multitree structure are twofold: (1). It makes the system more robust to peer churn. (2). Resource of the system are better utilized.

Despite the advantages of multitree structure, it is still tree-based. Thus, it suers from some of the main drawbacks of the tree-based structure. In particular the construction and maintenance of multiple-trees are still costly due to peer churn. behaviors.

Mesh-based P2P Systems

As the name suggests, in mesh-based P2P streaming systems, peers relationship can be represented as a mesh. That is, unlike in tree structures where peers can only get the whole data from one peer (their parent in the tree), peers in mesh overlays are able to connect to and retrieve data from multiple other peers, namely their neighbors.

Peers relationship is maintained in a dynamic way. New neighbors can be added and responseless neighbors can be removed. This design enhances the robustness of the system against peer churn: if a peer's neighbor leaves, the peer can still download video content from the remaining neighbors.

We illustrate in Figure 2.3 how peers in the same video session form a mesh overlay.

The system includes a tracker server to keep track of the active peers. As soon as a peer enters the system, it rst contacts the tracker to register its information (step 1 in Figure 2.3). Then, the tracker responds with a list of peers who are assumed to be active at that moment in the same streaming session (step 2). After receiving the peer list, the peer tries to establish connections to these peers by sending connection requests (step 3). If the remote peer approves, a positive reply message is sent (step 4).

Then, the connection is established and both peers add each other to their neighbor list. This process continues until the peer is connected to a sucient number of neighbors. For system dynamics, if a peer gracefully leaves the system, it noties the tracker and its neighbors. For unexpected departure (such as crash), the tracker and A key idea in the mesh-based P2P system design is to cut the original video into a sequence of small video portions with a short period (e.g. 1 second). The video portion are named as video chunks. In tree-based system, the video can be seen as a ow pushed from the root of the tree down to the leaves, whereas in meshbased system, small video chunks are pulled in parallel from multiple neighbors and assembled into the original video by the peer for display. Each chunk has a unique id (or sequence number) which implies its playback time. For example, lower id chunk will be played earlier. Peers buer the received chunks in order to (1) put them back in order for playing, and (2) oer the received chunks for its neighbors to download.

To transmit the video data, each peer maintains a buer map which indicates its chunk availability and exchanges it with all its neighbors periodically. By receiving the buer maps of it neighbors, a peer can decide which chunks and from which peers it should request. Mesh-based systems suer from two potential drawbacks: First, frequent buer map exchanges result in higher overhead. Second, pulling each individual video chunk can introduce additional transmission delays. However, the advantages of mesh-based systems, especially the ability to adapt to system dynamics, nally leads to successful deployment in the real-world. As far as we know, large-scale commercial running P2P live video systems utilize mesh-based overlays. A simulation study [START_REF] Magharei | Mesh or multiple-tree: A comparative study of live p2p streaming approaches[END_REF] also revealed that mesh-based systems have better performance than tree-based systems.

The advantages of mesh-based systems include robustness, scalability and bandwidth eciency. For robustness, peer churn can be recovered through quick neighbor discovery with gossip protocols. Also, mesh-based overlays are immune to peer upload bandwidth variation. For scalability, except the tracker, each peer is required to just maintain a local awareness of other peers, thus the system can easily scale up. For bandwidth eciency, each peer provides its upload bandwidth for its neighbors to download available chunks, which results in a high utilization of the bandwidth. We summarize the pros and cons of both tree-and mesh-based approaches in Table 2.1. The tree-based approach pushes the video ow along the tree, thus it exhibits relatively low source-to-end delay. Moreover, the control message overheads is lower than that of the mesh design. On the other hand, the mesh-based approach outperforms the tree-based one on the other aspects. The design of the mesh-based P2P protocol is arguably simpler than that of the tree-based. Moreover, it is robust to system dynamics such as peer churn and peer upload bandwidth variation, and nally has lower maintenance cost.

Multioverlay P2P Systems

A multioverlay P2P live streaming system consists of multiple peer-to-peer overlays, each for one video's diusion. Actually, almost all P2P live video streaming systems do their best to provide as many live videos (channels) as possible, thus they all consist of multiple P2P overlays. As for our example in Section 1.2, multioverlay systems are useful in many scenarios.

A number of work in the literature have also considered scenarios where a peer can watch several P2P live streams simultaneously. In [START_REF] Liang | Optimal bandwidth sharing in multiswarm multiparty p2p video-conferencing systems[END_REF], the authors proposed a multi-swarm P2P video conferencing system. In such a system, there are multiple users simultaneously distribute their video streams to multiple receivers. At the same time, a user can receive multiple streams from the same conference group.

In [START_REF] Wu | Strategies of conict in coexisting streaming overlays[END_REF][START_REF] Wu | Dynamic bandwidth auctions in multioverlay p2p streaming with network coding[END_REF], the authors considered a scenario that the upstream peers or the streaming servers distribute several videos simultaneously. From another view points, these nodes participate in multiple P2P networks, hence they are the receivers of multiple concurrent videos. In [START_REF] Wang | A exible divide-andconquer protocol for multi-view peer-to-peer live streaming[END_REF][START_REF] Wang | Improving multiview peer-to-peer live streaming systems with the divide-and-conquer strategy[END_REF], the author also studied a multiview P2P live streaming system, where a user can simultaneously watch multiple channels. At last, we also discussed in [ABH + 11] an application scenario of the multioverlay P2P system where MMOG players from the same team stream the videos of their game to each other for game cooperation purpose.

One of the thesis targets is the design of a multioverlay P2P live video streaming system to share a large number of user-generated live videos to a large-scale end users.

On the system level, two design problems have to be addressed: the intra-overlay video streaming problem and the inter-overlay bandwidth allocation problem, which is the decision that peers have to take about sharing their upload bandwidth into concurrent overlays. As we discussed in previous sections, the intra-overlay video streaming problem has been well investigated in the literature for more than a decade. Plenty existing P2P live streaming protocols can be deployed directly. In the following, we explain our idea of solving these two problems independently and the rationale behind such a design.

Inter-overlay Bandwidth Allocation vs. Intra-overlay Video Streaming

The existing work solving bandwidth allocation problem in the multioverlay system can be roughly classied into two classes. The rst class solves the intra-overlay video streaming problem and the inter-overlay bandwidth allocation problem all-atonce [LZL11, [START_REF] Wu | Strategies of conict in coexisting streaming overlays[END_REF][START_REF] Wu | Dynamic bandwidth auctions in multioverlay p2p streaming with network coding[END_REF]. It means that their solution determines the bandwidth allocated to each overlay on each peer, as well as the overlay construction for each P2P network. In [START_REF] Liang | Optimal bandwidth sharing in multiswarm multiparty p2p video-conferencing systems[END_REF], the authors investigated optimal bandwidth sharing strategies for a multi-swarm video conferencing application. To compensate bandwidth decit, the authors introduced bandwidth helpers (servers that provide upload bandwidth).

The objective is to nd the optimum video bit rates of video sources and helper sharing such that the utility of the system is maximized. Moreover, they use specic tree structure for intra-overlay video delivery. The construction of the tree is based on the allocated peer upload bandwidth for the overlay. In [WL07, WLL08], the interoverlay bandwidth allocation problem is solved with a distributed dynamic auction game. Each upstream peer dynamically and locally organizes an auction game in which the downstream peers bid for its upload bandwidth. According to the results of the auction games, peers form a mesh-based overlay. This proposal requires a specic media distribution mechanism based on network coding.

We believe contrarily that a clear separation between inter-overlay resource management and intra-overlay video diusion brings more benets to the system.

• Firstly, existing P2P systems can be used. One of the motivations is to leverage the advances that are obtained through research. For example, some works have designed promising solutions for the P2P delivery of video in underprovisioned overlay [LSR + 09]. The implementation of such P2P systems for the intra-overlay would be appropriate when the system is underprovisioned.

• Secondly, separating these two problems can enhance the system robustness in a dynamic environment. In multioverlay P2P system, besides regular peer churn, system dynamics also include the variation of allocated peer upload bandwidth into the overlays. In a dynamic system, peer joining, leaving, and switching videos lead to environment changes. Consequently, peers should reallocate their upload bandwidth according to the new settings. In all-at-once solutions, such changes lead to the reconstruction of the overlays.

• Last, solving the two problems together brings additional complexity. The problem formulation for such a double-objective problem is more complex. On the contrary, separating the two problems can simplify the problem.

System Underprovisioning

At last, it is worth to mention that none of the existing works deal with system underprovisioning. If a P2P network can receive enough reserved upload bandwidth (equal to or higher than the streaming requirement) from its peers, it is said to be overprovisioned, otherwise, it is underprovisioned. In other words, an underprovisioned P2P network endures bandwidth decit. In the context of intensive user-generated video sharing, multioverlay P2P systems can be underprovisioned. That is, the aggregated peers upload bandwidth is not sucient to deliver all the videos to all the peers in the system. In this case, to fully utilize peers upload bandwidth, a consequent optimization goal is to minimize the bandwidth decit: peers should allocate their upload bandwidth to the underprovisioned overlays instead of overprovisioned ones. We will further detail this optimization goal in Chapter 3.

The study of underprovisioned P2P overlays represents a new research topic that has not received enough attention. In general, scientists have rst tried to nd a way to provision the system so that they are no longer facing underprovisioning. For example, the lack of bandwidth resources can be tackled by provisioning on-the-y some additional servers to assist in the diusion of the video [WLZ08, [START_REF] Sweha | AngelCast: Cloud-based Peer-Assisted Live Streaming Using Optimized Multi-Tree Construction[END_REF][START_REF] Liang | Optimal bandwidth sharing in multiswarm multiparty p2p video-conferencing systems[END_REF].

This approach is compatible with our multioverlay system. Our goal of minimizing the bandwidth decit of the system also achieves the minimum upload bandwidth consumption on the server side. Another approach is to authorize peers to contribute to an overlay they have not subscribed to [START_REF] Wu | Redesigning multichannel p2p live video systems with view-upload decoupling[END_REF]. This approach works only if the overall system is overprovisioned. Moreover, in the context of live video sharing in social network applications, privacy concerns make it unacceptable.

For multioverlay P2P video streaming system, the aforementioned related works did not investigate system underprovisioning. In [START_REF] Liang | Optimal bandwidth sharing in multiswarm multiparty p2p video-conferencing systems[END_REF], bandwidth helpers are introduced to avoid the system becoming underprovisioned. In [WL07, WLL08],

the system cannot even bear underprovisioning, because their algorithm requires the system to be overprovisioned in order to converge. In the most relevant work [START_REF] Wang | A exible divide-andconquer protocol for multi-view peer-to-peer live streaming[END_REF][START_REF] Wang | Improving multiview peer-to-peer live streaming systems with the divide-and-conquer strategy[END_REF], the authors propose a bandwidth allocation protocol, named DAC, which fairly allocates upload bandwidth based on each overlay streaming demand. However, this approach is oblivious to each individual overlay's provisioning information. Thus, the protocol leads to biased results such that most resources are allocated to the overlays with high demand, although the excess resources could be allocated to other underprovisioned ones to alleviate bandwidth decits in these overlays. As a result, the overlays with low demand may suer from bandwidth decit even when the system is overprovisioned. Our multioverlay P2P video sharing system is further detailed in Chapter 3. We compared our solutions to this most relevant work. A detailed comparison is available in Section 3.7. The CDN providers implement three main algorithms for their system: content placement, content delivery, and user redirection algorithm. Content placement decides where to replicate content on dierent edge servers. It works in combination with the user redirection mechanism. The basic idea is to replicate content, and re-direct content requests to one of the replicas according to some selection strategy.

Content Placement

There are mainly three content placement approaches: push, non-cooperative pull, and cooperative pull. The push methods proactively replicate the content on edge servers before they are actually requested. Such a method can result in inecient system performance and bandwidth wastage. In non-cooperative pull methods, edge servers fetch the content from sources only when a client request cannot be satis- The central actor is the CDN provider which links content provider to the content consumer. Thus, the goal of a CDN is to ooad the trac originated to the content provider's infrastructure, and to make the content widely available to end-users with high performance by its widely deployed servers. A typical live stream delivery within the CDN network contains the following three phases, with each corresponds to one type of the CDN equipments:

• Phase I: Transcoding. Transcoding is performed by CDN sources. The source nodes receive the raw live stream data from the content provider. Then, they are responsible for coding it into a set of live streams and then forward these streams to the reector nodes.

• Phase II: Multiplication. The sources themselves cannot achieve the required output capacity to deliver the stream to all edge servers. The reectors aim to increase the fan-out of the sources. They multiply the received stream data and forward the stream data to the edge servers.

• Phase III: Delivery. At last, the edge servers receive the live streams and oer them to the clients inside their respective Internet Service Providers (ISPs).

In comparison to the infrastructureless approaches (such as P2P-based approaches), CDN provides guaranteed video services with high performance, for example, with low delay, high video bit rate, and low jitter. However, this comes from provisioning the CDN network with high cost. For CDN providers, a major challenge today is the contradiction between the rapidly increasing trac volume and the decient network capacity (for example, the underprovisioned CDN delivery network). Moreover, the rate-adaptive streaming technique (such as the DASH protocol) has been widely deployed. One objective of this thesis is the design of bandwidth ecient solutions for live rate adaptive streaming in underprovisioned CDN delivery network. In the following, we will rst introduce the mechanism of rate adaptive streaming by discussing in detail the DASH protocol. Then, we will discuss the process of live rate adaptive streaming in CDN delivery network and related works on this domain. The basic idea of DASH is that each video is cut into multiple small segments, and each segment holds several video representations. Each representation is associated with a certain quality, thus a certain encoding and a certain bit-rate. For example, we list in Table 2.2 the representations utilized in Akamai HTTP-based adaptive HDTV live streaming service [START_REF] De | An experimental investigation of the akamai adaptive video streaming[END_REF]. Each video is encoded into 5 versions. The video bit rate of the lowest representation is 330 kbps, which corresponds to a low resolution. Whereas the highest representation represents the HD 1080p version of the video with bit rate up to 3500 kbps.

During the transmission of the video, end users adaptively choose the proper representation for each segment, that is, the representation that maximizes the video quality that is allowed by both her network connection and device. Thus, the video bit rate is adaptively and dynamically determined by the last-mile available upload • First of all, the MPD le consists of a sequence of periods by specifying the period start time.

• Each period states multiple representations. Each representation corresponds to a dierent user choice on bit rate, resolution, and encoding, etc.

• Within each representation, a set of segments are listed. Segments is a data unit that can be uniquely referenced by an HTTP-URL.

• Within each segment, the segment info details how to access the data by showing the URL of the data unit.

DASH is also an HTTP-based streaming techniques, which avoids NAT/rewall traversal issues and also has the advantage of reusing the widely deployed standard HTTP caches (e.g. existing Internet CDNs). Thus, this technique is appropriate for CDN. Nowadays, there are plenty of commercial running adaptive streaming services: <?xml version=" 1 . 0 " e n c o d i n g=" u t f -8" ?> <MPD t y p e=" L i v e " m i n B u f f e r T i m e="PT3S" a v a i l a b i l i t y S t a r t T i m e=" 2010 -04-26 T 0 8 : 4 5 : 0 0 -08 : 0 0 " minimumUpdatePeriodMPD="PT5M0S" t i m e S h i f t B u f f e r D e p t h="PT1H30M0S" x m l n s=" urn:3GPP:ns:PSS:AdaptiveHTTPStreamingMPD:2009 " > <P e r i o d s e g m e n t A l i g n m e n t F l a g=" t r u e "> <R e p r e s e n t a t i o n b a n d w i d t h=" 1 2 8 0 0 0 "> <S e g m e n t I n f o d u r a t i o n="PT10S" baseURL=" mt500 "> <I n i t i a l i s a t i o n S e g m e n t U R L sourceURL=" f i f a 1 2 8 s e g _ i . 3 gp " /> <U r l T e m p l a t e sourceURL=" $ I n d e x $ . 3 g s " /> </ S e g m e n t I n f o> </ R e p r e s e n t a t i o n> <R e p r e s e n t a t i o n b a n d w i d t h=" 5 1 2 0 0 0 "> <S e g m e n t I n f o d u r a t i o n="PT10S" baseURL=" mt1000 "> <I n i t i a l i s a t i o n S e g m e n t U R L sourceURL=" f i f a 5 1 2 s e g _ i . • Adobe Flash Dynamic Streaming solution is a web-based service available to all devices running a browser with Adobe Flash plugin [ado].

• Apple HTTP Live Streaming is a client-side HTTP adaptive live streaming solution released by Apple for its products [appa].

• Akamai HD Network is the HTTP-based adaptive HDTV live streaming service provided by the worldwide leader of CDN, Akamai [aka].

• Netix adopts the DASH protocol for streaming online movies and TV shows [AGH + 12].

Live DASH over CDN

The DASH streaming protocol supports various video services, including on-demand and live video steaming. In comparison to on-demand video services, live streaming has special requirements and challenges. In live streaming, the content is generated on The minimumUpdatePeriodMPD eld gives the duration for user MPD update. The user should check for MPD updates at the indicated interval. The new MPD contains the same metadata for future media. Commonly, the update interval is longer than segment duration so that an MPD le contains the information for a certain amount of segments. In the example, the segment duration is 10 seconds, whereas the MPD update duration is set to 5 minutes. The availabilityStartTime announces the start time for the rst video segment (the start time of the rst period) in the MPD le. As previously said, the global UTC time is used for synchronization propose.

We illustrate the process of live rate adaptive streaming in Figure 2.8. In the user side, when a user clicks on the thumbnail of a video on the content provider's site, the user sends an HTTP GET request for the content. This request is redirected to an CDN edge server according to the CDN redirection strategy. The selected edge server releases a MPD le to the user. By parsing the MPD le, the user is able to fetch the live video content for display. When necessary, a MPD le update request is sent, and new MPD le is replied. For the CDN side, the content provider pushes the content to be delivered to the CDN source server. For live streaming, the CDN works in a push way such that the video ow is pushed continuously from the source to the edge servers through the CDN delivery network.

There are several challenges in the above process. First of all, the sharp growth of video trac is a severe threat for the CDN infrastructure. Besides, the multirepresentations characteristic of the rate adaptive streaming aggravates such capacity problem, since for a single channel the whole set of representations (frequently more than 20Mbps) should be delivered to the edge servers [AGH + 12]. As a result, the CDN delivery network can be underprovisioned: the network could not aord the delivery of all the required streams to all the edge servers. In this context, the objective of the CDN providers for live streaming is to maximize the throughput of their network under the restriction on the upload capacity of the CDN forwarding equipments. In the following, we will survey some of the relevant literature in related areas. 2.2). Hence, the throughput of the network is maximized when the number of delivered streams is maximized. We refer to such optimization problem as discretized streaming capacity problem. It is introduced in Chapter 4. This optimization problem provides a theoretical foundation for optimal live rate adaptive streams delivery in the CDN infrastructure.

Related Works

For live streaming in CDN, the tree structure is ecient and robust because the infrastructure is under the control of the CDN provider. The delivery trees are rooted on the CDN sources, and push the content ow down to the leaves, which covers the CDN edge servers. Thus, we aim to construct a set of delivery trees that achieve the above-mentioned optimization goal. There are two set of related work: the multiple tree packing problems and the minimum Bounded Degree Spanning Tree (BDST) problem.

The multiple tree packing problems have been studied in the context of peerassisted systems [START_REF] Rahimi | On fair and optimal multi-source ip-multicast[END_REF][START_REF] Sweha | AngelCast: Cloud-based Peer-Assisted Live Streaming Using Optimized Multi-Tree Construction[END_REF]. The problem is to minimize the amount of additional resources to serve all peers in a P2P system. This problem is dierent in CDNs, which are self-sustained networks. The missing resources cannot be compensated, rather, bandwidth resources need to be used in the best possible way. Numerous work have studied multi-tree packing for P2P application layer multicast protocols (see [HA + 07] for a survey). The goal is to span all nodes under application related optimization objective (e.g., to minimize tree height, or to reduce controlling overhead). However, in the context of CDN, each delivery tree only need to cover a set of edge servers (not all CDN equipments) in the network who require the stream. Such requirement is determined by the CDN content placement algorithms.

The BDST problem aims to determine a minimum-cost spanning tree while no node should have more than m children (see [START_REF] Michel | Minimum bounded degree spanning trees[END_REF]), which is NP-complete for any m ≥ 2. Related variations of this problem feature non-uniform degree bounds [START_REF] Könemann | Primal-dual meets local search: approximating MSTs with nonuniform degree bounds[END_REF].

Again, these work aim at spanning all nodes in the network while optimizing an objective function, while we aim at maximizing the number of spanned nodes under a node degree constraint. The only related work in this aspect is [START_REF] Blum | New metaheuristic approaches for the edge-weighted -cardinality tree problem[END_REF], which study the minimum spanning tree with at least k nodes in a weighted graph, but this work do not target the maximal k. Furthermore, these works do not deal with packing several trees and the resource allocation problem that such packing introduces. In this chapter, we introduce our multioverlay P2P video sharing system. The architecture of the system is shown in Figure 3.1. As the gure depicts, the system consists of multiple P2P live video streaming networks. Each P2P network contains one source (the video generator) and all peers (the video receivers) that have subscribed to its live stream (channel). For example, in the gure, three sources are sharing their videos to a set of peers. A centralized actor, say a management server, is required to orchestrate the multiple overlays and perform necessary computations.

In multioverlay systems, a user can watch multiple live videos simultaneously. For example, in Figure 3.1, p 1 watches the videos from s 1 and s 2 , while p 2 watches all the three videos. For such multi-watching characteristic, several possible application scenarios have been introduced in Section 1.2, and some related work are discussed in Section 2.2.4. As we discussed, besides the intra-overlay streaming problem, the system must also solve an inherent inter-overlay bandwidth allocation problem such that the multiple watching peers must decide how to share its uplink capacity among these concurrent overlays. In Section 2.2.4, we have stated our design principle: for intraoverlay video streaming, any state-of-the-art mesh-based P2P video streaming protocol can be deployed, and streaming overlays are constructed based on the allocated bandwidth. Then, in this chapter, we fully describe how we solve the inter-overlay bandwidth allocation problem.

For the bandwidth sharing problem, we especially focus on the provisioning of overlays. The provisioning of an overlay is calculated as the dierence between the overlay demand (the amount of bandwidth required to serve all peers in this overlay) and the overlay capacity (the amount of bandwidth actually reserved). In the multioverlay context, resources can be wasted if they are allocated to overprovisioned overlays, although they could be allocated to underprovisioned ones. We illustrate such bandwidth wastage in Figure 3.2. In the gure, an arrow from a peer to a source means that this peer reserves some resource units for this overlay. For example, peer p 2 reserves two resource units to the overprovisioned overlay s 3 although it could reserve them for the underprovisioned overlay s 2 . This problem is especially critical when the system is underprovisioned, that is, when the aggregate upload bandwidth of all peers cannot meet the demand to deliver all the videos. In the context of extensive live video sharing, the system has to deliver a large number of videos, under the constraint of limited total peers upload bandwidth. As a result, the system can be underprovisioned. Our simulations also conrm that for realistic parameter settings, the system is often underprovisioned.

Our Contribution

Our rst objective is to nd bandwidth allocation solutions that minimize the waste of resources. We show that the problem can be transformed into the computation of a maximum ow in a bipartite graph. The maximum ow problem has been extensively studied in the literature, and fast polynomial algorithms exist. Hence, the optimal bandwidth allocation can be computed rapidly for a large scale system.

The second contribution is a set of bandwidth allocation strategies for underprovisioned system which share the inevitable resource decit among overlays so that a pre-determined policy is satised. Several bandwidth strategies can be tackled by introducing a cost function to our maximum-ow problem. This is a generic solution because dierent cost functions can be designed for various strategies. We enumerated four possible strategies: minimize the number of underprovisioned channels, prioritize the most popular channels, prioritize fee-paying users, and prioritize videos that are globally more frequently watched as preferred videos. The computation of a minimum-cost maximum ow nds allocations that are optimal in terms of resource waste and correspond to the best allocations with respect to the policy of the service provider.

Our third contribution is a distributed algorithm that allocates the bandwidth based on proportional fairness (bandwidth is allocated according to overlays demand).

We show that this objective is equivalent to the maximization of the utility of ows in a bipartite ow network. We solve this optimization problem with the dual decomposition method. This method allows us to decompose the optimization problem into a set of subproblems and to solve it in a decentralized way with a distributed algorithm.

Finally, we present a set of simulations where we compare our strategies to the algorithms presented in the main previous work [START_REF] Wang | A exible divide-andconquer protocol for multi-view peer-to-peer live streaming[END_REF][START_REF] Wang | Improving multiview peer-to-peer live streaming systems with the divide-and-conquer strategy[END_REF]. The simulation results shows that, when the system is overprovisioned, our strategies make sure that all peers receive high quality videos. In case the system is underprovisioned, our strategies guarantee that a large part of peers enjoy high quality videos, according to the policy given by the service provider. To the best of our knowledge, this is the rst time that the quality of experience of users for diverse bandwidth allocation strategies in underprovisioned systems is studied.

The related work is discussed in Section 2. Section 3.6 discusses the practical relevance of the system. Section 3.7 evaluates the performance of the system. Finally, conclusions are presented in Section 3.8.

System Model

We rst give the notations used throughout this chapter (see Table 3.1). The system includes a global server. Its role is to authorize, or not, a peer to watch a video 3. Multioverlay P2P Video Sharing: Resource Allocation in Under-Provisioned System emitted by a source, and to compute an optimal bandwidth allocation.

Sources. The set of sources is denoted by S. A source s is associated with an overlay G s , which contains the set P s of all peers that have subscribed to this overlay.

To avoid confusion, s ∈ P s .

Peer-to-Peer Streaming. The intra-overlay P2P streaming system is out of the scope of this work. Our system is independent of intra-overlay structures. As we have discussed, any state-of-the-art mesh-based P2P live video streaming system can be used.

Peer Uplink Management. The set of all peers is denoted by P . We denote by G(p) the set of sources from which the peer p receives a video. Every peer can use its uplink to transfer the chunks it received to other peers in the same overlays. The upload capacity of p is denoted by B p while the upload capacity that p has reserved to serve video chunks in the overlay G s is denoted by b s p . Clearly, we have the following constraint on peer upload bandwidth:

s∈G(p) b s p ≤ B p
Note that a source s ∈ S can also be a receiver of another overlay as a casual peer. Yet, we assume that s reserves all of its upload bandwidth to its overlay G s .

Overlay Capacity and Demand. The capacity of an overlay G s is denoted by

C s : C s = p∈Ps b s p + B s
That is, C s is the aggregated upload bandwidth allocated from peers to G s , plus the capacity of the source. The demand of an overlay corresponds to the smallest overlay capacity required to satisfy all peers in P s . In a real system, the overhead resulting from the control trac of P2P streaming protocols cannot be neglected. Therefore, the demand D s of an overlay G s contains two parts. The rst part is the bandwidth required to stream the video to all peers.

D s = |P s | • (d s + o s )
Overlay Provisioning. The provisioning ∆ s of a given overlay G s is the dierence between its capacity C s and its demand D s :

∆ s = C s -D s
An overlay is said to be underprovisioned when ∆ s is negative. The average upload capacity is smaller than the video bit rate, so some peers in this overlay are unable to watch the video at full quality. The smaller the provisioning, the worse the video quality experienced by the peers. On the other hand, the overlay is overprovisioned when ∆ s is positive. We dene the notion of overlay underprovisioning as |∆ s | if the overlay is underprovisioned and zero, otherwise. Overlay Relative Provisioning. The relative provisioning ∆ r s of a given overlay G s is dened as the overlay provisioning divided by the number of peers in the overlay, that is:

∆ r s = ∆ s |P s |
System Provisioning: A system is said to be underprovisioned if the aggregate peer upload bandwidth cannot fulll the demand of streaming all the videos, that is:

p B p < s D s
Otherwise, it is said to be overprovisioned.

Minimizing Under-provisioning: Bipartite Network Flow

In order to solve the bandwidth allocation problem, we build a theoretical abstract structure, which is a bipartite ow network N = (V, E) according to source-peer relationship. For example, we represent in Figure 3.3 the bipartite graph related to the scenario of the system shown in Figure 3.1. The set V contains a virtual fountain l, a virtual sink q, the set P of all peers in the system, and the set S of all sources. Thus V = P ∪ S ∪ {l, q}.

The set of directed edges E gives the source-peer relationship. It includes three subsets. The rst one, E 1 = {(l → p) : p ∈ P }, contains edges from the fountain to each peer p with a maximum capacity of B p . The second one, E 2 = {(p → s) : p ∈ P, s ∈ G(p)}, contains edges from p to s if p subscribes to s with innite maximum capacity. The third set, E 3 = {(s → q) : s ∈ S}, contains edges from each source s to the sink with a maximum capacity equal to D s -B s , the overlay demand minus the source capacity. This ow network is used by the bandwidth allocation algorithm. The capacity of edges of peers and sources indicate the limitation in the amount of bandwidth resources that a peer can reserve and a source needed. The ows on edges from peers to sources represent the allocation of resources.

Our rst goal is to minimize the total underprovisioning. Given demands and capacities, the resource allocation should ensure that no resource is allocated to an

l p 1 p 2 p 3 p 4 s 1 s 2 s 3 q 9 5 8 8 12 6 12 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ Figure 3.3: Bipartite Flow Network
overprovisioned overlay when it could have been allocated to an underprovisioned one.

Let S + (respectively S -) be the set of sources (overlays) with a positive (respectively negative) provisioning. We look for an uplink sharing among the overlays so that the total underprovisioning is minimum. Hence, our rst goal is to minimize

s∈S -|∆ s |.
Proposition 1 The sum of underprovisioning s∈S -|∆ s | is minimum if and only if the maximum ow is achieved in the ow network.

Proof . We denote by f s,q the ow on the arc (s → q). The cut-set between V \{q} and {q} bounds a ow |f | = s∈S f s,q . For each source s, the absolute underprovisioning |∆ s | is equal to D s -B s -f s,q . For a source s in S + , we have D s -B s -f s,q equals to zero because the ow f s,q cannot be greater than D s -B s . Thus,

s∈S - |∆ s | = s∈S - (D s -B s -f s,q ) = s∈S (D s -B s -f s,q ) = A - s∈S f s,q
where A is a constant. Minimizing s∈S -|∆ s | is equivalent to maximizing s∈S f s,q . Moreover, (i) edges from l to P furnish the system with all capacities C = p B p , (ii) edges from P to S follow the rule of the bandwidth allocation. Hence, the overall underprovisioning s∈S -|∆ s | is minimized if and only if the ow is maximized.

The max-ow problem has been studied extensively in the literature. The Goldberg-

Tarjan algorithm [START_REF] Goldberg | A new approach to the maximum ow problem[END_REF], which is based on a method called preow-push, is one of the most famous algorithms. The principle is to push a ow to the nodes that are estimated to be closer to the sink. The estimation is measured by a distance label maintained on each node. This preow algorithm in a bipartite graph has been especially studied in [START_REF] Ravindra | Improved algorithms for bipartite network ow[END_REF]. In an unbalanced bipartite graph, the preow algorithm can be substantially sped up. A number of works [GGSP95, AGM

+ 05] also designed distributed algorithms. These previous works oer opportunities to develop distributed methods that minimize the total underprovisioning. In particular, these algorithms can be used to implement fast algorithm on a cluster of servers for the management of large-scale systems.

Cost Function Driven Bandwidth Allocation Strategies

When the system is underprovisioned, there is often more than one maximum ow.

So there is often more than one resource allocation that minimize the total underprovisioning. In this section, we show that in the ow network, with dedicated designed cost functions, the minimum-cost maximum ow can drive the distribution of upload bandwidth among underprovisioned sources. In other words, we are able to choose one allocation among all optimal resource allocations so that the chosen one matches a given pre-determined policy.

Minimum-cost Maximum-ow Problem

In the minimum-cost maximum-ow problem, each edge e in the ow network is associated with a certain cost(e). The cost of sending a ow is calculated as cost(e)•f e .

The minimum-cost maximum-ow problem is dened as, out of all maximum ows in the ow network, nding the one with the minimum sum of cost e cost(e) • f e .

It has been shown that the minimum-cost maximum-ow problem can be equivalently converted into the minimum-cost circulation problem by adding an edge from the sink to the source with innite capacity and large enough negative cost [START_REF] Ravindra | Network Flows: Theory, Algorithms, and Applications[END_REF].

Then, the latter problem can be solved in polynomial time [START_REF] Tardos | A strongly polynomial minimum cost circulation algorithm[END_REF][START_REF] Goldberg | Finding minimum-cost circulations by canceling negative cycles[END_REF]. It can also be solved by linear programming because the objective and constraints are all linear.

In our ow network model N = (V, E), we propose to dene a cost function for edges in E 3 . As the minimum-cost maximum-ow problem aims at minimizing the sum of ow cost, the edges associated with a lower cost will be prioritized in the bandwidth allocation. Consequently, dierent bandwidth allocation strategies can be applied by using correspondingly dened cost functions. This approach is generic in the sense that various cost functions can be designed, which result in various resource allocations. We present later four distinct bandwidth allocation strategies.

Strategy I: Prioritize Overlay Diversity

The goal of our rst strategy is to satisfy the maximum number of overlays. Here an overlay is said to be satised if its normalized relative provisioning is positive, or slightly negative. Thus, we dene our rst strategy as one that minimizes the sum of relative underprovisioning:

s∈S -|∆ r s |.
Overlays with lower population should be prioritized because they have less demand and are easily satised. Thus unpopular overlays should be assigned with smaller cost. Let us dene the cost function as:

cost 1 (e) = 1, If e ∈ E 1 ∪ E 2 1 -1 |Ps| , If e ∈ E 3
Then Proposition 2 shows that our rst strategy is given by the minimum-cost maximum ow corresponding to cost 1 (e).

Proposition 2 The minimum-cost maximum ow corresponding to cost 1 (e) minimizes the sum of relative underprovisioning s∈S -|∆ r s |.

System

Proof .

e cost 1 (e) • f e = e∈E 1 f e + e∈E 2 f e + e∈E 3 (1 - 1 |P s | ) • f e = 2|f max | + e∈E 3 (1 - 1 |P s | ) • f e = 2|f max | + e∈E 3 f e - s∈S D s -B s -|∆ s | |P s | = 3|f max | - s∈S D s -B s |P s | + s∈S - |∆ s | |P s | = A + s∈S - |∆ r s |
where A is a constant. Thus, minimizing e cost 1 (e) • f e is equivalent to minimizing s∈S -|∆ r s |.

Strategy II: Prioritize Overlay Popularity

Another reasonable strategy is to prioritize the most popular overlays since they are required by a large number of peers. On the opposite to the rst strategy, the number of unsatised overlays should be maximized in order to better serve the most popular ones. The second strategy is dened as the one that maximizes the sum of relative underprovisioning s∈S -|∆ r s |. Let us dene the cost function as:

cost 2 (e) = 1, If e ∈ E 1 ∪ E 2 1 |Ps| , If e ∈ E 3
Then our second strategy is given by the minimum-cost maximum ow corresponding to cost 2 (e).

Proposition 3 The minimum-cost maximum ow corresponding to cost 2 (e) maximizes s∈S -|∆ r s |.

Proof . The proof of Proposition 3 is similar to that of Proposition 2:

e cost 2 (e) • f e = e∈E 1 f e + e∈E 2 f e + e∈E 3 1 |P s | • f e = 2|f max | + s∈S - D s -B s -|∆ s | |P s | = 2|f max | + s∈S D s -B s |P s | - s∈S - |∆ s | |P s | = A - s∈S - |∆ r s |
where A is a constant. Thus, minimizing e cost 2 (e) • f e is equivalent to maximizing s∈S -|∆ r s |.

Strategy III: Prioritize Fee-Paying Sources

Many service operators have adopted a tiered business model, which prioritizes feepaying users. With this model, sources can be split into two classes: a premium class consisting of fee-paying sources and a second class consisting of non-paying sources.

A third strategy that prioritizes the premium class can be obtained with the following simple cost function.

cost 3 (e) =    1, If e ∈ E 1 ∪ E 2 1, {e = (s → t) , s ∈ P remium Class} 2, {e = (s → t) , s ∈ Second Class}

Strategy IV: Prioritize User Preference

When watching multiple videos, users pay more attention to a subset of preferred videos. This preference can be typically estimated by the window size of each video.

For example in Multi-view Internet TV, the major screen size video is the focus of users although channels in small windows do not receive much attention. We dene a strategy that prioritizes the overlays that are more frequently watched as preferred videos.

We rst dene a binary variable r s p , which is equal to one if p prefers the video emitted from s, and zero otherwise. Then, the normalized frequency of video s watched as preferred video can be measured as pref s = p∈Ps r s p |Ps| . The value of pref s is closer to one if it is more frequently watched as preferred video. In order to prioritize preferred videos, overlays with higher pref s value should be associated with higher provisioning.

Thus we can dene this strategy as maximizing

s∈S + pref s • 0 + s∈S -pref s • ∆ s .
Consequently, the objective of prioritizing user-preferred overlays can be equivalently written as minimizing

s∈S -pref s • |∆ s |.
The following cost function can be dened with respect to this objective.

cost 4 (e) = 1, If e ∈ E 1 ∪ E 2 1 -pref s , If e ∈ E 3
Proposition 4 The minimum-cost maximum ow corresponding to cost 4 (e) mini-

mizes s∈S -pref s • |∆ s |.
Proof . The proof of Proposition 4 is similar to that of Proposition 2:

e cost 4 (e) • f e = e∈E 1 f e + e∈E 2 f e + e∈E 3 (1 -pref s ) • f e = 2|f max | + e∈E 3 f e - s∈S - pref s • (D s -B s -|∆ s |) = 3|f max | - s∈S (D s -B s ) • pref s + s∈S - pref s • |∆ s | = A + s∈S - pref s • |∆ s |
where A is a constant. Thus, minimizing e cost 4 (e) • f e is equivalent to minimizing Previous strategies have a common drawback: they aim at ensuring a null provisioning to the prioritized overlays, although a slightly negative relative provisioning would have a small impact on the overall quality of experience. To address this problem, we introduce a tunable tolerable video quality parameter k and say that an overlay has tolerable video quality if its relative provisioning |∆ r s | is smaller than k. The demand D s of an overlay can be interpreted as the amount of upload bandwidth required by s to be provisioned as ∆ s = 0. If the system is very underprovisioned, rather than requiring perfect video quality on each source, we only require tolerable video quality. This can be done by tuning the parameter k. As a consequence, the actual D s is equal to

s∈S -pref s • |∆ s |.
|P s | • (d s + o s -k).

Fair Bandwidth Allocation Strategy

The bandwidth allocation strategies discussed in Sec 3.4 prioritize some overlays.

However, this can result in signicant resource decits in the unprioritized overlays.

Hence, we propose a fair upload bandwidth allocation strategy such that bandwidth is allocated based on overlays demand. Due to the non-linear fairness objective, we solve this optimization problem with the dual decomposition method [START_REF] Daniel | Alternative distributed algorithms for network utility maximization: Framework and applications[END_REF], which decomposes the original global optimization problem into a set of subproblems. Furthermore, we show how the subproblems can be locally solved by each source-peer pair with a distributed algorithm.

Problem Formulation

In the ow network model, the upload bandwidth allocated from peer p to source s can be seen as a ow along the path (l → p → s → q) with a value of b s p . Thus, the problem of fair allocation of upload bandwidth in underprovisioned systems can be formulated as maximizing the ow utility with respect to edges capacities, that is, (ii) the part D s • log(b s p ) reects the proportional fairness such that bandwidth is allocated according to each overlay's demand. Constraint (3.2) guarantees that ows on edges in E 1 will not violate the edges' capacity, while constraint (3.3) ensures no such violation on edges in E 3 .

Dual Decomposition Solution

This global optimization problem can be solved with the dual decomposition method [START_REF] Daniel | Alternative distributed algorithms for network utility maximization: Framework and applications[END_REF]. In optimization theory, large-scale problems with coupling constraints can be decomposed into subproblems by constraint relaxing. The subproblems can be solved in parallel or sequentially, which reduces the complexity of the original problem. Moreover, if each subproblem involves only local variables, a distributed algorithm can be used. The Lagrangian of (3.1) is

L(λ, µ) = s,p∈Ps U (b s p ) + p λ p (B p - s∈G(p) b p s ) + s µ s (D s - p∈Ps b p s ) = s,p∈Ps U (b s p ) - p λ p s∈G(p) b s p - s µ s p∈Ps b s p + p λ p B p + s µ s D s = s,p∈Ps (U (b s p ) -λ p b s p -µ s b s p ) + p λ p B p + s µ s D s (3.4)
where λ p ≥ 0 and µ s ≥ 0 are the dual variables to be minimized in the dual problem and λ and µ denote the vectors of λ p and µ s , respectively. The subgradient method is a convenient and general approach to iteratively update the dual variables into the optimum value. Let bs p (λ p , µ s ) the optimal solution of problem (3.5) with given λ p and µ s . Given (λ p , µ s ), bs p (λ p , µ s ) is unique due to the strict concavity of the utility function, and it can be calculated as:

bs p (λ p , µ s ) = D s λ p + µ s
Let ( λp , μs ) be a feasible dual solution, then the subgradient of φ s,p can be derived

φ s,p (λ p , µ s ) = sup b (U (b s p ) -λ p b s p -µ s b s p ) ≥ U (
From (3.7), the subgradient s(λ, µ) = -b(λ, µ) where b(λ, µ) is the optimum solution of problem (3.5) for a given (λ, µ). Thus, the dual variables can be updated by the following iteration:

λ p (t + 1) = [λ p (t) -α(B p - s∈G(p) bs p (λ p (t), µ s (t)))] + ∀p (3.8) µ s (t + 1) = [µ s (t) -α(D s - p∈Ps bs p (λ p (t), µ s (t)))] + ∀s (3.9)
where t is the iteration index, α is a small enough positive step size, and [•] + is the nonnegative orthant projection.

Distributed Algorithm

The E 1 edge price λ p can be locally updated by each peer p by ows pass over p, that is, the allocated upload bandwidth from p to its subscribed sources, while µ s can be updated by each source in the same way. In this section, we discuss the algorithm generated by dual decomposition which solves the global optimization problem in (3.1) locally by message passing between sources and peers coupled by constraint (3.2) and constraint (3.3).

The algorithm consists of two phases: an initialization phase and a running phase.

Initially, we set t = 0. Since the subgradient method starts from any given (λ, µ) and converges to the optimal solution, the initial value of (λ(0), µ(0)) is randomly generated. On the source side, each source randomly chooses µ s (0) such that µ s (0) > 0 and broadcasts µ s (0) to its peers. On the other hand, each peer randomly chooses a positive λ p (0) and calculates bs p (λ p (0), µ s (0)) with respect to (λ p (0), µ s (0)), and then sends bs p (λ p (0), µ s (0)) to the corresponding sources. Then, the algorithm goes into the iterative phase until it converges to the optimal solution. Each iteration is detailed in Algorithm 1 and Algorithm 2.

The algorithm requires message passing between peers and their subscribed sources.

For practical relevance, the source-to-peer information can be piggy backed using the video chunk messages, while for the reverse direction, the message integration mechanism can be used on upstream peers. According to the subgradient method, the dual variables (λ, µ) will converge to the optimum value with suciently small step size α. Moreover, the original primal problem (3.1) can be equivalently solved by the dual problem (3.4), the primal variable also converge into the optimum value.

Implementation and Practical Details

We provide implementation details to show the practical relevance of our theoretical framework.

Overall Architecture and Peer Dynamics

The main functions related to bandwidth allocation are implemented in a global server called P2PServer (as Figure 3.1). Every peer sends a report to P2PServer that contains an estimation of the available bandwidth. Then, P2PServer computes the bandwidth allocation and send it to peers. With the deployment of the P2PServer, centralized bandwidth allocation algorithms, for example, the maximum ow based algorithms presented in Section 3.3 and Section 3.4 can be implemented to calculate the optimum bandwidth allocation.

This approach is feasible in a static environment. However, all P2P video applications face the problem of peer churn and the available bandwidth can vary between two measurements. To cope with system dynamics, we followed the approach proposed in [WXR09, WXR11]. The system time is cut into sessions, and the computation is done periodically. The computation involves only peers and sources that exist in the system at the starting point of that session. During the session, new arriving peers allocate their upload bandwidth according to some predened strategy (e.g., equal allocation to the subscribed overlays). The capacity of the system to handle the dynamic behavior of peers only depends on the choice of session length. We evaluated the received video quality for dierent session lengths and peer churn rates in Section 3.7. They suggest that a delay of one minute between two re-computations is a reasonable choice.

nb. peers 1,000 5,000 10,000 50,000 100,000 time (in sec) 0.005 0.086 0.311 7.455 31.887 Table 3.2: Computation time for minimum-cost maximum-ow algorithms.

Peer-Server Communication Overhead

We are concerned about the trac generated by the peer-server communication. However, this trac has to be seen in light of the huge amount of data needed for the live video streams. For example, if the average number of videos watched by a peer is three, two bytes are used to specify the upload bandwidth reserved to an overlay, and the bandwidth allocation is recomputed every minute, then P2PServer needs to transmit 0.8 bps per peer. If we consider in addition the 54 bytes for the TCP/IP/Ethernet packet overhead, then 0.8 Mbps server upload bandwidth would be needed for 100,000 users. Similarly, if the report sent by a peer to P2PServer includes four bytes to specify the estimated upload bandwidth and four bytes for the peer ID, then only 0.826 Mbps server download bandwidth would be needed for 100,000 users. It shows that, from a network standpoint, the system can be implemented without much fear for scalability.

Algorithm Computation Time

We also studied the scalability in terms of computation. We measured the exact computation time of the preow maximum ow algorithm and a scaling approximation minimum-cost ow algorithm [START_REF] Goldberg | An ecient implementation of a scaling minimum-cost ow algorithm[END_REF]. The measurement was done on a typical server (2 × 4 cores Intel(R) Xeon(R) 2.67GHz CPUs). The results are average value of 5 runs (Table 3.2). The number of peers increases from 1,000 to 100,000. For each instance, the number of sources was set to 10% of the population. The number of channels watched by a peer was randomly chosen between 1 and 5.

Our measurements demonstrate that a practical implementation of the minimumcost maximum-ow algorithm can compute the resource allocation for very large instances (100,000 peers and 10,000 sources) in reasonable time. They also conrm that recompute every minute is a reasonable choice. The low peer to server communication overhead and the fast resource allocation algorithm show the feasibility of managing a centralized server to recompute periodically the optimal resource allocation in a dynamic environment.

Evaluation

To evaluate the performance of the system, especially in dynamic environments, we conducted two sets of simulations: a static scenario simulation and a dynamic scenario simulation. In the static scenario, we calculate the optimal bandwidth allocation of dierent algorithms for a set of peer-source congurations. This can be seen as calculating the optimal bandwidth allocation of a snapshot of a dynamic system.

The system provisioning was changed from an overprovisioned state into an under-provisioned state by increasing the video bit rate. We show that with reasonable multioverlay structure (number of overlays and overlay popularity), the system can be underprovisioned, which conrms our intuition that underprovisioning is a critical issue for multioverlay systems. The aim of the static scenario simulation is to reveal the behavior of the algorithms and compare them with respect to the video quality experienced by the peers. In the dynamic scenario, we introduced peer churn.

The system periodically recomputes the optimal bandwidth allocation every ∆t time with respect to the conguration at that moment. We dened three sub-scenarios: a join-only scenario, a leave-only scenario and a fully-dynamic scenario. Then, we evaluated the performance of the dynamic system under dierent peer churn rates and investigated the impact of the recomputation time interval ∆t.

The following algorithms were evaluated:

• DAC [WXR09]: It fairly allocates upload bandwidth based on overlays' demands, but it is blind to the provisioning of overlays.

• Diversity-based (Db): It corresponds to the strategy that prioritizes unpopular overlays (Section 3.4.2).

• Popularity-based (Pb): It corresponds to the strategy that prioritizes popular overlays (Section 3.4.3).

• Improved diversity-based (IDb) and Improved popularity-based (IPb): Versions of Db and Pb obtained by introducing the tolerable video quality parameter k as 50 kbps for underprovisioned system(Section 3.4.6).

• Payment-based (Pa): It prioritizes premium sources (Section 3.4.4).

• Preference-based (Pr): It prioritizes more frequently preferred overlays (Section 3.4.5). Each peer randomly chooses a video as its preferred one.

• Fairness-based (Fb): It allocates the upload bandwidth based on overlays' demands while being aware of the provisioning of overlays (Section 3.5).

• Naive (Nai): It equally allocates the upload bandwidth to the overlays it belongs.

Simulator Platform

To evaluate the proposed bandwidth allocation algorithms, we built a two-level simulator platform as shown in Figure 3.4. The rst level simulates an MMOG video sharing system in which users form friendships and share live videos of their game to their friends. Although we simulated MMOG video sharing services, we believe that the results are applicable to any social network-based video sharing service because our simulation model is based on rules that reect human nature (Pareto rule). In order to conduct realistic simulations, the peer-source watching relationship (which users publish videos and who are the receivers of these videos) is established based on a model drawn from real measurements. Upon the peer-source relationship, the bandwidth allocation algorithms act to allocate users upload bandwidth.

Higher Level

Lower Level

• Organize peer-source relationship

• Generate peer/source churn events

• Calculate upload bandwidth allocation cong_le churn_trace_le Overlay 1 P2PTVSim

Overlay 2 P2PTVSim

Overlay n P2PTVSim The current P2PTVSim simulator is far away from simulating a dynamic video streaming system. We modied the P2PTVSim simulator to support well controlled peer dynamics by loading peer churn events from a peer churn trace le. Thus, the higher level simulator generates, for each overlay, a simulation conguration le, as well as a trace le which contains peer churning events and bandwidth allocation information. Then, the lower level takes these two les as input and simulates the video chunk diusion in each overlay.

Finally, from the results of P2PTVSim, we also evaluated the video quality at each receiving peer by measuring the average luminance peak signal-to-noise-ratio (PSNR). The PSNR is a standard video quality metric computed as:

P SN R(dB) = 10 log 10 255 2 M SE
where M SE is the mean squared error between the original frame and the reconstructed frame.

Simulation Setting

Peer upload bandwidth followed a log-normal distribution with parameters µ = log(380) and σ = 0.8, ranging from 256 kbps to 5 Mbps (Figure 3.5(d)). For the static scenario, the video bit rate varied from 240 kbps to 330 kbps in steps of 30 kbps. The overall system changed from an overprovisioned state into an underprovisioned one.

For the dynamic scenario, the video bit rate was set to 330 kbps. The overhead was set to 50 kbps in both cases.

To establish a realistic peer-source watching relationship, there are three key questions to answer:

• What is the basic user relationship to support video sharing? In the context of user-generated content, video sharing is likely to occur between friends. Thus, the in-game user social network is the basic framework to support user interaction. Shen and Iosup [START_REF] Shen | The xre online meta-gaming network: Observation and high-level analysis[END_REF] observed that, on average, Xre users have 60 friends, and about 15% of the players have more than 100 friends. These gures are smaller than observations on Facebook (130 friends on average).

• Who are the video sources? Videos are spontaneously published by users, and especially by socially active users [WBS + 09]. We dened a mechanism where the probability that a user becomes a source depends on the number of its friends.

• Who are the receivers of each video? This directly aects the video popularity distribution. A user decides to watch a video based on its popularity (attractiveness). Measurements in [SI11, KSC + 12] show that the popularity of live game videos follows a power-law distribution.

We then build a realistic simulation model in which the peer-source watching relationship is formed in two phases: after the selection of sources, the friends of each source decide to watch this video or not based on its attractiveness. From 100 trace les collected from the Facebook network [TMP11], we selected the social network of Smith College as the in-game social network. This network is similar to the one in [START_REF] Shen | The xre online meta-gaming network: Observation and high-level analysis[END_REF]. It consists of 2,970 peers. The average social degree is 65.4, and 20.24% of the peers have more than 100 friends.

We modeled the publication of video according to the Pareto 80-20 rule 80% of videos are published by 20% of the most active users. The measurement in [WBS + 09] conrms our assumption that user activity is strongly related to user degree in the social graph (number of friends). We then chose the user social degree as the major criterion of activity and formalized a model in which users decide to publish a video based on a probability related to their social graph degree. That is, a user decides to publish a video based on a probability equal to e -i τ N , where i denotes its rank in terms of social degree in decreasing order, N denotes the total number of users, and τ is a parameter. As shown in Figure 3.5(a), the Pareto rule is followed when τ takes on values between 0.1 and 0.15. With τ = 0.1, on average, 214 videos were published with ve dierent random seeds.

We modeled the peer watching decision in a way that the resulting video popularity follows Zipf 's law. Assume that sources are ranked by their social degree (size of potential audience) in decreasing order, and s i is the ith source with n s i denoting its number of friends. We associated to each source s i an attractiveness index α i , which is equal to the probability with which its friends decide to watch this video. The attractiveness index α i was calculated such that the channel population follows Zipf 's law: We used a 600-frame video by concatenating 300 frames of the Foreman sequence and 300 frames of the Mother and Daughter sequence. Both sequences are in Common Intermediate Format (CIF) format and have a frame rate of 30 fps. The video was compressed with the H.264/AVC encoder at bit rates ranging from 240 to 330 kbps using the H.264 high prole. We used the Group of Pictures (GOP) structure IBBPBBPBBP (10 frames per GOP). Each chunk corresponds to one GOP, so each GOP is played back independently of the other chunks. At the receiver side, we used the standard frame copy error concealment technique to deal with lost frames.

ns i ns 1 • α i ∼ i -b .
With this technique, the last frame of the last decoded GOP is used to represent all frames of a missing chunk.

Static Scenario Simulation Provisioning Results

Our simulation results show the median result obtained from ve runs. In Figure 3.6, the resource decit shows the total underprovisioning s∈S -|∆ s |. The maximumow based approaches (Db, Pb, Pa and Pr) minimize the total underprovisioning. For video bit rate 240 kbps, the system is overprovisioned, and Db, Pb, Pa, Pr, IDb and IPb have zero total underprovisioning, which means that every overlay is well provisioned.

We observe that both IDb and IPb can have a slightly larger underprovisioning than Db and Pb. Indeed, the reduced overlay demand can perturb the computation of a maximum ow in the ow network. Moreover, constant k was set to 50 kbps although the video bit-rate varies, which explains why the dierence between curves is not constant.

Fb has a larger total underprovisioning than the maximum-ow based approaches because constraints (3.2) and (3.3) cannot guarantee the maximum ow. Then, peers equally allocate the unallocated bandwidth to all subscribed overlays. The overlay demand follows Zipf 's law. Because DAC allocates upload bandwidth to overlays according to proportional fairness, the most demanding overlays are highly overprovisioned while leaving the remaining overlays more underprovisioned.

Consequently, the total underprovisioning is higher. When the system goes into a more underprovisioned state, the dierence between DAC, Fb, and the maximumow based approaches decreases. Because DAC always allocates most resources to the high demanding overlays, when the system is very underprovisioned, even these overlays' demands cannot be fullled.

We expect that all algorithms (except Nai) have the same underprovisioning in very underprovisioned system. However, it is worthless to investigate this situation, because the performance of the system is naturally very poor. Besides, Nai has the highest total underprovisioning.

P2PTVSim Results

We rst show how the bandwidth is allocated among overlays by showing the percentage of lost chunks per peer in overlays ordered according to popularity for video bit rate 330 kbps (Figure 3.9(a) to Figure 3.9(h)). A low chunk loss means an overlay is well provisioned.

In Db, channels ranked 10 to 30 have high video quality, while the ten most popular overlays have high chunk losses. On the contrary, Pb produces high video quality for the rst ten most popular overlays. Some channels ranked after 50 have high chunk losses for Db. These are the overlays with few viewers, thus cannot receive enough resources collectively.

We now compare IDb to Db and IPb to Pb. In IDb, peers in the most popular channels lose fewer chunks, and more channels experience high-quality videos.

Similarly, in IPb, the rst 40 overlays experience relatively few chunk losses.

For the evaluation of Pa, the premium class channels were chosen to be the overlays ranked from 40 to 80. These overlays have far fewer missing chunks than the other overlays.

When we compare Fb to DAC, we observe that Fb has fewer chunk losses than DAC. This is because more resources from the overprovisioned high demand overlays are allocated to the underprovisioned ones. The DAC algorithm allocates most of the upload bandwidth to the rst overlays due to their large demands, making these overlays enjoy no chunk loss while leaving the remaining overlays with high chunk The results obtained by Nai may seem better than those of the other strategies. The chunk losses of Nai are almost uniform. In fact, this strategy takes the worst, as we will see later, all overlays are unsatised.

We do not show such a gure for Pr because the well provisioned overlays are the most preferred ones, which highly depend on user choice. Instead, we show in Figure 3.7 the average chunk losses of preferred videos and non-preferred videos for every peer. When the system is overprovisioned, peers receive the same video quality for both types of videos. As the resource decits increase, this strategy ensures that, globally, peers receive higher quality for their preferred videos. Figure 3.8 shows the total chunk losses in the system. We do not present results for the Pa and Pr algorithms because their performance highly depends on some uncertain user choices. When the system is overprovisioned, DAC has higher chunk losses because the low demanding overlays can be underprovisioned. When the system is in an underprovisioned state, the improved max-ow approaches (IDb and IPb) and Fb have the lowest total chunk losses.

PSNR Results

We now provide objective video quality results by measuring the average luminance PSNR at each receiving peer. To illustrate the distribution of the PSNR, we show the complementary cumulative distribution function (ccdf ) of peers (Figure 3.10). We distinguish three sets of allocations: (1) the maximum-ow allocations (Db and Pb), ( 2) their improved counterparts (IDb and IPb), and (3) Fb, DAC and Nai. We do not present results for the Pa and Pr algorithms for the reasons mentioned earlier in Section 3.7.3.

When the video bit rate is 240 kbps (Figure 3.10(a)), the system is overprovisioned. The maximum-ow based approaches ensure that almost all peers enjoy high video quality because every overlay is well provisioned. The DAC algorithm allocates resources to the most demanding overlays, making some peers experience poor video quality although the system is overprovisioned. The Fb algorithm has slightly worse results than the maximum-ow based approaches because the maximum ow cannot be ensured. However, compared to DAC, Fb balances resources from the overprovisioned overlays into less demanding underprovisioned ones, making fewer peers have poor video quality.

As the video bit rate increases, the system changes into an underprovisioned state.

We discuss in detail the results for video bit rate 330 kbps (Figure 3.10(d)). A signicant proportion of peers experience high video quality: 70% (respectively 80%) of peers for the maximum-ow allocations (respectively the improved ones). For DAC and Nai, this percentage is 40% and 60%, respectively. For the maximumow allocations, 5% of peers have poor video quality (less than 20 dB) due to their extreme bandwidth allocation strategy. The curve of Fb reects the fair strategy:

for almost all peers, the PSNR is between 30 dB and 37 dB. This strategy makes sure that no overlay is extremely well provisioned or bad provisioned.

Dynamic Scenario Simulation

We also conducted a set of dynamic scenario simulations by introducing peer churn.

When a user enters the system, it rst decides to become a source or not based on the mechanism stated in Section 3.7.2. If it decides to become a source, it emits videos during its whole playing session. During its playing session, if some friends emit a video, the peer decides to watch the video or not based on the video attractiveness index. The system periodically recomputes the bandwidth allocation every ∆t minutes. For peers that enter the system during two consecutive calculations, the upload bandwidth is equally allocated to the subscribed overlays. We simulated a dynamic system with 100 minutes simulation time.

Peer churn is modeled with the following parameters.

• ratio of peers initially in the system: γ ini .

• peer playing session length distribution: We followed the measurements in [START_REF] Feng | A long-term study of a popular mmorpg[END_REF] and modeled the playing session length by a Weibull distribution with scale = 11.7, shape = 0.456, and minimum session length 30 s.

• peer inter-arrival time distribution: Peers inter-arrivals can be modeled by a

Poisson process within a short period of time (one hour) [CHL06]. We generated short-time simulations (100 min), thus, we modeled peer arrivals as a Poisson process with arrival rate λ.

We conceived three scenarios: • a join-only scenario with γ ini = 0.8 and λ = 0.15. The player playing session length is set to the simulation time, thus, peers only join and do not leave the system.

• a leave-only scenario in which peers spend their lifetime in the system and then leave. Consequently, we set γ ini to 1, and λ to 0.

• a fully-dynamic scenario with γ ini = 0.8 in which peers join and leave. We extensively studied this scenario using two re-computation time periods (∆t = 2 min and ∆t = 5 min) and two peer churn rates (λ = 0.15 and λ = 0.05).

In Figure 3.11, we show how the number of peers evolves in the three scenarios.

In join-only, the number of peers steadily increases to the total number of peers. The change of the peer leaving rate for leave-only is due to the Weibull playing session distribution. For fully-dynamic, after 20 min, the number of peers is quite stable.

System Provisioning

We present the system provisioning for the three scenarios in Figure 3.12. The system provisioning is consistent with the number of peers (Figure 3.11). In the join-only scenario, as the peer number increases, the upload bandwidth decit increases from about 150 Mbps to around 300 Mbps. In the leave-only scenario, the system becomes less underprovisioned from around 300 Mbps to less than 50 Mbps. In the fully dynamic scenario (Figure 3.12(c)), after the sharp decrease at the beginning, the upload bandwidth decit remains around 50 Mbps. The curves of dierent algorithms are consistent with those obtained in the static simulation (Figure 3.6). Impact of the peer churn rate λ. Figure 3.13(e) shows the results for a higher peer churn rate (λ = 0.05). Compared to the results with lower churn rate and the same re-computation time period ∆t (Figure 3.13(c)), the percentage of peers with a PSNR higher than 35 dB decreases (about 11.1% for IDb and IPb, 12.8% for Fb and 8.7% for DAC). It shows that, with higher peer churn rate, the system performance degrades but still maintains an acceptable level.

PSNR Results

Conclusion

The problem of underprovisioned multioverlay P2P systems has not received enough attention. This Chapter makes several contributions to this open research topic. The rst contribution was to devise strategies that minimize the resource waste when upload bandwidth resources are allocated to overprovisioned overlays although they could be allocated to underprovisioned ones. The second contribution was to design strategies that balance the resource decit over the overlays. We dened several bandwidth allocation strategies that are optimal in terms of minimizing resource decit.

One of the original contributions of our work was to show that these strategies can be built as solutions of minimum-cost maximum-ow problems. We also designed a fair bandwidth allocation strategy that is aware of the provisioning of each overlay, and a corresponding distributed algorithm was developed. Finally we evaluated our algorithms through extensive simulations. We showed in particular that the introduction of a small tolerable video degradation for the most provisioned overlays and the provisioning-aware fairness based strategy can have a signicantly positive impact on the whole system. Furthermore, through a set of dynamic scenario simulations, we showed that the periodic recomputation of an optimal bandwidth allocation can cope with system dynamics.

A part of the work presented in this Chapter have been published in [LAB

+ 12].
We are also considering submitting the whole work as a journal paper. This work is involved in the CNG (Community Network Game) project [CNG], funded by the European Commission's Seventh Framework Programme (FP7, 2007-2013) under the grant agreement no. ICT-248175. The project developed an MMOG user communication tool that enables users to screencast their games either to the members of their guild or to a broader audience. This communication tool has been integrated in The Missing Ink MMOG [mis]. Figure 3.14 shows a snapshot of the screen of an Alpha tester during an online live streaming session. The tester is using the P2P system to For possible future work, decentralized system and distributed algorithms are directions deserve further investigation. Especially, since the improved strategies, which allow video quality degradation in the prioritized overlays, appear to be attractive, we believe a reasonable further step of the work including designing distributed algorithms that optimizes these strategies in a dynamic environment.

Chapter 4 Discretized Streaming Model for

Live Rate Adaptive Streaming

Introduction

We have illustrated the traditional architecture for the delivery of live video streams in the Internet in Figure 2.5 in Section 2.3. Three main actors are involved in this process: the content provider, the CDN provider and the end users. End users form a heterogeneous population, who consume the videos on a growing range of devices through dierent types of connections. Content providers are adopting rate adaptive streaming technologies (for example, the DASH protocol) to enhance its ability to serve this heterogenous population. CDNs handle the majority of video trac on behalf of content providers. However, to the best of our knowledge, currently there is no work that investigates the live rate adaptive streams delivery in the CDN infrastructure. In this chapter, we introduce our rst-step theoretical achievement on this domain: the discretized streaming model for the general problem of live rate adaptive streaming, and a fast near-optimum algorithm for a specic application scenario.

Live streaming requires the CDN provider to provision a delivery infrastructure in advance, i.e. to make sure that equipments in the CDN infrastructure are able to transmit streams from source servers to edge servers, and then to the end users. We have introduced the streaming capacity problem in Section 2.3.4. Here we briey recall, and discuss more details about this most relevant work to our study. This problem aims to determine the maximum deliverable bit rate of a P2P network. Some algorithms, mostly based on network coding, obtain near-optimal performances in terms of bandwidth utilization [START_REF] Niu | Asymptotic optimality of randomized peer-topeer broadcast with network coding[END_REF]. Unfortunately, these solutions are unrealizable in a CDN due to two main reasons. First, they rely on heavy computations which are intractable in the CDN hardware (although the equipment have a very large bandwidth, their computing capabilities are quite small [net]). Second, the proposed models are elastic video bit-rate based and assume innitely divisible data streams.

However, in the context of rate adaptive streaming, the video bit-rate of representations are well pre-dened. Each stream has to be either delivered in its entirety, or not delivered at all. Consequently, instead of maximizing the bit-rate, the throughput of the network is maximized by maximizing the number of delivered streams.

We propose the discretized streaming model which is more suitable for delivering multiple live rate adaptive video channels in modern CDNs. The main challenge is to determine a delivery scheme that maximizes the number of delivered streams in a 3-tier network (as shown in Figure 2.4) that is constrained by the capacity of its inner equipment. We give a formal formulation of the general problem that maximizes the utility of delivered streams by a set of delivery trees. Furthermore, we prove that the problem is NP-complete. This general problem formulation is the rst step towards a complete work of delivering live rate adaptive streams over the CDN infrastructure.

As the NP-completeness claim implies, it is currently impossible to implement an optimal solution for the general case. Then, we especially consider a practical scenario, which corresponds to today's CDN implementation of live streams. For this scenario, we present an algorithm, which is fast, easy to implement, and near optimal. We provide formal theoretical approximation bounds, which are shown to be negligible for the regarded conguration. The algorithm represents the second contribution for the problem. To our knowledge, today's CDN providers apply adhoc delivery techniques. Our algorithm is thus the rst scientic reference for optimal delivery in the discretized streaming model.

The remainder of the Chapter is organized as follows. In Section 4.2, we introduce the discretized streaming model and formally dene the problem. Then, in Section 4.3 we provide a formulation of the problem through Integer Linear Programming (ILP) and prove that it is NP-complete. We overview the rationale behind the network conguration in Section 4.4, and describe our near-optimal algorithm for the scenario.

The evaluation of the algorithm is provided in Section 4.5. Finally, some conclusion remarks are given in Section 4.6.

System Model and Problem Denition

In what follows, we present our model of live rate adaptive video streaming in a CDN network, which is followed by a formal optimization problem denition. We rst summarize the notations that will be used throughout this Chapter in Table 4.1.

Live Rate Adaptive Streaming in CDN

A CDN is composed of a set of communication devices and a set of directed communication links. The topology of a CDN is modeled by a directed graph G = (V, E), where V represents the communication devices, and E represents the communication links.

There are three types of communication devices, also referred to as nodes, in a CDN: a relatively small number of sources (origins), a medium size network of reectors, and a large number of edge servers. The sources receive and transcode the

V, E

The set of all nodes, and all links in the CDN

V S , V R , V E
The set of sources, reectors and edge servers in the CDN

E SR

The set of links connecting sources and reectors

E RR

The set of links inter-connecting reectors

E RE

The set of links connecting reectors and edge servers

d ij , i ∈ [k], j ∈ [l] The i-th representation of the j-th channel λ i , 1 ≤ i ≤ k
The bit-rate of the i-th representation of all channels T s ij The delivery tree of raw video channels into a set of live representations; the reectors deliver the representations to the CDN edges, and the edge servers oer the received representations to the clients inside their respective ISPs. Let V S , V R , V E ⊂ V be the set of sources, reectors and edge servers, respectively.

d ij rooted at s ∈ V S D(v), v ∈ V S ∪ V R The set of representations forwarded by v c(v), v ∈ V S ∪ V R
Accordingly, there are three types of possible connections in E: E SR connects sources to reectors, E RR allows communication between reectors, and E RE delivers the representations to the edge servers. They are formally dened as:

E SR ={(u, v) : u ∈ V S , v ∈ V R } E RR ={(u, v) : u, v ∈ V R } E RE ={(u, v) : u ∈ V R , v ∈ V E }.
The live streams consist of l dierent channels. In rate adaptive streaming, the raw video of each channel is transcoded into k representations, where the bit-rate of the i-th representation, 1 ≤ i ≤ k, is λ i . For simplicity of notation hereafter we denote by [m] the integer interval {1, . . . , m}. Also, let d ij be the i-th representation of the j-th channel, i ∈

[k], j ∈ [l].
The delivery of a representation d ij , i ∈ [k], j ∈ [l], from the source nodes to the edge servers is carried out through a set of trees, T ij . Each tree in T ij , also referred to as the delivery tree, has one of the source nodes as its root and edge servers as its leafs. We denote by T s ij the delivery tree of d ij rooted at s ∈ V S . For convenience, let V (T ) and E(T ) denote the node and edge sets of tree T , respectively.

Note that every forwarding node v, either source or reector, can participate in the delivery of multiple representations. However, for any representation d ij , i ∈ [k], j ∈ [l], v can be a part of only a single delivery tree in T ij . In addition, every forwarding node v ∈ V S ∪V R is also limited by the total outbound bit-rate (capacity) it can support, c(v). Let D(v) be the set of representations forwarded by v, v ∈ V S ∪V R . Then,

i∈[k] λ i • |{j : d ij ∈ D(v)}| ≤ c(v).
Like some related work [ASV11, AMM + 11, ZAB + 12], we consider that the outbound

Problem Denition

Ultimately we would like every edge server to receive all the representations it requires. This however might not be possible in a underprovisioned CDN. Due to the outbound capacity constraints at the forwarding nodes, the CDN may support the delivery of only a subset of representations for each edge server. In such case, the CDN provider leverages statistics to prioritize the delivery [START_REF] Nygren | The Akamai network: a platform for high-performance internet applications[END_REF].

The preferences of edge servers in respect to the available representations is captured in a utility score, such that α e ij is the utility score that edge server e assigns to representation d ij . To evaluate the performance of a delivery scheme, the idea is thus to evaluate a utility score function α e (X e ) for each edge server e ∈ V E as follows:

α e (X e ) = i∈[k] j∈[l] α e ij x e ij
where X e is an indicator matrix of size k × l such that x e ij has a value of 1 if e receives d ij and 0 otherwise.

Our objective is to study the Maximum Average Utility Score (MAUS) problem, which essentially is the maximization of the average utility score function of the edge servers, as summarized below.

Problem 1 Given the topology and capacity constraints of a CDN, nd delivery tree sets, {T ij } i∈[k],j∈ [l] , such that e∈V E α e (X e ) is maximized.

Problem Formulation and Problem Complexity

We now discuss the complexity of Problem 1. We rst provide an ILP formulation for MAUS, and then we show that the problem is NP-complete.

Integer Linear Programming formulation

We use the notation introduced in Section 4.2 and extend it by dening two new variables, y and h.

Let T s ij ∈ T ij , i ∈ [k], j ∈ [l]
, be a delivery tree. Then, for every edge (uv) ∈ E, y uv ijs is an indicator variable such that:

y uv ijs = 1 if (u, v) ∈ E(T s ij ), 0 otherwise. For nodes u, v ∈ V such that (u, v) / ∈ E we dene y uv ijs = 0. For every node v ∈ V , h v
ijs is an upper bound on the depth of v in T s ij , i.e.

h uv ijs = ≥ depth of v in T s ij , if (u, v) ∈ E(T s ij ), = ∞, otherwise.
To ease the notation, let us dene I v ijs (U ) to be the sum of y variables that correspond to incoming edges into v ∈ V from the nodes in U ⊆ V , i.e. Then, we present the formal problem formulation. The objective of the problem is to maximize the sum of the utility scores of the delivered streams through a set of delivery trees. Thus, we rst express the objective as follows:

I
max.

e∈V E k i=1 l j=1 α e ij x e ij (4.1)
The objective subjects to the following constraints:

x e ij ≤ s∈V S I e ijs (V R ) ∀i, j, e (4.2)
The constraints in (4.2) ensure that the indicator variables x have non-zero values only if there are incoming edges in the respective trees.

I r ijs (V S ∪ V R ) ≤ 1 ∀i, j, s, r (4.3)
I e ijs (V R ) ≤ 1 ∀i, j, s, e (4.4)
Constraints in (4.3) and (4.4) guarantee that every node has only one parent in every delivery tree.

k i=1 l j=1 O s ijs (V R )λ i ≤ c(s) ∀s (4.5) k i=1 l j=1 s∈V S O r ijs (V R ∪V E )λ i ≤ c(r) ∀r (4.6)
These two constraints (4.5) and (4.6) enforce the capacity restrictions on each node.

h s ijs = 0 ∀i, j, s

(4.7) h r ijs + 1 -h v ijs ≤ |V |(1 -y rv ijs ) ∀i, j, r, v (4.8)
These two constraints (4.7) and (4.8) guarantee that there is no cycle in the delivery trees.

O r ijs (V R ∪V E ) ≤ |V |(I r ijs ({s}∪V R )) ∀i, j, s, r (4.9)
I r ijs ({s}∪V R ) ≤ O r ijs (V R ∪V E ) ∀i, j, s, r (4.10)
Finally, in constraints (4.9) and (4.10), we require that reector nodes have outgoing edges in delivery trees if and only if there is an incoming edge. These two constraints accomplish the formulation of the problem.

NP-completeness

In this section, we demonstrate that the MAUS problem is NP-complete. Let DMAUS be the decision version of the MAUS problem.

Problem 2 Given topology and capacity constraints of a CDN, and a real number B, do there exist delivery tree sets,

{T ij } i∈[k],j∈[l] , such that e∈V E α e (X e ) ≥ B?
Clearly DMAUS is in NP. We now show that DMAUS is NP-hard by a reduction from 3-SAT. Recall that an instance of the 3-SAT problem consists of n variables, z 1 , . . . , z n , and m clauses, C 1 , . . . , C m , where each clause C j = (y

1 j ∨ y 2 j ∨ y 3 j ), j ∈ [m],
has exactly three literals.

Given an instance of the 3-SAT problem we construct an instance of the DMAUS problem. Let G 3SAT = (V, E) be the topology of a CDN. We dene V to be (i) a single source node, V S = {s}, (ii) 3n reectors that are partitioned into two sets, V R = Z ∪A, such that |Z| = n and |A| = 2n, (iii) and m edge servers V E = {u 1 , . . . , u m }. The node set Z = {v 1 , . . . , v n } represents the variables of the 3-SAT instance, the nodes in A = {v t 1 , v f 1 , . . . , v t n , v f n } represent the two possible values of these variables, and the edge servers represent the m clauses. Overall |V | = 1 + 3n + m.

The edge set E is composed of n links between s and the nodes in Z, 2n links that connect Z to A, and 3m links between A and the edge server nodes. More specically,

E ={(s, v) : v ∈ Z} ∪ {(v i , v t i ), (v i , v f i ) : i ∈ [n]} ∪ {(v t i , u j ) : i ∈ [n], j ∈ [m], z i is a literal in C j } ∪ {(v f i , u j ) : i ∈ [n], j ∈ [m], zi is a literal in C j }
For example, Figure 4.1 shows the CDN graph associated with a 3-SAT instance

(x 1 ∨ x 2 ∨ x 3 ) ∧ (x 1 ∨ x 2 ∨ x 4 ) ∧ (x 2 ∨ x 3 ∨ x 4
). The capacities of the nodes are dened as follows: c(s) = n and ∀i ∈

[n], c(v i ) = 1 and c(v t i ) = c(v f i ) = m.
We set the number of channels and representations to 1, and the utility score of receiving the single available representation at every edge server e ∈ V E is α e 11s = 1. Finally, the value B is chosen to be m. We now show that there is a solution to the 3-SAT problem i there is a solution to the DMAUS problem.

s v1 v t 1 v f 1 v2 v t 2 v f 2 v3 v t 3 v f 3 v4 v t 4 v f 4 C1 C2 C3
Let φ be a satisfying assignment for the 3-SAT problem instance. We incrementally construct the delivery tree T s 11 = (V s 11 , E s 11 ). At rst V s 11 = {s} and E s 11 = ∅. Then, if there exists an edge server u j / ∈ V 11 s , we pick one of the literals in C j that have a true assignment in φ (since φ is a satisfying assignment, there must be at least one such literal). W.l.o.g. let z i be a literal in C j and φ(z i ) = true. We add to the tree the nodes v i , v t i , u j and the edges (s, v i ), (v i , v t i ), and (v t i , u j ). Note that some of the nodes or the edges might already exist in the tree, so we just add the missing ones. These steps never violate the capacity constraints, as for any v i ∈ Z, at most one outgoing edge, either (v i , v t i ) or (v i , v f i ), can be added to E s 11 , which depends on the assignment φ (the rst in case φ(z i ) = true, and the latter otherwise). It is easy to conclude that T s 11 is a delivery tree rooted at s and has all the nodes V E as its leafs, and thus the utility score function has a total score of m. The feasibility of each step follows directly from the denition of the CDN topology, G 3SAT .

In the opposite direction, let T s 11 be a solution to the DMAUS problem (as there is only one representation, one channel and one source node, the solution is a single delivery tree). We construct φ by iterating over the nodes in V E . For every u j ∈ V E , if v t i is the parent of u j in T s 11 we dene φ(z i ) = true, and φ(z i ) = f alse otherwise. Note that due to capacity constraints, it is impossible that both v t i and v f i are in T s 11 , and thus the assignment is feasible, i.e. the same variable will never be assigned both true and f alse. After the iteration ends, if there are any undened variables, we set their values to true. What remains to be shown is that φ is a satisfying assignment.

For every clause C j , j ∈ [m], there must exist a literal which corresponds to the father of u j in T s 11 (due to the construction of G 3SAT ) and has a true assignment in φ (due to the iterative denition of φ), and thus C j is true.

A Practical Scenario and Algorithm

As the above NP-completeness claim implies, it is currently impossible to implement a fast optimal solution for the general case. Thus, we focus on a practical scenario which corresponds to today's CDN implementation. For this practical scenario, we propose a near optimal greedy algorithm which produces delivery trees for every channel.

Practical Bundle Delivery in CDN

In practical CDNs, one can assume that every reector is connected to any other reector by a direct link, i.e. for any u, v ∈ V R and u = v, it holds (u, v) ∈ E RR . This can be justied by the fact that the links between reectors are essentially international connections in the public Internet backbone, where any equipment is virtually connected to any other equipment. In fact, the specications of the CDN Federation [BSB + 12, Le 12] impose full connectivity between the hosts of every member CDN. In what follows we describe a fundamental and popular CDN scenario, named Homogeneous Bundle Delivery.

For services which are based on rate adaptive streaming, today's CDNs do not deliver each representation individually. Instead, they gather all representations of a given channel into one bundle, and deliver the whole bundle from the source(s) to the edge server(s). Due to the fact that the majority of transcoders are the same, all bundles have roughly the same size, which simplies the delivery management.

An example of this scenario is as follows: the client of a large-scale CDN is a prominent over-the-top (OTT) service provider, which diuses a TV package to a large audience. Every channel is bundled, with a total rate of λ = i λ i , i ∈ [k]. All the edge servers are expected to receive all the bundles in the same way, i.e. α e j = 1 for every e ∈ V E and j ∈ [l] (note the slight change of notation due to the bundling of representations). For a xed rate data stream, the capacity constraint of every node is essentially an upper bound on the number of simultaneous bundles that the node can support. For simplicity let b v = c(v)/λ be the number of bundles that can be supported by any v ∈ V S ∪ V R . As previously, we use the indicator variables x e j , e ∈ V E , j ∈ [l], which have the value of 1 if the edge server e receives the bundle of the j-th channel. As a result, the objective for this scenario can be summarized as follows:

max j∈[l] e∈V E x e j .

The Bundle-Delivery Algorithm

In this section, we describe a fast near-optimum algorithm which is named as Bundle-Delivery for the above practical scenario. The notations used for the description of the algorithm is shown in Table4.2.

First of all, for simplicity of exposition, and following our assumption of full connectivity between the source and reector nodes (E SR ), we can assume there is a single super-source s * with upload bandwidth b s * = s∈V S b s . Note that any solution for the case of having a single super-source can be easily converted into a solution s *

The super-source

λ = i λ i
The bit-rate of a bundle of all representations

T j

The delivery tree of the j-

th channel b v = c(v)/λ
The capacity measured on number of bundles for v ∈

V S ∪ V R b j v
The residual capacity of v after the constructure of T j f j v The number of boundle forwarded by v in T j Table 4.2: Notations for the Bundle-Delivery algorithm with multiple sources by distributing the load among the sources according to their upload capacities.

The detailed Bundle-Delivery algorithm is depicted in Algorithm 3. The Bundle-Delivery algorithm is composed of two phases. In the rst phase (from line 2 to line 12 in Algorithm 3), we iteratively construct one delivery tree T j for every channel j, j ∈ [l]. Then, in the second phase (from line 13 to line 15 in Algorithm 3), we provide a local improvement (named as 2-hop connection improvement) for potentially unused capacities in the rst phase. Each iteration of the rst phase can be further divided into two parts: rst we decide the set of reectors V j ⊆ V R will be be used as forwarding nodes in T j (from line 4 to line 11 in Algorithm 3); then, based on this set of forwarding reectors, we generate the delivery tree T j in line 12 of Algorithm 3.

The general motivation behind the algorithm is that by reducing the number of nodes in every T j we also reduce the amount of capacity wasted on inter-reector communication (because in the tree structure, the inter-connection capacity equals to the number of nodes in the tree minus 1). Based on our assumption of complete graph, for each delivering tree, the problem is selecting a minimum number of reectors (V j ) with sucient aggregate capacity. To achieve that, V j is composed of reectors with the maximum residual capacity at that time which is sucient to deliver the j-channel bundle to as many edge servers as possible. Note that nodes with residual capacity of 1 are not used in the rst phase due to the fact that having them as inner nodes in some T j is not benecial in any way (as they can forward a bundle to only one node). Instead, we use 2-hop connections in the second phase to utilize their capacity.

There are two main sets of variables in the algorithm. For every node v ∈ V R we use b j v , 0 ≤ j ≤ l, to denote the residual forwarding capacity of node v after the construction of trees T 1 , . . . , T j , i.e. the capacity which remains at v to forward bundles for channels j +1, . . . , l after it has already forwarded the bundles for channels 1, . . . , j. We also dene f j v , for every v ∈ V R , j ∈ [l], to be the number of bundles forwarded by v in T j , i.e. the number of children v has in T j . After V j is determined, these variables are updated according to the forwarding capacity used by each node in V j and construct the corresponding tree. After the construction of each tree, we update the number of bundles that can still be forwarded by the reectors and the super-source s * . This process continues until either all the channels are delivered to all the edge servers or the forwarding capacity of the super-source and/or the reectors is exhausted.

In the following, we explain the process of the tree construction and the two hop Algorithm 3: Algorithm: Bundle-Delivery

1: Initialize ∀v ∈ V R : b 0 v ← b v and j ← 1 2: Phase 1: 3: while ∃v ∈ V R : b j-1 v ≥ 2, b s * ≥ j, and j ≤ l do 4: Initialize V j ← ∅ and U j = {u : b j-1 u ≥ 2} 5: Initialize ∀v ∈ V R : f j v ← 0 6: while v∈V R f j v < |V j | + |V E | -1 and U j = ∅ do 7:
Extract from U j a node u * with maximum forwarding capacity, i.e. b j-1 u * = max u∈U b j-1 u 8:

f j u * ← min{b j-1 u * , |V E | + |V j | -v∈V j f j v } 9: Add u * to V j 10: Update ∀v ∈ V R : b j v = b j-1 v -f j v 11: Update j ← j + 1 12:
Construct delivery tree T j based on the nodes V j 13: Phase 2: 14: if not all edge servers receive all channel bundles and b s * > l then 15:

Use 2-hop connection improvement to deliver channel bundles connection optimization in detail.

Construct Delivery Tree

For every channel j, T j is a tree which is rooted at s * , has V j as its intermediate nodes, and some or all of V E as its leafs. The out-degree of every node v ∈ V j in T j is exactly f j v . The topology of the tree can be arbitrary with a single constraint, that the super-source has exactly one child in T j .

The topology of T j has no eect on the number of leafs in T j , which is ( v∈V j f j v -|V j | + 1) (as we show later). For live streaming, the source-to-end delay should be minimized. Thus, we would ultimately like the tree to have the minimum possible height to minimize the number of hops from the super-source node to the leafs. Minimizing the height of the delivery tree also reduce the latency from the root to the leaves in the tree. For that purpose, we construct T j in the following way.

• First connect s * to the node v with maximum value of f j v in V j .

• Then, connect v to f j v nodes with the next highest values of f j in V j , and repeat this process for every node in V j \ {v} according to decreasing value of f j until all the nodes in V j have a parent in T j .

• In the end of the above process, some nodes will have an out-degree less than the corresponding value of f j . Connect these nodes to a subset of edge servers, yet to be included in T j , such that the degree of those nodes will match their f j values (Lemma 1 below shows that it is always possible).

s * u v (1)
s * u v (2)
s * u v Figure 4.2: T j generation: V j = {u, v}, f j u = 3, f j v = 2. (3)
forwarding capacity than v, it is connected to s * and v is set as the child of u (Figure

). At this point the out-degrees of u and v are 1 and 0, respectively, which are less than their forwarding capacities in T j . Thus, both u and v are connected to 2 edge servers each (Figure

Two-hop Connection Improvement

Let j * be the last channel for which a delivery tree T j * was constructed. It is easy to observe that the trees generated are feasible delivery trees rooted at s * , where T j delivers the j-th channel bundle, j ∈ [j * ]. In the tree construction phase, for each tree, the super-source consumes 1 unit of upload capacity (because we restrict the number of children of the source to 1). Thus, after the tree construction phase, the source node might have some unused forwarding capacity.

As we show later, if not all edge servers receive every channel bundle, then every reector v ∈ V R has a forwarding capacity of b j * v ≤ 1. The second phase of the algorithm (2-hop connection improvement) aims to improve the performance by using the unused source and reectors capacity. Thus, we use reectors with non-zero forwarding capacity to deliver additional channel bundles to edge servers that are yet to receive them in a two-hop fashion

s * → v → u, where v ∈ V R with b j * v = 1, and u ∈ V E such that u is not a leaf in T i .
In the following Lemma 1, we will show that all the leafs in T j are edge server nodes.

Lemma 1 In every constructed tree T j there are exactly

v∈V j f j v -(|V j | -1) leafs and v∈V j f j v -(|V j | -1) ≤ |V E |.
Proof . Note that for any T j , j ∈ [l], the root s * has exactly one child. Therefore, |V j |-1 nodes have a parent node which is a reector. According to the tree construction in Algorithm 3, every reector v ∈ V j has an out-degree of f j v in T j . Thus, we can conclude that in T j a total of |V j |-1 forwarding capacity is used to deliver the channel bundle between reector nodes, which results in T j having v∈V j f j v -(|V j | -1) leaf nodes. In Algorithm 3, line 7 and line 8 enforce the inequality v∈V j f j v -(|V j | -1) ≤ |V E |, and therefore we can conclude that tree construction (line 12) is feasible, i.e. it is always possible to connect a reector v to some edge server, yet to be in T j , to ll the out-degree of v in T j .

Performance Analysis

In this section, we provide a detailed performance analysis of the Bundle-Delivery algorithm.

Running time

There are three main steps which contribute to the running time of the Bundle-Delivery algorithm.

• The initialization step (line 1 in Algorithm 3) and takes O(|V R |) time to execute.

• The second step is the tree construction phase (from line 2 to line 12 in Algorithm 3). We need to maintain the information about the residual forwarding capacity at every reector. This can be easily implemented by using an ordered list. At rst the reectors are sorted in decreasing order according to their initial forwarding capacity (b

0 v , v ∈ V R ).
Then, during the execution of the inner loop (line 6 to line 9 in Algorithm 3), for every j ∈ [l] at most one node in V j will not use all of its forwarding capacity in T j . Removing all the nodes except for, possibly, the last one, and moving the last one in the ordered list according to its updated residual capacity, takes O(|V R |) time. Clearly the use of the ordered list allows an easy implementation of the collection of nodes U j , as we are only interested in the information about the residual capacities in decreasing order.

Tree generation itself takes linear time in |V

j | + |V E |. Thus, the total running time of the second step is O(|V R | log |V R | + l • |V R | + l • |V E |).
• Finally, the third step (the 2-hop connection improvement) takes O(b

s * + |V R | + |V E |) time.
To conclude, the running time of Bundle-

Delivery is O(|V R | log |V R | + l • |V R | + l • |V E | + b s * ).

Approximation ratio

Then, we will theoretically analyze how our algorithm approaches to the optimum solution by measuring the approximation ratio. In the analysis we ignore the 2-hop connection improvement phase of the algorithm, as it has no direct eect on the performance bounds, but rather serves as a local improvement, which may or may not occur.

Let S and S * be the values of the solution obtained by Bundle-Delivery and the optimal one, respectively. The next lemma shows that either the unused capacity of every reector is at most 1 or S = S * .

Theorem 1 Following the execution of Bundle-Delivery and under the assumption that

S * ≥ |V E |, S/S * ≥ 1 -(b s * /|V E |).
Proof . We start by drawing an upper bound on the optimal solution. The number of edge servers that can potentially be reached by all the reectors is at most

v∈V R b v .
However, some of the capacity needs to be used to maintain the delivery trees (sourcereector, and reector-reector connections). In the best case scenario (in terms of wasted capacity), every node is used in only one tree, and b s * reectors have s * as their parent in one of the delivery trees. Thus,

S * ≤ v∈V R b v -|V R | + b s * .
Next we analyze the solution produced by Bundle-Delivery. If there exists a node v ∈ V R such that b j * v > 1 (recall that T j * is the last tree to be constructed), then according to Lemma 2, S = S * . Otherwise, for every

v ∈ V R , b j * v ≤ 1. Let x = |{v : b v > 1, b j * v = 1}|
be the number of nodes that had their residual bundle capacity reduced to 1 during the execution of the algorithm, and y = |{u : b u = 1}| be the number of nodes with bundle delivery capacity of 1 prior to the execution of the algorithm. Hence the total forwarding capacity used in all the delivery trees (before the 2-hop connection improvement),

j∈[j * ] v∈V j f j v = v∈V R b v -(x + y).
Note that when a node u * is selected to be added to V j , j ∈ [j * ], in line 7 of Algorithm 3, it cannot be used again unless it was the last node to be added to T j (due to the computation of the forwarding capacity f j u * ). Thus, the total number of reectors in all the delivery trees is the number of potentially participating nodes (v ∈ V R , with b v > 1) plus at most j * -1 times a node might appear in two and more trees (due to the partial assignment of f ). Formally, j∈

[j * ] |V j | ≤ |V R | -y + j * -1.
Based on Lemma 1 and the above we can now derive a lower bound for our solution. As discussed in the beginning of this section we ignore the 2-hope connection improvement in our evaluation (it can only improve the lower bound of S * ).

S = j∈[j * ]   v∈V j f j v -(|V j | -1)   = j∈[j * ] v∈V j f j v - j∈[j * ] (|V j | -1) ≥ v∈V R b v -(x + y) -(|V R | -y + j * -1) + j * = v∈V R b v -|V R | -x + 1
As we derived in Lemma 2, when a partial forwarding capacity

f j v < b j-1 v is assigned to some v ∈ V j , j ∈ [j * ],
the delivery tree T j has |V E | leafs. As we already stated in this proof, at most one node can be assigned a partial forwarding capacity in each tree, and thus there is a partial assignment in at least x delivery trees. As a result, S ≥ x|V E |. On the other hand, S ≤ S * ≤ l|V E |. Summarizing all of the above and under the assumption that S * ≥ |V E | we obtain the approximation ratio of the Bundle-Delivery algorithm as:

S/S * ≥ S * -x -b s * + 1 S * = 1 - x + b s * -1 S * ≥ 1 - 1 |V E | - b s * -1 S * ≥ 1 -(b s * /|V E |).

Evaluation

We now evaluate the approximation ratio, S/S * of the Bundle-Delivery algorithm proposed in Section 4. 4.4), the Bundle-Delivery algorithm achieves an approximation ratio of 1 -10 -3 . For networks with 1,000 edge servers, the ratio S/S * is at least 0.999056, and starting from x = 10,000 it is above 0.999906. Moreover, it should be noted that the computations were carried out in less than 30 seconds for every instance on a standard desktop PC. The evaluation demonstrates that our algorithm runs fast, and could obtain near optimum solutions.

Conclusions and future work

In this Chapter we introduced the discretized streaming model, which represents multiple rate adaptive live videos delivery in today's CDNs. We rst formulated a general optimization problem for prioritized live video delivery which we showed to be NP-complete. Then, we focused on a realistic scenario: the CDN provider is in charge of delivering the representations of each channel as one bundle. We developed a fast and simple algorithm that guarantees a solution which is at least 1 -(b s * /|V E |) times the optimal solution. To the best of our knowledge, this is the rst result for the discretized streaming model [START_REF] Liu | Fast near-optimal algorithm for delivering multiple live video streams in cdn[END_REF].

The work presented in this Chapter provide a fundamental theoretical basis toward live rate adaptive streaming in CDN. First of all, the problem formulated is a general problem, with undened utility function. It is of great importance to explore the computation of the utility score, which is inuenced by a large number of parameters, especially in the context of live rate adaptive streaming where the demand from clients may change very quickly. Secondly, the algorithm proposed in this work assumes complete graph CDN topology, consequently, in future work, it would be interesting to design algorithms for general CDN topologies.

In the next Chapter, we further explore the above limitations of this work. We specialize the general problem in to a user-centric problem such that the utility of an edge server on streams represents the QoE perceived by the users of the edge server on receiving the stream. Thus, the objective is to maximize overall user satisfaction on the services. Moreover, we redesign the three CDN functionalities (content placement, content delivery and user assignment) to build a practical CDN system that delivers live rate adaptive streams to a large audience in a dynamic environment. General delivery trees construction algorithm for random graph CDN topology is proposed. Rate adaptive streaming (also referred to as DASH) is designed to serve heterogenous video consuming devices. The objective is to maximize the Quality of Experience (QoE) of diverse users characterized by their end devices and access links. Rate adaptive streaming accomplishes this objective by providing multiple representations for the users. The users dynamically and adaptively choose the representation best ts to its characteristic. A consequence is that users are capable to play any of the representations (out of the alternative ones), on which the users perceive dierence levels of QoE. Out of all alternative representations, a user prefers to receive the one having the highest QoE. As the CDN capacity is dedicated to nally earn user satisfaction, a challenge for CDN providers is to design user-centric live video deliver scheme that maximizes the user satisfaction on the live streams delivered through its infrastructure.

As we have discussed in Chapter 4, the rapidly increasing live video trac and the multiple representations characteristic of rate adaptive streaming impose a heavy transmission burden on the CDN delivery network. Consistently, we consider (1). the most critical resource to provision is the overall amount of data that CDN equipments can emit per unit of time, and (2). the CDN infrastructure is underprovisioned. That is, the CDN infrastructure is not capable to convey all representations of requested contents to all the edge servers.

For the user-centric delivery, we reuse the discretized streaming model proposed in Chapter 4, which is especially designed for rate adaptive streaming in modern CDNs, by exploring the utility of edge servers on the streams. Typically, the utility connects the stream delivered to the edge server with the value appraised by users on the edge server to the stream. By dening user QoE based utility function, the user-centric discretized streaming model maximizes the user satisfaction on the delivered streams.

More specically, in the underprovisioned CDN, instead of serving all representations of a given channel to edge servers requesting this content, the model prioritizes the delivery of representations to the edge servers according to the user satisfaction level on the representations.

Our Contributions

We accomplished two contributions for the user-centric live rate adaptive streaming in CDN network, including a theoretical optimization problem formulation and a practical system. In the following, we summarize the two contributions separately. Contribution 1. The rst contribution relates to a theoretical optimization problem. First of all, we propose a QoE model which measures the user satisfaction level on the received representations. This model permits to dene a user QoE based utility function. The user-centric delivery scheme depends on such utility to evaluate streams by how users are satised with them. Then, we formulate a joint optimization problem based on the discretized streaming model presented in Chapter 4. The objective is to maximize the overall user satisfaction, as well as guarantee the maxmin fairness on user satisfaction levels. Further, we introduce new variables in order to make the model jointly decide three problems: (1) the representation that should be sent to the edge servers, (2) a set of delivering trees and (3) the assignment of users to edge servers. These three problems correspond to the three main mechanisms implemented by CDN providers: content placement, content delivery and user assignment. Through a set of simulation on a toy-CDN infrastructure, we demonstrate that the user-centric discretized streaming strategy could achieve higher user satisfaction comparing to the previous approaches. The rest of this Chapter is organized as follows. We describe in Section 5.2 the model that measures user satisfaction on representations. The optimization problem is formally given in Section 5.3 and evaluated in a toy-CDN infrastructure in Section 5.4.

We present in Section 5.5 a practical implementation of a CDN system for delivering live rate adaptive streams. We provide in Section 5.6 a rst evaluation based on a large-scale real-trace simulator. Finally, Section 5.7 concludes this work.

User-centric Discretized Streaming Model

When the delivery system is underprovisioned, a service provider cannot oer as many video representations as it would with a well-provisioned delivery system. As a consequence, the representation that ts the best a given user's downloading capability might not be oered by the CDN. This situation forces users to get a lower bit-rate video representation, hence with a lower quality.

We introduce the concept of user satisfaction for every user and every representation. The model we propose simplies the reality, but it takes into account two major features of rate adaptive streaming: (i) representations are encoded with pre-dened settings, and (ii) each end-user is characterized by a highest viewable representation.

Intuitively, it measures how far is the received representation to the best possible one for a given user. We detail this concept in Section5.2.1.

User satisfaction

The ideal way to measure the QoE perceived by human viewers is to run subjective tests and to combine the obtained scores into a Mean Opinion Score (MOS). An MOS traditionally ranges from 1 to 5, where 1 stands for bad quality and 5 for excellent quality. However, subjective test campaigns are costly to conduct and require time. We focus on the bit-rate parameters to measure QoE because it is a central parameter of rate-adaptive streaming. Indeed, (i) representations are encoded with pre-dened bit-rates, and (ii) each end-user is characterized by her highest viewable representation, which is the representation that the user can download with the highest bit-rate. In Fig. 5.1(b), we depict a typical MOS prole for a video. Without loss of generality, we combined the bit-rate QoE model given in [YH08] and the bit-rates recommended by Apple for the set of video representations in HTTP Live Streaming (see Table 5. 1 and [appb]). As can be expected, the MOS grows when the encoding bit-rate increases, but the growth is not linear. However, such MOS-based models of representations do not fully capture the satisfaction of a heterogeneous population of end-users. Indeed, the QoE depends on the context of video consumption [START_REF] Mitra | A probabilistic context-aware approach for quality of experience measurement in pervasive systems[END_REF]. For example an end-user watching a 0 1.0 2.0 3.0 4.0 5.0 Previous context-aware QoE models such as [START_REF] Mitra | A probabilistic context-aware approach for quality of experience measurement in pervasive systems[END_REF] do not consider multirepresentation streaming. Thus, we introduce the relative satisfaction metric (or satisfaction in short). We normalize the satisfaction of a given user getting a given representation to the satisfaction obtained if she gets her best possible representation.

This relative satisfaction is thus between 0 and 1. We show in Fig. 5.2 the relative satisfaction of an end-user who cannot play a video above the fourth representation.

We used the same MOS as in Let us now introduce some notations. The set of end-users is noted N . For each user n ∈ N , we denote by i n the index of the best possible representation, and by j n the index of the channel she is watching. Thus, d i n j n is the best possible representation requested by user n. We then dene a function M OS(d ij , n), which is the QoE rating of user n for representation d ij . In comparison with the plain MOS prole (Fig. 5.1(b)), this MOS score is user-related. There are two cases:

• End-user n can decode and watch d ij (i ≤ i n and j = j n ). In this case, the value of M OS(d ij , n) is the plain MOS prole of the representation M OS(d ij ).

• End-user n cannot decode and watch d ij (i > i n or j = j n ). In this case, we force M OS(d ij , n) to be equal to one (the least MOS score value). In of the population. It is the case here: users watching low-resolution representations will be served rst because satisfying them has a lower impact on the infrastructure in comparison to satisfying users watching high-denition (HD) representations. We thus need another objective function, which avoid such bias. A way to mitigate such weaknesses is to ensure some degree of fairness among the end-users. A simple user-centric objective is formulated as a max-min, where the goal is to maximize the satisfaction of the user that is the most poorly served, which is formally given by:

Obj maxmin : min n   e∈V E i∈[k] j∈[l] u n ij • z ne ij |∀n ∈ N   (5.3)
Due to the aforementioned weaknesses, we emphasize on the max-min objective depicted in Equation (5.3). Therefore, the overall objective function is dened as:

maximize ε • Obj global + Obj maxmin (5.4)
where is chosen to be small enough so that Obj maxmin always dominates Obj global .

In other words, the user-centric discretized streaming capacity problem is formulated as, rstly ensuring that all end-users have a decent satisfaction, and then maximizing globally the satisfaction of the whole population. In the following, we formulate an ILP model with this objective. It is worth to note that other objective functions can also be considered.

Integer Linear Program Formulation

We formulate an ILP model for the user-centric discretized streaming capacity problem. We reuse the variables dened for the discretized streaming ILP model:

y uv ijs = 1 if (u, v) ∈ E(T s ij ), 0 otherwise. h uv ijs = ≥ depth of v in T s ij , if (u, v) ∈ E(T s ij ), = ∞, otherwise. I v ijs (U ) = u∈U y uv ijs O v ijs (U ) = u∈U y vu ijs
In CDN, it is frequent that an edge-server is assigned to a given population of end-users, or a geographic area. For example, an edge-server can be located within the network of an Internet Service Provider (ISP) to serve exclusively clients of this ISP. We dene another binary variable:

• p e n = 1 indicates that user n ∈ N can be assigned to edge server e ∈ V E , 0 otherwise.

Constraint (5.5) makes sure that users get at most one representation from one edge-server.

e∈V E i j z ne ij ≤ 1 ∀n (5.5)
With constraint (5.6) edge-server send only the representations they receive.

z ne ij ≤ x e ij ∀n, e, i, j

(5.6) Constraint (5.7) redirects users to proper edge-servers.

z ne ij ≤ p e n ∀n, e

(5.7) Constraint (5.8) does not allow the delivery of representations that are not associated with a positive satisfaction.

z ne ij < u n ij + 1 ∀n, e, i, j

(5.8) Constraint (5.9) restricts edge-server capacity.

n∈N i j z ne ij • λ i ≤ c(e) ∀e
(5.9)

Then, the remaining constraints construct trees from source to edge-servers, which are identical to the Constraints from 4.2 to 4.10 presented in the ILP formulation of the discretized streaming model (Section 4.3). For uent reading, we repeat these constraints and shortly explain them:

x e ij ≤ s∈V S I e ijs (V R ) ∀i, j, e

(5.10)

I r ijs (V S ∪ V R ) ≤ 1 ∀i, j, s, r (5.11)
I e ijs (V R ) ≤ 1 ∀i, j, s, e

(5.12)

k i=1 l j=1 O s ijs (V R )λ i ≤ c(s) ∀s (5.13) k i=1 l j=1 s∈V S O r ijs (V R ∪V E )λ i ≤ c(r) ∀r (5.14)
h s ijs = 0 ∀i, j, s

(5.15)

h r ijs + 1 -h v ijs ≤ |V |(1 -y rv ijs ) ∀i, j, r, v (5.16) O r ijs (V R ∪V E ) ≤ |V |(I r ijs ({s}∪V R )) ∀i, j, s, r
(5.17)

I r ijs ({s}∪V R ) ≤ O r ijs (V R ∪V E ) ∀i, j, s, r
(5.18) Constraint (5.10) indicates that if there is no incoming edge, the stream is not received on the edge-server. Constraints (5.11) and (5.12) enforce a single parent in every tree. Constraints (5.13) and (5.14) enforce capacity restrictions. Constraints (5.15) and (5.16) prevent cycles in every tree. Constraint (5.17) states that if there is no incoming edge in a tree, there cannot be outgoing edges as well. Finally Constraint (5.18)forces reectors to have at least one output edge if they have an incoming edge in a tree.

This ILP model solves the three main CDN functionalities all at once. The optimal solution jointly indicates : (1) which representations are sent to which edge servers;

(2) how to deliver streams from CDN sources to CDN edge servers; and (3) how users are assigned to edge servers.

Proof-of-Concept for User-centric Discretized Streaming

We now show the relevance of our approach to address the challenge of maintaining a high satisfaction on a population of users in a context of underprovisioned CDN.

We considered a very simplied context. Our goal here is not to mimic the reality (we conducted realistic simulations in the following Section 5.6). It is rather a proofof-concept to illustrate the benets one can expect from our model. We implemented the ILP model in IBM ILOG CPLEX optimizer and computed the best achievable delivery in the following network conguration.

Due to the complexity of the ILP model, we evaluate the model in a toy CDN network, which consists of one source, two reectors and eight edge-servers. Figure 5.3

shows the topology. This infrastructure has been reserved and provisioned by the CDN provider to serve one channel, which is encoded in eight dierent representations.

The bit-rates of the representations are set according to the recommended Apple HTTP Live Streaming (see Table 5.1 and [appb]). We considered a population of 360 end-users interested in this channel. The number of users is set to a proper value to make sure that the bottleneck of the video delivery lies within the CDN delivery network, rather than the links between edge servers and end users. Users require one of the 8 representations based on their devices and access networks. The characteristics of devices and network connections (see Table 5.2) are inspired by some recent statistics collected during London Olympic games [nbc].

We assumed a scenario where the CDN provider has severely underprovisioned its infrastructure. The upload capacity of each source is 10 Mbps, which is enough to send all representations. However, the upload capacity of each reector is only 7. We refer to this approach as the traditional approach. To measure performances, we compute the Cumulative Distribution Function (CDF) of the satisfaction of users (see Figure 5.4). A point at (0.6, 0.2) means that 20% of users experience a relative satisfaction greater than 0.6.

We can immediately see in Figure 5.4 the weaknesses of the traditional approach based on the streaming capacity problem. The QoE is far from what can be obtained with a dedicated approach. With the traditional approach, two thirds of users have a satisfaction below 0.75 although there exist solutions where all users have a satisfaction over 0.82. highest one) are hosted in at least one edge server. On the contrary, the traditional approach provides the same set of representations to all edge servers. It is important to notice that the overall number of representations sent to the edge servers is larger in the traditional approach, but the diversity of these representations is lower. Moreover, the ILP is able to adjust the number of representations to both the capacity of the edge servers and the demand from end users.

Our second important observation is that our optimization problem is able to keep a high level of user satisfaction despite the very limited CDN infrastructure. Almost three quarters of the population do not experience any degradation although CDN capacity is less than one fth of what it should be. These results being promising, we developed algorithms that can be implemented in a real system based on the principles of the user-centric discretized streaming model. In the following, we describe the practical live rate adaptive streaming CDN system.

A Practical System: scadoosh

We describe now a practical implementation for CDNs. The overall system is named scadoosh, which stands for SCAle Down fOOtprint for live daSH. scadoosh aims to eciently exploit CDN infrastructure to deliver live video streams to a dynamic, large population of users. We use the nomenclature of the DASH standard, but scadoosh is independent of the implemented rate-adaptive technology.

In addition to the traditional 3-tier CDN infrastructure, scadoosh requires a centralized organizer, which we call a coordinator. The coordinator is in charge of orchestrating the delivery into a CDN network. Most CDNs rely on such a global coordinator, which manage the whole network or a restricted area. For simplicity, we consider hereafter one coordinator and one network, but multiple coordinators can co-exist in a giant CDN as long as the boundaries of the network they rule are well dened. For example it makes sense to consider one coordinator by continent for the largest CDNs. A scadoosh coordinator executes three main algorithms:

• User assignment algorithm aims to assemble users with similar requirements.

The result of this algorithm is a user distribution over the edge servers.

• Content placement algorithm calculates content utility, based on the reports scadoosh coordinator scadoosh coordinator scadoosh coordinator • Delivery trees construction algorithm determines a utility-driven multi-tree overlay that delivers videos from sources to edge servers.

We represent scadoosh in Figure 5.6 on a simple small CDN infrastructure where source, reectors and edge servers are depicted with a diamond, squares and circles respectively, and the CDN covers two ISP networks (gray clouds). The ISP on the left is even separated into two sub-networks (typically mobile and residential). scadoosh synchronizes on DASH periods (dened in DASH Media Presentation Description (MPD) le) to cope with the dynamic feature of rate-adaptive live streaming. For every period, scadoosh performs three actions:

1 every edge serves periodically reports to the coordinator about the last period. This report may include the number of served clients, the popularity of the dierent channels, the popularity of the dierent representations.

2 Upon reception of these reports, the coordinator can estimate the popularity of streams for the next period, and compute the utility score for every edge server and every stream. The utility score indicates the preference of an edge server to receive a given stream. Once utility scores of every edge server have been computed, the coordinator determines a multi-tree delivery where one tree is an overlay for the delivery of one representation stream. The coordinator aims at constructing a forest such that the edge servers receive their preferred streams.

The information about this forest overlay is sent to origin servers.

3 The edge servers are informed about the stream that they will receive during the next period. They can build their DASH MPD les accordingly. Then, users update the MPD le and use the new le to fetch upcoming content for the next period. During the whole next period, the sources and reectors use the multi-tree overlay to deliver the incoming live streams.

Type Specied User Assignment

How to assign an user to an edge server when the user starts a streaming session is generally the responsibility of the CDN providers through a DNS redirection scheme.

A tool like GeoDNS has been used for years on that purpose [geo]. In the case of proprietary delivery platforms, studies showed that the redirection depends on both network proximity, load-balancing [TFK + 11a] and business issues [START_REF] Plissonneau | A longitudinal view of http video streaming performance[END_REF]. In conformance with [START_REF] Kumar Adhikari | Where do you "tube"? uncovering youtube server selection strategy[END_REF], we assign here every end user to only one edge server and we promote a policy where the end users are assigned to edge servers according to the characteristics of their devices and network connections. Some network scientists have advocated such policy before us [tel]. We will show later that signicant gains in terms of CDN infrastructure can be achieved if the CDN is able to adequately redirect requests with regard to the specialization of edge servers. In the following, we present a practical (a.k.a. simple) implementation of such type-based user assignment.

In DASH, users have 2-dimension requirements: the watching channel and the requiring representation determined by the DASH rate adaptation algorithm. User assignment determines user distribution on edge servers, and further drives the usercentric content placement. This new characteristic allows for novel user assignment strategy that is aware of the second dimension of user requirement. Servers serve users who request videos from a wide spectrum of end devices. Proactively preposition all the representations on edge servers provides full DASH adaptation exibility. However, this is highly demanding on the CDN infrastructure. Assembling users with similar demand can mitigate the transmission burden on CDN infrastructure, while also provide certain DASH adaptation exibility. User requires representation based on the characteristics of their devices and access link. Consequently, users type can be used as the indicator of their requirement.

Consequently, we roughly distinguish three families of user types: mobi, HD and norm. In short, the mobi family is for users with mobile devices and low bandwidth network connections, the HD for users with high prole, and last, the norm is the nonspecialized family, which stands for other types of users and trac load redirected from the rst two families. Note that ner divisions with a higher number of families can be possible. End-users naturally drive the choice of the session family: an enduser watching the channel from her smartphone or having a poor network connection falls naturally in the mobi family while an end-user consuming the video on a High-Denition TV is a HD user.

With rate-adaptive streaming technologies, each family can be associated with a subset of representations. Users with the same type are assigned to be served by the same edge servers. Accordingly, edge servers are also specialized into three types: the mobi servers serve users from mobile devices, the HD servers are for users with high prole, last, the norm servers are the non-specialized servers which stand for other types of users and trac load redirected from the rst two types of servers. Indeed, we would like to leverage the fact that HD representations are rarely demanded by edge servers in the mobi family while HD edge servers should not require low-quality representations.

The technologies to identify users' family is out of the scope of this work. Here we only discuss shortly a possible plan for user identication. For mobi users, the mobile device detection technologies have been developed from the earliest days of the mobile web. Typically the HTTP User-Agent header eld allows any server to distinguish HTTP requests from mobile devices. Other quick testing can be done at session openings to roughly test the network connection. Then, in order to further recognize HD users from the other wired users, a concept of user prole can be used for the registered users. The prole of a user records the historical percentage of HTTP requests for HD segments when the video requests are NOT released from mobile devices. This prole can work as an indicator of user type, as users with high Internet access connections resided (such as FTTH and high speed ADSL) are more likely to have a high prole. Then, the wired users can be further categorized into HD users who are more likely to demand HD representations, and norm users who stand for the rest. Hereafter, we assume that the coordinator is able to identify the family of every user.

Once a user connects to the system, a number of live channels are made available to her. When the user clicks on the thumbnail of the video, an HTTP GET request is routed to the user assignment component. This component recognizes the type of the user. Then, the user assignment algorithm works as follows:

1. The algorithm rst searches for edge servers (1) from the same family, (2) within the same area (e.g. ISP), (3) hosting users watching the same channel, and [START_REF] Buyukkaya | Level-based peer-to-peer live streaming with rateless codes[END_REF] with load lower than a pre-dened threshold. If some edge servers match these requirements, the user is assigned to one of them by a random choice.

2. Otherwise, the algorithm restricts lookup to norm edge servers (1) within the same area, (2) hosting users watching the same channel, and (3) with load lower than the threshold. Similarly, the user is assigned to one of such servers.

3. Finally, if no edge server is found in the above steps, the user is assigned to the norm edge server within the same area with the minimum trac load. Otherwise, the system cannot provide live video service for this user.

Then, the user fetches a MPD le from the edge server, which states the base URL of the video, the available video representations, segments and their relative URLs.

After parsing the MPD le, the user requests the upcoming segments and plays the video.

There are several benets of the type specied user assignment: (1) Assembling users watching the same channels can provide DASH adaptation exibility. When DASH make adaptation decisions, the alternative representations are also required by some other users, thus already made available on the edge server.

(2) Assembling users with the same type can maintain high QoE with less load on the CDN infrastructure.

For mobi edge servers, the HD representations are rarely demanded, on the contrary, HD edge servers normally do not require low representations. Consequently, a subset of representations is sucient to provide high user QoE levels.

(3) Further, the redirection mechanism is aware of edge server area and trac load, thus curbs interdomain trac and provides server load balancing.

It is worth to mention that the composition of user types determines that of edge servers. The coordinator is in charge of setting the family for each edge server. Strategies to dynamically change the conguration of edge servers according to users demand have been recently developed [START_REF] Wang | Calms: Cloud-assisted live media streaming for globalized demands with time/region diversities[END_REF]. Such work complements our proposal.

Utility-based Content Placement

The intuition behind content placement is that we need to prioritize the delivery of certain representations over others for each edge server. In the system, we propose a simple function, where the utility of a representation d ij at the edge-server e ∈ V E (dened as α e ij in Chapter 4), is expressed as the potential aggregated satisfaction of all users that are served by e. Let N e ⊆ N be the set of end-users served by e.

Formally, we have:

α e ij = n∈Ne u n ij , ∀e ∈ V E , ∀i ∈ [k], ∀j ∈ [l]
A high utility for a representation d ij for e means that a large number of end-users served by e can be highly satised by d ij . Therefore the representation d ij should be delivered to e in priority. However, to compute the utility, the coordinator should know the requests that will be issued during the next period. The main challenge is that the number of requests for a given representation at an edge-server can dramatically and unpredictably change between two consecutive periods. To address this problem, we propose in the following a solution based on time series forecasting, where the coordinator leverages requests from previous periods to predict the requests for the next period, for every representation on every edge server.

The forecasting model that we utilized is called Autoregressive Integrated Moving Average (ARIMA) [BJ90]. This model has already proven its eciency for the popularity of channels in IPTV system [START_REF] Wu | On Dynamic Server Provisioning in Multichannel P2P Live Streaming[END_REF]. The algorithm is as follows:

1. Until sucient records are collected (50 periods are suggested in [BJ90]), the coordinator anticipates that the number of requests for each representation at each edge-server in the next period will be exactly the same as in the previous period.

ne ij (T + 1) = 2n e ij (T ) -n e ij (T -1) + a e ij (T + 1) -θ e i,j a e ij (T )
where n e ij (T ) and n e ij (T -1) are the records in periods T and T -1, and a e ij stands for random errors. In forecasting, the error for the future is treated as zero, thus a i,j e (T + 1) = 0. The error for the past is estimated as the dierence between the real value and the predicted value, thus a e ij (T ) = n e ij (T ) -ne ij (T ). The coecient θ e ij can be estimated from the least squares algorithm. To cope with dynamicity, we used the method suggested in [START_REF] Wu | On Dynamic Server Provisioning in Multichannel P2P Live Streaming[END_REF]: For each prediction ne ij (T ), we compare the real value n e ij (T ) against its 95% condence interval. If ve continuous real values lie outside the interval, the latest fty observations are used to retrain the θ e ij parameter, and the new θ e ij is used for the following prediction.

We show the quality of the video population prediction for both video types in Figure 5.9(a) and Figure 5.9(b). We utilize the standard way to show the performances of such prediction tools with overlapping curves. As shown in the gures, the ARIMA model is capable to accurately predict population changes for both types of videos.

Utility driven delivery trees construction

After the utility scores are determined, scadoosh coordinator constructs the delivery overlay. It knows (i) the status of the infrastructure, the graph G, and the available upload capacity of every source in V S and every reector in V R , and (ii) the utility score of every edge server in V E for every representation of every channel.

We describe now the algorithm that builds a multi-tree delivery overlay over the CDN infrastructure (shown in Algorithm 4). The main idea is to create delivery links between an edge server and one of the equipments (source or reector) that are able to deliver the representation. We process representations iteratively based on the utility score per rate unit (uspru). The uspru is computed for every representation d ij at G d ← augment G with node t, edges (t, s), s ∈ V S and edges (t, r), r ∈ V R receiving d

6:

nd max-residual path between e and t in G d

7:

update G with new capacities every edge server u by dividing the utility score α u ij by the bit-rate λ i . scadoosh coordinator rst sorts the set of usprus (line 1), then it processes each representation iteratively (lines 3-7).

Let e be the edge server that has to be served. Let d be the representation that has to be delivered, with bit-rate λ. We aim at delivering representation d to edge server e while minimizing the impact on the infrastructure. Our algorithm is inspired by the Maximum Residual Energy Routing Path algorithms, which are commonly used in wireless sensor networks with the goal to save energy [START_REF] Chang | Maximum lifetime routing in wireless sensor networks[END_REF]. Instead of delivering through the shortest path, which can quickly drain some equipments and make the network partitioned, the maximum residual capacity path is used. As a result, the bandwidth usage of all equipments are balanced and life time of the system is prolonged. Thus, we look for the delivery path such that the minimum remaining available upload capacity of all equipments in the path is maximum. We do it by multiplying the original non-directed links between two nodes to bi-direction links. We replace a link between two reectors (u, v) in G by two links (u, v, c(u)) and (v, u, c(v)) with each link weighted by the capacity of the head vertex. This bi-directional transformation is not needed for links between sources and reectors, and between reectors and edge servers, because streams are never sent in the reverse direction. As a result, in G (V , E ), the set of edges E is the union of:

E 1 = {(u, v, c(u)), (v, u, c(v))∀u, v ∈ V R , (u, v) ∈ E} E 2 = {(u, v, c(u)), ∀u ∈ V R , v ∈ V E , (u, v) ∈ E} E 3 = {(u, v, c(u)), ∀u ∈ V S , v ∈ V R , (u, v) ∈ E}
• The nal graph G d is obtained by augmenting the obtained graph G in order to ease the discovery of delivery path for the representation d. We add an abstract node denoted by t. The node t is linked to every node u which can serve the representation with an innite link. Consequently, E d also contains E 4 = {(t, u, ∞), ∀u has d}.

From graph G d , it is trivial to nd the path from the edge server e to the abstract node t with maximum residual weight. Especially, traditional shortest path algorithms such as the Dijkstra's one can be applied.

Evaluation

We now evaluate the performances of scadoosh. We developed our own simulator with the objective of simulating large-scale systems and a population of users having a behavior inspired from the real traces that obtained from justin.tv. We show that scadoosh is capable to maintain high user satisfaction with limited CDN infrastructure cost, and the type-specied user assignment strategy proposed in Section 5.5.1 can achieve higher user satisfaction.

We describe the settings of this simulator in Section5.6.1, and then we analyze the results in Section5.6.2.

Simulation settings

Population of users

We fetched real traces from a popular user-generated live video broadcasting platform, named justin.tv [jus], in August 2012.

2 Every ve minutes, we retrieved the popularity of channels of justin.tv. We took 150 of these measures to simulate the variation of popularity of channels in our system. The population variation traces of the 50 most popular channels are used to simulate end user behaviors. Figure 5.11 shows the global population of end users in our simulations.

User setting

We took inspiration from [nbc] to set the population heterogeneity, typically, half of them use mobile devices. This setting is identical to the user setting used in Section 5.4. We dened six types of user network connections: ADSL-slow, ADSLfast, FTTH, WIFI-slow, WIFI-fast and 3G.

CDN setting

We built a large CDN with ve geographic areas. In each area, equipments are interconnected through a random graph in which every link occurs independently with probability 0.8. Among the 50 channels, 30 channels are selected to be globally hot, which means that they are accessed by users from any area. The remaining 20 are locally hot channels, they are viewed only from users in one area. The capacity of CDN equipments is set to 1 Gbps. In order to serve all users at peak time (no user is rejected due to overloaded edge servers), the CDN contains 320 edge servers.

To value the underprovisioning of the CDN infrastructure, we changed the number of reectors. We set four underprovisioning congurations with respectively 15, 20, 25, and 30 reectors. The former one corresponds to a severely underprovisioned infrastructure scenario where only 47 Mbps in average have been reserved per edge server for the whole catalog of 50 channels, i.e. only 1.38 Mbps per channel that have to be served in every area (i.e. the globally hot channels and locally hot channels viewed in the area). Recall that, according to Apple HTTP Live Streaming setting [appb] (see Table 5.1), one channel is a pack of eight representations with an aggregated bit-rate over 11.6 Mbps. The most favorable scenario with 30 reectors is a slightly underprovisioned infrastructure scenario where the CDN reserved around 2.57 Mbps per channel and per edge server.

DASH setting

Each channel consists of 8 representations. Throughout this Chapter, the video bit rate of representations follows the recommendations from Apple HTTP Live Streaming setting [appb], see Table 5.1 for details.

Results

We now analyze the performances of scadoosh. Our main comparison is the ideal case where all users are served with their best representation. This comparison is captured by the metric based on relative satisfaction. In Section 5.6.2, we observe whether it is possible to maintain a good user satisfaction despite infrastructure underprovisioning. In Section 5.6.2, we focus on the impact of type-based user assignment on the overall performances.

Overall Performances

We use the same CDF function as in Figure 5.4 to show the performances of scadoosh. Let us now highlight the severely underprovisioned scenario with only 15 reectors. Again, scadoosh demonstrates its potential: 70% of users experience no degradation at all. Moreover, only 17% (respectively 9%) of users have a satisfaction below 0.88 (respectively 0.75). With respect to the severe underprovisioning of this infrastructure, these results are noteworthy since it shows that the population of users is reasonably well served although the CDN provisions less than half of the required infrastructure.

We now have a closer look at the edge servers where we distinguish into the three families of edge servers. See Figure 5.13. As can be expected, end users from the mobi family are almost not impacted by the underprovisioning. Indeed, the uspru of these clients is the highest. On the contrary, end-users from HD as well as norm are the ones that are the most aected by the underprovisioning. It is because a very under-provisioned CDN network cannot aord to deliver the high bandwidth consuming HD representations. In fact, in the most underprovisioned CDN network with 15 reectors, for HD edge servers, 51% of users can receive their required HD representations, and 29% percent of HD users receive the representation just below their required ones. This slight video quality degradation explains why globally users still perceive high satisfaction. Impact of Type-Specied User Assignment scadoosh includes three components: user assignment, content placement and tree delivery. We would like rst to evaluate the importance of the former algorithm, user assignment. Our proposal is to assign users to edge servers based not only on the channels they watch, but also on the type of device they use. As previously said, more accurate algorithms can be developed. Our goal here is to see whether such very simple implementation can already ensue in a gain of performances.

We refer to the type-specied user assignment mechanism proposed in Section 5.5.1 as SPC. We compare it to a strategy, which we refer to as GEN, that is more commonly used in CDN: it rst tries to assign a user to an edge server that hosts the same channel within the same area with trac load lower than the predened threshold; otherwise, the user is assigned to the edge server within the same area with the lowest trac load. We plot in Figure 5.14 the average satisfaction of users for both user assignment algorithms. As expected, with type specied user assignment, end users could obtain higher satisfaction with higher video quality. In order to show more details in user satisfaction levels, we show in Figure 5.15 the CDF of users on satisfaction. The gains of the type specied user assignment are more obvious. We can observe that SPC is able to deliver the best representation to a large subset of the population even when the system is very underprovisioned (with 15 reectors): 38% of the population instead of 30%. With regard to the low complexity of the SPC algorithm, such gain can justify its implementation.

Conclusion

This Chapter further develops the work presented in Chapter 4 toward the usercentric delivery of live rate adaptive videos in CDN. It provides both theoretical and practical contributions.

From a theoretical perspective, our main contribution is the formulation of an optimization problem using the user-centric discretized streaming model. In this problem, we maximize the satisfaction of users subject to the underprovisioning of CDN infrastructure. We formulate an Integer Linear Program (ILP), which jointly decides the choice of representations that should be sent to the edge servers, the building of a delivery overlay, and the assignment of end users to edge servers. We show that previous work related to streaming capacity do not satisfactorily address the problem met by CDN with rate-adaptive streaming, such as DASH.

Our second contribution is a practical system, named scadoosh. This system, which is inspired by our theoretical analysis, consists of three components. We evaluate the performances of scadoosh through a dynamic large-scale trace based simulation. We show that scadoosh can maintain a good QoE although the CDN infrastructure is severely underprovisioned in dynamic and large-scale CDNs.

The work presented in this chapter is still in progress. We have submitted this work to a journal, however, currently we have not obtained any valid publication.

For future work, we envision the following possible directions. On one hand, the optimization problem requires a more comprehensive theoretical analysis. On the other hand, in a more practical perspective, scadoosh is a rst step, which deserves further studies. We illustrated that the gains of each of the three algorithms are not always remarkable. Thus, one possible motivation is to nd better algorithms, with respect to the necessary trade-o between simplicity of implementation and practical benets. One of the most interesting challenge is to revisit forecasting algorithm so that the multi-representations feature of rate-adaptive streaming is actually taken into account. Another challenge is to determine some network topologies on top of which the QoE can be even better for a given underprovisioning. Finally, it would be extremely interesting to implement scadoosh on a real-world CDN infrastructure.

Chapter 6 Conclusion

The popularity of bandwidth-intensive online video services makes the Internet trac increase faster than the capacity of infrastructures. One of the consequences is that the network is strained to its limits, and can be frequently underprovisioned. For live streaming, which is delay-sensitive, the provisioning of the delivery network has a direct impact on the system performance. Although live streaming has been widely addressed in the literature over the past decade, underprovisioning has not received enough attention in the literature, despite the importance of this issue. It is either ignored, or solved by deploying some additional bandwidth helpers to prevent the system to become underprovisioned.

In this thesis, we study bandwidth ecient real-time video delivery solutions for two popular live video delivery technique: P2P and CDN. We design a multioverlay P2P video sharing system that enables casual Internet users to stream their own live videos. Moreover, we solve the bandwidth allocation problem which is to minimize the waste of user upload bandwidth. Especially, we propose several bandwidth allocation strategies for underprovisioned system. For CDN live streaming, we focus on rate adaptive streaming techniques. For this topic, we propose both theoretical streaming model and practical implementable system. In the following, we rst summarize the contributions of this thesis. Then, we will discuss the limitations of this work, and propose for possible future directions.

Synopsis

The main contributions in this thesis are summarized as follows:

• Optimum bandwidth allocation in multioverlay P2P system. We rst investigate the bandwidth allocation problem in a multioverlay P2P system. In our opinion, the problem of underprovisioned multioverlay P2P systems has not received enough attention. In order to mitigate resource decit, the goal is to maximally utilize end user's upload bandwidth. This goal corresponds to minimizing the resource waste when upload bandwidth resources are allocated to overprovisioned overlays although they could be allocated to underprovisioned ones. We show that such optimum bandwidth allocation corresponds to the maximum ow in a transformed bipartite ow network. Further, we design several bandwidth allocation strategies that balance the resource decit among the overlays for globally underprovisioned system. These strategies allow service providers to provision the overlays according to their business policies: prioritize some specic overlays, or fairly share the decit among all the overlays. Finally, the bandwidth allocation algorithms are validated through extensive simulations. We also show the system can cope with dynamics through a set of dynamic scenario simulations.

• Discretized streaming model for live rate adaptive streaming. • A practical CDN system for live rate adaptive streaming. The second practical contribution for live rate adaptive streaming in CDN is an implementation of a system, named scadoosh, which enables a CDN provider to eciently deliver live rate adaptive streams in a large-scale and dynamic environment. scadoosh redesigned the three CDN fundamental algorithms: content placement, content delivery and user redirection. At last, the performance of scadoosh is validated through a dynamic large-scale trace based simulation.

We show that scadoosh can maintain a good Quality of Experience although the CDN infrastructure is severely underprovisioned in dynamic and large-scale CDNs.

Besides the above main contributions, we also made minor contributions in some fellow scientists during the study of the thesis. In [LS13b], another fast near-optimum delivery trees construction algorithm is proposed for one specic application scenario of the generalized discretized streaming capacity problem. In this scenario, the CDN is fully connected and the CDN provider deploys a network with homogenous equipments with a uniform equipment capacity C. We also theoretically prove that the algorithm can obtain an approximation ratio of 1 -2λ * C -kl |V R | , where λ * denotes the maximum representation bit-rate, k (l, respectively) represents the number of representations (channels respectively), and |V R | is the number of reectors. Numerical experiments demonstrate that for large CDN instances, the algorithm obtains nearly optimum result (e.g. approximate ratio of 0.993 for CDN with 5,000 reectors) within very short time (30 seconds).

In [START_REF] Zhou | Joint optimization for the delivery of multiple video channels in telco-cdn[END_REF], we investigated the delivery of live video channels in the so-called Telco-CDNCDN deployed within the ISP domain. Telco-CDN can be regarded as an intra-domain overlay network with tight resources and critical deployment constraints. This paper addresses two problems in this context: (1) the construction of the overlays used to deliver the video channels from the entrypoints of the Telco-CDN to the appropriate edge servers; and (2) the allocation of the required resources to these overlays. Our ultimate goal is to maximize the number of delivered channels while preserving network resources. To achieve this goal, two approaches are proposed: (1) A joint optimization where both optimization problems are simultaneously addressed; and (2) a two-step optimization where the optimal overlays are rstly computed, then an optimal resource allocation based on these pre-computed overlays is performed.

We also devise heuristic algorithms for each of these approaches. The conducted evaluations of these two approaches and algorithms provide useful insights into the management of critical Telco-CDN infrastructures.

Limitations and Perspectives

In this thesis we contribute to research in improving bandwidth utilization of live video streaming for both P2P-based and CDN-based systems. But these works admit some limitations, which have to be addressed in future works.

• Decentralize the multioverlay P2P system. The algorithms that we implemented for the multioverlay P2P system rely on a centra actor (the management server) and centralized bandwidth allocation algorithms. The design of a decentralized multioverlay P2P system would be more appropriate with respect to the distributed nature of P2P systems. A key point in such a design is developing distributed bandwidth allocation algorithms. Currently, only one distributed algorithm has been designed for the fairness-based strategy. From the evaluation of the algorithms, the improved minimum-cost maximum-ow strategies have the highest performance in terms of user perceived video quality. Thus, a reasonable further step of the work includes designing distributed algorithms that optimizes these strategies.

• Optimum algorithms for the discretized streaming model. The discretized streaming model provides a theoretical foundation for multiple live rate adaptive videos delivery in today's CDNs. This topic should deserve further study. In this thesis, we proposed a fast near-optimum algorithm for one specic scenario. It would be also interesting to determine families of network infrastructures on top of which fast optimal delivery algorithms can be built. This future work can be integrated in the live rate adaptive streaming CDN system (scadoosh) as delivery forest construction algorithms.

• User QoE-based rate adaptive streaming. In the current work, we introduced a model to roughly estimate user QoE on perceived representations. This model is a generic one that could utilize any existing work on estimating QoE from various video bit rates. We envisioned two possible future work toward user QoE-based rate adaptive streaming. First, the lack of accuracy calls for more dedicated user QoE estimation models that take more parameters in input: for example, video resolution, video types, etc. Such models can provide more precise estimations on user QoEs to enable content providers and CDN providers to improve their delivery strategy. Second, the bit rates of representations are currently determined by the content provider in a somewhat arbitrary manner.

Since users can perceive dierent QoE on dierent bit rate of the videos, it would be interesting to determine the set of bit rates for representations based on user QoE values such that a certain optimization goal could be achieved.

• Improving the live rate adaptive streaming CDN system. The CDN system (scadoosh) that we proposed for live rate adaptive streaming is still at the earliest stages of development, and requires further improvement. For the following works, we envision improvement on each of the three components. The benets of the type specied user redirection mechanism has been proved. For the next step, more technical details for implementations with balances between practicality and protability are required. For the forecasting algorithm, the multi-representations feature of rate adaptive streaming should be taken into account. Then, ecient optimum trees construction algorithms should be also explored. At last, it would be very interesting to realize a true implementation of the scadoosh system. More generally speaking, the underprovisioning of delivery network remains an open research topic that has not received enough attention so far. Hence this topic deserves further in-depth study.

First of all, provisioning well the delivery network in advance remains the major cost for service providers. Moreover the provisioning of the network is also inuenced by dynamic user requirements: for the same delivery network, it could be overprovisioned under light service requirement, as well as underprovisioned under intensive service requirement. As a result, service providers could benet from elastic resource provisioning which adaptively determine the size of the delivery network on the y in response to temporal and spatial dynamics of service demands. In such work, changing the size of the network introduces extra costs, such as data migration, delay, etc.

  Par contre, un Content Delivery Network (CDN) a été élaboré pour s'adapter à une utilisation grande échelle des applications [mKPB06, KSW + 04, AMM + 11, NSS10]. Un Réseau CDN est basé sur le déploiement de plusieurs serveurs, qui collaborent pour répliquer le contenu (vidéo) et fournir un accès rapide et able au service. Les utilisateurs sont redirigés de manière transparente vers le serveur approprié. En fait, P2P et CDN sont deux solutions complémentaires. Les CDNs peuvent fournir des services garantis, mais ils doivent provisionner leur réseau avec susamment de capacité, ce qui engendre un coût non négligeable. Alors que les solutions P2P peuvent orir les services avec une garantie de service qui est seulement probable, mais à moindre coût. Par conséquent, les deux techniques, P2P et CDN, ont des dés et des exigences particulières. Un fournisseur de service de streaming vidéo en direct doit envisager attentivement la bonne approche lors de la phase de conception d'un système. Au cours des dernières années, la consommation de ux vidéo en ligne a augmenté signicativement. La nouvelle génération de technologies d'accès, par exemple 3G et 4G, permet d'accéder aux services de vidéo en ligne depuis n'importe quel endroit et à n'importe quel moment. Une bande passante plus large mène à une plus grande popularité des vidéos en Haute Dénition (HD). Les dispositifs avec caméras équipés permettent à chacun de générer du contenu en direct pour partager, et par conséquent, de nouveaux types de services de vidéo en direct émergent. Toutes ces tendances imposent de nouveaux dés aux services de ux vidéo en direct. Dans la suite, nous allons d'abord exposer nos observations sur l'état actuel et l'évolution de streaming vidéo en direct: La domination du trac vidéo. Les vidéo occupent déjà la majeure partie du trac Internet mondial, sur les réseaux xes et aussi sur les réseaux mobiles [san, cisa, cisb]. En 2012, l'analyse réalisée dans [san] sur le trac Internet en Amérique du Nord a montré que 65% du trac réseau xe et 57% du trac réseau mobile en sens descendant sont la vidéo. Les mêmes chires pour l'Europe étaient de 38% et 39% pour le réseau xe et le réseau mobile, respectivement. Jusqu'à présent, la croissance de la partie vidéo de l'ensemble du trac Internet correspond la prediction du rapport Cisco 2010 [cisb] qui prévoit que la vidéo représentera 90% du trac global en 2015. Actuellement, le service de vidéo en ligne, y compris des ux vidéos en direct, est devenu la principal industrie du loisir en ligne. Par exemple, le Jeux Olympiques de Londres représente entre 8-12% du trac réseau aux États-Unis au sommet [san].

  Le travail dans cette partie est un élément prépondérant du projet CNG (de l'anglais Community Network Game), un projet nancé par la Commission Européenne FP7 STREP. L'ambition du projet CNG est de permettre aux utilisateurs MMOG de délivrer leur propre contenu (vidéo par exemple) aux autres joueurs en utilisant le technologie P2P. xix L'étude réalisée dans ce travail est un système P2P multi-overlay de diusion de vidéos en direct. Nous nous concentrons sur le problème de l'allocation de bande passante, c'est à dire les utilisateurs qui regardent plusieurs vidéos doivent décider comment partager leur bande passante de liaison montante parmi les overlays. Typiquement, nous faisons attention à l'approvisionnement des overlays. Un overlay est sur-provisionné, si la bande passante qui lui est réservé est supérieure à sa demande de diusion, autrement, il est sous-provisionné. Donc, la bande passante est dite gaspillée si elle a été attribuée aux overlays sur-provisionnés, alors qu'elle aurait pu être attribuée à ceux sous-provisionnés. Notre première contribution est la formulation du problème d'allocation de bande passante optimale avec l'objectif de minimiser le gaspillage de bande passante. Nous le résoudrons par le problème de ot maximale dans un graphe biparti. Nous montrons donc qu'une solution optimale peut être trouvée en temps polynomial du nombre d'utilisateurs dans le système. Notre deuxième contribution est la conception de plusieurs stratégies d'allocation de bande passante, dont l'objectif est de partager le décit entre les overlays pour un système sous-provisionné. Nous avons proposé plusieurs politiques (par exemple, en donnant la priorité à la diversité des vidéos, aux vidéos les plus populaires, aux vidéos préférées et aux utilisateurs primes), et plus nous avons montré qu'il est possible de trouver la solution optimale depuis un problème de ot maximale avec coût minimum dans le même graphe biparti. Comme ca, les solutions peuvent être trouvées avec des algorithmes en temps quasi-polynomial. En plus, nous avons aussi proposé une stratégie équitable (fairness ) qui alloue la bande passante basée sur les demandes des overlays. Un algorithme distribué est conçu pour cette stratégie. Enn, nous avons également proposé des mécanismes concernant la praticabilité du système. Les performances de notre proposition ont été validées par une simulation dynamique à grande échelle basée sur des trace réelle. Nos contributions cherchent à résoure des problèmes ouverts que les travaux précédents [WLL08, WXR09, WXR11] n'ont pas réglés. Tout d'abord, les travaux précédents sont aveugle au provisionnement de l'overlay. Ensuite, ils obtiennent les résultats biaisés telles que certains overlays peuvent sourir de décit de ressource, même si le système est bien provisionné [WXR09, WXR11]. Deuxièmement, nous avons déni des politiques pour un système sous-provisionné. Dans des travaux précédents, le sous-provisionnement du système est ignoré [WXR09, WXR11] ou totalement inacceptable [WLL08]. Enn, nous avons comparé notre étude à celle la plus proche [WXR09, WXR11], l'évaluation montrant les avantages de notre approche. Modèle de streaming discrétisé pour diuser les vidéos adaptatifs en direct sur CDN Le deuxième contribution de cette thèse est la formulation d'un nouveau modèle, le modèle de streaming discrétisé, pour distribuer les vidéos adaptatifs dans le réseau CDN. Cette contribution comble une lacune importante dans la littérature scientique liée à CDN et streaming du vidéo en direct. En eet, le streaming du vidéo en direct a reçu trop peu d'attention dans la littérature. Une étude bibliographique [Pas12] a référencé 438 documents liés à la diusion de contenu depuis P2P, les réseaux assistés par des pairs et CDN; mais, seulement deux xx Résumé citations pour le streaming du vidéo en direct dans les CDNs [AMMS03, AEVW04]. Les travaux plus récents [AMM + 11, NSS10, ASV11] consacrés au streamin vidéo en direct dans les CDNs sont sur un sujet qui, selon nous, est moins important aujourd'hui. Leur objectif est de réduire le coût de la transmission sur les liens dit de peering entre les utilisateurs et les n÷uds CDN. Cependant, les CDNs modernes fonctionnent avec des serveurs qui se trouvent au sein du réseau des fournisseur d'accès à Internet (FAI, le terme en anglais est Internet Service Provider (ISP)), et sur des accords de peering avec ces FAIs [net]. En fait, le coût pour faire transiter du trac entre les réseaux diérents a diminué signicativement [Kro11], à un point où il n'est plus la considération principale. Au contraire, nous croyons que la préoccupation majeure pour les fournisseurs de CDN est la disponibilité de la bande passante par suite de l'augmentation rapide du trac. En outre, aucun des travaux précédents cible en streaming adaptatif, tandis que le streaming adaptatif est une grave menace pour la capacité limitée dans les réseaux d'infrastructure de CDN. Dans le même temps, une série de travaux ont étudié la capacité de streaming de réseaux [SLC + 11, ZLW11, NL11, KS11]. L'objectif est de déterminer le débit maxi- mum qui peut être livré à tous les n÷uds d'un réseau. Ces travaux sont basés sur la vidéo avec débit élastique et l'hypothèse que les ux de données sont divisibles inniment. Par contre, dans le contexte de streaming adaptatif, les débits des diérentes représentations du vidéo sont bien prédénis. Et plus, chaque ux doit être soit livré entièrement, soit ne pas être livré du tout. Le débit du réseau doit maximiser le nombre de ux délivrés, pas le débit livrable. Ainsi, nous avons conçu un nouveau modèle, qui maximise le nombre de ux délivrés d'un réseau. Pour ce travail, nous avons les contributions suivantes. D'abord, nous donnons une formulation du problème général par l'optimisation linéaire (OL) en nombres entiers (terme en anglais Integer Linear Programming (ILP)) et nous prouvons que le problème est NP-complet. Le problème général est formulé comme la maximisation de l'utilité des ux livrés par un ensemble d'arbres. La complexité NP-complétude implique qu'il est actuellement impossible de trouver une solution rapide et optimale pour le cas général. Ainsi, nous nous concentrons sur un scénario pratique, qui correspond à la mise en ouvre de CDN d'aujourd'hui en ux vidéo. Nous présentons un algorithme, qui est rapide, facile à mettre en ouvre, et quasi-optimale. Nous montrons théoriquement le facteur d'approximatio de l'algorithme, qui est négligeable pour la conguration considérée. Enn, nous évaluons le facteur d'approximatio de l'algorithme par une simulation numérique. Un système concentré sur les utilisateurs en streaming adaptatif en direct La troisième partie de ma thèse explore davantage le modèle de streaming discrétisé. Dans ce travail, nous spécialisons le modèle discrétisé général à un modèle centré sur les utilisateurs. Comme l'objectif d'un CDN est de satisfaire les utilisateurs, nous proposons un modèle qui maximise la satisfaction (mesurée en la Qualité d'Expérience (QoE)) des utilisateurs sur les ux livrés. Ainsi, ce modèle est nommé modèle de streaming discrétisé concentré sur les utilisateurs. La première contribution est un fondement théorique pour ce travail. D'abord, nous dénissons un modèle qui per-xxi met au fournisseur de CDN d'estimer objectivement la satisfaction de utilisateur sur chaque représentation dans le contexte de streaming adaptatif. Ce modèle permet la dénition de l'utilité de ux à base de QoE de utilisateur pour le modèle streaming discrétisé. Nous présentons plusieurs objectives possibles et nous nous concentrons sur l'objectif de garantir la max-min fairness de la satisfaction des utilisateurs, et en même temps de maximiser la satisfaction totale des utilisateurs. Nous formulons un modèle OL, qui conjointement décide: (1) la représentation qui doit être envoyée aux serveurs edge; (2) un ensemble d'arbres enracinés au serveur d'origine, et avec des serveurs edge qui sont des feuilles; et (3) l'association des utilisateurs et serveurs edge. Ces trois points correspondent aux trois mécanismes principaux de CDN pour la diusion du vidéo en direct: (1) le placement de contenu, (2) la diusion de contenu, et (3) l'association des utilisateurs. L'évaluation du modèle OL sur un ensemble de mini-infrastructures CDN démontre les avantages de notre modèle, notamment en comparaison des approches précédents [SLC + 11, ZLW11, NL11, KS11]. Ensuite, la deuxième contribution justie le modèle discrétisé concentré sur les utilisateurs dans un système pratique. En revisitant les trois mécanismes principaux de CDN, le système est capable d'utiliser ecacement l'infrastructure CDN pour diuser les vidéos adaptatifs en direct aux utilisateurs à grande échelle dans un environnement dynamique. Le système contient trois composantes. Chaque composante traite de l'un des trois mécanismes CDN principaux susmentionnés: • Un composant d'association d'utilisateur assemble les utilisateurs avec des exigences similaires.

  Online video streaming services can be roughly classied into two types: Video on Demand (VOD) services and live video services. As the name suggests, VOD services allow users to re-access the same video content multiple times at any moment while live video services broadcast real-time video streams provided by the content providers to an audience over the Internet. The real-time demand makes live video streaming far more challenging than VOD services. Since the rst online live show performed by the Severe Tire Damage band on June 24 1993, live video streaming has become one of the biggest and most popular realms in the Internet world. Multiple successful applications/platforms provide live video service to millions of people every second. For example, PPLive [ppl] served over 1,000,000 simultaneous users for Beijing Olympics games. On justin.tv, a webbased live video platform, one new live video starts every second, and users watch more than 300 million videos every month [jus]. These are two examples among many others.

  Video trac is already the major portion of global Internet trac, on both xed and mobile networks [san, cisa, cisb]. In 2012, measurement of Internet trac in north America showed that during peaks, 65% of the xed network and 57% of the mobile network downstream trac are video [san].

Figure 2 . 1 :

 21 Figure 2.1: Tree-based P2P overlay

Figure 2 .

 2 Figure 2.1 the underlying communication network is shown: end hosts are connected to each other through two routers. Then, based on the topology of the network, the system builds an application layer overlay (as shown in the top part of Figure 2.1) such that (1) each peer has limited number of neighbors and (2) a link between two peers has a good enough performances, e.g. in latency and bandwidth. On top of this overlay, a spanning tree construction algorithm can be used to build data delivery tree (the red arrows in Figure 2.1).

Figure 2 . 2 :

 22 Figure 2.2: Multitree-based P2P overlay

Figure 2 . 3 :

 23 Figure 2.3: Formulation of a mesh-based P2P overlay

  Our main idea is to rst solve the inter-overlay bandwidth allocation problem, then, upon the allocated bandwidth into each overlay, to use a state-of-the-art P2P video streaming protocol stands for constructing P2P overlays and streaming the videos. This idea is similar to the work presented in[START_REF] Wang | A exible divide-andconquer protocol for multi-view peer-to-peer live streaming[END_REF][START_REF] Wang | Improving multiview peer-to-peer live streaming systems with the divide-and-conquer strategy[END_REF], which represent the second class of approaches in the literature. This design requires the P2P video streaming protocol to well adapt to system dynamics, such as peer churn and peer bandwidth variations. Based on the discussions in previous sections, two possible solutions are available: the tree-based P2P streaming protocols and the mesh-based ones. As previously said, mesh-based P2P streaming protocols are a better t for the intra-overlay video streaming. Such a design perfectly combine the two problems, inter-overlay bandwidth allocation and intra-overlay video streaming, and reduce the complexity of the whole system.

Figure 2 . 4 :Figure 2

 242 Figure 2.4: CDN delivery network

Figure 2 .

 2 Figure 2.6: Media Presentation Data le

  Figure 2.7: A live MPD le example

Figure 2

 2 Figure 2.8: Distributing live rate adaptive streams in CDN

Figure 2 .

 2 Figure 2.7 depicts an example MPD le for live DASH video taken from [Sto11] and [LEF + 11]. The type eld is assigned to live to indicate that the video is a live one.

A

  surprisingly low amount of work are related to live video streaming in CDN networks. The earliest works [AMMS03, AEVW04] only deal with one stream. Multiple streams delivery is more complex because the forwarding nodes should determine how to allocate their upload bandwidth into the multiple streaming sessions for a global optimization objective. Some more recent works [AMM + 11, NSS10, ASV11] consider the node upload bandwidth limitation and multiple streams. Their objective is to reduce the bandwidth cost subject to the resource constraints. This objective is outdated since CDNs and ISPs develop peering agreements, which reduce the importance of the bandwidth cost. On the other hand, the major concern for current CDN providers is the huge volume of video trac to deliver, and the transmission burden on its limited CDN infrastructure. Thus, an appropriate objective for current CDN providers is to maximize the throughput of the CDN delivery network. The relation between edge servers and end users in the context of DASH is also widely studied in the literature [LBHG12, CMP11]. These studies could complement our work, which only deals with content delivery within the CDN infrastructure. The problem of maximizing the throughput of a network, subject to the upload capacities of the nodes has been addressed as the streaming capacity problem in the context of P2P networks [SLC + 11, ZLW11, NL11]. Their goal is to maximize the deliverable bit rate of the network. In other words, their model is based on elastic video bit rate. However, in the context of rate adaptive streaming, the bit rate of the representations are well predened (such as in Table

Figure 3 . 2 :

 32 Figure 3.2: Example of a sub-optimal bandwidth allocation.

2 . 4 .

 24 To sum up, our work improve the existing research in the following aspects: (i) none of the current work have proposed policies for the management of underprovisioned systems; (ii) their simulations considered only a small number of overlays (four overlays in most cases) with a very simple multioverlay structure. For example, in[START_REF] Wu | Dynamic bandwidth auctions in multioverlay p2p streaming with network coding[END_REF][START_REF] Wu | On Dynamic Server Provisioning in Multichannel P2P Live Streaming[END_REF], each peer participates to all overlays, and in[START_REF] Wang | A exible divide-andconquer protocol for multi-view peer-to-peer live streaming[END_REF] three simple overlay structures (chain, star and mesh) are studied. In our work, we simulated a large number of overlays (about 200), and the multioverlay structure is formed with a realistic simulation model. The remainder of this Chapter is organized as follows. Section 3.2 denes the system model. Section 3.3 presents our bipartite ow network model and shows that the resource allocation with minimum total underprovisioning is equal to the maximum ow in the model. Section 3.4 proposes several bandwidth allocation strategies dened by properly dened cost functions in the ow network. Section 3.5 introduces the fair bandwidth allocation strategy and solves it using the dual decomposition method.

3 .

 3 Multioverlay P2P Video Sharing: Resource Allocation in Under-Provisioned System 3.4.6 Practical Optimization

  D s = D s -B s . The utility function U (b s p ) = D s • log(b s p ) expresses the following connotations: (i) the objective function in (3.1) is dened as a strictly concave function to make the problem computationally solvable through convex optimization.

  A solution that satises (3.2) and (3.3) can always be found. Thus, Slater's strong duality constraint qualication holds, and the original constrained convex optimization problem can be solved via the dual problem (3.4) [BV04]. The master dual problem (3.5) is min φ(λ, µ) = s,p∈Ps φ s,p (λ p , µ s ) + λ T B + µ T D (3.5) for the dual variables λ 0 and µ 0 where B and D denote the vectors of B p and D s and φ s,p (λ p , µ s ) = sup b (U (b s p ) -λ p b s p -µ s b s p ) ∀s, p ∈ P s is the dual function obtained as the optimal value of the Lagrangian solved in (3.6). max U (b s p ) -λ p b s p -µ s b s p ∀s, p ∈ P s (3.6)

Figure 3 . 4 :

 34 Figure 3.4: The two level simulator platform

Figure 3 .

 3 Figure 3.5: Simulation Setting

  Figure 3.5(b) shows the number of videos and corresponding popularity generated by τ = 0.1 and b = 0.85. Due to the limitation of human attention, we set the maximum number of videos a peer can simultaneously watch to ve. Figure 3.5(c) shows the corresponding number of watched videos distribution.

Figure 3 . 6 :Figure 3 . 7 :

 3637 Figure 3.6: Total amount of missing upload capacity.

Figure 3 . 8 :

 38 Figure 3.8: Total chunk losses.

Figure 3 . 9 :

 39 Figure 3.9: Average chunk losses in overlays. Overlays are ordered by popularity. The video bit rate is 330 kbps.

Figure 3 .

 3 Figure 3.10: PSNR results.

Figure 3 .Figure 3 . 12 :

 3312 Figure 3.11: Number of peers in the system.

  Fully-dynamic ∆t = 2, λ = 0.05

Figure 3 .

 3 Figure 3.13: PSNR results.

Figure 3 .

 3 Figure 3.13 shows the PSNR results. The results are similar to the static ones. They demonstrate that recomputing the bandwidth allocation on a periodic basis works well. The results in Figure3.13(a) are worse than those in the other gures because the total under-provisioning is greater in the join-only scenario. In all scenarios, the

Figure 3 .

 3 13(d) shows the PSNR results for ∆t = 5 min. Compared to the results obtained with ∆t = 2 min (Figure3.13(c)), the percentage of peers with a PSNR higher than 35 dB decreases only slightly (2.5% for IDb and IPb, 0.5% for Fb and 0.1% for DAC). This indicates that re-computing the allocation after a few minutes does not aect the quality of the allocations signicantly.

Figure 3 .

 3 Figure 3.14: CNG user communication tool

  As a result, the sharp growth in the volume of video trac, and the widely deployed bandwidth consuming rate adaptive streaming technique impose a novel challenge for today's CDN providers: to cope with the underprovisioned CDN infrastructures. As a result, the goal of the CDN providers for live streaming is maximizing the throughput of the CDN delivery network, under the constraint of outbound capacity of CDN equipments [ASV11, AMM + 11, ZAB + 12].

Figure 4 . 1 :

 41 Figure 4.1: The CDN graph associated with 3-SAT

Figure 4 .

 4 Figure 4.2 shows an example of tree generation. The node-set V j is composed of two nodes: u and v with f j u = 3, and f j v = 2 (Figure 4.2(1)). As u has a higher

4 . 2 .Figure 4 . 3 :

 4243 Figure 4.3: Evaluation for small instances

Figure 4 . 4 :

 44 Figure 4.4: Evaluation for large instances

  In the previous Chapter 4, we have introduced a general optimization problem the discretized streaming capacity problem that maximizes the utility of delivered live rate adaptive streams in a underprovisioned CDN infrastructure, under the topology and capacity constraints of the CDN. We formally formulate the problem through ILP and prove that the complexity of the problem is NP-Complete. These work provide a theoretical foundation for live rate adaptive streaming in CDN. In this Chapter, we take a further step towards live DASH video delivery in CDNs by introducing a user-centric live DASH streaming CDN system.

Contribution 2 .

 2 The second contribution is a practical implementation which enables a CDN provider to eciently deliver live rate adaptive streams in a large-scale and dynamic environment. The system contains three components: (1) a user assignment component; (2) a content placement component; and (3) a content delivery component. Each component targets one of the three aforementioned CDN main mechanisms. At last, we conducted a large simulation campaign to evaluate the system performance. We utilized real traces collected from justin.tv [jus] website to set up the behavior of clients. The simulation results approve our expectation: the system could serve a large audience with high satisfaction and limited CDN infrastructure cost.

  Researchers have thus worked on QoE models that map objective non-perceptual video quality metrics into MOS values [RCKS10, TKS10, KSJI10]. The idea is that the combination of several paramaters (such as video bit-rate, packet loss, and video genre) can lead to a good estimation of the MOS. In particular, models based solely on video bit-rates represent a nice trade-o between the accuracy of QoE estimation and the simplicity of implementations [MHXW12, YH08, ZWCK13]. In the following, we consider that the CDN provider uses such bit-rate based QoE model to estimate onthe-y the MOS of a given video representation (Fig. 5.1(a)). One of the advantages of these models is that they do not require any computation on the user devices. Of course, more sophisticated QoE models, based on a wider set of parameters, can be implemented to improve MOS estimation accuracy.

1 :

 1 Figure 5.1: MOS models

  Fig. 5.1(b). Please observe in Fig. 5.2 that the third representation has a good relative satisfaction although the same representation has a disastrous MOS in Fig. 5.1(b).

Figure 5 . 4 :Figure 5 . 5 :

 5455 Figure 5.4: CDF of user satisfaction

3 Figure 5

 35 Figure 5.6: The scadoosh system

2 Figure 5

 25 Figure 5.8: ARIMA model identication

  Figure 5.9: Evaluation of the prediction

Figure 5

 5 Figure 5.10: Graph transformation

  Figure 5.11: Variation of global population over the 150 periods

Figure 5 . 12 :

 512 Figure 5.12: CDF of user satisfaction for three numbers of reectors

  Figure 5.13: Average satisfaction of users regarding to each edge server family

Figure 5 Figure 5

 55 Figure 5.14: Average satisfaction of users: GEN vs. SPC

  As far as we know, the discretized streaming model is the rst work related to live rate adaptive streams delivery in the CDN infrastructure. This part is the basic theoretical contribution for this problem. We rst dene a general optimization problem which captures the current main concerns of CDN providers: maximizing the throughput of the CDN delivery network by maximizing the utility of delivered streams. Especially, this model allows to prioritize the transmission of streams (measured by the utility) in underprovisioned CDN infrastructure. We formulate this problem through Integer Linear Programming, and prove that the complexity of the problem is NP-Complete. This general problem is further developed into a user-centric one by dening user QoE related utility. The user-centric discretized streaming model maximizes the overall satisfaction of a population, and at the same time guarantees max-min fairness on user satisfaction. The evaluation of the model in a set of toy-CDN infrastructures shows the benets of the user-centric discretized streaming on achieving higher user satisfaction comparing to the previous approaches. • A fast near-optimum algorithm for live rate adaptive transmission in CDN. As the aforementioned NP-Completeness indicates, it is impossible to quickly nd an optimal solution for the general discretized streaming capacity problem. The rst practical contribution for live rate adaptive streaming in CDN is a fast near-optimum algorithm for a specic scenario, which corresponds to today's CDN implementation of live streams. Specically, the CDN provider is in charge of delivering groups of representations as bundles. We provide formal theoretical approximation bound, which is at least 1 -(b s * /|V E |) times the optimal solution (where b s * is the capacity of the source, and |V E | denotes the number of edge servers in the network). This is the rst practical result for the discretized streaming model.

Table 2 .

 2 1: Comparison of tree-based and mesh-based P2P streaming protocols Multiple mesh-based P2P live video streaming systems have been implemented.

	Notation	Tree-based Mesh-based
	Complexity	high	low
	Source-to-end delay	low	high
	Overhead	low	high
	Peer churn	vulnerable	immune
	Bandwidth variation vulnerable	immune
	Maintenance cost	high	low
	The most popular systems are probably CoolStreaming and PPLive [Pas12, HLL + 07].

The Coolstreaming system, which was released in summer 2004, represents the rst successful large-scale P2P live streaming system [LXQ + 08]. CoolStreaming, which is based on a mesh network, has been further extended in

[START_REF] Xie | Coolstreaming: Design, theory, and practice[END_REF]

. PPLive is one of the most popular large scale P2P live video streaming applications. Measurements [HLL + 07] have revealed that PPLive follows the major design principle of mesh-based P2P live video streaming system: a gossip-based protocol for peer management and channel discovery; a mesh-pull P2P architecture for high quality video streaming.

  Figure 3.1: Three sources in a multioverlay live video system.

	3. Multioverlay P2P Video Sharing: Resource Allocation in Under-Provisioned
										System
			Management Server
				s 1		s 2		s 3
		p 2
	p 4	p 1			p 1	p 2		p 3 p 2	p 4
	overlay demand: 18		overlay demand: 12	overlay demand: 18
	overlay capacity: 18		overlay capacity: 10	overlay capacity: 20
	overlay provisioning: 0		overlay provisioning: -2	overlay provisioning: 2
	s 1 capacity: 6			s 2 capacity: 6	s 3 capacity: 6
	p 1 6	3	2	p 2	1	2	p 3	8	4	p 4 4
	capacity: 9		capacity: 5		capacity: 8	capacity: 8

  It is equal to |P s | • d s , where d s denotes the bit rate of the video emitted by s. The other part is the bandwidth used by the streaming protocol. This is equal to |P s |•o s , where o s represents the average overhead in the overlay G s . As a result, the capacity of an overlay is calculated as:

Table 3 .

 3 1: Notations used in Chapter 3

	P, S	set of peers, set of sources
	G s , P s overlay of source s and set of peers in G s
	B p	upload capacity of a peer p
	b s p	upload capacity reserved by p for G s
	G(p)	set of sources to which peer p subscribed
	d s	video bit rate of the video emitted by s
	o s	the average overhead of P2P streaming protocol in overlay G s
	D s , C s demand and capacity of G s
	∆ s , ∆ r s	provisioning and relative provisioning of G s

  3. Multioverlay P2P Video Sharing: Resource Allocation in Under-Provisioned System Algorithm 1: Source s at round t > 0 1: Wait for bs p (t -1) from p ∈ P s 2: Update µ s (t) with µ s (t -1) and bs Algorithm 2: Peer p at round t > 0 1: Update λ p (t) with λ p (t -1) and bs p (t -1) according to (3.8) 2: Wait for µ s (t) from s ∈ G(p) Solve problem (3.6) with λ p (t) and µ s (t) and obtain bs

	3: for p ∈ P s do	p (t -1) according to (3.9)
	4:
	3: for s ∈ G(p) do
	4:

Send µ s (t) to p p (t)

5:

Send bs p (t) to s as:

Table 4 .

 4 The upload capacity of the nodes α e ij , e ∈ V E The utility score of edge server e to representation d ij

1: Notations used in Chapter 4

  For simplicity, in the ILP formulation, we omit the use of set membership indication ∈ for the main notations. Whenever we write ∀i, ∀j, ∀s, ∀r, ∀e, and ∀v, we imply ∀i ∈ [k], ∀j ∈ [j], ∀s ∈ V S , ∀r ∈ V R , ∀e ∈ V E , and ∀v ∈ V , respectively. Moreover, we use i, j, s, r, e, and v to refer to representations, channels, sources, reectors, edge servers, and general nodes, respectively.

	v ijs (U ) =	y uv ijs
	u∈U
	Similarly, let O v ijs (U ) be the sum of y variables that correspond to outgoing edges
	from v to nodes in U , i.e.
	O v ijs (U ) =	y vu ijs
	u∈U

2

  Mbps, which is insucient. The aggregated upload capacities of reectors represent only16% of what would be required to send all representations to all edge servers. Finally, the capacity of edge servers is 80 Mbps. There is no constraint on the assignment from end users to edge servers.

	source
	reectors
	edge-servers
	population of end-users
	Figure 5.3: Topology of CDN toy-network
	able bit rate of a network (discussed in Chapter 2.3.4) Thus, we computed the best
	achievable streaming bit rate of the toy-network based on the algorithms described
	in [SLC + 11]. Then, we found the best packing of representations for such bit rate.
	We rst analyzed the solution that can be directly obtained from the streaming
	capacity problem. The streaming capacity problem obtains the maximum deliver-

Table 5

 5

	.2 shows the average downlink

Online Live Video Streaming

Multioverlay P2P Video Sharing: Resource Allocation in Under-Provisioned System

Discretized Streaming Model for Live Rate Adaptive Streaming capacity of equipment is the only constraint.

Discretized Streaming Model for Live Rate Adaptive Streaming

We are now ready to prove the main theorem of this section. We make a reasonable assumption that it is possible to deliver at least one channel to all the edge servers, i.e. S * ≥ |V E |.

We assume that the plain M OS(dij) is larger than 1 for all representations, because logarithmic QoE models are used [YH08].

A User-centric Live Rate Adaptive Streaming CDN System

Available at http://enstb.org/∼gsimon/Resources/Justintv

Publications

International Conference

Annie Gravey for her constant support, and Jean-Marie Bonnin for taking me in the RSM Department in Rennes.

My grateful thanks are also extended to

Lemma 2 At the end of the execution of Bundle-Delivery, it holds that if ∃u ∈ V R : b j * u > 1 then S = S * . Proof . Suppose that after the construction of T j * there exists a node u ∈ V R such that b j * u > 1. Clearly, b j u > 1 for every j ∈ [j * ] as the residual forwarding capacity b (•) u can only decrease in subsequent executions from line 3 to line 12 in the algorithm.

There are two possible cases during the construction of T j :

• Case 1: Node u was chosen in step line 7 of Algorithm 3. Then since b j * u > 1 we can conclude that f j u = |V E | + |V j | -v∈V j \{u} and u is the last node to be added to V j .

• Case 2: Node u was not chosen in step line 7 of Algorithm 3. Then, the inner loop of the tree construction phase (line 6 of Algorithm 3) ended due to equality

Thus, for every j ∈ [j * ] the equality

We note u n ij the satisfaction of user n ∈ N when n receives representation d ij . To compute u n ij , we use the ratio of the MOS of representation d ij to the MOS of its requested representation d i n j n . Since we would like the user satisfaction to be into the range [0, 1], we use the following computation: 1

Live video streaming in a CDN

We consider the same 3-tier CDN topology and live rate adaptive streaming mechanism as in Chapter 4. Hence, we reuse the model presented in Section 4.2.1. For uent reading, we shortly recall the notations used in the model.

A CDN G = (V, E) is composed of sources (V S ), reectors (V R ), and edge servers (V E ). The sources receive and transcode the raw video channels into a set of live representations; the reectors deliver the representations to the CDN edges, and the edge servers oer the received representations to the end-users. Consequently, there are three types of connections:

The delivery of a representation

, is carried out through a set, T ij , of trees of G. Each tree in T ij , has one of the source nodes as its root and edge-servers as its leafs. We denote by T s ij the delivery tree of d ij rooted at s ∈ V S .

Lastly, every forwarding node v is limited by the total outbound bit-rate (capacity) it can support, c(v), v ∈ V S ∪ V R . As we have discussed, the outbound capacity of the equipment is the only constraint.

Formulation of the Capacity Problem

We start the presentation of the optimization problem by introducing several objective functions in Section 5.3.1. We then present the ILP formulation in Section 5.3.2.

Objective Functions

As we consider the CDN is underprovisioned, the network cannot support to transmit all the requested streams to all the requiring edge servers. Under the upload capacity constraints at the forwarding nodes, the CDN supports the delivery of a subset of representations, based on the utility of the streams. To formalize the user-centric discretized streaming capacity problem, we dene two binary variables:

• x e ij = 1 indicates that edge-server e ∈ V E receives representation d ij , 0 otherwise (this notation has been dened in Chapter 4.2.1).

• z ne ij = 1 indicates that user n ∈ N is attached to edge-server e ∈ V E , and gets representation d ij from e, 0 otherwise. We suppose that the highest achievable representation for each user n is given.

It is determined by user device type and access link. From Section 5.2.1, the user satisfaction u n ij is thus known for all users and all representations.

The problem can be formulated by using only the variable x e ij upon giving user requirements on each edge-server. However, CDN implements three main algorithms: user-to-server assignment, content placement and content delivery. As one of the main functionalities of CDN, user assignment determines edge-server requirements, and has an direct impact on stream delivery. In this case, we would like to formulate the problem in a way which combines all the three aforementioned CDN functionalities. Thus, we use the variable z ne ij to include users' behaviors.

Then, the utility of representation d ij for edge-server e is the aggregated satisfaction of end users that are attached to e on representation d ij . Formally, the utility of an edge server e in V E can be written as:

It is possible to design many dierent objective functions. We propose one usercentric objective function in the following. An intuitive objective function consists in maximizing the average satisfaction of users, which is expressed as follows:

Obj global :

Such an objective function is simple, but it has some weaknesses. In particular, it can introduce biases, when Obj global can be maximized by focusing on a subset 3. Previous predictions are confronted to real requests. If the performances are below a threshold, the ARIMA parameters should be retrained.

More formally, let T be the current period, so the coordinator should predict the requests for period T + 1. If reports have been sent from edge servers to coordinator, the latter stores the times series n e ij (t), ∀i ∈ [K], j ∈ [L], e ∈ V E for all t ≤ T . For simplicity, we assume that all these time series are independent, thus we treat them separately. This is not true in DASH. We left for future work the design of more accurate prediction tools, which take into account the correlations between various representations.

Then, we need to identify the ARIMA(p, d, q) model (identify p, d, q parameters).

Nowadays, a huge number of live videos are generated and broadcasted by ordinary

Internet users (such as videos on justin.tv platform). We collected video popularity information from the justin.tv [jus] platform (a user-generated live video platform), and use these traces to validate our system (in Section 5. For these two types of videos, the autocorrelation ρ k and partial autocorrelation φ kk of the rst-order dierence series have dierent styles. However, for the secondorder dierence (∇ 2 ) popularity, both patterns have non-zero ρ1 and φkk tails o, indicating the ARIMA model is ARIMA(0, 2, 1). This model is identical to the one obtained in [START_REF] Wu | On Dynamic Server Provisioning in Multichannel P2P Live Streaming[END_REF], which is derived for traditional IPTV videos. This indicates that our system can be applied for both long-term and short-term types of videos.

Consequently, problems should be integrated in problem formulation for optimization purposes.

Finally, bandwidth ecient video delivery is not the only solution for mitigating the impact of system underprovisioning. Eorts could also be made in multiple directions: exploring new types of delivery network; increasing the capacity of the connection links; inventing new coding methods that could provide higher video quality with lower bandwidth consumption, and so on. In one word, scientists in all related domains should pay attention to the underprovisioning of the network.

X XML

Extensible Markup Language