Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-5340
Main Title: CloudNet embeddings
Subtitle: reliable performance for elastic cloud environments
Translated Title: CloudNet-Einbettungen
Translated Subtitle: zuverlässige Performanz in elastischen Cloud Umgebungen
Author(s): Fürst, Carlo
Advisor(s): Feldmann, Anja
Referee(s): Schmid, Stefan
Michiardi, Pietro
Costa, Paolo
Granting Institution: Technische Universität Berlin
Type: Doctoral Thesis
Language Code: en
Abstract: In multi-tenant cloud computing environments, such as Amazon EC2 or Microsoft Azure, the absence of strict network performance guarantees leads to unpredictable job execution times. To address this issue, there have been proposals to combine both guarantees on computing resources with guarantees on communication resources into an abstraction called a CloudNet. Multiple tenants can request CloudNet instances from a cloud provider. These requests amount to computationally challenging embedding problems which the provider must solve to realize the requests subject to resource constraints, or reject the requests. While the problem of resourceaware embeddings is well known, the shift toward cloud computing introduces key requirements which remain to be comprehensively addressed. In this work, we analyze two of these requirements and improve the way in which CloudNets are embedded to provide more options towards the tenant and increase the overall resource utilization of the provider. The first considered requirement of today’s cloud environments is the timeliness of the embedding process. Since the embedding problem is NP-hard, many prior solutions simplify the problem by introducing additional constraints to reduce the runtime. In this work, we consider two such constraints in more detail: The first constraint is that only one virtual machine of a tenant can be executed on one server. We show that this restriction comes at a high price and provide an optimal and generic preprocessor that allows all embedding algorithms to circumvent this constraint. The second constraint is on the topological flexibility of the CloudNets. While the general CloudNet embedding problem assumes that CloudNets form arbitrary topologies, simplifying abstractions, e.g. the virtual cluster, assume star-shaped CloudNets. We show that this subproblem of the CloudNet embedding problem is, contrary to previous beliefs, computationally tractable and show that it can even be solved taking data locality into account. The second requirement of today’s cloud environments which we address in this work is elasticity — the tenants can in- or decrease the size of their deployment at any time. We argue that the known approaches for providing dynamic CloudNets are not sufficient: Prior solutions to the embedding problem require the tenants to specify their resource demands, including up- and downgrades of bandwidth at deployment time, i.e., when they initially request their resources. This is at odds with the cloud paradigm and the way in which tenants interact with cloud providers nowadays. To overcome this problem, we propse a system called Kraken which can embed and modify virtual clusters in an online fashion. Kraken comes with an average runtime of 0.1 seconds for up to 16k servers and is provably optimal, as it minimizes reconfiguration and resource costs.
Es ist bekannt, dass ohne Garantien für Netzwerkressourcen die Performanz von Cloudanwendungen leidet und die Ausführungszeit unvorhersehbar wird. Deshalb ist es nötig, sowohl Garantien auf Rechenleistung und Netzwerk zu geben, und eine sogenannte CloudNet Abstraktion zu schaffen. Wenn ein Kunde eine CloudNet Anfrage stellt, muss der Anbieter entweder ein komplexes Einbettungsproblem lösen, um zu entscheiden auf welchem Teil seiner physischen Hardware er die Garantien realisieren möchte, oder die Anfrage ablehnen. Dieses Einbettungsproblem hat in letzter Zeit großes Interesse in der Forschung erfahren, wodurch eine Vielzahl unterschiedlicher Einbettungsverfahren entstanden sind. Einige dieser Verfahren sind jedoch nicht explizit für die Anwendung in der Cloud gestaltet, wodurch sie unterschiedliche für die Cloud typische Anforderungen nicht in vollem Maße umsetzen. Eine Anforderung der Cloud betrifft die Laufzeit: das Einbettungsproblem muss sehr schnell lösbar sein. Aufgrund der Tatsache, dass das Einbettungsproblem NP-schwer ist, vereinfachen viele vorherige Ansätze das Problem, indem sie zusätzliche Einschränkungen einführen. Eine mögliche Einschränkung wäre zu verbieten, dass mehrere Elemente eines CloudNets auf demselben Server untergebracht werden. Diese Einschränkung führt jedoch dazu, dass deutlich mehr Ressourcen für ein CloudNet benötigt werden. Wir präsentieren einen optimalen Vorverarbeitungsschritt, der es beliebigen Algorithmen erlaubt, diese Einschränkung zu umgehen. Eine weitere Möglichkeit ist es, die Topologie des CloudNets einzuschränken, z.B. auf einen sternförmigen Virtual Cluster. Wir zeigen, dass dieses Unterproblem des Einbettungsproblems, im Gegensatz zu bisherigen Annahmen, nicht NP-schwer ist und erläutern wie das Modell erweitert werden kann, um den Speicherort von zu verarbeitenden Daten mit zu berücksichtigen. Eine weitere Anforderung für Einbettungsverfahren ist die Unterstützung von Elastizität. Kunden können zu jeder Zeit weitere Ressourcen hinzumieten oder ihre gemieteten Ressourcen verringern. Da diese Möglichkeit maßgeblich zum Erfolg der Cloud beigetragen hat, sollten CloudNets ebenfalls elastisch sein. Gegenwärtige Einbettungsverfahren unterstützen jedoch nur offline Elastizität: Sie ermöglichen, dass sich die Garantien auf Netzwerkleistung zur Laufzeit ändern, fordern aber, dass der Kunde sämtliche Änderungen, die über die Laufzeit seines CloudNets auftreten, mit der initialen Anfrage bekanntgibt. Dies steht im Widerspruch zu der Art wie die Cloud heutzutage benutzt wird. Um dieses Problem zu beheben, entwerfen wir Kraken, ein System was es Kunden ermöglicht, CloudNets zu jeder Zeit zu verändern. Kraken ist nachweislich optimal und effizient genug, um sowohl Einbettungen als auch Modifikationen von CloudNets innerhalb von 0.1 Sekunden zu berechnen - in Cloudumgebungen mit 16 Tsd. Servern.
URI: http://depositonce.tu-berlin.de/handle/11303/5720
http://dx.doi.org/10.14279/depositonce-5340
Exam Date: 6-Jan-2016
Issue Date: 2016
Date Available: 29-Jun-2016
DDC Class: DDC::000 Informatik, Informationswissenschaft, allgemeine Werke::000 Informatik, Wissen, Systeme::006 Spezielle Computerverfahren
Subject(s): network virtualization
algorithms
resource guarantees
embedding problem
data center
Netzwerkvirtualisierung
Algorithmen
Ressourcengarantieen
Einbettungsproblem
Usage rights: Terms of German Copyright Law
Appears in Collections:Institut für Telekommunikationssysteme » Publications

Files in This Item:
File Description SizeFormat 
fuerst_carlo.pdf2.69 MBAdobe PDFThumbnail
View/Open


Items in DepositOnce are protected by copyright, with all rights reserved, unless otherwise indicated.