//img.uscri.be/pth/19d65cd061e2a0849dbd713af9e2d8dbf57c3bc1
La lecture en ligne est gratuite
Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres
Télécharger Lire

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

215 pages
Björn SchnizlerResource Allocation in the Grid Studies on eOrganisation and Market Engineering 6Universität Karlsruhe (TH)Herausgeber:Prof. Dr. Christof Weinhardt. Thomas DreierProf. Dr. Rudi StuderResource Allocation in the Grid A Market Engineering Approachby Björn SchnizlerDissertation, genehmigt von der Fakultät für Wirtschaftswissenschaftender Universität Fridericiana zu Karlsruhe, 2007Referenten: Prof. Dr. Christof Weinhardt, Prof. Dr. Rudi StuderImpressumUniversitätsverlag Karlsruhec/o UniversitätsbibliothekStraße am Forum 2D-76131 Karlsruhewww.uvka.deDieses Werk ist unter folgender Creative Commons-Lizenz lizenziert: http://creativecommons.org/licenses/by-nc-nd/2.0/de/Universitätsverlag Karlsruhe 2007 Print on DemandISSN: 1862-8893ISBN: 978-3-86644-165-1AcknowledgementsThis work would not have come into being without the support of many colleagues andfriends. I am grateful to all those people who supported and inspired me while facing severalacademic and personal challenges.In particular, I am grateful to my thesis advisor Professor Dr. Christof Weinhardt. Hisvisionary ideas and his constant support and guidance encouraged me to overcome manyhurdles 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 fortheir support.
Voir plus Voir moins

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