A Survey on Content Placement Algorithms for Cloud-Based Content Delivery Networks <s> B. PUSH-BASED CONTENT PLACEMENT IN CCDNs <s> Since user demand for a Video-on-demand (VoD) service varies with time in one-day period, provisioning self-owned servers for the peak load it must sustain a few hours per day leads to bandwidth underutilization at other times. Content clouds, e.g. Amazon Cloud Front and Azure CDN, let VoD providers pay by bytes for bandwidth resources, potentially leading to cost savings even if the unit rate to rent a machine from a cloud provider is higher than the rate to own one. In this paper, based on long-term traces from two large-scale VoD systems and temporal development model of content clouds, we tackle challenges, design and potential benefits in migrating VoD services into the hybrid cloud-assisted deployment, where the user requests are partly served by the self-owned servers and partly served by the cloud. Our measurements show that the popularity of the most popular videos decays so quickly, for example, by 11% after one hour that it poses large challenges on updating videos in the cloud. However, the trace-driven evaluations show that our proposed migration strategies (active, reactive and smart strategies), although simply based on the current information, can make the hybrid cloud-assisted VoD deployment save up to 30% bandwidth expense compared with the Clients/Server mode. They can also handle unpredicted the flash crowd traffic with little cost. It also shows that the cloud price and server bandwidth chosen play the most important roles in saving cost, while the cloud storage size and cloud content update strategy play the key roles in the user experience improvement. <s> BIB001 </s> A Survey on Content Placement Algorithms for Cloud-Based Content Delivery Networks <s> B. PUSH-BASED CONTENT PLACEMENT IN CCDNs <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> BIB002 </s> A Survey on Content Placement Algorithms for Cloud-Based Content Delivery Networks <s> B. PUSH-BASED CONTENT PLACEMENT IN CCDNs <s> Delivering on-demand web content to end-users in order to carry out strict QoS metrics is not a trivial task for globally distributed network providers. This task becomes still harder when content popularity varies over the time and the SLA definitions have to include both transfer rate and latency metrics. Current worldwide content delivery approaches and datacenter infrastructures rely on cumbersome replication schemes that are agnostic to edge-network resources, and damage content provision. In this work we present AREN, an novel replication scheme for cloud storage on edge networks. AREN relies on a collaborative cache strategy and bandwidth reservation to adapt the replication degree according to strict SLA contracts and content popularity growth. We have evaluated the performances of replication schemes on edge networks using Caju, a content distribution system for edge networks. Compared to a non-collaborative caching, evaluations show that AREN prevents nearly 99.8% of all SLA violations when the storage system is heavily loaded. We also show that AREN provides a sevenfold decrease in the amount of storage usage for replicas, and it increases by roughly 20% the aggregate bandwidth, hence accelerating content delivery. <s> BIB003 </s> A Survey on Content Placement Algorithms for Cloud-Based Content Delivery Networks <s> B. PUSH-BASED CONTENT PLACEMENT IN CCDNs <s> In recent years, companies such as eBay, Facebook, Google, Microsoft, and Yahoo! have made large investments in massive data centers supporting cloud services. These data centers are becoming the hosting platform for a wide spectrum of composite applications with an increasing trend towards more communication intensive applications. As a result, the bandwidth requirements within and between data centers is rapidly growing, and the efficient management of these networking resources is becoming a key ingredient in the ability to offer cost effective cloud services. Replica placement is a specific aspect of cloud management where the goal is to optimally place the applications and their related data over the available cloud infrastructure. The problem is inherently complex since data is continuously updated, and the cost associated with this update increases with the number of data replica and the network distance between them. We model this problem as a soft-capacitated connected facility location problem, which is NP-Hard in the general case. We present the first deterministic constant approximation algorithm for this problem and show, using extensive simulations and realistic data center and network topology, that our algorithm provides practically good placement decisions. <s> BIB004 </s> A Survey on Content Placement Algorithms for Cloud-Based Content Delivery Networks <s> B. PUSH-BASED CONTENT PLACEMENT IN CCDNs <s> In recent years, technical challenges are emerging on how to efficiently distribute the rapid growing user-generated contents (UGCs) with long-tailed nature. To address this issue, we have previously proposed cloud centric media network (CCMN) for cost-efficient UGCs delivery. In this paper, we further study the content placement problem in CCMN. Our objective is to minimize the monetary cost incurred by using cloud resources to orchestrate an elastic and global content delivery network (CDN) service. In particular, this objective is achieved via a two-step method. First, for a single content, we map it into a k-center problem, and find a logarithmic relationship between the mean hop distance from users to contents, and the reciprocal of replica number. Second, for multiple contents, we formulate a convex optimization with storage and bandwidth capacity constraints, which can be solved by our proposed algorithm. Finally, we verify the algorithm based on real-world traces collected from a popular video website in China. Our numerical results suggest that, the optimal number of replica for each content follows a power law in respect to its popularity, under feasible storage and bandwidth constraints, in a set of deployed backbone networks. <s> BIB005 </s> A Survey on Content Placement Algorithms for Cloud-Based Content Delivery Networks <s> B. PUSH-BASED CONTENT PLACEMENT IN CCDNs <s> Cloud-oriented content delivery networks (CCDNs) constitute a promising alternative to traditional content delivery networks. Exploiting the advantages and principles of the cloud, such as the pay as you go business model and geographical dispersion of resources, CCDN can provide a viable and cost-effective solution for realizing content delivery networks and services. In this paper, a hierarchical framework is proposed and evaluated toward an efficient and scalable solution of content distribution over a multiprovider networked cloud environment, where inter and intra cloud communication resources are simultaneously considered along with traditional cloud computing resources. To efficiently deal with the CCDN deployment problem in this emerging and challenging computing paradigm, the problem is decomposed to graph partitioning and replica placement problems while appropriate cost models are introduced/adapted. Novel approaches on the replica placement problem within the cloud are proposed while the limitations of the physical substrate are taken into consideration. The performance of the proposed hierarchical CCDN framework is assessed via modeling and simulation, while appropriate metrics are defined/adopted associated with and reflecting the interests of the different identified involved key players. <s> BIB006 </s> A Survey on Content Placement Algorithms for Cloud-Based Content Delivery Networks <s> B. PUSH-BASED CONTENT PLACEMENT IN CCDNs <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. PUSH-BASED CONTENT PLACEMENT IN CCDNs <s> Content Placement (CP) problem in Cloud-based Content Delivery Networks (CCDNs) leverage resource elasticity to build cost effective CDNs that guarantee QoS. In this paper, we present our novel CP model, which optimally places content on surrogates in the cloud, to achieve (a) minimum cost of leasing storage and bandwidth resources for data coming into and going out of the cloud zones and regions, (b) guarantee Service Level Agreement (SLA), and (c) minimize degree of QoS violations. The CP problem is NP-Hard, hence we design a unique push-based heuristic, called Weighted Social Network Analysis (W-SNA) for CCDN providers. W-SNA is based on Betweeness Centrality (BC) from SNA and prioritizes surrogates based on their relationship to the other vertices in the network graph. To achieve our unique objectives, we further prioritize surrogates based on weights derived from storage cost and content requests. We compare our heuristic to current state of the art Greedy Site (GS) and purely Social Network Analysis (SNA) heuristics, which are relevant to our work. We show that W-SNA outperforms GS and SNA in minimizing cost and QoS. Moreover, W-SNA guarantees SLA but also minimizes the degree of QoS violations. To the best of our knowledge, this is the first model and heuristic of its kind, which is timely and gives a fundamental pre-allocation scheme for future online and dynamic resource provision for CCDNs. <s> BIB008 </s> A Survey on Content Placement Algorithms for Cloud-Based Content Delivery Networks <s> B. PUSH-BASED CONTENT PLACEMENT IN CCDNs <s> The increasing popularity of online social networks (OSNs) has been transforming the dissemination pattern of social video contents. Considering the unique features of social videos, e.g., huge volume, long-tailed, and short length, how to utilize the information propagation pattern to improve the efficiency of content distribution for social videos attracts more and more attention. In this paper, we first conduct a large scale measurement to explore the social video viewing behavior under the community classification. Based on the measurement, we investigate the community driven sharing video distribution problem under the cloud-centric content delivery network (CDN) architecture. In particular, we formulate it as a constrained optimization problem with the objective to minimize the operational cost. The constraint is the averaged transmission delay. Following that, we propose a dynamic algorithm to seek the optimal solution. Our trace-driven experiments further demonstrate our algorithm can make a better tradeoff between monetary cost and QoS, and outperforms the traditional method with less operational cost while satisfying the QoS requirement. <s> BIB009 </s> A Survey on Content Placement Algorithms for Cloud-Based Content Delivery Networks <s> B. PUSH-BASED CONTENT PLACEMENT IN CCDNs <s> Content distribution networks (CDNs) built on Clouds have recently started to emerge. Compared to conventional CDNs, Cloud-based CDNs have the benefit of cost efficient hosting services without owning infrastructure. However, resource provisioning and replica placement in cloud CDNs involve a number of challenging issues, mainly due to the dynamic nature of demand patterns. To deal with this dynamic nature, this paper proposes a set of novel algorithms to solve the joint problem of resource provisioning and caching (i.e., replica placement) for cloud-based CDNs with an emphasis on handling the dynamic demand patterns. Firstly, we propose a provisioning and caching algorithm framework called Differential Provisioning and Caching (DPC) algorithm, which aims to rent cloud resources to build CDNs and whereby to cache contents so that the total rental cost can be minimized while all demands are served. DPC operates in 2 steps to maximize total demands and to minimize the total rental cost for new resources to serve all remaining demands. For each step of DPC, we design both greedy and iterative heuristics, each with different advantages over the existing approaches. Moreover, to dynamically adjusts the placement of contents and route maps, we further propose the Caching and Request Balancing (CRB) algorithm, which is light-weight and thus can be frequently executed as a companion of DPC to maximize the total demands. Performance evaluation results are presented to demonstrate the effectiveness and competitiveness of our approaches when compared to existing algorithms. <s> BIB010 </s> A Survey on Content Placement Algorithms for Cloud-Based Content Delivery Networks <s> B. PUSH-BASED CONTENT PLACEMENT IN CCDNs <s> Cloud service provisioning on top of virtual infrastructures is of major importance in modern ICT, since it is directly correlated to the way business models are designed and revenue is generated from the cloud service providers. In this work we examine an end-to-end content replication problem over cloud-based multi-technology infrastructures. We extend the classical model where every network node is a potential replica carrier and the link weights represent hops/delay and we examine replication schemes for content that a) is requested by customers belonging in different virtual networks and b) depending on the requester there is different impact on the system operational cost. We examine both centralized and distributed content replication management policies and we evaluate their performance through extended simulations, by means of total cost, the number of object replacements and the number of iterations required. © 2014 IEEE. <s> BIB011 </s> A Survey on Content Placement Algorithms for Cloud-Based Content Delivery Networks <s> B. PUSH-BASED CONTENT PLACEMENT IN CCDNs <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> BIB012
In the context of push-based content delivery algorithms, the first major step is the assignment of end-users to surrogates that meet their requests, while minimizing cost and maximizing QoS. There is a prerequisite to this assignment, which is the mapping stage when end-users' requests are mapped to the surrogates in CCDN by a request redirector based on geographic locations or for load balancing. Typically, it is assumed in push-based CP algorithms that the mapping is arbitrary and a set of surrogate servers with a set of end-users are the input to the push-based content delivery algorithm. The end-user requests are estimated and content access patterns are predicted BIB007 based on prediction models. The surrogate locations are either arbitrary or based on the datacenter locations of large-scale cloud infrastructure providers BIB008 . An approach to the end-user, surrogate assignment problem is to model it as the re-known Facility Location (FL) problem BIB004 . Steiner tree approximation BIB004 can be applied to the end-user, surrogate assignment problem to achieve solutions within a constant factor from the optimal. On the other hand, when the end-user, surrogate assignment problem is modeled as the knapsack problem BIB007 , it eventually begins with the prioritization of surrogate servers. The prioritization is achieved based on the benefit of the surrogate to the entire CCDN, the perceived QoS of the end-users or per-unit weight-based algorithms. Algorithms that consider the selection of surrogate servers in CCDN are prioritized based on their benefit of reducing network traffic and latency BIB007 . Uniquely, surrogate servers cooperate to prioritize and store content that minimizes operational cost but maximizes content stored in each level of hierarchy in CCDN, which is organized in tiers based on the inherent technology domains BIB005 . The components of pushbased CP algorithms are shown in Fig. 16 . In QoS-based surrogate server prioritization techniques ( BIB002 , BIB005 , BIB009 , BIB006 ), end-users are assigned to surrogate servers such that all end-users are within a QoS distance of the surrogates and their content. The QoS distance can be based on hop-count, delay or geodesic distance BIB006 . In per-unit weight-based surrogate prioritization techniques, bandwidth-storage ratio (  , BIB010 ) prioritizes surrogate servers such that the cost of storing and delivering content is optimized. The weighted shortest path metrics BIB008 are often used to prioritize the surrogates that offer the lowest content delivery cost and the best QoS such that the surrogate is on the shortest path based on betweenness centrality (BC). The BC metric prioritizes surrogates such that the surrogate with the largest number of shortest paths passing through it with the lowest storage and bandwidth costs has the highest priority. Typically, the end-user, surrogate server assignment problem is tackled by prioritizing surrogates. However, end-users can be clustered based on geodesic distances, complex OSN relationships and similarity preferences in content BIB009 to implement CP algorithms that are meticulously designed to account for end-user behavior and OSN relationships. The push-based CP algorithms that terminate after end-user, surrogate server assignment are static pre-allocation algorithms ( BIB005 , BIB006 , BIB008 ), executed for a static snapshot of time. The push-based CP algorithm using convex optimization with Topkis-Veinott's feasible direction algorithm BIB005 minimizes the cost of storage and bandwidth in terms of the mean hop distance between end-users and content. Meanwhile, greedy heuristics ( BIB006 , BIB008 ) have been designed to implement end-user, surrogate assignment inspired from the shortest path betweenness centrality (SPBC). Realistically, there is a discrepancy between the estimated/predicted and real end-user requests since the predicted end-user requests is only as good as the prediction model. The difference depends on the accuracy of the estimation and/or prediction models. Dynamic push-based CP algorithms are pre-allocation algorithms followed by a dynamic adaptation phase that is executed online during live end-user requests. Dynamic push-based CP algorithms can adapt to changes in end-user requests or content access patterns by either re-provisioning the resources (  , BIB009 ) or re-routing the end-user requests from busy surrogate servers to underutilized surrogates BIB010 . Alternatively, push-based CP algorithms can also dynamically update the content placed on the surrogate servers BIB002 , while incurring minimum operational cost, if end-user requests are violating QoS. Generally, centralized knowledge is necessary for enduser surrogate server assignment. However, distributed pushbased CP algorithms ( BIB007 , BIB011 ) have been devised for resilient CP in CCDNs. Moreover, hybrid push-pull CP algorithm BIB007 for CCDNs has also been employed to minimize operational cost, maximize QoS and dynamically adapt to the changing end-user requests, leveraging the benefits of pull-and push-based CP. Meanwhile, hybrid approaches ( BIB001 , BIB003 ) are being investigated to offload content from the origin server(s) to CCDNs, only when the original traditional CDN capacity is exceeded. However, this does not account for a long-term effect on operational cost or on leasing and re-leasing resources when content is pushed to the cloud, with respect to frequently changing end-user demands. In TABLE 4 , we evaluate the CP algorithms for CCDNs against the well-motivated design criteria based on content and the cloud model. It is evident that, though the content characteristics are intrinsic to CP algorithms and impact their VOLUME 6, 2018 efficiency  , it is often overlooked in the design of CP algorithms. Furthermore, temporal, spatial and OSN relationships affect content access patterns, which are rarely included in CP models and algorithms. Hu et al. BIB012 , BIB009 use OSN relationships to classify end-users into similar groups and achieve 30% improvement in performance of CP algorithm. This is the evidence that content characteristics should be included in the design of CP algorithms for CCDNs.