Latency-aware stream operator placement optimization in fog computing environments

Abstract

Das Internet der Dinge (Internet of Things, IoT) wird immer beliebter und damit steigt auch die Anzahl der beteiligten Geräte und der zu verarbeitenden Daten schnell an. Die verteilte Datenstromverarbeitung ist ein Software-Engineering-Muster zum Bau von Anwendungen als Topologien von Operatoren und wird häufig zur Verarbeitung von IoT-Daten verwendet. Fog Computing ist ein neues Paradigma zur Bewältigung dieser Datenmengen und soll niedrigere Latenzzeiten bieten, indem die Berechnungen auf Fog-Ressourcen, die näher an den IoT-Geräten oder Nutzern sind, durchgeführt werden. Das erfordert Verbesserungen bei der Verteilung von Operatoren auf Rechenressourcen. Von Fog-Ressourcen wird erwartet, dass sie im Vergleich zum Cloud Computing über vielfältigere Eigenschaften und Fähigkeiten verfügen und geographisch verteilt sein. Diese Arbeit zielt darauf ab, die Platzierung von Operatoren in Fog- und Cloud-Computing-Umgebungen zu verbessern. Ein eingeschränktes Optimierungsproblem wird definiert und heuristisch mit drei Ansätzen gelöst: Dem Bergsteigeralgorithmus, einem Ameisensystem und einer Hybridlösung. Die Platzierungen werden dabei auch regelmässig zur Laufzeit erneut optimiert. Die Heuristiken sind in Apache Storm integriert und werden in einem emulierten Netzwerk mit zufällig generierten Topologien getestet. Sie werden mit zwei statischen Lösungen verglichen: Apache Storms Standard-Planer und R-Storm. Die beste Heuristik übertraf den Standard-Planer wesentlich im Durchsatz und den Latenzzeiten. Im Vergleich mit R-Storm konnte durch die zuverlässigere Platzierung der durchschnittliche Durchsatz um 11% erhöht werden und die minimale Latenz um 36% reduziert werden. Außerdem hat die Lösung den Vorteil, dass sie dynamisch Anpassungen der Platzierung an unterschiedliche Lasten und Veränderungen in der Umgebung durchführen kann.

The Internet of Things (IoT) is growing in popularity, and as such, the number of devices involved and the amount of data to be processed are rising quickly. Distributed stream processing is a software engineering pattern to build applications as topologies of operators and is often used to process IoT data. Fog computing is a new paradigm intended to handle the increasing data loads and offer lower latencies by moving computations onto fog resources closer to IoT devices or users. This necessitates improvements to the distribution of operators to computational resources. Fog resources are expected to have more varied capabilities when compared to cloud computing and to be geographically distributed. This thesis aims to improve the placement of operators in fog and cloud computing environments. A constrained optimisation problem is defined and heuristically solved with three approaches: Hill-climbing, an ant system and a hybrid solution. The placements are also periodically re-optimised at runtime. The heuristics are integrated into Apache Storm and benchmarked in an emulated network with randomly generated topologies. They are compared against two static solutions: Apache Storm’s default scheduler and the Resource Aware Scheduler. The best heuristic outperformed the default scheduler significantly in throughput and latency. In comparison to the Resource Aware Scheduler, average throughput was increased by 11% because of the more reliable placement performance and the minimum latency was reduced by 36%. Additionally, the presented solution has the advantage of dynamically adjusting placements to different loads and changes in the environment.