Article in Proceedings INPROC-2011-43

BibliographySchilling, Björn; Koldehofe, Boris; Rothermel, Kurt: Efficient and Distributed Rule Placement in Heavy Constraint-Driven Event Systems.
In: Proceedings of the 13th IEEE International Conference on High Performance Computing and Communications (HPCC-2011).
University of Stuttgart, Faculty of Computer Science, Electrical Engineering, and Information Technology.
pp. 355-364, english.
IEEE, September 2011.
DOI: 10.1109/HPCC.2011.53.
Article in Proceedings (Conference Paper).
CR-SchemaC.2.4 (Distributed Systems)

Complex Event Processing (CEP) is of increasing importance in many industrial applications to integrate a huge number of events in a scalable manner. A core challenge towards scalable CEP is to efficiently distribute the rules which define how correlations between events can be detected within an event processing network. Furthermore, migration of rules is essential to adapt to changing conditions. While recently significant effort has been spent on optimizing CEP with respect to dedicated optimization goals, such as minimizing latency and bandwidth usage, there remains a fundamental gap in supporting requirements that emerge from deploying CEP over heterogeneous and independent processing environments. Heterogeneity typically imposes many constraints on the placement of rules, which increases the complexity of the underlying optimization problem and cannot be handled efficiently by existing solutions.

In this paper we examine the distributed placement, migration and optimization of rules in the context of the constraint optimization problem to minimize network usage. We propose and evaluate a placement algorithm that efficiently finds valid solutions in scenarios where the solution space is heavily restricted by constraints. The algorithm operates in a decentralized way and is adaptive to dynamic changes of processing nodes, rules, and load characteristics of the event processing network. The optimization algorithm adopts techniques from simulated annealing to avoid local minima. Furthermore, the proposed rule migration policies resolve invalid placements quickly and therefore ensure high availability. The evaluations show that the proposed algorithm is able to efficiently find near optimum solutions within heavy constraint-driven network conditions.

Full text and
other links
PDF (1272428 Bytes)
The original publication is available at IEEE Xplore
CopyrightThis material is posted here with permission of the IEEE. Such permission of the IEEE does not in any way imply IEEE endorsement of any products or services. Internal or personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution must be obtained from the IEEE (contact By choosing to view this document, you agree to all provisions of the copyright laws protecting it.
Department(s)University of Stuttgart, Institute of Parallel and Distributed Systems, Distributed Systems
Entry dateJune 28, 2011
   Publ. Department   Publ. Institute   Publ. Computer Science