（计算机应用技术专业论文）基于微观经济学的网格资源分配模型研究及其仿真实现.pdf

东北走学硕士学位论文 基于微观经济学的网格资源分配模型研究及其仿真实现 摘要 计算网格是伴随着互联网技术迅速发展起来的，专门针对大规模分布 式计算的一种新型计算模式。在计算网格环境中的资源具有分布性、自治 性、异构性和动态性，因此选择一个合适的资源分配模型支持有效的资源 管理是实现高性能协同计算的关键。另外，将微观经济学引入网格计算能 够很好地体现网格资源分配中资源所有者与资源消费者之间关系，市场模 型非常适合体现网格动态特点，为计算网格的资源分配提供合理的渠道。 当前引入网格中的多种经济模型都存在一些缺陷，单一模式已不能适合网 格的特点。 本文针对网格市场中竞争资源的特点，设计了将微观经济学引入网格 市场的模型中，该模型体现了微观经济学在网格资源分配系统中的应用， 它利用市场经济中的供求原则对资源的所有者和资源的使用者进行调解 以保证双方互利互惠，这样不仅吸引了更多的资源加入网格系统中，同时 保证了网格用户更经济地选择网格资源。本文在比较用于网格环境的几种 经济模型基础上，设计了一种引入n a s h 均衡理论的双摸机制。该模型采 用供求关系影响网格提供者资源售价，以售价调节网格消费者资源占用 量，这样支持了网格提供者与网格消费者“双赢”的实现。该模型支持两 种资源分配模式：在网格资源丰富时，采用博弈模式，基于n a s h 均衡和 p a r e t o 最优为消费者确定最优资源占用量，同时为网格资源提供者确定最 优售价；在网格资源稀缺时，采用竞价模式为网格资源消费者分配资源。 对于提出的模型，本文设计出网格资源分配的算法，为验证其正确性 和可行性，在n s 2 平台上进行仿真实验。仿真结果表明，该模型是可行和 有效的，具有较好的性能。 关键词：计算网格；资源分配；微观经济学；n a s h 均衡；p a r e t o 最优： 竞价 查! ! 查兰翌主兰竺堡圭 塑塾里塑 r e s e a r c ha n ds i m u l a t e di m p l e m e n t a t i o no f m i c r o e c o n o m i c s b a s e dr e s o u r c e a s s i g n m e n tm o d e l f o rg r i dc o m p u t i n g a b s 仃a c t c o m p u t a t i o n a lg r i d ，w i t ht h er a p i dd e v e l o p m e n to fi n t e r n e tt e c h n i p u e ，i s an e wk i n do fc o m p u t a t i o n a lm o d e l a i m e da tal a r g es c a l ed i s t r i b u t e d c a l c u l a t i o n t h er e s o u r c e si nc o m p u t a t i o n a lg r i da r ed i s t r i b u t e d ，a u t o n o m i c ， i s o m e r o u sa n d d y n a m i c t h e s e l e c t i o no fak i n do fa d a p t e dr e s o u r c e m a n a g e m e n tm o d e lt om a n a g eg r i dr e s o u r c e se f f e c t i v e l yi s ak e yt ot h e i m p l e m e n t a t i o no fh i g h p o w e r e dc o o p e r a t e dc o m p u t a t i o n o nt h eo t h e rh a n d ， t h ei n t r o d u c t i o no fm i c r o e c o n o m i c st ot h eg r i dc o m p u t a t i o nc a nw e l le m b o d y t h er e l a t i o n sb e t w e e nt h eo w n e r sa n du s e r so fr e s o u r c ei nt h eg r i dr e s o u r c e a l l o c a t i o n m a r k e tm o d e li sv e r yf i tt op r e s e n tt h ed y n a m i cc h a r a c t e r i s t i c so f g r i d sa n dc a np r o v i d er e a s o n a b l ec h a n n e lf o rt h er e s o u r c ea l l o c a t i o n o f c o m p u t a t i o n a lg r i d p r e s e n t l y ，m a n yo ft h ee c o n o m i cm o d e st h a ti n t r o d u c e dt o g r i d sh a v es o m ed r a w b a c k s ，a n dt h es i n g u l a rm o d ec a nn ol o n g e r f i tt h e c h a r a c t e r i s t i c so fg r i d b a s e do nt h ec o m p e t i t i o nr e s o u r c e sc h a r a c t e r i s t i c so ft h ec o m p u t a t i o n a l g r i dm a r k e t ，t h et h e s i sd e s i g n sam o d et oi n t r o d u c em i c r o e c o n o m i c st ot h e g r i dm a r k e t t h em o d e le m b o d i e st h ea p p l i c a t i o no fm i c r o e c o n o m i c si nt h e a l l o c a t i o ns y s t e mo ft h eg r i dr e s o u r c e ，a n dm a k e su s eo ft h es u p p l ya n d d e m a n dp r i n c i p l ei nt h em a r k e te c o n o m ym e d i a t i n gb e t w e e nt h eo w n e r sa n d u s e r so fr e s o u r c et oe n s u r em u t u a lb e n e f i tb e t w e e nt h et w op a r t s ，w h i c hn o t o n l ya t t r a c t sm o r er e s o u r c e st ot h eg r i ds y s t e mb u ta l s om a k es u r et h a tg r i d c o n s u m e r ss e l e c tg r i dr e s o u r c em o r ee c o n o m i c a l l y a f t e rc o m p a r i n gs e v e r a l e c o n o m i cm o d e l sa p p l i e dt og r i de n v i r o n m e n t ，t h et h e s i sd e s i g n sab i m o d e m e c h a n i s mw i t hn a s he q u i l i b r i u mp r i n c i p l ei m p o r t e d t h i sm o d e le m p l o y s s u p p l ya n dd e m a n dr e l a t i o n ，w h i c ha f f e c t st h es e l l e r sp r i c et oa d j u s tt h e r e s o u r c eo c c u p a n c yo fg r i dc o n s u m e r st h r o u g hp r i c e ，w h i c ha s s u r e st h e i i i 东北大学硕士学位论文 a b s t r a c t “w i n w i n o fg r i ds u p p l i e r sa n dc o n s u m e r s t h ec u r r e n tm o d e le n a b l e st w o m o d e so fr e s o u r c ea l l o c a t i o n ：w h e nt h eg r i dr e s o u r c ei si na b u n d a n c e ，i tw i l l u s eg a m et h e o r ym o d e ，w h i c hi sb a s e do nn a s he q u i l i b r i u ma n dp a r e t o o p t i m a l i t yt od e t e r m i n et h eo p t i m a lr e s o u r c eo c c u p a n c yf o rg r i dc o n s u m e r sa s w e l la st od e t e r m i n et h eo p t i m a lp r i c ef o rt h es u p p l i e r so fg r i dr e s o u r c e ；w h e n t h eg r i dr e s o u r c ei si ns p a r s i t y ，i tw i l lu s e b i d i n gm o d et oa l l o c a t er e s o u r c ef o r g r i du s e r s f o rt h em o d e lb r o u g h tf o r t h ，t h i st h e s i sw o r k so u tam e t h o do fc a l c u l a t i o n f o rd i s t r i b u t i o no fg r i dr e s o u r c e i no r d e rt ov a l i d a t ei t sv a l i d i t ya n df e a s i b i l i t y , e m u l a t ee x p e r i m e n ti sc a r r i e do u to nt h en s 2p l a t f o r m ，a n dt h er e s u l ts h o w s t h a tt h em o d ei sn o t o n l yf e a s i b l ea n de f f e c t i v eb u ta l s o h a ss a t i s f a c t o r y p e r f o r m a n c e k e yw o r d s ：c o m p u t a t i o n a lg r i d ；r e s o u r c ea s s i g n m e n t ；m i c r o e c o n o m i c s ； n a s he q u i l i b r i u m ；p a r e t oo p t i m a l i t y ；b i d i n g i v 独创声明 本人声明所呈交的学位论文是在导师的指导下完成的。论文 中取得的研究成果除加以标注和致谢的地方外，不包含其他人己 经发表或撰写过的研究成果，也不包括本人为获得其他学位而使 用过的材料。与我一同工作的同志对本研究所做的任何贡献均已 在论文中作了明确的说明并表示谢意。 学位论文作者签名：丑象砗 日期：毋1 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、使 用学位论文的规定：即学校有权保留并向国家有关部门或机构送 交论文的复印件和磁盘，允许论文被查阅和借阅。本人同意东北 大学可以将学位论文的全部或部分内容编入有关数据库进行检 索、交流。 ( 如作者和导师同意网上交流，请在下方签名；否则视为不 同意。) 学位论文作者签名： 签字日期： 导师签名： 签字日期： ! 翌生! 兰竺垃堡圭 苎二兰竺堕 1 1 网格 1 1 1 网格的概念 第一章绪论 网格是构筑在互联网上将地理上广泛分布的大量计算资源( 包括高速互联网、 高性能计算机、大型数据库、传感器、远程设备、p c 等) 融为一体，让资源共享 和协同问题求解能在一个动态的、多结构的虚拟组织中进行，为人们提供更多的 资源、功能和交互性“。网格系统包括网格的物理资源及对资源管理以及逻辑上 的抽象，它充分吸收各种资源，并将它们转化为一种随处可见的、可靠的、标准 且经济的计算能力。 人们常常会问传统分布式系统与网格有什么区别? 从学术角度讲，网格是分 布式系统的一种形态，但网格不同于传统的分布式系统。它是松耦合的环境，有 异构性和动态性，有跨多个管理域多样和动态的资源共享关系，传统分布式系统 大多是基于同构平台的相对封闭的系统，对资源的定义局限于某些特定的数据和 软、硬件。而网格是一个开放的系统，为异构资源建立了一个共享平台，网络上 任何资源都可以共享和利用。简言之，它是一个广域网的分布系统，支持分布式 应用，这些应用可共享网格中的所有资源，能提供满足要求的服务质型“。 传统互联网实现了计算机硬件的连通，w e b 实现了网页的连通，而网格则要 实现互联网上分散在不同地理位置资源的全面连通，目的为把整个互联网整合成 一台“虚拟的超级计算机”，实现计算资源、存储资源、通信资源、软件资源、 信息资源、知识资源的全面共享。网格将与i p v 6 技术一同引领“第三代互联网浪 潮”。 1 1 2 网格的特性 网格的技术特征包括：资源共享、协同工作，这两项是网格的基本技术要求； 通用开放标准、非集中控制、非平凡服务，这三项是i a n f o s t e r 提出的网格检验标 准；动态功能、开放系统。 东北大学硕士学位论文 第一章绪论 网格具有如下特点”1 ： 分布性：这是网格的最主要的特点。组成网格的各种资源是分布在地理位 置的不同的地方，而不是集中在一起的，跨越的地理范围较广。 自治性：网格的资源有自己的本地管理机构或处在本地管理机构的管理之 下，网格资源或强或弱地有本地自治能力。网格管理系统必须尊重本地管 理者，迁就本地管理策略，不能把网格的意愿强加到资源上，更不能替换 本地管理系统。网格只能根据资源加入网内时与网格系统签署的谅解备忘 录合理地使用资源，在尊重谅解备忘录的基础上，网格系统可以把某个资 源强制授权给请求用户使用。 异构性： c ) 9 格涉及的资源类型多样，规模较大，分布在不同的地理位置上。 表现在异构的地理位置，异构的管理域，异构的操作系统等等。 扩展性：网格的扩展性要求体现在规模、能力、兼容性等几个方面。网格 的设计和实现必须要考虑到新的资源能否很自然地加入到网格中，并与原 来的资源联合，共同发挥作用，不降低嘲格计算的性能。为了建造网格， 必须部署一系列相关服务。这其巾包括一些底层的服务，如安全性管理、 信息服务、目录服务、资源交易、资源分配和服务质量。 动态性：网格中的资源可以自由地随时加入和离开网格系统，网格资源的 可获得性是随时间的变化而动态变化的，一个网格资源贡献给阚格用户使 用的潜力是随时问的变化而动态变化，网格资源的负载也是动态变化的。 例如，台超级计算机，在资源所在地的白天工作时间段，它可能只提供 4 0 的计算能力给网格用户使用，6 0 出拥有者自己使用。晚上，则可能 提供1 0 0 的计算能力给网格用户使用。 1 1 3 网格的体系结构 当前旧格发展面临的主要问题是统一标准，网格体系结构的主要功能是划分 系统基本组件，指定组件的目的与功能，刻画组件之间的相互作用，整合各部分 组件。当前已经提出并实现了若十种合理的网格体系结构。下面介绍目前影响比 较广泛的两种网格体系结构：网格协议体系结构( g r i dp r o t o c o l a r c h i t e c t u r e ) 和计 算经济的网格体系结构g r a c e ( g r i d a r c h i t e c t u r ef o r c o m p u t a t i o n a le c o n o m y ) 模 犁，前者以g l o b u s 和开放网格服务结构o g s a ( o p e n g r i d s e r v i c e s a r c h i t e c t u r e ) 为代表1 。 g l o b u s 五层沙漏结构 g l o b u s 五层沙漏结构 一2 一 东北大学硕士学住论文 第一章绪论 i a n f o s t e r 于2 0 0 1 年提出了网格协议体系结构g l o b u s ，当时被认为是网格 建设的核心，是标准化的协议与服务，并可与i n t e m e t 网络协议进行类比。该协议 建立在互联网协议之上，以互联网协议中的通信、路由、名字解析等功能为基础。 计算网格的协议分为构造层、连接层、资源层、汇集层和应用层共五层结构，如 下图所示。 图1 1g l o b u s 与网络协议体系结构的关系 f i g 1 1g l o b u sa n d i t s r e l a t i o n s h i p w i t h i n t e r a c t p r o t o c o l a r c h i t e c t u r e 构造层是网格中可以被共享的资源所在的层，该层包括计算设备、存储设备、 目录、分布式文件系统、分布式计算机池、计算机集群、网络、传感器、贵重仪 器以及其他设备。该层的功能是向上提供网格中可共享使用的资源接口，网格通 过支持设备共享的协议来访问本地设备。 连接层是网格中处理通信与授权控制的核心协议层。构造层的各种资源间的 数据交换都在这一层的控制下实现。各资源间的授权验证、安全控制也在这里实 现。在此协议中提供一次登录、委托授权、局域安全方案整合、基于用户的信任 关系等功能。 资源层的作用是网格中对单个资源实施控制，与可用资源进行安全握手，对 资源进行初始化，监测资源运行状况，统计与付费有关的资源使用数据。该层使 用连接层的通信和安全协议，实现资源共享的安全协商、启动、控制、监控、记 账、付款等。资源层协议有信息协议和管理协议两种。信息用来获得关于资源结 构和状态的信息，管理协议用来协商访问和共享资源。 汇集层的作用是将资源层提交的受控资源汇集在一起，供应用程序共享使用。 汇集层提供目录服务、资源分配、日程安排、资源代理、资源监测诊断、网格启 一3 - 东北大学硕士学位论文第一章绪论 动、负载控制、账户管理等功能，协调多个资源之间的工作，有跨资源集合的交 互协议和服务。 网格的最上面一层是应用层，网格应用包括代码和网格调用两部分。网格应 用可以调用网格各低层提供的有用服务，如资源管理服务、数据访问服务、资源 发现服务等。为便于网格应用程序开发，需要构建支持网格计算的库函数。应用 程序通过服务调用网格上的资源来完成任务。 面向服务的o g s a 结构 o g s a 是o l o b u s 工作组和g g f 合作于2 0 0 2 年提出的面向服务的开放网格服 务结构。该结构是要将当时网格领域最热门的两大技术计算网格和万维网服 务结合起来，把原来按照两条路线进行的研究活动归纳到一条主线上来。其核心 思想是结合w e b 服务技术，通过抽象封装各种类型的资源、信息、数据，并按照 统一规范定义一系列的接口用于服务发现、动态服务创建、生命期管理、通知等 操作。o g s a 对w e b 服务进行了扩展，提出了网格服务的概念。在一个o g s a 中 一切都是网格服务，可以将网格视为可扩展的网格服务的集合。如图1 2 所示： 图1 2 0 g s a 及与w e b 的关系 f i g 1 2o g s a a n di t sr e l a t i o n s h i pw i t hw e b 计算经济的网格体系结构g r a c e 网格系统中的资源供需关系，与现实世界中的商品经济模型是可以类比的： 资源提供者相当于商品制造商，为用户提供计算资源，并从中获利；资源使用者 4 东北大学硕士学位论文 第一章绪论 相当于商品购买者，为了满足自己的资源需求支付一定的费用。他们都是由利益 驱动的，为了获得最大利益而制定策略。据此，r a j k u m a r b u y y a 提出了经济网格 及计算经济网格体系结构模型( 如图1 3 ) ，本文将以此模型为基础，进行详细的 论述并建立资源分配模型。 图1 3g r a c e 和n i m r o d g 资源经纪人 f i g 1 3g r a c ea n dn i m r o d gr e s o u r c eb r o k e r 计算经济网格体系结构的特点如下： ( 1 ) 供求原则的投资回报机制也促进了计算服务质量的提高和资源的升级， 经济学原理是调节供求关系的最重要的机制： ( 2 ) 为访问网格资源的用户提供公平的价格机制，并允许对一切资源进行交 易； ( 3 ) 建立以用户为中心，而不是系统为中心的调度政策，提供了资源分配和 管理的有效机制； ( 4 ) 综合了分层模型和抽象所有者模型的实质。该模型更能体现网格动态协 同广域的特点。 1 2 网格资源管理 网格计算的核心是资源管理，它负责组织和管理各种类型的资源，以满足不 一5 一 东北太学硕士学住论文第一章绪论 同应用的需求。好的管理通常包括资源发现、资源目录、容错、资源供应、资源 监控以及服务水平的管理活动。资源管理领域最令人感兴趣的方面是对服务水平 的需求，从网格资源池中挑选恰当的资源，然后高效分配给用户以满足其要求。 1 2 1 网格资源管理的目的和功能 网格是将网络上分布的、异构的、由多个不同组织所拥有的资源有机地组成 一个逻辑上的整体。资源管理的目的就是把网格中分布的各种资源统一管理起来， 为用户提供一种一致的、简单方便的、高效的协同使用资源的机制。资源管理的 目的主要有三个： 为用户提供访问资源的简单接口，将实际使用资源的具体细节隐藏起来， 用户看到的是一个抽象的逻辑资源。资源的接口常常是很复杂的，抽象后， 复杂的技术细节都被隐藏起来。 协同资源的共享使用。所谓网格资源的共享就是协同使用网格资源的权力。 资源共享的协同是指受时空约束的资源的联合分配和联合预约，网格共享 可以获得的资源服务能力不是单个资源能力的简单累加，而是资源整合后 的强大的服务能力。 资源管理器作为用户使用资源的代理，并建立安全的网格资源使用机制。 资源管理器为用户的应用建立一个虚拟组织，虚拟组织v o 是由与应用相关 的资源、对资源的协同管理和任务协调管理所构成的集合，v o 中的资源是 随用户应用的进度不断变化的，相应的v o 的边界也在动态变化。 如果资源不想继续在网格上存在，可向资源管理器发送请求注销自己，资源 信息数据库中该资源的信息被相应地清除，该资源作为网格资源的生命周期就结 束了。当用户再次请求资源时，就不可能再获得该资源的信息了。具体讲网格资 源管理器应具备以下主要功能”1 ： ( 1 ) 资源注册 资源注册是资源的拥有者向网格注册中心声明、登记目前自己的闲置的可共 享的资源，使之变成网格资源，能被网格用户发现并使用。在此过程中，需要确 定资源的使用接口、描述资源的功能、确定共享策略等。资源的请求者应遵循标 准的资源描述和接口规范提出资源请求。 ( 2 ) 资源描述 资源描述要采用统一的描述框架和描述形式，以支持网格成员问的互操作。在 6 东北大学硕士学位论文 第一章绪论 同一资源注册中心应采用统一的资源描述方法，以实现在注册中心涉及的资源范 围的有效资源调度。在不同的资源注册中心之间交换信息时，遵循共同的中间交 换格式，也可以实现两个注册中心问的交互。即所谓的网格技术与平台和具体实 现无关。 ( 3 ) 资源发现 为资源请求者提供描述资源需求的方式，能够根据资源需求描述在资源信息 数据库中查找匹配满足需求的资源信息，并返回请求者。资源的分配是在资源本 身共享的策略的基础上进行的，资源共享也必须根据策略进行。 ( 4 ) 资源分配 网格资源是动态协同分配和联合调度的，在使用之前需要将资源部署到资源 的运行环境中，即虚拟组织中。 ( 5 ) 资源代理 作为在用户和资源之间中介，代替用户完成资源发现、分配、调度和使用等 操作。 ( 6 ) 资源回收和注销 资源回收是分配给用户的资源在使用完后，网格要进行回收，以便分配给其 他用户使用。资源注销是指资源由于资源或节点失效等原因要求退出网格，相应 为其修改资源信息数据库的记录。 1 2 。2 网格资源管理的分类 根据文献”1 可以将网格资源管理进行分类。 网格资源调度系统可以分为集中式、层次式和分布式。由于网格中的可用资 源是随时变化的，因此调度系统必须是自适应性的，为了实现这一点，可以设计 预测技术，通过对当前调度状态的评估，提出新的调度策略满足用户的需求。比 如价格机制，智能代理技术的采用。 服务质量q o s 分为强、弱和无三类，由于网格应用的不同，尤其是当前面向服 务的网格 1 0 l 和交互式网格 1 1 1 在多媒体应用，工程c a d 等的应用，对q o s 提出更多 样化的要求，如何基于用户个性化雕j q o s 要求，如网格特殊带宽需要和作业完成时 间和费用来作为q o s 参数是一个挑战性的问题。市场经济学原理的引入能反应了网 格的这一实际情况，同时又是一个较热点研究方向。 具体情况如下表所示： 一7 - 东北大学硕士学位论文 第一章绪论 表1 1 网格资源管理分类法 t a b l el ，lt a x o n o m yo f g r i dr e s o u r c em a n a g e m e n t 资源管理系统的属性分类法 网格类型 机器体系结构 命名空间结构 服务质量 资源信息存储 资源发现 资源信息分发 调度器体系结构 调度器策略 状态估计 重新调度 计算网格、数据网格和服务网格 平面犁、层次型、细胞型 关系型、层次型、不规则型 弱、强、无 网络目录、分布式对象技术 查询、代理 批处理( 周期处理) 、在线处理( 按需处理) 集中型、层次型、分布型 系统中心式、用户中心式 预测式( 启发式、价格模型和机器学习) 、非预测式 周期式、事件驱动式 1 2 3 网格资源管理的核心技术 由于存在数量惊人且不同类型的潜在网格计算资源，资源管理的挑战成为网 格计算环境中一个重要的研究课题。这些资源管理情况通常包括资源发现、资源 目录、故障隔离、资源供应、资源监控、访问资源花费协商、资源选择、分配策 略以及服务水平的管理活动。资源管理领域最令人感兴趣的方面是根据对服务水 平的需求从网格资源池中挑选恰当的资源，然后高效提供给用户以满足其要求。 在供应领域，人们发现了网格计算基础设施中另一个有价值并且是非常关键 的特点，也即是它自我管理、自我诊断、自我修复以及自我配置提供自主能力。 其中最引人注目的资源管理中间件方案是网格分配管理器：g r a m ( g l o b u sr e s o u r c e a l l o c a t i o nm a n a g e r ) 。g r a m 可以为用户提供了健壮的作业管理服务，该服务包括 作业分配、状态管理、数据分布、启动停止作业等。为了建造网格，必须部署一 系列相关服务。这其中包括一些底层的服务如安全性管理、信息服务、目录服务、 资源交易、资源分配和服务质量。 8 一 东北走学硕士学位论文 第一章绪论 1 2 4 网格资源闲置与稀缺的矛盾 超级计算机的不断发展，使之成为复杂科学计算领域的主导，但以超级计算 机为中心的计算模式存在明显的不足，虽然它处理能力强大，但造价极高，通常 只有国家一级的部门，如航天、气象等部门才有能力配备这样昂贵的设备。随着 人们日常生活和工作中遇到的计算越来越复杂，人们需要数据处理能力强大价格 相对便宜的计算机，超级计算机的昂贵价格使它成为稀缺资源，显然很难进入一 般工作领域。 在当今世界，大约有4 亿台个人电脑，在任何时刻其大部分处理能力、存储 能力和其它资源都是闲置的，即使美国能源部的超级计算机的利用率也只在3 0 到7 0 之间。资源的闲置和资源的稀缺形成鲜明对比。这样的闲置资源可以通过 网络共享让其他用户受益，作为回报自己还可以在需要资源帮助时获得其他用户 的资源。 2 0 世纪9 0 年代，出现了分布计算系统，将多个p c 、工作站、服务器连接起 来形成一个强大的计算能力。其中松散耦合的分布系统构成了网格的雏形，它的 许多成熟的理论、模型、技术都可以稍加修改甚至直接应用于网格技术中。 “网格”是借鉴电力网的概念提出来的，意思是高性能计算用户接入网格以后， 就如同电力用户将插头插入电源，可以得到“随，i i , 所需”的电力( 计算资源) 供 应，不需要知道电力究竞来自何处( 高性能计算机和其他信息资源) 。显然，网格 将从根本上改变计算机( 尤其是超级计算机) 使用的模式和概念。网格的目标就 是让人们使用网络资源像用电一样简单。 信息的本质特点是可以共享，信息不但可以同时使用，而且也不会因多次使 用同一信息资源折旧或损耗。网格就是把整个因特网上的闲置资源整合起来，形 成类似一台巨大的超级计算机，为用户提供一个透明的、安全的高性能计算环境， 实现资源共享的最大化。 1 3 本文的研究目的和意义 本文利用市场机制非常适合解决网格资源管理和调度问题，通过市场价格的 浮动反映资源供需状况的动态变化的特点，并将微观经济学理论运用于网格资源 分配和调度。博弈论作为主流经济学的一部分，已成为微观经济学的基础，纳什 均衡是其较广泛应用的定理。本文通过纳什均衡理论实现资源优化，这种动态协 一9 东北大学硕士学位论文 第一章绪论 调资源的管理机制比较适合网格资源动态的特性。 本文在已有的网格经济模型基础上，设计了基于纳什均衡和竞价双模式的网 格资源管理模型，依靠市场机制的作用，实现了网格资源提供者和网格资源使用 者的双赢，进而实现网格资源的调度和分配。 同时为验证该模型和算法的可行性，采用网络模拟工具n s 2 ”来实现仿真模 拟实验，为计算网格资源分配提出一个可行的研究途径。 1 4 本文的主要工作 本文针对现有基于市场经济的网格资源调度研究，只考虑由供求关系影响的一 般均衡理论而未对网格条件下资源提供方和资源使用方的完全竞争性给以足够思 考的问题。针对当前研究比较广泛的七种模型存在的不足，提出了改进模型，采 用博弈的方法，寻找网格系统的纳什均衡点，本文提出一种基于微观经济学的网 格资源分配模型，依据供求关系影响网格资源定价，以定价调节网格用户的资源 使用量，均衡网格节点负载，支持网格资源提供方与用户之间的“双赢”。该模型 支持两种资源分配模式：在网格资源丰富时采用第一种模式，基于n a s h 均衡和 p a r e t o 最优为网格用户确定最优资源使用量，同时为网格资源提供者确定最优定 价；在网格资源稀缺时采用第二种模式，采用基于竞价的资源分配策略为网格用 户分配资源。仿真结果表明，该模式是可行和有效的，具有良好的性能。 本文的章节设置为：第一章讲述了网格的理论基础和当前网格资源管理领域的 研究情况。第二章介绍了基于计算经济网格资源管理体系结构和运用于该体系下 的微观经济学多种模型的特点，第三章在第二章的基础设计了基于微观经济学的 网格资源分配模型，第四章对该模型所设计的算法进行仿真实现，第五章结论。 1 0 一 东北大学硕士学位论文 第二章基于计算经济的网格资源管理体系结构 第二章基于计算经济的网格资源管理体系 结构 基于计算经济的网格资源管理体系结构是由b u y y a 教授提出的吲，它是在网格 资源管理中引入经济学理论的代表，该体系在资源发现和调度过程中遵从市场经 济中的供求原则，通过相应机制将网格使用者的资源购买报价与各个资源所有者 的服务报价进行匹配，使网格资源达到较优的分配。下面我们对此进行详细介绍。 2 1 概述 网格使地理上分布的异构资源集成在一起，为完成大规模科学计算、工程、 电子商务而组成虚拟组织，共享资源、交换数据。由于网格包含大量的各种各样 的资源，这些资源为不同的组织拥有，各组织对资源的管理机制和策略、费用和 目标都不尽相同，全局资源管理和调度富有挑战性。传统调度只考虑系统性能， 而忽视了用户的服务质量要求，将网格定义为一个虚拟组织系统、一种合作问题 解决的环境以及一种无缝的方式共享信息和资源的手段，于是需要一种合适的方 法使得这个虚拟组织的各个成员能够有效地共享资源，事实证明经济模型是帮助 管理和评价资源分配的有效手段。 2 1 1 引入经济学原理的原因 在网格中引入经济学主要基于以下的原因9 1 ： 现有的网格系统大多是为了一些学术研究目的而开发的，它们强调资源的 共享和协同工作，但是却没有考虑到资源的价格因素。在实际应用中，大 量的资源并不是无偿使用的，更重要的是要吸引资源的拥有者加入网格， 就必须保证他们的利益。 网格是一个异构的、动态的分布式环境，对资源使用和资源供应都是在不 断的变化中，通过经济学，特别是基于价格的市场机制，由价格浮动来反 映资源供求的动态变化，通过供需均衡实现资源优化分配，能够很好地表 一1 】 东北大学硕士学位论文 第二章基于计算经济的网播资源管理体系结构 现网格的动态变化特征。 网格环境下的资源分配及其消费者、生产者的行为，微观经济学中的一些 模型正好与之配合。资源请求者和提供者能根据自己的实际情况作出决 策，最大化各自的效用和利益。 系统内嵌入经济原理，鼓励资源拥有者贡献他们的空闲资源并能从中获 利，有助于建立大规模的网格系统。 2 1 2 目前的研究情况 目前典型的计算网格系统，如g l o b u s 、w e b f l o w 、l e g i o n 等，都没有 在资源管理中使用经济学方法。但是在计算机系统的资源管理中使用经济学方法， 特别是使用经济学解决分布式系统的负载平衡问题，却是近2 0 多年来非常活跃一 个研究领域，其基本思想是：使用价格信号反映资源的忙闲程度；通过使用最便 宜的资源执行新到的用户作业，实现整个系统的负载平衡。 这些研究成果不能直接用于计算网格的资源管理，其原因在于：首先，它们 的着眼点主要是负载平衡，因而对于服务质量保证的支持很弱；其次，需要一个 中央市场或是公告牌，因而算法的可扩展性不好；再有，资源分配的对象是具体 的任务，粒度小导致开销大，一部分工作基本没有考虑计算网格的广域特点。 2 2 一种计算经济网格体系结构 2 2 1 概述 计算经济的网格体系结构( g r a c e ) 是支持计算经济的最完善的网格体系结 构。它支持微观经济学中的七种经济模型。它根据用户定义和要求的最后期限和 预算限制来进行资源调度，使资源达到更好的利用。在一个全球计算环境中，所 有的用户都倾向于使用更有力的资源，这将出现某些资源被过度使用，而另一些 资源却得不到充分利用。这就需要计算经济和合适的服务价格策略来克服这种情 况。资源拥有者允许用一种可以获得最大利益的方式来请求一个开放的市场价格。 同时资源消费者将允许选择一个符合它们的q o s 要求的资源。因此，当对某种资 源的需要很大时，价格相应地就高些。这将帮助调节网格资源和服务的供求平衡。 1 2 东北走学硕士学位论文 第二章基于计算经济的网捂资瓣管理体系结构 2 2 2g r a c e 澳大利亚m o n a s h 大学i 拘b u y y a 教授基于y - 期对市场机制在分布式系统中应用 的研究成果，提出了经济学理论在网格中的运用并丌发了g r i d b u s e c o g r i d ，在文献 6 ，1 2 ，1 4 ，1 6 d f 深入探讨了网格环境中的基于经济学的分布式资源管理和调度 问题，基于一系列应用组件构造了一个计算经济的网格体系结构g r a c e ”。 g r a c e 是一个基于多种经济学模型之上的分布的、可计算的经济学体系框架， 用于在网格环境中进行资源交易。由于目前的一些网格系统，女f l g l o b u s 、l e g i o n 等已经提供了大量的成熟的可重用的中间件，例如资源协同分配服务d u r o c 、认 证和安全服务g s i 等等，所以g r a c e 并没有重新搭建一个网格平台，而是在g l o b u s 之上进行了扩展，补充了。些负责资源交易的中间件，例如网格f 订场目录g m d 、 网格交易服务器g t s 和用于电予交付的g b a n k 等等。上一章我们简单介绍了 g r a c e ，其中图1 1 体现了其的基本架构，下面洋细说明如下； g r a c e 侧重于研究网格资源的分配方式，主要包括以下四部分： 网格服务供应商g s p ( g r i ds e r v i c ep r o v i d e r ) ：包括地理上分布的所有互联资 源和网格中本地资源管理系统，主要是拥有资源的服务供应商( 相当于网格节点) 对资源进行合理的分配，以满足交易服务器和资源预约的要求。同时服务供应商 按照经济模型制定价格策略和交易原则，以求获得最大利益。交易服务器是服务 供应商本身的代理程序，遵循价格策略与用户仂、商资源使用价格，指导结账系统 记录资源消耗情况。网格服务供应商和网格用户，通过劂格银行和网格市场服务器 进行结算。 网格中间件服务层g m s ( g r i dm i d d l e s o f ts e r v i c e ) ：利用网格中间件实现了构 造经济网格模型所需的各种服务，其中包括登录、安全和服务质量控制，提供必 要的网格信息供网格浏览器查找所需资源，通过交易中间件连接交易服务器和交 易管理器，执行任务模块完成姿源的正确分配，存储中间件存储各种必要信息。 可以直接使用g l o b u s 或其他网格系统的相关中间件来提供这些功能。网格市场 目录g m d ( g r i dm a r k e td i r e c t o r y ) 类似于公告板，刚格资源提供者可在其上面发 布自己的资源相关信息，使得网格资源代理g r b 町以进行资源查找和选择。q b a n k 则是电子支付手段的一个范例，这方面研究有q b a n k 25 1 ，n e c h e q u e 【2 6 】，n e t c a s h ” 等。 网格资源代理层g r b ( g r i dr e s o u r c eb r o k e r ) ：负责资源发现、资源选择、资 源绑定等关键任务和计算初始化、单一资源映像等功能。资源经纪层由作业控制 1 3 东北大学硕士学住论文 第二章基于计算经济的网格资源管理体系结构 代理、调度顾问、网格浏览器、交易管理器和部署代理五部分组成。作业控制代 理负责接收用户作_ k 并规范化，它作为总控负责豁督程序的执行。调度顾问负责 资源发现和资源选择。交易管理器是负责与每个网格服务提供者的交易服务器进 行资源价格协商，在调度顾问的资源选择算法指导下，评估资源的访问开销，为 调度顾问提供资源选择依据。部，署代理负责将作q p 与实际资源进行绑定，在选定 的资源上激活任务，并周期性地向作业控制代理更新任务执行状态。网格浏览器 和资源调度器用于资源发现和选择。 网格用户层g c ( g r i dc l i e n t ) ：用户对网格系统提出自己的要求，包括所需资 源和交易所必须的信息，如价格、时间限制、偏好等。用户可使用网格应用程序， 直接囱网格经纪层提出要求，或者用户利用网格语言编程环境，编写自己的网格 程序提交给网格经纪层。用户可以通过w e b 在远程资源卜提交数据和收集结果。 在g r a c e 架构中交易管理器居于核心地位，g r b 完成资源选择后，其内部 的交易管理器就会与对应的资源提供者g s p 的交易管理器进行通信，讨论对资源 的使用问题，最主要的也就是价格问题。g r a c e 架构中提出了例如固定价格、拍 卖、垄断等多种经济学模型，提供了多种可选择的价格协商机制。现在中已经实 现了的网格资源代理g r b 模型，b u y y a 教授用大量实验证明使用n i m r o d g 作为 g r a c e 架构中的网格资源代理效果显著。 2 。2 3n i m r o d g n i m r o d g 1 2 1 是计算经济驱动的网格资源代理，它是d s t c ( 分布式系统技术 中心) 和m o n a s h 大学合作开发的一个1 具集，主要设计目标是提供基于网格环境 的大型分布式实验平台，提供。种简单的声明式参数化建模语言使用户可以规范 化他们所要提交的作业和需求，并使用经济学模型进行资源调度和协同分配。 n i m r o d g 通过n i m o r d 和g l o b u s 的软件来划多个域的资源进行使用就如同这些资 源属于个人域样。它基于计算经济的原则，还提山了独创的资源管理及作业调 度算法。 n i m r o d g 还提供了优秀的g u i 客户端，方便了用户的使用。目前n i m r o d g 在生物信息学、生态建模、c a d 、数字化电影制作方面都发挥了不小的作用，下 面对这些工具进行详细介绍： 简单的描述性编程语占可以同g u i 工具起创建脚本，将应用程序参数化为 数据文件；拥有可编程实体的网格资源代理，司用于对网格资