网格经济学模型.ppt

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