Computation of the normalising constant for product-form models of distributed systems with synchronisation

Highlights

• We consider stochastic models of distributed systems with fork-join and batches of jobs.

• We provide an algorithm for the efficient computation of the performance indices.

• We compare the performance of the algorithm with the state of the art.

• We show some application scenarios in the case of distributed systems.

Abstract

Performance evaluation of large distributed systems plays a pivotal role in the design of Internet of Things (IoT) applications, or Big Data analysis, where high scalability and low response times are required. However, this performance assessment requires models, methodologies and tools tailored for this type of systems. Product-form queueing networks have been widely adopted for the analysis of sequential computations thanks to the availability of efficient algorithms for the computation of the average performance indices. However, this formalism has strong limitations since it does not allow one to model fork-join constructs or batches of jobs. Product-form stochastic Petri nets partially overcome these limitations but, on the other hand, general algorithms for the computation of the expected performance indices are not known or require strong assumptions on the model structure. In this paper, we define a new algorithm for the analysis of product-form stochastic Petri nets which works under much less restrictive assumptions than those previously proposed. The idea is that, in many cases, the entire state space of the model can be stored in memory thanks to multi-valued decision diagrams and the computation of the net’s performance indices can take advantage of the tree structure that characterises this representation. Finally, we present a case study and several examples that will be used to study the performance of the algorithm for realistic scenarios.

Introduction

Performance evaluation of large distributed systems is a challenging research topic that has attracted much attention over the last decades. In many practical cases, benchmarking the systems is too complicated and simulations may be time expensive and inappropriate for studies that must compare many possible configurations with the aim of choosing the best according to a certain metric. Analytical models, despite their strong assumptions, have shown to be a viable route to understand and tune the system’s performance at the early stages of its development (see, e.g., [1]).

Many works rely on queueing systems to study distributed architectures (see, e.g., [2], [3] for some recent references) but due to their very abstract level of representation of resource contention, Markovian queueing networks (QNs) find a wider application (see, e.g., [4], [5], [6]). Under mild conditions, Markovian queueing networks admit a product-form solution, i.e., the expression of the stationary distribution can be derived without resorting to the explicit solution of the Markov chain underlying the model. However, product-forms do not immediately imply the analytical tractability of the models. Indeed, for queueing networks several algorithms have been defined for the computation of the average performance indices in an efficient and numerically stable way (see [7] for a survey of the classical algorithms and [8] for a recent application). The drawback of this formalism consists in its limitations: aside from the assumptions on the distributions of service times and on the scheduling disciplines, product-form queueing networks are not able to model fork-join constructs nor batches of jobs or resources. Clearly, in distributed systems, this is a serious limitation. For example, in MapReduce based computations, the Map and Reduce phases correspond to fork and join constructs, respectively.

One of the most important formalisms that overcome the limitations of QN are the stochastic Petri nets (SPNs) [9], [10], [11]. They are widely used for modelling and performance evaluation of computer systems, computer networks, telecommunication systems as well as in bioinformatics where they are employed in modelling of various biological and biochemical processes. Like QNs [7], their underlying stochastic process is a continuous-time Markov chain (CTMC). Also like QNs, in practical use, SPNs suffer from the problem of state space explosion which consists in an exponential, in model size, growth of the number of distinct states of the underlying CTMC. This limits the scope of performance evaluation methods to models for which the underlying CTMC is small enough to be solved (i.e., to compute its transient or stationary probability distribution), or has a special structure. Because of these difficulties with solving models with large state spaces, a wide range of approximation methods and special solution methods for models with special structure or characteristics have been developed.

Product-form models, firstly identified for QNs [12], [13], have been studied for SPNs [14], [15], [16], [17] and other modelling formalisms; for a model in this class, the stationary probability distribution can be obtained in the form of a product over model components. State probabilities for these models are usually obtained in an unnormalised form (formally, a measure over the state space of the process is obtained), requiring the computation of the normalising constant which can be computed directly as a sum of unnormalised probabilities over the state space of the underlying CTMC or using more efficient convolution algorithms [18], [19]. The normalisation phase is crucial for determining most of the performance indices of the model.

The stationary analysis of product-form models is greatly simplified in comparison to other models and more complex models with larger state spaces can be efficiently analysed. However, the convolution algorithm for SPNs requires a special structure of the reachability set and can only be applied to the class of S-invariant reachable SPNs. Furthermore, at the current state of the art, it is not known how to automatically check the membership of this class without generating the reachability set, and the convolution is less efficient than in the case of QNs due to the need to solve a large number of systems of linear Diophantine equations. The S-invariant reachability restriction severely limits the utility of the convolution algorithm.

Multi-valued decision diagrams (MDDs) [20], data structures that encode discrete functions of discrete variables, have been used with great success in generation and storage of very large state spaces for bounded SPN models [21], [22]. In the present work, we use MDDs that encode state spaces of product-form models in order to efficiently compute the normalising constant for models with finite state spaces. We also propose related methods for the computation of performance measures of product-form SPNs with finite reachability sets. While we need to generate the reachability set of the SPN, we do not require S-invariant reachability and the proposed algorithm can thus be applied to general SPNs. Also, in contrast to convolution, we do not need to solve systems of Diophantine equations. Hence, the performance of the proposed algorithm on S-invariant reachable SPNs is thus much better than the convolution algorithm if reachability set generation is not taken into account, while being comparable otherwise.

The paper is laid out as follows. First, in Section 2, we propose a review of the literature on this topic. In Section 3, we introduce SPNs and product-forms. Section 4 introduces some notation for state spaces of the models handled in the paper, and defines MDDs. Based on these definitions, we introduce a novel recursive algorithm for computation of the normalising constant for general product-form models. In particular, the algorithm can be applied to SPNs. Section 5 compares the proposed algorithm to the convolution algorithm for a class of product-form SPNs [19] and proposes methods for performance evaluation, comparing them to the mean value algorithm (MVA) [23]. In Section 6 we report results of computational experiments on SPNs in which we test performance of the proposed algorithm and compare it to the performance of the SPN convolution algorithm. Finally, Section 7 concludes the paper. Appendix A contains the proofs of statements from the main part of the paper. While our main contributions are directed to the case of SPNs, for the sake of clarity we include in Appendix B a comparison with the convolution algorithm for a class of product-form QNs [18], which can be considered as a special case of what we propose here. The point of the latter appendix is not to compare the proposed algorithm with the convolution algorithm on QNs, but to drive the intuition of the reader who is expert on the queueing network analysis.