Deliverable D12
Bounds for Networks
The formalism of stochastic Petri nets has emerged as a powerful tool
for the description of parallel and distributed systems (see Deliverable D1). The present deliverable
focuses on analytical results which can be used for evaluating the
quantitative performance of such networks. The state of the art is
mainly based on bounds, although new exact analytical results were
also recently obtained within the project, in particular using product
form theory (see the talk of Richard Boucherie in the program of the
Torino Workshop) and using (max,+) techniques (see reference D12-4 below and the presentation by Jean Mairesse,
also in the proceedings of the Torino workshop).
The paper ``Comparison Properties of Stochastic Decision Free Petri
Nets'', by the INRIA group (see Chapter 3 of the proceedings of the
Sophia-Antipolis workshop: D12-1), gives new
bounds for stochastic event graphs based on the (max,+) recursive
equation approach; the convex ordering relations that exist between
deterministic and stochastic systems are presented in a unified
way. The bounds by association lead to Large Deviation bounds which
are also new within this context. Another general result states that
the throughput is a concave function of the initial marking, at least
for certain classes of firing time c.d.f. Thus for instance, the
throughput in the Qmips model described in D1 is a concave increasing
function of the multiprogramming degree.
The paper ``Structural Techniques and Performance Bounds of
Stochastic Petri Net Models'', also in D12-1, gives an overview
of the results obtained by the Zaragoza group on bounding techniques for
stochastic Petri nets. Qualitative and quantitative aspects are jointly used
for deriving performance bounds. The key concepts are those of P or T
semi flows, which allow one to obtain bounds on throughput and response
times which may in some cases only depend on the first moments of the firing
times. The special cases of Markovian nets and specific classes such as
Event Graphs lead to improved bounds.
The paper ``Operational Analysis of Timed Petri Nets and Application
to the Computation of Performance Bounds'' (D12-2), is a joint work by the Torino and the
Zaragoza groups. It was presented at the Torino workshop on Solution
Methods. Operational analysis techniques are to partially
characterize the behaviour of timed Petri nets under very weak
assumptions on their timing semantics. New operational inequalities
are derived that are typical of the presence of synchronization and
that were therefore not considered in queueing network models. We
show an interesting application of the operational laws to the
statement and the efficient solution of problems related to the
estimation of performance bounds insensitive to the timing probability
distributions. The results obtained generalize and improve in a clear
setting results that were derived in the last few years for several
different subclasses of timed Petri nets. In particular the extension
to Well-Formed Coloured nets appears straightforward and allows an
efficient exploitation of models symmetries.
The paper ``Computing bounds for the performance indices of
quasi-lumpable Stochastic Well-Formed Nets'', by the Torino group in
collaboration with UCLA (D12-3), was also presented at the Torino
workshop on Solution Methods. Structural symmetries in Stochastic
Well-Formed Colored Petri Nets (SWN) lead to behavioral symmetries
that can be exploited using the Symbolic Reachability Graph (SRG)
construction algorithm: This allows one to compute an aggregated
Reachability Graph (RG) and a ``lumped'' Continuous Time Markov Chain
(CTMC) that contains all the information needed to study the
qualitative properties and the performance of the modeled system
respectively. Some models exhibit qualitative behavioral symmetries
that are not completely reflected at the CTMC level, we call them
quasi-lumpable SWN models. In these cases, exact performance
indices can be obtained by avoiding the aggregation of those markings
that are qualitatively but not quantitatively equivalent. An
alternative approach consists in aggregating all the qualitatively
equivalent states, and computing approximated performance indices.
The paper ``Analytical Computation of Lyapunov Exponents in Stochastic
Event Graphs'', by the INRIA group (D12-4),
proposes an approach aimed at computing analytically the statistics of
the transient evolution of stochastic (max,+) ( but also
(min,+),(min,max,+) and others) systems. The technique essentially
consists in translating the (max,+) recurrence on random variables
onto a (+,x) linear recurrence on Laplace transforms. Although
currently restricted to the simplest systems, this method provides an
interesting insight on quantities such as the speed of convergence to
the stationary regime, the covariances and the central limit
convergence of the system. The fact that exact results can be computed
allows the evaluation of several bounding techniques.
The papers ``On the Saturation Rule for the Stability of Queues' and
``On the Stability of Jackson Queueing Networks', by INRIA, were also
presented at the Torino workshop. The conjecture on the stability
region for Jackson type networks is proved using recursive equation
techniques. The extension to general Free Choice Nets is underway, and
first results were presented on the matter in Torino.
- D12-1
- Chapter 3 of the Proceedings of the INRIA-Sophia
Antipolis Qmips Workshop on Stochastic Petri Nets,
INRIA Internal Publication, November 1992.
- Structural Techniques and Performance Bounds for Stochastic
Petri Net Models, J. Campos and M. Silva.
- Approximation Techniques for Stochastic
Macroplace/Macrotransition Nets, H. Jungnitz, A. Desrochers and M. Silva.
- Comparison Properties of Stochastic Decision Free Petri Nets,
F. Baccelli and Z. Liu.
- D12-2
- Operational Analysis of Timed Petri Nets and Application to the
Computation of Performance Bounds, G. Chiola, C. Anglano, J. Campos, J.M.
Colom and M. Silva (front page).
To appear in the Proceedings of the Torino Qmips Workshop on
Solution Methods, CWI Internal Publication, 1993.
- D12-3
- Computing bounds for the performance indices of quasi-lumpable
Stochastic Well-Formed Nets, G. Franceschinis and R. R. Muntz
(front page).
To appear in the Proceedings of the Torino Qmips Workshop on
Solution Methods, CWI Internal Publication, 1993.
- D12-4
- Analytical Computation of Lyapunov Exponents in Stochastic
Event Graphs, Alain Jean-Marie.
To appear in the Proceedings of the Torino Qmips Workshop on
Solution Methods, CWI Internal Publication, 1993.
- D12-5
- On the Saturation Rule for the Stability of Queues/
On the Stability of Jackson Queueing Networks, F. Baccelli and S. Foss,
INRIA Reports No. 1945 and 2015
(front page).
To appear in the Proceedings of the Torino Qmips Workshop on
Solution Methods, CWI Internal Publication, 1993.
Page Web by
Alain Jean-Marie
(Alain.Jean-Marie@sophia.inria.fr)
Last Modified: 26 September 1995.