一种基于序贯博弈的网格资源分配策略
作者:
基金项目:

Supported by the National Natural Science Foundation of China under Grant No.50479055 (国家自然科学基金)

  • 摘要
  • | |
  • 访问统计
  • |
  • 参考文献 [31]
  • |
  • 相似文献
  • |
  • 引证文献
  • | |
  • 文章评论
    摘要:

    网格环境中资源的负载预测是实现资源优化分配的关键任务之一,而网格资源的动态性和异构性使得准确判断资源的负载状态十分困难.针对已有的分配策略对资源负载评估的不足,提出了一种基于序贯博弈的优化用户时间的网格资源分配策略.该策略将正比例资源共享的网格环境中多用户竞争同一计算资源的问题形式化为一个多人序贯博弈,通过寻求该序贯博弈中各个阶段博弈的纳什均衡解来预测资源负载;然后利用此负载信息生成所有用户的最优出价组合和资源的优化价格;最后根据各用户出价,按比例分配资源的计算能力.通过对网格模拟器GridSim的实验研究,结果表明,该策略能够得到合理的用户出价,降低资源占用时间,从而弥补了Bredin提出的优化策略中未考虑资源未来负载变化的缺陷,实现了资源的优化分配.其结论说明运用序贯博弈方法预测资源负载是可行的,且能更好地适应网格环境下异构资源的动态性.

    Abstract:

    Failure detector is one of the fundamental building blocks to build reliable grid environments. There are large numbers of distributed applications with different QoS of failure detection in grids. Thus, in order to keep its efficiency and scalability in grid environments, a failure detector should not only provide QoS of accurate failure detection for applications, but also avoid redundant loads of designing multiple detectors for different QoS. Therefore, a new failure detector GA-FD (adaptive failure detector for grid) is presented, which adopts heartbeat detection strategy based on PULL mode. GA-FD can provide QoS of failure detection for multi-applications according to quantitative QoS metrics , and does not need any hypothesis about message behavior ),,(UMLMRUDTTTand clock synchronization. In addition, it proves that GA-FD implements a failure detector that belongs to ◇P in the partially synchronous model, and the experimental results are given in the end.

    参考文献
    [1]Foster I,Kesselman C,Tuecke S.The anatomy of the grid:Enabling scalable virtual organizations.Int'l Journal of Supercomputer Applications,2001,15(3):200-222.
    [2]Foster I.The grid:Computing without bonds.Scientific American,2003,288(4):78-85.
    [3]Yang GW,Jin H,Li ML,Xiao N,Li W,Wu ZH,Wu YW,Tang FL.Grid computing in China.Journal of Grid Computing,2004,2(2):193-206.
    [4]Jin H,Zou DQ,Han ZF.Implementation of a grid system based on Web.Mini-Micro Systems,2003,24(12):2053-2056 (in Chinese with English abstract).
    [5]Jin H.Challenges of grid computing.In:Fan W,Wu Z,Yang J,eds.Advances in Web-Age Information Management:Proc.of the 6th Int'l Conf.LNCS 3739,Berlin:Springer-Verlag,2005.25-31.
    [6]Krauter K,Buyya R,Maheswaran M.A taxonomy and survey of grid resource management system for distributed computing.Software:Practice and Experience,2002,32(2):135-164.
    [7]Ding J,Chen GL,Gu J.A unified resource mapping strategy in computational grid environments.Journal of Software,2002,13(7):1303-1308 (in Chinese with English abstract).http://www.jos.org.cn/1000-9825/13/1303.pdf
    [8]Zhang WS,Yang GW,Shen MM,Zheng WM.RSDictionary-A global namespace for distributed computing environment.Journal of Computer Research and Development,2005,42(8):1409-1414 (in Chinese with English abstract).
    [9]Li W,Xu ZW,Bu GY,Cha L.An effective resource locating algorithm in grid environments.Chinese Journal of Computers,2003,26(11):1546-1549 (in Chinese with English abstract).
    [10]Weng CL,Lu XD.A pricing algorithm for market-based resource management on grid computing systems.Journal of Computer Research and Development,2004,41(7):1151-1156 (in Chinese with English abstract).
    [11]Cao HQ,Xiao N,Lu XC,Liu Y.A market-based approach to allocate resources for computational grids.Journal of Computer Research and Development,2002,39(8):913-916 (in Chinese with English abstract).
    [12]Cheng JQ,Wellman MP.The WALRAS algorithm:A convergent distributed implementation of general equilibrium outcomes.Journal of Computational Economics,1998,12(1):1-24.
    [13]Buyya R,Abramson D,Giddy J.A case for economy grid architecture for service-oriented grid computing.In:Proc.of the 10th IEEE Int'l Heterogeneous Computing Workshop.Washington:IEEE Computer Society,2001.776-790.
    [14]Wolski R,Plank JS,Brevik J,Bryan T.Analyzing market-based resource allocation strategies for the computational grid.Int'l Journal of High Performance Computing Applications,2001,15(3):258-281.
    [15]Abramson D,Buyya R,Giddy J.A computational economy for grid computing and its implementation in the nimrod-G resource broker.Future Generation Computer Systems,2002,18(8):1061-1074.
    [16]Nash JF.Non-Cooperative games.Annals of Mathematics,1951,54(2):286-295.
    [17]Kwok YK,Song SS,Hwang K.Selfish grid computing:Game-Theoretic modeling and NAS performance results.In:Proc.of the IEEE Int'l Symp.on Cluster Computing and the Grid.Washington:IEEE Computer Society,2005.349-356.
    [18]Bredin J,Kotz D,Rus D,Maheswaran RT,Imer C,Basar T.Computational markets to regulate mobile-agent systems.Autonomous Agents and Multi-Agent Systems,2003,6(3):235-263.
    [19]Maheswaran RT,Ba-ar T.Nash equilibrium and decentralized negotiation in auctioning divisible resources.Group Decision and Negotiation,2003,12(5):361-395.
    [20]Liu C,Yang L,Foster I,Angulo D.Design and evaluation of a resource selection framework for grid applications.In:Proc.of the 11th IEEE Int'l Symp.on High-Performance Distributed Computing.Washington:IEEE Computer Society,2002.63-72.
    [21]Wolski R,Spring N,Hayes J.The network weather service:A distributed resource performance forecasting service for metacomputing.Future Generation Computing Systems,1999,15(5-6):757-768.
    [22]Arabe JNC,Beguelin A,Lowekamp B,Seligman E,Starkey M,Stephan P.Dome:Parallel programming in a distributed computing environment.In:Proc.of the 10th Int'l Parallel Processing Symp.Washington:IEEE Computer Society,1996.218-224.
    [23]Gehring J,Reinefeld A.Mars:A framework for minimizing the job execution time in a metacomputing environment.Future Generation Computing Systems,1996,12(1):87-99.
    [24]Foster I,Kesselman C.Globus:A metacomputing infrastructure toolkit.Int'l Journal of Supercomputer Applications,1998,11(2):115-128.
    [25]Buyya R,Murshed M.GridSim:A toolkit for modeling and simulation of grid resource management and scheduling.Journal of Concurrency and Computation:Practice and Experience,2002,14(13-15):1175-1220.
    [4]金海,邹德清,韩宗芬.基于Web的网格系统的实现.小型微型计算机系统,2003,24 (12):2053-2056.
    [7]丁箐,陈国良,顾钧.计算网格环境下一个统一的资源映射策略.软件学报,2002,13(7):1303-1308.http://www.jos.org.cn/ 1000-9825/13/1303.pdf
    [8]张武生,杨广文,沈美明,郑纬民.RSDictionary--一种用于分布式计算环境的全局名字空间.计算机研究与发展,2005,42(8):1409-1414.
    [9]李伟,徐志伟,卜冠英,查礼.网格环境下一种有效的资源查找方法.计算机学报,2003,26(11):1546-1549.
    [10]翁楚良,陆鑫达.一种基于市场机制的网格资源调价算法.计算机研究与发展,2004,41(7):1151-1156.
    [11]曹鸿强,肖侬,卢锡城,刘艳.一种基于市场机制的计算网格资源分配方法.计算机研究与发展,2002,39(8):913-916.
    相似文献
引用本文

李志洁,程春田,黄飞雪,李欣.一种基于序贯博弈的网格资源分配策略.软件学报,2006,17(11):2373-2383

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2006-06-09
  • 最后修改日期:2006-07-22
文章二维码
您是第19702689位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号