TU Darmstadt / ULB / TUbiblio

Scaling Topology Pattern Matching: A Distributed Approach

Stein, Michael ; Frömmgen, Alexander ; Kluge, Roland ; Wang, Lin ; Wilberg, Augustin ; Koldehofe, Boris ; Mühlhäuser, Max :
Scaling Topology Pattern Matching: A Distributed Approach.
In: In Proceedings of the ACM/SIGAPP Symposium on Applied Computing (SAC).
[Konferenz- oder Workshop-Beitrag], (2018)

Kurzbeschreibung (Abstract)

Graph pattern matching in network topologies is a building block of many distributed algorithms. Based on a limited local view of the topology, pattern-based algorithms substantiate the decisionmaking of each device on the occurrence of graph patterns in its surrounding topology. Existing pattern-based algorithms require that each device has a sufficiently large local view to match patterns without support of other devices. In practical environments, the local view is often restricted to one hop. Thus, algorithms matching non-trivial patterns are locked out from such environments today. This paper presents the first algorithm for distributed topology pattern matching, enabling pattern matching beyond the local view. Outgoing from initiating devices, our pattern matcher delegates the matching procedure to further devices in the network. Exploring major contextual parameters of our algorithm, we show that the optimal local view size depends on scenario-specific conditions. Our pattern matcher provides the flexibility for adaptations of the local view size at runtime. Making use of this flexibility, we optimize the execution of an established pattern-based algorithm and evaluate our pattern matcher in two topology control case studies for the Internet of Things. By scaling the view size of each device in a distributed way, our adaptive approach achieves significant communication cost savings in face of dynamic conditions.

Typ des Eintrags: Konferenz- oder Workshop-Beitrag (Keine Angabe)
Erschienen: 2018
Autor(en): Stein, Michael ; Frömmgen, Alexander ; Kluge, Roland ; Wang, Lin ; Wilberg, Augustin ; Koldehofe, Boris ; Mühlhäuser, Max
Titel: Scaling Topology Pattern Matching: A Distributed Approach
Sprache: Englisch
Kurzbeschreibung (Abstract):

Graph pattern matching in network topologies is a building block of many distributed algorithms. Based on a limited local view of the topology, pattern-based algorithms substantiate the decisionmaking of each device on the occurrence of graph patterns in its surrounding topology. Existing pattern-based algorithms require that each device has a sufficiently large local view to match patterns without support of other devices. In practical environments, the local view is often restricted to one hop. Thus, algorithms matching non-trivial patterns are locked out from such environments today. This paper presents the first algorithm for distributed topology pattern matching, enabling pattern matching beyond the local view. Outgoing from initiating devices, our pattern matcher delegates the matching procedure to further devices in the network. Exploring major contextual parameters of our algorithm, we show that the optimal local view size depends on scenario-specific conditions. Our pattern matcher provides the flexibility for adaptations of the local view size at runtime. Making use of this flexibility, we optimize the execution of an established pattern-based algorithm and evaluate our pattern matcher in two topology control case studies for the Internet of Things. By scaling the view size of each device in a distributed way, our adaptive approach achieves significant communication cost savings in face of dynamic conditions.

Fachbereich(e)/-gebiet(e): 18 Fachbereich Elektrotechnik und Informationstechnik > Institut für Datentechnik > Echtzeitsysteme
18 Fachbereich Elektrotechnik und Informationstechnik > Institut für Datentechnik > Multimedia Kommunikation
20 Fachbereich Informatik > Telekooperation
DFG-Sonderforschungsbereiche (inkl. Transregio) > Sonderforschungsbereiche > SFB 1053: MAKI – Multi-Mechanismen-Adaption für das künftige Internet
DFG-Sonderforschungsbereiche (inkl. Transregio) > Sonderforschungsbereiche > SFB 1053: MAKI – Multi-Mechanismen-Adaption für das künftige Internet > A: Konstruktionsmethodik > Teilprojekt A1: Modellierung
DFG-Sonderforschungsbereiche (inkl. Transregio) > Sonderforschungsbereiche > SFB 1053: MAKI – Multi-Mechanismen-Adaption für das künftige Internet > C: Kommunikationsmechanismen > Teilprojekt C2: Informationszentrische Sicht
18 Fachbereich Elektrotechnik und Informationstechnik > Institut für Datentechnik
DFG-Sonderforschungsbereiche (inkl. Transregio) > Sonderforschungsbereiche
DFG-Sonderforschungsbereiche (inkl. Transregio) > Sonderforschungsbereiche > SFB 1053: MAKI – Multi-Mechanismen-Adaption für das künftige Internet > A: Konstruktionsmethodik
DFG-Sonderforschungsbereiche (inkl. Transregio) > Sonderforschungsbereiche > SFB 1053: MAKI – Multi-Mechanismen-Adaption für das künftige Internet > C: Kommunikationsmechanismen
18 Fachbereich Elektrotechnik und Informationstechnik
20 Fachbereich Informatik
DFG-Sonderforschungsbereiche (inkl. Transregio)
Veranstaltungstitel: In Proceedings of the ACM/SIGAPP Symposium on Applied Computing (SAC)
Hinterlegungsdatum: 22 Jan 2018 11:53
Export:

Optionen (nur für Redakteure)

Eintrag anzeigen Eintrag anzeigen