PhD Theses at KOM

Monetary Efficiency in Infrastructure Clouds - Solution Strategies for Workload Distribution and Auction-based Capacity Allocation

Ulrich Lampe

Friday May 03, 2013

English abstract:

Since the early days of computing, a vision has been to provide Information Technology services in the form of a utility, just like water, electricity, or telephony. With the advancement of the cloud computing paradigm since the mid-2000s, this vision has been put into realization. Cloud computing builds on and combines multiple existing technologies and paradigms, such as virtualization and Service-Oriented Architecture, to deliver various forms of Information Technology services over the Internet. In this thesis, our focus is on the most elementary class of Information Technology: computing infrastructure. In this context, we examine two important research problems and propose solution strategies, based on the conjoint objective of monetary efficiency.
As the first major contribution, we introduce the so-called Cloud-orientedWorkload Distribution Problem (CWDP). This problem concerns the distribution of a workload, which comprises multiple computational jobs, across leased infrastructure. We assume the position of a cloud user, who aims at cost-minimal deployment under consideration of resource constraints. On the basis of a mathematical optimization model, we propose the exact solution approach CWDP-EXA.KOM. Given its high time complexity, we further propose the heuristic optimization approach CWDP-HEU.KOM, which is complemented by the improvement procedure CWDP-IMP.KOM. The practical applicability and performance of these optimization approaches is demonstrated using a quantitative evaluation, based on realistic data from the cloud computing market.
As the second key contribution, we examine the Equilibrium Price Auction Allocation Problem (EPAAP). This problem refers to the allocation of Virtual Machine instances based on an equilibrium price auction scheme. For that matter, we focus on the role of a cloud provider, who pursues the aim of profit maximization. We formalize the problem as an optimization model, which permits to deduce the exact optimization approach EPAAP-EXA.KOM. We further propose a heuristic optimization approach, named EPAAP-HEU.KOM, and improvement procedure EPAAP-IMP.KOM. All three approaches are thoroughly analyzed through a quantitative evaluation.

German abstract:

Seit der Frühzeit des Computers existiert die Vision, Informationstechnologie in der Form eines Versorgungsguts bereitzustellen, ähnlich wie Wasser, Strom oder Telephonie. Mit der zunehmenden Verbreitung des Cloud Computing-Paradigmas seit Mitte der 2000er-Jahre hat diese Vision ihre Umsetzung erfahren. Cloud Computing beruht auf und kombiniert verschiedene existierende Technologien und Paradigmen, darunter Virtualisierung und Service-orientierte Architekturen, um diverse Arten von Informationstechnologie-Diensten über das Internet bereitzustellen. In der vorliegeden Arbeit liegt der Schwerpunkt auf der elementarsten Klasse von Informationstechnologie: Infrastruktur. In diesem Kontext werden zwei wichtige Forschungsfragestellungen untersucht and zugehörige Lösungsansätze entwickelt, jeweils in Hinblick auf das übergeordnete Ziel monetärer Effizienz.
Der erste Kernbeitrag dieser Arbeit befasst sich mit dem sogenannten Cloudoriented Workload Distribution Problem (CWDP). Dieses Problem betrifft die Verteilung eines Workloads, welcher sich aus einer Menge von Jobs zusammensetzt, auf gemieteter Infrastruktur. Der Schwerpunkt liegt in diesem Zusammenhang auf der Sicht eines Cloud-Benutzers, welcher eine kostenminimale Verteilung unter Einhaltung von Ressourcenrestriktionen anstrebt. Auf Basis eines mathematischen Optimierungsmodells wird der exakte Lösungsansatz CWDP-EXA.KOM hergeleitet. Aufgrund von dessen hoher Zeitkomplexität wird ein heuristischer Lösungsansatz namens CWDP-HEU.KOM vorschlagen, welcher durch das Verbesserungsverfahren CWDP-IMP.KOM ergänzt wird. Die praktische Anwendbarkeit und Performanz der drei genannten Optimierungsansätze wird mittels einer quantitativen Evaluation untersucht, welcher reale Daten aus dem Cloud Computing-Markt zugrundeliegen.
Der zweite Kernbeitrag der Arbeit widmet sich dem sogenannten Equilibrium Price Auction Allocation Problem (EPAAP). Dieses betrifft die Allokation von Virtuellen Maschinen-Instanzen basierend auf einer Gleichgewichtspreisauktion. In diesem Zusammenhang liegt der Schwerpunkt der Betrachtung auf der Rolle eines Cloud-Anbieters, dessen Ziel in der Maximierung seiner Profite besteht. Die initiale Formalisierung des Problems als Optimierungsmodell gestattet die Ableitung eines exakten Lösungsverfahrens namens EPAAP-EXA.KOM. Weiterhin wird ein heuristisches Lösungsverfahren, EPAAP-HEU.KOM, sowie ein Verbesserungsverfahren, EPAAP-IMP.KOM, vorgeschlagen. Die drei Ansätze werden im Rahmen einer quantitativen Evaluation detailliert analysiert.

PhD Theses