A Survey on Content Placement Algorithms for Cloud-Based Content Delivery Networks <s> B. CONTENT FLOW IN CONTENT PLACEMENT <s> Numerous replica placement algorithms have been proposed in the literature for use in content delivery networks. However, little has been done to compare the various placement algorithms against each other and against caching. This paper debates whether we need replica placement algorithms in content delivery networks or not. The paper uses extensive evaluation of algorithms, systems and web workloads to answer this question. We conclude that a simple delayed-LRU caching scheme outperforms, or at least performs as well as the best replica placement algorithms. As LRU caching is less complex than most replica placement algorithms, caching is clearly the preferred option. However, we believe that replica placement algorithms will be necessary once properties such as availability, reliability, performance and bounded update propagation will have to be guaranteed by content delivery networks. <s> BIB001 </s> A Survey on Content Placement Algorithms for Cloud-Based Content Delivery Networks <s> B. CONTENT FLOW IN CONTENT PLACEMENT <s> Content distribution networks (CDNs) are increasingly being used to disseminate data in today's Internet. The growing interest in CDNs is motivated by a common problem across disciplines: how does one reduce the load on the origin server and the traffic on the Internet, and ultimately improve response time to users? In this direction, crucial data management issues should be addressed. A very important issue is the optimal placement of the outsourced content to CDN's servers. Taking into account that this problem is NP complete, a heuristic method should be developed. All the approaches developed so far assume the existence of adequate popularity statistics. Such information though, is not always available, or it is extremely volatile, turning such methods problematic. This paper develops a network-adaptive, non-parameterized technique to place the outsourced content to CDN's servers, which requires no a-priori knowledge of request statistics. We place the outsourced objects to these servers with respect to the network latency that each object produces. Through a detailed simulation environment, using both real and synthetic data, we show that the proposed technique can yield up to 25% reduction in user-perceived latency, compared with other heuristic schemes which have knowledge of the content popularity. <s> BIB002 </s> A Survey on Content Placement Algorithms for Cloud-Based Content Delivery Networks <s> B. CONTENT FLOW IN CONTENT PLACEMENT <s> The addition of storage capacity in network nodes for the caching or replication of popular data objects results in reduced end-user delay, reduced network traffic, and improved scalability. The problem of allocating an available storage budget to the nodes of a hierarchical content distribution system is formulated; optimal algorithms, as well as fast/efficient heuristics, are developed for its solution. An innovative aspect of the presented approach is that it combines all relevant subproblems, concerning node locations, node sizes, and object placement, and solves them jointly in a single optimization step. The developed algorithms may be utilized in content distribution networks that employ either replication or caching/replacement. In addition to reducing the average fetch distance for the requested content, they also cater to load balancing and workload constraints on a given node. Strictly hierarchical, as well as hierarchical with peering, request routing models are considered. <s> BIB003 </s> A Survey on Content Placement Algorithms for Cloud-Based Content Delivery Networks <s> B. CONTENT FLOW IN CONTENT PLACEMENT <s> This paper investigates the optimal replication of data objects at hierarchical and transparent Web proxies. By transparent, we mean the proxies are capable of intercepting users' requests and forwarding the requests to a higher level proxy if the requested data are not present in their local cache. Two cases of data replication at proxies are studied: 1) proxies having unlimited storage capacities and 2) proxies having limited storage capacities. For the former case, an efficient algorithm for computing the optimal result is proposed. For the latter case, we prove the problem is NP-hard, and propose two heuristic algorithms. Extensive simulations have been conducted and the simulation results have demonstrated significant performance gain by using the proposed data replication algorithms and also shown the proposed algorithms out-perform the standard Web caching algorithm (LRU threshold method). <s> BIB004 </s> A Survey on Content Placement Algorithms for Cloud-Based Content Delivery Networks <s> B. CONTENT FLOW IN CONTENT PLACEMENT <s> Transparent data replication is a promising technique for improving the system performance of a large distributed network. Transcoding is an important technology which adapts the same multimedia object to diverse mobile appliances; thus, users' requests for a specified version of a multimedia object could be served by a more detailed version cached according to transcoding. Therefore, it is particularly of theoretical and practical necessity to determine the proper version to be cached at each node such that the specified objective is achieved. In this paper, we address the problem of multimedia object placement for transparent data replication. The performance objective is to minimize the total access cost by considering both transmission cost and transcoding cost. We present optimal solutions for different cases for this problem. The performance of the proposed solutions is evaluated with a set of carefully designed simulation experiments for various performance metrics over a wide range of system parameters. The simulation results show that our solution consistently and significantly outperforms comparison solutions in terms of all the performance metrics considered <s> BIB005 </s> A Survey on Content Placement Algorithms for Cloud-Based Content Delivery Networks <s> B. CONTENT FLOW IN CONTENT PLACEMENT <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> BIB006 </s> A Survey on Content Placement Algorithms for Cloud-Based Content Delivery Networks <s> B. CONTENT FLOW IN CONTENT PLACEMENT <s> Cloud computing and 'Storage As A Service' (SaaS) are experiencing a momentous popularity increase due to its flexible, and scalable access to resources. Especially, cloud storage is becoming an economical alternative to traditional content delivery networks (CDNs) such as Akamai and Limelight Networks for moderate-size content providers. Previous research on content distribution mainly focuses on reducing latency experienced by content customers. A few recent studies address the issue of bandwidth usage in CDNs, as the bandwidth consumption is an important issue due to its relevance to the cost of content providers. However, few researches consider both bandwidth consumption and delay performance for the content providers that use cloud storages with limited budgets, which is the focus of this paper. We develop an efficient light-weight approximation algorithm toward the joint optimization problem of content placement. We also conduct the analysis of its theoretical complexities. The performance bound of the proposed approximation algorithm exhibits a much better worst case than those in previous studies. We further extend the approximate algorithm into a distributed version that allows it to promptly react to dynamic changes in users' interests. The extensive results from both simulations and Planetlab experiments exhibit that the performance is near optimal for most of the practical conditions. <s> BIB007 </s> A Survey on Content Placement Algorithms for Cloud-Based Content Delivery Networks <s> B. CONTENT FLOW IN CONTENT PLACEMENT <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> BIB008
In general, content placement can be modeled as push-or pull-based strategies, as illustrated in Fig. 2 , depending on the direction of content flow between the origin server(s) and the surrogate servers. Push-based content placement is proactive, whereas pull-based is reactive to end-user requests for content. In push-based CP, content providers estimate end-user requests or predict content access patterns and replicate content from origin server(s) to surrogates, prior to receiving end-user requests for content. The pull-based approach is relatively simpler, where end-user requests instigate the surrogates to download and store content from the origin server(s) or the neighboring surrogate server(s). Initially, in pull-based CP, all end-user requests will result in a miss, since the surrogate will need to download content from the origin or nearby surrogate server(s). Gradually, as the repository on the surrogate server grows, end-user requests will result in a hit and end-user requests will be directly satisfied by the surrogate server. The surrogates can cooperate with each other, to download content from another surrogate(s) that is in closer proximity than the origin server, or directly from the origin server in cooperative or non-cooperative schemes, respectively. In push-based CP, contingencies are in-place to cater to unpredicted end-user requests and content access patterns. Generally, commercial CCDNs employ simple caching such as least recently used (LRU) ( BIB008 ,  , BIB005 ) for content placement. The limited storage capacity of cache requires a cache management and replacement strategy. This is simplistic in implementation, such as low bookkeeping (maintenance) and traffic and storage overhead. However, these techniques should be improved for reliability, availability and other performance metrics BIB001 . Interestingly, simple caching with LRU cache replacement outperforms various push-based content placement algorithms, when the update period is delayed to approximately once in a day BIB001 . But, cooperative push-based CP algorithms also yield high performance over other content placement algorithms BIB002 . Generally, the efficiency of pulland push-based content placement rely significantly on the accuracy of the prediction and estimation models for the prediction of end-user requests or content access patterns BIB006 . Therefore, caching, pull-based CP, is complementary to pushbased CP that can work together to further increase the QoS of CCDNs BIB003 . This is essential in designing CP algorithms that eventually replace the content stored on the surrogate servers. Therefore, a hybrid ( BIB004 , BIB007 ) of pull-and push-based content placement algorithms can leverage both the spatial and temporal correlations in data and the heavy tail distribution exhibited by the popularity of content. In the following sections, we will discuss the different problem solving techniques for content placement in CCDNs.