Towards a Product Form Solution for Stochastic Process Algebras

Testo completo

(1)

Towards a Product Form Solution for Stochastic Process Algebras

Matteo Sereno

Dipartimento di Informatica, Universit`a degli Studi di Torino, Corso Svizzera 185, 10149 Torino, Italy

We examine product form equilibrium distributions for stochastic process algebra models, finding conditions that guarantee the existence of a solution for the traffic equations. These equations are a set of linear equations, which are the basis of exact analysis of product form models like queueing networks, stochastic Petri nets, as well as stochastic process algebras. This paper illustrates how the equilibrium distribution can be expressed as a product for a certain class of stochastic process algebra models that satisfy certain conditions. Although the product form criterion derived in this paper is developed in the context of Performance Evaluation Process Algebra (PEPA), the results can be easily generalised to any of the other stochastic process algebras.

1. INTRODUCTION

The advantages of having structured modelling paradigms have been pointed out by several authors in recent years. Many efforts have been devoted to the study of modelling techniques in which compositionality plays a fundamental role. One outcome of the last years is the definition of new paradigms for performance mod- elling based on classical process algebras (CCS, CSP) which are known as Stochastic Process Algebras (SPAs).

These include PEPA (Gilmore & Hillston, 1994; Hill- ston, 1994), MTIPP (Gotz et al., 1994; Hermanns &

Rettelbach, 1994), Buchholz’s MPA (Buchholz, 1994) and Bernardo et al.’s MPA (Bernardo et al., 1994).

A major drawback of these languages is the need to work at the state space level. Even for relatively small models the size of the state space is huge and this prevents the use of these formalisms for comput- ing performance measures of many interesting systems.

To overcome this problem solutions based on aggrega- tion techniques that avoid the construction of the entire state space of the model have been proposed (Hillston, 1995b; Ribaudo, 1995).

In this paper we approach the state space explosion problem using different arguments by characterising SPA models that exhibit Product Form (PF) equilib- rium distribution.

The PF criterion for SPAs presented here is derived from the PF for SPNs derived by Henderson et al. and presented in several papers, see for instance (Boucherie

& Sereno, 1994; Henderson et al., 1989; Henderson &

Taylor, 1991).

Our goal is to import the results derived for SPNs into the stochastic process algebra environment. This would be the starting point for further investigations.

The availability of a PF criterion for SPAs could be combined with the typical features of SPAs (for in- stance compositionality) to obtain efficient computa- tional methods for the computation of performance measures.

Although the product form criterion derived in this paper is developed in the context of PEPA (Hillston, 1994), the results can be easily generalised to any of the other stochastic process algebras.

The paper is organised as follows. In Section 2 we first introduce some notation. Sections 3 and 4 contain the main results while some examples are given in Section 5.

Finally, Section 6 concludes the paper outlining possible future work on this topic.

2. INTRODUCTORY DEFINITIONS

Performance Evaluation Process Algebra (PEPA) is an algebraic description technique based on a classical pro- cess algebra (Hoare, 1985; Milner, 1989) and enhanced with timing information. This extension allows one to compute performance measures as well as to deduce qualitative properties of the modelled systems. In this section we briefly introduce PEPA. More detailed in- formation can be found in (Gilmore & Hillston, 1994;

Hillston, 1994).

Process algebras are mathematical theories which model concurrent systems by their algebra and provide a tool for reasoning about the structure and behaviour of the model. Systems are viewed as collections of agents who execute actions. In PEPA actions take time and exponentially distributed random variables repre- senting their duration are associated with them.

An activity a ∈ Act is described as a pair (α, r), where α ∈ A is the type of the activity and r ∈ IR+ is

(2)

the parameter of the negative exponential distribution associated with the action. Activities may be passive and in this case the rate is unspecified and it is denoted by>.

Systems are described as interactions of components that perform a set of activities and the syntax for de- scribing such components is the following

P ::= (α, r).P | P + Q | P

><

L Q | P/L | A Prefixing is the basic mechanism to build the be- haviour of components: (α, r).P carries out the activity (α, r) and then behaves like P .

The component P + Q enables activities of P and Q.

A race condition governs the dynamic behaviour of a model whenever more than one activity is enabled. This means that we may think of all the activities attempting to proceed, but only the fastest succeeding. The first activity to complete in P + Q determines its behaviour.

The component P

><

L Q represents a system where processes P and Q work together to perform some activ- ities. The set L is called the cooperation set and defines the action types on which the components must syn- chronise or cooperate. P and Q proceed independently with any activities whose types do not occur in the co- operation set L. However, activities with action types in the set L are assumed to require the simultaneous involvement of both components.

When the set L is empty,

><

L has the effect of par- allel composition, allowing components to proceed con- currently without any interaction between them. In this case the concise notation P ||Q is usually used.

The component P/L behaves as the component P except that any activities of types within the set L are hidden, meaning that their type is not visible. Instead they appear as the unknown type τ and can be regarded as an internal delay by the component. The rate of the activity is unaffected by hiding. When a type has been hidden within a component the component cannot participate in a cooperation on that type.

It is assumed that there is a countable set of con- stants. Constants are components whose meaning is given by defining equation such as Adef= P which gives the constant A the behaviour of P .

Definition 1. If P (a,r)−→ P0, then P0is a (one-step) derivative of P . In general, P0 is a derivative of P if P (a−→ · · ·1,r1) (a−→ Pn,rn) 0.

These derivatives are the states of the labelled multi- transition system. For any PEPA component the set of derivatives which can evolve from the component can be defined recursively.

Definition 2. The derivative set of a PEPA com- ponent Sys is denoted ds(Sys) and it can be defined as the smallest set of components such that:

if Sysdef= Sys0 then Sys0∈ ds(Sys);

if Sysi ∈ ds(Sys) and there exists a ∈ Act(Sysi) such that Sysi−→ Sysa j, then Sysj∈ ds(Sys).

Thus derivative set is the set of components which capture reachable states of the system. These form the nodes of the transition diagram representing the possi- ble behaviours of the system, this graph is called the derivation graph.

The Markov process underlying any finite PEPA com- ponent can be obtained directly from the derivation graph. A state of the Markov process is associated with each node of the graph and the transitions be- tween states are defined by the arcs of the graph. Since all activity durations are exponentially distributed, the total transition rate between two states will be the sum of the activity rates labelling arcs connecting the corre- sponding nodes in the derivation graph.

To ensure that the underlying Markov process is er- godic, the derivation graph of a PEPA model must be strongly connected. Some necessary conditions for er- godicity, at the syntactic level of a PEPA model, have been defined in (Hillston, 1994).

From the necessary condition for ergodicity it follows that we can define the syntax of PEPA expressions in terms of sequential components S and model components P (Hillston, 1995a):

P ::= S | P

><

L P | P/L S ::= (α, r).S | S + S | A

In the following we will consider only PEPA models with a structure such that the underlying Markov chain is ir- reducible with finite state space and positive-recurrent states. It follows that all PEPA models that are de- scribed in this paper represent systems with steady state behaviour.

The states of a PEPA model are syntactic terms, or derivatives. A model component consists of one or more cooperating sequential components, and these cooper- ating components will be apparent in every derivative of the model. The sequential components involved in the model and the cooperation sets remain static through- out the evolution of the model. Only the particular derivative exhibited by each of the sequential compo- nents may change. This allows one to obtain a more compact and useful representation of any state. The next two definitions allow us to formalise this compact representation of the states of a PEPA model (Hillston, 1995a).

Definition 3. Let Sys be a model component com- prised of sequential components S1, S2, . . . , SK. Then a state vector of the model component Sys as deriva- tive Sysi is the vector (S1i, S2i, . . . , SKi) where Shi, 1≤ h ≤ K is the current derivative of Sh in Sysi.

Definition 4. A sequential component Sk is said to be redundant within the state vector representation of a model component Sys if Sk is a sequential component of Sys and for all derivatives Sysi ∈ ds(Sys) given

(3)

(P

1

;P

1

;Q

1 )

(P

2

;P

1

;Q

1

) (P

1

;P

2

;Q

1 ) (a

1

;r

1 )

(P

2

;P

2

;Q

1 ) (P

3

;P

1

;Q

2

) (P

1

;P

3

;Q

2 )

(P

3

;P

2

;Q

2 ) (P

2

;P

3

;Q

2 ) (a

1

;r

1 )

(a

1

;r

1 ) (a

1

;r

1 ) (a

3

;r

3 )

(a

3

;r

3 )

(a

3

;r

3

) (a

3

;r

3 ) (a

2

;r

2

) (a

2

;r

2 )

(a

2

;r

2

) (a

2

;r

2 )

FIGURE 1. Derivation graph of the PEPA model of Example 1

the current derivatives of the sequential components Sji, j 6= k, the current derivative of Sk, Ski can be inferred.

If a sequential component is redundant within a state vector, a reduced state vector may be obtained in which the derivatives of this component have been eliminated.

Example 1. Consider a system defined as P1 def

= (a1, r1).P2

P2

def= (a2, r2).P3

P3 def

= (a3, r3).P1

Q1 def

= (a1, >).Q1+ (a2, >).Q2

Q2

def= (a3, >).Q1

Sys def= (P1||P1)

><

{a1,a2,a3}(Q1)

Figure 1 shows the derivation graph of this PEPA model. In this figure the derivatives are represented as state vectors.

From the previous figure we can observe it is possi- ble to group the derivatives in strong equivalence classes (Hillston, 1995b). This equivalence relation groups to- gether all the states that can be obtained by permu- tation of the sequential components inside cooperat- ing components. For instance the partition into strong equivalence classes of the derivative set of the previous PEPA model is

{

{(P1, P1, Q1)} ,

{(P2, P1, Q1), (P1, P2, Q1)} , {(P2, P2, Q1)} ,

{(P3, P1, Q2), (P1, P3, Q2)} , {(P3, P2, Q2), (P2, P3, Q2)}

}

.

It is easy to see that this partitioning satisfies the lumpability conditions, see (Hillston, 1995b).

Using this equivalence notion we can derive an use- ful representation of the state vector of a given strong equivalence class.

Definition 5. Let Sys be a model component com- prising sequential components S1, S2, . . . , SK and N the number of distinct sequential derivatives that can be ex- hibited in Sys. If Sysi∈ ds(Sys) then the strong equiv- alence class to which the state vector (S1i, S2i, . . . , SKi) belongs can be represented as the equivalence vector m = (m1i, m2i, . . . , mNi), where mli (for l = 1, . . . , N ) records the instances of Sli exhibited in Sysi.

In the PEPA model of Example 1 there are only two sequential components (P and Q) but there are five distinct sequential derivatives (P1, P2, P3, Q1, Q2).

Figure 2 shows the aggregation of the derivation graph presented in Figure 1.

(2;0;0;1;0)

(1;1;0;1;0)

(0;2;0;1;0) (a

1

;2r

1 )

(a

1

;r

1 )

(a

2

;r

2 )

(1;0;1;0;1)

(a

2

;2r

2 )

(0;1;1;0;1)

(a

3

;r

3 )

(a

3

;r

3 )

FIGURE 2. Aggregate representation of the derivation graph of the PEPA model of Example 1

In the following we call the set of all the equiva- lence vectors the aggregate derivation set (denoted by

(4)

ads(Sys)).

Let us introduce two definitions that will be used to derive the PF-criterion. Let Sys be a model compo- nent comprising sequential components S1, S2, . . . , SK. WithAct(Sys) we denote the set of actions of Sys.

For any action a ∈ Act(Sys) we define the pre-set of a (P re(a)) as the set of components that enable the action a. In an analogous way we define the post-set of a as the set of components which might result from the completion of the action a.

The pre- and the post-sets of the actions of the PEPA model of Example 1 are

action pre-set post-set a1 {P1, Q1} {P2, Q1} a2 {P2, Q1} {P3, Q2} a3 {P3, Q2} {P1, Q1}

In general the syntax of the language allows one to have the same action occurring in different instances within the same component (perhaps with different rates), but for the purposes of this paper we need an additional restriction due to the fact that an action can- not have more than one pre-set. To achieve this goal we assume that the actions of any sequential compo- nent must have different names. Moreover, actions of the same name belonging to distinct sequential compo- nents must occur in cooperation (synchronisation). The impact of this assumption on the language is an issue that has yet to be addressed.

The next examples show situations that are not al- lowed.

Example 2. Consider a system defined as P1 def

= (a1, r1).P2

P2 def

= (a2, r2).P3

P3

def= (a1, r3).P1

Sys def= P1||P1||P1

the pre- and the post-sets of the actions of Sys are action pre-set post-set

a1 {P1} , {P3} {P2, P1} a2 {P2} {P3}

Action a1 does not satisfy the previous assumption because it has two distinct pre-sets.

Example 3.

P1

def= (a1, r1).P2

P2 def

= (a2, r2).P3

P3

def= (a3, r3).P1

Q1 def

= (a1, >).Q2

Q2 def

= (a3, r4).Q1

Sys def= P1

><

{a1}Q1

the pre- and the post-sets of the actions of Sys are action pre-set post-set

a1 {P1, Q1} {P2, Q2}

a2 {P2} {P3}

a3 {P3} , {Q2} {P1} , {Q1}

The previous assumption is not satisfied by action a3; it is satisfied by a1 because this action belongs to the cooperation set.

In an analogous way to the equivalence vector rep- resentation for the state vector, we denote by P re(a) and P ost(a) the equivalence vector representation of the pre- and post-set of the action a. Using this nota- tion an action a enabled in one of the derivatives rep- resented by the equivalence vector m can be seen as a transformation

n + P re(a) −→ n + P ost(a),a

where n is the equivalence vector representation of the states obtained from any vector represented by m by removing the set of components of the pre-set of a.

2.1. Markov chain model

Assume that the finite PEPA model Sysdef= Sys0com- prising sequential processes S1, S2, . . . , SK can be rep- resented by a stable regular, continuous-time Markov chain X ={X(t), t ≥ 0}, such that X(t) = {Sysi} in- dicates that the system, at time t, behaves as one of the components in the strong equivalence class to which Sysi belongs. The state space of this Markov chain is ads(Sys). A state m represents a strong equivalence class. The rate at which an action a is executed in state m is

q(P re(a), P ost(a); m − P re(a)) = µ(a)Φ(m−P re(a))

Φ(m) p(P re(a),P ost(a)), (1) with m and m− P re(a) + P ost(a) ∈ ads(Sys). We have added the state depending function Φ(m− P re(a))/Φ(m) in the transition rates to ac- count for the state-dependent service rate in the ag- gregate CTMC.

The transition rate from state m to state m0 = m− P re(a) + P ost(a) in the Markov chain X is

q(m, m0) = X

n + Pre(a)=m, n + Post(a)=m’

q(P re(a), P ost(a), n). (2)

A collection of positive numbers, w = (w(m), m ∈ ads(Sys)), is called an invariant measure for the Markov chain X, if it satisfies the following equations

X

m’ ∈ ads(Sys)

{

w(m)q(m, m0)− w(m0)q(m0, m)

}

= 0, (3)

(5)

for all m ∈ ads(Sys). The previous equations are called the global balance equations for X. When w is a proper distribution over ads(Sys) it is called equi- librium distribution, in this case it will be denoted by π = (π(m), m ∈ ads(Sys)).

In the literature several more restrictive forms of bal- ance exist (see (van Dijk, 1993) for details). In par- ticular, it is well known that a form of local balance is the common feature for all performance models with product form equilibrium distribution. In this paper we will use the group-local-balance property (Boucherie

& van Dijk, 1991) to prove that the proposed prod- uct form distribution is an equilibrium distribution. A measure w satisfies the group-local-balance property for the Markov chain X if for all g, g0, n such that n + g ∈ ads(Sys)

X

g06=g

{

w(n + g)q(g, g0; n) +

−w(n + g0)q(g0, g; n)

}

= 0, (4)

where g and g0 represent the equivalence vector of the pre- and the post-sets of actions. If we sum the group- local-balance equations over all g, n such that n+g = m we obtain the global balance equations.

2.2. The role of the function Φ(·)

The aim of this section is to clarify the role played by the function Φ(·).

Example 4. Consider a system defined as C1 def

= (a1, r1).C2

C2 def

= (a2, r2).C1

Sys def= C1||C1||C1

the pre- and the post-sets of the actions of Sys are action pre-set post-set

a1 {C1} {C2} a2 {C2} {C1}

Figure 3 shows the derivation graph of this PEPA model. In this figure the derivatives are represented as state vectors.

The partition into strong equivalence classes of the derivative set of the previous PEPA model is

{

{(C1, C1, C1)} ,

{(C2, C1, C1), (C1, C2, C1), (C1, C1, C2)} , {(C2, C2, C1), (C2, C1, C2), (C1, C2, C2)} , {(C2, C2, C2)}

}

.

Figure 4 shows the aggregation of the derivation graph presented in Figure 3.

To compute the rate at which an action a is executed in state m = n + P re(a) we must count the num- ber of transitions in the derivation graph that bring

(3;0)

(2;1)

(1;2)

(0;3) (a

1

;3r

1

) (a

2

;r

2 )

(a

1

;2r

1 )

(a

2

;2r

2 )

(a

1

;r

1 )

(a

2

;3r

2 )

FIGURE 4. Aggregate representation of the derivation graph of the PEPA model of Example 4

the PEPA system from one of the derivatives repre- sented by n + P re(a) to one of the derivatives rep- resented by n + P ost(a). Let us consider the effect of action a on the i-th (for i = 1, . . . , N ) component of the equivalence vector m. We know from Definition 5 that mi = ni + P rei(a) records the number of sequential components that behave as Si. The action a trans- forms P rei(a) of the mi components. The number of transitions in the derivation graph that are represented by the transition of the aggregate derivation graph

ni+ P rei(a)−→ na i+ P osti(a)

is equal to the number of different combinations of P rei(a) objects chosen between a set of ni+ P rei(a) and can be obtained by

(P rei(a))!

ni+ P rei(a) P rei(a)



= (ni+ P rei(a))!

ni! . Note that we restricted our attention to the i-th compo- nent of the vector m. Let us denote by D(m, P re(a)) the number of transitions in the derivation graph that are represented by the transition

n + P re(a)−→ n + P ost(a)a

in the aggregated derivation graph. Using the previous reasoning we can obtain that

D(m, P re(a)) =

(m1)!(m2)! . . . (mN)!

(m1−P re1(a))!(m2−P re2(a))! . . . (mN−P reN(a))!. (5) If the function Φ(·) is defined as

Φ(m) = 1

(m1)!(m2)! . . . (mN)! (6) we obtain that

Φ(m−P re(a))

Φ(m) =

(m1)!(m2)! . . . (mN)!

(m1− P re1(a))!(m2− P re2(a))! . . . (mN− P reN(a))!

(6)

a

1

(C

1

;C

1

;C

1 )

a

2

(C

2

;C

1

;C

1 )

(C

2

;C

2

;C

1 )

(C

1

;C

2

;C

1

) (C

1

;C

1

;C

2 )

(C

2

;C

1

;C

2

) (C

1

;C

2

;C

2 ) a

2 a

1

a

1

a

2

a

1 a

2 a

1 a

2

a

1 a

2

a

1 a

2 a

1 a

2

a

2

(C

2

;C

2

;C

2 ) a

1

a

1 a

2

a

1

a

2

FIGURE 3. Derivation graph of the PEPA model of Example 4

= D(m, P re(a)).

The previous reasoning gives an interpretation for the function Φ(·) that has been introduced in the expression of the rates in the aggregated derivation graph (Equa- tion 1).

In the PEPA model of Example 4 we can see that the rates between states in the aggregated derivation graph can be computed as shown in the table below (note that 0! = 1).

Transition Rate

[3, 0]−→ [2, 1]a1 (3−1)!3! r1 = 3r1

[2, 1]−→ [1, 2]a1 (2−1)!·1!2!·1! r1= 2r1

[1, 2]−→ [0, 3]a1 (1−1)!·2!1!·2! r1= r1

[0, 3]−→ [1, 2]a2 (3−1)!3! r2 = 3r2

[1, 2]−→ [2, 1]a2 1!·(2−1)!1!·2! r2= 2r2

[2, 1]−→ [3, 0]a2 2!·(1−1)!2!·1! r2= r2

3. THE ROUTING PROCESS

The central feature of this PF-criterion is to consider the actions of the PEPA model to be themselves states in a Markov chain, which we call the routing process.

This is achieved by considering the pre- and post-sets of the PEPA system to be states of this Markov chain.

Using the equivalence vector of pre- and the post-sets we define the setR as

R = [

a∈Act(Sys)

P re(a) ∪ [

a∈Act(Sys)

P ost(a).

The set R contains all the equivalence vectors of the pre- and the post-sets of actions of Sys.

Define single step transition probabilities of the set R as

p(b, b0) = P rob(P re(a), a, P ost(a))

whenever there exists an action a with b = P re(a), b0 = P ost(a). Otherwise let p(b, b0) = 0.

Note that the requirement that no action can have more that one pre-set means that these probabilities are well defined.

Define the routing chain as a Markov chain y = (y(τ), τ ≥ 0)

whose state space isR with transition rates qy(b, b0) = µ(a)p(b, b0),

where b = P re(a), b0 = P ost(a), and µ(a) is the rate of the action a. The global balance equations for the routing chain y are

X

a0∈Act(Sys)

{

f (P re(a)) · µ(a) · p(P re(a), P re(a0)) +

−f(P re(a0)) µ(a0) p(P re(a0), P re(a))

}

= 0, (7)

for all a ∈ Act(Sys). These equations represent the pro- cess algebra equivalent of the well-known traffic equa- tions for queueing networks and stochastic Petri nets.

This set of linear equations are the basis of the anal- ysis of PF-QNs, PF-SPNs, and Product Form Process Algebras as well.

Remark (Traffic Equations) In queueing network literature the traffic equations are usually denoted by ci =PN

j=1cjpji (for i = 1, . . . , N ), where the ci-s are the solutions of these equations and pji is the routing probability from station j to station i. If we substitute ci = f (P re(i)) · µ(i) and pji = p(P re(j), P re(i)) we can see that Equations (7) are equivalent to the stan- dard traffic equations of queueing networks.

The next step is to establish the constraints that a PEPA model must satisfy to have an invariant measure

(7)

for the routing chain. The following definition and as- sumption are essential to this aim.

Definition 6. For A ⊆ Act(Sys) define K(A), the set of equivalence vectors of the pre-sets and post-sets of actions in A, as

K(A) = [

a∈A

P re(a) ∪ [

a∈A

P ost(a).

The subset of actions A is said to be closed if for any l ∈ K(A) there exists a0, a00∈ A such that l = P re(a0), as well as l = P ost(a00); that is, each post-set is also a pre-set for an action in A, and vice-versa each pre-set is also a post-set.

The following assumption is the key to identify those PA components for which there exists a positive solution for the traffic equations.

Assumption 1. Assume that all the actions a ∈ Act(Sys) belong to at least one closed set, i.e., assume that for all a ∈ Act(Sys) there exists a subset A ⊆ Act(Sys) such that a ∈ A and A is a closed set.

Let ClA = {A1, A2, . . . , Ah} be the set of closed sets.

On this set we define an equivalence relation as fol- lows. Let Ai, Aj ∈ ClA, we say that Ai, Aj are in com- mon pre-set relation (notation Ai P R Aj) if there exists a ∈ Ai, b ∈ Aj such that P re(a) = P re(b). The rela- tion P R is the transitive closure of P R.

The relation P R induces a partition of the set of actions of the system into strong equivalence classes.

From the relation P R we can also derive a partition of the states of the routing chain. Define S(A) ⊆ S to be the set of states of y corresponding to the strong equivalence class to which the set A belongs.

The next theorem shows that the partition of ClA into strong equivalence classes {P R(A)}A ∈ ClA ob- tained from the relation P R induces a partition {S(A)}A ∈ ClA of the set of states of the routing chain if and only if Assumption 1 is satisfied.

Theorem 1. Assumption 1 is necessary and suffi- cient for the existence of an invariant measure of the routing chain.

Proof We have to observe that the routing chain has an invariant measure if and only if the state space S contains only irreducible sets. Therefore it is sufficient to prove that Assumption 1 is a necessary and sufficient condition for the partitioning of S into irreducible sets {S(A)}A ∈ ClA.

For any Ai, Aj∈ ClA if Ai P R Ajthen by definition of the sets S(·) we have that S(Ai) = S(Aj). If there are two subsets A0, A00of the S and S(A0)∩ S(A00)6= ∅ then ∃ a ∈ Act such that a ∈ S(A0)∩ S(A00) and a belongs to both the strong equivalence classes P R(A0) and P R(A00), and hence P R(A0) = P R(A00). Hence this shows that S(Ai) = S(Aj) if Ai P R Aj.

We can see by Assumption 1 that P R induces a partition of S into irreducible sets. From the Perron- Frobenius theorem (cf. Seneta (Seneta, 1981)) it follows

that there exists an invariant measure for the routing chain.

Conversely, assume that an invariant measure exists for the routing chain. This implies that S is partitioned in irreducible sets. Let Vi, i = 1, . . . v, denote the irre- ducible sets of y. Let a ∈ Act be an action and Vj be an irreducible set of states of y such that a ∈ Vj. Since Vj is an irreducible set we have that for all v ∈ Vj there exist two sequences of actions σ = ai1ai2. . . aip and σ0 = aj1aj2. . . ajq with the following properties. Let P, P0 be two components belonging to the derivative set of Sys such that in the component P the ac- tion a is enabled (i.e., P = (. . . , P re(a), . . .)), and in the component P0 the action v is enabled (i.e., P0 = (. . . , P re(v), . . .)), then from the irreducibil- ity of the set Vj it follows that P −→ · · ·ai1 −→ Paip 0 and P0 −→ · · ·aj1 −→ P . Thus the set of actionsajq

ai1, ai2, . . . , aip, aj1, aj2, . . . , ajq

is a closed set. Sim- ilarly, from the irreducibility we may conclude that all subsets of actions contained in Vjbelong to a closed set.

The traffic equations for the PEPA model are closely related to the global balance equations for y. The traffic equations are

X

a0∈Act(Sys)

f (P re(a)) · µ(a) · p(P re(a), P re(a0)) = X

a0∈Act(Sys)

f (P re(a0)) µ(a0) p(P re(a0), P re(a)). (8)

The traffic equations balance the average rate at which the the equivalence vector of the pre-set of an action a P re(a) is “absorbed” with the average rate at which P re(a) is “formed”. We have to point out that this form of balance requires that P re(a) is the post-set of some action a0 if P re(a) is the pre-set for an action a.

4. CLOSED FORM SOLUTION

Theorem 2. Let Sys be a model component com- prising sequential components S1, S2, . . . , Sk. With Act(Sys) and ads(Sys) we denote the respectively the set of actions and aggregate derivative set of Sys. Assume that there exists an invariant mea- sure f (·) for the traffic equations, and a function πf (·): ads(Sys) −→ IR+ which have the property that, for all a ∈ Act(Sys) and n + P re(a) in the aggregate derivative set,

πf(n + P re(a))

πf(n + P re(b)) = f (P re(a))

f (P re(b)). (9) whenever p(P re(a), P re(b)) > 0.

Then the equilibrium distribution of Sys is given by π(m) = 1

GΦ(m) πf(m), ∀ m ∈ ads(Sys), (10) where G is a normalisation constant.

Proof To prove this theorem we have to show that the measure Φ(m)πf(m) satisfies the group-local-balance

(8)

X

a 0

6=a

f(

m

)f(

m

)q(

Pre

(a);

Pre

(a0);

m Pre

(a))+

(

m Pre

(a)+

Pre

(a0))f(

m Pre

(a)+

Pre

(a0))q(

Pre

(a0);

Pre

(a);

m Pre

(a))g=

Eq.(1)

= X

a 0

6=a

f(

m

)f(

m

)(a)(

m Pre

(a))

(

m

) p(

Pre

(a);

Pre

(a0))+

(

m Pre

(a)+

Pre

(a0))f(

m Pre

(a)+

Pre

(a0))(a0) (

m Pre

(a))

(

m Pre

(a)+

Pre

(a0))p(

Pre

(a0);

Pre

(a))g

= (

m Pre

(a))X

a 0

6=a f

f

(

m

)(a)p(

Pre

(a);

Pre

(a0)) f(

m Pre

(a)+

Pre

(a0))p(

Pre

(a0);

Pre

(a))g

= (

m Pre

(a))f(

m

)



f

(

m

)aX06=aff(

m

)(a)p(

Pre

(a);

Pre

(a0)) f(

m Pre

(a)+

Pre

(a0))p(

Pre

(a0);

Pre

(a))g

= (

m Pre

(a))f(

m

)X

a 0

6=a

f(a)p(

Pre

(a);

Pre

(a0)) f(

m Pre

(a)+

Pre

(a0))



f

(

m

) p(

Pre

(a0);

Pre

(a))g

Eq.(7)

= (

m Pre

(a))X

a 0

6=a

f(a)p(

Pre

(a);

Pre

(a0)) f(

Pre

(a0))

f(

Pre

(a))p(

Pre

(a0);

Pre

(a))g

= (

m Pre

(a))f(

Pre

(a))

f(

Pre

(a))aX06=af(a)p(

Pre

(a);

Pre

(a0)) f(

Pre

(a0))

f(

Pre

(a))p(

Pre

(a0);

Pre

(a))g

= (

m Pre

(a))X

a 0

6=a

ff(

Pre

(a))(a)p(

Pre

(a);

Pre

(a0)) f(

Pre

(a0))p(

Pre

(a0);

Pre

(a))g

Eq.(6)

= 0:

FIGURE 5. Derivations of Theorem 2

property (Equations (4)). The substitution of Φ(·)πf(·) and the expression of the rates (1) into the group-local- balance equations yields the derivations that are shown in Figure 5. This proves the theorem.

Conventionally “product form” has been associated with the equilibrium solution of Jackson queueing net- works which involves a product over the nodes of the queueing network. In the following it is shown how Jackson networks and their solution can be derived as a special case of the above results. Theorem 2 also gives a product form solution. The product in this case is

“hidden” in the function πf. This function is usually difficult to obtain from Equation (9). In the following we present some examples where this function is derived by analysing the “structure” of the PEPA system.

5. EXAMPLES

Example 5. Simple Jackson network (with ran- dom order service policy and infinite server semantics).

Consider the Jackson network depicted in Figure 6, where α, 1 − α denote the routing probabilities that a customer goes from station 1 to station 2 and from station 1 to station 3, respectively. A PEPA compo- nent that models the behaviour of a customer inside this queueing network is

Q1

def= (a01, r01).Q2+ (a001, r001).Q3, Q2 def

= (a2, r2).Q1, Q3 def

= (a3, r3).Q1,

where aiis the action representing the service at station i, r01+ r100= µ1, r0r10

1+r001 = α, r0r001

1+r001 = 1− α, r2= µ2, and r3 = µ3. If in the network there are N customers the PEPA system can be defined as

QNdef= Q|1||Q1{z|| . . . ||Q1}

N times .

The equivalence vector of the model compo- nent QN corresponding to one of the derivatives of the strong equivalence class {QNi} is a triple mi = (m1i, m2i, m3i), where mhi, with 1 ≤ h ≤ 3, is the number of derivatives in {QNi} that behave as Qh. For instance if the state vector of the derivative QNiis (Q1i, Q2i, . . . , QNi), such that Qki = Q1, for any 1 ≤ k ≤ N, then the equivalence vector representation of this state is mi= (N, 0, 0).

The pre- and the post-sets of the actions of this ex- ample are summarised in the table below.

action pre-set post-set a01 {Q1} {Q2} a001 {Q1} {Q3} a2 {Q2} {Q1} a3 {Q3} {Q1}

(9)

Note that since P re(a01) = P re(a001) we use P re(a1) to denote pre-set of a01 and a001.

It is easy to see that the PEPA component QN satis- fies Assumption 1 and hence there is a positive solution for the traffic equations (8). A solution to these equa- tions must satisfy the following equations

f (P re(a1))(r01+ r001) = f (P re(a2))r2+f (P re(a3))r3, f (P re(a2))r2 = f (P re(a01))r01,

f (P re(a3))r3 = f (P re(a001))r100.

We can easily verify that f (P re(a))(r01 + r100) = 1, f (P re(a2))r2 = α, and f (P re(a3))r3 = 1− α is a solution to these equations. A function πf given by

πf(m) = Y3 i=1

f (P re(ai))mi

satisfies Equation (10) for all m∈ ads(QN) and hence the equilibrium distribution for the PEPA system is

π(m) = 1 GΦ(m)

Y3 i=1

f (P re(ai))mi.

1

1

2 3



1



2



3

FIGURE 6. Jackson queueing network

Example 6. Queueing network with finite buffer capacity (with random order service policy and infinite server semantic).

Consider the queueing network depicted in Figure 7.

In this network station 3 has a buffer with finite capac- ity. It is well known that, in general, blocking prevents product form solution as it destroys the local balance property. It is worth noting that there are particu- lar blocking situations that preserve local balance and hence the product form solution (see (van Dijk, 1993) for details). In the network of Figure 7, if the cus- tomers are blocked when the buffer of station 3 is full, the network has product form solution. A PEPA com- ponent that models the behaviour of a customer inside

1 2



2

3



3



1

FIGURE 7. Queueing network with a finite capacity buffer

the queueing network of Figure 7 is Q1 def

= (a1, r1).Q2, Q2

def= (a2, r2).Q3

Q3 def

= (a3, r3).Q1,

while the PEPA component that models a position in the buffer is

Buf0 def= (a1, >).Buf0+ (a2, >).Buf00, Buf00 def= (a3, >).Buf0.

If in the queueing network there are N customers and the buffer of station 3 can contain up to M customers then the PEPA system that models the queueing net- work of Figure 7 (with random order service policy) is

BLdef= (Q1||Q1|| . . . ||Q1)

| {z }

N times

><

{a1,a2,a3}

(Buf0||Buf0|| . . . ||Buf0)

| {z }

M times

.

The state vector of BL as derivative BLi is the vector (Q1i, . . . , QNi, Buf1i, . . . BufMi). Given the current derivative of the component Qh, i.e., Qhi

(1 ≤ h ≤ N) the current derivatives of the compo- nents Bufk (1 ≤ k ≤ M) can be inferred. Hence the sequential components Bufk are redundant (see Def- inition 4) and the state vector can be represented as (Q1i, . . . , QNi).

For this PEPA system we have that action pre-set post-set

a1 {Q1, Buf0} {Q2, Buf0} a2 {Q2, Buf0} {Q3, Buf00} a3 {Q3, Buf00} {Q1, Buf0}

Thus the system satisfies Assumption 1 and hence there is a positive solution for the traffic equations. It is easy to check that f (P re(ai))ri= 1, from which we can derive that f (P re(ai)) = 1/ri, for 1≤ i ≤ 3.

The equivalence vector representation is mi = (m1i, m2i, m3i), where mhi (1 ≤ h ≤ 3) is the number of derivatives in {BLi} that behave as Qh. A function πf given by

πf(m) = Y3 i=1

f (P re(ai))mi

(10)

satisfies Equation (10) for all m∈ ads(QN) and hence the equilibrium distribution for the PEPA system is

π(m) = 1 GΦ(m)

Y3 i=1

f (P re(ai))mi.

Example 7. The taxi station system.

market garden

taxi station

customer

taxi

walk

taxi run FIGURE 8. Taxi station system

Consider the system depicted in Figure 8. In this system there are a given number of customers and a another one of taxis. If there is an available taxi in the taxi station a customer has two possibilities. He/she can take a taxi to go to the market. The taxi waits for the customer to complete the visit to the market and then it brings the customer back to the taxi station, becoming therefore available to other people. In Figure 8 this pos- sibility is represented by the right cycle. The customer can also choose to walk through the garden and then to go back to the taxi station (left cycle of Figure 8).

If there are no taxis in the taxi station a customer can only walk.

A PEPA component that models the behaviour of a customer inside the system depicted in Figure 8 is

C1

def= (a1, r1).C2+ (a3, r3).C3, C2

def= (a2, r2).C1

C3 def

= (a4, r4).C1,

while the PEPA component that models the behaviour of a taxi is

T1

def= (a3, >).T2, T2 def

= (a4, >).T1.

A taxi station system in which there are two customers and one taxi is modelled by

T S def= (C1||C1)

><

{a3,a4}(T1) .

The state vector of the model component T S as derivative T Si is the vector (C1i, C2i, T1i). The

equivalence vector representation is a five-tuple mi = (m1i, m2i, m3i, m4i, m5i), where the meaning of the components can be resumed by the following table

component number of components mi in T Si that behave thus

m1i C1

m2i C2

m3i C3

m4i T1

m5i T2

From the structure of T S we can observe that the last component of the vector mi is redundant.

The pre- and the post-sets of the actions of T S are action pre-set post-set

a1 {C1} {C2} a2 {C2} {C1} a3 {C1, T1} {C3, T2} a4 {C3, T2} {C1, T1}

It is possible to see that the PEPA component T S sat- isfies Assumption 1 and hence there is a positive so- lution to the traffic equations. We can observe that the routing chain contains two irreducible sets of states

{

{P re(a1), P re(a2)} , {P re(a3), P re(a4)}

}

. A so-

lution to the traffic equations must satisfy f (P re(a1))r1 = f (P re(a2))r2, f (P re(a2))r2 = f (P re(a1))r1, f (P re(a3))r3 = f (P re(a4))r4, f (P re(a4))r4 = f (P re(a3))r3.

We can easily verify that f (P re(ai))ri= 1 is a solution to these equations and hence f (P re(ai)) = 1/ri, for 1≤ i ≤ 4. A function πf given by

πf(m)=

f (P re(a1)) f (P re(a3))

m1

f (P re(a2)) f (P re(a4))

f (P re(a1)) f (P re(a3))

m4

=

r3

r1

m1 r4

r2

r3

r1

m4

satisfies Equation (10) for all m ∈ ads(T S) and hence the equilibrium distribution for the the PEPA system is

π(m) = 1 GΦ(m)

r3

r1

m1 r4

r2

r3

r1

m4 .

6. CONCLUSIONS AND FURTHER WORK We have introduced some basic ideas for finding equi- librium distributions based on “syntactic” analysis of a SPA model rather than on state space analysis. Sev- eral issues have yet to be addressed. We need for in- stance to find a method to compute the function πf(·) (Equation 9) as well as to derive efficient algorithms to compute the normalisation constant (Equation 10).

The solution of these problems will provide a way to compute performance measure for a class of SPA models without analysing the state space.

figura

Updating...

Riferimenti

Updating...

Argomenti correlati :