TU Darmstadt / ULB / TUprints

InterestCast: Adaptive Event Dissemination for Interactive Real-Time Applications

Lehn, Max (2016)
InterestCast: Adaptive Event Dissemination for Interactive Real-Time Applications.
Technische Universität Darmstadt
Ph.D. Thesis, Primary publication

[img]
Preview
Text
Thesis 2016-04-18 tuprints.pdf - Accepted Version
Copyright Information: CC BY-NC-ND 3.0 Unported - Creative Commons, Attribution, NonCommercial, NoDerivs.

Download (4MB) | Preview
Item Type: Ph.D. Thesis
Type of entry: Primary publication
Title: InterestCast: Adaptive Event Dissemination for Interactive Real-Time Applications
Language: English
Referees: Buchmann, Ph.D. Alejandro ; Nahrstedt, Ph.D. Klara
Date: 2016
Place of Publication: Darmstadt
Date of oral examination: 26 February 2016
Abstract:

Many networked applications use push-based many-to-many communication. Especially real-time applications, such as online games and other virtual reality applications, need to synchronize state between many participants under strict latency requirements. Those applications typically exchange frequent state updates and therefore require an appropriate dissemination mechanism. Centralized and server-based solutions do not minimize latency, since they always need an extra round-trip to the server. In addition, a server infrastructure constitutes a potential performance bottleneck and thus a scalability limitation. Direct communication between event source and destination is often latency-minimal but quickly exceeds the capacities especially of poorly connected participants because each one needs to communicate individually with many others. Our proposed solution, InterestCast, provides a decentralized event dissemination mechanism that uses peer-to-peer event forwarding, allowing powerful participants to help weak participants with the event multiplication and dissemination. To obtain forwarding configurations that best fit the current situation and application needs, InterestCast adapts them dynamically and continuously during runtime. The application’s needs are passed as utility functions, which determine the utility of events with a given latency for a given interest level. Interest levels serve as an abstraction for the importance of events from a specific source, allowing a more fine-grained prioritization than an all-or-nothing subscription model. This is particularly useful if the importance of updates depends on virtual reality distance or another application-specific metric. InterestCast runs an incremental local optimization algorithm that repeatedly evaluates all possible rerouting operations from the point of view of the respective local node. In each iteration, the best operation is chosen based on the application’s utility functions and a system model that predicts the effects of a given operation. As this optimization process is run on each node independently, it scales well with the number of participants. The prediction only uses local knowledge as well as information from the local neighborhood in up to two hops, which is provided by a neighborhood information exchange protocol. Our evaluation shows that the results of InterestCast’s distributed optimization are close to the global optima computed by a integer program solver. Computing the optimum for a given situation globally at runtime, however, is infeasible due to its computational complexity, even with a highly simplified network model. In detailed network simulations, we further demonstrate the superiority of InterestCast over a purely direct event dissemination in online gaming scenarios. In comparison with the direct dissemination, InterestCast significantly reduces the traffic of weak nodes and almost quadruples the possible number of participants for the same average delivery latency of high-interest events.

Alternative Abstract:
Alternative AbstractLanguage

Viele Netzwerkanwendungen verwenden push-orientierte Kommunikation zwischen vielen Anwendern. Insbesondere Echtzeitanwendungen, wie etwa Onlinespiele und andere Virtual-Reality-Anwendungen bedürfen der Synchronisierung des Anwendungszustands zwischen vielen Teilnehmern unter engen Latenz-Voraussetzungen. Solche Anwendungen tauschen typischerweise regelmäßig Zustands-Updates aus und benötigen einen dafür geeigneten Verteilungsmechanismus. Zentralisierte, serverbasierte Lösungen minimieren Latenz insofern nicht, als sie immer einen separaten Round-Trip zum Server benötigen. Hinzu kommt, dass die Serverinfrastruktur einen potentiellen Performance-Engpass darstellt und damit die Skalierbarkeit einschränkt. Direkte Kommunikation zwischen Quelle und Ziel ist meist Latenz-minimal, führt aber schnell zur Überschreitung der Netzwerkkapazität, insbesondere bei schwach angebundenen Teilnehmern. Denn so muss jeder mit vielen anderen Teilnehmern individuell kommunizieren. Die in dieser Arbeit vorgestellte Lösung, InterestCast, bietet einen dezentralen Mechanismus zur Verteilung von Ereignissen, welcher eine Peer-to-Peer-Weiterleitung von Ereignissen verwendet und so starken Teilnehmern erlaubt, schwachen bei der Vervielfältigung und Verbreitung von Ereignis-Meldungen zu helfen. Um die Weiterleitungskonfiguration zu erhalten, die in der momentanen Situation am besten für die jeweiligen Anforderungen der Anwendung geeignet sind, passt InterestCast diese zur Laufzeit kontinuierlich an. Die Anforderungen der Anwendung werden als Nutzenfunktionen spezifiziert, die den Nutzen von Ereignissen mit einer gegebenen Auslieferungsverzögerung bewertet, abhängig vom Interesse am jeweiligen Ereignis. Interessensniveaus dienen als eine Abstraktion für die Wichtigkeit von Ereignissen von einer bestimmten Quelle und erlauben eine Priorisierung der Auslieferung von Ereignis-Benachrichtigungen. Dies ist besonders nützlich wenn die Wichtigkeit von Ereignissen z.B. vom Abstand der Teilnehmer in der virtuellen Realität oder von sonstigen anwendungsspezifischen Metriken abhängt. InterestCast führt einen inkrementellen lokalen Optimierungsalgorithmus aus, der wiederholt alle möglichen Veränderungen der Weiterleitungen aus Sicht des jeweils lokalen Knotens auswertet. In jedem Durchlauf wird anhand der Nutzenfunktionen und einem Systemmodell die Operation ausgewählt, von der die größte Verbesserung des Gesamtzustands erwartet wird. Da dieser Optimierungsprozess auf jedem Knoten unabhängig ausgeführt wird, skaliert er gut mit der Teilnehmerzahl. Die Vorhersage verwendet nur lokales Wissen sowie Informationen aus der Nachbarschaft in bis zu zwei Schritten, welche über ein entsprechendes Austauschprotokoll gewonnen werden. Unsere Auswertungen zeigen, dass die Ergebnisse der verteilten Optimierung von InterestCast nahe an den globalen Optima liegen, welche wir anhand der verwendeten Modelle mit Hilfe eines Solvers für Integer-Programme ermitteln. Die Lösung des globalen Optimums zur Laufzeit ist jedoch unpraktikabel, da die Komplexität des Problems selbst mit einem stark vereinfachten Netzwerkmodell zu äußerst langen Berechnungszeiten führt. In detaillierten Netzwerksimulationen zeigen wir außerdem die Überlegenheit von InterestCast über eine rein direkte Verteilung der Ereignisse in Online-Spiel-Szenarien. Im Vergleich mit der direkten Verteilung reduziert Inter- estCast die nötige Datenmenge bei schwachen Knoten erheblich und vervierfacht beinahe die mögliche Teilnehmerzahl bei gleichbleibender durchschnittlicher Auslieferungszeit von Ereignissen von hohem Interesse.

German
URN: urn:nbn:de:tuda-tuprints-53982
Classification DDC: 000 Generalities, computers, information > 004 Computer science
Divisions: 20 Department of Computer Science
20 Department of Computer Science > Databases and Distributed Systems
Date Deposited: 02 May 2016 07:45
Last Modified: 09 Jul 2020 01:16
URI: https://tuprints.ulb.tu-darmstadt.de/id/eprint/5398
PPN: 386821283
Export:
Actions (login required)
View Item View Item