Deterministic real-time communication with bounded delay is an essential requirement for many safety-critical cyber–physical systems, and has received much attention from major standardization bodies such as IEEE and IETF. In particular, Ethernet technology has been extended by time-triggered scheduling mechanisms in standards like TTEthernet and Time-Sensitive Networking. Although the scheduling mechanisms have become part of standards, the traffic planning algorithms to create time-triggered schedules are still an open and challenging research question due to the high complexity of the problem. In particular, so-called plug-and-produce scenarios require the ability to extend schedules on the fly within seconds. The need for scalable scheduling and routing algorithms is further supported by large-scale distributed real-time systems like smart energy grids with tight communication requirements. In this paper, we tackle this challenge by proposing two novel algorithms called Hierarchical Heuristic Scheduling (H2S) and Cost-Effective Lazy Forwarding Scheduling (CELF) to create time-triggered schedules for TTEthernet. H2S and CELF are highly efficient and scalable, computing schedules for more than 45,000 streams on random networks with 1000 bridges as well as a realistic energy grid network within seconds or even sub-seconds.

Overload situations, in the presence of resource limitations, in complex event processing (CEP) systems are typically handled using load shedding to maintain a given latency bound. However, load shedding might negatively impact the quality of results (QoR). To minimize the shedding impact on QoR, CEP researchers propose shedding approaches that drop events/internal state with the lowest importances/utilities. In both black-box and white-box shedding approaches, different features are used to predict these utilities. In this work, we propose a novel black-box shedding approach that uses a new set of features to drop events from the input event stream to maintain a given latency bound. Our approach uses a probabilistic model to predict these event utilities. Moreover, our approach uses Zobrist hashing and well-known machine learning models, e.g., decision trees and random forests, to handle the predicted event utilities. Through extensive evaluations on a real-world and several synthetic datasets and a representative set of CEP queries, we show that, in the majority of cases, our load shedding approach outperforms state-of-the-art black-box load shedding approaches, w.r.t. QoR.

In complex event processing (CEP), load shedding is performed to maintain a given latency bound during overload situations when there is a limitation on resources. However, shedding load implies degradation in the quality of results (QoR). Therefore, it is crucial to perform load shedding in a way that has the lowest impact on QoR. Researchers, in the CEP domain, propose to drop either events or partial matches (PMs) in overload cases. They assign utilities to events or PMs by considering either the importance of events or the importance of PMs but not both together. In this article, we combine these approaches where we propose to assign a utility to an event by considering both the event importance and the importance of PMs. We propose two load shedding approaches for CEP systems. The first approach drops events from PMs, while the second approach drops events from windows. We adopt a probabilistic model that uses the type and position of an event in a window and the state of a PM to assign a utility to an event. We, also, propose an approach to predict a utility threshold that is used to drop the required amount of events to maintain a given latency bound. By extensive evaluations on two real-world datasets and several representative queries, we show that, in the majority of cases, our load shedding approach outperforms state-of-the-art load shedding approaches, w.r.t. QoR.

Many networked applications, e.g., in the domain of cyber-physical systems, require strict service guarantees for time-triggered traffic flows, usually in the form of jitter and latency bounds. It is a notoriously hard problem to compute a network-wide traffic plan, i.e., a set of routes and transmission schedules, that satisfies these requirements, and dynamic changes in the flow set add even more challenges. Existing traffic-planning methods are ill-suited for dynamic scenarios because they either suffer from high computational cost, can result in low network utilization, or provide no explicit guarantees when transitioning to a new traffic plan that incorporates new flows. Therefore, we present a novel approach for dynamic traffic planning of time-triggered flows. Our conflict-graph-based modeling of the traffic planning problem allows for the reconfiguration of active flows to increase the network utilization, while also providing per-flow QoS guarantees during the transition to the new traffic plan. Additionally, we introduce a novel heuristic for computing the new traffic plans. Evaluations of our prototypical implementation show that we can efficiently compute new traffic plans in scenarios with hundreds of active flows for a wide range of settings.

