利用文件优化分配实现Web服务器集群负载均衡的研究
|
摘要
随着因特网的飞速发展和网络应用的广泛展开，人们对信息服务平台提出了更高的要求，不仅需要快速响应性、高可伸缩性、高可用性、易管理性、高性能价格比，还需要提供对关键企业级应用非常有价值的功能特性。服务器集群系统是近年来随着Internet和Web的发展兴起的一种具有强大生命力的新兴技术，通过请求分配使集群达到负载均衡是提高这种系统运行效率的基本手段。虽然目前已经对这个课题进行了很多研究工作，但这些工作大多偏重于前端的调度，而忽略了后台服务器上文档的分布及文档间的相关性。本文在前人研究的基础上，深入地研究了Web文档的拷贝、相关性等一系列特性，在分析了节点服务器的能力后，把Web文档优化分配在后端节点上，来实现服务器集群的负载均衡。本文的研究工作主要包含以下几个方面的内容和成果：
1、研究了Web文档的各种特性，并将这些特性作为Web服务器集群系统中文档优化分配的依据。
2、实现了Web服务器集群后台文档访问、分布的监测系统。
3、提出了Web文档间的条件访问概率，文档的拷贝和相关性，并研究了Web文档间链接和条件访问概率的运算。
4、提出并实现了一种Web文档归类算法——文档簇。
5、研究并改进了已有的文档优化分配理论，用遗传法、贪心法等实现了具体分配。
6、提出了Web文档的初始优化分配、定期优化分配和即时优化分配。
With the explosive growth of Internet and World Wide Web's traffic, High Scalability, Reliability, Availability and Efficient Cost/Performance ratio are strongly required for the Information Service Platform-Network Servers. Server Cluster is a newly developed technology with the thriving of the Internet and the Web. Achieving load balancing by request dispatching is one of the basic strategies for improving the performance and efficiency of this kind of systems. Although a lot of researches have been made within this field, people pay importance to the form's dispatching and ignore the distribution and correlation of the files on the latter's servers. On the basis of the anterior researches, this paper studies on a series of characteristics of the web files, such as copies and correlation. After analyzing the ability of the servers, all files are allocated to the servers suitably, which realizes the load balancing of the server cluster. The contributions of this paper are as the following:
1 Studying the characteristics of all kind of web files, and optimizing the web files according to these characteristics.
2 Realizing the monitor system of the visit and the distribution of the latter's web files.
3 This paper produces the conditional-visit-probability, the copies and the correlation of the web files, and studying the operation method.
4 This paper produces and realizes an algorithm of the web file classification 桭ile Cluster.
5 Studying and improving the optimizing allocation theory of the files, and realizing the material allocation by the cupidity and the genetic algorithm.
6 Producing the initializing optimizing allocation , the periodic optimizing allocation and the instant optimizing allocation of the web files.
1、研究了Web文档的各种特性，并将这些特性作为Web服务器集群系统中文档优化分配的依据。
2、实现了Web服务器集群后台文档访问、分布的监测系统。
3、提出了Web文档间的条件访问概率，文档的拷贝和相关性，并研究了Web文档间链接和条件访问概率的运算。
4、提出并实现了一种Web文档归类算法——文档簇。
5、研究并改进了已有的文档优化分配理论，用遗传法、贪心法等实现了具体分配。
6、提出了Web文档的初始优化分配、定期优化分配和即时优化分配。
With the explosive growth of Internet and World Wide Web's traffic, High Scalability, Reliability, Availability and Efficient Cost/Performance ratio are strongly required for the Information Service Platform-Network Servers. Server Cluster is a newly developed technology with the thriving of the Internet and the Web. Achieving load balancing by request dispatching is one of the basic strategies for improving the performance and efficiency of this kind of systems. Although a lot of researches have been made within this field, people pay importance to the form's dispatching and ignore the distribution and correlation of the files on the latter's servers. On the basis of the anterior researches, this paper studies on a series of characteristics of the web files, such as copies and correlation. After analyzing the ability of the servers, all files are allocated to the servers suitably, which realizes the load balancing of the server cluster. The contributions of this paper are as the following:
1 Studying the characteristics of all kind of web files, and optimizing the web files according to these characteristics.
2 Realizing the monitor system of the visit and the distribution of the latter's web files.
3 This paper produces the conditional-visit-probability, the copies and the correlation of the web files, and studying the operation method.
4 This paper produces and realizes an algorithm of the web file classification 桭ile Cluster.
5 Studying and improving the optimizing allocation theory of the files, and realizing the material allocation by the cupidity and the genetic algorithm.
6 Producing the initializing optimizing allocation , the periodic optimizing allocation and the instant optimizing allocation of the web files.
引文
[1] 吴功宜 吴英《计算机网络教程》电子工业出版社 1998
[2] Srinivasan Seetharaman. IP over DWDM. http://www.cis.ohio-state.edu-/～jain/cis788-99/ip_dwdm
[3] Lucent Technologies. Web ProForum tutorial: DWDM. October 1999, http://www.webproforum.com/acrobat/dwdm.pdf
[4] Yan Chen Lili Qiu Weiyu Chen Luan Nguyen. Clustering Web Content for Efficient Replication.
[5] http://www-900.ibm.com/developerWorks/en/linux/cluster/lvs/part1/index.shtml Linux服务器集群系统——LVS项目介绍 作者：章文嵩
[6] Yahoo! Inc., The Yahoo! Directory and Web Services, http://www.yahoo.com/
[7] Hypertext Transfer Protocol Secure http://iroi.seu.edu.cn/books/ee_dic/whatis/https.htm
[8] http://www-900.ibm.com/developerWorks/cn/linux/cluster/cluster_system/base/part2/index2.shtml
[9] Kai Hwang．高级计算机体系结构(英文版)，机械工业出版社，1999
[10] 徐志伟 黄凯．可扩展并行计算—技术结构与编程。机械工业出版社，2000
[11] David E. Culler、Jaswinder Pal Singh、Anoop Gupta．并行计算机体系结构(英文版)机械工业出版社，1999
[12] 郑纬民，石威，汪东升 高性能集群计算：结构与系统(第一卷)电子工业版社，2000
[13] T. Brisco. "DNS Support for Load Balancing", April 1995.Network Working Group RFC 1794.
[14] V. Cardellini, M. Colajanni, P. S. Yu. DNS dispatching algorithms with state estimators for scalable Web-server clusters, World Wide Web Journal, Baltzer Science Publ., vol.2, no.3, pp. 101-113, 1999
[15] H.W. Braun. and K. C. Claffy. Web Traffic Characterization: An Assessment of the Impact of Caching Documents from NCSA's Web Server. Computer Networks and ISDN Systems, 1995, 28:37-51
[16] Luis Aversa and Azer Bestavros. Load Balancing A Cluster Of Web Servers Using Distributed Packet Rewriting.In Proceedings of the IEEE International Performance, Computing and Communications conference, Phoenix, AZ USA, February 2000.C.Perkins, IETF RFC2003
[17] H. Bryhni, E. Klovning, and O. Kure. A comparison of load balancing techniques for scalable web servers. IEEE Net-work, 14(4):58-64, July/Aug. 2000.
[18] Cisco Inc. Scaling the World Wide Web. Technical Report, Available From: http://www.cisco.com
[19] Andy Stanfork-Clark, IBM Watson Research Center. Load Distribution for Scalable Web Servers. 1996
[20] G. Hunt, E. Nahum, and J. Tracey. "Enabling content-based load distribution for scalable services". Technical report, IBM T.J Watson Research Center, May 1997.
[21] 邸烁。Web Server集群请求分配和负载平衡研究。[博士论文]清华大学计算机系1999
[22] Guerney D.H.Hunt, German S.Goldszmidt, Richard P.King, and Rajat Mukherjee.Network Dispatcher: A Connection Router for Scalable Internet Services.In the Proceedings of the Seventh International World Wide Web Conference,Brisbane,Autralia, April 1998
[23] Cisco Inc. Scaling the World Wide Web. Technical Report, Available From: http://www.cisco.com
[24] Nortel Networks Ltd. Alteon ACE director, http://www.nortelnetworks.com/.
[25] 武汉大学电信学院网络通信实验室，《高性价比网络服务器集群技术研究报告》，2002．12
[26] Wesley W.Chu Optimal File Allocation in a Multiple Computer System. IEEE Trans. On Computers, 1969
[27] Lawrence W.Dowdy, Derrell V.Foster. Comparative Models of the File Assignment Problem. ACM Computing Surveys,1982
[28] ViVek S.Par, Mohit Aron.Locality-Aware Request Distribution in Clusterbased Network Servers.In Proceedings of the 8th Conference on Architectural Support for Programming Languages and Operating System, San Joes.CA,Oct 1998.
[29] Mohit Aron, Darren Sanders,Peter Druschel,and Willy Zwaenepoel."Scalable Content-Aware Request Distribution in Cluster-Based Network Servers'.In Proceedings of the 2000 USENIX Annual Technical Conference, San Diego,CA USA,June 2000
[30] 《用TCP／IP进行网际互连第一卷：原理、协议与结构》赵刚等译 电子工业出版社 2001
[31] http://www.linuxvirtualserver.org/
[32] http://www.mosix.com.
[33] 应朝晖，高洪奎 黄若衡 《分布式文件系统》
[34] 白英彩编著 《分布式处理系统》科学出版社．
[35] 陈国良 《并行计算机体系结构》高等教育出版社．
[36] Doreen L. Galli著徐良贤等译 《分布式操作系统原理及实践》
(《Distributed Operating System Concepts and Practice》) .
[37] (美)Erez Zadok；邱仲潘等译《Linux网络文件系统管理指南》电子工业出版社．
[38] B.Narendran.Data Distribution Algorithms for Load Balanced Fauld-Tolerant Web Access 1997 IEEE.
[39] Abdelnaser Adas, Traffic Models in Broadband Networks NCR-9396299,GIT-CC-96-01,NOV 1997
[40] Martic F.Arliot et al.Web Server Workload Characterization: The Search For invariants,In Proceeding of the ACM SIGMETRICS'96 Conference,Philadelphia,PA,April 1996.
[41] Coda分布式文件系统www.coda.cs.cmu.edu.
[42] 李双庆 古平 程代杰 Web集群系统负载均衡策略分析与研究．
[43] 李傲雷 李治柱 分布式Web服务器负载均衡策略的仿真与应用．
[44] 林闯《Web服务器集群请求分配和选择的性能分析》计算机学报．
[45] 沈恒范《概率论与数理统计》高教出版社．
[46] Chu-Sing Yang and Mon-Yen Luo.Efficient Content Placement and Management on Cluster-based Web Servers. 0-7803-5864-3 2000 IEEE.
[47] Li-Chuan Chen Hyeong-Ah Choi. Approximation Algorithms for Data Distribution with Load Balancing of Web Servers. International Conference on Cluster Computing. 2002 IEEE.
[48] Chu-Sing Yang and Mon-Yen Luo. A Content Placement and Management System for Distributes Web-Server Systems.
[49] 李定锁 郭成城 晏蒲柳《Web服务器集群中的文件优化分配》计算机工程与应用 2004年16期
[50] Ben Chung-Pun Ng and Cho-li Wang.Document Distribution Algorithm for Load Balancing on an Extensible Web Server Architecture. 2002 IEEE.
[51] 孟祥武 程虎．利用遗传算法求解文件分配问题．软件学报1997年2月8卷2期。
[52] 李敏强 寇纪凇 林丹 李书全《遗传算法的基本理论与应用》科学出版社．
[53] Robert Kostelac Gordan Gledec. Balancing Web Server Workload Using Genetic Algorithms.
[54] Thomas V.Huynh.Optimal File Allocation in a Distribution Conputer Net Work by Orthogonal Array Experiments. 1997 IEEE.
[55] 张玉洁 高建明．基于模拟退火的文件优化分配．新疆大学学报14卷2期．
[56] Tao Zhao and Vijay Karamcheti. Enforcing Resource Sharing Agreements among Distributed Server Clusters. Computer Society 2002 IEEE.
[57] Akiko Nakaniwa Masaki Onishi Hiroyuki Ebara Hiromi Okada. Sensitivity Analysis of File Allocation for Distributed Information Networks. 1999 IEEE.
[58] Akiko Nakaniwa Masaki Ohnishi, Hiroyuki Ebara, Hiromi Okada.File Allocation in Distributed Multimedia Information Networks. 1998 IEEE.
[59] Randal C.Burns, Robert M.Rees, Darrel D.E.Long. Efficient Data Distribution in a Web Server Farm. INTERNET COMPUTING 2001 IEEE.
[60] Virv V.Phoha S.Sitharama lyengar and Raigopal Kannan. Faster web Page Allocation with Neural Networks. INTERNET COMPUTING 2002 IEEE.
[2] Srinivasan Seetharaman. IP over DWDM. http://www.cis.ohio-state.edu-/～jain/cis788-99/ip_dwdm
[3] Lucent Technologies. Web ProForum tutorial: DWDM. October 1999, http://www.webproforum.com/acrobat/dwdm.pdf
[4] Yan Chen Lili Qiu Weiyu Chen Luan Nguyen. Clustering Web Content for Efficient Replication.
[5] http://www-900.ibm.com/developerWorks/en/linux/cluster/lvs/part1/index.shtml Linux服务器集群系统——LVS项目介绍 作者：章文嵩
[6] Yahoo! Inc., The Yahoo! Directory and Web Services, http://www.yahoo.com/
[7] Hypertext Transfer Protocol Secure http://iroi.seu.edu.cn/books/ee_dic/whatis/https.htm
[8] http://www-900.ibm.com/developerWorks/cn/linux/cluster/cluster_system/base/part2/index2.shtml
[9] Kai Hwang．高级计算机体系结构(英文版)，机械工业出版社，1999
[10] 徐志伟 黄凯．可扩展并行计算—技术结构与编程。机械工业出版社，2000
[11] David E. Culler、Jaswinder Pal Singh、Anoop Gupta．并行计算机体系结构(英文版)机械工业出版社，1999
[12] 郑纬民，石威，汪东升 高性能集群计算：结构与系统(第一卷)电子工业版社，2000
[13] T. Brisco. "DNS Support for Load Balancing", April 1995.Network Working Group RFC 1794.
[14] V. Cardellini, M. Colajanni, P. S. Yu. DNS dispatching algorithms with state estimators for scalable Web-server clusters, World Wide Web Journal, Baltzer Science Publ., vol.2, no.3, pp. 101-113, 1999
[15] H.W. Braun. and K. C. Claffy. Web Traffic Characterization: An Assessment of the Impact of Caching Documents from NCSA's Web Server. Computer Networks and ISDN Systems, 1995, 28:37-51
[16] Luis Aversa and Azer Bestavros. Load Balancing A Cluster Of Web Servers Using Distributed Packet Rewriting.In Proceedings of the IEEE International Performance, Computing and Communications conference, Phoenix, AZ USA, February 2000.C.Perkins, IETF RFC2003
[17] H. Bryhni, E. Klovning, and O. Kure. A comparison of load balancing techniques for scalable web servers. IEEE Net-work, 14(4):58-64, July/Aug. 2000.
[18] Cisco Inc. Scaling the World Wide Web. Technical Report, Available From: http://www.cisco.com
[19] Andy Stanfork-Clark, IBM Watson Research Center. Load Distribution for Scalable Web Servers. 1996
[20] G. Hunt, E. Nahum, and J. Tracey. "Enabling content-based load distribution for scalable services". Technical report, IBM T.J Watson Research Center, May 1997.
[21] 邸烁。Web Server集群请求分配和负载平衡研究。[博士论文]清华大学计算机系1999
[22] Guerney D.H.Hunt, German S.Goldszmidt, Richard P.King, and Rajat Mukherjee.Network Dispatcher: A Connection Router for Scalable Internet Services.In the Proceedings of the Seventh International World Wide Web Conference,Brisbane,Autralia, April 1998
[23] Cisco Inc. Scaling the World Wide Web. Technical Report, Available From: http://www.cisco.com
[24] Nortel Networks Ltd. Alteon ACE director, http://www.nortelnetworks.com/.
[25] 武汉大学电信学院网络通信实验室，《高性价比网络服务器集群技术研究报告》，2002．12
[26] Wesley W.Chu Optimal File Allocation in a Multiple Computer System. IEEE Trans. On Computers, 1969
[27] Lawrence W.Dowdy, Derrell V.Foster. Comparative Models of the File Assignment Problem. ACM Computing Surveys,1982
[28] ViVek S.Par, Mohit Aron.Locality-Aware Request Distribution in Clusterbased Network Servers.In Proceedings of the 8th Conference on Architectural Support for Programming Languages and Operating System, San Joes.CA,Oct 1998.
[29] Mohit Aron, Darren Sanders,Peter Druschel,and Willy Zwaenepoel."Scalable Content-Aware Request Distribution in Cluster-Based Network Servers'.In Proceedings of the 2000 USENIX Annual Technical Conference, San Diego,CA USA,June 2000
[30] 《用TCP／IP进行网际互连第一卷：原理、协议与结构》赵刚等译 电子工业出版社 2001
[31] http://www.linuxvirtualserver.org/
[32] http://www.mosix.com.
[33] 应朝晖，高洪奎 黄若衡 《分布式文件系统》
[34] 白英彩编著 《分布式处理系统》科学出版社．
[35] 陈国良 《并行计算机体系结构》高等教育出版社．
[36] Doreen L. Galli著徐良贤等译 《分布式操作系统原理及实践》
(《Distributed Operating System Concepts and Practice》) .
[37] (美)Erez Zadok；邱仲潘等译《Linux网络文件系统管理指南》电子工业出版社．
[38] B.Narendran.Data Distribution Algorithms for Load Balanced Fauld-Tolerant Web Access 1997 IEEE.
[39] Abdelnaser Adas, Traffic Models in Broadband Networks NCR-9396299,GIT-CC-96-01,NOV 1997
[40] Martic F.Arliot et al.Web Server Workload Characterization: The Search For invariants,In Proceeding of the ACM SIGMETRICS'96 Conference,Philadelphia,PA,April 1996.
[41] Coda分布式文件系统www.coda.cs.cmu.edu.
[42] 李双庆 古平 程代杰 Web集群系统负载均衡策略分析与研究．
[43] 李傲雷 李治柱 分布式Web服务器负载均衡策略的仿真与应用．
[44] 林闯《Web服务器集群请求分配和选择的性能分析》计算机学报．
[45] 沈恒范《概率论与数理统计》高教出版社．
[46] Chu-Sing Yang and Mon-Yen Luo.Efficient Content Placement and Management on Cluster-based Web Servers. 0-7803-5864-3 2000 IEEE.
[47] Li-Chuan Chen Hyeong-Ah Choi. Approximation Algorithms for Data Distribution with Load Balancing of Web Servers. International Conference on Cluster Computing. 2002 IEEE.
[48] Chu-Sing Yang and Mon-Yen Luo. A Content Placement and Management System for Distributes Web-Server Systems.
[49] 李定锁 郭成城 晏蒲柳《Web服务器集群中的文件优化分配》计算机工程与应用 2004年16期
[50] Ben Chung-Pun Ng and Cho-li Wang.Document Distribution Algorithm for Load Balancing on an Extensible Web Server Architecture. 2002 IEEE.
[51] 孟祥武 程虎．利用遗传算法求解文件分配问题．软件学报1997年2月8卷2期。
[52] 李敏强 寇纪凇 林丹 李书全《遗传算法的基本理论与应用》科学出版社．
[53] Robert Kostelac Gordan Gledec. Balancing Web Server Workload Using Genetic Algorithms.
[54] Thomas V.Huynh.Optimal File Allocation in a Distribution Conputer Net Work by Orthogonal Array Experiments. 1997 IEEE.
[55] 张玉洁 高建明．基于模拟退火的文件优化分配．新疆大学学报14卷2期．
[56] Tao Zhao and Vijay Karamcheti. Enforcing Resource Sharing Agreements among Distributed Server Clusters. Computer Society 2002 IEEE.
[57] Akiko Nakaniwa Masaki Onishi Hiroyuki Ebara Hiromi Okada. Sensitivity Analysis of File Allocation for Distributed Information Networks. 1999 IEEE.
[58] Akiko Nakaniwa Masaki Ohnishi, Hiroyuki Ebara, Hiromi Okada.File Allocation in Distributed Multimedia Information Networks. 1998 IEEE.
[59] Randal C.Burns, Robert M.Rees, Darrel D.E.Long. Efficient Data Distribution in a Web Server Farm. INTERNET COMPUTING 2001 IEEE.
[60] Virv V.Phoha S.Sitharama lyengar and Raigopal Kannan. Faster web Page Allocation with Neural Networks. INTERNET COMPUTING 2002 IEEE.