基于层次调度的网格结构模型及其资源预留技术的研究
|
摘要
资源管理是网格系统的最主要的关键技术之一,对于开发计算网格系统具有重大的理论意义和实用价值。资源管理包括资源的组织、定位、发现、调度、分配、确认、进程创建以及准备所需资源的其它活动。它提供了管理的功能和概念,使集群能够被当作单一资源,系统管理员根据预先定义好的标准通过资源管理软件确保资源的合理分配和使用,以最终达到资源共享的目的。为了让用户分配到合适的资源,完成用户递交的任务、并达到用户所希望的QoS,资源预留技术成为资源管理中不可回避的一个重要组成部分。
本文的主要工作是在传统的基于层次调度的网格模型—P2P-Grid之上,提出了一种新的网格结构模型Group-Grid,解决了传统网格结构模型中尚存的几个主要问题。并在该结构模型之上,提出了一种具体的资源预留机制。
本文提出的网格结构模型Group-Grid,是把网格中所有的资源按照资源提供者分为一个个的小型网格。该模型通过借用服务发现组件来达到快速查找资源的目的。改进了P2P-Grid使用泛洪法所导致的网络负担增大,查找周期过长的缺点。而且还具有扩展性强,易于调整等特点。而基于该结构模型的资源预留策略,是在现有的一般性预留策略的基础上,提出了任务分块、预留取消以及预留级别等概念,从而保证了资源预留的灵活性和可靠性,并提高了预留成功率和资源预留客户的QoS。另外,针对传统资源预留算法无法均衡网络整体资源利用的不足,本文还对现有的兼顾即时任务的资源预留算法进行改进,提出了一种改进的资源预留算法,通过将即时任务转化为预留任务提交到整个网络来减少即时任务的平均等待时间,而且能实现整个网络的负载均衡,提高网格的资源利用率。仿真结果表明,该资源预留策略比旧有的策略在预留成功率上提高了15%,在网络资源利用率上提高了5%。
Resource management is one of the most important key technologies, and it is of great theoretical practical value for the development of grid computing. Resource management includes resource organization, location, discovery, scheduling, allocation, confirmation, process creation, and other activities to prepare the necessary resources. It provides functions and concepts of management, so that clusters can be used as a single resource, and according to predefined criteria, the system administrator ensures the rational allocation and use of resources through resource management software, in order to eventually achieve the purpose of sharing resources. Resource reservation technology is an important part of resource management, so as to make users to have appropriate resources, complete the task which the users submitted, and achieve the QoS that users desired.
The goal of this paper is to give a new model Group-Grid based on traditional grid hierarchical scheduling model-"P2P-Grid", and it can solve the main problems in traditional grid model. Group-Grid use service discovery component to achieve quickly find resources. Moreover, it improved the performance to avoid network burden caused by flooding algorithm and long searching period. It's also scalable and easy to adjust. Based on the existing general strategy, this thesis put forward some new concepts such as task block; cancel reservation and the reservation level, for ensuring the flexibility and reliability of resource reservation. The resource reservation strategy improves reservation success rate as well as the entire grid resource reservation client QoS.
In addition, the traditional resource reservation algorithm cannot balance the lack of overall network resource utilization, and the existing resource reservation which including the task queue has been improved in this paper. And the paper gives an improved resource reservation algorithm and it can reduce the average waiting time for queued tasks by reserved for the task instead the task queue. It also can achieve load balancing of the network and improve the utilization of grid resources. Simulation results show that the resource reservation strategy than the old reservation on the success rate increased by 15%, improve the utilization of network resources by 5%.
本文的主要工作是在传统的基于层次调度的网格模型—P2P-Grid之上,提出了一种新的网格结构模型Group-Grid,解决了传统网格结构模型中尚存的几个主要问题。并在该结构模型之上,提出了一种具体的资源预留机制。
本文提出的网格结构模型Group-Grid,是把网格中所有的资源按照资源提供者分为一个个的小型网格。该模型通过借用服务发现组件来达到快速查找资源的目的。改进了P2P-Grid使用泛洪法所导致的网络负担增大,查找周期过长的缺点。而且还具有扩展性强,易于调整等特点。而基于该结构模型的资源预留策略,是在现有的一般性预留策略的基础上,提出了任务分块、预留取消以及预留级别等概念,从而保证了资源预留的灵活性和可靠性,并提高了预留成功率和资源预留客户的QoS。另外,针对传统资源预留算法无法均衡网络整体资源利用的不足,本文还对现有的兼顾即时任务的资源预留算法进行改进,提出了一种改进的资源预留算法,通过将即时任务转化为预留任务提交到整个网络来减少即时任务的平均等待时间,而且能实现整个网络的负载均衡,提高网格的资源利用率。仿真结果表明,该资源预留策略比旧有的策略在预留成功率上提高了15%,在网络资源利用率上提高了5%。
Resource management is one of the most important key technologies, and it is of great theoretical practical value for the development of grid computing. Resource management includes resource organization, location, discovery, scheduling, allocation, confirmation, process creation, and other activities to prepare the necessary resources. It provides functions and concepts of management, so that clusters can be used as a single resource, and according to predefined criteria, the system administrator ensures the rational allocation and use of resources through resource management software, in order to eventually achieve the purpose of sharing resources. Resource reservation technology is an important part of resource management, so as to make users to have appropriate resources, complete the task which the users submitted, and achieve the QoS that users desired.
The goal of this paper is to give a new model Group-Grid based on traditional grid hierarchical scheduling model-"P2P-Grid", and it can solve the main problems in traditional grid model. Group-Grid use service discovery component to achieve quickly find resources. Moreover, it improved the performance to avoid network burden caused by flooding algorithm and long searching period. It's also scalable and easy to adjust. Based on the existing general strategy, this thesis put forward some new concepts such as task block; cancel reservation and the reservation level, for ensuring the flexibility and reliability of resource reservation. The resource reservation strategy improves reservation success rate as well as the entire grid resource reservation client QoS.
In addition, the traditional resource reservation algorithm cannot balance the lack of overall network resource utilization, and the existing resource reservation which including the task queue has been improved in this paper. And the paper gives an improved resource reservation algorithm and it can reduce the average waiting time for queued tasks by reserved for the task instead the task queue. It also can achieve load balancing of the network and improve the utilization of grid resources. Simulation results show that the resource reservation strategy than the old reservation on the success rate increased by 15%, improve the utilization of network resources by 5%.
引文
[1]. Catlett C, Smarr L. Metacomputing. Communications of the ACM,1992,35(6):44-52.
[2]. Foster I, Kesselman C, Nick J M, et al. The physiology of the grid:An open grid services architecture for distributed systems integration. In: Berman F, Fox G, Hey A, eds. Grid computing:Making the global infrastructure a reality. Chichester:Wiley,2002.217-250.
[3]. Foster I, Kesselman C, Tuecke S. The anatomy of the grid:Enabling scalable virtual organizations. International Journal of High-performance Computing Application,2001,15(3):200-222.
[4]. Foster I, Kesselman C. The globus project:A status report. Future Generation Computer Systems,1999,15(5-6):607-621.
[5]. Czajkowski K, Foster I, Karonis N, et al. A resource management architecture for metacomputing systems. In:Feitelson D G, Rudolph L, eds. Job scheduling strategies for parallel processing, Lecture Notes in Computer Science 1459. Berlin:Springer-Verlag,1998.62-82.
[6]. Thain D, Tannenbaum T, Livny M. Condor and the grid. In:Berman F, Hey A, Fox G, eds. Grid computing-making the global infrastructure a reality. Chichester:Wiley,2003.299-337.
[7]. Min R, Maheswaran M. Scheduling co-reservations with priorities in grid computing systems. In:Proceedings of the 2nd IEEE/ACM International Symposium Cluster Computing and the Grid,Berlin,Germany,2002.Los Alamitos:IEEE Computer Society Press,2002.266-269.
[8]. Mateescu G. Quality of service on the grid via metascheduling with resource co-scheduling and co-reservation. International Journal of High Performance Computing Applications,2003,17(3):209-218.
[9]. Foster I, Fidler M, Roy A, et al. End-to-end quality of service for high-end applications. Computer Communications,2004,27(14):1375-1388.
[10]. Czajkowski K, Foster I, Kesselman C. Resource co-allocation in computational grids. In:Proceedings of the 8th International Symposium on High Performance Distributed Computing, Redondo Beach,CA,USA,1999.Los Alamitos:IEEE Computer Society Press,1999.219-228.
[11]. Foster I, Kesselman C. Globus:A Metacomputing Infrastructure Toolkit. Intl J. Supercompute Applications.1997,11 (2):115-128.
[12]. Grimshaw A. S, Wulf W. A. The Legion Vision of a World wide Virtual Computer. Communications o the ACM,1997,40(1):39-45.
[13]. Litzkow M. J, Livny M, Mutka M. W. Condor-A hunter of idle workstations. 8th International Conference on Distributed Computing Systems,1988,104-111.
[14]. Segal B. Grid Computing:The European Data Project, IEEE Nuclear Science Symposium and Medica Imaging Conference,Lyon,15-20 October 2000.
[15]. Open Grid Services Infrastructure(OGSI).2003.http://www.ggf.org/ogsi-wg.
[16]. Sato M, Nakada H, Sekiguchi S, et al. Ninf:A Network based Information Library for a Globa World-Wide Computing Infrastructure. In:Proceedings of HPCN'97(LNCS-1225),1997,491-502.
[17]. 徐志伟,李伟.织女星网格的体系结构研究[J].计算机研究与发展,2002,39(8).
[18]. Jon MacLaren. Advance reservations:state of the art. the GGF GRAAP-WG, Oct.4 2002.
[19]. 李波,支持网格资源预留的作业调度算法研究[学位论文],武汉,华中科技大学,2005.
[20]. P.Shenoy and H.Vin.Cello:A disk scheduling framework for next generation operating systems. Proc.ACM SIGMERICS'98,1998,pp.44-55
[21]. L.Zhang, S.Deering, D.Estrin, Shenker and D.Zappala. Resource Reservation Protocol(RSVP),IEEE Network, RFC 2205,Sep.1993
[22]. H.Chu and K.Nahrstedt. CPU service classes for multimedia applications. Proc. IEEE Int. Conf. On Multimedia Computing and System(ICMCS'99),1999 pp.296-301
[23]. G.Garimella. Advance CPU Reservations with the Dynamic Soft Real-Time Scheduler.Master's Thesis, University of Illinois at Urbana-Champaign, May 1999
[24]. K.Kim and K.Nahrstedt. A Resource Broker Model with Integrated Reserva-tion Scheme. IEEE International Conference on Multimedia and Expo2000(ICME'00),Aug.2000,pp.859-862
[25]. 叶从欢,P2P-Grid模型及其环境下资源管理关键技术研究[学位论文],成 都,电子科技大学,2004.
[26]. 裘楷,一种面向服务的P2P网格资源管理模型[学位论文],西安,西安电子科技大学,2007.
[27]. Barry G.Lawson and Evgenia Smirni. Multiple-queue Backfill Scheduling with Priorities and Reservation for Parallel Systems.8th Workshop on Job Scheduling Strategies for Parallel processing,2002
[28]. F.Azzedin and M.Maheswaran. Synchronous Queuing:A Co-allocation Mechanism for Multimedia Enabled Grids. Thirteenth IASTED International Conference on Parallel and Distributed Computing System(PDCS'01),Aug.2001,pp.27-32.
[29]. Gary Hoo and W.Johnston. QoS as middleware:bandwidth reservation system design. The Eighth IEEE International Symposium on High Performance Distributed Computing,Aug.1999
[30]. D.Xu, K.Nahrstedt, A.Viswanathan, D.Wichadkul. QoS and contention-aware multi-resource reservation. Proceedings of the 9th IEEE International Symposium on High Performance Distributed Computing (HPDC-9),Pittsburgh, PA,Aug.2001,pp.3-10
[31]. 蒲静,基于任务可分的网格资源预留机制[J].计算机工程与应用.2008.44(12).118-120.
[32]. 李冉,于炯,侯勇,在共享环境下基于时间预测的资源预留[J].现代计算机.291期.2008.9.4-6.
[33]. 胡志刚,谌任,一种兼顾即时任务的资源预留机制[J].计算机工程.2006.32(12).60-61.
[34]. 丁长松,胡志刚,胡周君,一种面向效益均衡的网格资源预留机制[J].小型微型计算机系统.2010.31(3).413-417.
[35]. 黄智兴,网格环境下基于经济机制的资源预留方法研究[学位论文],重庆,西南大学,2006.
[36]. 田东,陈蜀宇,吴长泽,基于间隔型双边拍卖的网格资源预留算法[J].计算机应用.2007.27(1).15-18.
[37]. 石晓晶,刘方爱,王胜川,基于双向拍卖的网格资源预留机制研究[J].网络与通信.2008.2.26-29.
[38]. 丁长松,胡志刚,胡周君,一种面向随机性负载的计算网格资源预留定价策略[J].计算机应用.2009.29(6).1711-1714.
[39]. 李静,韩起云,远程教育网格资源预留模型[J].计算机工
[40]. Foster I, Kesselman C. The Grid:Blueprint for a Future Computing Infrastructure[M].San Mateo:Morgan Kaufmann Publishers,1999.
[41]. Foster I, Kesselman C, Lee C, et al. A Distributed Resource Management Architecture That Supports Advance Reservations and Co-allocation[C].International Workshop on Quality of Service, London,U.K.,1999:27-36.
[42]. Dana Moore, John Hebeler. PEER-TO-PEER[M]苏忠,战晓雷等译.北京：清华大学出版社,2003.
[43]. Wolfgang Hoschek. A Unified Peer-to-Peer Database Framework for Scalable Service and ResourceDiscovery. http://dsd.lbl.gov/～hoschek/publications/ch6-grid2002.pdf.
[44]. Ian Foster, Adriana Ianmitch. A Peer-to-Peer Approach to Resource Location in Grid Environments http://people.cs.uchicago.edu/～anda/papers/iamnitchi-bookch.pdf.
[45]. Shrideep Pallickara, Geoffrey Fox. NaradaBrokering:A Distributed Middleware Framework and Architecture for Enabling Durable Peer-to-Peer Grids. http://grids.ucs.indiana.edu/ptliupages/publications/NB-Framework.pdf
[46]. 曹亮,王茜,卢菁.XML数据在关系数据库中存储和检索的研究和实现[J].东南大学学报(自然科学版),2002,(01).
[47]. 杨长兴,吕祯恒.一种统一的资源预留策略[J].计算机工程与应用.2005.24.144-146.
[48]. Smith V, Foster I, Taylor V. Scheduling with Advanced Reservation[C]. International Parallel and Distributed Processing Symposium,2000:127-132.
[49]. Sulistio A, Buyya R.A Grid Simulation Infrastructure Supporting Advance Reservation[C].Proceedings of the 16th International Conference on Parallel and Distributed Computing and Systems, MIT, Cambridge,USA,2004:1-7.
[2]. Foster I, Kesselman C, Nick J M, et al. The physiology of the grid:An open grid services architecture for distributed systems integration. In: Berman F, Fox G, Hey A, eds. Grid computing:Making the global infrastructure a reality. Chichester:Wiley,2002.217-250.
[3]. Foster I, Kesselman C, Tuecke S. The anatomy of the grid:Enabling scalable virtual organizations. International Journal of High-performance Computing Application,2001,15(3):200-222.
[4]. Foster I, Kesselman C. The globus project:A status report. Future Generation Computer Systems,1999,15(5-6):607-621.
[5]. Czajkowski K, Foster I, Karonis N, et al. A resource management architecture for metacomputing systems. In:Feitelson D G, Rudolph L, eds. Job scheduling strategies for parallel processing, Lecture Notes in Computer Science 1459. Berlin:Springer-Verlag,1998.62-82.
[6]. Thain D, Tannenbaum T, Livny M. Condor and the grid. In:Berman F, Hey A, Fox G, eds. Grid computing-making the global infrastructure a reality. Chichester:Wiley,2003.299-337.
[7]. Min R, Maheswaran M. Scheduling co-reservations with priorities in grid computing systems. In:Proceedings of the 2nd IEEE/ACM International Symposium Cluster Computing and the Grid,Berlin,Germany,2002.Los Alamitos:IEEE Computer Society Press,2002.266-269.
[8]. Mateescu G. Quality of service on the grid via metascheduling with resource co-scheduling and co-reservation. International Journal of High Performance Computing Applications,2003,17(3):209-218.
[9]. Foster I, Fidler M, Roy A, et al. End-to-end quality of service for high-end applications. Computer Communications,2004,27(14):1375-1388.
[10]. Czajkowski K, Foster I, Kesselman C. Resource co-allocation in computational grids. In:Proceedings of the 8th International Symposium on High Performance Distributed Computing, Redondo Beach,CA,USA,1999.Los Alamitos:IEEE Computer Society Press,1999.219-228.
[11]. Foster I, Kesselman C. Globus:A Metacomputing Infrastructure Toolkit. Intl J. Supercompute Applications.1997,11 (2):115-128.
[12]. Grimshaw A. S, Wulf W. A. The Legion Vision of a World wide Virtual Computer. Communications o the ACM,1997,40(1):39-45.
[13]. Litzkow M. J, Livny M, Mutka M. W. Condor-A hunter of idle workstations. 8th International Conference on Distributed Computing Systems,1988,104-111.
[14]. Segal B. Grid Computing:The European Data Project, IEEE Nuclear Science Symposium and Medica Imaging Conference,Lyon,15-20 October 2000.
[15]. Open Grid Services Infrastructure(OGSI).2003.http://www.ggf.org/ogsi-wg.
[16]. Sato M, Nakada H, Sekiguchi S, et al. Ninf:A Network based Information Library for a Globa World-Wide Computing Infrastructure. In:Proceedings of HPCN'97(LNCS-1225),1997,491-502.
[17]. 徐志伟,李伟.织女星网格的体系结构研究[J].计算机研究与发展,2002,39(8).
[18]. Jon MacLaren. Advance reservations:state of the art. the GGF GRAAP-WG, Oct.4 2002.
[19]. 李波,支持网格资源预留的作业调度算法研究[学位论文],武汉,华中科技大学,2005.
[20]. P.Shenoy and H.Vin.Cello:A disk scheduling framework for next generation operating systems. Proc.ACM SIGMERICS'98,1998,pp.44-55
[21]. L.Zhang, S.Deering, D.Estrin, Shenker and D.Zappala. Resource Reservation Protocol(RSVP),IEEE Network, RFC 2205,Sep.1993
[22]. H.Chu and K.Nahrstedt. CPU service classes for multimedia applications. Proc. IEEE Int. Conf. On Multimedia Computing and System(ICMCS'99),1999 pp.296-301
[23]. G.Garimella. Advance CPU Reservations with the Dynamic Soft Real-Time Scheduler.Master's Thesis, University of Illinois at Urbana-Champaign, May 1999
[24]. K.Kim and K.Nahrstedt. A Resource Broker Model with Integrated Reserva-tion Scheme. IEEE International Conference on Multimedia and Expo2000(ICME'00),Aug.2000,pp.859-862
[25]. 叶从欢,P2P-Grid模型及其环境下资源管理关键技术研究[学位论文],成 都,电子科技大学,2004.
[26]. 裘楷,一种面向服务的P2P网格资源管理模型[学位论文],西安,西安电子科技大学,2007.
[27]. Barry G.Lawson and Evgenia Smirni. Multiple-queue Backfill Scheduling with Priorities and Reservation for Parallel Systems.8th Workshop on Job Scheduling Strategies for Parallel processing,2002
[28]. F.Azzedin and M.Maheswaran. Synchronous Queuing:A Co-allocation Mechanism for Multimedia Enabled Grids. Thirteenth IASTED International Conference on Parallel and Distributed Computing System(PDCS'01),Aug.2001,pp.27-32.
[29]. Gary Hoo and W.Johnston. QoS as middleware:bandwidth reservation system design. The Eighth IEEE International Symposium on High Performance Distributed Computing,Aug.1999
[30]. D.Xu, K.Nahrstedt, A.Viswanathan, D.Wichadkul. QoS and contention-aware multi-resource reservation. Proceedings of the 9th IEEE International Symposium on High Performance Distributed Computing (HPDC-9),Pittsburgh, PA,Aug.2001,pp.3-10
[31]. 蒲静,基于任务可分的网格资源预留机制[J].计算机工程与应用.2008.44(12).118-120.
[32]. 李冉,于炯,侯勇,在共享环境下基于时间预测的资源预留[J].现代计算机.291期.2008.9.4-6.
[33]. 胡志刚,谌任,一种兼顾即时任务的资源预留机制[J].计算机工程.2006.32(12).60-61.
[34]. 丁长松,胡志刚,胡周君,一种面向效益均衡的网格资源预留机制[J].小型微型计算机系统.2010.31(3).413-417.
[35]. 黄智兴,网格环境下基于经济机制的资源预留方法研究[学位论文],重庆,西南大学,2006.
[36]. 田东,陈蜀宇,吴长泽,基于间隔型双边拍卖的网格资源预留算法[J].计算机应用.2007.27(1).15-18.
[37]. 石晓晶,刘方爱,王胜川,基于双向拍卖的网格资源预留机制研究[J].网络与通信.2008.2.26-29.
[38]. 丁长松,胡志刚,胡周君,一种面向随机性负载的计算网格资源预留定价策略[J].计算机应用.2009.29(6).1711-1714.
[39]. 李静,韩起云,远程教育网格资源预留模型[J].计算机工
[40]. Foster I, Kesselman C. The Grid:Blueprint for a Future Computing Infrastructure[M].San Mateo:Morgan Kaufmann Publishers,1999.
[41]. Foster I, Kesselman C, Lee C, et al. A Distributed Resource Management Architecture That Supports Advance Reservations and Co-allocation[C].International Workshop on Quality of Service, London,U.K.,1999:27-36.
[42]. Dana Moore, John Hebeler. PEER-TO-PEER[M]苏忠,战晓雷等译.北京：清华大学出版社,2003.
[43]. Wolfgang Hoschek. A Unified Peer-to-Peer Database Framework for Scalable Service and ResourceDiscovery. http://dsd.lbl.gov/～hoschek/publications/ch6-grid2002.pdf.
[44]. Ian Foster, Adriana Ianmitch. A Peer-to-Peer Approach to Resource Location in Grid Environments http://people.cs.uchicago.edu/～anda/papers/iamnitchi-bookch.pdf.
[45]. Shrideep Pallickara, Geoffrey Fox. NaradaBrokering:A Distributed Middleware Framework and Architecture for Enabling Durable Peer-to-Peer Grids. http://grids.ucs.indiana.edu/ptliupages/publications/NB-Framework.pdf
[46]. 曹亮,王茜,卢菁.XML数据在关系数据库中存储和检索的研究和实现[J].东南大学学报(自然科学版),2002,(01).
[47]. 杨长兴,吕祯恒.一种统一的资源预留策略[J].计算机工程与应用.2005.24.144-146.
[48]. Smith V, Foster I, Taylor V. Scheduling with Advanced Reservation[C]. International Parallel and Distributed Processing Symposium,2000:127-132.
[49]. Sulistio A, Buyya R.A Grid Simulation Infrastructure Supporting Advance Reservation[C].Proceedings of the 16th International Conference on Parallel and Distributed Computing and Systems, MIT, Cambridge,USA,2004:1-7.
© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号 地址：北京市海淀区学院路29号 邮编：100083 电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700 |