A Survey on Content Placement Algorithms for Cloud-Based Content Delivery Networks <s> A. PULL-BASED CONTENT PLACEMENT IN CCDNs <s> Web caching is an important technique for reducing Internet access latency, network traffic, and server load. This paper investigates cache management strategies for the en-route web caching environment, where caches are associated with routing nodes in the network. We propose a novel caching scheme that integrates both object placement and replacement policies and which makes caching decisions on all candidate sites in a coordinated fashion. In our scheme, cache status information along the routing path of a request is used in dynamically determining where to cache the requested object and what to replace if there is not enough space. The object placement problem is formulated as an optimization problem and the optimal locations to cache the object are obtained using a low-cost dynamic programming algorithm. Extensive simulation experiments have been performed to evaluate the proposed scheme in terms of a wide range of performance metrics. The results show that the proposed scheme significantly outperforms existing algorithms which consider either object placement or replacement at individual caches only. <s> BIB001 </s> A Survey on Content Placement Algorithms for Cloud-Based Content Delivery Networks <s> A. PULL-BASED CONTENT PLACEMENT IN CCDNs <s> Transparent data replication has been considered a promising technique for improving system performance for a large distributed network. In this paper, a hybrid transparent replication model is presented. We address the problems of replication proxy placement in the network and data replica placement on the installed proxies given that a maximum of M proxies are allowed. Both reads and writes are considered in these problems. The performance objective is to minimize the total data transfer cost. To address the placement problems, we first present the optimal solutions for a single object in a tree network without/with constraint on the number of replicas. Based on that, two schemes, namely, aggregate access (AGGA) and weighted popularity (WPOP), are proposed for the replication proxy placement problem. An optimal solution is described for the replica placement problem. The performance of the proposed placement schemes is evaluated with a set of carefully designed simulation experiments over a wide range of system parameters. The results give us several helpful intuitions in deploying transparent replication proxies in a practical system. <s> BIB002 </s> A Survey on Content Placement Algorithms for Cloud-Based Content Delivery Networks <s> A. PULL-BASED CONTENT PLACEMENT IN CCDNs <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> BIB003 </s> A Survey on Content Placement Algorithms for Cloud-Based Content Delivery Networks <s> A. PULL-BASED CONTENT PLACEMENT IN CCDNs <s> How documents of a Web site are replicated and where they are placed among the server nodes have an important bearing on balance of load in a geographically distributed Web server (DWS) system. The traffic generated due to movements of documents at runtime could also affect the performance of the DWS system. In this paper, we prove that minimizing such traffic is NP-hard. We propose a new document distribution scheme that periodically performs partial replication of a site's documents at selected server locations to maintain load balancing. Several approximation algorithms are used in it to minimize traffic generated. The simulation results show that this scheme can achieve better load balancing than a dynamic scheme, while the internal traffic it causes has a negligible effect on the system's performance. <s> BIB004 </s> A Survey on Content Placement Algorithms for Cloud-Based Content Delivery Networks <s> A. PULL-BASED CONTENT PLACEMENT IN CCDNs <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> BIB005 </s> A Survey on Content Placement Algorithms for Cloud-Based Content Delivery Networks <s> A. PULL-BASED CONTENT PLACEMENT IN CCDNs <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> BIB006 </s> A Survey on Content Placement Algorithms for Cloud-Based Content Delivery Networks <s> A. PULL-BASED CONTENT PLACEMENT IN CCDNs <s> Expiration-based consistency management is widely used to keep replicated contents up-to-date in the Internet. The effectiveness of replication can be characterized by the communication costs of client accesses and consistency management. Both costs depend on the locations of the replicas. This paper investigates the problem of placing replicas in a network where replica consistency is managed by the expiration-based scheme. Our objective is to minimize the total cost of client accesses and consistency management. By analyzing the communication cost of recursive validations for cascaded replicas, we prove that in the optimal placement scheme, the nodes not assigned replicas induce a connected subgraph that includes the origin server. Our results are generic in that they apply to any request arrival patterns. Based on the analysis, an O(D)-time algorithm is proposed to compute the optimal placement of the replicas, where D is the sum of the number of descendants over all nodes in the routing tree <s> BIB007 </s> A Survey on Content Placement Algorithms for Cloud-Based Content Delivery Networks <s> A. PULL-BASED CONTENT PLACEMENT IN CCDNs <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> BIB008 </s> A Survey on Content Placement Algorithms for Cloud-Based Content Delivery Networks <s> A. PULL-BASED CONTENT PLACEMENT IN CCDNs <s> Geographically replicating popular objects in the Internet speeds up content distribution at the cost of keeping the replicas consistent and up-to-date. The overall effectiveness of replication can be measured by the total communication cost consisting of client accesses and consistency management, both of which depend on the locations of the replicas. This paper investigates the problem of placing replicas under the widely used TTL-based consistency scheme. A polynomial-time algorithm is proposed to compute the optimal placement of a given number of replicas in a network. The new replica placement scheme is compared, using real Internet topologies and Web traces, against two existing approaches which do not consider consistency management or assume invalidation-based consistency scheme. The factors affecting their performance are identified and discussed <s> BIB009 </s> A Survey on Content Placement Algorithms for Cloud-Based Content Delivery Networks <s> A. PULL-BASED CONTENT PLACEMENT IN CCDNs <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> BIB010 </s> A Survey on Content Placement Algorithms for Cloud-Based Content Delivery Networks <s> A. PULL-BASED CONTENT PLACEMENT IN CCDNs <s> The exploding HD video streaming traffic calls for deploying content servers deeper inside network operators' infrastructures. Telco-CDN are new content distribution services that are managed by Internet Service Providers (ISP). Since the network operator controls both the infrastructure and the content delivery overlay, it is in a position to engineer telco-CDN so that networking resources are optimally utilized. In this paper, we show the following two findings: 1. it is possible to implement an efficient algorithm for the placement of video chunks into a telco-CDN. We present an algorithm, which is based on a genetic algorithm implemented on the MapReduce framework. We show that, for a national VoD service, computing a quasi-optimal placement is possible. 2. such push strategy makes sense because it allows to actually take into account fine-grain traffic management strategies on the underlying infrastructure. Our proposal re-opens the debate about the relevance of such "push" approach (where the manager of telco-CDN proactively pushes video content into servers) versus the traditional caching approach (where the content is pulled to the servers from requests of clients). Our proposal of a quasi-optimal tracker enables fair comparisons between both approaches for most traffic engineering policies. We illustrate the interest of our proposal in the context of a major European Telco-CDN with real traces from a popular Video-on-Demand (VoD) service. Our experimental results show that, given a perfect algorithm for predicting user preferences, our placement algorithm is able to keep aligned with LRU caching in terms of the traditional hit-ratio, but the workload on some troubled links (e.g., over-used links) in a push-based strategy is significantly alleviated. <s> BIB011 </s> A Survey on Content Placement Algorithms for Cloud-Based Content Delivery Networks <s> A. PULL-BASED CONTENT PLACEMENT IN CCDNs <s> Caching is frequently used by Internet Service Providers as a viable technique to reduce the latency perceived by end users, while jointly offloading network traffic. While the cache hit-ratio is generally considered in the literature as the dominant performance metric for such type of systems, in this paper we argue that a critical missing piece has so far been neglected. Adopting a radically different perspective, in this paper we explicitly account for the cost of content retrieval, i.e. the cost associated to the external bandwidth needed by an ISP to retrieve the contents requested by its customers. Interestingly, we discover that classical cache provisioning techniques that maximize cache efficiency (i.e., the hit-ratio), lead to suboptimal solutions with higher overall cost. To show this mismatch, we propose two optimization models that either minimize the overall costs or maximize the hit-ratio, jointly providing cache sizing, object placement and path selection. We formulate a polynomial-time greedy algorithm to solve the two problems and analytically prove its optimality. We provide numerical results and show that significant cost savings are attainable via a cost-aware design. <s> BIB012 </s> A Survey on Content Placement Algorithms for Cloud-Based Content Delivery Networks <s> A. PULL-BASED CONTENT PLACEMENT IN CCDNs <s> Geographically distributed cloud platforms enable an attractive approach to large-scale content delivery. Storage at various sites can be dynamically acquired from (and released back to) the cloud ... <s> BIB013 </s> A Survey on Content Placement Algorithms for Cloud-Based Content Delivery Networks <s> A. PULL-BASED CONTENT PLACEMENT IN CCDNs <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> BIB014 </s> A Survey on Content Placement Algorithms for Cloud-Based Content Delivery Networks <s> A. PULL-BASED CONTENT PLACEMENT IN CCDNs <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> BIB015
Caching is a popular pull-based technique for increasing content availability and reducing content access latency. It is widely employed in a wide range of applications, such as document and data replication. It is the reactive pull-based CP in CCDNs and fetches content on-demand. Since surrogate servers have limited resources, with respect to the size of the catalogue, they must be optimally utilized. Commonly, cache replacement algorithms dictate content and the order in which content should be purged from surrogate servers to make space for new content. The components of pull-based CP algorithms are shown in Fig. 15 . Generally, caching can be decomposed into en-route caching, hierarchical caching BIB008 and their hybrid. In en-route caching, end-user requests are served by the first surrogate server that contains content, in the path from the end-user to the origin server. However, in hierarchical caching, the requests are propagated along the hierarchical levels until it can be satisfied. En-route caching in traditional CDNs has been shown to solve the set of replica-blind CP problems in polynomial time BIB001 . The algorithm implementations range from k-optimization BIB001 and dynamic programming BIB001 to mincost flow problem  -to mention a few. CP algorithms using en-route caching strategies can be extended to include robustness for QoS, surrogate server capacity and content consistency ( BIB005 , BIB007 , BIB009 ). Hierarchical caching for CP organizes surrogates into internal and core surrogate servers BIB012 for jointly minimizing the cost of content access and maximizing the hits. Evidently, a hybrid between enroute BIB002 and hierarchical caching is often explored in CP to increase content availability and reduce content access times BIB008 . Cooperative caching for CP includes placement, searching and consistency management  . Traditional cooperative caching for CP updates content when a miss generates a request for content with higher utility value than any other content BIB014 . A utility value is associated with content to denote its demand on the surrogate server while other caching algorithms assume equal utility values for all content. Generally, traditional commercial CDNs employ caching for CP with LRU cache replacement BIB008 due to its simplicity and ease of implementation and maintenance. Similarly, pull-based caching for CP in CCDNs BIB013 devise a cache with a TTL-based cache replacement policy. The pull-based caching accounts for elastic resources in CCDNs and jointly optimizes operational cost and content miss. The TTL cache replacement policy purges content if it is not accessed within a fixed, predetermined period of time. The content delivery costs include the cost of leasing bandwidth resources in the cloud for content retrieval and the cost of storing content on surrogate servers that pull content on a miss. Therefore, requests cannot be redirected as per traditional en-route or hierarchical caching techniques since they would incur additional operational costs. Naively, if end-user requests are redirected just to minimize the content delivery costs to the nearest surrogate server, which may or may not have content, it will increase the cost of content delivery as there is cost associated with redirection, content retrieval and content storage on the redirected surrogate server. However, if requests were redirected in a topskewed scheme BIB013 , to the surrogates that have the highest request rates and lowest content delivery costs, then there is a high probability that it will yield a hit since content may be already stored there. Otherwise, since this is a surrogate server that serves a high number of requests, there is a higher probability that even if content is not already there, the pulled content will yield future cache hits. Since caching algorithms are on-demand, they are intrinsically dynamic in resource provisioning BIB013 . Recently, caching with mixed cache replacement strategies BIB015 have been devised to accommodate for dynamic popularity based on a short window of observation and the different characteristics of videos in different categories. The considered categories are News, Sports, Movies, TV or Music. Video content from these categories are assigned a probability p for discarding the videos based on the category and age of content. For example, videos in News category are age sensitive so they have a high probability of eviction from the surrogate in the event of a miss and there is a need to replace content on surrogate. In the academic realm, there has always been a continuous struggle to justify pull-or push-based CP for content delivery BIB011 . However, a simple caching technique with LRU technique outperforms various push-based CP algorithms, when the update period is delayed BIB003 . But caching can only increase the maximum hit ratio by 40-50% BIB004 . In short, caching is an online, distributed, greedy, local variant of pushbased CP algorithms BIB010 , which purges content faster than push-based CP algorithms BIB006 .