In many IoT systems, network gateways and servers must handle traffic from a vast number of devices. The incoming traffic typically exhibits high variance and autocorrelation. Moreover, as load increases, servers and gateways slow down and may even completely crash. Consequently, long periods of overload may be observed leading to long response times or even instability of the system. To prevent such situations, incoming traffic must be regulated through traffic shaping schemes. This paper analyzes a class traffic shaping schemes under stochastic assumptions and demonstrates how their parameters can be optimized to reduce the population and response time of the system without discarding incoming traffic. The analysis is based on matrix geometric methods and a new approach to analyze the stability of infinite Markov chains.

In [1] a new traffic shaping scheme denoted as Quasi-Deterministic Transmission Policy’ (QDTP) has been proposed and analyzed under deterministic and stochastic assumptions. This model is extended by considering phase type distributed and possible correlated arrivals, delays and services combined with load dependent behavior. Load dependent behavior is important to model overload situations at processing devices in a realistic way. It is shown that the resulting model describes a Quasi Birth Death Process (QBD) without state dependent rates for the delays and a Level Dependent Quasi Birth Death Process (LDQBD) with state dependent rates for the delays. We present an approach based on the recursive computation of QBDs or LDQBDs which can be applied if the number of states remains moderate. Larger models can be solved by a block iteration method. Finally, we show how the population in the system can be minimized by choosing an appropriate delay rate or vector of delay rates.

Markov Reward Models are widely used for performance or dependability analysis. Usually parameters of these models are assumed to be exactly known, results can then be computed numerically from the underlying Markov Reward Process. However, most times model parameters are estimated and are thus subject to uncertainty such that analysis becomes challenging and is usually done by analyzing the model for a large sample of possible input parameter settings which requires a huge effort if several parameters are uncertain. An alternative to this brute force approach is the computation of a simpler surrogate model from a smaller set of samples and apply the surrogate as a substitute for the Markov Reward Model. This paper presents several surrogate models, shows how they can be applied for Markov Reward Models and compares their quality by means of three different examples.

Dynamic Fault Trees (DFTs) are a powerful and widely used class of models for reliability analysis of technical systems. They describe the relation between failure times of elementary components and failures of the system modeled by the DFT. Failure times of elementary components are assumed to be independent and often exponentially distributed. Then the underlying stochastic process is a Continuous Time Markov Chain (CTMC) which is often analyzed numerically. In this paper, we use phase type distributions to model failure times of elementary components and extend DFTs by introducing two new types of nodes to express different variants of correlation between failure times which often can be observed in real systems. Since the use of phase type distributions enlarges the state space of the CTMC, compositional techniques allowing a compact representation of the generator matrix and analysis techniques exploiting this compact representation are also introduced. In particular, analysis techniques are presented that exploit the specific structure of the DFT.

The paper presents a new approach and a related software environment for the parallel simulation of swarms of autonomous robots in real time. The software environment has been developed for model based analysis of algorithms to control large swarms of distributed autonomous mobile robots communicating over an unreliable and capacity restricted wireless network. It includes a physical simulation of static obstacles, dynamic obstacles with scriptable movement, soil condition, active jammers, static and dynamic link obstacles with configurable damping as well as noise floors. The simulated ground based mobile robots use control particle belief propagation (C-PBP) as a randomized and sample based model predictive closed loop controller in combination with cost functions to evaluate the situations. We emphasize where the use of shared memory parallelism is beneficial and which inaccuracies in computations are acceptable to increase performance without losing realism.

