Routing And Caching Algorithms For Multimedia Transmission Over Software-Defined Networks

The rapid growth of rich media-enabled applications has greatly changed the way that people use the Internet, bringing the demand for high quality multimedia content into an unprecedented level. For instance, online social network users share nowadays not only texts and images, but also audio and video content. High-quality video is also demanded by the prevalence of retina-level resolution displays, new content platforms, and emerging technologies such as virtual reality. As a consequence, the video content that needs to be delivered in real-time has grown significantly in terms of volume, size and diversity.The fast increasing multimedia traffic brings many challenges, including the guar-antee of high quality of service, avoiding low transmission efficiency, and servicing heterogeneous users. In response to these challenges, researchers from different back-grounds propose various compression schemes, new network architectures, and adap-tive streaming techniques. Among these works, research on network architectures has a unique value. First, the Internet is designed based on the point-to-point communication model during the last century, which cannot provide good support to the one-to-many transmission model that is commonly seen in nowadays applications. Second, renovat-ing the underlying architecture also provides a way to solve many intrinsic problems that trouble today’s network through which multimedia content is streamed. By adopting new networking architectures, we enable the possibility to fully utilize nice characteris-tics of new coding schemes (e.g. scalable video coding) and new streaming techniques (e.g. adaptive streaming) and facilitates their deployment. For example, two famous network architectures, software-defined networking (SDN) and named data network-ing (NDN), provide effective solutions to the intrinsic deficiency of today’s network by introducing flexible global routing and in-network caching, respectively. These recent progresses create great potentials for further improving the performance of multimedia content transmission.This thesis is based on SDN, one of the most recognized architecture for future network, and focused on improving the performance and efficiency of multimedia con-tent transmission. We consider the routing problem under classic SDN setting, and the routing and caching problem under a SDN setting with in-network caching support. Specifically, we first consider the classic SDN architecture that has no caching capa-bility. We propose a multi-path routing algorithm that calculates routing path while satisfying the request’s requirements on bandwidth, delay, and delay jitter. The algo-rithm also considers the relative priority requirements of different data layers of the requested content, and uses this information to improve user experience. To further increase transmission efficiency, we consider an SDN setting with in-network caching support, where caching functionalities are added to several routing nodes. In such set-ting, we design a new routing algorithm that tries to aggregate multimedia traffic and utilizes the cache nodes to reduce bandwidth consumption. Finally, we study the cache replacement strategy on cache nodes and propose a machine learning based cache re-placement algorithm that significantly improves the cache hit rate of cache nodes. In this way, we further improve the overall transmission efficiency.Main contributions of this thesis are listed as follows:1) This thesis proposes a multi-path routing algorithm to deliver layered multime-dia content. The algorithm exploits the priority requirements between different layers of the requested multimedia data and allocates routing path according to the requirements to improve the quality of service. In this way, the algorithm creates substantial potentials for scalable coding techniques. When processing a user’s request, the algorithm also considers the request’s bandwidth requirement, latency requirement, and latency jitter requirement. By utilizing the flexibility of global routing in SDN, the algorithm dynamically calculates and allocates paths for the request, therefore avoids link congestion and improves transmission per-formance.2) This thesis proposes a routing technique targeted for SDN with in-network caching support. By using the flexible routing mechanism of SDN, we design an inte-ger linear programming (ILP) based algorithm that aggregates multimedia traffic into cache nodes to save link bandwidth, and thereby improves transmission effi-ciency.3) This thesis proposes popularity-driven content caching, an online algorithm that learns the relationship between the future popularity of a content and its recent access pattern. Using the popularity forecasting result, the algorithm knows the trend of each content and makes proper cache replacement decisions to maximize the cache hit rate. We proved that both the learning regret and the loss of cache hit rate is sublinear in the number of received content requests, compared to the optimal oracle caching scheme that knows the future popularity of all content. We design extensive simulations with real world traces to validate the effectiveness of our algorithms. The algorithm not only outperforms all other benchmarks in the simulation, but also significantly reduces the number of cache replacement, which is a long-standing issue of traditional cache replacement algorithms because fre-quent cache replacment can lead to heavy I/O pressure on a cache system. The amortized time complexity of the proposed algorithm is logarithmic in the number of received requests.