A Survey on Content Placement Algorithms for Cloud-Based Content Delivery Networks <s> D. FORMAL MODELING <s> The delivery of large files to individual users, such as video on demand or application programs to the envisioned network computers is expected by many to be one of the main tasks of broadband communication networks. This requires high bandwidth capacity as well as fast and dense storage servers. This motivates multimedia service providers to optimize the delivery network, as well as the electronic content allocation.A hierarchical architecture for the distribution of multimedia content was introduced by Nussbaumer, Patel, Schaffa, and Sterbenz (INFOCOM 94). They addressed the trade-off between bandwidth and storage requirements that results from the placement of the content servers in the hierarchy tree. They presented a centralized algorithm to compute the best level of the hierarchy for the server location to minimize the combined cost of communication and storage.In this work we solve a general case where servers can be placed at different levels of the hierarchy. We develop a distributed optimal location algorithm that requires small nodal memory capacity and computational power. Previous results for related problems for caching system design are of higher complexity. Previous results for related classic operations research problems are limited to centralized algorithms, based on linear programming, that are not easy to convert into distributed algorithms. Instead, to obtain our results, we observed that the use of dynamic programming naturally lends itself to a distributed implementation.For the specific problem at hand, we also managed to find a natural function (a generalization of the problem) that simplifies the combination operation used in the design of a dynamic program. <s> BIB001 </s> A Survey on Content Placement Algorithms for Cloud-Based Content Delivery Networks <s> D. FORMAL MODELING <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> BIB002 </s> A Survey on Content Placement Algorithms for Cloud-Based Content Delivery Networks <s> D. FORMAL MODELING <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> BIB003 </s> A Survey on Content Placement Algorithms for Cloud-Based Content Delivery Networks <s> D. FORMAL MODELING <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> BIB004 </s> A Survey on Content Placement Algorithms for Cloud-Based Content Delivery Networks <s> D. FORMAL MODELING <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> BIB005 </s> A Survey on Content Placement Algorithms for Cloud-Based Content Delivery Networks <s> D. FORMAL MODELING <s> Vehicular Ad-Hoc Network (VANET) applications usually require some kind of content to be delivered to vehicles. However, this task is easier said than done because of the VANET's specific characteristics, such as highly dynamic topology, short intermittent contacts, different density scenarios, and large-scale, to name a few. Thus, one concept that seems to be of great help is that of Content Delivery Network (CDN), in which strategically nodes are selected to act as servers and to help on the delivery process. Some researchers have started working on the application of such concept to VANET scenarios. In this paper, we present the state-of-the-art survey on the vehicular content delivery network (VCDN) field by presenting and discussing the main related studies found in the literature. <s> BIB006 </s> A Survey on Content Placement Algorithms for Cloud-Based Content Delivery Networks <s> D. FORMAL MODELING <s> We propose a novel roadside unit (RSU) cloud, a vehicular cloud, as the operational backbone of the vehicle grid in the Internet of Vehicles (IoV). The architecture of the proposed RSU cloud consists of traditional and specialized RSUs employing software-defined networking (SDN) to dynamically instantiate, replicate, and/or migrate services. We leverage the deep programmability of SDN to dynamically reconfigure the services hosted in the network and their data forwarding information to efficiently serve the underlying demand from the vehicle grid. We then present a detailed reconfiguration overhead analysis to reduce reconfigurations, which are costly for service providers. We use the reconfiguration cost analysis to design and formulate an integer linear programming (ILP) problem to model our novel RSU cloud resource management (CRM). We begin by solving for the Pareto optimal frontier (POF) of nondominated solutions, such that each solution is a configuration that minimizes either the number of service instances or the RSU cloud infrastructure delay, for a given average demand. Then, we design an efficient heuristic to minimize the reconfiguration costs. A fundamental contribution of our heuristic approach is the use of reinforcement learning to select configurations that minimize reconfiguration costs in the network over the long term. We perform reconfiguration cost analysis and compare the results of our CRM formulation and heuristic. We also show the reduction in reconfiguration costs when using reinforcement learning in comparison to a myopic approach. We show significant improvement in the reconfigurations costs and infrastructure delay when compared to purist service installations. <s> BIB007
The CP optimization problem has multiple objectives with various competing utility or cost functions. Generally, smaller CP optimization problems are addressed, incorporating only some of the cost functions. Typically, the different cost functions are broadly classified into latency minimization, operational cost minimization or joint minimization of latency and operational cost. In latency minimization, the objective is to reduce the backbone network traffic, i.e. the traffic between the surrogates and origin server(s). Latency minimization problems include, but are not limited to, objectives that minimize distance and/or traffic between the end-users and the surrogates. Distance metrics can simply be the geodesic distance, Euclidean distance based on network topology, hop counts or complex distance metrics that account for network propagation, queuing, processing and transmission delays. Network traffic is induced between the surrogate servers and the origin server(s) for content retrieval, replication, updates, and/or consistency. The minimization of distance or traffic between the surrogates and origin server(s) explicitly places more content on the surrogates and implicitly improves QoS, with respect to the end-user perceived latency. Generally, a distance metric is used to conjure the end-user perceived latency ( BIB004 , BIB005 ). However, network conditions are also used for the end-user perceived latency, such as traffic volume and round trip times (RTT). Operational cost minimization objectives pertain to the cost of storage, cost of network bandwidth and cost of processing BIB001 , if applicable. The cost of using network bandwidth is attributed to delivering content to end-users, retrieving content from origin server(s) or other surrogates to meet end-user requests, updating content, replicating content and/or maintaining consistency among the copies of content BIB002 . The cost of processing is included to accommodate for computational resources used in the cloud to compute or execute algorithms for content management. Operational cost minimization guarantees optimal cost for CCDN operations, while latency minimization guarantees QoS for end-users. Therefore, these are competing objectives that are not mutually exclusive. For example, the cost of using bandwidth in the network is proportional to the traffic induced into the network for content access or retrieval. So, bandwidth utilization is important in CP models such that it does not congest network backbone with CCDN traffic. In such cases, these two objectives work together. These objectives can be modeled independently or jointly from different perspectives. For instance, from the perspective of VoD and online gaming content providers, content must prioritize latency and consistency, respectively. Fig. 4 illustrates the various utility functions for the CP problem that can be included as the objectives for latency minimization and/or operational cost minimization. Many times, minimization functions can be modeled as maximization functions. For instance, minimizing latency can be modeled as maximizing traffic between the end-users and surrogate servers in close proximity to the end-users. General utility functions, such as content access or bandwidth and storage cost, are essential for cost and latency minimization objectives. However, where multiple copies, i.e. the replicas, of content are globally distributed to achieve content availability, it becomes necessary to update content and maintain consistency among the replicas. In this case, either origin server(s) can invalidate content or the surrogate servers can validate content BIB003 for consistency. Since this induces additional bandwidth cost and complexity, it is often not deployed BIB003 . Furthermore, as content evolves to be more interactive and end-user driven, such as UGC, there is a growing need to include consistency management as an objective in content placement in CCDNs. CP models and algorithms rarely account for the state of the underlying network as an objective. However, achieving fault tolerance should be a primary objective. In this case, CP models must maintain content availability, within QoS, in a 'lossy' network, where surrogates and bandwidth could be unavailable due to link failure. Lossy networks are intrinsic characteristics of networks that have intermittent connectivity, such as vehicular clouds BIB007 . They consist of small-scale datacenters incorporated into processing units in vehicles and roadside infrastructures such as traffic lights. The vehicular cloud can offer CCDN services such that end-users can share and retrieve content while on the go BIB006 . Therefore, fault tolerance, content availability and consistency will become major objectives of CP in CCDNs, especially as they are overlay on non-traditional cloud infrastructures and underlying technologies.