The traditional expectation-maximization (EM) algorithm is a general purpose algorithm for maximum likelihood estimation in problems with incomplete data. Several variants of the algorithm exist to estimate the parameters of phase-type distributions (PHDs), a widely used class of distributions in performance and dependability modeling. EM algorithms are typical offline algorithms because they improve the likelihood function by iteratively running through a fixed sample. Nowadays data can be generated online in most systems such that offline algorithms seem to be outdated in this environment. This paper proposes an online EM algorithm for parameter estimation of PHDs. In contrast to the offline version, the online variant adds data immediately when it becomes available and includes no iteration. Different variants of the algorithms are proposed that exploit the specific structure of subclasses of PHDs like hyperexponential, hyper-Erlang or acyclic PHDs. The algorithm furthermore incorporates current methods to detect drifts or change points in a data stream and estimates a new PHD whenever such a behavior has been identified. Thus, the resulting distributions can be applied for online model prediction and for the generation of inhomogeneous PHDs as an extension of inhomogeneous Poisson processes. Numerical experiments with artificial and measured data streams show the applicability of the approach.

Fluid Stochastic Petri Nets (FSPNs) which have discrete and continuous places are an established model class to describe and analyze several dependability problems for computer systems, software architectures or critical infrastructures. Unfortunately, their analysis is faced with the curse of dimensionality resulting in very large systems of differential equations for a sufficiently accurate analysis. This contribution introduces a class of FSPNs with a compositional structure and shows how the underlying stochastic process can be described by a set of coupled partial differential equations. Using semi discretization, a set of linear ordinary differential equations is generated which can be described by a (hierarchical) sum of Kronecker products. Based on this compact representation of the transition matrix, a numerical solution approach is applied which also represents transient solution vectors in compact form using the recently developed concept of a Hierarchical Tucker Decomposition. The applicability of the approach is presented in a case study analyzing a degrading software system with rejuvenation, restart, and replication.

Modern driver assistance systems for self-driving cars often rely on data collected by different sensors to determine the necessary system decisions. To prevent system failures, different validation techniques are used. The development is often split between car manufacturers and suppliers, whereby the requested test effort is one main project acceptance criterion. Already available effort estimation methods are not applicable, because they rely on implementation details that do not exist at early phases or on project experiences or individual expert expectations, which are not reliable enough to be employed as trustworthy source. Therefore, we provide in this paper an analytic approach for the computation of the error probability of a multi-sensor system. Based on this, we can give estimations for the test effort such that with statistical confidence no errors of the sensor system can be expected during the tests. The approach is able to take both the dependencies between successive sensor errors and the correlation between different sensors into account, mainly by using discrete time Markov chains. The provided approach therefore allows to design multi-sensor systems such that a specified overall error probability can be met and to give an estimation for the upper bound of the test effort.

Quantitative aspects of modern IT systems are often specified by service level agreements (SLAs) which relate the maximal load of a system with guaranteed bounds for response times and delays. These quantities are specified for single services which are combined in a service oriented architecture (SOA) to composed services offered to potential users or other service providers. To derive SLAs for composed services and to plan the required capacity to guarantee SLAs, appropriate methods and tools have to be used that compute results based on information given in SLAs. In this paper it is argued that most available approaches are not sufficient to analyze systems based on SLA information. A new method and a tool are presented that support the efficient calculation of bounds for delays in composed systems based on bounds for the load and the delay of the individual components which are specified in the SLAs of the components. Furthermore, the presented tool can be used to generate bounds for the required processing capacity which a provider has to provide in order to guarantee the quality of service defined in the SLAs.

Model checking of Continuous Time Markov Chains (CTMCs) is a widely used approach in performance and dependability analysis and proves for which states of a CTMC a logical formula holds. This viewpoint might be too detailed in several practical situations, especially if the states of the CTMC do not correspond to physical states of the system since they are introduced for example to model non-exponential timing. The paper presents a general class of automata with stochastic timing realized by clocks. A state of an automaton is given by a logical state and by clock states. Clocks trigger transitions and are modeled by phase type distributions or more general state based stochastic processes. The class of stochastic processes underlying these automata contains CTMCs but also goes beyond Markov processes. The logic CSL is extended for model checking automata with clocks. A formula is then proved for an automata state and for the clock states that depend on the past behavior of the automaton. Basic algorithms to prove CSL formulas for logical automata states with complete or partial knowledge of the clock states are introduced. In some cases formulas can be proved efficiently by decomposing the model with respect to concurrently running clocks which is a way to avoid state space explosion.