Low-latency stream processing applications (SPA) distribute the event streams on parallel instances of the application’s operators to avoid queuing. Each operator has a set of processing nodes for its instances. Edge and fog infrastructures promise, among other things, low communication latency and are thus of interest for low-latency SPAs. Yet, they include heterogeneous, even volatile nodes which makes the parallel processing of SPAs challengingAvailable solutions for parallel SPAs often assume homogeneity and stable infrastructures.Thus, we aim to balance the stream processing among heterogeneous, instable infrastructures using a decentralized control mechanism. We propose a decentralized, dynamic, and lightweight approach to re-balance SPA-load according to the nodes current performance, while minimizing latencies. In doing so, we introduce the Coda-EFC framework for window-based stream processing on heterogeneous distributed infrastructures. It dynamically adapts its load balancing to node performance without computing quickly outdated schedules and aims for latency-optimal load balancing. We introduce two adaptive load balancing strategiesone tailored for heterogeneous, dynamic infrastructures, the other an adaptation of a state-of-the art approach.

Many applications require the processing of event streams from different sources in combination with large amounts of background knowledge. Semantic CEP is a paradigm designed specifically for that. It extends complex event processing (CEP) with RDF support and uses a network of operators to process RDF streams in combination with RDF knowledge bases. Another popular class of systems designed for a similar purpose are the RDF stream processors (RSPs). These are systems that extend SPARQL (the RDF query language) with stream processing capabilities. Semantic CEP and RSPs have similar purposes but focus on different things. The former focuses on scalability and distributed processing while the latter tend to focus on the intricacies of RDF stream processing per se. In this paper we propose the use of RSP engines as building blocks for Semantic CEP. We present an infrastructure, called DSCEP, that allows the encapsulation of existing RSP engines into CEP-like operators so that these can be seamlessly interconnected in a distributed, decentralized operator network. DSCEP handles the hurdles of such interconnection, such as reliable communication, stream aggregation and slicing, event identification and time-stamping, etc., allowing users to concentrate on the queries. We also discuss in the paper how DSCEP can be used to speedup monolithic SPARQL queries by splitting them into parallel subqueries operating over restricted parts of the knowledge base.

Publish/subscribe systems have to react fast on changes in their environment while handling many events with low end-to-end latency and high throughput. Moving the broker functionality of publish/subscribe systems to the underlying network layer reduces the path length of events and, in addition, forwarding benefits from powerful and programmable hardware. So far attempts of underlay publish/subscribe depend on a specific API of the network devices, e. g., the OpenFlow protocol, which have restrictions in dealing with dynamic devices and corresponding changes in the introduced attribute names for matching and filtering events.In this work, we focus on the next generation of network devices, which are envisioned to provide reconfigurable hardware components, specified by the open P4 description language. We introduce two new approaches that enable a flexible and generic attribute/value encoding, understandable by P4-capable packet processors, to benefit from the performance properties of hardware. Furthermore, the proposed approaches reduce the effort in encoding and decoding event messages.

Complex event processing (CEP) systems continuously process input event streams to detect patterns. Over time, the input event rate might fluctuate and overshoot the system's capabilities. One way to reduce the overload on the system is to use load shedding. In this paper, we propose a load shedding strategy for CEP systems which drops a portion of the CEP operator's internal state (a.k.a. partial matches) to maintain a given latency bound. The crucial question here is how many and which partial matches to drop so that a given latency bound is maintained while minimizing the degradation in the quality of results. In the stream processing domain, different load shedding strategies have been proposed that mainly depend on the importance of individual tuples. However, as CEP systems perform pattern detection, the importance of events is also influenced by other events in the stream. Our load shedding strategy uses Markov chain and Markov reward process to predict the utility/importance of partial matches to determine the ones to be dropped. In addition, we represent the utility in a way that minimizes the overhead of load shedding. Furthermore, we provide algorithms to decide when to start dropping partial matches and how many partial matches to drop. By extensively evaluating our approach on three real-world datasets and several representative queries, we show that the adverse impact of our load shedding strategy on the quality of results is considerably less than the impact of state-of-the-art load shedding strategies.

