Contents
I Foundations1
1 Introduction3
1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3
1.2 Objectives and Contributions . . . . . . . . . . . . . . . . . . . . . . . . .4
1.3 Outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .6
2 Grid Technologies9
2.1 Evolution of Grid Technologies . . . . . . . . . . . . . . . . . . . . . . . .9
2.1.1 First Generation Grids . . . . . . . . . . . . . . . . . . . . . . . .10
2.1.2 Second Generation Grids . . . . . . . . . . . . . . . . . . . . . . .11
2.1.3 Third Generation Grids . . . . . . . . . . . . . . . . . . . . . . . .14
2.2 Open Grid Services Architecture - State of the Art . . . . . . . . . . . . .15
2.2.1 Service Oriented Architectures and Web Services . . . . . . . . . .16
2.2.2 OGSA Platform Architecture . . . . . . . . . . . . . . . . . . . . .19
2.2.3 Globus Toolkit 4 as a Reference Implementation . . . . . . . . . .20
2.3 Resource Management in Grids . . . . . . . . . . . . . . . . . . . . . . . .21
2.3.1 Requirements upon a Resource Allocation Manager . . . . . . . . .23
2.3.2 Resource Allocation Process . . . . . . . . . . . . . . . . . . . . .25
2.3.2.1Stage 1 - Resource Discovery . . . . . . . . . . . . . . .25
2.3.2.2Stage 2 - Resource Selection . . . . . . . . . . . . . . .27
2.3.2.3Stage 3 - Resource Usage . . . . . . . . . . . . . . . . .28
2.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .28
3 Moving Markets to the Grid31
3.1 Why Markets for the Grid? . . . . . . . . . . . . . . . . . . . . . . . . . .32
3.1.1 Community Sharing . . . . . . . . . . . . . . . . . . . . . . . . .32
3.1.2 Priority Sharing . . . . . . . . . . . . . . . . . . . . . . . . . . . .33
3.1.3 Fixed Pricing . . . . . . . . . . . . . . . . . . . . . . . . . . . . .34
3.1.4 Markets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .36
3.2 Foundations of Markets . . . . . . . . . . . . . . . . . . . . . . . . . . . .36
3.2.1 Microeconomic System Framework . . . . . . . . . . . . . . . . .36
3.2.1.1Economic Environment . . . . . . . . . . . . . . . . . .37
3.2.1.2Institution . . . . . . . . . . . . . . . . . . . . . . . . .39
3.2.1.3Agent Behavior . . . . . . . . . . . . . . . . . . . . . .40
3.2.1.4System Performance . . . . . . . . . . . . . . . . . . . .41
3.2.2 Mechanism Design . . . . . . . . . . . . . . . . . . . . . . . . . .43
3.2.2.1Revelation Principle . . . . . . . . . . . . . . . . . . . .44
3.2.2.2Vickrey-Clarke-Groves Mechanism . . . . . . . . . . . .45
3.2.2.3Impossibility Theorems . . . . . . . . . . . . . . . . . .47
3.2.3 Practical Mechanism Design . . . . . . . . . . . . . . . . . . . . .48
3.2.3.1Negotiations . . . . . . . . . . . . . . . . . . . . . . . .48
3.2.3.2Auctions . . . . . . . . . . . . . . . . . . . . . . . . . .49
3.3 Market Engineering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .52
3.3.1 Stage 1 - Environmental Analysis . . . . . . . . . . . . . . . . . .53
3.3.2 Stage 2 - Design and Implementation . . . . . . . . . . . . . . . .54
3.3.3 Stage 3 - Testing . . . . . . . . . . . . . . . . . . . . . . . . . . .54
3.3.4 Stage 4 - Introduction . . . . . . . . . . . . . . . . . . . . . . . .55
3.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .55
4 Environmental Analysis57
4.1 Environment De nition . . . . . . . . . . . . . . . . . . . . . . . . . . . .58
4.1.1 Trading Object De nition . . . . . . . . . . . . . . . . . . . . . .58
4.1.2 Market Segmentation . . . . . . . . . . . . . . . . . . . . . . . . .59
4.1.3 Market Targeting . . . . . . . . . . . . . . . . . . . . . . . . . . .61
4.1.4 Potential Participants . . . . . . . . . . . . . . . . . . . . . . . . .61
4.2 Requirement Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . .62
4.3 Meeting the Requirements . . . . . . . . . . . . . . . . . . . . . . . . . .63
4.3.1 Market Mechanisms for Load Balancing and Parallel Computing . .63
4.3.1.1PDP Auctions at Harvard University . . . . . . . . . . .63
4.3.1.2Ferguson's Load Balancing Approach . . . . . . . . . .64
4.3.1.3The Spawn System . . . . . . . . . . . . . . . . . . . .64
4.3.1.4Popcorn . . . . . . . . . . . . . . . . . . . . . . . . . .65
4.3.1.5Resource Coordination with ADAMCO . . . . . . . . .65
4.3.1.6Re ection . . . . . . . . . . . . . . . . . . . . . . . . .66
4.3.2 Market Mechanisms for Grids . . . . . . . . . . . . . . . . . . . .67
4.3.2.1Nimrod/G and the Computational Economy . . . . . . .67
4.3.2.2G-Commerce . . . . . . . . . . . . . . . . . . . . . . .67
4.3.2.3The Open Computation Exchange and Arbitration Network 68
4.3.2.4CATNETS . . . . . . . . . . . . . . . . . . . . . . . . .69
4.3.2.5Grosu and Das Approach . . . . . . . . . . . . . . . . .70
4.3.2.6The tsfGrid Auction . . . . . . . . . . . . . . . . . . . .72
4.3.2.7Re ection . . . . . . . . . . . . . . . . . . . . . . . . .73
4.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .75
II Design and Implementation77
5 Design of a Grid Market Mechanism79
5.1 Design Space for Combinatorial Auctions . . . . . . . . . . . . . . . . . .79
5.1.1 Combinatorial Bidding Languages . . . . . . . . . . . . . . . . . .80
5.1.2 Single Sided Combinatorial Auctions . . . . . . . . . . . . . . . .82
5.1.2.1Winner Determination . . . . . . . . . . . . . . . . . . .82
5.1.2.2Generalized Vickrey Auction . . . . . . . . . . . . . . .84
5.1.2.3Pricing Per Column . . . . . . . . . . . . . . . . . . . .86
5.1.2.4Iterative Combinatorial Auctions . . . . . . . . . . . . .86
5.1.3 Combinatorial Exchanges . . . . . . . . . . . . . . . . . . . . . .87
5.1.3.1Winner Determination . . . . . . . . . . . . . . . . . . .88
5.1.3.2Pricing . . . . . . . . . . . . . . . . . . . . . . . . . . .90
5.1.4 Re ection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .93
5.2 MACE: A Multi-Attribute Combinatorial Exchange . . . . . . . . . . . . .93
5.2.1 Bidding Language . . . . . . . . . . . . . . . . . . . . . . . . . .94
5.2.2 Winner Determination . . . . . . . . . . . . . . . . . . . . . . . .97
5.2.2.1Mixed Integer Program Formulation . . . . . . . . . . .97
5.2.2.2Example . . . . . . . . . . . . . . . . . . . . . . . . . . 100
5.2.3 Pricing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
5.2.3.1VCG Pricing . . . . . . . . . . . . . . . . . . . . . . . . 102
5.2.3.2Approximated VCG Pricing . . . . . . . . . . . . . . . . 103
5.2.3.3K-Pricing . . . . . . . . . . . . . . . . . . . . . . . . . 103
5.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
6 Implementation of the Market Mechanism107
6.1 Solving the Winner Determination Problem . . . . . . . . . . . . . . . . . 108
6.1.1 Exact Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
6.1.2 Tractable Special Cases . . . . . . . . . . . . . . . . . . . . . . . 109
6.1.3 Approximations . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
6.1.4 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
6.2 The MACE Market Service . . . . . . . . . . . . . . . . . . . . . . . . . . 111
6.2.1 Architectural Overview . . . . . . . . . . . . . . . . . . . . . . . . 111
6.2.1.1External Interfaces . . . . . . . . . . . . . . . . . . . . . 112
6.2.1.2Management Layer . . . . . . . . . . . . . . . . . . . . 112
6.2.1.3Mechanism Layer . . . . . . . . . . . . . . . . . . . . . 112
6.2.1.4Third Party Layer . . . . . . . . . . . . . . . . . . . . . 113
6.2.2 Application Areas . . . . . . . . . . . . . . . . . . . . . . . . . . 113
6.2.2.1CATNETS . . . . . . . . . . . . . . . . . . . . . . . . . 113
6.2.2.2Ontology-driven Markets . . . . . . . . . . . . . . . . . 114
6.3 Preliminary Requirement Satisfaction . . . . . . . . . . . . . . . . . . . . 114
6.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
III Evaluation117
7 Simulation Design119
7.1 Principles of Simulation . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
7.1.1 Basic Concepts . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
7.1.2 Stages in a Simulation Study . . . . . . . . . . . . . . . . . . . . . 121
7.1.3 Advantages and Disadvantages of Simulations . . . . . . . . . . . 122
7.2 Problem De nition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
7.2.1 Optimal Winner Determination . . . . . . . . . . . . . . . . . . . 123
7.2.1.1Computational Tractability . . . . . . . . . . . . . . . . 123
7.2.1.2Allocative Ef ciency . . . . . . . . . . . . . . . . . . . 124
7.2.1.3Incentive Compatibility . . . . . . . . . . . . . . . . . . 124
7.2.2 Approximated Winner Determination . . . . . . . . . . . . . . . . 125
7.2.2.1Allocative Ef ciency . . . . . . . . . . . . . . . . . . . 125
7.2.2.2Incentive Compatibility . . . . . . . . . . . . . . . . . . 126
7.2.3 Re ection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126
7.3 Simulation Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
7.3.1 Economic Environment . . . . . . . . . . . . . . . . . . . . . . . . 127
7.3.2 Market Mechanism . . . . . . . . . . . . . . . . . . . . . . . . . . 129
7.3.3 Behavior of Agents . . . . . . . . . . . . . . . . . . . . . . . . . . 129
7.4 Bidding Scenarios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
7.4.1 Generating Domain Independent Bids . . . . . . . . . . . . . . . . 130
7.4.2 Generating Realistic Bids . . . . . . . . . . . . . . . . . . . . . . 131
7.4.3 Simulation Settings . . . . . . . . . . . . . . . . . . . . . . . . . . 132
7.5 Model Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134
7.5.1 jCase - Java Combinatorial Auction Simulation Environment . . . 134
7.5.2 Veri cation and Validation . . . . . . . . . . . . . . . . . . . . . . 136
7.5.2.1Veri cation . . . . . . . . . . . . . . . . . . . . . . . . 136
7.5.2.2Validation . . . . . . . . . . . . . . . . . . . . . . . . . 136
7.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
8 Simulation Results139
8.1 Optimal Winner Determination . . . . . . . . . . . . . . . . . . . . . . . . 140
8.1.1 Computational Tractability . . . . . . . . . . . . . . . . . . . . . . 140
8.1.2 Manipulating Agents . . . . . . . . . . . . . . . . . . . . . . . . . 143
8.1.2.1Ef ciency Loss . . . . . . . . . . . . . . . . . . . . . . 143
8.1.2.2K-Price Incentive Compatibility . . . . . . . . . . . . . . 145
8.1.2.3Approximated VCG Incentive Compatibility . . . . . . . 149
8.1.2.4Re ection . . . . . . . . . . . . . . . . . . . . . . . . . 152
8.2 Approximated Winner Determination . . . . . . . . . . . . . . . . . . . . 153
8.2.1 Ef ciency Loss . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153
8.2.2 Incentive Compatibility . . . . . . . . . . . . . . . . . . . . . . . . 155
8.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159
9 Summary and Future Work161
9.1 Review of this Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162
9.2 Open Questions and Future Directions . . . . . . . . . . . . . . . . . . . . 163
9.2.1 Limitations and Potential Extensions of this Approach . . . . . . . 163
9.2.2 Real World Application . . . . . . . . . . . . . . . . . . . . . . . 164
Appendix169
A Proof of MACE Properties169
B Simulation Appendix173
B.1 CPLEX Settings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173
B.2 Results: Optimal Winner Determination . . . . . . . . . . . . . . . . . . . 174
B.2.1 Ef ciency Loss . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174
B.2.2 Manipulating Agents . . . . . . . . . . . . . . . . . . . . . . . . . 174
B.2.2.1 K-Price Incentive Compatibility . . . . . . . . . . . . . . 174
B.2.2.2 Approximated VCG Incentive Compatibility . . . . . . . 174
B.3 Results: Approximated Winner Determination . . . . . . . . . . . . . . . . 177
Bibliography179
Another Grid Computing Books
Download
No comments:
Post a Comment