A new class of non-Markovian models is introduced that results from the combination of stochastic automata networks and a very general class of stochastic processes, namely, rational arrival processes, which are derived from matrix exponential distributions. It is shown that the modeling formalism allows a compact representation of complex models with large state spaces. The resulting stochastic process is non-Markovian, but it can be analyzed with numerical techniques like a Markov chain, and the results at the level of the automata are stochastic distributions that can be used to compute standard performance and dependability results. The model class includes stochastic automata networks with phase-type distributed and correlated event times and also includes models that have a finite state space but cannot be represented by finite Markov chains. The paper introduces the model class, shows how the descriptor matrix can be represented in compact form, presents some example models, and outlines methods to analyze the new models.

Continuous Time Markov Decision Processes (CTMDPs) are used to describe optimization problems in many applications including system maintenance and control. Often one is interested in a control strategy or policy to optimize the gain of a system over a finite interval which is denoted as finite horizon. The computation of an ε-optimal policy, i.e., a policy that reaches the optimal gain up to some small ε, is often hindered by state space explosion which means that state spaces of realistic models can be very large or even infinite. The paper presents new algorithms to compute approximately optimal policies for CTMDPs with large or infinite state spaces. The new approach allows one to compute bounds on the achievable gain and a policy to reach the lower bound using a variant of uniformization on a finite subset of the state space. It is also shown how the approach can be applied to models with unbounded rewards or transition rates for which uniformization cannot be applied per se.

Inhomogeneous continuous-time Markov chains play an important role in different application areas. In contrast to homogeneous continuous-time Markov chains, where a large number of numerical analysis techniques are available and have been compared, few results about the performance of numerical techniques in the inhomogeneous case are known. This paper presents a new variant of the uniformization technique, the most efficient approach for homogeneous Markov chains. The new uniformization technique allows for the stable computation of strict bounds for the transient distribution of inhomogeneous continuous-time Markov chains, which is not possible with other numerical techniques that provide only an approximation of the distribution and asymptotic bounds. Furthermore, another variant of uniformization is presented that computes an approximation of the transient distribution and is shown to outperform standard differential equation solvers if transition rates change slowly.

Path-based techniques make the analysis of very large Markov models feasible by trading off high computational complexity for low space complexity. Often, a drawback in these techniques is that they have to evaluate many paths in order to compute reasonably tight bounds on the exact solutions of the models. In this paper, we present a path composition algorithm to speed up path evaluation significantly. It works by quickly composing subpaths that are precomputed locally at the component level. The algorithm is computationally efficient since individual subpaths are precomputed only once, and the results are reused many times in the computation of all composed paths. To the best of our knowledge, this work is the first to propose the idea of path composition for the analysis of Markov models. A practical implementation of the algorithm makes it feasible to solve even larger models, since it helps not only in evaluating more paths faster but also in computing long paths efficiently by composing them from short ones. In addition to presenting the algorithm, we demonstrate its application and evaluate its performance in computing the reliability and availability of a large distributed information service system in the presence of fault propagation and in computing the probabilities of buffer overflow and buffer flushing in a media multicast system with varying system configurations

The representation of general distributions or measured data by phase-type distributions is an important and nontrivial task in analytical modeling. Although a large number of different methods for fitting parameters of phase-type distributions to data traces exist, many approaches lack efficiency and numerical stability. In this paper, a novel approach is presented that fits a restricted class of phase-type distributions, namely, mixtures of Erlang distributions, to trace data. For the parameter fitting, an algorithm of the expectation maximization type is developed. This paper shows that these choices result in a very efficient and numerically stable approach which yields phase-type approximations for a wide range of data traces that are as good or better than approximations computed with other less efficient and less stable fitting methods. To illustrate the effectiveness of the proposed fitting algorithm, we present comparative results for our approach and two other methods using six benchmark traces and two real traffic traces as well as quantitative results from queuing analysis

