A Survey on Content Placement Algorithms for Cloud-Based Content Delivery Networks <s> 2) SOLUTION ANALYSIS AND COMPUTATIONAL COMPLEXITY <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> 2) SOLUTION ANALYSIS AND COMPUTATIONAL COMPLEXITY <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> 2) SOLUTION ANALYSIS AND COMPUTATIONAL COMPLEXITY <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> 2) SOLUTION ANALYSIS AND COMPUTATIONAL COMPLEXITY <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> 2) SOLUTION ANALYSIS AND COMPUTATIONAL COMPLEXITY <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
Tremendous work has been done on studying and classifying traditional CDN CP problems as polynomial, NP, NPC or NP-Hard. Traditional CP problems based on CCDN infrastructure have been successfully mapped onto known NP-Complete and NP-Hard problems such as facility location, knapsack and k-median ( BIB002 ,  ). There are special cases and variants of both the decision and optimization of CP problems that are tractable ( BIB001 , BIB004 , BIB005 - BIB003 ) using treebased BIB004 algorithms or dynamic programming ( BIB005 , BIB003 ). However, unrealistic assumptions, such as surrogate servers have infinite capacity BIB004 or only one level of hierarchy BIB001 , limits their applicability. Interestingly, CP model is polynomial, when the surrogate servers are assumed to be ''replicablind'' BIB005 , i.e. unaware of the location of content replica. In such cases, end-user requests are propagated from one surrogate server to another along the path to the origin, known as en-route caching, to solve the CP problem in polynomial time BIB002 . The CP problem as a min-cost flow problem  is solved optimally in polynomial time while assuming a low rate of updates and a low rate of change in content access patterns. Building such an extensive repository for CP in CCDNs remains a challenge.