Master Thesis MSTR-2018-30

BibliographyFlaig, Albert: Window drop load shedding in complex event processing.
University of Stuttgart, Faculty of Computer Science, Electrical Engineering, and Information Technology, Master Thesis No. 30 (2018).
59 pages, english.

In Complex Event Processing (CEP) huge input event streams are processed to interpret specific situations in real time. In the field of parallel CEP the event stream is split into different windows which can be processed in parallel by several operator instances. This paradigm reduces the load imposed on a single operator instance and allows for horizontal scalability. However, in case of high load, the operator instances may not be able to process the incoming events in time; the unprocessed events are queued up resulting in a higher processing latency. In such situations it can be desirable to impose a latency bound on the system. One way to satisfy the given latency bound, is to do load shedding by dropping incoming windows. This problem is not trivial, as it is unclear when, which and how many windows need to be dropped. To answer these questions we try to find out the most promising windows, e.g. windows which may yield a high amount of complex events, yet impose a low impact on processing time. However, this adds additional challenges, as the processing latency of a window depends on many unknown variables, such as the size of the window, the types of incoming events, the position of these events relative to each other and even on the processing latency of other overlapping windows. Furthermore, even if the quality and processing latency of a window is determined, there are several open questions regarding the timing and frequency of load shedding in order to not violate the latency bound, but still keep enough windows active. In the scope of this thesis, we introduce a latency and quality model to estimate the processing latency a window induces. Based on this model, we propose an algorithm which decides the windows to drop in case of high system load to satisfy a given latency bound while minimizing the loss of quality.

Full text and
other links
Department(s)University of Stuttgart, Institute of Parallel and Distributed Systems, Distributed Systems
Superviser(s)Rothermel, Prof. Kurt; Slo, Ahmad
Entry dateMay 27, 2019
   Publ. Computer Science