A Survey on Content Placement Algorithms for Cloud-Based Content Delivery Networks <s> F. PARAMETER SETTINGS <s> The rapid growth of new information services and business-oriented applications entails the consideration of quality of service (QoS) in content distribution. This paper investigates the QoS-aware replica placement problems for responsiveness QoS requirements. We consider two classes of service models: replica-aware services and replica-blind services. In replica-aware services, the servers are aware of the locations of replicas and can therefore optimize request routing to improve responsiveness. We show that the QoS-aware placement problem for replica-aware services is NP-complete. Several heuristic algorithms for fast computation of good solutions are proposed and experimentally evaluated. In replica-blind services, the servers are not aware of the locations of replicas or even their existence. As a result, each replica only serves the requests flowing through it under some given routing strategy. We show that there exist polynomial optimal solutions to the QoS-aware placement problem for replica-blind services. Efficient algorithms are proposed to compute the optimal locations of replicas under different cost models. <s> BIB001 </s> A Survey on Content Placement Algorithms for Cloud-Based Content Delivery Networks <s> F. PARAMETER SETTINGS <s> This paper compares and analyzes 10 heuristics to solve the fine-grained data replication problem over the Internet. In fine-grained replication, frequently accessed data objects (as opposed to the entire website contents) are replicated onto a set of selected sites so as to minimize the average access time perceived by the end users. The paper presents a unified cost model that captures the minimization of the total object transfer cost in the system, which in turn leads to effective utilization of storage space, replica consistency, fault-tolerance, and load-balancing. The set of heuristics include six A-Star based algorithms, two bin packing algorithms, one greedy and one genetic algorithm. The heuristics are extensively simulated and compared using an experimental test-bed that closely mimics the Internet infrastructure and user access patterns. GT-ITM and Inet topology generators are used to obtain 80 well-defined network topologies based on flat, link distance, power-law and hierarchical transit-stub models. The user access patterns are derived from real access logs collected at the websites of Soccer World Cup 1998 and NASA Kennedy Space Center. The heuristics are evaluated by analyzing the communication cost incurred due to object transfers under the variance of server capacity, object size, read access, write access, number of objects and sites. The main benefit of this study is to facilitate readers with the choice of algorithms that guarantee fast or optimal or both types of solutions. This allows the selection of a particular algorithm to be used in a given scenario. <s> BIB002 </s> A Survey on Content Placement Algorithms for Cloud-Based Content Delivery Networks <s> F. PARAMETER SETTINGS <s> Creating replicas of frequently accessed data objects across a read-intensive Content Delivery Network (CDN) can result in reduced user response time. Because CDNs often operate under volatile conditions, it is of the utmost importance to study replica placement techniques that can cope with uncertainties in the system parameters. We propose four CDN replica placement heuristics that guarantee a robust performance under the uncertainty of arbitrary CDN server failures. By robust performance we mean the solution quality that a heuristic guarantees given the uncertainties in system parameters. The simulation results reveal interesting characteristics of the studied heuristics. We report these characteristics with a detailed discussion on which heuristics to utilize for robust CDN data replication given a specific scenario. <s> BIB003 </s> A Survey on Content Placement Algorithms for Cloud-Based Content Delivery Networks <s> F. PARAMETER SETTINGS <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> BIB004 </s> A Survey on Content Placement Algorithms for Cloud-Based Content Delivery Networks <s> F. PARAMETER SETTINGS <s> Caching and replication of popular data objects contribute significantly to the reduction of the network bandwidth usage and the overall access time to data. Our focus is to improve the efficiency of object replication within a given distributed replication group. Such a group consists of servers that dedicate certain amount of memory for replicating objects requested by their clients. The content replication problem we are solving is defined as follows: Given the request rates for the objects and the server capacities, find the replica allocation that minimizes the access time over all servers and objects. We design a distributed approximation algorithm that solves this problem and prove that it provides a 2-approximation solution. We also show that the communication and computational complexity of the algorithm is polynomial with respect to the number of servers, the number of objects, and the sum of the capacities of all servers. Finally, we perform simulation experiments to investigate the performance of our algorithm. The experiments show that our algorithm outperforms the best existing distributed algorithm that solves the replica placement problem. <s> BIB005 </s> A Survey on Content Placement Algorithms for Cloud-Based Content Delivery Networks <s> F. PARAMETER SETTINGS <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> BIB006 </s> A Survey on Content Placement Algorithms for Cloud-Based Content Delivery Networks <s> F. PARAMETER SETTINGS <s> Content distribution networks (CDNs) using storage clouds have recently started to emerge. Compared to traditional CDNs, storage cloud-based CDNs have the advantage of cost effectively offering hosting services to Web content providers without owning infrastructure. However, existing work on replica placement in CDNs does not readily apply in the cloud. In this paper, we investigated the joint problem of building distribution paths and placing Web server replicas in cloud CDNs to minimize the cost incurred on the CDN providers while satisfying QoS requirements for user requests. We formulate the cost optimization problem with accurate cost models and QoS requirements and show that the monthly cost can be as low as 2.62 US Dollars for a small Web site. We develop a suite of offline, online-static and online-dynamic heuristic algorithms that take as input network topology and work load information such as user location and request rates. We then evaluate the heuristics via Web trace-based simulation, and show that our heuristics behave very close to optimal under various network conditions. <s> BIB007 </s> A Survey on Content Placement Algorithms for Cloud-Based Content Delivery Networks <s> F. PARAMETER SETTINGS <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> BIB008 </s> A Survey on Content Placement Algorithms for Cloud-Based Content Delivery Networks <s> F. PARAMETER SETTINGS <s> News articles are a captivating type of online content that capture a significant amount of Internet users' interest. They are particularly consumed by mobile users and extremely diffused through online social platforms. As a result, there is an increased interest in promptly identifying the articles that will receive a significant amount of user attention. This task falls under the broad scope of content popularity prediction and has direct implications in various contexts such as caching strategies or online advertisement policies. In this paper we address the problem of predicting the popularity of news articles based on user comments. We formulate the prediction task into a ranking problem where the goal is not to infer the precise attention that a content will receive but to accurately rank articles based on their predicted popularity. To this end, we analyze the ranking performance of three prediction models using a dataset of articles covering a four-year period and published by 20minutes.fr, an important French online news platform. Our results indicate that prediction methods improve the ranking performance and we observed that for our dataset a simple linear prediction method outperforms more dedicated prediction methods. <s> BIB009 </s> A Survey on Content Placement Algorithms for Cloud-Based Content Delivery Networks <s> F. PARAMETER SETTINGS <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> BIB010 </s> A Survey on Content Placement Algorithms for Cloud-Based Content Delivery Networks <s> F. PARAMETER SETTINGS <s> In this paper we look at content placement in the high-dimensional regime: there are n servers, and O(n) distinct types of content. Each server can store and serve O(1) types at any given time. Demands for these content types arrive, and have to be served in an online fashion; over time, there are a total of O(n) of these demands. We consider the algorithmic task of content placement: determining which types of content should be on which server at any given time, in the setting where the demand statistics (i.e. the relative popularity of each type of content) are not known a-priori, but have to be inferred from the very demands we are trying to satisfy. This is the high- dimensional regime because this scaling (everything being O(n)) prevents consistent estimation of demand statistics; it models many modern settings where large numbers of users, servers and videos/webpages interact in this way. We characterize the performance of any scheme that separates learning and placement (i.e. which use a portion of the demands to gain some estimate of the demand statistics, and then uses the same for the remaining demands), showing it is order-wise strictly suboptimal. We then study a simple adaptive scheme - which myopically attempts to store the most recently requested content on idle servers - and show it outperforms schemes that separate learning and placement. Our results also generalize to the setting where the demand statistics change with time. Overall, our results demonstrate that separating the estimation of demand, and the subsequent use of the same, is strictly suboptimal. <s> BIB011 </s> A Survey on Content Placement Algorithms for Cloud-Based Content Delivery Networks <s> F. PARAMETER SETTINGS <s> The rapid growth of wireless content access implies the need for content placement and scheduling at wireless base stations. We study a system under which users are divided into clusters based on their channel conditions, and their requests are represented by different queues at logical front ends. Requests might be elastic (implying no hard delay constraint) or inelastic (requiring that a delay target be met). Correspondingly, we have request queues that indicate the number of elastic requests, and de ficit queues that indicate the de ficit in inelastic service. Caches are of finite size and can be refreshed periodically from a media vault. We consider two cost models that correspond to inelastic requests for streaming stored content and real -time streaming of events, respectively. We design provably optimal policies that stabilize the request queues(hence ensuring finite delays)and reduce average deficit to zero [hence ensuring that the quality -of-service (QoS) target is met]at small cost. We illustrate our approach through simulations. <s> BIB012 </s> A Survey on Content Placement Algorithms for Cloud-Based Content Delivery Networks <s> F. PARAMETER SETTINGS <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> BIB013 </s> A Survey on Content Placement Algorithms for Cloud-Based Content Delivery Networks <s> F. PARAMETER SETTINGS <s> Content Delivery Networks (CDN) and their globally dispersed caches host a myriad of User Generated Videos (UGV) to meet end-user requests with quality of service. To efficiently utilize the limited storage of the caches, it is imperative to improve the hit ratio of UGVs. In contrast to the traditional static content, UGV popularity is highly dynamic and dependent on end-user behavior. Therefore, we devise a novel popularity prediction model for UGV, using a hybrid regression model. Our hybrid regression model dynamically adapts the popularity of UGV that is built from a historical training dataset. We reduce error in predicting popularity by up to 14%, when compared to pure offline and online approaches, with a small increase in the execution time and memory overhead. Our novel popularity prediction model accounts for end- user behavior by considering the end-user video watch time and the number of shares for the UGVs. To improve cache performance in CDN, we employ a cache replacement strategy that leverages our popularity prediction model to efficiently evict the less popular UGVs for more popular content. We compare our novel cache replacement strategy with the traditional and state-of-the-art cache replacement strategies and show an increase in the average hit ratio of up to 74% and 7%, respectively, for UGVs with shortterm popularity. <s> BIB014
Algorithms can be validated analytically or via extensive simulation and empirical testing. In contrast to empirical and simulation validation, analytical validation can gauge the suboptimality of the algorithm by defining a constant factor approximation to the optimal BIB005 or optimality for smallscale scenarios. The effectiveness of the algorithms depends on various parameter settings BIB003 . Beginning with the underlying network model for CCDN, such as hierarchical (  , BIB012 ), random BIB001 , Waxman BIB001 , power law-based BIB002 , etc. Interestingly, point-of-presence (PoP)-node-to-Internet Protocol (IP) address mappings BIB007 are complemented by latency information from web traces to build realistic scenarios. Typically, content is gathered from VoD or UGV providers by crawling ( BIB004 ,  ) to gather UGC metadata and statistics or by analyzing HTTP traffic BIB006 or randomly BIB008 selecting UGC uploaded to YouTube. The YouTube UGC is decomposed into data and metadata. The metadata consists of static (e.g., title, upload time) and dynamic data (e.g., view count) BIB004 . The data consists of the static video content and a dynamic related video list, view statistics, including details about referrers and view counts due to the corresponding referrer, as illustrated in Fig. 5 . Generally, the probabilistic and statistical moments of a random variable (e.g., mean, variance, percentile, etc.) are employed to describe the popularity and correlation of content. However, various analytical, empirical and learning techniques are also used for setting parameter values, as illustrated in Fig. 6 . For example, numerical analysis, entropy and dispersion, similarity analysis and machine learning can be employed for content characterization. Linear regression BIB009 and hybrid regression models BIB014 are often used for predicting the popularity of content. A Gini coefficient can measure the distributional inequality and the value of the Gini coefficient measures the gap between popular videos and niche video BIB004 . Entropy and dispersion techniques are employed to study end-user behavior such as the probability of replay, view distribution and patterns BIB013 . Entropy and peak intensity BIB008 are used in the study of content correlation and relationships. These techniques can measure the intensity and consistency of the end-user interests in a specific spatial area. Interestingly, anomaly detection and traffic analysis are also employed to uncover content relationships BIB010 . Reinforcement learning techniques are also used in unsupervised analysis through clustering BIB010 of data and designing placement algorithms BIB011 . In this way, content relationships are formulated, defined or configured to study regularities or irregularities, similarity or dissimilarity in content relationships BIB010 , using entropy, temporal similarity and distribution-based techniques. 