During the design of large technical systems, the use of analytic and simulative models to test and dimension the system before implementation is of practical importance for an efficient and reliable design process. However, setting up the necessary models is time-consuming and therefore often too expensive in practice. Usually most information for modeling is already available in the design tool used to develop such extensive systems and only needs to be extracted for automatic model building. This paper presents an automated modeling approach from an existing design database using the example of a network analysis for building automation fieldbuses. The analysis is based on an analytical decomposition approach that enables fast estimation of performance measures for large-scale networks. The combination of fast analytical algorithms with automatic model generation allows network performance engineering with minimized effort for model generation and analysis.

The representation of general distributions or measured data by phase-type distributions is an important and non-trivial task in analytical modeling. Although a large number of different methods for fitting parameters of phase-type distributions to data traces exist, many approaches lack efficiency and numerical stability. In this paper, a novel approach is presented that fits a restricted class of phase-type distributions, namely mixtures of Erlang distributions, to trace data. For the parameter fitting an algorithm of the expectation maximization type is developed. The paper shows that these choices result in a very efficient and numerically stable approach which yields phase-type approximations for a wide range of data traces that are as good or better than approximations computed with other less efficient and less stable fitting methods. To illustrate the effectiveness of the proposed fitting algorithm, we present comparative results for our approach and two other methods using six benchmark traces and two real traffic traces.

We present a new approximate solution technique for the numerical analysis of superposed generalized stochastic Petri nets (SGSPNs) and related models. The approach combines numerical iterative solution techniques and fixed point computations using the complete knowledge of state space and generator matrix. In contrast to other approximation methods, the proposed method is adaptive by considering states with a high probability in detail and aggregating states with small probabilities. Probabilities are approximated by the results derived during the iterative solution. Thus, a maximum number of states can be predefined and the presented method automatically aggregates states such that the solution is computed using a vector of a size smaller or equal to the maximum. By means of a non-trivial example it is shown that the approach computes good approximations with a low effort for many models.

We present new algorithms for the solution of large structured Markov models whose infinitesimal generator can be expressed as a Kronecker expression of sparse matrices. We then compare them with the shuffle-based method commonly used in this context and show how our new algorithms can be advantageous in dealing with very sparse matrices and in supporting both Jacobi-style and Gauss-Seidel-style methods with appropriate multiplication algorithms. Our main contribution is to show how solution algorithms based on Kronecker expression can be modified to consider probability vectors of size equal to the “actual” state space instead of the “potential” state space, thus providing space and time savings. The complexity of our algorithms is compared under different sparsity assumptions. A nontrivial example is studied to illustrate the complexity of the implemented algorithms.

Superposed generalized stochastic Petri nets (SGSPNs) and stochastic automata networks (SANs) are formalisms to describe Markovian models as a collection of synchronously communicating components. Both formalisms allow a compact representation of the generator matrix of the Markov chain, which can be exploited for very space efficient analysis techniques. The main drawback of the approaches is that for many models the compositional description introduces a large number of unreachable states, such that the gain due to the compact representation of the generator matrix is completely lost. This paper proposes a new approach to avoid unreachable states without losing the possibility to represent the generator matrix in a compact form. The central idea is to introduce a preprocessing step to generate a hierarchical structure which defines a block structure of the generator matrix, where every block can be represented in a compact form similar to the representation of generator matrices originally proposed for SGSPNs or SANs. The resulting structure includes no unreachable states, needs only slightly more space than the compact representation developed for SANs and can still be exploited in efficient numerical solution techniques. Furthermore, the approach is a very efficient method to generate and represent huge reachability sets and graphs.

Performance analysis of multiprocessor architectures in the early design phases is an important task in the development of complex parallel architectures. An approach for the hierarchical modeling and analysis of a wide class of multiprocessor architectures is introduced. The technique combines and extends several efficient approaches to analyze large CTMCs underlying hierarchical models of multiprocessor systems. First, the generator matrix is represented in a very compact format which can be exploited in efficient numerical solution techniques. Second, symmetries inherent in most multiprocessor systems can be exploited by generating a CTMC with a smaller state space, which results from exact aggregation. Symmetry exploitation is fully automated and keeps the compact representation of the generator matrix.