CDN内容分发网络优化方法的研究
|
摘要
内容分发网络是为了改善网络负载不均,增加用户满意度而发展起来的热门网络技术。目前最典型的内容分发网络包括点对点网络(P2P)与内容发布网(CDN)两种,文章首先简要介绍了点对点网络与内容发布网的概念和发展现状,并详细给出了内容发布网网络中的几种主要技术:内容路由、内容分发、内容管理。
本文的主要工作围绕商业应用中的PUSH模型展开。它与前人研究的PUSH技术相比,有两个特点。一是更高的时效性:至少在一个触发时隙内能完成求解;二是求解的连续性。
与一般的内容分发模型相比,本研究与前人文章主要有四点不同:一是简化拓扑到以节点为单位。把一片代理区域内所有用户和代理服务器看做一个统一节点,不考虑具体的边缘服务器到用户的路由,这样做极大的提高了模型规模的可扩展性,而且还把具体的路由技术从内容分发技术中剥离开。二是确立了以内容发布网运营商为服务对象,完全从内容发布网运营商的角度出发考虑问题,不仅使模型的目标函数和限制条件更完备,也更有实际说服力。三是采用内容聚类的思想,把多个热度相似的内容组合成一个频道,在调度时看成一个整体。四是在求解多目标函数的模型时,本文没有把两个目标放在一起加权求和,而是假设两种应用环境,分成两个子模型分别求解。
最小化网络带宽问题的数学模型是一个标准0-1规划模型,本文不仅用标准的隐数法求解此模型,还给出了自己的启发式解法,并通过大量实验表明,在线性求解时间内,启发解的性能达到了最优解的95%。而最小化服务器损耗问题的数学模型属于混合整数规划,变量数目很多时根本无法求最优解。本文用启发式算法求解,并用估计的最优解的上限与之对比,以反映启发解的性能。实际仿真时做出了两个小的改进,通过对比实验表明,性能比以前调高10%左右。
Content Distribution Network is a hot technology aimed to improve the network load balance, increase customer satisfaction. The most typical content delivery network are P2P and CDN. We have given a brief introduction to both P2P and CDN first, then in detail discussed about three technology in CDN: content dilivery, routine, and management.
This thesis mainly studies one type of content delivery strategy for CDN, named realtime-PUSH strategy. Compare to normal PUSH strategy, it has two characters: first, it must be much more efficient in time; second, the environment is a continuing process.
Compared to former research, our model has four differences: 1, We have brought node clustering structure to our model, which means we no longer care about the different behaves between proxy, client , or source, but combine them as a whole node. In this way, the scalability of model is greatly improved. 2, The main purpose of this research is to help CDN provider, so that the model has precise goals and limits, and is much closer to reality. 3, All the contents are clustered as some bucks, called channel. 4, When facing a extremely complicate problem, we depart the problem into two sub-problems, and then gives two different model to fix out each.
The goal of the first model is to minimize the bandwidth consuming. This model has turned out to be a standard 0-1 linear programming. Later in this thesis, we not only give the standard method to solve this problem, but also give a heuristic algotithm. Through a huge number of experiments, we prove that the heuristic algorithm is much more efficient in time and its solution is about 95% close to the optimal one. The goal of the second model is to minimize the exchange of all channels on all proxies. This model proved to be a mixture nonlinear programming problem, and is very hard to get its optimal solution. So we have to give a heuristic algorithm instead. In order to estimate the perfomence of this heuristic algorithm, also give a estimation on the optimal solution. At last made two small changes on the algorithm, under certurn circumtances, the performance can be improved by 10%, with the price of 2 or 3 times of time consuming.
本文的主要工作围绕商业应用中的PUSH模型展开。它与前人研究的PUSH技术相比,有两个特点。一是更高的时效性:至少在一个触发时隙内能完成求解;二是求解的连续性。
与一般的内容分发模型相比,本研究与前人文章主要有四点不同:一是简化拓扑到以节点为单位。把一片代理区域内所有用户和代理服务器看做一个统一节点,不考虑具体的边缘服务器到用户的路由,这样做极大的提高了模型规模的可扩展性,而且还把具体的路由技术从内容分发技术中剥离开。二是确立了以内容发布网运营商为服务对象,完全从内容发布网运营商的角度出发考虑问题,不仅使模型的目标函数和限制条件更完备,也更有实际说服力。三是采用内容聚类的思想,把多个热度相似的内容组合成一个频道,在调度时看成一个整体。四是在求解多目标函数的模型时,本文没有把两个目标放在一起加权求和,而是假设两种应用环境,分成两个子模型分别求解。
最小化网络带宽问题的数学模型是一个标准0-1规划模型,本文不仅用标准的隐数法求解此模型,还给出了自己的启发式解法,并通过大量实验表明,在线性求解时间内,启发解的性能达到了最优解的95%。而最小化服务器损耗问题的数学模型属于混合整数规划,变量数目很多时根本无法求最优解。本文用启发式算法求解,并用估计的最优解的上限与之对比,以反映启发解的性能。实际仿真时做出了两个小的改进,通过对比实验表明,性能比以前调高10%左右。
Content Distribution Network is a hot technology aimed to improve the network load balance, increase customer satisfaction. The most typical content delivery network are P2P and CDN. We have given a brief introduction to both P2P and CDN first, then in detail discussed about three technology in CDN: content dilivery, routine, and management.
This thesis mainly studies one type of content delivery strategy for CDN, named realtime-PUSH strategy. Compare to normal PUSH strategy, it has two characters: first, it must be much more efficient in time; second, the environment is a continuing process.
Compared to former research, our model has four differences: 1, We have brought node clustering structure to our model, which means we no longer care about the different behaves between proxy, client , or source, but combine them as a whole node. In this way, the scalability of model is greatly improved. 2, The main purpose of this research is to help CDN provider, so that the model has precise goals and limits, and is much closer to reality. 3, All the contents are clustered as some bucks, called channel. 4, When facing a extremely complicate problem, we depart the problem into two sub-problems, and then gives two different model to fix out each.
The goal of the first model is to minimize the bandwidth consuming. This model has turned out to be a standard 0-1 linear programming. Later in this thesis, we not only give the standard method to solve this problem, but also give a heuristic algotithm. Through a huge number of experiments, we prove that the heuristic algorithm is much more efficient in time and its solution is about 95% close to the optimal one. The goal of the second model is to minimize the exchange of all channels on all proxies. This model proved to be a mixture nonlinear programming problem, and is very hard to get its optimal solution. So we have to give a heuristic algorithm instead. In order to estimate the perfomence of this heuristic algorithm, also give a estimation on the optimal solution. At last made two small changes on the algorithm, under certurn circumtances, the performance can be improved by 10%, with the price of 2 or 3 times of time consuming.
引文
[1]钟瑛,我国互联网发展现状及其竞争格局,新闻与传播研究,2007,13(4):29-33
[2]夏淑华,浅谈P2P技术应用及存在的问题,警官论坛, 2007,6(4):178-184
[3]金世杰,赵问道, CDN网络路由技术,计算机应用研究, 2003, 5(5):156-159
[4]杨明川, CDN中的负载均衡技术,信息网络, 2003,8(2):45-49
[5]王樟,柳健, CDN网络中的内容分发技术研究,网络与应用, 2004,7(2):87-98
[6]姜文颖, CDN网络中八种负载均衡实现技术的探讨,中国数据通信, 2004,8(3):134-145
[7]董梅,肖民,宽带流媒体领域的CDN技术,广播电视信息, 2005,3(2):121-125
[8]徐卫东,王康,适用于内容分发网络的动态负载均衡策略,计算机科学, 2005,10(2): 48-51
[9]宋家友,桑红涛, CDN技术的发展及应用,宽带网络与传输, 2005,7(1):25-30
[10]马明霞,张学军, CDN技术及其在图书馆局域网中的应用,现代图书情报技术, 2004(4)1:13-22.
[11]聂秀英,网络内容分发技术,电信科学, 2004,3(2):36-50.
[12] Y.Chen, R.H.Katzynamic, Replica placement for scalable content delivery, in: Proc of 1st Int.Workshop on Peer-to-Peer Systems, 2002,5(3):124-126
[13] M.Chen,J.P.Singh and A.LaPaugh, Subscription-enhanced content delivery, in: Proc of WCW’03, 2003,3:56-78
[14] C.Huang and T.Abdelzaher, Towards content distribution networks with latency guarantees, in: Proc of 12th IWQoS, 2004,12(4):123-127
[15] J.Kangasharju,J.Roberts,and K.W.Ross, Object replication strategies in content distribution networks, in: Proc of WCW’01, 2001,1:43-67
[16] Yannis Matalas,Nikolaos D, A Scalable Framework for Content Replication in Content Distribution Networks, Journal of Algorithms, 2001,11(2):110–115.
[17] M.Korupolu,G.Plaxton,and R.Rajaraman, Placement algorithms for hierarchical cooperative caching, Journal of Algorithms, 2001,4(2):79-95
[18] A.Bestavros, WWW Traffic Reduction and Load Balancing Through Server-based Caching, IEEE Concurrency, 1997,6(4)104-135
[19]陈宝林,最优化理论与算法,清华大学出版社, 2005.10
[20] Luenberger D G. Linear and nonlinear programming. Addison-Wesley, 1984
[21] Lili Qiu, Venkata N.Padmanabhan, On the Placement of Web Server Replicas, IEEE INFOCOM, 2001,3(5)145-167
[22] Kazem,and S.Guha, Improved Combinatorial Algorithms for the Facility Location and K-Median Problems, in: Proc of the 40th Annual IEEE Conference on Foundations of Computer Science, 1999,6:89-102
[23] L.Qiu,V.N.Padmanabhan,and G.M.Voelker, On the placement of Web server replica, in: Proceedings of IEEE INFOCOM, 2001,7:78-98
[24] S.Jamin,C.Jin,Y.Jin,D.Raz,Y.Shavitt,L.Zhang, On the Placement of Internet Instrumentation, in: Proc.of INFOCOM’2000, 2000,6:56-63
[25] B.Krishnamurthy and J.Wang, On Network-Aware Clustering of Web Clients, In: Proc of SIGCOMM’2000, 2000,4:25-50
[26] B.Li,M.J.Golin,G.F.Ialiano,and X.Deng, On the Optimal Placement of Web Proxies in the Internet, in: Proc.of INFOCOM, 1999,8:84-92
[27] E.W.Zegura,K.L.Calvert,and S.Bhattacharjee, How to Model an Inter- netWork, in: Proc of INFOCOM, 1996,7:87-97
[28] Jussi Kangasharju, James Roberts, Object replication strategies in content distribution networks, Computer Communications, 2002,7(2):43-77.
[29] Yan Chen, Lili Qiu, Efficient and Adaptive Web Replication using Content Clustering, IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS, 2003,10(2):56-72.
[30] Padmanabhan,S.Kutten,R.Soffer, Optimal allocation of electronic Content, in: Proceedings of IEEE Infocom, 2001,2:124-143
[31] S.Jamin,C.Jin, Constrained mirror placement on the Internet, in:Proceedings of IEEE INFOCOM, 2001,4:32-56
[32] NLANR measurement and operations analysis team. http://moat.nlanr.net.
[33] A.Luotonen and K.Altis, World-wide web proxies, in: Proc of the
[34] First International Conference, 1994,12:65-86
[35] T.P.Kelly,Y.-M.Chan,S.Jamin,and J.K.MacKie-Mason, Biased replacement policies for web caches:Differential quality-of-service and aggregate user value, in: Proc of the International Web Caching Workshop, 1999,6:123-134
[36] V.N.Padmanabhan and J.C.Mogul, Using predictive prefetching to improve world wide web latency, in: Proc of ACM SIGCOMM Computer, 1996,6:45-59
[37] P.Wolfe, and H. P. Crowder, Validation of Subgradient Optimization, Math Programming, 1974,16(2):62 - 88
[38] Tolga Bektas,Jean-Fran, Exact algorithms for the joint object placement and request routing problem in content distribution networks, Computers&Operations Research, 2007,2:43-58
[39] uanping Z,Weidong W,Xiaopeng T,Yonghu Z, Data replication at web proxies in content distribution network, Lecture notes in computer Science, 2003 ,10(5):560–569
[40] Kangasharju J,Roberts J,Ross KW, Object replication strategies in content distribution networks, Computer Communications, 2002,3(4)156-178
[41] Tassiulas L, Market-based resource allocation for content delivery in the Internet, IEEE Transactions on Computers, 2003,4(2):78-96
[42] Datta A,Dutta K,Thomas H,VanderMeer D, World wide wait:a study of Internet scalability and cache-based approaches to alleviate it, Management Science, 2003,4(3):32-60
[43] Radoslavov P,Govindan R,Estrin D, Topology informed Internet replica placement, Computer Communications, 2002,5(5)113-130
[2]夏淑华,浅谈P2P技术应用及存在的问题,警官论坛, 2007,6(4):178-184
[3]金世杰,赵问道, CDN网络路由技术,计算机应用研究, 2003, 5(5):156-159
[4]杨明川, CDN中的负载均衡技术,信息网络, 2003,8(2):45-49
[5]王樟,柳健, CDN网络中的内容分发技术研究,网络与应用, 2004,7(2):87-98
[6]姜文颖, CDN网络中八种负载均衡实现技术的探讨,中国数据通信, 2004,8(3):134-145
[7]董梅,肖民,宽带流媒体领域的CDN技术,广播电视信息, 2005,3(2):121-125
[8]徐卫东,王康,适用于内容分发网络的动态负载均衡策略,计算机科学, 2005,10(2): 48-51
[9]宋家友,桑红涛, CDN技术的发展及应用,宽带网络与传输, 2005,7(1):25-30
[10]马明霞,张学军, CDN技术及其在图书馆局域网中的应用,现代图书情报技术, 2004(4)1:13-22.
[11]聂秀英,网络内容分发技术,电信科学, 2004,3(2):36-50.
[12] Y.Chen, R.H.Katzynamic, Replica placement for scalable content delivery, in: Proc of 1st Int.Workshop on Peer-to-Peer Systems, 2002,5(3):124-126
[13] M.Chen,J.P.Singh and A.LaPaugh, Subscription-enhanced content delivery, in: Proc of WCW’03, 2003,3:56-78
[14] C.Huang and T.Abdelzaher, Towards content distribution networks with latency guarantees, in: Proc of 12th IWQoS, 2004,12(4):123-127
[15] J.Kangasharju,J.Roberts,and K.W.Ross, Object replication strategies in content distribution networks, in: Proc of WCW’01, 2001,1:43-67
[16] Yannis Matalas,Nikolaos D, A Scalable Framework for Content Replication in Content Distribution Networks, Journal of Algorithms, 2001,11(2):110–115.
[17] M.Korupolu,G.Plaxton,and R.Rajaraman, Placement algorithms for hierarchical cooperative caching, Journal of Algorithms, 2001,4(2):79-95
[18] A.Bestavros, WWW Traffic Reduction and Load Balancing Through Server-based Caching, IEEE Concurrency, 1997,6(4)104-135
[19]陈宝林,最优化理论与算法,清华大学出版社, 2005.10
[20] Luenberger D G. Linear and nonlinear programming. Addison-Wesley, 1984
[21] Lili Qiu, Venkata N.Padmanabhan, On the Placement of Web Server Replicas, IEEE INFOCOM, 2001,3(5)145-167
[22] Kazem,and S.Guha, Improved Combinatorial Algorithms for the Facility Location and K-Median Problems, in: Proc of the 40th Annual IEEE Conference on Foundations of Computer Science, 1999,6:89-102
[23] L.Qiu,V.N.Padmanabhan,and G.M.Voelker, On the placement of Web server replica, in: Proceedings of IEEE INFOCOM, 2001,7:78-98
[24] S.Jamin,C.Jin,Y.Jin,D.Raz,Y.Shavitt,L.Zhang, On the Placement of Internet Instrumentation, in: Proc.of INFOCOM’2000, 2000,6:56-63
[25] B.Krishnamurthy and J.Wang, On Network-Aware Clustering of Web Clients, In: Proc of SIGCOMM’2000, 2000,4:25-50
[26] B.Li,M.J.Golin,G.F.Ialiano,and X.Deng, On the Optimal Placement of Web Proxies in the Internet, in: Proc.of INFOCOM, 1999,8:84-92
[27] E.W.Zegura,K.L.Calvert,and S.Bhattacharjee, How to Model an Inter- netWork, in: Proc of INFOCOM, 1996,7:87-97
[28] Jussi Kangasharju, James Roberts, Object replication strategies in content distribution networks, Computer Communications, 2002,7(2):43-77.
[29] Yan Chen, Lili Qiu, Efficient and Adaptive Web Replication using Content Clustering, IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS, 2003,10(2):56-72.
[30] Padmanabhan,S.Kutten,R.Soffer, Optimal allocation of electronic Content, in: Proceedings of IEEE Infocom, 2001,2:124-143
[31] S.Jamin,C.Jin, Constrained mirror placement on the Internet, in:Proceedings of IEEE INFOCOM, 2001,4:32-56
[32] NLANR measurement and operations analysis team. http://moat.nlanr.net.
[33] A.Luotonen and K.Altis, World-wide web proxies, in: Proc of the
[34] First International Conference, 1994,12:65-86
[35] T.P.Kelly,Y.-M.Chan,S.Jamin,and J.K.MacKie-Mason, Biased replacement policies for web caches:Differential quality-of-service and aggregate user value, in: Proc of the International Web Caching Workshop, 1999,6:123-134
[36] V.N.Padmanabhan and J.C.Mogul, Using predictive prefetching to improve world wide web latency, in: Proc of ACM SIGCOMM Computer, 1996,6:45-59
[37] P.Wolfe, and H. P. Crowder, Validation of Subgradient Optimization, Math Programming, 1974,16(2):62 - 88
[38] Tolga Bektas,Jean-Fran, Exact algorithms for the joint object placement and request routing problem in content distribution networks, Computers&Operations Research, 2007,2:43-58
[39] uanping Z,Weidong W,Xiaopeng T,Yonghu Z, Data replication at web proxies in content distribution network, Lecture notes in computer Science, 2003 ,10(5):560–569
[40] Kangasharju J,Roberts J,Ross KW, Object replication strategies in content distribution networks, Computer Communications, 2002,3(4)156-178
[41] Tassiulas L, Market-based resource allocation for content delivery in the Internet, IEEE Transactions on Computers, 2003,4(2):78-96
[42] Datta A,Dutta K,Thomas H,VanderMeer D, World wide wait:a study of Internet scalability and cache-based approaches to alleviate it, Management Science, 2003,4(3):32-60
[43] Radoslavov P,Govindan R,Estrin D, Topology informed Internet replica placement, Computer Communications, 2002,5(5)113-130