网格计算下基于虚拟组织的资源管理与调度研究

论文摘要

网格计算（Grid Computing）是当前互联网研究中的一个热点,也是并行和分布处理技术的一个发展方向。它充分利用网上的闲置处理能力,把整个网络整合成一台巨大的超级计算机,实现了计算资源、数据资源、存储资源、信息资源、知识资源、专家资源的全面共享。在网格计算中,资源管理、任务调度和任务管理是网格必须具备的三个基本功能。本文从理论上对基于虚拟组织（VO）的资源管理进行了研究,结合市场经济模型对任务调度进行了探索,其主要研究工作及贡献可体现在以下几个方面:本文讨论了网格计算环境下基于VO的资源共享、协同工作机制与理论模型。通过对网格VO的研究,提出了一种新的基于链路带宽的VO集合模型,并给出了一种简单而有效的VO聚合算法。针对VO中资源属性动态变化和资源更新操作远高于资源注册操作的特点,提出了一种基于哈希表-二叉树（HT-BST）的资源管理模型。该模型综合考虑了已有的链表结构的优缺点,将注册资源通过二叉树型结构按ID顺序联系起来,实现了资源发现和查找效率上的优化,充分适应资源负载以及各种属性快速变化的特点。利用市场经济中的价格杠杆原理,提出了一种简单有效的资源计费模型,实现了VO内资源的负载均衡。本文详细介绍了由澳大利亚Monash大学开发的基于计算经济学的网格框架（GRid Architecture for Computational Economy,简称GRACE）的网格资源代理Nimrod-G的体系结构以及Nimrod-G内部实体的工作流程。重点描述了由Nimrod-G自带的DBC最优时间、DBC最优费用调度算法。在已有算法的基础之上,提出了LP-DBC最优时间和LP-DBC最优费用调度算法。该算法基于一种全新的思想,将任务调度问题转化为线性规划问题,采用单纯形算法获得近似最优解,从而获得资源的最优执行时间以及该任务的最小完成时间,进而获得资源的最优任务分配数。本文采用网格仿真工具GridSim,搭建了基于Broker的网格仿真平台,采用Java语言实现了图形界面客户端。仿真结果显示LP-DBC算法与Nimrod-G自带的DBC算法在任务分配方案上基本相似,然而LP-DBC算法的总任务完成时间明显小于Nimrod-G自带的DBC算法的总任务完成时间,这也说明了LP-DBC算法具有较低的时间复杂度。随着网格任务粒度的增大,仿真结果表明LP-DBC算法在调度任务中的时间开销越来越小,说明了LP-DBC算法具有一定的应用价值。

论文目录

• 摘要
• Abstract
• 目录
• 第一章 绪论
• 1.1 网格计算出现的背景
• 1.2 网格计算研究背景及意义
• 1.3 网格计算在国内外研究现状
• 1.4 网格计算目前存在的问题
• 1.5 本文的组织结构
• 第二章 网格计算相关技术
• 2.1 网格的体系结构
• 2.1.1 五层沙漏体系结构
• 2.1.2 开放网格服务体系结构
• 2.1.3 Web 服务资源框架
• 2.2 网格计算中的虚拟组织
• 2.2.1 虚拟组织的定义
• 2.2.2 构建虚拟组织存在的问题
• 2.3 常用网格调度算法
• 2.3.1 Min-min 算法
• 2.3.2 Max-min 算法
• 2.3.3 遗传算法
• 2.3.4 模拟退火算法
• 2.3.5 基于Agent 的任务调度算法
• 2.3.6 其他任务调度算法
• 2.4 网格计算与云计算
• 2.4.1 云计算的定义
• 2.4.2 云计算的三大服务
• 2.4.3 云计算与网格计算的异同
• 2.5 小结
• 第三章 虚拟组织聚合模型及其资源管理模型
• 3.1 基于链路传输带宽的VO 聚合模型
• 3.1.1 问题描述
• 3.1.2 VO 聚合算法
• 3.2 VO 资源计费模型
• 3.3 资源信誉度模型
• 3.4 基于HT-BST 的VO 资源管理模型
• 3.4.1 HT 资源管理模型
• 3.4.2 BST 冲突解决方法
• 3.4.3 资源的插入算法
• 3.4.4 资源的查找算法
• 3.5 小结
• 第四章 基于Nimrod-G 的LP-DBC 调度算法
• 4.1 Nimrod-G 调度系统
• 4.1.1 Nimrod-G 体系结构
• 4.1.2 Nimrod-G 执行流程
• 4.1.3 基于Nimrod-G 的DBC 调度算法
• 4.1.3.1 DBC 时间最优算法
• 4.1.3.2 DBC 费用最优算法
• 4.2 LP-DBC 算法
• 4.2.1 LP-DBC 最优时间算法
• 4.2.1.1 问题描述
• 4.2.1.2 算法基本思想
• 4.2.1.3 算法实例
• 4.2.2 LP-DBC 最优费用算法
• 4.2.2.1 问题描述
• 4.2.2.2 算法基本思想
• 4.2.2.3 算法实例
• 4.2.3 LP-DBC 算法实现
• 4.2.4 LP-DBC 算法在时间复杂度上的优化
• 4.3 小结
• 第五章 Gridsim 仿真及性能分析
• 5.1 现有的网格仿真环境
• 5.2 Gridsim 的安装和运行
• 5.3 仿真参数设置
• 5.4 仿真计划
• 5.5 仿真结果
• 5.6 性能分析
• 5.7 小结
• 第六章 总结和展望
• 6.1 总结
• 6.2 创新点
• 6.3 展望
• 致谢
• 参考文献
• 攻读硕士学位期间取得的研究成果