網(wǎng)格經(jīng)濟學模型

GridComputing9-2

TheGridEconomyLuWeinaNetworkandInformationCenter,USTCweinalu@2007.4.26OutlineINTRODUCTION網(wǎng)格經(jīng)濟學模型定價、計費和付費機制幾個相關項目博弈論ResourceManagementandScheduling資源消費者：Haveworktodoandneedstobemet資源提供者：HaveresourcesanddictateaccesstothemResourceManagementandScheduling網(wǎng)格資源提供者GridResourceProvider(GRP)：為了吸引資源消費者，它們將提供具有競爭性服務入口，從而使它擁有的資源得到最大程度的使用網(wǎng)格資源消費者GridResourceConsumer(GRC)：在其需要的時間限制內(nèi)，希望能用最少的資源使用費用來解決它提出的問題。ResourceManagementandSchedulingSystem-centricpolicies(traditionalapproach)目的是獲得系統(tǒng)范圍性能的最優(yōu)化由一個調(diào)度部件基于成本函數(shù)決定哪個任務在哪個資源上運行Legion,Condor,AppLeSPST,

NetSolve,PUNCHDonottakeresourceaccesscost(price)intoconsideration用戶不想以高價購買而想通過協(xié)商定價User-centricpolicies目的是獲得用戶基于QoS需求的效用的最大化需要由經(jīng)濟學原則來驅(qū)動ResourceManagementandScheduling基于經(jīng)濟的方法調(diào)度策略是在運行時動態(tài)制定的，由終端用戶需求直接或間接驅(qū)動。終端用戶以付費為代價,取代了傳統(tǒng)的以運行應用所需要的軟件和硬件成本為代價價格策略基于供求GridEconomy:MethodologyforManaging

Supply-and-DemandforResourcesandEncouragingResourceSharingWhyEconomicsinGrid在網(wǎng)格系統(tǒng)的實際應用中，大量的資源不是無償使用的，要吸引資源的擁有者加入網(wǎng)格，就必須保證他們的利益，這就需要經(jīng)濟學理論作支持。網(wǎng)格是一個異構的、動態(tài)的分布式環(huán)境，對資源的使用和供應都是在不斷的變化之中。通過引入經(jīng)濟學，特別是基于價格的市場機制，由價格浮動來反映資源供需情況的變化，通過供需均衡實現(xiàn)資源優(yōu)化分配，能夠很好地表現(xiàn)網(wǎng)格的動態(tài)特征。網(wǎng)格環(huán)境下的資源分配涉及到消費者、生產(chǎn)者的個體行為，微觀經(jīng)濟學中的一些模型正好與之配合。OutlineINTRODUCTION網(wǎng)格經(jīng)濟學模型定價、計費和付費機制幾個相關項目博弈論網(wǎng)格信息服務器（GIS）記錄了網(wǎng)格中可用資源的信息,在網(wǎng)格環(huán)境中起中介和仲裁的作用網(wǎng)格資源消費者欲尋找合適的資源,必須先向網(wǎng)格信息服務器查詢,獲得適合自己條件的資源的信息,然后再與資源提供者進行交互。網(wǎng)格資源提供者想要出售資源,必須先向網(wǎng)格信息服務器注冊,資源消費者才可能找到這個資源。網(wǎng)格信息服務器還負責協(xié)調(diào)網(wǎng)格貨幣的流通。網(wǎng)格經(jīng)濟模型的特點資源作為一種商品,其價格主要由該商品的供求狀況所決定。GRC和GRP都可以來提出進行資源分配交易。GRP和GRC都致力于最大化他們自己的效用函數(shù)。GRP提供資源時可以定義資源價格,價格有可能具有多個參數(shù)來反映資源的實際情況。網(wǎng)格計算環(huán)境必須提供合適的底層,包括安全、信息、遠程資源的透明存取和信息服務等使我們能夠?qū)RP和GRC聯(lián)系在一起。常見模型現(xiàn)有的用于網(wǎng)格資源交易管理的經(jīng)濟模型主要有:商品市場模型,

牌價模型,議價模型,投標模型,

