网格服务建模分析

1、2006年第 23卷第 10期 微电子学与计算机 1引言在网格环境下 , 服务动态地分布在异构的广域网中 , 对服务的透明访问与管理构成了网格研究的 一个重要内容 。 各种资源动态加入网格系统 , 它们 可以随时中止服务 , 从网格中退出 ; 资源是分布在 各种异构的系统中 , 故动态性与异构性是网格建模 中的重要考虑因素 。 文献 1提出了基于协议的五 层沙漏模型的网格体系结构 , 基于此思想 , Globus 项目组开发了相应的工具包 GT2, GT2中的 MDS2实现了资源的监测和发现 。 随着网格技术逐渐向工 业 标 准 靠 拢 , 文 献 2提 出 了 以 服 务 为 中 心 的 网

2、 格 体 系 结 构 OGSA , Globus 项 目 组 随 后 推 出 了 基 于OGSA 的工具包 GT4, GT4中的服务的监测与发现 由 MDS4实现 。 虽然 MDS2和 MDS4实现了资源和服务的发现与监测 , 但是关于服务的性能评价与分 析没有进行深入研究 。 文献 35主要研究了网格 环境下资源管理和调度模型 , 但是没有考虑到资源 的动态性 , 文献 6研究了资源状态变化时 (资源故 障或主动退出虚拟组织 网格服务的建模 , 但是其 研究建立在集中调度的基础上 。 基于以上研究工作 , 本文拟讨论在网格环境中 , 分层管理模式下的 服务建模问题 。2集中调度模型文献 6将

3、集中调度下的网格服务建模成强度为 的泊松分布 , 到达虚拟组织的作业被以概率 q 1,q 2, , q N 分发到各资源 。 在此基础上推导出了资源队列长度有限并且当资源发生故障时 , 调度中心在 获得资源故障信息存在延时的情况下 , 作业丢包率 的稳态概率 。该模型的优点在于 , 可以获得各个资源的利用 率 , 同时可以通过合理的调度算法 , 提高资源的利 用率 , Condor-G , Nimrod/G 等系统就可以用 该 模 型 来描述 。 但是存在的问题在于 , 当调度中心发生故 障时 , 整个系统将会无法正常工作 。与集中调度不同的调度方式是分布式调度 , 目 前一些 P2P 系统采

4、用了这种调度方法 , 其具体过程 如下 :当某个资源不能完成提交到其上的作业请求 时 , 就以广播的方式向其周围资源查询是否能完成 该作业 , 并在该作业上设置一个有效时间 , 如果发 现可以满足该作业要求的资源时 , 则将该作业提交 到其上 , 否则 , 这些资源又继续在它们周围的资源 查找 , 直到找到合适的资源或者该作业的有效时间收稿日期 :2006-05-24基金项目 :中国博士后科学基金项目 (2003034155211工程十五建设项目 (CERS-219899004网格服务建模分析殷 杰王跃宣 吴 澄(清华大学 自动化系 国家 CIMS 工程技术研究中心 , 北京 100084摘要

5、 :在网格环境下 , 资源以服务的形式共享 。 针对虚拟组织内网格服务的动态性和广域性 , 分析了网格服务的特点 , 指出了网格服务建模需要着重考虑的因素 , 并建立了其相应的数学模型 , 对其进行了初步分析 , 对若干个 小规模虚拟组织组成的网格系统进行了仿真实验 , 实验结果验证了模型的合理性 。 关键词 :网格 , 服务 , 虚拟组织 , 建模 中图分类号 :TP393.1文献标识码 :A文章编号 :1000-7180(2006 10-0015-03Modeling and Analyzing of Grid ServiceYIN Jie, WANG Yue-xuan, WU Cheng

6、(National CIMS Engineering Research Center, Department of Automation, Tsinghua University, Beijing 100084Abstract:In grid, all resources are shared in the form of services. The dynamic characteristic and scalability of grid isintroduced and analyzed, especially the important factors in modeling grid

7、 service. A related mathematical model is giv-en here with preliminary analyses. The experiment in a small scale grid system with several VO, each consists of some resources as the service providers, validates the model provided in this paper. Key words:Grid, Service, Virtual organization, Modeling1

8、5微电子学与计算机 2006年第 23卷第 10期过期为止 。这种调度方法的优点在于不存在单点失效问 题 , 但缺点在于资源组织分散 , 不利于管理 ; 资源的 利用不平衡 ; 当资源动态变化时 , 必须通知所有的 相关资源 ; 并且其资源查找方式多为广播式的 , 占 用大量带宽 。3混合调度模型网格上的服务 , 综合安全与查找效率的平衡 ,可以采用分层管理模式 。 在这种模式下 , 资源组织 成虚拟组织 (VO , VO 又组织成更高层次的 VO , VO 内部采用集中调度的方式 , VO 分布于整个广域网 内 , VO 之间信息交互与任务调度是分布的 。 提交到 虚拟组织上的作业都是在具体

9、的资源上完成的 , 故 提交到某 VO 上的作业 , 可能被分配到直接归属于 该 VO 的资源上 , 也可能分配到其子 VO 上 , 再由子VO 在内部再次分配 。 但从提供服务角度看 , 父 VO和子 VO 是平等的 。图 1是基于分层管理模式下的混合调度模型 , 它将虚拟组织之间作业迁移的分布式调度与虚拟 组织内部的集中调度综合在一起 。 由于在作业调度 上 , 父 VO 与子 VO 是平等的 , 这种平等性在图 1中 表示为 VO 之间无差异的作业迁移 。 图 1中各 VO 之间是协作的 , 设提交到各 VO 的作业服从强度为 i (i , 为网格中 VO 的集 合 的泊松分布 , p

10、A L 表示一个提交到 VO A 中作业由 于各种原因迁移到 VO L 中的概率 。 VO 与其子 VO 的关系主要体现在 VO 之间的迁移概率的大小上 , 非常明显 , 一个父 VO 向其子 VO 的作业迁移概率 要大于其它 VO 。 q i1, q i2, , q iN i (i , 为网格中VO 的集合 ; N i 表示 VO i 内的资源数 表示当一个作 业到达 VO i 后 , 分配到各资源上的概率 。 q i1, q i2, , q iN i 可以是事先约定的常数 , 也可以是随着各服务提供者的队列长度与利用率 , 而动态进行调整 。 但需 要满足式 (1 约束 :T ij =1

11、p ij+N ik =1 q ik=1(i (1式 中 , T i 表 示 VO i 可 以 将 作 业 转 移 到 其 上 的VO 数 , 表现在图 1上就是 VO 的出度 (箭头从该 VO 发出的虚线的数量 , 如 VO A 的 T A 是 2, VO L 的 T L 是 1; N i 表示 VO i 内的资源数量 。 从式 (1 可以看 出 , 当对于某 VO , 其出度为零时 , 式 (1 可简化成 :N ik =1 q ik=1(i (2于是该模型就回归成了文献 6的形式 , 也就是 整个网格系统变成了一个个的服务孤岛 。下面考虑一种特殊情况 , 当各 VO 的泊松流强 度 相同时

12、, 并且由 p ij 组成的矩阵 P 是对称矩阵 ,p ij 表示从 VO i 向 VO j 的作业迁移概率 , 则在满足此条件下 , 各 VO 的服务队列可以当作 M/M/1来 处 理 , 文献 6中的一些结论也就适用于本模型 。 4仿真研究以下通过实验 , 来验证本模型的合理性 。 图 2给出了当各 VO 的泊松流强度 不相同 , 且 p ij 组成 的矩阵不对称的网格拓扑结构 。 其中 , VO2是 VO1的子 VO , VO4是 VO3的子 VO 。 图 3给出了图 2所 示拓扑结构下 , 各 VO 平均作业丢失率的实验值与M/M/1模型下的理论值的对比 , 其中各个资源队列 的队列容

13、量为 5。从图 3可以看出 , 实验得出的作业丢失率要低 于理论计算值 , 这是因为部分提交到 VO 上的作业 部分被迁移到了其它的 VO 上 , 使得实际的 =/162006年第 23卷第 10期 微电子学与计算机与计算时的 有了区别 。 另外 , 从仿真结果可以看 出 , 由于协作关系的存在 , 使得各个资源的作业丢 失率均有所减少 。5结束语从以上实验结果看来 , 将网格服务建模成图 1所示的模型是合理的 , 在性能分析与结构优化等方 面是有可能的 。 当然 , 还有许多的研究工作 , 还有待 进一步的深入 :如将作业调度到不同资源的策略研 究 、 考虑作业优先级的服务模型研究 、 各资

14、源的服 务队列有限时 , 队列长度 、 丢包率与资源稳定性的 定性关系等 。 模型的研究对于应用与优化都有较好 的指导意义 , 本文初步提出了网格环境下 , 服务的 建模与分析工作 , 大量研究工作还有待展开 。 参考文献 :1I Foster, C Kesselman, S Tuecke. The anatomy of the grid: enabling scalable virtual organizations. International J. Supercomputer Applications, 2001, 15(3:200222 2I Foster, C Kesselman,

15、J Nick, S Tuecke. The physiology of the grid:an open grid services architecture for distribut-ed systems integration. January, 2002. http:/www.Globus. org/research/papers/ogsa.pdf3Cao J, Jarvis S A, Saini S. ARMS:an agent -based re-source management system for Grid computing, Sci. Pro-gram., 2002, 1

16、0(2:1351484Nitzberg B, Schopf J. Current activities in the scheduling and resource management area of the global grid forum, Lect. Notes Comput. Sci., 2002:25375Spooner D P, Jarvis S A, Cao J, et al. Local grid scheduling techniques using performance prediction. IEE proc., Com-put. Digit. Tech., 200

17、3, 150(2:87966Thomas N, Bradley J T, Knottenbelt W J:Stochastic anal-ysis of scheduling strategies in a grid-based resource mod-el, IEE Proceedings-software, 2004, 151(4:232 239作者简介 :殷 杰 男 , (1980- , 博士研究生 。 研究方向为网格计算 、 语 义网格 、 智能控制等 。制实现代理的迁移 。 系统中不同网络节点间的 MA 的发送和请求 , 即不同节点上的 MAE 与 MAE 之间 的交互用 RMI

18、实现 。3.4用户与系统的交互过程(1 用户登录 :当用户需要查询数据时 , 用户通 过本地 Peer 输入查询条件 , 本地 Peer 为用户生成 相应的 SA , 并将 SA 发送到网络上 。 当用户离线时 , 由于移动代理 SA 自主执行的特点 , 系统允许用户 在发出查询请求并派发 SA 之后 , 离开网络 。 而此时 SA 将脱机继续在网络间执行用户对其赋予的资源 检索任务 。 (2 代理任务的执行 :当 SA 移动到一个 网络节点上时 , 先通过该节点提供的数据检索接口 与 IA 进行交互 , 对该节点持有的 RDF 数据进行检 索 , 查找相应的数据 。 之后 , SA 将自动离开当前宿主 节点回到网络上 , 向下一个目标移动 。 (3 获得查询 结果 :用户可以通过 GUI 查看本地节点上接收到的 查询结果 , 并根据结果中对资源的描述选择自己感 兴趣的资源 , 使用本地代理进行下载 。4结束语该模型采用代理技术对 P2P 系统中的 RDF 文 档进行检索 , 使用 RDQL 作为查询语言 , 通过图形 化界面与用户交互实现资源检索 , 能提升网络带宽 资源利用率和系统效率 , 并具有较好的可扩展性 。参考文献 :1Crespo A,