一种基于在线反向拍卖的计算网格资源分配方法
|
摘要
网格系统被定义为下一代的计算平台,用来解决科学和工程领域的大型问题。网格的最终目标是实现网络虚拟环境上的资源共享和协同工作,消除资源孤岛。资源分配和任务调度是网格计算系统中的两个关键技术。在传统的计算系统中所使用的资源管理协议的前提是可以完全控制所有资源,所以它们不能被简单的应用于复杂的网格环境中。因此,我们需要一种新的资源分配方法。
拍卖模型是解决网格资源分配难题的一个有效方法,因为它提供了一个分布式的结构,比其它经济模型容易实现,并且反映了资源所有者的自治权。网格资源的动态性要求资源所有者和网格用户通过某种机制在使用资源的数量和价格方面达成一致,拍卖模型提供了这种机制。但是,根据网格资源的自治性、动态性的特征,一些传统的拍卖协议在应用到网格环境中时存在一些瓶颈。
在本文中,我们根据计算网格环境中资源的动态性特征以及利用经济机制进行网格资源管理的优越性,提出了一种基于在线反向拍卖机制的计算网格资源分配方法。在这种方法中,代理人利用前边投标价格的均值作为后一个投标的定价;并且代理人在接收到资源提供者的投标后,可以立即作出该资源提供者是否中标的决策并通知资源提供者,这样就避免了先进行投标的资源提供者多余的等待时间。然后,我们证明这种方法满足经济学中激励相容的要求,即网格资源提供者会为了自己利益的最大化而报出自己真实的估价。最后,利用网格仿真工具Gridsim对所提出的网格资源分配方法进行模拟,验证了算法的正确性及其性能。
Grid systems are defined as next generation computing platforms for solving large scale problems in science and engineering.The final goal of Grid technology is to realize resource share and coordinating work in virtual network environment and eliminate the resource isolated island.Resource allocation and task scheduling are two key technologies in grid computing system.The resource management protocols used in traditional computing systems cannot be simply applied to complex Grid environments because they assume complete control over resources.Thus we need new resource allocation protocols.
Auctioning models are a source of solutions to the challenge of resource allocation in Grid because they provide a decentralized structure,are easier to implement than other economic models and respect the autonomy of resource owners.The dynamic nature of the Grid requires mechanisms where resource users and owners can agree upon the amount of resources they will use and the price paid for them.Auctions allow owners and users to establish prices to resources in the Grid.However,there are some bottlenecks in traditional auction protocols applying in grid environment because of the autonomous and dynamic characteristics of grid resources.
In this paper,an on-line reverse auction method of resource allocation for computational grids was proposed to solve the problem of resource management considering the autonomous and dynamic characteristics of computing resources in the computational grid environment and the advantages of economics mechanism.In this method,the current price can be set using former bids.And bidders arriving one by one the on-line buyer must be required to make a decision immediately about each bid as it is received.Then we prove that the algorithm is incentive compatible and simulate the auction protocol in Gridsim to evaluate the performance and accuracy of this method.
拍卖模型是解决网格资源分配难题的一个有效方法,因为它提供了一个分布式的结构,比其它经济模型容易实现,并且反映了资源所有者的自治权。网格资源的动态性要求资源所有者和网格用户通过某种机制在使用资源的数量和价格方面达成一致,拍卖模型提供了这种机制。但是,根据网格资源的自治性、动态性的特征,一些传统的拍卖协议在应用到网格环境中时存在一些瓶颈。
在本文中,我们根据计算网格环境中资源的动态性特征以及利用经济机制进行网格资源管理的优越性,提出了一种基于在线反向拍卖机制的计算网格资源分配方法。在这种方法中,代理人利用前边投标价格的均值作为后一个投标的定价;并且代理人在接收到资源提供者的投标后,可以立即作出该资源提供者是否中标的决策并通知资源提供者,这样就避免了先进行投标的资源提供者多余的等待时间。然后,我们证明这种方法满足经济学中激励相容的要求,即网格资源提供者会为了自己利益的最大化而报出自己真实的估价。最后,利用网格仿真工具Gridsim对所提出的网格资源分配方法进行模拟,验证了算法的正确性及其性能。
Grid systems are defined as next generation computing platforms for solving large scale problems in science and engineering.The final goal of Grid technology is to realize resource share and coordinating work in virtual network environment and eliminate the resource isolated island.Resource allocation and task scheduling are two key technologies in grid computing system.The resource management protocols used in traditional computing systems cannot be simply applied to complex Grid environments because they assume complete control over resources.Thus we need new resource allocation protocols.
Auctioning models are a source of solutions to the challenge of resource allocation in Grid because they provide a decentralized structure,are easier to implement than other economic models and respect the autonomy of resource owners.The dynamic nature of the Grid requires mechanisms where resource users and owners can agree upon the amount of resources they will use and the price paid for them.Auctions allow owners and users to establish prices to resources in the Grid.However,there are some bottlenecks in traditional auction protocols applying in grid environment because of the autonomous and dynamic characteristics of grid resources.
In this paper,an on-line reverse auction method of resource allocation for computational grids was proposed to solve the problem of resource management considering the autonomous and dynamic characteristics of computing resources in the computational grid environment and the advantages of economics mechanism.In this method,the current price can be set using former bids.And bidders arriving one by one the on-line buyer must be required to make a decision immediately about each bid as it is received.Then we prove that the algorithm is incentive compatible and simulate the auction protocol in Gridsim to evaluate the performance and accuracy of this method.
引文
[1]I Foster and C.Kesselman.The Grid:Blueprint for a New Computing Infrastructure.San Francisco,CA,USA:Morgan Kaufmann Publishers Inc.,1999.
[2]罗作民,张景,李军怀,谢长生.网格计算及其关键技术综述.计算机工程与应用,2003,39(30):18-22.
[3]Joshy J,Craig F著.战晓苏,张少华译 Grid Computing.北京:清华大学出版社,2005.
[4]Luo Junzhou,Ji peng,Wang Xiaozhi,et al.Resource management and task scheduling in grid computing.Proceedings of the 8th International Conference on Computer Supported Cooperative Work in Design,Berlin.2005:431-436.
[5]http://news.xinhuanet.com/it/2002-05/08/content_384700.htm.
[6]王璞,彭玲.一种新的经济网格计算任务调度控制模型.计算机科学.2008,35(03):106-108.
[7]翁楚良,陆鑫达.一种基于双向拍卖机制的计算网格资源分配方法.计算机学报.2006,29(06):1004-1009.
[8]LIANG Z Y,SUNY,ZHANG L,et al.Reverse auction-based grid resources allocation[C]PRIMA.2006:150-161.
[9]http://www.gridbus.org/papers/gecon2006.pdf
[10]Fipa dutch auction interaction protocol specification.FIPA-Foundation for Intelligent Physical Agents(http://www.fipa.org/),August(2001).
[11]刘敏,蔡勇.基于有效性的逆荷兰式拍卖网格资源调度.微电子学与计算机.2007,24(07):66-68.
[12]Mathias Dalheimer,Franz-Josef Pfreundt and Peter Merz.Formal Verification of a Grid Resource Allocation Protocol.8th IEEE International Symposium on Cluster Computing and the Grid.Lyon,France 2008:332-339.
[13]陈冬娥,杨扬,刘丽.基于反拍卖的计算网格资源分配方法.北京科技大学学报.2007,29(05):548-552.
[14]洪学海,许卓群,丁文魁.网格计算技术及应用综述.计算机科学,2003,30(08):1-5+9.
[15]Abramson D,Sosie R,Giddy J,et al.Nimrod:a tool for performing parameterized Simulation computing using distributed workstations.Proceedings of the 4th IEEE Symp.On High Performance Distributed Computing,1995.
[16]李志洁.基于经济原理的网格资源分配策略与算法研究:(硕士学位论文).大连:大连理工大学,2008.
[17]马秀芳,时和平,温云.网格安全研究现状及面临的问题 电信快报.2007,(03):37-40.
[18]http://www.ict.ac.cn/~xuzhiwei/research.html.
[19]田苗.基于移动Agent的网格资源发现机制的研究:(硕士学位论文).大连:大连海事大学,2008
[20]刘炜.基于网格的面向Agent软件分析与设计建模方法及环境研究:(博士学位论文).上海:上海大学,2005
[21]Foster I,Kesselman C,Tuecke S.The anatomy of the grid:Enabling scalable virtual organizations.Int'l Journal of High Performance Computing Applications.2001,(15):200-222.
[22]Ian Foster.What is the Grid? A Three Point Checklist.Grid Today-Daily News and Information for the Global Grid Community.2002(16).
[23]I.Foster.Grid Technologies & Applications:Architecture & Achievements.International Conference on Computing in High Energy and Nuclear Physics.2001.
[24]都志辉,陈渝,刘鹏.网格计算.北京:清华大学出版社,2002.
[25]都志辉等.以服务为中心的网格体系结构OGSA.计算机科学.2003,30(07):22-29.
[26]李茂胜.基于市场的网格资源管理研究:(硕士学位论文).合肥:中国科学技术大学,2006.
[27]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.
[28]Foster I.The grid:A new infrastructure for 21st century science.Physics Today.2002,55(2):42-47.
[29]郝熙,周枫.OGSA开放网格服务体系结构研究.山西电子技术.2007,(01):87-89.
[30]刘洪涛.网格环境下资源管理与调度方法的研究与应用:(硕士学位论文).武汉:武汉理工大学.2008.
[31]A.Chevrenak,I.Foster,C.Kesselmna,C.Salisbury and S.Tuecke.The Data Grid:Towards an architecture for the distributed management and analysis of large Scientific datasets.Journal of Network and Computer Applications.2000,23(3):187-200.
[32]M.Hyatt,R.Vrablik.The Information Grid-Secure access to any information,anywhere,over any network.Tech.rep.,IBM developer Works,2004.[Online].Available:http://www-106.ibm.com/eveloperworks/librayr/gr-infogrid.html.
[33]M.Cannataro and D.Talia.KNOWLEDGE GRID An Architecture for Distributed Knowledge Discovery.Communication of ACM.2003,46(1).
[34]Hai Zhuge.China's e-Science Knowledge Grid Environment.IEEE Intelligent Systems.2004,19(1):13-17.
[35]谭树斐.源发现机制的研究:(硕士学位论文).长沙:中南大学,2005.
[36]何琨,赵勇.网格资源管理与调度研究综述.武汉理工大学学报.2005,27(4):1-5.
[37]樊宁.网格的资源管理和信息管理概述[DB/OL].http://www.ibm.com/developerworks/cn/grid/gr-fannl/.2006.
[38]孙常莹.网格环境下资源管理机制的研究:(硕士学位论文).大庆:大庆石油学院.2007.
[39]Buyya R,Abramson D,Giddy J.A case for economy grid architecture for service oriented grid computing.Proceedings of the 15th IEEE International Parallel and Distributed Processing Symposium.San Francisco,California,USA.2001:776-790.
[40]Buyya R,Abramson D,Giddy J,et al.Economic models for resource management and scheduling in grid computing.Concurrency and Computation:Practice and Experience.2002,14(13-15):1507-1542.
[41]McKnight L W,Boroumand J.Pricing internet services:approaches and challenges.IEEE computer.2000,33(2):128-129.
[42]Smith R,Davis R.The contract net protocol:high level communication and control in distributed Problem solver.IEEE Transactions on Computers,1980,29(12):1104-1113.
[43]Viekrey W.Counter-speculation,auctions,and competitive sealed tenders.Journal of inance.1961,16(1):9-37.
[44]Das R,Hanson J,Kephart J,et al.Agent-human interactions in the continuous double auction.Proceedings of the International Joint Conferences on Artificial Intelligence,2001.
[45]徐金红,徐维军.在线反向拍卖的定价策略及竞争分析.系统工程理论与实践.2008,28(05):47-54.
[46]http://baike.baidu.com/view/130867.htm.
[47]http://www.globus.org/gridsim/.
[48]张国强.关于网格模拟工具GridSim的研究.辽宁教育行政学院学报.2007,(11):175-176.
[49]丛珊.基于GridSim的网格模拟技术的研究:(硕士学位论文).哈尔滨:哈尔滨工业大学.2006.
[50]穆晓芳.基于拍卖机制的网格作业调度遗传算法研究:(硕士学位论文).太原:原理工大学.2007.
[51]李立.GridSim网格仿真工具研究.电脑知识与技术 2007,5(13):43-44.
[2]罗作民,张景,李军怀,谢长生.网格计算及其关键技术综述.计算机工程与应用,2003,39(30):18-22.
[3]Joshy J,Craig F著.战晓苏,张少华译 Grid Computing.北京:清华大学出版社,2005.
[4]Luo Junzhou,Ji peng,Wang Xiaozhi,et al.Resource management and task scheduling in grid computing.Proceedings of the 8th International Conference on Computer Supported Cooperative Work in Design,Berlin.2005:431-436.
[5]http://news.xinhuanet.com/it/2002-05/08/content_384700.htm.
[6]王璞,彭玲.一种新的经济网格计算任务调度控制模型.计算机科学.2008,35(03):106-108.
[7]翁楚良,陆鑫达.一种基于双向拍卖机制的计算网格资源分配方法.计算机学报.2006,29(06):1004-1009.
[8]LIANG Z Y,SUNY,ZHANG L,et al.Reverse auction-based grid resources allocation[C]PRIMA.2006:150-161.
[9]http://www.gridbus.org/papers/gecon2006.pdf
[10]Fipa dutch auction interaction protocol specification.FIPA-Foundation for Intelligent Physical Agents(http://www.fipa.org/),August(2001).
[11]刘敏,蔡勇.基于有效性的逆荷兰式拍卖网格资源调度.微电子学与计算机.2007,24(07):66-68.
[12]Mathias Dalheimer,Franz-Josef Pfreundt and Peter Merz.Formal Verification of a Grid Resource Allocation Protocol.8th IEEE International Symposium on Cluster Computing and the Grid.Lyon,France 2008:332-339.
[13]陈冬娥,杨扬,刘丽.基于反拍卖的计算网格资源分配方法.北京科技大学学报.2007,29(05):548-552.
[14]洪学海,许卓群,丁文魁.网格计算技术及应用综述.计算机科学,2003,30(08):1-5+9.
[15]Abramson D,Sosie R,Giddy J,et al.Nimrod:a tool for performing parameterized Simulation computing using distributed workstations.Proceedings of the 4th IEEE Symp.On High Performance Distributed Computing,1995.
[16]李志洁.基于经济原理的网格资源分配策略与算法研究:(硕士学位论文).大连:大连理工大学,2008.
[17]马秀芳,时和平,温云.网格安全研究现状及面临的问题 电信快报.2007,(03):37-40.
[18]http://www.ict.ac.cn/~xuzhiwei/research.html.
[19]田苗.基于移动Agent的网格资源发现机制的研究:(硕士学位论文).大连:大连海事大学,2008
[20]刘炜.基于网格的面向Agent软件分析与设计建模方法及环境研究:(博士学位论文).上海:上海大学,2005
[21]Foster I,Kesselman C,Tuecke S.The anatomy of the grid:Enabling scalable virtual organizations.Int'l Journal of High Performance Computing Applications.2001,(15):200-222.
[22]Ian Foster.What is the Grid? A Three Point Checklist.Grid Today-Daily News and Information for the Global Grid Community.2002(16).
[23]I.Foster.Grid Technologies & Applications:Architecture & Achievements.International Conference on Computing in High Energy and Nuclear Physics.2001.
[24]都志辉,陈渝,刘鹏.网格计算.北京:清华大学出版社,2002.
[25]都志辉等.以服务为中心的网格体系结构OGSA.计算机科学.2003,30(07):22-29.
[26]李茂胜.基于市场的网格资源管理研究:(硕士学位论文).合肥:中国科学技术大学,2006.
[27]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.
[28]Foster I.The grid:A new infrastructure for 21st century science.Physics Today.2002,55(2):42-47.
[29]郝熙,周枫.OGSA开放网格服务体系结构研究.山西电子技术.2007,(01):87-89.
[30]刘洪涛.网格环境下资源管理与调度方法的研究与应用:(硕士学位论文).武汉:武汉理工大学.2008.
[31]A.Chevrenak,I.Foster,C.Kesselmna,C.Salisbury and S.Tuecke.The Data Grid:Towards an architecture for the distributed management and analysis of large Scientific datasets.Journal of Network and Computer Applications.2000,23(3):187-200.
[32]M.Hyatt,R.Vrablik.The Information Grid-Secure access to any information,anywhere,over any network.Tech.rep.,IBM developer Works,2004.[Online].Available:http://www-106.ibm.com/eveloperworks/librayr/gr-infogrid.html.
[33]M.Cannataro and D.Talia.KNOWLEDGE GRID An Architecture for Distributed Knowledge Discovery.Communication of ACM.2003,46(1).
[34]Hai Zhuge.China's e-Science Knowledge Grid Environment.IEEE Intelligent Systems.2004,19(1):13-17.
[35]谭树斐.源发现机制的研究:(硕士学位论文).长沙:中南大学,2005.
[36]何琨,赵勇.网格资源管理与调度研究综述.武汉理工大学学报.2005,27(4):1-5.
[37]樊宁.网格的资源管理和信息管理概述[DB/OL].http://www.ibm.com/developerworks/cn/grid/gr-fannl/.2006.
[38]孙常莹.网格环境下资源管理机制的研究:(硕士学位论文).大庆:大庆石油学院.2007.
[39]Buyya R,Abramson D,Giddy J.A case for economy grid architecture for service oriented grid computing.Proceedings of the 15th IEEE International Parallel and Distributed Processing Symposium.San Francisco,California,USA.2001:776-790.
[40]Buyya R,Abramson D,Giddy J,et al.Economic models for resource management and scheduling in grid computing.Concurrency and Computation:Practice and Experience.2002,14(13-15):1507-1542.
[41]McKnight L W,Boroumand J.Pricing internet services:approaches and challenges.IEEE computer.2000,33(2):128-129.
[42]Smith R,Davis R.The contract net protocol:high level communication and control in distributed Problem solver.IEEE Transactions on Computers,1980,29(12):1104-1113.
[43]Viekrey W.Counter-speculation,auctions,and competitive sealed tenders.Journal of inance.1961,16(1):9-37.
[44]Das R,Hanson J,Kephart J,et al.Agent-human interactions in the continuous double auction.Proceedings of the International Joint Conferences on Artificial Intelligence,2001.
[45]徐金红,徐维军.在线反向拍卖的定价策略及竞争分析.系统工程理论与实践.2008,28(05):47-54.
[46]http://baike.baidu.com/view/130867.htm.
[47]http://www.globus.org/gridsim/.
[48]张国强.关于网格模拟工具GridSim的研究.辽宁教育行政学院学报.2007,(11):175-176.
[49]丛珊.基于GridSim的网格模拟技术的研究:(硕士学位论文).哈尔滨:哈尔滨工业大学.2006.
[50]穆晓芳.基于拍卖机制的网格作业调度遗传算法研究:(硕士学位论文).太原:原理工大学.2007.
[51]李立.GridSim网格仿真工具研究.电脑知识与技术 2007,5(13):43-44.