<div>The demand for global video has been burgeoning across industries. With the expansion and improvement of video-streaming services, cloud-based video is evolving into a necessary feature of any successful business for reaching internal and external audiences. Over-the-top (OTT) video streaming, e.g., Netfix and YouTube, has been dominating the global IP traffic in recent years. More than 50% of OTT video traffic are now delivered through content distribution networks (CDNs). Even though multiple solutions have been proposed for improving congestion in the CDN system, managing the ever-increasing traffic requires a fundamental understanding of the system and the different design fexibilities (control knobs) to make the best use of the hardware limitations. In Addition, there is no analytical understanding for the key quality of experience (QoE) attributes (stall duration, average quality, etc.) for video streaming when transmitted using CDN-based multi-tier infrastructure, which is the focus of this thesis. The key contribution of this thesis is to provide a white-box analytical understanding of the key QoE attributes of the enduser in cloud storage systems, which can be used to systematically address the choppy user experience and have optimized system designs. The rst key design involves the scheduling strategy, that chooses the subset of CDN servers to obtain the content. The second key design involves the quality of each video chunk. The third key design involves deciding which contents to cache at the edge routers and which content needs to be stored at the CDN. Towards solving these challenges, this dissertation is divided into three parts. Part 1 considers video streaming over distributed systems where the video segments are encoded using an erasure code for better reliability. Part 2 looks at the problem of optimizing the tradeoff between quality and stall of the streamed videos. In Part 3, we consider caching partial contents of the videos at the CDN as well as at the edge-routers to further optimize video streaming services. We present a model for describing a today's representative multi-tier system architecture</div><div>for video streaming applications, typically composed of a centralized origin server, several CDN sites and edge-caches. Our model comprehensively considers the following factors: limited caching spaces at the CDN sites and edge-routers, allocation of CDN for a video request, choice of different ports from the CDN, and the central storage and bandwidth allocation. With this model, we optimize different quality of experience (QoE) measures and present novel, yet efficient, algorithms to solve the formulated optimization problems. Our extensive simulation results demonstrate that the proposed algorithms signicantly outperform the state-of-the-art strategies. We take one step further and implement a small-scale video streaming system in a real cloud environment, managed by Openstack, and validate our results</div>