Placement Strategy for Replicated Servers in CDN
作者单位：Department of Automation Shanghai Jiao Tong University Key Laboratory of System Control and Information Processing Ministry of Education of China
会议名称：《第37届中国控制会议》
会议日期：2018年
学科分类：08[工学] 081201[工学-计算机系统结构] 0812[工学-计算机科学与技术（可授工学、理学学位）]
基 金：supported by the National Natural Science Foundation of China under Grant Nos.61473189 and 61773255 the Natural Science Foundation of Shanghai(No.17ZR1445200) the Science Fund for Creative Research Groups of the National Natural Science Foundation of China(No.61521063)
关 键 词：Web replica placement algorithm content distribution network(CDN) network segmentation
摘 要：Study of Content Distribution Networks（CDNs） attracts increasing attentions recently. Deploying a set of servers across the Internet containing replicated content will certainly provide users with better experience by reducing request latency and balancing the load. However, due to the large-scale and high-volume requests from the users, quantities of proxy servers are needed resulting in high cost of facilities. Therefore, it is necessary to find an optimal replicated-server placement that can improve Internet performance while controlling the budget. To solve this problem, we first propose a new model, CF LP EC,based on which the nature of Internet can be described. In addition, we analyze the feasibility and compare several lower bound algorithms of the new model. Based on CF LP EC, we testify the performance of the network-segmentation algorithm. The proposed algorithm uses K-means algorithm to cluster the network and for each cluster, greedy algorithm is applied to find out an approximate placement in this area. As we obtain the solutions for all the clusters respectively, we merge them to constitute the final solution for the whole network. Instead of directly stitching them together, possible situations that will occur on the boundaries between two clusters are also taken into consideration. Finally, we learn from the natural characteristics of the Internet to construct the simulation model, and simulation results illustrate the feasibility and effectiveness of the proposed algorithm.