Distributed Resource Management with
Monetary Incentives
vorgelegt von
Diplom-Mathematiker
Andreas Tanner
aus Potsdam
von der Fakultät IV – Elektrotechnik und Informatik –
der Technischen Universität Berlin
zur Erlangung des akademischen Grades
Doktor der Naturwissenschaften
Dr. rer. nat.
genehmigte Dissertation
Promotionsausschuß:
Vorsitzender: Prof. Dr.-Ing. Adam Wolisz
Betreuer: Prof. Dr. Hans-Ulrich Heiß
Gutachter: Prof. Dr. Kurt Geihs
Gutachter: Prof. Giuseppe Persiano, Ph.D.
Tag der wissenschaftlichen Aussprache: 7. Juli 2005
Berlin 2005
D 83
2
Zusammenfassung
Moderne Kommunikationsnetzwerke erlauben die gleichzeitige Ausführung einer
Vielzahl von Anwendungen. So ist es nicht verwunderlich, dass Mechanismen zur
Ressourcenvergabe, seien es Übertragungsbandbreite oder Rechenkapazität, in der
Informatik seit langer Zeit erforscht werden. Jedoch gehen die klassischen Mecha-
nismen von
kooperierenden Nutzern
, die nicht versuchen, das System zu ihrem
Vorteil zu manipulieren, aus. Andererseits wird die informationstechnische Infra-
struktur schon aufgrund der hohen Installationskosten von Nutzern ohne gemein-
same Interessen und über Firmengrenzen hinweg genutzt. Stehen nun Ressourcen
in begrenzter Menge zur Verfügung, ist die Entstehung von Allokationskonflikten
unvermeidlich. Ein natürlicher Ansatz zur Lösung solcher Konflikte ist die Etablie-
rung eines
Marktes
für die Ressourcenvergabe.
Diese Arbeit schlägt Marktmechanismen für die Ressourcenvergabe in verteilten
Computersystemen vor. Wir präsentieren ein neues, budgetausgeglichenes Preis-
bildungsschema für kombinatorische Tauschmärkte, welches die Berechnung der
Akzeptanz von Geboten unabhängig agierender Handelspartner erlaubt. Ebenso
haben wir eine neue Methode zur Synchronisierung der Gebote entwickelt und
zeigen, dass sie einer periodischen oder zufälligen Marktbereinigung überlegen ist.
Die neu entwickelten Mechanismen wenden wir auf die Bandbreitenvergabe für
Punkt-zu-Punkt-Kommunikation an und zeigen mittels einer Simulationsrechnung,
dass die Auktionierung der Bandbreite für einen großen Teil des Parameterraumes
zu höherer Effizienz als ein Fixpreisverkauf führt, obwohl die Auktionierung – im
Unterschied zur Wahl eines optimalen Fixpreises – keine Informationen über die
statistische Verteilung der Gebote der Nutzer benötigt.
Die Situation für Gruppenkommunikation erweist sich als schwieriger. Kellys klas-
sischer Equlibriums-Mechanismus für die Bandbreitenvergabe verliert bei der An-
wendung auf Gruppenkommunikation seine Effizienz. Wir präsentieren eine – nicht
budgetausgeglichene – Verallgemeinerung von Feigenbaums Grenzkostenmechanis-
mus auf ein Gruppenkommunikationsszenario mit Publish/Subscribe-Struktur, und
entwickeln einen Algorithmus zur effizienten, verteilten Preisberechnung.
3
Abstract
Modern communication networks handle millions of applications simultaneously,
and mechanisms of resource sharing, most prominently sharing of data transmission
bandwidth and processing power, between competing jobs have been considered
in computer science since its beginning. Classical mechanisms, however, balance
claims of
cooperating
users that do not try to manipulate the system to their advan-
tage. Due to their cost of installation, information technology infrastructure has to
be used by clients with no joint interest: by individual users and accross borders of
companies. With resources available only in a limited quantity, allocation conflicts
do arise. It is natural to apply the classical remedy for conflict resolution and install
a
market
for the system’s resources.
This thesis proposes market mechanisms for resource allocation in distributed
computer systems. We define a new budget-balanced pricing scheme for combina-
torial exchanges that allows matching of bids of autonomous buyers and sellers. We
suggets a new bid synchronization rule and prove that it performs superior to peri-
odic and random bid clearing. We give an application of a combinatorial exchange
to unicast bandwidth allocation. We demonstrate by a simulation that, for a large
part of the parameter space, auctioning bandwidth performs superior to fixed price
bandwidth sale, while not requiring prior information on the distribution of bids.
The situation for unicast cost sharing is more complicated. After proving that
the classical equilibrium mechanism of Kelly can’t looses much efficiency if applied
to group communication, we present a generalization of Feigenbaum’s adoption of
marginal cost pricing to publish/subscribe settings. We also develop an algorithm
for efficient distributed price computation.
4
Danksagung
Diese Arbeit entstand während meiner Tätigkeit als wissenschaftlicher Mitarbeiter
am
Institut für Intelligente Netze und Management Verteilter Systeme
an der TU
Berlin.
Ich habe Herrn Prof. Dr. Kurt Geihs zu danken, der in seiner Zeit an der TU Berlin
für eine stimulierende Arbeitsumgebung sorgte, die mir eigenständige Forschung
ermöglicht hat, und der mich in der Wahl meines Forschungsthemas bestärkte.
Herr Prof. Dr. Hans-Ulrich Heiss stellte sich freundlicherweise als Gutachter zur
Verfügung und gab mir wertvolle Kritik und Anregungen in der Phase der Fertig-
stellung der Arbeit.
Gero Mühl ermutigte mich nachdrücklich, meine Ergebnisse zu Papier zu bringen.
Er und Michael A. Jaeger waren außerordentlich hilfreiche Koautoren und haben
mich durch unbeirrtes Insistieren zu größerer Präzision gezwungen. All meinen
Kollegen bin ich für die vielen anregenden Diskussionen, die mir halfen, die prak-
tische Anwendbarkeit meiner Ideen nicht aus den Augen zu verlieren, zutiefst zu
Dank verpflichtet.
Meiner Familie, und besonders meiner lieben Frau Ximena, danke ich für die
Ermutigung, sich auf das Wagnis Forschung einzulassen, und für die Geduld und
Nachsicht in der langen Zeit bis zur Fertigstellung der Arbeit.
5
Loading more pages...