The proliferation of new devices (such as smartphones and tablets) promotes new multimedia services (e.g. user-generated live video broadcasting), as well as new streaming techniques (e.g. rate-adaptive streaming). As a matter of fact, scientists observe a formidable, sustainable growth of Internet traffic related to video streaming. Yet, network infrastructures struggle to cope with this growth and it is now frequent that a delivery network is insufficiently provisioned. Such underprovisioning problem is more severe for live videos due to its real-time requirement. In this thesis, we focus on bandwidth efficient video delivery solutions for live streaming in underprovisioned video delivery networks. Specifically, we have two main contributions: (1) a user-generated live videos sharing system based on peer-to-peer (P2P) technique, and (2) a live rate-adaptive streaming system based on Content Delivery Network (CDN). First of all, we built an multioverlay P2P video sharing system which allows Internet users to broadcast their own live videos. Typically, such a system consists of multiple P2P live video streaming systems, and faces the problem of finding a suitable allocation of peer upload bandwidth. We designed various bandwidth allocation algorithms for this problem and showed how optimal solutions can be efficiently computed. Then, we studied the problem of delivering live rate-adaptive streams in the CDN. We identified a discretize streaming model for multiple live videos in modern CDNs. 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 specific scenario. This work is the first 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. Further, we presented a practical system, which efficiently utilizes CDN infrastructure to deliver live video streams to viewers in dynamic and large-scale CDNs. The benefits 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 efficient live video delivery solutions in underprovisioned delivery network for multiple streaming technologies. The aim is to maximally utilize the bandwidth of relay nodes (peers in P2P and forwarding equipments in CDN) to achieve an optimization goal.
Multiple Live Videos Delivery in Underprovisioned Networks