Beowulf集群系统负载均衡问题研究
摘要
计算机集群系统是通过高速网络将一组PC或工作站连接起来构成的高可靠、可扩展的服务器系统。集群中各PC或工作站通过统一调度、协调运行达到高效并行处理的目的。Beowulf集群结构开放,具有较高的性能价格比,是典型的集群系统之一。集群系统负载均衡策略是目前集群系统研究的重要课题。
本文首先对Beowulf集群服务器负载均衡问题的相关理论进行了介绍与分析。然后从集群系统的服务器端出发,提出了一种基于遗传算法的Beowulf集群系统节点负载均衡算法,用节点的总体资源、CPU的就绪队列长度和节点的任务数来构造遗传算法的目标函数,既考虑了Beowulf集群异构的特点,又能很好地体现负载程度,通过使用网络压力测试工具对该算法进行性能测试,表明能够降低服务器端请求的响应时间,改善了系统性能。从客户端角度出发,提出了一种动态反馈自适应均衡改进算法,采用客户端下载速度来衡量节点的负载,通过仿真模拟表明该算法有效地达到均衡负载的目的,能够根据资源使用状况及时做出反应,从而为客户端提供良好的服务能力。
Computer cluster system is an expandable server system having high reliability which connects a group of PCs or workstations to build a high-speed network. These PCs and workstations are parallel handled by unified scheduling and coordinately running in the cluster system. Beowulf cluster system is more cost-effective than other cluster systems. It is a typical one of the most popular cluster system. And the load balance policy of it is an important subject of cluster system at present.
In this paper, an introduction and analysis of relative theory and principle is done about load balance problem of the cluster server. And then according to the research of cluster system server, a load balance algorithm for nodes of Beowulf cluster is proposed based on the genetic algorithm. The object function with the general resource of nodes is constructed with the length of ready array and the number of nod tasks, which not only considering the isomeric feature of Beowulf cluster, but also expressing the load extension. The network performance test with the net pressure testing tools has been made, which shows it can low the response time of the server to enhance the system performance. A dynamic feedback self-adapting updated algorithm is supposed considering the client, using the download speed to measure the load of nods. Simulation has indicated that this algorithm can obtain the load balance effectively, and can provide a good service effect for clients according the condition of resource scheduling.
本文首先对Beowulf集群服务器负载均衡问题的相关理论进行了介绍与分析。然后从集群系统的服务器端出发,提出了一种基于遗传算法的Beowulf集群系统节点负载均衡算法,用节点的总体资源、CPU的就绪队列长度和节点的任务数来构造遗传算法的目标函数,既考虑了Beowulf集群异构的特点,又能很好地体现负载程度,通过使用网络压力测试工具对该算法进行性能测试,表明能够降低服务器端请求的响应时间,改善了系统性能。从客户端角度出发,提出了一种动态反馈自适应均衡改进算法,采用客户端下载速度来衡量节点的负载,通过仿真模拟表明该算法有效地达到均衡负载的目的,能够根据资源使用状况及时做出反应,从而为客户端提供良好的服务能力。
Computer cluster system is an expandable server system having high reliability which connects a group of PCs or workstations to build a high-speed network. These PCs and workstations are parallel handled by unified scheduling and coordinately running in the cluster system. Beowulf cluster system is more cost-effective than other cluster systems. It is a typical one of the most popular cluster system. And the load balance policy of it is an important subject of cluster system at present.
In this paper, an introduction and analysis of relative theory and principle is done about load balance problem of the cluster server. And then according to the research of cluster system server, a load balance algorithm for nodes of Beowulf cluster is proposed based on the genetic algorithm. The object function with the general resource of nodes is constructed with the length of ready array and the number of nod tasks, which not only considering the isomeric feature of Beowulf cluster, but also expressing the load extension. The network performance test with the net pressure testing tools has been made, which shows it can low the response time of the server to enhance the system performance. A dynamic feedback self-adapting updated algorithm is supposed considering the client, using the download speed to measure the load of nods. Simulation has indicated that this algorithm can obtain the load balance effectively, and can provide a good service effect for clients according the condition of resource scheduling.
引文
[1]Korch M,Rauber T.Evaluation of Task Pools for the Implementation of Parallel Irregular Algorithms[C].Proceedings of the International Conference on Parallel Processing Workshops,2002,597-604.
[2]陈星.黄卡玛.构建基于Windows和MPI的Beowulf并行计算系统[J].计算机工程与应用.2003,39(11):59-61.
[3]Stevens R.Unix Network Programming(Volume Ⅰ):Networking APIs Sockets and XTI(Second Edition)协].Prentice-Hall,Inc.,1998.
[4]李贵明.俞国扬.罗家融.基于Linux的Beowulf集群的实现[J].计算机工程.2003,29(11):9-51.
[5]汪大清.关于计算机集群中的负载均衡探讨.福建电脑.2007,(2):68-68+79
[63 HU Jin-zhu,Xu Song.Dynamic Feedback Adjustment Adaptive Algorithm of Load Balancing in the Distributed System.MINI-MACRO SYSTEMS.2003,24(8):1510-1515.
[7]Thomas Kunz.The Influence of Different Workload Descriptions on a Heuristic Load Balancing Scheme[J].IEEE Trans on Software Engineering,1991,17(7):725-730.
[8]Chen Hua-ping,Huang Liu-sheng,Chen Guo-liang.Task scheduling in parallel and distributed computing(J].Computer Science,1999,26(6):33-36.
[9]Wang Shuang,Xiu Baoxin,Xiao Weidong.Research on Dynamic Load-balancing Algorithm for Web-Service Cluster System.Computer Engineering and Applications.2004.
[10]刘洋,周家启,谢开贵,等.基于Beowulf集群的大规模电力系统方程并行PCG求解.电工技术学报.2006,21(3):105-111.
[11]朱一群,朱秋萍.多媒体实时传输协议RTP的研究.计算机应用研究.2002,19(10):122-124
[12]董科军,南凯,阎保平.一种可扩展的集群Web服务器.计算机工程与应用.2003,39(25):46-49
[13]胡子昂,王立.算法,网络拓扑及调度频率与动态负载均衡的关系[J].计 算机工程与科学.2000,22(1):105-107.
[14]MAO rao,PAN Juan,ZHENG Gu-ping.Dynamic load balancing self-adapting algorithm in mufti-processor systems and its improvement.INFORMATION ON ELECTRIC POWER.2002,No.2.
[15]Peng Guozheng,Qiu Yulan:Peng Dechun.Several Random Load Balancing Algorithm.Computer Engineering.2001.2.
[16]汪东升,郑纬民.高可用集群计算.小型微型计算机系统.2001,21(11):1126-1129.
[17]Haakon Brhni A Comparison of LoadBaIancing Techniques for Scalable Web Servers University of Oslo EsPen Klovning and ivind Kure,Telenor Research and Development,IEEE Network July/August 2000.
[18]邸烁,郑纬民,王鼎兴,等,可扩展并行Web server集群技术,小型微型计算机系统.1999,20(10):721-725.
[19]马双良,张英敏,宋丽君.基于LVS和计算任务的实时集群负载均衡方法.计算机工程与设计.2007,28(20):4934-4937+5011
[20]Tu Yicheng,Lei Shan.Towards cost-effective on-demand continuous media service:a peer-to-peer approach.Purdue University,course project report.Fall 2002
[21]何炎祥,宋文欣,郭锋.高级操作系统[M].北京:科学出版社,1999.
[22]Buyya R.High Performance Cluster Computing Architectures and Systems,Volume I.Posts&Telecommunications Press,2002.
[23]Buyya R.高性能集群计算:结构与系统(第一卷).郑纬民、石威、汪东升等译.电子工业出版社,2001.
[24]Wang L,Siegel H J,Roychowdhury V P A genetic-algorithm-based approachfor task matching and scheduling in heterogeneous computing environments[C].In:S'Heterogeneous Computing Workshop,1996.
[25]A Y Zomaya,C Ward,B Macey.Genetic Scheduling for Parallel Processor Systems:Comparative Studies and Performance Issues[J].IEEE Trans Parallel and distributed Systems,1999,10(8):795-812.
[26]胡玉兰,张丽萍.基于遗传算法的投资优化问题的应用研究[J].计算机工程与设计.2002,8(8):78-80.
[27]YANG Xiao,Guizani M.多尺度网络中具有全延迟约束的最佳分页负载均衡[J].IEEE无线通讯学报.2006,5(8):2202-2209(英文版)
[28]Huican Zhu,Tao Yang,Qi Zheng,David Watson,Oscar H.Ibarra, Terence R.Smith:Adaptive Load Sharing for Clustered Digital Library Servers.Int.J.on DigitalLibraries 2(4):225-235(2000).
[29]Yu Mei,Lin Zong-Kai,Guo Yu-Chai,Lin Shou-Xun.Load balancing and fault-tolerant services in multi-server system.Journal of System Simulation,2001
[30]刘永芳,刘丽,张乐英.遗传算法的新改进-扰动式遗传算法.合肥工业大学学报(自然科学版)).2003,26(4):614-618.
[31]Albert YZomaya,Yee-Hwei.The Observations on Using Genetic Algorithms for Dynamic Load-balancing[JJ.IEEE Trans.On Parallel and Distributed Systems,2001,12(9):899-911.
[32]LI Ren-fa,LI Hong,YU Fei,XU Cheng.An Intrusion Detection System Based on Load Balancing.Journal of System Simulation.2004,July,Vpl.16
[33]薛军,李增智,王云岚.负载均衡技术的发展.小型微型计算机系统.2003,24(12):2100-2103
[34]杨磊,郭庆平.负载均衡技术分析及LVS实现,武汉理工大学学报.2004,28(1):77-79
[35]冯晶,朱兰娟,吴智铭.分布式RAID中Cache模块的设计.计算机应用.,2005,25(2):475-477.
[36]Xue Guangtao,You Jinyuan,He Xiao jian.A stable group model based on mobile peer-to-peer.Jounal of Computer Research and Development,2003,40(12):1801-1805.
[37]ZHOU Jiliang,PENG Xiaoning,WANG Zhenghua.Research and implementation of cluster-based scheduling algorithms for load balancing.Computer Engineering.June 2005.
[38]刘健,徐磊,张维明.基于动态反馈的负载均衡算法.计算机工程与科学.,2003,25(5):65-68.
[39]Floyd S,Jackson V Random Early Detection Gateways for Congestion Avoidance.IEEEIACM Transaction on Networking,1993,1(4):397-413.
[40]谢高岗,阂应弊,张大方,等.一个基于实际测试的网络流量模型.计算机工程与科学.2001,23(5):51-53.
[41]Fuchs E.Jackson P E.Estimation of Distributions of Random Variables for Certain Computer Communication Traffic Models[J].Communication of ACM.1970,13(12):752-767.
[42]W E.Leland,M.S.Taqqu,W Willinger and D.V Wilson.On the Self-Similar Nature of Ethernet Traffic.IEEE/ACM Transactions on Networking,1994,2(1):1-15.
[43]P Abry and D.Veitch.Wavelet Analysis of Long-range-dependent Traffic.IEEE Trans on Information Theory,1998,44(1):2-15.
[44]覃少华,李子木,等.一种新的基于代理缓存的流媒体分送策略.计算机工程.2005,31(2):33-35.
[45]Chesire M,Wolman A,Voelker G M.Measurement and Analysis of a Streaming Media Workload.In Proceedings of the Third USENIX Symposium on Internet Technologies and Systems(USITS-01),2001,3.
[46]Chervenak A L,Tertiary storage:an evaluation of new applications(R].Computer Science Division Technical Report UDB/CSD 94!847,Berkley.PH.D Thesis,University of California,1994.
[47]Z.G.Coffman.Computer and job-shop scheduling theory[M].NewYork:Wiley,1976
[48]Yin-Fu Huang,Chih-Chiang Fang.Load balancing for clusters of VOD servers.Information Sciences,2004,113-138.
[49]朱福喜,何炎祥.并行分布计算中的调度算法理论与设计.武汉:武汉大学出版社,2003-05.
[50]Han Bin,Wang Shitong.Genetic Algorithm with Individual Adaptive Mutation Probability.COMPUTER ENGINEERING AND APPLICATIONS.2002.11
[51]唐世洁,朱启疆.遗传算法中初始种群与交叉、变异率对解的影响及其解决方案.科技通报.2001.17(3):1-7.
[52]周健,戴梅尊等.远程实时视频传输的自适应技术.清华大学学报(自然科学版)2004,44(7):103-105+110.
[53]舒万能,郑世汪,马卫,陈广东,杜建华.基于遗传算法的网格计算任务调度方法设计,WCACA06,大连,2006.6:15-18
[54]朱萍.多媒体课件点播系统视频服务器的负载均衡设计与实现:[硕士学位论文].北京:北京师范大学,2001.
[55]周远晖,陆玉昌,石纯一基于克服过早收敛的自适应并行遗传算法[J].清华大学学报(自然科学版),1998,38(3):93-95.
[56]陈斌全,罗省贤.基于热点内容的下载服务Web集群动态负载均衡.计算机应用.2004.24(4):106-108.
[57]Cherkasova L,Phaal P Session Based Admission Control:a Mechanism for Peak Load Management of Commercial Web Sites.IEEE Transactions on Computers,2002,51(6).
[58]http://www.isi.edu/nsnam/ns/.
[59]http://140.116.72.80/~smallko/ns2/ns2,htm
[60]刘安丰,陈志刚,邓晓衡,等.基于cache优化的Web集群负载均衡算法.计算机工程.2004,30(10):12-13.
[2]陈星.黄卡玛.构建基于Windows和MPI的Beowulf并行计算系统[J].计算机工程与应用.2003,39(11):59-61.
[3]Stevens R.Unix Network Programming(Volume Ⅰ):Networking APIs Sockets and XTI(Second Edition)协].Prentice-Hall,Inc.,1998.
[4]李贵明.俞国扬.罗家融.基于Linux的Beowulf集群的实现[J].计算机工程.2003,29(11):9-51.
[5]汪大清.关于计算机集群中的负载均衡探讨.福建电脑.2007,(2):68-68+79
[63 HU Jin-zhu,Xu Song.Dynamic Feedback Adjustment Adaptive Algorithm of Load Balancing in the Distributed System.MINI-MACRO SYSTEMS.2003,24(8):1510-1515.
[7]Thomas Kunz.The Influence of Different Workload Descriptions on a Heuristic Load Balancing Scheme[J].IEEE Trans on Software Engineering,1991,17(7):725-730.
[8]Chen Hua-ping,Huang Liu-sheng,Chen Guo-liang.Task scheduling in parallel and distributed computing(J].Computer Science,1999,26(6):33-36.
[9]Wang Shuang,Xiu Baoxin,Xiao Weidong.Research on Dynamic Load-balancing Algorithm for Web-Service Cluster System.Computer Engineering and Applications.2004.
[10]刘洋,周家启,谢开贵,等.基于Beowulf集群的大规模电力系统方程并行PCG求解.电工技术学报.2006,21(3):105-111.
[11]朱一群,朱秋萍.多媒体实时传输协议RTP的研究.计算机应用研究.2002,19(10):122-124
[12]董科军,南凯,阎保平.一种可扩展的集群Web服务器.计算机工程与应用.2003,39(25):46-49
[13]胡子昂,王立.算法,网络拓扑及调度频率与动态负载均衡的关系[J].计 算机工程与科学.2000,22(1):105-107.
[14]MAO rao,PAN Juan,ZHENG Gu-ping.Dynamic load balancing self-adapting algorithm in mufti-processor systems and its improvement.INFORMATION ON ELECTRIC POWER.2002,No.2.
[15]Peng Guozheng,Qiu Yulan:Peng Dechun.Several Random Load Balancing Algorithm.Computer Engineering.2001.2.
[16]汪东升,郑纬民.高可用集群计算.小型微型计算机系统.2001,21(11):1126-1129.
[17]Haakon Brhni A Comparison of LoadBaIancing Techniques for Scalable Web Servers University of Oslo EsPen Klovning and ivind Kure,Telenor Research and Development,IEEE Network July/August 2000.
[18]邸烁,郑纬民,王鼎兴,等,可扩展并行Web server集群技术,小型微型计算机系统.1999,20(10):721-725.
[19]马双良,张英敏,宋丽君.基于LVS和计算任务的实时集群负载均衡方法.计算机工程与设计.2007,28(20):4934-4937+5011
[20]Tu Yicheng,Lei Shan.Towards cost-effective on-demand continuous media service:a peer-to-peer approach.Purdue University,course project report.Fall 2002
[21]何炎祥,宋文欣,郭锋.高级操作系统[M].北京:科学出版社,1999.
[22]Buyya R.High Performance Cluster Computing Architectures and Systems,Volume I.Posts&Telecommunications Press,2002.
[23]Buyya R.高性能集群计算:结构与系统(第一卷).郑纬民、石威、汪东升等译.电子工业出版社,2001.
[24]Wang L,Siegel H J,Roychowdhury V P A genetic-algorithm-based approachfor task matching and scheduling in heterogeneous computing environments[C].In:S'Heterogeneous Computing Workshop,1996.
[25]A Y Zomaya,C Ward,B Macey.Genetic Scheduling for Parallel Processor Systems:Comparative Studies and Performance Issues[J].IEEE Trans Parallel and distributed Systems,1999,10(8):795-812.
[26]胡玉兰,张丽萍.基于遗传算法的投资优化问题的应用研究[J].计算机工程与设计.2002,8(8):78-80.
[27]YANG Xiao,Guizani M.多尺度网络中具有全延迟约束的最佳分页负载均衡[J].IEEE无线通讯学报.2006,5(8):2202-2209(英文版)
[28]Huican Zhu,Tao Yang,Qi Zheng,David Watson,Oscar H.Ibarra, Terence R.Smith:Adaptive Load Sharing for Clustered Digital Library Servers.Int.J.on DigitalLibraries 2(4):225-235(2000).
[29]Yu Mei,Lin Zong-Kai,Guo Yu-Chai,Lin Shou-Xun.Load balancing and fault-tolerant services in multi-server system.Journal of System Simulation,2001
[30]刘永芳,刘丽,张乐英.遗传算法的新改进-扰动式遗传算法.合肥工业大学学报(自然科学版)).2003,26(4):614-618.
[31]Albert YZomaya,Yee-Hwei.The Observations on Using Genetic Algorithms for Dynamic Load-balancing[JJ.IEEE Trans.On Parallel and Distributed Systems,2001,12(9):899-911.
[32]LI Ren-fa,LI Hong,YU Fei,XU Cheng.An Intrusion Detection System Based on Load Balancing.Journal of System Simulation.2004,July,Vpl.16
[33]薛军,李增智,王云岚.负载均衡技术的发展.小型微型计算机系统.2003,24(12):2100-2103
[34]杨磊,郭庆平.负载均衡技术分析及LVS实现,武汉理工大学学报.2004,28(1):77-79
[35]冯晶,朱兰娟,吴智铭.分布式RAID中Cache模块的设计.计算机应用.,2005,25(2):475-477.
[36]Xue Guangtao,You Jinyuan,He Xiao jian.A stable group model based on mobile peer-to-peer.Jounal of Computer Research and Development,2003,40(12):1801-1805.
[37]ZHOU Jiliang,PENG Xiaoning,WANG Zhenghua.Research and implementation of cluster-based scheduling algorithms for load balancing.Computer Engineering.June 2005.
[38]刘健,徐磊,张维明.基于动态反馈的负载均衡算法.计算机工程与科学.,2003,25(5):65-68.
[39]Floyd S,Jackson V Random Early Detection Gateways for Congestion Avoidance.IEEEIACM Transaction on Networking,1993,1(4):397-413.
[40]谢高岗,阂应弊,张大方,等.一个基于实际测试的网络流量模型.计算机工程与科学.2001,23(5):51-53.
[41]Fuchs E.Jackson P E.Estimation of Distributions of Random Variables for Certain Computer Communication Traffic Models[J].Communication of ACM.1970,13(12):752-767.
[42]W E.Leland,M.S.Taqqu,W Willinger and D.V Wilson.On the Self-Similar Nature of Ethernet Traffic.IEEE/ACM Transactions on Networking,1994,2(1):1-15.
[43]P Abry and D.Veitch.Wavelet Analysis of Long-range-dependent Traffic.IEEE Trans on Information Theory,1998,44(1):2-15.
[44]覃少华,李子木,等.一种新的基于代理缓存的流媒体分送策略.计算机工程.2005,31(2):33-35.
[45]Chesire M,Wolman A,Voelker G M.Measurement and Analysis of a Streaming Media Workload.In Proceedings of the Third USENIX Symposium on Internet Technologies and Systems(USITS-01),2001,3.
[46]Chervenak A L,Tertiary storage:an evaluation of new applications(R].Computer Science Division Technical Report UDB/CSD 94!847,Berkley.PH.D Thesis,University of California,1994.
[47]Z.G.Coffman.Computer and job-shop scheduling theory[M].NewYork:Wiley,1976
[48]Yin-Fu Huang,Chih-Chiang Fang.Load balancing for clusters of VOD servers.Information Sciences,2004,113-138.
[49]朱福喜,何炎祥.并行分布计算中的调度算法理论与设计.武汉:武汉大学出版社,2003-05.
[50]Han Bin,Wang Shitong.Genetic Algorithm with Individual Adaptive Mutation Probability.COMPUTER ENGINEERING AND APPLICATIONS.2002.11
[51]唐世洁,朱启疆.遗传算法中初始种群与交叉、变异率对解的影响及其解决方案.科技通报.2001.17(3):1-7.
[52]周健,戴梅尊等.远程实时视频传输的自适应技术.清华大学学报(自然科学版)2004,44(7):103-105+110.
[53]舒万能,郑世汪,马卫,陈广东,杜建华.基于遗传算法的网格计算任务调度方法设计,WCACA06,大连,2006.6:15-18
[54]朱萍.多媒体课件点播系统视频服务器的负载均衡设计与实现:[硕士学位论文].北京:北京师范大学,2001.
[55]周远晖,陆玉昌,石纯一基于克服过早收敛的自适应并行遗传算法[J].清华大学学报(自然科学版),1998,38(3):93-95.
[56]陈斌全,罗省贤.基于热点内容的下载服务Web集群动态负载均衡.计算机应用.2004.24(4):106-108.
[57]Cherkasova L,Phaal P Session Based Admission Control:a Mechanism for Peak Load Management of Commercial Web Sites.IEEE Transactions on Computers,2002,51(6).
[58]http://www.isi.edu/nsnam/ns/.
[59]http://140.116.72.80/~smallko/ns2/ns2,htm
[60]刘安丰,陈志刚,邓晓衡,等.基于cache优化的Web集群负载均衡算法.计算机工程.2004,30(10):12-13.