拍賣模型,按比例分配資源模型,壟斷模型等等。商品市場模型由GRP決定使用資源的價格,根據(jù)資源的使用量對網(wǎng)格資源消費者進行收費資源價格的制定應該能夠使資源的供求關系達到均衡。根據(jù)定價策略分成兩種：價格不變：對供求變化不敏感基于供求關系：當需求增加或者供給減少時,價格會增加直到市場達到新的供求均衡。商品市場模型商品市場模型優(yōu)點：資源消費者可以清楚地看到所有在網(wǎng)格中的資源和使用價格信息,以便消費者根據(jù)自己的QoS需求來尋找合適的資源提供者。缺點：由于價格是按照供求情況事先確定好的,也不考慮到資源的利用效率,不管最后的服務質(zhì)量是否達到要求,使用價格是不會改變的,所以缺乏一定的靈活性。牌價模型牌價模型和商品價格模型很相似，區(qū)別是，為了吸引新的消費者去建立市場共享或鼓勵使用者考慮使用更便宜的時間而發(fā)布專門的告示。在這種情況下，代理不直接和GSP協(xié)商價格，而是使用牌價，通常這些價格比一般情況下的價格都更便宜。牌價模型招標模型分布式環(huán)境中用于服務協(xié)商的最廣泛的模型。一般步驟：l.消費者通告它的請求,同時從GSP中邀請競標。2.感興趣的GSP評估這個請求，并提交競標價。3.代理對各個GSP的競標價進行評價，接著和最合適的GSP簽訂協(xié)議。4.代理和GSP進行私下的協(xié)商，并使用資源。招標模型優(yōu)點是，如果被選擇的GSP不能夠提交一個令人滿意的服務結(jié)果，它可以向別的GSP尋找服務。招標模型允許不經(jīng)過協(xié)商而直接簽訂合同。這種模型可以簡化協(xié)議和提高某些服務的效率。拍賣模型在拍賣模型中,處理的是一個GRP對多個GRC的情況,其中主要有三類角色:資源提供者,資源消費者以及協(xié)調(diào)者。協(xié)調(diào)者是主持拍賣過程的角色,設定了一系列買方和賣方都認可的規(guī)則。拍賣模型拍賣模型拍賣模型上升拍賣（英式拍賣）下降拍賣（荷蘭式拍賣）第一價格密封拍賣第二價格密封拍賣（Vickrey拍賣）......拍賣模型從某種程度上來說保護了網(wǎng)格資源提供者GRP,對于GRP來說比較有優(yōu)勢,也能讓一些非常有能力的GRP貢獻出更好的資源,讓消費者使用。但使用此類模型可能導致競價過高,超過網(wǎng)格資源代理GRB所能承受的范圍。這個模型并不需要對全局價格信息有過多了解,比較容易實施。OutlineOVERVIEW網(wǎng)格經(jīng)濟學模型定價、計費和付費機制幾個相關項目博弈論定價、計費、付費在網(wǎng)格經(jīng)濟環(huán)境中，資源擁有者和使用者都希望能獲得最大的收益。當有許多的GSP提供相似的價格時，它們將需要一個競爭性的定價結(jié)構來吸引用戶，高效率地使用資源和最大化收益。被用戶應用所消費的資源需要記賬并被計費，所以應有不同的付費機制。GSP使用GridBank等的系統(tǒng)，這些系統(tǒng)作為中間人協(xié)調(diào)服務計費的工作。如何確定價格一個簡單的定價方案是采用固定價格模型基于不同參數(shù)的定價方案包括如下幾種:統(tǒng)一定價模型競爭性經(jīng)濟模型使用時間......結(jié)算和付費的服務事項用戶的應用有不同的資源需求，這依賴于其執(zhí)行的計算和解決問題時使用的算法。如下的資源消費需要進行記賬和付費.CPU－使用時間和系統(tǒng)時間內(nèi)存最大的常駐編排尺寸－頁面大小頁錯誤使用的存儲器消費的網(wǎng)絡帶寬信號接收獲取的軟件和庫付費機制一個基于計算經(jīng)濟的網(wǎng)格框架需要支持不同的付費機制，它們包括預先付費先使用后付費基于承認的使用像GridBank這樣的中介機構OutlineINTRODUCTION資源作為一種商品格經(jīng)濟學模型定價、計費和付費機制幾個相關項目博弈論ComputePowerMarketCPM計算力市場是網(wǎng)格環(huán)境下基于市場機制的資源和作業(yè)調(diào)度系統(tǒng)，它特別是針對低端個人計算設備設計的。傳送元計算環(huán)境到一個計算市場，通過閑置的資源租用計算力，存貯，和特殊服務在計算市場中解決問題。CPM主要由市場，資源消費者，資源提供者和它們的相互作用組成。它支持商品市場模型、合約模型、拍賣模型。GESAGESA即網(wǎng)格經(jīng)濟學服務框架(GridEconomicServicesArchitecture),是GlobalGridForum(GGF)的一個工作組計劃，目標是在GGF所提出的開放網(wǎng)格服務架構OGSA之上制定關于網(wǎng)格經(jīng)濟學服務架構的一些標準和規(guī)范。其包括了網(wǎng)格經(jīng)濟學服務接口(GridEconomicServicesInterface,GESI)、可交易網(wǎng)格服務(ChargeableGridServices,CGS)和網(wǎng)格銀行服務(GridBankingServices,GBS)幾個關鍵項目G-CommerceG-Commerce是美國田納西大學的研究項目，使用市場經(jīng)濟學中的商品市場和拍賣模型在網(wǎng)格中進行動態(tài)資源分配。在G-Commerce中資源的價值是根據(jù)供需變化而變，對比了采用不同市場策略時的市場均衡，消費者效用和資源提供者效用.Gridbus/EcoGrid澳大利亞的Buyya深入探討了網(wǎng)格環(huán)境中的基于經(jīng)濟學的分布式資源管理和調(diào)度問題，并設計了一系列應用組件,構架了一個通用的網(wǎng)格經(jīng)濟學框架GRACE(GRidArchitectureforComputationalEconomy）GRACE是一個基于經(jīng)濟學模型的分布式、可計算的經(jīng)濟學體系框架，用于在網(wǎng)格環(huán)境中進行資源交易。它利用了目前的一些網(wǎng)格系統(tǒng)如Globus,Legion等提供的大量、成熟、可重用的中間件，例如資源協(xié)同分配服務DUROC、認證和安全服務GSl等等，并進行了擴展，補充負責資源交易的中間件，如網(wǎng)格市場服務GMS、網(wǎng)格交易服務器GTS和用于電子支付的GBank等等。GRACE架構GRACEGRACE架構中定義了一個網(wǎng)格資源經(jīng)紀人(GRB)層，負責資源發(fā)現(xiàn)、選擇和綁定等關鍵任務。其中作業(yè)控制代理負責接收用戶作業(yè);網(wǎng)格瀏覽器和資源調(diào)度器用于資源發(fā)現(xiàn)和選擇;交易管理器負責與每個網(wǎng)格服務提供者的交易管理器進行資源價格協(xié)商:部署代理則將作業(yè)與實際資源進行綁定。網(wǎng)格中間件層負責提供認證、QOS保障等基本服務，這些功能可以直接使用現(xiàn)有的Globus或其他網(wǎng)格系統(tǒng)的相關中間件。網(wǎng)格市場服務GMS類似于公告板，網(wǎng)格資源提供者可以在上面發(fā)布自己的資源相關信息，使得網(wǎng)格資源代理GRB可以進行資源查找和選擇。GRACE網(wǎng)格服務提供者層中的資源分配采用一些包括MOSIX、LSF與Condor那樣的隊列系統(tǒng)進行本地資源管理。在GRACE架構中交易管理器居于核心地位，GRB完成資源選擇后，其內(nèi)部的交易管理器就會與對應的資源提供者，也就是網(wǎng)格服務提供者GSP的交易管理器進行通信，討論對資源的使用問題，最主要的也就是價格問題。GRACE架構中提出了固定價格、拍賣、壟斷等多種經(jīng)濟學模型，提供了多種可選擇的價格協(xié)商機制。GRACENimrod-G是GRACE框架下的網(wǎng)格資源代理GRB原型，使用Nimrod-G作為GRACE架構中的網(wǎng)格資源代理效果顯著。定價算法基于兩項最為重要的QoS需求來設計，即作業(yè)運行時間(runtime)和預算(budget)。參考文獻“TheGrideconomy”RajkumarBuyya,DavidAbramson,SrikumarVenugopal“GridResourceAllocationandControlUsingComputationalEconomies”R.Wolski,J.Brevik,J.PlankandT.Bryan“EconomicModelsforResourceManagementandSchedulinginGridComputing”R.Buyya,D.Abramson,J.GiddyandH.StockingerGridEconomyComesofAge:GridbusTechnologiesforService-OrientedClusterandGridComputingR.BuyyaNimrod-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,博弈論weinalu@2007.4.26博弈論

（gametheory）：也叫對策論，所分析的是兩個或兩個以上的比賽者或參與者選擇能夠共同影響每一參加者的行動或策略的方式以及相應的均衡問題。博弈論博弈論的指導思想：假設你的對手在研究你的策略，并采取追求自身最大利益行動的時候，你如何選擇最有效的策略。策略選擇占優(yōu)策略（dominantstrategy）：無論其他博弈者采用何種戰(zhàn)略，該博弈者的策略總是最好的。占優(yōu)均衡（dominantequilibrium）：在兩個（或全部）博弈者都采用占優(yōu)策略時的結(jié)果。納什均衡（Nashequilibrium）：在其他博弈者的策略給定時，沒有一方還能改善自己的獲利的境況。智豬博弈

豬圈里有兩只豬，一只比較大，一只比較小。豬圈狹長，豬食槽在一頭，豬食按鈕在另一頭，按一下會有8個單位的豬食落進槽里。由于按鈕和食槽距離較遠，按按鈕的體力耗費相當于2個單位的食物。若大豬先到，大豬吃7個單位，小豬只能吃1個單位；若同時到，大豬吃5個單位，小豬吃3個單位；若小豬先到，大豬小豬各吃4個單位3，12，47，-10，0按按等待等待小豬大豬智豬博弈的納什均衡：（按，等待）小豬的占優(yōu)策略：等待智豬博弈的支付矩陣：大豬無占優(yōu)策略答案是：小豬將舒舒服服地等在食槽邊，而大豬則為一點殘羹不知疲倦地奔忙于按鈕和食槽之間?！靶∝i躺著大豬跑”的現(xiàn)象是由于故事中的游戲規(guī)則所導致的。規(guī)則的核心指標是：每次落下的事物數(shù)量和按鈕與投食口之間的距離。改變方案改變方案一：減量方案。投食僅原來的一半分量。結(jié)果是小豬大豬都不去按按鈕了。小豬去按，大豬將會把食物吃完；大豬去按，小豬將也會把食物吃完。誰去按按鈕，就意味著為對方貢獻食物，所以誰也不會有按按鈕的動力了。

如果目的是想讓豬們?nèi)ザ喟窗粹o，這個游戲規(guī)則的設計顯然是失敗的。

