TU Darmstadt / ULB / TUbiblio

Scaling Topology Pattern Matching: A Distributed Approach

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

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.

Item Type: Conference or Workshop Item
Erschienen: 2018
Creators: Stein, Michael and Frömmgen, Alexander and Kluge, Roland and Wang, Lin and Wilberg, Augustin and Koldehofe, Boris and Mühlhäuser, Max
Title: Scaling Topology Pattern Matching: A Distributed Approach
Language: English
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.

Divisions: 18 Department of Electrical Engineering and Information Technology > Institute of Computer Engineering > Real-Time Systems
18 Department of Electrical Engineering and Information Technology > Institute of Computer Engineering > Multimedia Communications
Department of Computer Science > Telecooperation
DFG-Collaborative Research Centres (incl. Transregio) > Collaborative Research Centres > CRC 1053: MAKI – Multi-Mechanisms Adaptation for the Future Internet
DFG-Collaborative Research Centres (incl. Transregio) > Collaborative Research Centres > CRC 1053: MAKI – Multi-Mechanisms Adaptation for the Future Internet > A: Construction Methodology > Subproject A1: Modelling
DFG-Collaborative Research Centres (incl. Transregio) > Collaborative Research Centres > CRC 1053: MAKI – Multi-Mechanisms Adaptation for the Future Internet > C: Communication Mechanisms > Subproject C2: Information-centred perspective
18 Department of Electrical Engineering and Information Technology > Institute of Computer Engineering
DFG-Collaborative Research Centres (incl. Transregio) > Collaborative Research Centres
DFG-Collaborative Research Centres (incl. Transregio) > Collaborative Research Centres > CRC 1053: MAKI – Multi-Mechanisms Adaptation for the Future Internet > A: Construction Methodology
DFG-Collaborative Research Centres (incl. Transregio) > Collaborative Research Centres > CRC 1053: MAKI – Multi-Mechanisms Adaptation for the Future Internet > C: Communication Mechanisms
18 Department of Electrical Engineering and Information Technology
Department of Computer Science
DFG-Collaborative Research Centres (incl. Transregio)
Event Title: In Proceedings of the ACM/SIGAPP Symposium on Applied Computing (SAC)
Date Deposited: 22 Jan 2018 11:53
Export:

Optionen (nur für Redakteure)

View Item View Item