网格经济学模型hlvb.pptx

GridComputing9-2TheGridEconomyLuWeinaNetworkandInformationCenter,USTC2007.4.262007-4-26 1 GridComputing 9-2 The Grid EconomyOutline INTRODUCTION 网格经济学模型 定价、计费和付费机制 几个相关项目 博弈论2007-4-26 2 GridComputing 9-2 The Grid EconomyResource Management and Scheduling资源消费者：Haveworktodoandneedstobemet资源提供者：Haveresourcesanddictateaccesstothem2007-4-26 3 GridComputing 9-2 The Grid EconomyResource Management and Scheduling 网格资源提供者GridResourceProvider(GRP)：为了吸引资源消费者，它们将提供具有竞争性服务入口，从而使它拥有的资源得到最大程度的使用 网格资源消费者GridResourceConsumer(GRC)：在其需要的时间限制内，希望能用最少的资源使用费用来解决它提出的问题。2007-4-26 4 GridComputing 9-2 The Grid EconomyResource Management and Scheduling System-centricpolicies(traditionalapproach)目的是获得系统范围性能的最优化 由一个调度部件基于成本函数决定哪个任务在哪个资源上运行 Legion,Condor,AppLeSPST,NetSolve,PUNCH Donottakeresourceaccesscost(price)intoconsideration 用户不想以高价购买而想通过协商定价 User-centricpolicies 目的是获得用户基于QoS 需求的效用的最大化 需要由经济学原则来驱动2007-4-26 5 GridComputing 9-2 The Grid EconomyResource Management and Scheduling 基于经济的方法 调度策略是在运行时动态制定的，由终端用户需求直接或间接驱动。终端用户以付费为代价,取代了传统的以运行应用所需要的软件和硬件成本为代价 价格策略基于供求2007-4-26 6 GridComputing 9-2 The Grid EconomyGrid Economy:Methodology for Managing Supply-and-Demand for Resources and Encouraging Resource Sharing2007-4-26 7 GridComputing 9-2 The Grid EconomyWhy Economics in Grid 在网格系统的实际应用中，大量的资源不是无偿使用的，要吸引资源的拥有者加入网格，就必须保证他们的利益，这就需要经济学理论作支持。网格是一个异构的、动态的分布式环境，对资源的使用和供应都是在不断的变化之中。通过引入经济学，特别是基于价格的市场机制，由价格浮动来反映资源供需情况的变化，通过供需均衡实现资源优化分配，能够很好地表现网格的动态特征。网格环境下的资源分配涉及到消费者、生产者的个体行为，微观经济学中的一些模型正好与之配合。2007-4-26 8 GridComputing 9-2 The Grid EconomyOutline INTRODUCTION 网格经济学模型 定价、计费和付费机制 几个相关项目 博弈论2007-4-26 9 GridComputing 9-2 The Grid Economy网格信息服务器（GIS）记录了网格中可用资源的信息,在网格环境中起中介和仲裁的作用 网格资源消费者欲寻找合适的资源,必须先向网格信息服务器查询,获得适合自己条件的资源的信息,然后再与资源提供者进行交互。网格资源提供者想要出售资源,必须先向网格信息服务器注册,资源消费者才可能找到这个资源。网格信息服务器还负责协调网格货币的流通。2007-4-26 10 GridComputing 9-2 The Grid Economy网格经济模型的特点 资源作为一种商品,其价格主要由该商品的供求状况所决定。GRC 和GRP 都可以来提出进行资源分配交易。GRP 和GRC 都致力于最大化他们自己的效用函数。GRP 提供资源时可以定义资源价格,价格有可能具有多个参数来反映资源的实际情况。网格计算环境必须提供合适的底层,包括安全、信息、远程资源的透明存取和信息服务等使我们能够将GRP 和GRC 联系在一起。2007-4-26 11 GridComputing 9-2 The Grid Economy常见模型 现有的用于网格资源交易管理的经济模型主要有:商品市场模型,牌价模型,议价模型,投标模型,拍卖模型,按比例分配资源模型,垄断模型等等。2007-4-26 12 GridComputing 9-2 The Grid Economy商品市场模型 由GRP 决定使用资源的价格,根据资源的使用量对网格资源消费者进行收费 资源价格的制定应该能够使资源的供求关系达到均衡。根据定价策略分成两种：价格不变：对供求变化不敏感 基于供求关系：当需求增加或者供给减少时,价格会增加直到市场达到新的供求均衡。2007-4-26 13 GridComputing 9-2 The Grid Economy商品市场模型2007-4-26 14 GridComputing 9-2 The Grid Economy商品市场模型 优点：资源消费者可以清楚地看到所有在网格中的资源和使用价格信息,以便消费者根据自己的QoS 需求来寻找合适的资源提供者。缺点：由于价格是按照供求情况事先确定好的,也不考虑到资源的利用效率,不管最后的服务质量是否达到要求,使用价格是不会改变的,所以缺乏一定的灵活性。2007-4-26 15 GridComputing 9-2 The Grid Economy牌价模型 牌价模型和商品价格模型很相似，区别是，为了吸引新的消费者去建立市场共享或鼓励使用者考虑使用更便宜的时间而发布专门的告示。在这种情况下，代理不直接和GSP 协商价格，而是使用牌价，通常这些价格比一般情况下的价格都更便宜。2007-4-26 16 GridComputing 9-2 The Grid Economy牌价模型2007-4-26 17 GridComputing 9-2 The Grid Economy招标模型 分布式环境中用于服务协商的最广泛的模型。一般步骤：l.消费者通告它的请求,同时从GSP 中邀请竞标。2.感兴趣的GSP 评估这个请求，并提交竞标价。3.代理对各个GSP 的竞标价进行评价，接着和最合适的GSP 签订协议。4.代理和GSP 进行私下的协商，并使用资源。2007-4-26 18 GridComputing 9-2 The Grid Economy招标模型 优点是，如果被选择的GSP 不能够提交一个令人满意的服务结果，它可以向别的GSP 寻找服务。招标模型允许不经过协商而直接签订合同。这种模型可以简化协议和提高某些服务的效率。2007-4-26 19 GridComputing 9-2 The Grid Economy拍卖模型 在拍卖模型中,处理的是一个GRP 对多个GRC的情况,其中主要有三类角色:资源提供者,资源消费者以及协调者。协调者是主持拍卖过程的角色,设定了一系列买方和卖方都认可的规则。2007-4-26 20 GridComputing 9-2 The Grid Economy拍卖模型2007-4-26 21 GridComputing 9-2 The Grid Economy拍卖模型 拍卖模型 上升拍卖（英式拍卖）下降拍卖（荷兰式拍卖）第一价格密封拍卖 第二价格密封拍卖（Vickrey 拍卖）.2007-4-26 22 GridComputing 9-2 The Grid Economy拍卖模型 从某种程度上来说保护了网格资源提供者GRP,对于GRP 来说比较有优势,也能让一些非常有能力的GRP 贡献出更好的资源,让消费者使用。但使用此类模型可能导致竞价过高,超过网格资源代理GRB 所能承受的范围。这个模型并不需要对全局价格信息有过多了解,比较容易实施。2007-4-26 23 GridComputing 9-2 The Grid EconomyOutline OVERVIEW 网格经济学模型 定价、计费和付费机制 几个相关项目 博弈论2007-4-26 24 GridComputing 9-2 The Grid Economy定价、计费、付费 在网格经济环境中，资源拥有者和使用者都希望能获得最大的收益。当有许多的GSP 提供相似的价格时，它们将需要一个竞争性的定价结构来吸引用户，高效率地使用资源和最大化收益。被用户应用所消费的资源需要记账并被计费，所以应有不同的付费机制。GSP 使用GridBank 等的系统，这些系统作为中间人协调服务计费的工作。2007-4-26 25 GridComputing 9-2 The Grid Economy如何确定价格 一个简单的定价方案是采用固定价格模型 基于不同参数的定价方案包括如下几种:统一定价模型 竞争性经济模型 使用时间.2007-4-26 26 GridComputing 9-2 The Grid Economy结算和付费的服务事项 用户的应用有不同的资源需求，这依赖于其执行的计算和解决问题时使用的算法。如下的资源消费需要进行记账和付费.CPU 使用时间和系统时间 内存 最大的常驻编排尺寸页面大小 页错误 使用的存储器 消费的网络带宽 信号接收 获取的软件和库2007-4-26 27 GridComputing 9-2 The Grid Economy付费机制 一个基于计算经济的网格框架需要支持不同的付费机制，它们包括 预先付费 先使用后付费 基于承认的 使用像GridBank 这样的中介机构2007-4-26 28 GridComputing 9-2 The Grid EconomyOutline INTRODUCTION 资源作为一种商品格经济学模型 定价、计费和付费机制 几个相关项目 博弈论2007-4-26 29 GridComputing 9-2 The Grid EconomyCompute Power Market CPM 计算力市场是网格环境下基于市场机制的资源和作业调度系统，它特别是针对低端个人计算设备设计的。传送元计算环境到一个计算市场，通过闲置的资源租用计算力，存贮，和特殊服务在计算市场中解决问题。CPM 主要由市场，资源消费者，资源提供者和它们的相互作用组成。它支持商品市场模型、合约模型、拍卖模型。2007-4-26 30 GridComputing 9-2 The Grid EconomyGESA GESA 即网格经济学服务框架(GridEconomicServicesArchitecture),是GlobalGridForum(GGF)的一个工作组计划，目标是在GGF 所提出的开放网格服务架构OGSA 之上制定关于网格经济学服务架构的一些标准和规范。其包括了网格经济学服务接口(GridEconomicServicesInterface,GESI)、可交易网格服务(ChargeableGridServices,CGS)和网格银行服务(GridBankingServices,GBS)几个关键项目2007-4-26 31 GridComputing 9-2 The Grid EconomyG-Commerce G-Commerce 是美国田纳西大学的研究项目，使用市场经济学中的商品市场和拍卖模型在网格中进行动态资源分配。在G-Commerce 中资源的价值是根据供需变化而变，对比了采用不同市场策略时的市场均衡，消费者效用和资源提供者效用.2007-4-26 32 GridComputing 9-2 The Grid EconomyGridbus/EcoGrid 澳大利亚的Buyya 深入探讨了网格环境中的基于经济学的分布式资源管理和调度问题，并设计了一系列应用组件,构架了一个通用的网格经济学框架GRACE(GRidArchitectureforComputationalEconomy）GRACE 是一个基于经济学模型的分布式、可计算的经济学体系框架，用于在网格环境中进行资源交易。它利用了目前的一些网格系统如Globus,Legion 等提供的大量、成熟、可重用的中间件，例如资源协同分配服务DUROC、认证和安全服务GSl 等等，并进行了扩展，补充负责资源交易的中间件，如网格市场服务GMS、网格交易服务器GTS 和用于电子支付的GBank 等等。2007-4-26 33 GridComputing 9-2 The Grid EconomyGRACE 架构2007-4-26 34 GridComputing 9-2 The Grid EconomyGRACE GRACE 架构中定义了一个网格资源经纪人(GRB)层，负责资源发现、选择和绑定等关键任务。其中作业控制代理负责接收用户作业;网格浏览器和资源调度器用于资源发现和选择;交易管理器负责与每个网格服务提供者的交易管理器进行资源价格协商:部署代理则将作业与实际资源进行绑定。网格中间件层负责提供认证、QOS 保障等基本服务，这些功能可以直接使用现有的Globus 或其他网格系统的相关中间件。网格市场服务GMS 类似于公告板，网格资源提供者可以在上面发布自己的资源相关信息，使得网格资源代理GRB 可以进行资源查找和选择。2007-4-26 35 GridComputing 9-2 The Grid EconomyGRACE 网格服务提供者层中的资源分配采用一些包括MOSIX、LSF 与Condor 那样的队列系统进行本地资源管理。在GRACE 架构中交易管理器居于核心地位，GRB 完成资源选择后，其内部的交易管理器就会与对应的资源提供者，也就是网格服务提供者GSP 的交易管理器进行通信，讨论对资源的使用问题，最主要的也就是价格问题。GRACE 架构中提出了固定价格、拍卖、垄断等多种经济学模型，提供了多种可选择的价格协商机制。2007-4-26 36 GridComputing 9-2 The Grid EconomyGRACE Nimrod-G 是GRACE 框架下的网格资源代理GRB 原型，使用Nimrod-G 作为GRACE 架构中的网格资源代理效果显著。定价算法基于两项最为重要的QoS 需求来设计，即作业运行时间(runtime)和预算(budget)。2007-4-26 37 GridComputing 9-2 The Grid Economy参考文献“TheGrideconomy”RajkumarBuyya,DavidAbramson,SrikumarVenugopal“GridResourceAllocationandControlUsingComputationalEconomies”R.Wolski,J.Brevik,J.PlankandT.Bryan“EconomicModelsforResourceManagementandSchedulinginGridComputing”R.Buyya,D.Abramson,J.GiddyandH.Stockinger GridEconomyComesofAge:GridbusTechnologiesforService-OrientedClusterandGridComputingR.Buyya Nimrod-G:AnArchitectureforaResourceManagementandSchedulingSysteminaGlobalComputationalGridR.Buyya,D.Abramson,J.Giddy“AuctionsforNetworkResourceSharing,”A.LazarandN.Semret“AMarket-OrientedGridDirectoryServiceforPublicationandDiscoveryofGridServiceProvidersandtheirServices,”J.Yu,S.Venugopal,andR.Buyya“AGridServiceBrokerforSchedulingDistributedData-OrientedApplicationsonGlobalGrids,”S.Venugopal,R.Buyya,andL.Winton,2007-4-26 38 GridComputing 9-2 The Grid Economy博弈论2007.4.262007-4-26 39 GridComputing 9-2 The Grid Economy 博弈论（game theory）：也叫对策论，所分析的是两个或两个以上的比赛者或参与者选择能够共同影响每一参加者的行动或策略的方式以及相应的均衡问题。博弈论2007-4-26 40 GridComputing 9-2 The Grid Economy 博弈论的指导思想：假设你的对手在研究你的策略，并采取追求自身最大利益行动的时候，你如何选择最有效的策略。策略选择占优策略（dominant strategy）：无论其他博弈者采用何种战略，该博弈者的策略总是最好的。2007-4-26 41 GridComputing 9-2 The Grid Economy占优均衡（dominant equilibrium）：在两个（或全部）博弈者都采用占优策略时的结果。纳什均衡（Nash equilibrium）：在其他博弈者的策略给定时，没有一方还能改善自己的获利的境况。2007-4-26 42 GridComputing 9-2 The Grid Economy智猪博弈猪圈里有两只猪，一只比较大，一只比较小。猪圈狭长，猪食槽在一头，猪食按钮在另一头，按一下会有8个单位的猪食落进槽里。由于按钮和食槽距离较远，按按钮的体力耗费相当于2个单位的食物。若大猪先到，大猪吃7个单位，小猪只能吃1个单位；若同时到，大猪吃5个单位，小猪吃3个单位；若小猪先到，大猪小猪各吃4个单位2007-4-26 43 GridComputing 9-2 The Grid Economy3，1 2，47，-1 0，0按按等待等待小猪大猪智猪博弈的纳什均衡：（按，等待）小猪的占优策略：等待智猪博弈的支付矩阵：大猪无占优策略2007-4-26 44 GridComputing 9-2 The Grid Economy 答案是：小猪将舒舒服服地等在食槽边，而大猪则为一点残羹不知疲倦地奔忙于按钮和食槽之间。“小猪躺着大猪跑”的现象是由于故事中的游戏规则所导致的。规则的核心指标是：每次落下的事物数量和按钮与投食口之间的距离。2007-4-26 45 GridComputing 9-2 The Grid Economy改变方案 改变方案一：减量方案。投食仅原来的一半分量。结果是小猪大猪都不去按按钮了。小猪去按，大猪将会把食物吃完；大猪去按，小猪将也会把食物吃完。谁去按按钮，就意味着为对方贡献食物，所以谁也不会有按按钮的动力了。如果目的是想让猪们去多按按钮，这个游戏规则的设计显然是失败的。2007-4-26 46 GridComputing 9-2 The Grid Economy 改变方案二：增量方案。投食为原来的一倍分量。结果是小猪、大猪都会去按按钮。谁想吃，谁就会去按按钮。反正对方不会一次把食物吃完。小猪和大猪相当于生活在物质相对丰富的“共产主义”社会，所以竞争意识却不会很强。对于游戏规则的设计者来说，这个规则的成本相当高（每次提供双份的食物）；而且因为竞争不强烈，想让猪们去多按按钮的效果并不好。2007-4-26 47 GridComputing 9-2 The Grid Economy 改变方案三：减量加移位方案。投食仅原来的一半分量，但同时将投食口移到按钮附近。结果呢，小猪和大猪都在拼命地抢着按按钮。等待者不得食，而多劳者多得。每次的收获刚好消费完。对于游戏设计者，这是一个最好的方案。成本不高，但收获最大。2007-4-26 48 GridComputing 9-2 The Grid Economy 原版的“智猪博弈”故事给了竞争中的弱者（小猪）以等待为最佳策略的启发。但是对于社会而言，因为小猪未能参与竞争，小猪搭便车时的社会资源配置的并不是最佳状态。为使资源最有效配置，规则的设计者是不愿看见有人搭便车的。而能否完全杜绝“搭便车”现象，就要看游戏规则的核心指标设置是否合适了。2007-4-26 49 GridComputing 9-2 The Grid Economy斗鸡博弈 假设有两个人举着火棍从独木桥的两端走向中央进行火拼，每个人都有两种战略：继续前进，或退下阵来。若两个人都继续前进，则两败俱伤；若一方前进另一方退下来，前进者取得胜利，退下来的丢了面子；若两人都退下来，两人都丢面子。2007-4-26 50 GridComputing 9-2 The Grid Economy-3，-3 2，00，2 0，0进进退退乙甲斗鸡博弈有两个纳什均衡：如果一方进，另一方的最优战略就是退。斗鸡博弈的支付矩阵：2007-4-26 51 GridComputing 9-2 The Grid Economy囚徒困境 两个嫌疑犯（和）作案后被警察抓住，隔离审讯；警方的政策是“坦白从宽，抗拒从严”，如果两人都坦白则各判年；如果一人坦白另一人不坦白，坦白的放出去，不坦白的判年；如果都不坦白则因证据不足各判1年。2007-4-26 52 GridComputing 9-2 The Grid Economy坦白 不坦白坦白-8,-8 0,-10不坦白-10,0 1,1Nash Equilibrium 2007-4-26 53 GridComputing 9-2 The Grid Economy三方对决 话说有三个仇家，分别叫做张三、李四和王五，他们决定来一场 话说有三个仇家，分别叫做张三、李四和王五，他们决定来一场三方对决。总共有 三方对决。总共有 两个回合 两个回合：第一回合，每人得到一次射击机会，射：第一回合，每人得到一次射击机会，射击次序分别为张三、李四和王五；第一回合过后，幸存者得到第二次 击次序分别为张三、李四和王五；第一回合过后，幸存者得到第二次射击机会，射击次序还是张三、李四和王五。射击机会，射击次序还是张三、李四和王五。对于每一个参与对决的人，最佳结果都是成为唯一幸存者；次佳 对于每一个参与对决的人，最佳结果都是成为唯一幸存者；次佳结果则是成为两个幸存者之一；排在第三位的结果，是无人死亡，最 结果则是成为两个幸存者之一；排在第三位的结果，是无人死亡，最差的结果当然是自己被对方打死。差的结果当然是自己被对方打死。2007-4-26 54 GridComputing 9-2 The Grid Economy张三的枪法最糟糕，瞄准张三的枪法最糟糕，瞄准1010次只有次只有33次能够打中次能够打中目标；李四的水平高一点，精确度有目标；李四的水平高一点，精确度有8080；王五；王五是神枪手，百发百中。是神枪手，百发百中。那么，张三的第一回合的最优策略应该是什么？那么，张三的第一回合的最优策略应该是什么？在这个问题里，谁有最大的机会幸存下来？在这个问题里，谁有最大的机会幸存下来？2007-4-26 55 GridComputing 9-2 The Grid Economy三方对决之分析假如张三先向李四开枪并打中对方，他等于签下自己的死亡保证书，因为接下来轮到王五，而他是百发百中。王五不可能放弃向张三开枪的机会，因为开枪将使他得到自己的最佳结果。所以，张三向李四开枪不是吸引人的选择。假如张三先向王五开枪并打中对方，接下来轮到李四，李四会向张三开枪，李四的精确度是80，所以张三活命的机会只有20。2007-4-26 56 GridComputing 9-2 The Grid Economy 到目前为止，上述选择没有一个显得很有吸引力。张三的最佳策略是什么呢？实际上，他的最佳策略是向空中开枪！若是这样，李四就会向王五开枪，假如他没打中，王五将向李四开枪并打死李四。于是进入第二轮，又轮到张三开枪了；由于只剩下一个对手，他至少有30的概率保住性命，因为这是他打中剩下这个对手的概率。2007-4-26 57 GridComputing 9-2 The Grid Economy 这个案例也说明一个道理：弱者可能通过放弃自己的第一个成功机会取得更好的结果。因此，你的幸存机会不仅取决于你自己的本事，还要看你威胁到的人。一个没有威胁到任何人的弱者，可能由于较强的对手相互残杀而幸存下来。王五是最厉害的神枪手，但在此案例中的幸存概率却最低，只有14。李四有56的取胜机会；张三的最佳策略使他能以30的精确度换取41.2的幸存概率。2007-4-26 58 GridComputing 9-2 The Grid Economy 经典博弈论 剪刀、石头、布 性别战.演化博弈论 鹰鸽博弈 雪堆博弈.2007-4-26 59 GridComputing 9-2 The Grid Economy参考文献 张维迎，博弈论与信息经济学，上海三联书店，1996 美Fudenberg、法Tirole，博弈论，中国人民大学出版，2002年（原著1991）法Laffont、Martimort，激励理论(第一卷)：委托代理模型，中国人民大学出版社，2002年 王则柯，博弈论平话，中国经济出版社 AGameTheoreticFrameworkforIncentivesinP2PSystems PricingDifferentiatedServices:AGame-TheoreticApproach RobustIncentiveTechniquesforPeer-to-PeerNetworks ConsideringAltruisminPeer-to-PeerInternetStreamingBroadcast 基于博弈论框架的p2p 激励模型2007-4-26 60 GridComputing 9-2 The Grid EconomyThankyou!2007-4-26 61 GridComputing 9-2 The Grid Economy