改變方案二：增量方案。投食為原來的一倍分量。結(jié)果是小豬、大豬都會去按按鈕。誰想吃，誰就會去按按鈕。反正對方不會一次把食物吃完。小豬和大豬相當于生活在物質(zhì)相對豐富的“共產(chǎn)主義”社會，所以競爭意識卻不會很強。

對于游戲規(guī)則的設計者來說，這個規(guī)則的成本相當高（每次提供雙份的食物）；而且因為競爭不強烈，想讓豬們?nèi)ザ喟窗粹o的效果并不好。

改變方案三：減量加移位方案。投食僅原來的一半分量，但同時將投食口移到按鈕附近。結(jié)果呢，小豬和大豬都在拼命地搶著按按鈕。等待者不得食，而多勞者多得。每次的收獲剛好消費完。

對于游戲設計者，這是一個最好的方案。成本不高，但收獲最大。

原版的“智豬博弈”故事給了競爭中的弱者（小豬）以等待為最佳策略的啟發(fā)。但是對于社會而言，因為小豬未能參與競爭，小豬搭便車時的社會資源配置的并不是最佳狀態(tài)。為使資源最有效配置，規(guī)則的設計者是不愿看見有人搭便車的。而能否完全杜絕“搭便車”現(xiàn)象，就要看游戲規(guī)則的核心指標設置是否合適了。斗雞博弈假設有兩個人舉著火棍從獨木橋的兩端走向中央進行火拼，每個人都有兩種戰(zhàn)略：繼續(xù)前進，或退下陣來。若兩個人都繼續(xù)前進，則兩敗俱傷；若一方前進另一方退下來，前進者取得勝利，退下來的丟了面子；若兩人都退下來，兩人都丟面子。-3，-32，00，20，0進進退退乙甲斗雞博弈有兩個納什均衡：如果一方進，另一方的最優(yōu)戰(zhàn)略就是退。斗雞博弈的支付矩陣：囚徒困境兩個嫌疑犯（Ａ和Ｂ）作案后被警察抓住，隔離審訊；警方的政策是“坦白從寬，抗拒從嚴”，如果兩人都坦白則各判８年；如果一人坦白另一人不坦白，坦白的放出去，不坦白的判１０年；如果都不坦白則因證據(jù)不足各判1年。