Control mechanisms of stream processing applications (SPAs) that ensure latency bounds at minimal runtime cost mostly target a specific infrastructure, e.g., homogeneous nodes. With the growing popularity of the Internet of Things, fog, and edge computing, SPAs are more often distributed on heterogeneous infrastructures, triggering the need for a holistic SPA-control that still considers heterogeneity. We therefore combine individual control mechanisms via the latency-distribution problem that seeks to distribute latency budgets to individually managed components of distributed SPAs for a lightweight yet effective end-to-end control. To this end, we introduce a hierarchical control architecture, give a formal definition of the latency-distribution problem, and provide both an ILP formulation to find an optimal solution as well as a heuristic approach, thereby enabling the combination of individual control mechanisms into one SPA while ensuring global cost minimality. Our evaluations show that both solutions are effective---while the heuristic approach is only slightly more costly than the optimal ILP solution, it significantly reduces runtime and communication overhead.

Complex event processing systems process the input event streams on-the-fly. Since input event rate could overshoot the system's capabilities and results in violating a defined latency bound, load shedding is used to drop a portion of the input event streams. The crucial question here is how many and which events to drop so the defined latency bound is maintained and the degradation in the quality of results is minimized. In stream processing domain, different load shedding strategies have been proposed but they mainly depend on the importance of individual tuples (events). However, as complex event processing systems perform pattern detection, the importance of events is also influenced by other events in the same pattern. In this paper, we propose a load shedding framework called eSPICE for complex event processing systems. eSPICE depends on building a probabilistic model that learns about the importance of events in a window. The position of an event in a window and its type are used as features to build the model. Further, we provide algorithms to decide when to start dropping events and how many events to drop. Moreover, we extensively evaluate the performance of eSPICE on two real-world datasets.

We propose two extensions for a state-of-the-art method of rollback-recovery in distributed CEP (complex event processing). In CEP, an operator network is used to search for patterns in events streams. Sometimes these operators fail and lose their state. Rollback-recovery is a method for dealing with such state losses. The type of rollback-recovery we consider is upstream backup, where the state of a failed operator is recovered by replaying to it the input events that led it to that state. These events are kept in upstream operators' memory buffers, which are trimmed continuously as the downstream operator progresses. The first extension we propose saves memory and speeds up recovery by avoiding to store and retransmit unnecessary events. The second extension makes the base method of upstream backup compatible with data-parallel CEP, allowing that the windows into which operators partition their input be processed in parallel. We evaluated the proposed extensions through experiments that showed a significant reduction in memory usage and recovery time at the expense of a negligible processing overhead during normal operation.

Many important real-world applications-such as social networks or distributed data bases-can be modeled as hypergraphs. In such a model, vertices represent entities-such as users or data records-whereas hyperedges model a group membership of the vertices-such as the authorship in a specific topic or the membership of a data record in a specific replicated shard. To optimize such applications, we need an efficient and effective solution to the NP-hard balanced k-way hypergraph partitioning problem. However, existing hypergraph partitioners that scale to very large graphs do not effectively exploit the hy-pergraph structure when performing the partitioning decisions. We propose HYPE, a hypergraph partitionier that exploits the neighborhood relations between vertices in the hypergraph using an efficient implementation of neighborhood expansion. HYPE improves partitioning quality by up to 95% and reduces runtime by up to 39% compared to streaming partitioning.

