A Survey on Content Placement Algorithms for Cloud-Based Content Delivery Networks <s> B. CONTEMPORARY CONTENT CHARACTERISTICS <s> Hosting a collection of millions of videos, YouTube offers several features to help users discover the videos of their interest. For example, YouTube provides video search, related video recommendation and front page highlight. The understanding of how these features drive video views is useful for creating a strategy to drive video popularity. In this paper, we perform a measurement study on data sets crawled from YouTube and find that the related video recommendation, which recommends the videos that are related to the video a user is watching, is one of the most important view sources of videos. Despite the fact that the YouTube video search is the number one source of views in aggregation, the related video recommendation is the main source of views for the majority of the videos on YouTube. Furthermore, our results reveal that there is a strong correlation between the view count of a video and the average view count of its top referrer videos. This implies that a video has a higher chance to become popular when it is placed on the related video recommendation lists of popular videos. We also find that the click through rate from a video to its related videos is high and the position of a video in a related video list plays a critical role in the click through rate. Finally, our evaluation of the impact of the related video recommendation system on the diversity of video views indicates that the current recommendation system helps to increase the diversity of video views in aggregation. <s> BIB001 </s> A Survey on Content Placement Algorithms for Cloud-Based Content Delivery Networks <s> B. CONTEMPORARY CONTENT CHARACTERISTICS <s> In this paper we present a complete measurement study that compares YouTube traffic generated by mobile devices (smart-phones,tablets) with traffic generated by common PCs (desktops, notebooks, netbooks). We investigate the users' behavior and correlate it with the system performance. Our measurements are performed using unique data sets which are collected from vantage points in nation-wide ISPs and University campuses from two countries in Europe and the U.S. Our results show that the user access patterns are similar across a wide range of user locations, access technologies and user devices. Users stick with default player configurations, e.g., not changing video resolution or rarely enabling full screen playback. Furthermore it is very common that users abort video playback, with 60% of videos watched for no more than 20% of their duration. We show that the YouTube system is highly optimized for PC access and leverages aggressive buffering policies to guarantee excellent video playback. This however causes 25%-39% of data to be unnecessarily transferred, since users abort the playback very early. This waste of data transferred is even higher when mobile devices are considered. The limited storage offered by those devices makes the video download more complicated and overall less efficient, so that clients typically download more data than the actual video size. Overall, this result calls for better system optimization for both, PC and mobile accesses. <s> BIB002 </s> A Survey on Content Placement Algorithms for Cloud-Based Content Delivery Networks <s> B. CONTEMPORARY CONTENT CHARACTERISTICS <s> One of the most popular user activities on the Web is watching videos. Services like YouTube, Vimeo, and Hulu host and stream millions of videos, providing content that is on par with TV. While some of this content is popular all over the globe, some videos might be only watched in a confined, local region. In this work we study the relationship between popularity and locality of online YouTube videos. We investigate whether YouTube videos exhibit geographic locality of interest, with views arising from a confined spatial area rather than from a global one. Our analysis is done on a corpus of more than 20 millions YouTube videos, uploaded over one year from different regions. We find that about 50% of the videos have more than 70% of their views in a single region. By relating locality to viralness we show that social sharing generally widens the geographic reach of a video. If, however, a video cannot carry its social impulse over to other means of discovery, it gets stuck in a more confined geographic region. Finally, we analyze how the geographic properties of a video's views evolve on a daily basis during its lifetime, providing new insights on how the geographic reach of a video changes as its popularity peaks and then fades away. Our results demonstrate how, despite the global nature of the Web, online video consumption appears constrained by geographic locality of interest: this has a potential impact on a wide range of systems and applications, spanning from delivery networks to recommendation and discovery engines, providing new directions for future research. <s> BIB003 </s> A Survey on Content Placement Algorithms for Cloud-Based Content Delivery Networks <s> B. CONTEMPORARY CONTENT CHARACTERISTICS <s> In this paper, we report YouTube traffic measurements from Orange IP backbone network connecting residential customers. We exhibit its salient features in relation to the performance of caching. By examining the file popularity distribution, we show that video requests are highly volatile in that a huge number of files are viewed only a few times; these files are therefore not relevant for caching. Nevertheless, there is a subset of files which are massively viewed by end users and are worth caching. On the basis of this experimental observation, we develop a mathematical model for estimating the efficiency of file caching in the presence of noise traffic composed of those files which are rarely requested and thus “pollute” the cache. We then proceed to trace-driven simulations in order to check the qualitative conclusions derived from the theoretical model. <s> BIB004 </s> A Survey on Content Placement Algorithms for Cloud-Based Content Delivery Networks <s> B. CONTEMPORARY CONTENT CHARACTERISTICS <s> YouTube is the most popular service in today's Internet. Google relies on its massive content delivery network (CDN) to push YouTube videos as close as possible to the end-users, both to improve their watching experience as well as to reduce the load on the core of the network, using dynamic server selection strategies. However, we show that such a dynamic approach can actually have negative effects on the end-user quality of experience (QoE). Through the comprehensive analysis of one month of YouTube flow traces collected at the network of a large European ISP, we report a real case study in which YouTube QoE-relevant degradation affecting a large number of users occurs as a result of Google's server selection strategies. We present an iterative and structured process to detect, characterize, and diagnose QoE-relevant anomalies in CDN distributed services such as YouTube. The overall process uses statistical analysis methodologies to unveil the root causes behind automatically detected problems linked to the dynamics of CDNs' server selection strategies. <s> BIB005 </s> A Survey on Content Placement Algorithms for Cloud-Based Content Delivery Networks <s> B. CONTEMPORARY CONTENT CHARACTERISTICS <s> We address the problem of content replication in large distributed content delivery networks, composed of a data center assisted by many small servers with limited capabilities and located at the edge of the network. We aim at optimizing the placement of contents on the servers to offload the data center as much as possible. We model the sub-system constituted by the small servers as a loss network, each loss corresponding to a request to the data center. Based on large system / storage behavior, we obtain an asymptotic formula for the optimal replication of contents and propose adaptive schemes to attain it by reacting to losses, as well as faster algorithms which can react before losses occur. We show through simulations that our adaptive schemes outperform significantly standard replication strategies both in terms of loss rates and adaptation speed. <s> BIB006 </s> A Survey on Content Placement Algorithms for Cloud-Based Content Delivery Networks <s> B. CONTEMPORARY CONTENT CHARACTERISTICS <s> One of the key goals of Network Functions Virtualization (NFV) is achieving energy efficiency through workload consolidation. A good example for maximizing energy savings is the Virtualization of Content Delivery Networks (vCDNs) NFV use case where the video streaming workloads exhibit significant difference between prime-time and non-prime-time usage of the infrastructure. This paper examines the practical challenges in maximizing energy efficiency for vCDN workloads. This paper proposes an open NFV architectural framework for conveying content virality information from Cloud applications such as YouTube, Twitter and mechanisms for leveraging it to maximize the energy efficiency for vCDN workloads. This paper also proposes a more general architecture for any Cloud/NFV application that may experience virality. <s> BIB007 </s> A Survey on Content Placement Algorithms for Cloud-Based Content Delivery Networks <s> B. CONTEMPORARY CONTENT CHARACTERISTICS <s> A significantly large proportion of HTTP traffic results from bandwidth-intensive multimedia content circulating through online social networks (OSNs). With multimedia content providers, such as YouTube, often relying on content delivery network (CDN) infrastructures, the pursuit lies in exploiting the user activity extracted from OSNs to improve the content prefetching mechanism. Aiming to reduce bandwidth usage, we incorporated a dynamic mechanism to CDNsim, a stand-alone CDN traffic simulator. This mechanism is based on a dynamic policy that takes patterns of information transmission over OSNs into account. Herein, we demonstrate that the performance of CDNs can be improved, and the cost of copying to surrogate servers is taken into consideration. <s> BIB008 </s> A Survey on Content Placement Algorithms for Cloud-Based Content Delivery Networks <s> B. CONTEMPORARY CONTENT CHARACTERISTICS <s> Popular online video-on-demand (VoD) services all maintain a large catalog of videos for their users to access. The knowledge of video popularity is very important for system operation , such as video caching on content distribution network (CDN) servers. The video popularity distribution at a given time is quite well understood. We study how the video popularity changes with time, for different types of videos, and apply the results to design video caching strategies. Our study is based on analyzing the video access levels over time, based on data provided by a large video service provider. Our main finding is, while there are variations, the glory days of a video’s popularity typically pass by quickly and the probability of replaying a video by the same user is low. The reason appears to be due to fairly regular number of users and view time per day for each user, and continuous arrival of new videos. All these facts will affect how video popularity changes, hence also affect the optimal video caching strategy. Based on the observation from our measurement study, we propose a mixed replication strategy (of LFU and FIFO) that can handle different kinds of videos. Offline strategy assuming tomorrow’s video popularity is known in advance is used as a performance benchmark. Through trace-driven simulation, we show that the caching performance achieved by the mixed strategy is very close to the performance achieved by the offline strategy. <s> BIB009 </s> A Survey on Content Placement Algorithms for Cloud-Based Content Delivery Networks <s> B. CONTEMPORARY CONTENT CHARACTERISTICS <s> The increasing popularity of online social networks (OSNs) has been transforming the dissemination pattern of social video contents. We can utilize the social information propagation pattern to improve the efficiency of social video distribution. In this paper, motivated by the social community classification, we present a social video replication and user request dispatching mechanism in the cloud content delivery network architecture to reduce the system operational cost, while guaranteeing the averaged service latency. Specifically, we first present a community classification method that clusters social users with social relationships, close geolocations, and similar video watching interests into various communities. Then, we conduct a large-scale measurement on a real OSN system to study the diversities of social video propagation and the effectiveness of our communities on smoothing the diversity. Finally, we propose the community-based video replication and request dispatching strategy and formulate it as a constrained optimization problem. Based on a stochastic optimization framework, we derive an online solution and rigorously prove the optimality. We evaluate our algorithm on a real trace under realistic settings and demonstrate that our algorithm can reduce the monetary cost by 30% against traditional approaches with the same service latency. <s> BIB010
On top of the classical content characteristics, contemporary content characteristics include mobility, interactivity and OSN relationships. These characteristics greatly influence the design of CP algorithms in CCDNs BIB010 . In 2014, 64% of global consumer Internet traffic was video content and 57% of this video traffic was delivered through CDNs  . By 2019, the video traffic is estimated to increase by 80%  and the traffic coming from mobile devices and applications will increase by ten folds  . It is imperative to cater to the near future demands of the global Internet traffic by delivering varying video resolutions in different formats with QoS via efficient content placement algorithms in CCDNs. Fig. 8 illustrates the various components of video streaming, such as chunk size, format, resolution and playback mode. The resolution is inferred from the bitrate BIB005 and the playback mode depicts whether video is in playback, fast forward, rewind or pause mode. Traditionally, video content is decomposed into chunks of pseudo-equal sizes and delivered through CDN infrastructure. These components are leveraged to predict end-user behavior and interactivity, which influence the performance of content placement algorithms ( BIB002 , BIB003 ). For mobile devices, such as tablets, laptops and cell phones, multimedia content is stored in different resolutions and formats BIB002 . Transcoding techniques are applied to match device requirements to the delivered video content. The chunks vary in size based on mobile or fixed platform, such as personal computer (PC). The chunk sizes are typically fixed in PC and variable in mobile environment. They are often limited by buffer size, dictated by the device BIB002 . Today's video content hails from providers that offer VoD and UGC services. Videos are selected from catalogues that host dozens of categories, such as Music, Movie, Family, Children, Sport, News, Classic, Featured, Recently Uploaded, etc. Generally, end-users can only play videos through VoD services, whereas end-users can share, edit and delete their own multimedia content through applications that offer UGC services. Furthermore, today's VoD and UGC applications and services also include an OSN perspective, where end-users can interact with each other to suggest, share and rate video content hosted in VoD and UGC applications. This complicates popularity prediction and leaves it susceptible to unpredictability BIB010 . From the perspective of CP algorithms, the chunking mechanism in video streaming, the video operations (e.g., fast forward and reverse), the spatial and temporal correlations and the complex OSN relationships pose new challenges. Today, videos are generally hosted in VoD systems or as UGV on UGC hosting sites, such as Netflix and YouTube, respectively. End-users can only subscribe to watch videos in the catalogue of VoD providers whereas end-users produce and consume videos hosted by UGC providers. Both VoD and UGC providers host videos but they are strikingly different BIB004 , as illustrated in Fig. 9 . VoD content has a finite, though huge, catalogue and is stored on edge of content delivery network BIB006 whereas UGC catalogue is seemingly infinite as it is continuously growing with content uploaded by end-users and stored within the content delivery network BIB006 . VoD content is usually uploaded by VoD content providers at off-peak times and their prediction models can closely estimate the demand for content. Therefore, VoD content is less volatile than UGC BIB004 and UGV has a virality attribute BIB007 due to the interactivity of end-users that share and link UGV on OSN BIB008 . The predictability of VoD greatly reduces the burden for CP algorithms BIB009 since video content is controlled by the content provider and is not erratically uploaded, edited and deleted by end-users, as in UGC. The VoD and UGC catalogue contain videos that can be classified into a dozen different categories, such as Children, Sports, News, Music, Movie, etc. The number of end-users that view the video is recorded and maintained as the view count in the metadata of the video. Typically, video popularity is inferred by the view count. However, it can be assessed by two different techniques: 1) Based on the temporal evolution of the number of views and 2) the number of views before and after the maximum (the peak of) number of views BIB003 . Fig. 10 illustrates the lifecycle of a video, which resonates with the temporal evolution of popularity. The first phase of a video is the hot phase, when it generates high view counts, usually within the first week of being released/hosted BIB009 . As videos get older, they enter the warm or lukewarm BIB001 phase, where popularity and the view count are attributed to video search, spread by word-of-mouth BIB009 or appearing on recommended and related video lists BIB001 . As the video gets older, it enters the cold BIB009 phase, when the popularity significantly wanes and the video hardly generates any view counts. Though videos are inherently static, only warm videos exhibit popularity that is very well estimated by the Zipf function ( BIB009 , BIB004 ). The popularity of hot videos is much larger than those predicted by Zipf functions BIB004 . The popularity of cold videos falls sharply BIB004 , i.e. the popularity of content that lies at the far end of long tail functions, such as Zipf. It should be noted that different techniques are used to collect data, from an ISP ( BIB005 , BIB004 ) or from campus networks BIB002 . The data from ISP is diverse and depicts end-users whose behavior is very varied. The data from campus networks introduces a natural bias. For example, in a university campus network results are skewed since end-users are primarily students with different content access patterns. Meanwhile, data can be collected by crawling (  , BIB001 ) to gather UGC metadata and statistics or analyzing HTTP traffic BIB002 or randomly BIB003 selecting UGC uploaded to YouTube. However, despite the data collection scheme, popularity distribution of all samples follows the Zipf distribution. All categories of videos follow similar trends with respect to temporal evolution in popularity ( BIB001 , BIB003 , BIB009 ). The key characteristics can be identified as follows: 1) Only a small subset of hot videos is selected to be featured in recommended BIB009 and trending video lists, which significantly skews their popularity BIB001 and therefore their view counts are distinctly different from warm and lukewarm videos BIB003 . 2) Although all categories follow similar trends with respect to popularity, there are some categories that are highly sensitive to the age of video, such as those appearing under News and Sports categories, since less people are interested in stale News BIB009 . 3) Certain categories are susceptible to local popularity since they are bound by cultural or language barriers while others enjoy global popularity, i.e. their popularity spread to other regions BIB003 . Most VoD and UGC service providers cater to mobile end-users, such as those accessing VoD and/or UGC videos via tablets and mobile phones. So, mobile content is a special subclass of VoD and UGC. However, content geared for mobile devices require special handling. VoD and UGC service providers must deliver content with QoS, through a communication medium known for slower downlink rates and intermittent connectivity. Mobile multimedia content is delivered to smart phones, tablets, set-top-boxes and smart TVs that access content via wireless and 3G/4G Internet connections. The wireless medium and the video streaming process pose challenges for the CP algorithms.