TY - GEN
T1 - Scaling topology pattern matching
T2 - 33rd Annual ACM Symposium on Applied Computing, SAC 2018
AU - Stein, Michael
AU - Frömmgen, Alexander
AU - Kluge, Roland
AU - Wang, Lin
AU - Wilberg, Augustin
AU - Koldehofe, Boris
AU - Mühlhäuser, Max
PY - 2018/4/9
Y1 - 2018/4/9
N2 - 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 decision-making 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.
AB - 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 decision-making 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.
KW - Graph pattern matching
KW - Locality control
KW - Topology control
UR - http://www.scopus.com/inward/record.url?scp=85050519119&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85050519119&partnerID=8YFLogxK
U2 - 10.1145/3167132.3167241
DO - 10.1145/3167132.3167241
M3 - Conference contribution
AN - SCOPUS:85050519119
T3 - Proceedings of the ACM Symposium on Applied Computing
SP - 996
EP - 1005
BT - Proceedings of the 33rd Annual ACM Symposium on Applied Computing, SAC 2018
PB - Association for Computing Machinery
Y2 - 9 April 2018 through 13 April 2018
ER -