分布式系统中的主机负载预测与动态负载均衡研究
|
摘要
动态负载均衡是网络计算的关键技术，如何提高动态负载均衡的性能，一直是网络计算人员研究的一个热点。传统的动态负载均衡方法总是收集结点负载的实时值作为任务在各结点分配的依据，但这种方法会产生决策时延，造成进程抖动现象，使均衡系统的性能大大下降。如果我们能准确地衡量和预测结点的负载，并结合负载均衡策略，将有效解决以上问题，大大提高网络计算的性能。
基于这种思想，本文运用数学、统计学、人工智能学等多学科的知识建立了多种预测主机负载的预测模型，主要包括传统的线性时间序列模型、特殊的自我平衡及趋势预测时间序列模型、神经网络BP模型。本文通过实验评估比较了这些预测模型的预测性能，获得了各预测模型的优劣，从中选择了具有较佳预测性能的时间序列AR、混合趋势预测MT、神经网络BP三种预测模型构建了预测模型模板库。
在获得良好预测模型的基础上，本文建立了HLPS(Host Load Prediction System)模型体系，并开发了应用于LINUX分布式环境的HLPS软件包，可以对主机负载进行实时在线预测。然后，本文应用HLPS成果，提出了基于负载预测的任务运行时间预测理论，这和传统的针对特定应用构建性能模型以预测任务运行时间的方法相比，在预测简易性、可操作性上有了较大的提高。最后，本文把负载预测和动态负载均衡有效结合起来，提出了一种高效的基于负载预测的动态负载均衡算法，该算法使用预测的方法获得负载信息，并采取了改进型接收者驱动策略。经性能分析和实验评估，这种方法与传统的动态负载均衡方法相比具有一定的优越性，有效地提高了动态负载均衡系统的性能。
Dynamic load balancing is the crucial technology on Network Computing,and how to improve the performance of dynamic load balancing is the research emphasis of the people working on Network Computing.Traditional dynamic load balancing methods have always collected the real time values of the node load on the grounds of task distributed on each node,But,this method may produce decision-making delay,and cause task-migration vibration,and then greatly degrade the performance of balancing system.If we can accurately measure and predict node load,and incorporate dynamic load balancing strategy,we should availably resolve above problem, and markedly improve the performance of Network Computing.
Based on this idea,we utilize multi-discipline knowledge including maths,statistics,and artificial intelligence to construct many kinds of prediction models,such as traditional time series models,homeostatic and tendency-based time-series models,neural networks BP model.We compare these prediction models and get its performance by testing evaluation, then we choose some benign prediction models includeing AR,MT,BP to build the prediction models template.
We thus construct HLPS framework, and develop HLPS software packages in linux distributed environment, the software may provide real-time on line prediction on host load.Afterwards,we rest on HLPS to expound the theory on prediction on the running time of task,this method has some improvement in facility and operation compared with traditional methods that construct performance model for given applications.Ultimately,we effectively combine load prediction with dynamic load balancing to propose prediction-based dynamic load balancing method that get load information by prediction and adopt reformative receiver-initiated strategy. According to performance analysis and experiment evaluation,this method is superior,and improve the performance of dynamic load balancing systems.
基于这种思想，本文运用数学、统计学、人工智能学等多学科的知识建立了多种预测主机负载的预测模型，主要包括传统的线性时间序列模型、特殊的自我平衡及趋势预测时间序列模型、神经网络BP模型。本文通过实验评估比较了这些预测模型的预测性能，获得了各预测模型的优劣，从中选择了具有较佳预测性能的时间序列AR、混合趋势预测MT、神经网络BP三种预测模型构建了预测模型模板库。
在获得良好预测模型的基础上，本文建立了HLPS(Host Load Prediction System)模型体系，并开发了应用于LINUX分布式环境的HLPS软件包，可以对主机负载进行实时在线预测。然后，本文应用HLPS成果，提出了基于负载预测的任务运行时间预测理论，这和传统的针对特定应用构建性能模型以预测任务运行时间的方法相比，在预测简易性、可操作性上有了较大的提高。最后，本文把负载预测和动态负载均衡有效结合起来，提出了一种高效的基于负载预测的动态负载均衡算法，该算法使用预测的方法获得负载信息，并采取了改进型接收者驱动策略。经性能分析和实验评估，这种方法与传统的动态负载均衡方法相比具有一定的优越性，有效地提高了动态负载均衡系统的性能。
Dynamic load balancing is the crucial technology on Network Computing,and how to improve the performance of dynamic load balancing is the research emphasis of the people working on Network Computing.Traditional dynamic load balancing methods have always collected the real time values of the node load on the grounds of task distributed on each node,But,this method may produce decision-making delay,and cause task-migration vibration,and then greatly degrade the performance of balancing system.If we can accurately measure and predict node load,and incorporate dynamic load balancing strategy,we should availably resolve above problem, and markedly improve the performance of Network Computing.
Based on this idea,we utilize multi-discipline knowledge including maths,statistics,and artificial intelligence to construct many kinds of prediction models,such as traditional time series models,homeostatic and tendency-based time-series models,neural networks BP model.We compare these prediction models and get its performance by testing evaluation, then we choose some benign prediction models includeing AR,MT,BP to build the prediction models template.
We thus construct HLPS framework, and develop HLPS software packages in linux distributed environment, the software may provide real-time on line prediction on host load.Afterwards,we rest on HLPS to expound the theory on prediction on the running time of task,this method has some improvement in facility and operation compared with traditional methods that construct performance model for given applications.Ultimately,we effectively combine load prediction with dynamic load balancing to propose prediction-based dynamic load balancing method that get load information by prediction and adopt reformative receiver-initiated strategy. According to performance analysis and experiment evaluation,this method is superior,and improve the performance of dynamic load balancing systems.
引文
[1]刘振英，方滨兴，胡铭曾，等．一种有效的动态负载平衡方法．软件学报，2001，12(4)：563～569
[2]X.Zhang,M.Barrientos,J.Chen, et al. HACC: An Architecture for Cluster-Based Web Server. Proceedings of the Third USENLX Windows NT Sysposium, July, 1999: 155～164
[3]邸烁，郑纬民，王鼎兴，等．并行WWW服务器集群请求分配算法的研究。软件学报，1999，10(7)：713～718
[4]Lin F C H, Keller R M. The gradient model load balancing method. IEEE Transaction on Software Engineering, 1987, SE-13 (1): 32～38
[5]Shu W, Kate L V. A dynamic scheduling strategy for the Chare-Kernei system. In Proceedings of Supercomputing'89, Reno, Nevada, Nov, 1989:389～398
[6]陈华平，计永昶，陈国良．分布式动态负载平衡调度的一个通用模型．软件学报，1998，9(1)：25～29
[7]Rich Wolski. Dynamically forecasting network performance using the network weather service. Cluster Computing, 1998, 1(1): 119～132
[8]Martin Quinson. Dynamic Performance Forecasting for Network-Enabled Servers in a Metacomputing Environment. PMEO-PDS'02, April, 2002:15～19
[9]P. Dinda, D. O' Halloran. The statistical properties of host load. CMU Technical Report CMU-CS-TR-98-175
[10]P. Dinda, David R. O'Hallaron. An Evaluation of Linear Models for Host Load Prediction. CMU-CS-98-148
[11]P. Dinda, David R. O'Halloran. An Extensible Toolkit for Resource Prediction In Distributed Systems. CMU-CS-99-138
[12]LOWEKAMP, B., MILLER, N., SUTHERLAND, D., et al. A resource monitoring system for network-aware applications. HPDC, July, 1998, IEEE:189～196
[13]Zinky JA, Bakken DE, Schantz RE. Architectural support for quality of service for CORBA objects. Theory and Practice of Object Systems, April, 1997, 3 (1):1～20
[14]Rich Wolski, Neil Spring, Jim Hayes. Predicting the CPU availability of time-shared Unix systems. HPDC, August, 1999:35～51
[15]S. Vazhkudai, J.M. Schopf, I. Foster. Predicting the Performance of Wide Area Data Transfers. IPDPS, April, 2002:15～19
[16]Lingyun Yang, Ian Foster, Jennifer M. Schopf. Homeostatic and Tendency-based CPU Load Predictions. IPDPS, April, 2003:22～26
[17]李庆华，郭志鑫．一种面向工作站网络的系统负载预测方法．华中科技大学学报(自然科学版)，2002，30(6)：49～51
[18]许建峰，朱晴波，胡宁，等．分布式实时系统中的预测调度算法．软件学报，2000，11(1)：95～103
[19]Hans-Martin Krolzing. Time Series and Dynamic Models. Cambridge University Press, 1997. Chapters 1, 5, 6, 9
[20]Hamilton, J.D. Time Series Analysis. Princeton University Press, 1994. Chapters 1-5,7,8, 11
[21]David．Kleinbaum，Lawrence L．Kupper，Keith E．Mullerl，et al．应用回归分析和其他多元方法(英文版·第3版)．机械工业出版社，2003．20～315
[22]Simon Haykin．神经网络原理(叶世伟，史忠植译)．机械工业出版社，2004．5～260
[23]Dinda, David. R. O'Hallaron. Realistic CPU Workloads Through Host Load Trace Playback. LCR, 2000: 246-259. or www.cs.nwu.edu/～pdinda/LoadTraces
[24]Jennifer M. Schopf, Francine Berman. Performance Prediction in Production Environments. IPPS/SPDP, 1998:67～92
[25]Jennifer M. Schopf. Structural Prediction Models for High-Performance Distributed Applications. Proceedings of the Cluster Computing Conference (CCC '97), March, 1997:26～44
[26]Dinda,David R. O'Hallaron. An Evaluation of Linear Models for Host Load Prediction. CMU-CS-98-148
[27]Soumen Chakrabarti et al. Randomized Load Balancing for tree-structured compution. Proceedings of the International Conference'94 on Parallel Distributed Systems, Hsinchu, Taiwan, Dec, 1994:19～21
[28]傅强，郑纬民．一种适用于机群系统的动态任务调度方法．软件学报，1999，10(1)：19～23
[29]刘振英，方滨兴，胡铭曾，等．一个有效的动态负载平衡方法．软件学报，2001，12(4)：563～569
[30]陈志刚，李登，曾志文．分布式系统中一种动态负载均衡策略、相关模型及算法研究．小型微型计算机系统，2002，12(23)：1434～1437
[31]Campos L M, Scherson I D. Rate of change load balancing in distributed and parallel system. Parallel Computing, 2000, 26:1213～1230
[32]Zaki,M.J, Li,W, Parthasarathy, S. Customized Dynamic Load Balancing for a Network of workstations. Journal of Parallel and Distributed Computing, 1997, 43(2):156～162
[33]W. Leland, T. Ott. Load-balancing heuristics and process behavior. In Proceedings of Performance and ACM Sigmentrics, May, 1986:54～69
[34]Eager, D. L., E. D. Lazowska, J. Zahorjan. The limited performance benefits of migrating active processes for load sharing. SIGMETRICS '88, 1988:63～72
[35]M. Mutka, M Livny. The available capacity of a privately owned workstation environment. Performance Evaluation, July, 1991, 12 (4): 269～284
[36]M. Harchol-Balter, A. Downey. Exploiting process lifetime distributions for dynamic load balancing. In Proceedings of the 1996 ACM SIGMETRICS Conference, May, 1996: 13～24
[37]Lingyun Yang,Jennifer M. Schopf, Ian Foster. Conservative Scheduling:Using Predicted Variance to Improve Scheduling Decision in Dynamic Enviroments. HPDC,February, 2003:45～69
[38]Byoung-Dai Leel, Jennifer M. Schopf. Run-Time Prediction of Parallel Applications on Shared Environments. HPDC, February, 2003:22～39
[39]Jennifer M. Schopf. Using Stochastic Information To Predict Application
Behavior On Contended Resources. International Journal of Foundations of Computer Science, 2001, 12 (3): 341～363
[40]Jennifer M. Schopf,Francine Berman. Using Stochastic Intervals to Predict Application Behavior on Contended Resources. In Proceedings of IPPS/SPDP '98,1997. SB99
[41]G.Manimaran, C.Siva Ram Murthy. an efficient dynamic scheduling algotithm for multiprocessor real-time systems. IEEE Trans. Parallel and Distributed systems, March1998, 9 (3): 312～319
[42]Xiao Qin,Hong Jiang. Dynamic, Reliability-driven Scheduling of Parallel Real-time Jobs in Heterogeneous Systems. International Conference on Parallel Processing (ICPP '01), September 2001: 03-07
[43]陈志刚，李登，曾志文．分布式系统中动态负载均衡实现模型．中南工业大学学报，2001，32(6)：635～639
[44]毛国君，杨名生，王秀坤，等．分布式系统中的双向启动自适应任务分配算法．计算机学报，1996，19(7)：514～519
[45]杨孟洲，姜晓红，潘志庚，等．分布式虚拟环境中的信息服务和资源定位．计算机研究与发展，2000，37(10)：1227～1232
[46]刘红霞，李东，胡铭曾．工作站网络中负载参数的一种收集方法．小型微型计算机系统，2000，21(3)：261～263
[2]X.Zhang,M.Barrientos,J.Chen, et al. HACC: An Architecture for Cluster-Based Web Server. Proceedings of the Third USENLX Windows NT Sysposium, July, 1999: 155～164
[3]邸烁，郑纬民，王鼎兴，等．并行WWW服务器集群请求分配算法的研究。软件学报，1999，10(7)：713～718
[4]Lin F C H, Keller R M. The gradient model load balancing method. IEEE Transaction on Software Engineering, 1987, SE-13 (1): 32～38
[5]Shu W, Kate L V. A dynamic scheduling strategy for the Chare-Kernei system. In Proceedings of Supercomputing'89, Reno, Nevada, Nov, 1989:389～398
[6]陈华平，计永昶，陈国良．分布式动态负载平衡调度的一个通用模型．软件学报，1998，9(1)：25～29
[7]Rich Wolski. Dynamically forecasting network performance using the network weather service. Cluster Computing, 1998, 1(1): 119～132
[8]Martin Quinson. Dynamic Performance Forecasting for Network-Enabled Servers in a Metacomputing Environment. PMEO-PDS'02, April, 2002:15～19
[9]P. Dinda, D. O' Halloran. The statistical properties of host load. CMU Technical Report CMU-CS-TR-98-175
[10]P. Dinda, David R. O'Hallaron. An Evaluation of Linear Models for Host Load Prediction. CMU-CS-98-148
[11]P. Dinda, David R. O'Halloran. An Extensible Toolkit for Resource Prediction In Distributed Systems. CMU-CS-99-138
[12]LOWEKAMP, B., MILLER, N., SUTHERLAND, D., et al. A resource monitoring system for network-aware applications. HPDC, July, 1998, IEEE:189～196
[13]Zinky JA, Bakken DE, Schantz RE. Architectural support for quality of service for CORBA objects. Theory and Practice of Object Systems, April, 1997, 3 (1):1～20
[14]Rich Wolski, Neil Spring, Jim Hayes. Predicting the CPU availability of time-shared Unix systems. HPDC, August, 1999:35～51
[15]S. Vazhkudai, J.M. Schopf, I. Foster. Predicting the Performance of Wide Area Data Transfers. IPDPS, April, 2002:15～19
[16]Lingyun Yang, Ian Foster, Jennifer M. Schopf. Homeostatic and Tendency-based CPU Load Predictions. IPDPS, April, 2003:22～26
[17]李庆华，郭志鑫．一种面向工作站网络的系统负载预测方法．华中科技大学学报(自然科学版)，2002，30(6)：49～51
[18]许建峰，朱晴波，胡宁，等．分布式实时系统中的预测调度算法．软件学报，2000，11(1)：95～103
[19]Hans-Martin Krolzing. Time Series and Dynamic Models. Cambridge University Press, 1997. Chapters 1, 5, 6, 9
[20]Hamilton, J.D. Time Series Analysis. Princeton University Press, 1994. Chapters 1-5,7,8, 11
[21]David．Kleinbaum，Lawrence L．Kupper，Keith E．Mullerl，et al．应用回归分析和其他多元方法(英文版·第3版)．机械工业出版社，2003．20～315
[22]Simon Haykin．神经网络原理(叶世伟，史忠植译)．机械工业出版社，2004．5～260
[23]Dinda, David. R. O'Hallaron. Realistic CPU Workloads Through Host Load Trace Playback. LCR, 2000: 246-259. or www.cs.nwu.edu/～pdinda/LoadTraces
[24]Jennifer M. Schopf, Francine Berman. Performance Prediction in Production Environments. IPPS/SPDP, 1998:67～92
[25]Jennifer M. Schopf. Structural Prediction Models for High-Performance Distributed Applications. Proceedings of the Cluster Computing Conference (CCC '97), March, 1997:26～44
[26]Dinda,David R. O'Hallaron. An Evaluation of Linear Models for Host Load Prediction. CMU-CS-98-148
[27]Soumen Chakrabarti et al. Randomized Load Balancing for tree-structured compution. Proceedings of the International Conference'94 on Parallel Distributed Systems, Hsinchu, Taiwan, Dec, 1994:19～21
[28]傅强，郑纬民．一种适用于机群系统的动态任务调度方法．软件学报，1999，10(1)：19～23
[29]刘振英，方滨兴，胡铭曾，等．一个有效的动态负载平衡方法．软件学报，2001，12(4)：563～569
[30]陈志刚，李登，曾志文．分布式系统中一种动态负载均衡策略、相关模型及算法研究．小型微型计算机系统，2002，12(23)：1434～1437
[31]Campos L M, Scherson I D. Rate of change load balancing in distributed and parallel system. Parallel Computing, 2000, 26:1213～1230
[32]Zaki,M.J, Li,W, Parthasarathy, S. Customized Dynamic Load Balancing for a Network of workstations. Journal of Parallel and Distributed Computing, 1997, 43(2):156～162
[33]W. Leland, T. Ott. Load-balancing heuristics and process behavior. In Proceedings of Performance and ACM Sigmentrics, May, 1986:54～69
[34]Eager, D. L., E. D. Lazowska, J. Zahorjan. The limited performance benefits of migrating active processes for load sharing. SIGMETRICS '88, 1988:63～72
[35]M. Mutka, M Livny. The available capacity of a privately owned workstation environment. Performance Evaluation, July, 1991, 12 (4): 269～284
[36]M. Harchol-Balter, A. Downey. Exploiting process lifetime distributions for dynamic load balancing. In Proceedings of the 1996 ACM SIGMETRICS Conference, May, 1996: 13～24
[37]Lingyun Yang,Jennifer M. Schopf, Ian Foster. Conservative Scheduling:Using Predicted Variance to Improve Scheduling Decision in Dynamic Enviroments. HPDC,February, 2003:45～69
[38]Byoung-Dai Leel, Jennifer M. Schopf. Run-Time Prediction of Parallel Applications on Shared Environments. HPDC, February, 2003:22～39
[39]Jennifer M. Schopf. Using Stochastic Information To Predict Application
Behavior On Contended Resources. International Journal of Foundations of Computer Science, 2001, 12 (3): 341～363
[40]Jennifer M. Schopf,Francine Berman. Using Stochastic Intervals to Predict Application Behavior on Contended Resources. In Proceedings of IPPS/SPDP '98,1997. SB99
[41]G.Manimaran, C.Siva Ram Murthy. an efficient dynamic scheduling algotithm for multiprocessor real-time systems. IEEE Trans. Parallel and Distributed systems, March1998, 9 (3): 312～319
[42]Xiao Qin,Hong Jiang. Dynamic, Reliability-driven Scheduling of Parallel Real-time Jobs in Heterogeneous Systems. International Conference on Parallel Processing (ICPP '01), September 2001: 03-07
[43]陈志刚，李登，曾志文．分布式系统中动态负载均衡实现模型．中南工业大学学报，2001，32(6)：635～639
[44]毛国君，杨名生，王秀坤，等．分布式系统中的双向启动自适应任务分配算法．计算机学报，1996，19(7)：514～519
[45]杨孟洲，姜晓红，潘志庚，等．分布式虚拟环境中的信息服务和资源定位．计算机研究与发展，2000，37(10)：1227～1232
[46]刘红霞，李东，胡铭曾．工作站网络中负载参数的一种收集方法．小型微型计算机系统，2000，21(3)：261～263