A Survey on Content Placement Algorithms for Cloud-Based Content Delivery Networks <s> C. PROBLEM SOLVING APPROACH <s> Studies the cache performance in a remote caching architecture. The authors develop a set of distributed object replication policies that are designed to implement different optimization goals. Each site is responsible for local cache decisions, and modifies cache contents in response to decisions made by other sites. The authors use the optimal and greedy policies as upper and lower bounds, respectively, for performance in this environment. Critical system parameters are identified, and their effect on system performance studied. Performance of the distributed algorithms is found to be close to optimal, while that of the greedy algorithms is far from optimal. > <s> BIB001 </s> A Survey on Content Placement Algorithms for Cloud-Based Content Delivery Networks <s> C. PROBLEM SOLVING APPROACH <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> BIB002 </s> A Survey on Content Placement Algorithms for Cloud-Based Content Delivery Networks <s> C. PROBLEM SOLVING APPROACH <s> This paper studies the optimal placement of web files for en-route web caching. It is shown that existing placement policies are all solving restricted partial problems of the file placement problem, and therefore give only sub-optimal solutions. A dynamic programming algorithm of low complexity which computes the optimal solution is presented. It is shown both analytically and experimentally that the file-placement solution output by our algorithm outperforms existing en-route caching policies. The optimal placement of web files can be implemented with a reasonable level of cache coordination and management overhead for en-route caching; and importantly, it can be achieved with or without using data prefetching. <s> BIB003 </s> A Survey on Content Placement Algorithms for Cloud-Based Content Delivery Networks <s> C. PROBLEM SOLVING APPROACH <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> C. PROBLEM SOLVING APPROACH <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> C. PROBLEM SOLVING APPROACH <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> BIB006 </s> A Survey on Content Placement Algorithms for Cloud-Based Content Delivery Networks <s> C. PROBLEM SOLVING APPROACH <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> BIB007 </s> A Survey on Content Placement Algorithms for Cloud-Based Content Delivery Networks <s> C. PROBLEM SOLVING APPROACH <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> BIB008 </s> A Survey on Content Placement Algorithms for Cloud-Based Content Delivery Networks <s> C. PROBLEM SOLVING APPROACH <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
The content placement problem is defined as an optimization problem. In CCDNs, dynamic programming  , convex programming BIB007 , Lyapunov optimization BIB009 and Topkis-Veinott's feasible direction algorithm BIB007 have been used to produce local and global optimal results. Traditional CP problems in CDNs, as decision problems, are thoroughly investigated (  , BIB001 , BIB004 , BIB005 - BIB003 ). They can be classified into replica-aware and replica-blind BIB005 CP problems, based on surrogates knowledge of the location of the copies, i.e. the replicas of content. The set of replicablind CP problems are polynomial BIB005 . However, generic traditional CP problems have been successfully mapped to known NP-Complete and NP-Hard problems, such as facility location, knapsack and k-median ( BIB004 , BIB002 ,  ,  ). Similarly, modeling of CP variants belonging to NP-Complete (NP-C) BIB008 and NP-Hard (NP-H) BIB006 has been studied in CCDNs. Therefore, no polynomial time solution exists and hence, efficient heuristics have to be devised for large-scale and practical CP problems However, each step delineated in Fig. 2 is in itself an active area of research and poses numerous research challenges. We will see that the efficiency of content placement algorithms is inherently dependent on content, its intrinsic properties and relationships and the cost model of the underlying infrastructure.