Resource allocation in the Grid [Elektronische Ressource] : a market engineering approach / by Björn Schnizler

Sujets

• Informatik
• Handel

Informations

• Publié par: karlsruher_institut_fur_technologie
• Publié le: 01 janvier 2007
• Nombre de lectures: 16
• Langue: English
• Poids de l'ouvrage: 2 Mo

Extrait

Björn Schnizler
Resource Allocation in the Grid Studies on eOrganisation and Market Engineering 6
Universität Karlsruhe (TH)
Herausgeber:
Prof. Dr. Christof Weinhardt. Thomas Dreier
Prof. Dr. Rudi StuderResource Allocation in the Grid
A Market Engineering Approach
by
Björn SchnizlerDissertation, genehmigt von der Fakultät für Wirtschaftswissenschaften
der Universität Fridericiana zu Karlsruhe, 2007
Referenten: Prof. Dr. Christof Weinhardt, Prof. Dr. Rudi Studer
Impressum
Universitätsverlag Karlsruhe
c/o Universitätsbibliothek
Straße am Forum 2
D-76131 Karlsruhe
www.uvka.de
Dieses Werk ist unter folgender Creative Commons-Lizenz
lizenziert: http://creativecommons.org/licenses/by-nc-nd/2.0/de/
Universitätsverlag Karlsruhe 2007
Print on Demand
ISSN: 1862-8893
ISBN: 978-3-86644-165-1Acknowledgements
This work would not have come into being without the support of many colleagues and
friends. I am grateful to all those people who supported and inspired me while facing several
academic and personal challenges.
In particular, I am grateful to my thesis advisor Professor Dr. Christof Weinhardt. His
visionary ideas and his constant support and guidance encouraged me to overcome many
hurdles during my PhD studies.
In addition, I thank Professor Dr. Rudi Studer for co advising me. Thanks to my com
mittee members Professor Dr. Andreas Geyer Schulz and Professor Dr. Christian Hipp for
their support.
The work presented in this book was partially integrated into CATNETS, a project funded
by the European Union. I thank Professor Dr. Daniel Veit for managing the at the
University of Karlsruhe and for encouraging me during my work. Thanks to Professor Dr.
Torsten Eymann for acquiring and leading the project. Aside from all my project colleagues,
I particularly thank Dr. Omer Rana, Liviu Joita, and Pablo Chacin for helping me out with
several Grid related challenges.
I am indebted to my colleagues in the research group on Information and Market Engi
neering at the Institute of Information Systems and Management, University of Karlsruhe.
Thank you very much for your support and for being vital and collaborating colleagues. Par-
ticular thanks to Dr. Ilka Weber for her mathematical support and Dr. Dirk Neumann for
many fruitful discussions and debates. Thanks to Kiet Vo and Dr. Jörg Sandrock for their en
couragement and constant support. Several other colleagues deserve thanks for reading my
chapters and sharing ideas: Thanks to Carsten Block, Dr. Clemens van Dinther, Dr. Matthias
Kunzelmann, and Stefan Luckner.
In addition, I thank Dr. Peter Haase and Holger Rau for their feedback and their constant
support. I am grateful to Bess Dawson, Ashley Nicholson, and Nadine Scholz for proofread
ing parts of the book.
Personally, I am grateful to my mother Inge for enabling my education and for supporting
and encouraging me in finishing this work.
Björn Schnizler
iiiivContents
I Foundations 1
1 Introduction 3
1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Objectives and Contributions . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.3 Outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2 Grid Technologies 9
2.1 Evolution of Grid Technologies . . . . . . . . . . . . . . . . . . . . . . . . 9
2.1.1 First Generation Grids . . . . . . . . . . . . . . . . . . . . . . . . 10
2.1.2 Second 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.1 Stage 1 – Resource Discovery . . . . . . . . . . . . . . . 25
2.3.2.2 Stage 2 – Selection . . . . . . . . . . . . . . . 27
2.3.2.3 Stage 3 – Resource Usage . . . . . . . . . . . . . . . . . 28
2.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3 Moving Markets to the Grid 31
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.1 Economic Environment . . . . . . . . . . . . . . . . . . 37
3.2.1.2 Institution . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.2.1.3 Agent Behavior . . . . . . . . . . . . . . . . . . . . . . 40
3.2.1.4 System Performance . . . . . . . . . . . . . . . . . . . . 41
3.2.2 Mechanism Design . . . . . . . . . . . . . . . . . . . . . . . . . . 43
3.2.2.1 Revelation Principle . . . . . . . . . . . . . . . . . . . . 44
3.2.2.2 Vickrey Clarke Groves Mechanism . . . . . . . . . . . . 45
vvi CONTENTS
3.2.2.3 Impossibility Theorems . . . . . . . . . . . . . . . . . . 47
3.2.3 Practical Mechanism Design . . . . . . . . . . . . . . . . . . . . . 48
3.2.3.1 Negotiations . . . . . . . . . . . . . . . . . . . . . . . . 48
3.2.3.2 Auctions . . . . . . . . . . . . . . . . . . . . . . . . . . 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 Analysis 57
4.1 Environment Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
4.1.1 Trading Object Definition . . . . . . . . . . . . . . . . . . . . . . 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.1 PDP Auctions at Harvard University . . . . . . . . . . . 63
4.3.1.2 Ferguson’s Load Balancing Approach . . . . . . . . . . 64
4.3.1.3 The Spawn System . . . . . . . . . . . . . . . . . . . . 64
4.3.1.4 Popcorn . . . . . . . . . . . . . . . . . . . . . . . . . . 65
4.3.1.5 Resource Coordination with ADAMCO . . . . . . . . . 65
4.3.1.6 Reflection . . . . . . . . . . . . . . . . . . . . . . . . . 66
4.3.2 Market Mechanisms for Grids . . . . . . . . . . . . . . . . . . . . 67
4.3.2.1 Nimrod/G and the Computational Economy . . . . . . . 67
4.3.2.2 G Commerce . . . . . . . . . . . . . . . . . . . . . . . 67
4.3.2.3 The Open Computation Exchange and Arbitration Network 68
4.3.2.4 CATNETS . . . . . . . . . . . . . . . . . . . . . . . . . 69
4.3.2.5 Grosu and Das Approach . . . . . . . . . . . . . . . . . 70
4.3.2.6 The tsfGrid Auction . . . . . . . . . . . . . . . . . . . . 72
4.3.2.7 Reflection . . . . . . . . . . . . . . . . . . . . . . . . . 73
4.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
II Design and Implementation 77
5 Design of a Grid Market Mechanism 79
5.1 Design Space for Combinatorial Auctions . . . . . . . . . . . . . . . . . . 79
5.1.1 Combinatorial Bidding Languages . . . . . . . . . . . . . . . . . . 80
5.1.2 Single Sided Auctions . . . . . . . . . . . . . . . . 82
5.1.2.1 Winner Determination . . . . . . . . . . . . . . . . . . . 82
5.1.2.2 Generalized Vickrey Auction . . . . . . . . . . . . . . . 84
5.1.2.3 Pricing Per Column . . . . . . . . . . . . . . . . . . . . 86
5.1.2.4 Iterative Combinatorial Auctions . . . . . . . . . . . . . 86
5.1.3 Combinatorial Exchanges . . . . . . . . . . . . . . . . . . . . . . 87
5.1.3.1 Winner Determination . . . . . . . . . . . . . . . . . . . 88