Search

A large variety of product-form solutions for continuous-time Markovian models can be derived by checking a set of structural properties of the underlying stochastic processes and a condition on their reversed rates. In previous work (Marin and Vigliotti (2010) [9]) we have shown how to derive a large class of product-form solutions using a different formulation of the Reversed Compound Agent Theorem (GRCAT). We continue this line of work by showing that it is possible to exploit this result to approximate the steady-state distribution of non-product-form model interactions by means of product-form ones.

Queueing systems with Poisson arrival processes and Hypo- or Hyper-exponential service time distribution have been widely studied in the literature. Their steady-state analysis relies on the observation that the infinitesimal generator matrix has a block-regular structure and, hence, the matrix analytic method may be applied. Let π n k be the steady-state probability of observing the k th phase of service and n customers in the queue, with 1 ≤ k ≤ K , and K the number of phases, and let π n = ( π n 1 , … , π n K ) . Then, it is well-known that there exists a rate matrix R such that π n + 1 = π n R . In this paper, we give a symbolic expression for such a matrix R for both cases of Hypo- and Hyper-exponential queueing systems. Then, we exploit this result in order to address the problem of approximating a M / HYPO K / 1 queue by a product-form model. We show that the knowledge of the symbolic expression of R allows us to specify the approximations for more general models than those that have been previously considered in the literature and with higher accuracy.

Product-forms are well-known in the community of performance evaluation because they allow the computation of the stationary state probabilities of large models that would otherwise be intractable. Roughly speaking, a product-form model consists of several interacting components. Under some conditions, the steady-state probabilities of these components can be derived in isolation as if the interactions with the remaining parts of the system are modelled by independent Poisson processes. The steady-state distribution of the joint model can be derived as the (normalised) product of the distributions of the isolated components. In the last few years some authors have introduced the idea of higher order product-forms or conditional product-forms that differ from ordinary product-forms because once the components of a model are isolated, the interactions with the rest of the system are not anymore seen as independent Poisson processes. However, to the best of our knowledge, up to now these methods have been applied only to approximate non-product-form models. In this paper we propose for the first time two classes of feed-forward queueing network models whose stationary distributions have conditional product-forms but not ordinary product-forms.

Product-forms in Stochastic Petri nets (SPNs) are obtained by a compositional technique for the first time, by combining small SPNs with product-forms in a hierarchical manner. In this way, performance engineering methodology is enhanced by the greatly improved efficiency endowed to the steady-state solution of a much wider range of Markov models. Previous methods have relied on analysis of the whole net and so are not incremental-hence they are intractable in all but small models. We show that the product-form condition for open nets depends, in general, on the transition rates, whereas closed nets have only structural conditions for a product-form, except in rather pathological cases. Both the ''building blocks'' formed by the said small SPNs and their compositions are solved for their product-forms using the Reversed Compound Agent Theorem (RCAT), which, to date, has been used exclusively in the context of process-algebraic models. The resulting methodology provides a powerful, general and rigorous route to product-forms in large stochastic models and is illustrated by several detailed examples.

Given a domain G, a reflection vector field d(.) on the boundary of G, and drift and dispersion coefficients b(.) and \sigma(.), let L be the usual second-order elliptic operator associated with b(.) and \sigma(.). Under suitable assumptions that, in particular, ensure that the associated submartingale problem is well posed, it is shown that a probability measure $\pi$ on \bar{G} is a stationary distribution for the corresponding reflected diffusion if and only if $\pi (\partial G) = 0$ and $\int_{\bar{G}} L f (x) \pi (dx) \leq 0$ for every f in a certain class of test functions. Moreover, the assumptions are shown to be satisfied by a large class of reflected diffusions in piecewise smooth multi-dimensional domains with possibly oblique reflection., Comment: 48 pages

Modern computer systems consist of a large number of dynamic hardware and software components that interact according to some specific rules. Quantitative models of such systems are important for performance engineering because they allow for an earlier prediction of the quality of service. The application of stochastic modelling for this purpose is limited by the problem of the explosion of the state space of the model, i.e. the number of states that should be considered for an exact analysis increases exponentially and is thus huge even when few components are considered. In this paper we resort to product-form theory to deal with this problem. We define an iterative algorithm with the following characteristics: a) it deals with models with infinite state space and block regular structure (e.g. quasi-birthadeath) without the need of truncation; b) in case of detections of product-form according to RCAT conditions, it computes the exact solution of the model; c) in case of non-product-form, it computes an approximate solution. The very loose assumptions allow us to provide examples of analysis of heterogeneous product-form models (e.g., consisting of queues with catastrophes and/or batch removals) as well as approximating non-product-form models with non-exponential service time distributions and negative customers.

In queueing networks with blocking, stations wishing to transmit customers to a full queue are blocked and need to take alternative action on completing a service. In general, product-forms, i.e. separable solutions for such a network's equilibrium state probabilities, do not exist but some product-forms have been obtained over the years in special cases, using a variety of techniques. We show that the Reversed Compound Agent Theorem (RCAT) can obtain these diverse results in a uniform way by its direct application, so unifying product-forms in networks with and without blocking. New product-forms are also constructed for a type of blocking we call `skipping', where a blocked station sends its output-customers to the queue after the one causing the blocking in that customer's path. Finally, we investigate a novel congestion management scheme for networks of finite-capacity queues in which a station with a full queue transmits signals that delete customers from upstream queues in order to reduce incoming traffic.

In this paper we provide a general method to derive product-form solutions for stochastic models. We take inspiration from the Reversed Compound Agent Theorem and we provide a different formulation using labeled automata, a generalization which encompasses a bigger class of product-form solutions, and a new proof based on the solution of the system of global balance equations. We show that our result may have practical applications in the performance evaluation of complex software and hardware architectures and can be the base for the development of new analysis tools or the extension of existing ones.

In this paper we study product-form conditions for Generalized Stochastic Petri Net models. We base our results on the Reversed Compound Agent Theorem (RCAT) that has been recently formulated in the stochastic process algebra research field. In previous works, we defined finite structured GSPN models equivalent to BCMP service stations. In this paper we prove the conditions under which it is possible to combine those GSPN models with other ones whose underlying stochastic processes satisfy RCAT conditions. Finally, we present a practical application which exhibits a product-form solution based on these new results and previous ones which were based on the M ⇒ M property. From a theoretical point of view, the results point out new relations among product-form model classes. As a practical consequence we have a possible definition of a hybrid formalism modelling tool that can identify product-forms.

Queueing networks with multiple classes of customers play a fundamental role for evaluating the performance of both software and hardware architectures. The main strength of product–form models, in particular of BCMP queueing networks, is that they combine a flexible formalism with efficient analysis techniques and solution algorithms. In this paper we provide an algorithm that starting from a high–level description of a system, and from the definition of its components in terms of interacting sub–systems, computes a multiple–class and multiple–chain BCMP queueing network. We believe that the strength of this approach is twofold. First, the modeller deals with simplified models, which are defined in a modular and hierarchical way. Hence, we can carry on sensitivity analysis that may easily include structural changes (and not only on the time parameters). Second, maintaining the product–form property allows one to derive the average system performance indices very efficiently. The paper also discusses the application of the algorithm for the performance evaluation of websites with modular architectures, such as those based on content management systems.