A Survey on Content Placement Algorithms for Cloud-Based Content Delivery Networks <s> IV. DESIGN CRITERIA OF CP ALGORITHMS BASED ON CONTENT <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> BIB001 </s> A Survey on Content Placement Algorithms for Cloud-Based Content Delivery Networks <s> IV. DESIGN CRITERIA OF CP ALGORITHMS BASED ON CONTENT <s> One of the most striking properties of the Internet is its flexibility to accommodate features it was not conceived for. Among the most significant examples, in this survey we consider the transition of the Internet from a reliable fault-tolerant network for host-to-host communication to a content-centric network, i.e. a network mostly devoted to support efficient generation, sharing and access to content. We survey this research area according to a top-down approach. We present a conceptual framework that encompasses the key building blocks required to support content-centric networking in the Internet. Then we describe in detail the two most important types of content-centric Internet technologies, i.e., Content-Delivery Networks (CDNs) and P2P systems. For each of them, we show how they cover the key building blocks. We then identify the functional components of CDN and P2P content management solutions, and discuss the main solutions proposed in the literature for each of them. We consider different types of content (both real time and non real time), and different networking environments (fixed, mobile, ...). Finally, we also discuss the main recent research trends focused on how to design the Future Internet as a native content-centric network. <s> BIB002 </s> A Survey on Content Placement Algorithms for Cloud-Based Content Delivery Networks <s> IV. DESIGN CRITERIA OF CP ALGORITHMS BASED ON CONTENT <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> IV. DESIGN CRITERIA OF CP ALGORITHMS BASED ON CONTENT <s> Power-laws are ubiquitous in the Internet and its applications. This tutorial presents a review of power-laws with emphasis on observations from Internet measurements. First, we introduce power-laws and describe two commonly observed power-law distributions, the Pareto and Zipf distributions. Two frequently occurring terms associated with these distributions, specifically heavy tails and long tails, are also discussed. Second, the preferential attachment model, which is a widely used model for generating power-law graph structures, is reviewed. Subsequently, we present several examples of Internet workload properties that exhibit power-law behavior. Finally, we explore several implications of power-laws in computer networks. Using examples from past and present, we review how researchers have studied and exploited power-law properties. We observe that despite the challenges posed, power-laws have been effectively leveraged by researchers to improve the design and performance of Internet-based systems. <s> BIB004 </s> A Survey on Content Placement Algorithms for Cloud-Based Content Delivery Networks <s> IV. DESIGN CRITERIA OF CP ALGORITHMS BASED ON CONTENT <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> BIB005 </s> A Survey on Content Placement Algorithms for Cloud-Based Content Delivery Networks <s> IV. DESIGN CRITERIA OF CP ALGORITHMS BASED ON CONTENT <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> BIB006
There are various implications of the inherent characteristics of classical and contemporary content, end-user behavior and their OSN relationships on content for CP algorithms. However, their implications can be broadly classified as those that influence content access patterns or popularity. As illustrated in Fig. 11 , these are critical in designing efficient CP algorithms for CCDNs. Content access patterns not only account for spatial and temporal locality, but they also include devices that generate the content access request. The heterogeneity in end-user mobile devices requires a set of different resolutions and formats of content to be stored for content delivery. This requires CP algorithms for CCDNs to meet the requirements of content access for heterogeneous end-user devices. Traditional CDNs were designed for static content BIB002 and accommodating CP algorithms to cater to content for mobile devices faced numerous challenges BIB002 . The number of mobile devices is expected to far exceed that of the desktop and hard-wired devices, requiring content providers hosting in CCDNs to keep multiple formats of the same video content. This supports the diversity in hardware and software in the devices. For instance, though YouTube caches multiple formats of a video, it still results in a miss and degradation in QoS, since all video formats are not equally popular and end-users may be redirected to datacenters that are farther away in proximity BIB001 . These are required for designing effective CP algorithms in CCDNs. The temporal, spatial and OSN relationships influence content access patterns. End-users within a geographical region have increased similarity. End-users in similar social groups or OSN relationships will have similar content access patterns. Therefore, temporal, social and OSN relationships can influence content access patterns and should be leveraged in CP algorithms to minimize the storage cost and increase QoS in serving the end-user requests. Another intrinsic property of content is correlations based on recommendation engines or referred videos or sites. It is important that CP algorithms are sensitive to content access patterns of correlated and referred videos since they can significantly impact the popularity of content. Content popularity follows heavy-tail distributions, such as those parameterized by power law and exponential functions. Idealistic distributions (e.g., Gaussian Normal) and power law distributions can capture populations that vary in orders of magnitude (  , BIB004 ). Their heavy tails, i.e. large values on x-axis, allow to study the data quantitatively, that otherwise would have been written off as outliers. This trend in popularity implies that, though pull-based approach is simple and effective, it will not give high hit ratio as the data in the long tail will generate misses BIB004 . The cache hit rate is also dependent on the cache size and the eviction probability of the content BIB006 . Furthermore, the low probability of replay BIB006 of video content implies that the popularity will eventually decrease, suggesting that any content will eventually become stale and require replacement. As long as the stale content occupies space on the cache, it will generate a cache miss. Nonetheless, CP is commercially achieved via pull-based caching (e.g., UGC on YouTube). This is because bandwidth is a resource in CCDNs that must be optimized and caching with simple LRU yields high byte hit ratio that efficiently utilizes the cloud bandwidth resources. The global file hit ratio is generally low, i.e. around 35%, due to the UGC that lies in the long tail BIB005 . However, considering a byte hit ratio, the heavy hitters, i.e. the popular files, push the byte hit ratios significantly higher, to about 75% BIB005 . Moreover, the popularity of content can be arbitrarily modeled by a power law function, but different categories of content are represented by different power law functions. The shape of the power law functions is controlled using shape parameter in a power law function. This influences efficiency in modeling the popularity of content that belong in different categories since popularity is directly proportional to the age of various video categories. Therefore, Least Recently Used (LRU) and Least Frequently Used (LFU) cache replacement strategies alone are not adaptive enough to the dynamically changing popularity of content in different categories BIB006 . However, FIFO performs best for News category since it corresponds to the observation that stale news looses end-user interest. Therefore, old news videos should be replaced first BIB006 whereas, for movies, music and TV, LFU enables cache replacement algorithms to effectively reflect the dynamic popularity of these categories BIB006 . A mixed cache replacement strategy can adapt to changing popularity BIB006 . For example, LFU and FIFO probabilistically evict the least frequently used or the oldest content and outperform simple LFU and LRU with moderate overhead BIB006 . Furthermore, the high spatial correlation in content access patterns instigate the preferential caching of videos for different geographic regions BIB003 , as end-users with similar interests are geographically clustered in the same country, town or neighborhood. Furthermore, cache management can also include filtering techniques BIB005 , such that content is stored on the surrogate servers after a certain number of end-user requests have been received. Unfortunately, filtering reduces byte hit ratio since heavy hitters enter cache late and do not maximize bandwidth savings BIB005 . Therefore, it is critical to design CP algorithms that are sensitive to dynamically changing popularity, age and content category.