Stein, Michael ; Frömmgen, Alexander ; Kluge, Roland ; Wang, Lin ; Wilberg, Augustin ; Koldehofe, Boris ; Mühlhäuser, Max (2018)
Scaling Topology Pattern Matching: A Distributed Approach.
In Proceedings of the ACM/SIGAPP Symposium on Applied Computing (SAC).
Konferenzveröffentlichung, Bibliographie
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: | Konferenzveröffentlichung |
---|---|
Erschienen: | 2018 |
Autor(en): | Stein, Michael ; Frömmgen, Alexander ; Kluge, Roland ; Wang, Lin ; Wilberg, Augustin ; Koldehofe, Boris ; Mühlhäuser, Max |
Art des Eintrags: | Bibliographie |
Titel: | Scaling Topology Pattern Matching: A Distributed Approach |
Sprache: | Englisch |
Publikationsjahr: | 2018 |
Veranstaltungstitel: | In Proceedings of the ACM/SIGAPP Symposium on Applied Computing (SAC) |
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 18 Fachbereich Elektrotechnik und Informationstechnik > Institut für Datentechnik > Echtzeitsysteme 18 Fachbereich Elektrotechnik und Informationstechnik > Institut für Datentechnik 18 Fachbereich Elektrotechnik und Informationstechnik > Institut für Datentechnik > Multimedia Kommunikation 20 Fachbereich Informatik 20 Fachbereich Informatik > Telekooperation DFG-Sonderforschungsbereiche (inkl. Transregio) DFG-Sonderforschungsbereiche (inkl. Transregio) > Sonderforschungsbereiche 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 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 DFG-Sonderforschungsbereiche (inkl. Transregio) > Sonderforschungsbereiche > SFB 1053: MAKI – Multi-Mechanismen-Adaption für das künftige Internet > C: Kommunikationsmechanismen > Teilprojekt C2: Informationszentrische Sicht |
Hinterlegungsdatum: | 22 Jan 2018 11:53 |
Letzte Änderung: | 14 Jun 2021 06:14 |
PPN: | |
Export: | |
Suche nach Titel in: | TUfind oder in Google |
Frage zum Eintrag |
Optionen (nur für Redakteure)
Redaktionelle Details anzeigen |