Tài liệu Studying and developing a cdn caching algorithm using machine learning

VIETNAM NATIONAL UNIVERSITY HO CHI MINH CITY HO CHI MINH CITY UNIVERSITY OF TECHNOLOGY FALCUTY OF COMPUTER SCIENCE AND ENGINEERING ——————– * ——————— GRADUATION THESIS STUDYING AND DEVELOPING A CDN CACHING ALGORITHM USING MACHINE LEARNING Major: Computer Science Council : Computer Science Instructor: Assoc. Prof. Thoai Nam Reviewer: Dr. Nguyen Le Duy Lai —o0o— Student 1: Tran Trung Quan - 1752044 Student 2: Pham Trong Nhan - 1752394 HO CHI MINH CITY, 08/2021 Acknowledgement We would love to show our deep and honest gratitude to our advisor, Assoc. Prof. Thoai Nam, for his guidance, advice, enthusiasm, and encouragement in helping us research and implement this study. We would like to extend our thanks to two postgraduate students from the High-Performance Computing Lab, Mr. Tran Ngoc Anh Tu and Mr. La Hoang Loc, for their assistance in directing and implementing this research. We would like to thank lecturers in the Faculty of Computer Science and Engineering, Ho Chi Minh City University of Technology, for their enthusiastic transfer of knowledge during the years we studied at the university. We are mindful that this project is still incomplete and involves inevitable mistakes. To further change, we would love to receive feedback from the lecturers. Finally, we wish you health, prosperity, and success on your chosen paths. Declaration Content Delivery Network is not a new concern, but are still a challenge due to the growth of digital content and network infrastructure. Vietnam currently does not have much in-depth research on this subject. There is a lot of knowledge about the study process that is not part of the program at the university level, but we promise that this is our research under the guidance of Assoc. Prof. Thoai Nam. The research content and results are legitimate and have never been published before. The data used for analysis and feedback has been collected by me from several different sources and will be indicated in the reference section. Besides, we have also used some reviews, evaluations, and figures of other authors and organizations. All have citations and annotations. We are entirely responsible for the content of our research. The Ho Chi Minh City University of Technology is not involved in the copyright infringements caused by our research. Contents 1 2 Introduction 1.1 Overview . . . 1.2 Goal . . . . . . 1.3 Scope . . . . . 1.4 Thesis Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Knowledge Base 2.1 Content Delivery Network . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1.2 CDN Taxonomy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1.3 Content Placement . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1.4 Request Routing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1.5 Open Issues in CDNs . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 A Light-weight Content Distribution Scheme for Cooperative Caching in TelcoCDNs [19] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2.1 Approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2.2 Model of Light-weight Content Distribution for Cooperative caching . 2.2.3 Color-based caching scheme’s Evaluation . . . . . . . . . . . . . . . . 2.3 Color-based Cooperative Cache and its Routing Scheme for Telco-CDNs [24] . 2.3.1 Approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3.2 Color Tag Based Cooperative Caching, Color Tags Management Algorithm and Routing Algorithm . . . . . . . . . . . . . . . . . . . . . . 2.3.3 Research Result . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.4 Emulation of the color-based caching scheme in Telco-CDNs with Mininet using real data [29] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.4.1 Analyze CDN real log from SBD Inc. - Workload types . . . . . . . . 2.4.2 Trace-based system analysis . . . . . . . . . . . . . . . . . . . . . . . 2.4.3 Development CDN Emulation Tool . . . . . . . . . . . . . . . . . . . 2.5 Simulated Annealing [32] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.5.1 Local Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.5.2 Basic Simulated Annealing . . . . . . . . . . . . . . . . . . . . . . . . 2.5.3 Mathematical Modeling . . . . . . . . . . . . . . . . . . . . . . . . . 2.5.4 Finding minimal traffic time of color-based cooperative caching in TelcoCDNs by using Simulated Annealing algorithm . . . . . . . . . . . . . 2.6 Bayesian Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.6.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.6.2 Introduction to Bayesian Optimization . . . . . . . . . . . . . . . . . . 2.6.3 Model of the function: Gaussian Processes . . . . . . . . . . . . . . . ii 1 1 2 2 2 3 3 3 3 7 10 11 12 12 13 16 20 20 21 24 25 26 27 29 32 32 33 35 36 39 39 40 41 2.6.4 2.6.5 3 4 5 Choice of kernels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Acquisition functions . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 43 Proposed Solution 3.1 Analysis: Current Problem with Normal Separator Rank Algorithm . . . . . . 3.1.1 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Proposed Solution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2.1 Finding minimal traffic time of color-based cooperative caching in TelcoCDNs by using Bayesian Optimization. . . . . . . . . . . . . . . . . . 46 46 46 47 Evaluation 4.1 First Phase: Evaluation with Simulated Datasets 4.1.1 Setting . . . . . . . . . . . . . . . . . 4.1.2 Experiment 1 . . . . . . . . . . . . . . 4.1.3 Experiment 2 . . . . . . . . . . . . . . 4.1.4 Experiment 3 . . . . . . . . . . . . . . 4.1.5 Experiment 4 . . . . . . . . . . . . . . 4.1.6 Experiment 5 . . . . . . . . . . . . . . 4.1.7 Summary . . . . . . . . . . . . . . . . 4.2 Second Phase: Evaluation with Real Datasets . 4.3 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 54 54 55 57 58 59 60 61 61 64 . . . . . . 66 66 66 66 66 66 67 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Summary 5.1 Achievements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.1.1 Knowledge about CDN system and related problems . . . . . . . 5.1.2 Using Bayesian Optimization to solve the optimization problems . 5.1.3 Achievements in experiences, knowledge, and soft skills . . . . . 5.2 Drawbacks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.3 Future Improvements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 List of Tables 2.1 Example of a record in system log . . . . . . . . . . . . . . . . . . . . . . . . 27 3.1 3.2 Sampling set of different increased rank number . . . . . . . . . . . . . . . . . Number of separator ranks in different sampling sets . . . . . . . . . . . . . . 52 52 4.1 4.2 Setting for evaluating with Simulated Datasets . . . . . . . . . . . . . . . . . . Initial sampling separator ranks . . . . . . . . . . . . . . . . . . . . . . . . . . 54 54 iv List of Figures 2.1 2.2 2.3 2.4 2.5 2.6 2.7 2.8 2.9 2.10 2.11 2.12 2.13 2.14 2.15 2.16 2.17 2.18 2.19 2.20 2.21 2.22 2.23 2.24 2.25 2.26 2.27 2.28 2.29 2.30 2.31 2.32 2.33 2.34 CDN Composition. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . CDN Composition - Relationship. . . . . . . . . . . . . . . . . . . . . . . . . CDN Composition - Interaction Protocols. . . . . . . . . . . . . . . . . . . . . Content Distribution and Management. . . . . . . . . . . . . . . . . . . . . . . Surrogate placement. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Content management subsystem. . . . . . . . . . . . . . . . . . . . . . . . . . End-user to CDN interaction. . . . . . . . . . . . . . . . . . . . . . . . . . . . Utilities for modeling objectives and constraints. . . . . . . . . . . . . . . . . Taxonomy of request-routing mechanisms. . . . . . . . . . . . . . . . . . . . . Example of contents cached in three servers according to their color tags and popularities. [19] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Proposed LFU-LRU Hybrid Cache Architecture. [19] . . . . . . . . . . . . . . Request handling algorithm with proposed hybrid caching scheme. [19] . . . . Server colorization algorithm. [19] . . . . . . . . . . . . . . . . . . . . . . . . Popularity class and corresponding tags with four colors. [19] . . . . . . . . . Unidirectional ring topology with 8 nodes with their corresponding colorations. [19] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2D-mesh topology with two different colorations. [19] . . . . . . . . . . . . . NTT mesh topology in Japan and its coloration. [19] . . . . . . . . . . . . . . Simulation parameters. [19] . . . . . . . . . . . . . . . . . . . . . . . . . . . The number of contents in each popularity class.[19] . . . . . . . . . . . . . . Configurations of the computing host for GA. [19] . . . . . . . . . . . . . . . Comparison of convergence. [19] . . . . . . . . . . . . . . . . . . . . . . . . . Normalized traffic on a ring-based network with 8 nodes.[19] . . . . . . . . . . Normalized traffic on a 2D-mesh network with 25 nodes.[19] . . . . . . . . . . Normalized traffic on the NTT network with 55 nodes.[19] . . . . . . . . . . . Cache hit ratio with a change in the popularity. [19] . . . . . . . . . . . . . . . Separator ranks for each gamma parameter when 1000 contents are classified into five popularity classes. [24] . . . . . . . . . . . . . . . . . . . . . . . . . Iterative calculation for separator ranks algorithm. [24] . . . . . . . . . . . . . Color-based routing that finds the nearest cache server with the requesting colortag. [24] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Structure of the color-tag based cache server. [24] . . . . . . . . . . . . . . . . Color based routing algorithm. [24] . . . . . . . . . . . . . . . . . . . . . . . NTT-like mesh topology and its coloration with four colors. [24] . . . . . . . . Traffic reduction under different routing and caching strategies. [24] . . . . . . Video Streaming workflow [29] . . . . . . . . . . . . . . . . . . . . . . . . . The proportion of number of requests and content size for Multipurpose Internet Mail Extensions [29] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . v 4 5 6 6 7 8 8 9 10 13 14 14 15 16 16 17 17 17 18 18 18 19 19 19 20 21 22 23 23 24 25 25 26 28 2.35 2.36 2.37 2.38 2.39 2.40 2.41 Upper: General hit rate for 3 services, Lower: Sum latency for 3 services. [29] . Components of the tool. [29] . . . . . . . . . . . . . . . . . . . . . . . . . . . The tool’s workflow. [29] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Request-response flow [29] . . . . . . . . . . . . . . . . . . . . . . . . . . . . Number of content was requested in each interval in CDN. . . . . . . . . . . . T min comparison between Simulated Annealing and Original algorithms. . . . T est num run comparison between Simulated Annealing and Original algorithms. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 30 30 31 38 38 Test function of original algorithm with increased rank = 1 . . . . . . . . . . . . Test function of original algorithm with separator rank (Increased rank = 1) . . . Test function of original algorithm with increased rank = 4 . . . . . . . . . . . . 50 51 51 The topology of France CDN network. . . . . . . . . . . . . . . . . . . . . . . Evaluation Bayesian Optimization (BO) method with original method (Sampling set: ”all-rank”, Increased rank = 1) . . . . . . . . . . . . . . . . . . . . . 4.3 Evaluation different initial sampling points of Bayesian Optimization (Sampling set: ”all-rank”, Increased rank = 1) . . . . . . . . . . . . . . . . . . . . . 4.4 Compare three acquisition functions (Sampling set: ”all-rank”, Increased rank = 1, Initial sampling points: 200) . . . . . . . . . . . . . . . . . . . . . . . . . 4.5 Compare two sampling sets ”all-rank” and ”only-sorted” (Increased rank = 1, Initial sampling points: 200) . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.6 Compare different initial sampling points of ”only-sorted” sampling set (Increased rank = 1) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.7 Compare increased rank = 1 and increased rank = 4 (Sampling set: ”all-rank”, Initial sampling points: 200, Acquisition function: MPI) . . . . . . . . . . . . 4.8 Compare increased rank = 1 and increased rank = 4 (Sampling set: ”onlysorted”, Initial sampling points: 200, Acquisition function: MPI) . . . . . . . . 4.9 Evaluation minimum estimate traffic time through 24 intervals between Bayesian Optimization (BO) and Original method (Acquisition function: MPI, Search space: ”all-rank”, Initial sampling point = 200, Increase rank = 1) . . . . . . . 4.10 Evaluation number of executing Test function between Bayesian Optimization (BO) and Original method through 24 intervals (Acquisition function: MPI, Search space: ”all-rank”, Initial sampling point = 200, Increase rank = 1) . . . 4.11 Compare the difference percentage with the original method through 24 intervals of different sampling sets (Initial sampling points: 200, Acquisition function: MPI, Increase rank = 1) . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 3.1 3.2 3.3 4.1 4.2 39 55 57 58 59 60 60 61 62 63 64 Chapter 1 Introduction 1.1 Overview Due to the growth of network infrastructure and digital content, Internet traffic has increased rapidly over the years. At the same time, the number of people consuming web-based information and services is rising exponentially. A study [1] has estimated that Internet traffic will increase 3x in the next 5 years. By 2021, more than 82% of the whole internet will be video traffic caused by Video-on-Demand (VoD) services. As this enormous traffic creates multiple congested connections and degrades the network performance, VoD providers typically place their content on Content Delivery Networks (CDNs). Content Delivery Networks have emerged to overcome Internet congestion and overload by offering infrastructure and mechanisms to deliver content and services in a scalable manner. CDN applications can be found in many industries, such as research institutions, media advertising, data centers, Internet Service Providers (ISPs), e-commerce, network carriers, and other carrier businesses. Although CDNs could reduce video traffic, their servers are usually located in different network locations. Even though several CDN providers place their cache servers on ISP networks, this method still does not reduce traffic considerably [2]. The reason is that the servers are only in limited locations and CDN providers have no global knowledge of the underlying network. Several ISPs are planning to build their own CDNs by placing cache servers on their networks, which are called Telco-CDNs [2], [3]. They reduce the traffic on the peering links as well as internal communication links by confining the video requests to their networks. However, because of the limited storage space and inefficient allocation of contents, the traffic reduction achieved is not sufficient. Moreover, the objective of the Telco-CDN is to improve the efficiency of both the overlay and the underlying network infrastructure, which is different from conventional CDN. To address this problem, recent studies aim to minimize traffic by increasing cache capacity. They use a cooperative caching strategy, which adds multiple cache storage by sharing cache server contents. In the study of Li et al. [2], they proposed a content allocation algorithm based on Genetic Algorithm (GA) to always give a sub-optimal solution in the context of the network traffic. Although such strategies could eliminate a large amount of traffic, the time it takes to measure the solution using a cluster is especially long. Such a long calculation will lead to cache allocation inconsistencies, as access patterns vary by 20-60% per hour [4]. To overcome the limitations of the GA algorithm, Nakajima et al. [19], [24] proposed a light-weight color-based caching scheme using co-operative caching [2], [5] and hybrid caching [6]. The scheme focuses on two important factors of traffic reduction: content distribution 1 and the duplication of popular content by grouping caches and servers using a novel color tag scheme. These color tags are efficiently distributed to the caches and servers through a lightweight color distribution scheme. Even though the scheme reduces the computation time while keeping an approximate solution compared with the GA in terms of network traffic, the scheme’s computation time to find the color’s separator rank is still pretty long when the number of content categories increases. The color distribution scheme is quietly equivalent to a bruteforce strategy. Therefore, some calculations are not necessary. In this research, we propose a solution based on Bayesian Optimization to solve the problem of lowering the calculation time of determining the color’s separator rank. Then, we’ll evaluate the simulated and real datasets to determine the best-fitting parameter of the Bayesian Optimization approach as it applies to our situation based on comparison with the original color’s separator rank finding algorithm. 1.2 Goal The main objective of this research is to improve the computation time of the color separator rank finding algorithm using Bayesian Optimization and evaluation it with the previous research and other solutions. To achieve such a goal, we plan to carry out the following tasks: • Study CDNs and their related properties and problems. • Study the light-weight color-based caching scheme using co-operative caching and hybrid caching. • Study Bayesian Optimization. • Apply the Bayesian Optimization solution to solve the computation time problem. • Evaluating our solution with previous research and other algorithms. 1.3 Scope Although the color-based cooperative caching scheme is a new scheme to solve the content distribution and delivery in the CDN system, it still has many shortcomings that need improvement. In our thesis, we only concentrate on re-implementing the content’s color distribution algorithm that computes faster than the previous one. Additionally, we do not consider the new method will give an approximate solution compared to the old one. In general, we will examine suggesting methods that are more time-optimal in terms of computing time while remaining within a certain range of acceptable errors in comparison to the original answer. 1.4 Thesis Structure In the next section, we will study CDNs, color-based caching schemes, and the theoretical background required for this research. In Chapter 3, we discussed the details of our proposed Bayesian Optimization approach. In the next section, we evaluate our solution to find the best setting for the Bayesian Optimization method and compare it with the original solution. In the final chapter, we conclude and schedule the plan for the next stage. 2 Chapter 2 Knowledge Base 2.1 2.1.1 Content Delivery Network Introduction As the Internet developed and evolved, the network traffic grew exponentially, driven by fast adoption of broadband access, increased network complexity, and richness of content. This brings new challenges to the management and distribution of content to the user. Dealing with high traffic demands puts enormous pressure on a web server, and web servers are gradually completely overloaded by an increase in traffic, and the website containing its contents temporarily becomes inaccessible. A Content Delivery Network is a collaboratory collection of Internet network components that replicates content across a variety of Web servers in order to distribute content to end-users transparently and efficiently. They provide network capacity services by optimizing bandwidth, enhancing accessibility, and ensuring consistency by duplication of content. The typical functionalities of a CDN include: • Request redirection and content delivery services, sending a request to the nearest relevant cache CDN server using congestion bypass mechanisms. • Content outsourcing and distribution services, to replicate and cache content from the origin server to distributed Web servers. • Content negotiation services, to meet specific needs of each individual user (or group of users). • Management services, included network management, accounting management, and content utilization monitoring and reporting. A CDN distributes content across the globe to a network of Web servers to deliver content to end-users in a secure and timely manner. The material is repeated either on-demand as users request it or maybe replicated beforehand by selecting the contents of the distributed web servers. The contents of the adjacent mirrored Web servers are delivered to the client. As a result, the user unknowingly ends up connecting with a nearby mirrored CDN server and retrieves files from that server. 2.1.2 CDN Taxonomy Taxonomy of CDNs based on four key issues: • CDN Composition 3 • Content distribution and management • Request-routing • Performance measurement CDN Composition The structure of a CDN can differ depending on the content/services, it offers to its customers. Under the CDN framework, a collection of surrogates is used to structure the contentdelivery portion, certain configurations of relationships and mechanisms are used to redirect client requests to a surrogate, and interaction protocols are used for communicating between CDN components. Figure 2.1: CDN Composition. CDN Organization, there are 2 general approaches for building CDN: • In the overlay approach, application-specific servers and caches at various locations on the network control the delivery of specific content types (e.g. Web content, streaming media, and real time video). Apart from offering basic network access and assured QoS for specific request/traffic, essential network elements such as routers and switches do not play an active role in the distribution of content. CDN services replicate content on cache servers all over the world. As content requests are sent from end-users, they are forwarded to the closest CDN node. • In the network approach, a code is given to define particular application types and to forward applications based on predetermined policies in the network elements, including routers and switches. Examples of this method involve systems that route content requests to local caches or shift traffic to specialized servers that are optimized to serve specific content types. Servers, The servers used by a CDN are of two types – origin and replica servers: • Origin server is where the definitive version of the content resides. It is updated by the content provider. • A replica server preserves a copy of the content but may act as an authoritative guide for client responses. The origin server connects with distributed replica servers to update the 4 content contained in the replica server. A cache server allows copies (i.e. caches) of data at the edge of the network to prevent the need to reach the origin server to address any content request. Relationships, includes components such as clients, surrogates, origin servers, proxy caches, and other network elements. These components interact to copy and cache data on a CDN. Replication requires making and storing a replicated copy of the content on multiple computers. Usually, it requires ”pushing” content from the origin server to the replica server. Figure 2.2: CDN Composition - Relationship. The graphical representations of those relationships are: 1. Client-to-surrogate-to-origin server 2. Network element-to-caching proxy 3. Caching proxy arrays 4. Caching proxy meshes Interaction Protocols, Based on the interaction relationships mentioned above, we may define the interaction protocols that are used to communicate with CDN components. Such interactions can be narrowly divided into two types: interaction between network elements and interaction between caches. 5 Figure 2.3: CDN Composition - Interaction Protocols. Content/Service Types, CDN providers host third-party content for fast delivery of any digital content, including – static content, dynamic content, streaming media and different content services. There are 3 main types to consider: • Static content refers to content with a low level of transition. It does not change based at the request of the customer. This includes static HTML pages, embedded images, executable, PDF documents, audio and/or video files. • Dynamic content refers to content that is personalized by the user or generated on-demand by the implementation of an application process. It also varies based on the user’s requests. • Streaming media can be live or on-demand. Content is transmitted ”immediately” from the encoder to the media server, and then to the media device. Streaming servers are adopted with advanced protocols for service distribution through the IP network. Content Distribution and Management Figure 2.4: Content Distribution and Management. Content control in the CDN is strategically critical for effective content distribution and optimal efficiency. Distribution of content require: • Collection and distribution of content based on the type and frequency of individual user requests • Location of surrogates to such geographical locations so that the edge servers are customercentered. 6 • Outsourcing material to determine which outsourcing approach to follow. • Content management is primarily based on techniques for the management of the cache In this section, we focus on Surrogate placement because of relatively essential part to our Color-based cooperative caching in CDN. Figure 2.5: Surrogate placement. The aim of ideal surrogate placement is to reduce the perceived latency of users for obtaining information and to decrease total network bandwidth usage for transmitting replicated content from servers to clients. The optimization of all of these metrics results in decreased maintenance and connectivity costs for the CDN provider. For surrogate server placement, the CDN administrators also determine the optimal number of surrogate servers using single-ISP and multi-ISP approach [13]: • In a single-ISP strategy, a CDN provider usually deploys at least 40 surrogate servers across the network edge to enable the distribution of content [14]. The strategy in a single-ISP approach is to position one or two surrogates within the scope of the ISP coverage of each major city. The ISP is equipping the surrogates with large caches. The downside to this strategy is that the surrogates may be put at a distance from the clients of the CDN provider. • In the Multi-ISP approach, the CDN supplier positions as many ISP Presence Points (POPs) worldwide as possible. Supplies are put next to customers and, as a result, the content is delivered securely and on time from the ISP of the requesting customer. Apart from the expense and sophistication of setup, the key downside of the multi-ISP strategy is that each surrogate server receives less (or no) content requests which can result in idle resources and low CDN performance [15]. 2.1.3 Content Placement Various operating subsystems operate in the content distribution network, including content management and routing requests [16]. The content management subsystem, as shown in Fig. 2.6, is responsible for choosing the content to be mirrored and the proxy server(s) that will host replicated content for the quality of service end-user demands (QoS). The request router has a series of policies for routing end-user requests to either the load balancing server(s) or the QoS server(s). The content management subsystem (CMS) is vital to QoS. In the sense of CDNs, CMS determines where to locate surrogate servers, what to replicate, and which surrogate servers to keep replicas of content. 7 Figure 2.6: Content management subsystem. In general terms, content placement algorithms are either pull or push, based on how surrogate servers get content from the origin server. • Pull-based technique: Caching employed to increase content availability and reduce content access latency. (Reactive) • Push-based technique: preemptively store content to meet an estimated demand (Proactive) • Cooperative technique: content placement algorithms retrieve missing content from the neighboring surrogates Figure 2.7: End-user to CDN interaction. 8 Depending on the direction of content flow between the origin server(s) and the surrogate servers. • In push-based content placement, content providers estimate end-user requests or predict content access patterns and replicate content from the origin server(s) to surrogates, prior to receiving end-user requests for content. And contingencies are in place to cater to unpredicted end-user requests and content access patterns. • In pull-based content placement, the end-user requests prompt the surrogates to import and store content from the origin server(s) or the adjacent surrogate server(s). Initially, all end-user requests will result in a failure, since the surrogate will need to retrieve content from the original or neighboring surrogate server(s). Gradually, as the repository on the surrogate server expands, the end-user requests will result in hits and the end-user requests will be immediately fulfilled by the surrogate server. Surrogates can cooperate with each other to download content from a surrogate(s) that is closer to the origin server or directly from the origin server with cooperative or non-cooperative schemes. The efficiency of pull and push-based content placement rely significantly on the accuracy of the prediction and estimation models for the prediction of end-user requests or content access patterns. But, cooperative push-based content placement algorithms also yield high performance over other content placement algorithms [17]. Content placement algorithms are sensitive to content access patterns of correlated and referred videos since they can significantly impact the popularity of content. Content popularity follows heavy-tail distributions, such as those parameterized by power law and exponential functions: • Pull-based approach is simple and effective, it will not give high hit ratio as the data in the long tail will generate misses • The cache hit rate is also dependent on the cache size and the eviction probability of the content Formal Modeling 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. Figure 2.8: Utilities for modeling objectives and constraints. 9 The goal is to decrease the latency, i.e. to reduce traffic between the substitutes and the server of origin(s). The problem of latency reduction comprises objectives that reduce distance and/or traffic between end users and surrogates but are not limited to. Distance or traffic between providers and origin servers is greatly reduced and more content is specifically imposed on consumers and the QoS indirectly increases the perceived latency of the end-user. A distance metric is typically used to evade the assumed latency of the end-user. However, network conditions are also used for the end-user perceived latency, such as traffic volume and round trip times (RTT). The goals of decreased operation costs apply to computing costs, connectivity costs for the network, and transmission costs. The cost of bandwidth usage is dependent on the distribution to end-users of content, the retrieval of content from source servers or other surrogates to accommodate demands of end-users, the downloading of contents, the replication of content, and/or the maintaining of a cohesive content of copies. Those targets are therefore conflicting and do not preclude each other. For instance, the cost of network bandwidth is proportional to the network traffic needed to access or retrieve information. In CP models it is necessary however to use the bandwidth to prevent the congestion of CDN traffic on the network backbone. The underlying network status is rarely taken into account by CP models and algorithms. However, it should be a primary aim to gain fault tolerance. The CP model must in this instance ensure content compatibility in a ’lossy’ network within QoS, where backups and capacity might not be available due to the failure of the connection. 2.1.4 Request Routing Request-routing mechanisms inform the client about collection of the replica servers created by the request-routing algorithms. From this information, the replica server, the origin server, and the client will communicate to choose the best route that optimizes the cost of the communication. Request-routing systems can be categorized according to a variety of criteria. Figure 2.9: Taxonomy of request-routing mechanisms. 10 Fig. 2.9 shown classified request-routing mechanisms. There are three major mechanisms widely used in real application: DNS-based request routing, HTTP redirection, and URL rewriting. DNS-based request routing The DNS-based request routing system allows content delivery providers to map a symbolic name of a replacement host with its numerical IP address using the updated DNS server. It is used for the collection and distribution of full-site content. A domain name has many IP addresses connected with it in the DNS-based request routing. When the content request of the end user is made, the DNS server of the service provider returns the IP addresses of the servers containing the replica of the requested object. The DNS solution of the client selects one of these servers. To make a decision, the solver can issue the probes to the servers and choose the response times to these probes. It can also gather historical information from clients on the basis of past access to these servers. The benefit of this strategy is transparency, since the providers are referred to by their DNS names and not their IP addresses. DNS-based solution is highly common due to its flexibility and isolation from any real replicated operation. The downside of DNS-based request-routing is that it increases network latency due to extended DNS search times. HTTP Redirection HTTP redirection propagates the replica server collection information in the HTTP headers. HTTP protocols allow a Web server to respond to a client request with a special message that allows the client to re-submit the request to another server. The HTTP redirect can be used for both full-site and partial-site content collection and execution. Flexibility and simplicity are the key benefits of this approach. The most important drawback to HTTP redirection is the lack of clarity. In addition, the overhead perceived by this method is important as it adds unnecessary round-trip messages into the handling of requests as well as over HTTP. URL Rewriting In URL rewriting approach, the origin server redirects clients to various surrogate servers by rewriting the dynamically generated URLs of the sites. It is primarily used for the collection and distribution of partial-site content where embedded objects are submitted as a response to client requests. URL rewriting can be either pro-active or reactive. In pro-active method, the URLs for embedded objects on the main HTML page are formulated before the contents are loaded to the origin server. The reactive method includes rewriting the built-in URLs of the HTML page as the client request hits the origin server. The key benefit of URL rewriting is that clients are not tied to a single surrogate server since the rewrite URLs have DNS names that point to a group of surrogate servers. The drawbacks of this method are the delay in URL parsing and the potential bottleneck introduced by the in-path feature. Another downside is that content with a changed connection to the surrounding proxy server rather than the root server is non-cacheable. 2.1.5 Open Issues in CDNs With the growing of CDN networks, there are several challenges that need to be discussed. Several service providers are improving their CDN system steadily to increase the effectiveness of content delivery. 11 Akamai Intelligent Platform Akamai owns one of the largest CDNs with 20% of Internet traffic nowadays. In such large delivery platforms many technological challenges arise. First, defending websites from distributed Denial-of-Service attacks [8] motivates caching and filtering techniques, which can handle large amounts of requests. Secondly, Akamai uses the principle of a cloud or elastic CDN, where storage capabilities are modified dynamically to satisfy the demand [9]. Google Google Global Cache (GCC) system comprises caches installed at ISP premises. GCC is targeted at serving YouTube content locally and reducing bandwidth costs [10]. GCC’s importance inspired the analysis of the relationship between service providers and network operators and particularly the design of price models for rental in-network caching capacities at operator sites. Security is another related challenge; previous work has suggested schemes for the confidentiality of content [11] allowing straightforward caching of encrypted flows but caching encrypted content is one of the challenging open topics in the future. Netflix Open Connect Similarly to GCC, the Netflix CDN is partially deployed within ISPs [12] but their content catalog is much smaller and the file popularity more predictable. Netflix was thus highly innovative in researching space-time request profiles, strategies for pre-loading caches overnight, and in reducing daytime flow. An open research challenge in this sense is to detect the popularity shifts in advance and to identify video files online, whether they are caching or not. Amazon AWS AWS provides Amazon Cloudfront, a virtual CDN that delivers CDN facilities using the cloud storage platform. Amazon enables one to rent caching services dynamically per hour by adjusting the storage capacity. Along with other related technologies suggested by Akamai and others, this cloud or elastic cache architecture motivates further research into the new business paradigm and the dynamic cache location and dimensioning. 2.2 2.2.1 A Light-weight Content Distribution Scheme for Cooperative Caching in Telco-CDNs [19] Approach Due to the rapid evolution of Video-on-Demand (VoD) services, traffic on the Internet is increasingly enormous. Such immense traffic not only reduces the customer experience because of congested connections but also increases the connectivity costs. Although Content Delivery Networks have reduced the traffic due to caching videos, the corresponding cache servers are typically located outside the networks of the Internet Service Providers (ISPs). This means that traffic on peer connections between ISPs and CDNs can not be minimized by CDNs, leading to many congested links. This circumstance leads to the concept of placing CDNs inside ISPs; several ISPs have considered building Telco-CDNs or ISP-Operated CDNs which are CDNs managed by ISPs rather than global CDN providers. In Telco-CDNs, cache servers are located directly in the backbone networks of the ISPs, and ISPs manage several cache servers with complete knowledge of the network’s properties. Therefore, in such a scenario, ISPs are possible to apply many advanced 12