Details

Autor(en) / Beteiligte

• Knollmann, Till
• Meyer auf der Heide, Friedhelm[Akademischer Betreuer]
• Disser, Yann[Akademischer Betreuer]
• Scheideler, Christian[Akademischer Betreuer]

Titel

Online algorithms for allocating heterogeneous resources

Ort / Verlag

Paderborn

Erscheinungsjahr

2023

Link zum Volltext

• Hochschulschriften Visual Library - Scan2Web Hochschulschriften UB Paderborn (s2w-hsspadubpb)
• Hochschulschriften Visual Library - Scan2Web Hochschulschriften UB Paderborn (s2w-hsspadubpb)

Link zu anderen Inhalten

• Volltext
• Volltext

Verknüpfte Titel

Beschreibungen/Notizen

• Tag der Verteidigung: 30.05.2023
• Open Access
• ger: Mit der weltweiten Verbreitung des Cloud Computing sind Cloud-Anbieter täglich mit Fragen konfrontiert wie z.B., wo die virtuellen Server eines Kunden platziert werden sollen und welche Dienste an einem bestimmten Standort angeboten werden sollen. Dienste sollten sich in der Nähe der Kundenanfragen befinden, damit die Netzbelastung gering ist und eine zufriedenstellende Benutzererfahrung geboten wird. Gleichzeitig ist die Änderung der Standorte von Diensten mit Kosten für die Migration/Einrichtung virtueller Maschinen verbunden. Darüber hinaus sind künftige Anfragen von Kunden in der Regel unbekannt, so dass Algorithmen zur kosteneffizienten und dynamischen Verwaltung von Diensten erforderlich sind. Das obige Szenario wurde in der theoretischen Informatik unter dem Begriff Ressourcenallokation ausgiebig erforscht. Die klassischen Modelle betrachten jedoch nur eine Art von Dienst, während die Realität heterogen ist, d.h. Cloud-Anbieter verwalten mehrere, unterschiedliche Dienste. Daher wird in der folgenden Arbeit der Einfluss heterogener Ressourcen auf die Leistung von Online-Algorithmen für Ressourcenallokationsprobleme untersucht, indem wir Güter zum Modellieren von Diensten einführen. Wir betrachten drei fundamentale klassische Modelle - das Page Migration Problem, das Facility Location Problem und das k-Server Problem. In jedem Modell erlauben wir den Ressourcen das Anbieten verschiedener Güter, präsentieren untere Schranken für die Kompetitivität und entwickeln und analysieren Algorithmen.
• eng: With the rise of cloud computing worldwide, cloud providers are confronted with questions such as "Where to place virtual servers of a client?" and "Which services to provide at a location?" every day. Services should be close to clients requests for a low network load and a satisfying experience for the clients. Simultaneously, changing the locations of services implies costs for migrating and deploying virtual machines. Further, future requests of clients are usually unknown, which requires algorithms to manage services cost-efficiently and dynamically. The above scenario has extensively been researched in theoretical computer science under the term resource allocation. However, classical models consider only one kind of service, while the reality is heterogeneous, i.e., cloud providers manage multiple different services. Therefore, the following thesis studies the influence of heterogeneous resources on the performance of online algorithms for resource allocation problems by introducing commodities modeling services. We consider three fundamental classical models - the page migration problem, the facility location problem, and the k-server problem. In each model, we allow resources to offer different commodities, present lower bounds on the competitive ratio, and design and analyze algorithms.