Analytics and Algorithms for Real Time IoT Workflow Composition in the Edge-Cloud Infrastructure
With the growth of Internet of Things (IoT), edge-based data stream processing (DSP) technologies are rapidly evolving with more and more data generated and processed for critical decision making. Many research works investigated the management of edge computing resources for IoT data processing tasks. However, IoT data streams flow into the edge continuously and, hence, IoT DSP has a periodical nature. Existing works rarely deal with the issues related periodical data processing. In this dissertation, we identify the gaps in current technologies for IoT data processing and develop solutions to bridge these gaps. The first gap in edge based IoT data processing is the overhead in the deployment model. Existing approaches have an implicit or explicit assumption about how to execute the DSP components on the edge nodes. Essentially, each DSP component in a DSP workflow should be built as a virtual machine, a container, or a serverless function so that it can be flexibly deployed at the selected edge node. In this model, the edge node responsible for the execution needs to allocate resources to the container and start it up. In fact, a well-built Docker image for machine learning is approximately 1GB and the transfer time together with the startup time spans 10 to 20 seconds, which is a significant overhead in real time DSP. With periodical DSP, the edge node either needs to restart each DSP component upon periodical invocations, resulting in recurring overhead, or needs to retain the DSP component in memory, incurring memory and cache overhead. Instead, we propose a service-oriented approach. Generally, among the large number of DSP workflows submitted to the edge cloud, there will be a lot of common data processing components. Thus, we run these DSP components as long running services instead of independent, encapsulated units to facilitate reuse and, subsequently, avoid the undesirable overhead. Correspondingly, service composition is needed for each workflow to select the set of services and hosts to satisfy its QoS requirements. Also, the conventional edge resource management problem for independent workflows needs to be converted into the service allocation problem in the edge cloud. A set of new solutions, including Robinhood greedy algorithm and the integrated greedy and genetic algorithm, are developed to provide efficient service allocation decisions. Experimental results show that our solution can significantly improve the edge resource management for periodical DSP workflow executions. The second gap due to periodical DSP workflows is the timing analysis techniques. It is not clear how to model a system with Poisson arrival of workflows which must be activated periodically. We show that when Poisson-arrival workflows generate periodically arriving jobs with uniformly distributed periods and lifetimes, the job arrival can still be approximated by the Poisson process. Accordingly, Markov model can be used to estimate the response time for DSP service execution. Also, the communication latency is an important factor in real-time IoT applications. Most of the existing works only consider the available network bandwidth and current data size for estimating the communication cost for data delivery, without taking the traffic from other workflows into account. We build a model to derive the average traffic for communication links in the edge network for handling the data exchange for DSP workflows. These novel techniques enable proper timing analysis for DSP workflow executions. The third gap due to periodicity in DSP is the workload fluctuation on the hosting edge nodes for the long living DSP workflows. In traditional workflow composition methods, the timing analysis is based on the current state of the system. When a periodical DSP workflow is activated at a certain future time, the workload for the selected services and edge hosts may have changed, which may cause the violation of the timing requirements for the workflow, even though the timing requirements were satisfied at the composition time. A worse situation may happen if the edge nodes perform admission control to control its service response time. A new activation for a workflow may get declined due to the heavy load on the hosting edge node at the time. This may subsequently require recomposition and transfer of a large amount of data and learnt models, causing significant delays. Thus, at service composition time, we need to make workload predictions to ensure that the service hosts we selected will be able to admit the workflow at all its invocations and satisfy its real time requirement. We explore different prediction methods for service workload prediction, including Neural Networks and ARIMA. We combine the prediction methods with QoS aware service composition techniques. Experimental results show that our prediction-based service composition approach can result in 40% in average less timing violations compared to the composition methods that do not consider service host workload predictions. In the above, we have considered various techniques for better timing analysis in service composition for periodical DSP workflows. However, these analysis techniques may incur significant overhead if applied to the very large number of potential candidate compositions. To cope with the problem, we have developed a three-phase composition approach. We first use a highly efficient but moderately accurate algorithm to eliminate most of the candidate compositions based on simpler analysis techniques. Then, the more accurate analyses are performed on a relatively small number of selected candidate compositions in the second phase. In the third phase, specific concrete services are selected for grounding to complete the composition for the workflow and for on-the-fly testing. The approach is scalable and can effectively achieve service composition for satisfying real-time requirements. Experimental studies show that the proposed approach does improve the effectiveness and time for composition of real time DSP workflows.