With the vision of Internet of Things gaining popularity at a global level, efficient publish/subscribe middleware for communication within and across data centers is extremely desirable. In this respect, the very popular Software-Defined Networking, which enables publish/subscribe middleware to perform line-rate filtering of events directly on hardware, can prove to be very useful. While deploying content filters directly on switches of a software-defined network allows optimized paths, high throughput rates, and low end-to-end latency, it suffers from certain inherent limitations with respect to number of bits available on hardware switches to represent these filters. Such a limitation affects expressiveness of filters, resulting in unnecessary traffic in the network. In this paper, we explore various complementary techniques to represent content filters expressively while being limited by hardware. We implement and evaluate techniques that i) use workload, in terms of events and subscriptions, to represent content, and ii) efficiently select attributes to reduce redundancy in content. Our detailed performance evaluations show the potential of these techniques in reducing unnecessary traffic when subjected to different workloads. Furthermore, the techniques proposed in this paper require significant updates to the network, i.e., the data plane, which must be performed in a consistent manner to ensure desired system behavior. As a result, in this paper, we, also, design and evaluate a light-weight approach that ensures data plane consistency in the presence of dynamic network updates.

With the increasing popularity of software-defined networking (SDN), ternary content-addressable memory of switches can be directly accessed by a publish/subscribe middleware to perform filtering operations at low latency. In this way, three important requirements for a publish/subscribe middleware can be fulfilled, namely, bandwidth efficiency, line-rate performance, and low latency in forwarding messages between producers and consumers. Nevertheless, it is challenging to sustain line-rate performance in the presence of dynamically changing interests of producers and consumers. In this paper, we realize a scalable, SDN-based publish/subscribe middleware, called PLEROMA, that performs efficient forwarding at line-rate. Moreover, PLEROMA offers methods to efficiently reconfigure a deployed topology in the presence of dynamic subscriptions and advertisements. We evaluate the performance of both the data plane and the control plane of PLEROMA to support our claim. Furthermore, we evaluate and benchmark the performances of SDN-compliant hardware and software switches in the context of our middleware.

Over the past few decades, content-based publish/subscribe has been primarily implemented as an overlay network of software brokers. Even though such systems provide the possibility of bandwidth efficient expressive filtering in software, they cannot match up to the performance (in terms of end-to-end latency and throughput) of communication protocols implemented on the network layer. To exploit network layer performance benefits, recently, content-based publish/subscribe was realized using the capabilities of Software-defined Networking (SDN). While SDN allows line-rate forwarding of events by content filters directly installed on switches, it suffers from inherent hardware limitations (w.r.t. flow table size, limited availability of bits in header fields) that adversely impact expressiveness of these filters, resulting in unnecessary network traffic. In this paper, we strike a balance between purely application-layer-based and purely network-layer-based publish/subscribe implementations by realizing the first hybrid content-based middleware that enables filtering of events in both layers. Moreover, we provide different selection algorithms with varying degrees of complexity to determine the events to be filtered at each layer such that unnecessary network traffic can be minimized while also considering delay requirements of the middleware. Our hybrid middleware offers full flexibility to configure it according to the performance requirements of the system. We provide a detailed performance evaluation of the proposed selection algorithms to determine their impact on the performance of the designed hybrid middleware which we further compare to state-of-the art solutions.

With the increasing popularity of Software-defined networks (SDN), TCAM memory of switches can be directly accessed by a publish/subscribe middleware to perform filtering operations at low latency. This way two important requirements for a publish/subscribe middleware can be fulfilled: namely bandwidth efficiency and line-rate performance in forwarding messages between producers and consumers. Nevertheless, it is challenging to sustain line-rate performance in the presence of dynamic changes in the interest of producers and consumers. In this paper, we propose and evaluate the PLEROMA middleware to realize publish/subscribe at line-rate and bandwidth efficiently in SDN. PLEROMA offers methods to efficiently reconfigure a deployed topology in the presence of dynamic subscriptions and advertisements. Furthermore, PLEROMA ensures interoperability and independent reconfiguration of multiple controlled SDN networks.