Grundidee des Ansatzes ist, dass die Recheneinheiten selbst die Verteilung der Anwendungskomponenten untereinander aushandeln. Dazu wird der neue Algorithmus des Forschungsteams parallel auf allen Edge-Knoten des Netzwerks ausgeführt. In regelmäßigen Abständen starten die einzelnen Knoten eine Auktion für die auf ihnen gehostete Software-Komponente und laden benachbarte Knoten zur Teilnahme an der Auktion ein. Diese geben Gebote darüber ab, wie stark sich die Latenzzeit verbessern würde, wenn die Software-Komponente bei ihnen ausgeführt würde. Ist eine Verbesserung möglich, wird die versteigerte Komponente zum Knoten mit dem besten Gebot, also der größtmöglichen Verbesserung, migriert.

Der dezentrale Ansatz hat im Vergleich zu einer zentralen Lösung mehrere Vorteile. So lässt sich die Lösung gut auf die Größe des Netzwerks skalieren. Zudem besteht nicht die Gefahr eines Single-Point-of-Failure (SPOF), da die Entscheidungen über die Positionierung von mehreren Knoten getroffen wird. Empirische Untersuchungen zeigen, dass der entwickelte Algorithmus bei der Optimierung der Platzierung im Edge-Netzwerk sehr effektiv ist - sowohl bei einer initialen Platzierung der Komponenten als auch dynamisch im laufenden Betrieb.

Das Forschungsteam hat den Ansatz im „Journal of Parallel and Distributed Computing“ veröffentlicht. Er ist frei zugänglich.

Sven Smolka, Leon Wißenberg and Zoltán Ádám Mann: EdgeDecAp: An auction-based decentralized algorithm for optimizing application placement in edge computing.Journal of Parallel and Distributed Computing, 2023 [DOI].

Abstract

In edge computing, application components can be placed over a range of computational devices from cloud data centers to nodes at the network edge. Application placement can have significant impact on important metrics like latency and resource utilization. Thus, application placement is an important optimization problem. In edge computing, the characteristics of both the infrastructure and the application may change over time, which may require the dynamic re-optimization of the application placement. Most algorithms suggested so far for the dynamic re-optimization of edge application placement are centralized, i.e., they rely on one entity collecting information from the whole infrastructure and making decisions centrally. However, centralized approaches suffer from limited scalability and are vulnerable to failures.

In this paper, we present a decentralized approach for the dynamic re-optimization of edge application placement. We adopt an algorithm of Malek et al. for distributed systems and modify it to make it applicable to edge computing. In this approach, each node makes decisions autonomously, using auctions for coordination. Our empirical results demonstrate that the proposed algorithm is very effective in optimizing edge application placement. In an edge system with 637 edge nodes and 563 end devices, our algorithm achieves 54% higher reduction of application latency than a previous decentralized algorithm.

Keywords

Edge computing, Fog computing, Application placement, Decentralized algorithm, Auction