NashEquilibrium

三方對決

話說有三個仇家，分別叫做張三、李四和王五，他們決定來一場三方對決?？偣灿袃蓚€回合：第一回合，每人得到一次射擊機會，射擊次序分別為張三、李四和王五；第一回合過后，幸存者得到第二次射擊機會，射擊次序還是張三、李四和王五。

對于每一個參與對決的人，最佳結(jié)果都是成為唯一幸存者；次佳結(jié)果則是成為兩個幸存者之一；排在第三位的結(jié)果，是無人死亡，最差的結(jié)果當然是自己被對方打死。張三的槍法最糟糕，瞄準10次只有3次能夠打中目標；李四的水平高一點，精確度有80％；王五是神槍手，百發(fā)百中。

那么，張三的第一回合的最優(yōu)策略應該是什么？在這個問題里，誰有最大的機會幸存下來？三方對決之分析

假如張三先向李四開槍并打中對方，他等于簽下自己的死亡保證書，因為接下來輪到王五，而他是百發(fā)百中。王五不可能放棄向張三開槍的機會，因為開槍將使他得到自己的最佳結(jié)果。所以，張三向李四開槍不是吸引人的選擇。

假如張三先向王五開槍并打中對方，接下來輪到李四，李四會向張三開槍，李四的精確度是80％，所以張三活命的機會只有20％。