Mathematical and Computer Modelling 49 (2009) 14361448

Contents lists available at ScienceDirect

Mathematical and Computer Modelling

journal homepage: www.elsevier.com/locate/mcm

Colored stochastic Petri nets for modelling and analysis of multiclass

retrial systems
Nawel Gharbi a, , Claude Dutheillet b , Malika Ioualalen a
a
Department of Computer Science, University of Sciences and Technology USTHB, BP. 32 El Alia 16111 Algiers, Algeria
b
LIP6, University Pierre et Marie Curie, 104 avenue du Prsident Kennedy, 75016 Paris, France

article info a b s t r a c t

Article history: Most retrial models assume that customers and servers are homogeneous. However,
Received 9 March 2008 multiclass (or heterogeneous) retrial systems arise in various practical areas such as
Received in revised form 31 October 2008 telecommunications and cellular mobile networks. Multiclass models are far more difficult
Accepted 12 November 2008
for mathematical analysis than single class ones. So, explicit results are available only in
few special cases. Actually, so far multiclass retrial systems have been analyzed only by
Keywords:
means of queueing theory and almost all studies consider models with several customers
Finite source multiclass retrial systems
Heterogeneous customers
classes and a service station consisting in one single server or multiple homogeneous
Heterogeneous servers (identic) servers and an infinite population size. In this paper, we propose an approach for
Colored generalized stochastic Petri nets modelling and analyzing finite-source retrial systems with several customers classes and
Modelling servers classes using the Colored Generalized Stochastic Petri Nets (CGSPNs). This high-
Performance measures level mathematical model is appropriate for describing and analyzing the performance
of systems exhibiting concurrency and synchronization, possibly with heterogeneous
components. Using a high-level formalism makes the description of the system easier,
while preserving the possibility of obtaining exact performance results. We show how
the main steady-state performance indices can be derived and we analyze the behaviour
of heterogeneous retrial systems under two service disciplines. The numerical results are
graphically displayed to illustrate the effect of system parameters and service discipline on
the mean response time.
2009 Elsevier Ltd. All rights reserved.

1. Introduction

Retrial systems (or systems with returning customers) arise naturally in many telecommunication and computer
networks. Over the last two decades, there has been a renewed interest on this topic, which is mainly explained by the
advances in telecommunication technology leading to the use of new facilities as repeat last number, ring back when
free, etc.
Retrial systems are characterized by the feature that arriving customers who find all servers busy join a retrial group
called the orbit, to try again for their requests in random order and at random intervals. For a comprehensive review of the
main results and literature on this topic, the interested reader is referred to the surveys papers by Kulkarni and Liang [1],
Artalejo and Falin [2], the monograph by Falin and Templeton [3] and the bibliographical information given by Artalejo [4,5].
Most retrial systems assume that the input process is homogeneous from the point of view of customer characteristics
such as the arrival time, the service time and the inter-retrial time distributions. In practice, however, these characteristics
may differ widely for different customer types. This leads us to multiclass retrial systems, which arise in various practical

Corresponding author.
E-mail address: [email protected] (N. Gharbi).

0895-7177/$ see front matter 2009 Elsevier Ltd. All rights reserved.
doi:10.1016/j.mcm.2008.11.006
 N. Gharbi et al. / Mathematical and Computer Modelling 49 (2009) 14361448 1437

areas as telecommunication networks, telephone switching systems and digital cellular mobile networks. However,
multiclass models are far more difficult for mathematical analysis than single class models. So, explicit results are available
only in few special cases. For a complete survey on retrial models with two types of customers (K = 2), see [69].
Multiclass retrial queueing systems with K 2 were investigated by some researchers as Falin [10], Grishechkin [11]
and Langaris [12]. However, in all these papers, only the single server models with infinite population were considered.
On the other hand, finite-source retrial systems with heterogeneous sources were studied in [1315] for single server case
and in [16] for multiple homogeneous (identic) servers case. In fact, the investigated models in all these articles correspond to
multiclass retrial queues where each customers class (or source) is limited to one customer and the service station consists
of one server or multiple homogeneous servers.
Retrial models with several heterogeneous servers are still an interesting topic, even in homogeneous customers case.
In fact, we have found in the literature only the few papers of Efrosinin [17] and Sztrik [18,19] in which retrial queues with
homogeneous customers and heterogeneous servers were considered. To the best knowledge of the authors, there is no
paper on retrial systems with several classes of customers and classes of servers. Hence, the aim of this paper is the analysis
of finite-source multiclass retrial systems. Indeed, in many practical situations, it is important to take into account the fact
that the rate of generation of new primary calls decreases as the number of customers in the system increases. This can be
done with the help of finite-source models or quasi-random models, where each individual source generates its own flow of
primary demands. Retrial models with finite-source [20,31] are recent interest in modelling magnetic disk memory systems,
hybrid fiber-coax [21], cellular mobile networks [22,9] and local-area networks with non-persistant CSMA/CD protocols [23].
Multiclass retrial systems are usually analyzed by queueing theory. Petri net formalisms are never seen in this area.
However, the colored generalized stochastic Petri nets (CGSPNs) [24,25] have shown to be a very effective mathematical
model, appropriate for describing and analyzing performance of parallel systems with heterogeneous components and that
exhibit concurrency and synchronization. Moreover, this model allows to obtain performance indices either with analytic
means or by numerical algorithms.
The objective of this paper is to present a method for modelling and evaluating performances of finite-source multiclass
retrial systems using the colored generalized stochastic Petri nets model. The customers (servers resp.) are grouped in
classes, that is the customers (servers resp.) of a given class have the same parameters. Hence, we show how the behavior
of these rather complicated retrial systems can be intuitively described with CGSPNs model, and how several exact
performance indices can be derived for the two service policies: Random Server and Fastest Free Server disciplines.
The proposed approach allows to obtain several benefits. In particular, it offers the possibility of using optimal methods,
results and tools developed within the CGSPNs framework. On the other hand, the advantage of the use of CGSPNs is the fact
that it is a high-level stochastic model which allows the explicit representation of conditional choices and synchronization
and also to reduce the complexity of models with respect to other stochastic formalisms.
The modelling and the analysis of retrial systems using the Petri nets formalism was introduced initially by Gharbi
in [26], for the single server retrial systems with homogeneous customers. The approach was next applied for retrial systems
with multiple non-reliable servers [27]. In both investigations, the formalism used was the generalized stochastic Petri
nets (GSPNs) [28]. The purpose of this paper is to generalize the model and the analysis of [27,18,19,16]. The novelty of
the investigation is the combination of several customers classes, servers classes and the different service policies with
essentially the use of colored generalized stochastic Petri nets.
The paper is organized as follows: in Section 2, we describe the mathematical model of finite-source multiclass retrial
systems considered. In Section 3, the basics of CGSPNs are reviewed. Section 4 presents the CGSPN models describing
multiclass retrial systems under the different service policies. Performance indices are derived in Section 5. Next, several
numerical calculations are carried out using the efficient software tool GreatSPN. The results are graphically displayed with
some comments and discussions. Finally, we give a conclusion.

2. Mathematical model

We consider retrial systems with a finite source (population) of potential customers divided in n classes (n 1). Each
class i (1 i n) contains ki homogeneous customers, from the point of view of arrival time, service time and inter-retrial
time distributions. All or some of these characteristics may change for different classes. Each customer is either free, under
service or in orbit at any time. The primary requests of free customers of class i arrive to the system according to the so
called quasi-random input stream with rate i . Hence, a free customer of class i, can generate at time t, a primary request
for service in any interval (t , t + dt ) with probability i (ki xi )dt + o(dt ) as dt 0, where ki is the population size of class
i and xi is the number of class i customers in the system.
The service station consists of m classes of servers (m 1). Each class j (1 j m) contains sj identical servers. There
are two possible states for a server: idle or busy. If there is an idle server at the moment a customer request arrives, then the
service starts immediately. The customer becomes under service and the server becomes busy. Each customer request
must be served by one and only one server.
In this paper, we consider two different service policies, namely Random Server discipline and Fastest Free Server discipline.
In the case of Random Server discipline, the server to which a request is assigned is chosen randomly among all idle servers,
whatever their class, whereas in the Fastest Free Server case, the availability of servers is always examined according to a
decreasing order of service speeds. The service times of class i customers are independent and exponentially distributed
1438 N. Gharbi et al. / Mathematical and Computer Modelling 49 (2009) 14361448

with rate i,j if a server of class j is servicing a customer of class i. After service completion, the customer becomes free, so
it can generate new primary calls, and the server becomes idle again. Otherwise, if all the servers are busy at the arrival of a
call, the customer (of the ith class) joins the orbit and starts generation of a flow of repeated calls exponentially distributed
with rate i , until he finds one free server. We assume that all customers are persistent in the sense that they keep making
retrials until they receive their requested service.
As usual, we assume that the arrival, service and inter-retrial times are mutually independent of each other.

3. An overview of colored generalized stochastic Petri nets

Generalized Stochastic Petri nets (GSPNs) [28] are a graphical and mathematical model suitable for describing
and analyzing systems that are characterized as being concurrent, asynchronous, distributed, non-deterministic and/or
stochastic. Provided that the transitions of the model have an exponentially distributed firing delay, the reachability graph of
a model is isomorphic to a Markov chain. If immediate transitions are added, the model becomes semi-Markovian, however
an embedded Markov chain can be extracted and a steady-state distribution can be computed if the system is ergodic.
However, two classical problems arise when applying the GSPNs formalism to complex systems. The first one is the
complexity of the model itself, when the number of entities it is made of increases. To cope with this difficulty, higher-level
nets have been introduced.
Among the various models, we focus on Colored Petri Nets (CPNs) [29]. In this model, colors are added to the objects
representing the system components, thus making it possible to fold the representation without losing information on
which component executes an action. The identification of the active entity is done by means of color functions that label
the arcs of the model. Color functions can be complex, yet there are several advantages in allowing only a restricted set of
simple functions in the model. On the one hand, the complexity of the function should not hide the complexity of the system:
the main features of the system, such as fork/join, must remain visible. An easy way to reach this goal is to use only simple
symmetrical functions, i.e., functions that apply identically to all the elements of a class of colors. This approach has been
used in [24] and we will show that it is suitable for modelling and analyzing multiclass retrial systems with several types
of servers. On the other hand, adding constraints on the functions makes it possible to develop analysis techniques that still
take advantage of the structure of the model, which would be lost with complex functions. Last but not least, experience
shows that most systems can be represented in a rather intuitive way by using only a very small set of functions.
The second and very usual problem when dealing with complex systems is the size of the generated states spaces. This
can make the complete analysis of the system impossible. Fortunately, as we already mentioned, CGSPNs offer a possibility
of coping with this problem by taking advantage of the symmetries of the system, if any. In particular, if the timing of the
system also verify some symmetry property, a lumped Markov chain can be automatically derived from the model [25].
For the definition of CGSPNs model, we start by giving some basic concepts.

Definition 1. A multiset a over non-empty set A is a mapping a [A N]. Intuitively, P a multiset is a set that can contain
several occurrences of the same element. It can be represented by a formal sum: a = xA a(x).x.
a(x) is the number of occurrences of x in a. We denote by 0 the empty multiset, i.e., x A, 0(x) = 0. Bag (A) is the set of
multisets over A.
A CGSPN is a bipartite graph whose nodes are places (drawn as circles) and transitions. Transitions can be either timed
(represented by rectangles) or immediate (represented by thin bars).
Timed transitions describe the execution of time consuming activities. In this paper, we consider Markovian models,
where the firing delays of timed transitions are exponentially distributed;
Immediate transitions model the activities whose duration is negligible with respect to the time scale of the problem,
such as synchronization or choice. They have priority over timed transitions and fire in zero time, once they are enabled.
Places can contain tokens. Places, together with the distribution of tokens among them, play the role of describing
the system state, while transitions represent events that cause state changes. In CGSPNs, a token can incorporate some
information, indeed a token can be regarded as an instance of a data structure with a certain number of fields, whose
semantics depends on the place the token belongs to. The definition of the data type associated with each place is called
place color domain. The data type fields are selected from a set of basic types called basic color classes. The specification
of the basic color classes is part of the net definition.
For instance, a place can represent the assignment of a client to a server. The basic color classes involved are the
set of clients C and the set of servers S. The place color domain will be C S and a token in the place will be a tuple
hci , sj i, ci C , sj S, meaning that client ci has been assigned to server sj . The color domain of a place p is denoted C (p).
Color classes can be finite or infinite. In this paper, we consider only color classes with finite cardinality which can be
defined by enumeration of the elements.
A state of the system is represented by a distribution of colored tokens among places, which is called a marking. The
initial distribution is denoted M0 . For a marking M, M (p) is a multiset over C (p), that is, M (p)(c ) represents the number of
tokens of color c C (p) that place p contains when the marking is M.
Transitions in CGSPNs can be considered as procedures with formal parameters. The formal parameter types define the
transition color domain; their declaration is part of the net description and the type associated with each parameter must
 N. Gharbi et al. / Mathematical and Computer Modelling 49 (2009) 14361448 1439

be a basic color class. Hence, like for places, the color domain of a transition is a Cartesian product of basic color classes. The
color domain of transition t is denoted C (t ).
A transition whose formal parameters have been instantiated to actual values is called transition instance. We use
notation [t , c ] for an instance of transition t, where c C (t ) represents the assignment of actual values to the transition
parameters.
In CGSPNs, a priority structure is defined over transitions as was originally defined for GSPNs. Timed transitions have
priority 0, whereas immediate transitions have positive priorities. Different immediate transition instances may have
different priorities, however the default value is 1 for every instance.
Arcs are labelled by color functions that map a color instance of a transition onto a multiset of colored tokens. Color
functions are used to decide whether a transition is enabled in a marking, meaning that the action it represents can take
place in the current state of the system. If so, color functions also determine the effect of the transition firing on the marking.
We summarize these features in the following definition:

Definition 2. Colored generalized stochastic Petri nets [24]

Formally, a colored generalized stochastic Petri net CGSPN,
CGSPN = hP , T , CB, C , W , W + , W h , Pri, M0 , i, is made of:
P the finite set of places;
T the finite set of timed and immediate transitions, P T = , P T 6= ;
CB the family of basic color classes: CB = {C1 , . . . , Cn } with Ci Cj = ;
C is a function on P T that associates with any node r a color domain C (r ) which is a Cartesian product of elements of
CB;
W , W + , W h : W (p, t ), W + (p, t ), W h (p, t ) [C (t ) Bag (C (p))] are color functions that respectively label the
input, output and inhibitor arcs between transition t and place p;
Pri the priority function is defined as follows: t T , Pri(t ) : C (t ) N. Pri(t )(c ) is the priority of color instance [t , c ];
M0 is the initial marking which describes the initial state of the system: Q p P , M0 (p) Bag (C (p));
is a function defined on the set of transitions T such that (t ) : C (t ) ( pP Bag (C (p))) R+ is the timing function
of the model.

3.1. Semantics of CGSPN

3.1.1. Untimed semantics

For a transition instance [t , c ] to be enabled in a marking M, there are several conditions to fulfill:
for any input place p of the transition and for any color cp of C (p), the number of tokens of color cp in p must be greater
or equal to the number of tokens required by the firing: M (p)(cp ) W (p, t )(c )(cp )
for any inhibitor place p of transition t (inhibitor arcs are circle-headed) and for any color cp of C (p), the number of tokens
of color cp in p must be less than the number of tokens determined by the inhibitor function: M (p)(cp ) < W h (p, t )(c )(cp )
there is no transition instance with higher priority than [t , c ] that fulfills the two preceding conditions.
The enabling of transition instance [t , c ] in marking M is denoted by M [t , c i.
If a transition instance [t , c ] is enabled in a marking M, it can fire and modify the state of the system, leading to a new
marking M 0 . The firing is denoted by M [t , c iM 0 and M 0 is computed by removing tokens from input places and adding tokens
to output places according to color functions:
p P , cp C (p), M 0 (p)(cp ) = M (p)(cp ) W (p, t )(c )(cp ) + W + (p, t )(c )(cp ).
A marking M is said to be reachable if there exists a sequence of transition instance firings starting in the initial marking
M0 and leading to M.
If the state space is finite, the complete behavior of the system can be represented by means of a reachability graph. The
reachability graph is a graph whose nodes are reachable markings. There is an arc from M to M 0 iff there exists a transition
instance [t , c ] such that M [t , c iM 0 .

3.1.2. Timed semantics

Thanks to the priority assignment policy, the association of an exponential or zero delay with every transition does not
modify the set of reachable states. In fact, it has been shown [24] that the reachability graph of such models is isomorphic
to a semi-Markov process.
Disregarding time and only considering state changes, an embedded Markov chain can be extracted from this process.
The probability associated with state change M [t , c iM 0 is given by:
(t )(c , M )
.
(t 0 )(c 0 , M )
P
M [t 0 ,c 0 i
1440 N. Gharbi et al. / Mathematical and Computer Modelling 49 (2009) 14361448

Fig. 1. CGSPN model of finite-source multiclass retrial systems.

For any transition instance [t , c ], (t )(c , M ) defines the mean firing delay for instance [t , c ] in marking M, if t is a timed
transition, and the weight of instance [t , c ] in marking M, if t is immediate.
If the system is ergodic, a steady-state solution of the Markov chain can be computed, from which the steady-state
probabilities of the original process can be retrieved.
Based on the steady-state solution, several performance indices can be computed. In a colored stochastic Petri net, such
indices are the distribution of colored tokens in places, the mean throughput of transition instances or the response time
of a subnet. It should be clear that relevant performance indices always relate to the number of tokens of a given color. For
instance, we are interested in computing the response time of a customer of a given class.

4. Colored stochastic models of multiclass retrial systems

In this section, we present a method for modelling and analyzing finite-source multiclass retrial systems with several
types of customers and servers, using colored generalized stochastic Petri nets (CGSPNs). We show that the two service
disciplines we mentioned in the introduction can be represented by almost similar models.

4.1. Random Server discipline

Fig. 1 shows the CGSPN model with Random Server discipline.

In the retrial systems that we study, we can distinguish several classes of customers and classes of servers. However,
customers (resp. servers) of a given class have the same behavior. Hence, we do not need to distinguish elements that
belong to the same class, for which we associate the same color.
In the model that we propose, place Cus Free contains the free (potential) customers. The firing of transition Arriv al for
some instance c means that a customer of class c has issued a request. This firing transfers a token c from place Cus Free to
place Choice. If some server is available (place Ser Idle is not empty), then transition Begin Ser v is enabled and the token
that arrives in place Cus Ser v bears a double information: the class of the customer and the class of the server it has been
assigned to.
When the service of a customer of class c by a server of class r is completed, transition Ser v ice fires, a token with color c
is put back in place Cus Free and a token with color r is put back to place Ser Idle.
If there is no server available at the arrival time of the request, transition Go Orbit can fire and the token representing
the requesting customer is moved to place Orbit. After some time, the customer will repeat its request by firing transition
Retrial and it will be sent again to place Choice.
More formally, the n classes of customers (n 1) and the m classes of servers (m 1) are represented by two basic
color sets C and R:

C = {c1 , c2 , . . . , cn }
R = {r1 , r2 , . . . , rm }.

The color domain of each place is directly derived from the type of elements that the place can contain:

C (Cus Free) = C (Orbit ) = C (Choice) = C ;

C (Ser Idle) = R;
C (Cus Ser v) = C R, as this place contains compound elements.
 N. Gharbi et al. / Mathematical and Computer Modelling 49 (2009) 14361448 1441

Let us denote by ki the number of customers of class i. They will be represented by ki tokens of color ci , all of which are
initially present in place Cus Free. Similarly, the sj servers of class rj are represented by tokens that are initially in place
Ser Idle.
We thus have the following initial marking:
M0 (Cus Free) = k1 .c1 + k2 .c2 + + kn .cn
M0 (Ser Idle) = s1 .r1 + s2 .r2 + + sm .rm
M0 (Choice) = M0 (Orbit ) = M0 (Cus Ser v) = 0
Pn Pm
We will use: K = i=1 ki to denote the overall population size, and SV = i=1 si for the total number of servers.
The color domain of transitions determines which variables should be instantiated when performing the action
represented by the transition. For instance, transition Arriv al only requires to identify the class of the requesting customer,
hence C (Arriv al) = C . But, when firing transition Begin Ser v , we need to select a class of customers and a class of servers,
hence C (Begin Ser v) = C R.
The color functions labeling the arcs specify the action of the transition on the marking of the neighboring places. The
color functions that we use in this model are defined as follows:
X (resp. Y ) is a projection function on the first (resp. second) component of a color instance. Hence, if C (t ) = C , then
c C (t ), X (c ) = c. Whereas, if C (t ) = C1 C2 then (c1 , c2 ) C (t ), X (c1 , c2 ) = c1 and Y (c1 , c2 ) = c2 .
Straightforwardly, hX , Y i(c1 , c2 ) = (c1 , c2 ).
S is a constant synchronization function that gathers all elements belonging to the color domain of place Ser Idle:
c C (Go Orbit ), S (c ) = r1 + + rm .

As function S labels an inhibitor arc, the enabling of transition Go Orbit for color c in marking M, requires that ri
R, M (Ser Idle)(ri ) < S (c )(ri ). As ri R, S (c )(ri ) = 1, then the transition is enabled only if place Ser Idle is empty.
Rates of transitions can be parameterized on the color of the entity crossing the transition. This mechanism allows
different arrival or retrial rates depending on customer type. Also, service times depends on customer and server types.
The firing of transition Arriv al indicates the arrival of a primary call. Its service semantics is infinite server semantics,
because all free customers are able to generate primary requests. The firing rate i of this transition depends on the
customer color that generates the call. At the arrival of the request, if place Ser Idle contains at least one idle server of
any type, immediate transition Begin Ser v fires. Hence, the customer starts to be served and the server moves into busy
state. However, if the arriving customer of color ci finds no idle server of any type, immediate transition Go Orbit fires and
the customer joins place Orbit. Once there, he starts generating a flow of repeated calls exponentially distributed with rate
i . The firing of transition Retrial represents the arrival of a repeated call from the orbit. As the customers in the orbit can
independently generate repeated calls for service, transition Retrial should have infinite server semantics.
When timed transition Service fires, the customer under service returns to the free state (place Cus Free) and the server
becomes idle and ready to serve another customer (place Ser Idle). The service semantics of transition Service is also infinite
server semantics, because several servers can work simultaneously. Moreover, the rate i,j of this transition depends on
customer color and also on the color of the used server.

4.2. Fastest Free Server discipline

The model depicted in Fig. 1 corresponds to Random Server discipline, in which a request is randomly assigned to any free
server. In the Fastest Free Server, case, the idleness of servers is always examined according to a decreasing order of speeds.
Hence, to model the Fastest Free Server discipline, we assume that in server class R = {r1 , r2 , . . . , rm }, servers of color rj
are faster that those of color rq , j < q. Then the representation of Fastest Free Server discipline is done by modifying the
priority function for transition Begin Ser v as follows:
hci , rj i C (Begin Ser v), j, q, j < q,
Pri(Begin Ser v)(hci , rj i) > Pri(Begin Ser v)(hci , rq i).
Now, a customer will be assigned a free server of color r1 if any. Otherwise, the customer checks for a server of color r2 , and
so on. However, if j, 1 j m, all the servers of color rj are busy, the customer joins place Orbit.

5. Stochastic analysis

In this section, we show how the CGSPN models that we propose can be used to easily obtain the main steady-state
performance indices of multiclass retrial systems.
The reachability graphs of these models are finite and strongly connected. Hence, the underlying Markov processes are
ergodic and the steady-state distribution exists and is unique.
The solution of a process at steady-state is the probability distribution vector = (1 , 2 , . . . , n ), where i denotes
the steady-state probability that the process is in state Mi . can be computed by applying the embedded Markov chain
resolution algorithm [24].
1442 N. Gharbi et al. / Mathematical and Computer Modelling 49 (2009) 14361448

Having the stationary probability distribution , several performance measures of multiclass retrial systems with several
types of servers can be derived as follows:
The mean number of free customers of type i (n(Fi) ):
This corresponds to the mean number of tokens of color ci in place Cus Free.
(i)
X
nF = Mj (Cus Free)(ci ).j (1)
j:Mj RS

where Mj (Cus Free)(ci ) is the number of tokens of color ci in place Cus Free when the marking is Mj and the sum is over
all the tangible markings of the reachability set (RS).
Hence, the mean number of free customers nF is given by:
n
(i)
X
nF = nF (2)
i =1

The mean number of customers of type i in the orbit (n(Oi) ):

This corresponds to the mean number of tokens of color ci in place Orbit.
(i)
X
nO = Mj (Orbit )(ci ).j (3)
j:Mj RS

where Mj (Orbit )(ci ) is the number of tokens of color ci in place Orbit when the marking is Mj .
Hence, the mean number of customers in the orbit nO is given by:
n
(i)
X
nO = nO (4)
i=1

The mean number of customers of type i under service (n(Si) ):

This corresponds to the mean number of tuples hci , rk i in place Cus Ser v , rk being any server color.
(i)
X X
nS = Mj (Cus Ser v)(hci , rk i).j
j:Mj RS rk R

= ki (nF(i) + n(Oi) ) (5)

Mj (Cus Ser v)(hci , rk i) is the number of tuples in place Cus Ser v where a customer of class ci is assigned to a server of
class rk when the marking is Mj . The first sum is over all reachable tangible markings and the second one is over the types
(colors) of servers.
Hence, the mean number of customers under service nS is given by:
n
(i)
X
nS = nS = K (nF + nO ) (6)
i =1

where K is the population size.

The mean number of customers of type i in the system (n(i) ):
This represents the mean number of customers of color ci under service or in the orbit.
(i) (i) (i)
n(i) = nS + nO = ki nF . (7)
Hence, the mean number nc of customers in the system is given by:
n
n(i) = K nF
X
nc = (8)
i=1

The mean number of idle servers of type k (n(I k) )

This corresponds to the mean number of tokens of color rk in place Ser Idle.
(k)
X
nI = Mj (Ser Idle)(rk ).j (9)
j:Mj RS

where Mj (Ser Idle)(rk ) is the number of tokens of color rk in place Ser Idle when the marking is Mj .
Hence, the mean number of idle servers nI is given by:
m
(k)
X
nI = nI (10)
k=1
 N. Gharbi et al. / Mathematical and Computer Modelling 49 (2009) 14361448 1443

The mean number of busy servers of type k (n(Bk) )

This corresponds to the mean number of tuples of color hci , rk i in place Cus Ser v .
(k)
X X
nB = Mj (Cus Ser v)(hci , rk i).j
j:Mj RS ci C

= sk n(I k) (11)
Mj (Cus Ser v)(hci , rk i) is the number of tuples in place Cus Ser v where a customer of class ci is assigned to a server of
class rk when the marking is Mj . sk is the total number of servers of type k.
Hence, the mean number of busy servers nB is given by:
m
(k)
X
nB = nB = SV nI (12)
k=1

where SV is the total number of servers.

Utilization of servers of type k by customers of type i(U (i,k) )
This corresponds to the mean number of tokens of color hci , rk i in place Cus Ser v .

U (i,k) =
X
Mj (Cus Ser v)(hci , rk i).j . (13)
j:Mj RS

The mean generation rate of primary calls of type i (i )

It represents the throughput of transition Arriv al with respect to color ci .
X
i = Mj (Cus Free)(ci ).i .j . (14)
Mj RS :Mj [Arriv al,ci i

where the sum is over markings that enable transition instance [Arriv al, ci ].
Hence, the mean generation rate of primary calls is given by:
n
X
= i . (15)
i =1

The mean generation rate of repeated calls by a customer of type i ( i ):

This represents the retrial frequency of customers of type i in the orbit. It corresponds to the throughput of transition
Retrial with respect to color ci .
X
i = Mj (Orbit )(ci ).i .j (16)
Mj RS :Mj [Retrial,ci i

where the sum is over markings that enable transition instance [Retrial, ci ].
Hence, the mean generation rate of repeated calls is given by:
n
X
= i (17)
i=1

The mean service rate of type i customers by servers of type k (i,k ):

This represents the throughput of transition Service with respect to customers of color ci and servers of color rk .
X
i ,k = Mj (Cus Ser v)(hci , rk i).i,k .j (18)
Mj RS :Mj [Ser v ice,hci ,rk ii

where the sum is over markings that enable transition instance [Ser v ice, hci , rk i].
The mean service rate of customers of type i(i ):
This represents the throughput of transition Service with respect to customers of color ci , whatever the type of the
server.
m
X
i = i ,k (19)
k=1

The mean service rate of servers of type k(k ):

This represents the throughput of transition Service with respect to servers of color rk , whatever the type of customer.
n
X
k = i,k (20)
i=1
1444 N. Gharbi et al. / Mathematical and Computer Modelling 49 (2009) 14361448

Availability of r servers of type k (A(rk) )(0 r sk ):

This corresponds to the probability that exactly r servers of color rk are idle.

A(rk) =
X
j (21)
j:Mj (Ser Idle)(rk )=r

Utilization of r servers of type k (Ur(k) )(0 r sk ):

(k)
The probability that at least r servers of color rk (1 r sk ), are servicing (Ur ) is given by:
sk r
(k)
Ur(k) =
X
Ai . (22)
i=0

Hence, the probability that at least one server of color rk is used is given by:

U (k) = 1 A(skk) . (23)

The probability that all servers of color rk are servicing is given by:
(k)
Us(kk) = A0 . (24)
(k,i)
The probability that at least one server of color rk is used by a customer of color ci (U ) is given by:
U (k,i) =
X
j (25)
j:Mj (Cus Ser v)(hci ,rk i)1

The mean waiting time of a customer of type i (W i ):

The mean waiting time W i of a customer of color ci in the steady state, can be easily obtained with the help of Littles
formula:
(i)
nO
Wi = (26)
i
The mean service time of a customer of color ci by a server of color rk (S i,k ):
1
S i,k = (27)
i,k
The mean response time of a customer of color ci served by a server of class rk (Ri,k ):
(i)
nO 1
Ri,k = W i + S i,k = + (28)
i i,k
The blocking probability of a primary customer of color ci (B(pi) ):
ki
x.i .Prob[Mj (Cus Free)(ci ) = x and Mj (Ser Idle) = 0]
P P
j:Mj RS x=1
(i)
Bp = . (29)
i
Hence, the blocking probability of primary customers:
n
1X
Bp = i .B(pi) (30)
i =1

The blocking probability of a repeated call of color ci (B(ri) ):

ki
x.i .Prob[Mj (Orbit )(ci ) = x and Mj (Ser Idle) = 0]
P P
j:Mj RS x=1
(i)
Br = . (31)
i
Hence, the blocking probability of customers in the orbit:
n
1X
Br = i .B(ri) (32)
i =1
 N. Gharbi et al. / Mathematical and Computer Modelling 49 (2009) 14361448 1445

Table 1
Parameters of systems with several classes of customers.
Servers number Sizes of sources
Source 1: 10 0.1
Fig. 2 4 x axis Source 2: 8 2 1
Source 3: 12 10
Source 1: 10 1
Fig. 3 4 0.5 Source 2: 8 5 x axis
Source 3: 12 10

Fig. 2. Mean response time versus primary calls generation rate.

The blocking probability of a customer of color ci (B(i) ):

B(i) = B(pi) + B(ri) . (33)
Hence, blocking probability B is given by:
n
B(i) .
X
B= (34)
i=1

6. Numerical results and discussions

In this section, we study the influence of system parameters, retrial phenomenon and service disciplines on the mean
performance measures of multiclass systems. To this end, we used the GreatSPN tool [30] version 2.0.2, both for the
description and the analysis of our colored GSPN models.
First, we present some examples to illustrate graphically the effect of the system main parameters on the mean response
time of retrial systems with several classes of customers and homogeneous servers. For an easier representation of graphs,
we consider 3 classes of customers. The parameters of the studied systems are given in Table 1.
In Fig. 2, the mean response time of customers of the three classes with different retrial rates, is displayed as a function
of primary calls generation rate.
From these curves, it can be seen that the mean response time increases with primary requests arrival intensity, but it
decreases as retrial intensity increases. Hence, the best performance is obtained by customers of the third class, which have
the highest retrial rate. On the other hand, we note that the mean response time increases rapidly with arrival rate, when
the retrial intensity is low. However, for high retrial rates, the mean response time increases slowly. For example, the mean
response time of customers of the first class ( = 0.1) is sixteen times more important when the arrival rate varies from 0.1
to 0.5, but for the third class of customers ( = 10), the evolution is around 50%.
Fig. 3 shows the influence of service and retrial rates on the mean response time. As can be expected, we see that
increasing the service rate improves the performance of the system. Hence, customers of the third class (3 = 10) have
the best (lowest) response times. Furthermore, it can be observed that the mean response time decreases rapidly as the
retrial rate increases when retrial intensity is low. But, when more and more repeated requests arrive, the decreasing is not
considerable.
We now consider systems with homogeneous customers and several classes of heterogeneous servers. We mainly
concentrate on the effect of system parameters and service discipline on the mean response time. In our example, we
consider that the first class consists in one server with rate 1 = 2, the second class consists in two servers with rate
2 = 5 and the third class consists in the three fastest servers with rate 3 = 8.
1446 N. Gharbi et al. / Mathematical and Computer Modelling 49 (2009) 14361448

Fig. 3. Mean response time versus retrial rate.

Table 2
Parameters of systems with several classes of servers.
K Class 1 Class 2 Class 3

Fig. 4 50 x axis 1 1:1 = 2 2:2 = 5 3:3 = 8

Fig. 5 50 1 x axis 1:1 = 2 2:2 = 5 3:3 = 8

Fig. 4. Mean response time versus primary calls generation rate.

The input parameters of the studied systems are collected in Table 2.

In Figs. 4 and 5, the mean response time is plotted versus the primary call generation rate and the retrial rate, respectively.
We have presented two curves in each figure, which correspond to the Random Server and the Fastest Free Server disciplines.
From these figures, we can see that the mean response time increases with an increasing rate of primary arrivals and a
decreasing intensity of repeated calls. In addition, the difference between the two service policies is clearly shown. As can
be expected, the results of Fastest Free Server discipline are always better than those of the Random Server discipline. This
is all the more obvious as the intensity of primary arrivals is high.
We finally consider totally heterogeneous retrial systems with 3 classes of customers having different retrial rates and 2
classes of servers (fast and low servers).
For the verification of the colored GSPN models proposed in our paper, we considered the case where customers of the
different classes have the same parameters (arrival and retrial rates) and all servers are homogeneous. That is, the service
rates are the same for all classes of servers. The obtained results were compared to the results generated by the Pascal
program given in the book of Falin and Templeton [3], since if all customers and servers are homogeneous, the measures
should approach the corresponding ones in multiserver retrial queues with single class of customers and identical servers.
Table 3 summarizes the results of our numerical experiments. As it was expected, we can see that the sums of the
corresponding performance measures of the different classes of customers and the different classes of servers of our colored
net are very close ('105 ) to the homogeneous retrial queue case. In addition, the results of the two service disciplines are
the same, because all servers are assumed to have the same service rate.
Now, we investigate the effect of system parameters and service disciplines on the mean response time of totally
heterogeneous retrial systems. To this end, we consider a system with one fast server (1 = 5) and two slow servers
 N. Gharbi et al. / Mathematical and Computer Modelling 49 (2009) 14361448 1447

Fig. 5. Mean response time versus retrial rate.

Table 3
Verifications in the homogeneous case.
Homogeneous case [3] Multiclass system
Random Server Fastest Free Server

Number of servers 4 1s1 + 3s2 1s1 + 3s2

Sizes of sources 20 10c1 + 6c2 + 4c3 10c1 + 6c2 + 4c3
Primary calls generation rate 0.1 0.1 (c1 , c2 , c3 ) 0.1 (c1 , c2 , c3 )
Service rate 1 1 (s 1 , s 2 ) 1 (s 1 , s 2 )
Retrial rate 1.2 1.2 (c1 , c2 , c3 ) 1.2 (c1 , c2 , c3 )
s1 : 0.521 866 s1 : 0.521 866
Mean number of busy servers 1.800748 s2 : 1.278 884 s2 : 1.278 884
Total: 1.800 750 Total: 1.800 750
c1 : 0.095 887 c1 : 0.095 887
Mean number of sources 0.191771 c2 : 0.057 532 c2 : 0.057 532
of repeated calls c3 : 0.038 355 c3 : 0.038 355
Total: 0.191 773 Total: 0.191 773
c1 : 0.900 374 c1 : 0.900 374
Mean rate of primary 1.800748 c2 : 0.540 224 c2 : 0.540 224
calls generation c3 : 0.360 150 c3 : 0.360 150
Total: 1.800 748 Total: 1.800 748
Mean waiting time 0.106495 0.106 496 0.106 496

Table 4
Mean response time of systems with heterogeneous customers and servers.
Class 1: 1 = 0.1 Class 2: 2 = 1 Class 3: 3 = 10
Random Fastest Random Fastest Random Fastest

0.01 0.355301 0.308448 0.354009 0.307421 0.353878 0.307320

0.05 0.493347 0.441976 0.376320 0.340948 0.364160 0.330612
0.1 1.100978 1.016795 0.446152 0.417840 0.377183 0.355165
0.5 15.443962 15.267005 1.925974 1.908168 0.590826 0.587176
1 41.000866 40.879087 4.426307 4.414946 0.843 833 0.842541
5 100.233382 100.207120 10.288084 10.285549 1.337306 1.336992
10 109.556050 109.536685 11.218722 11.216850 1.417344 1.417103

(2 = 2). The customers are partitioned into three classes with different retrial rates as follows: (k1 = 10, 1 = 0.1; k2 =
8, 2 = 1; k3 = 12, 3 = 10).
Table 4 illustrates the behavior of the mean response time as a function of the generation rate of primary calls for the
different classes of customers.
The results confirm our expectations with respect to service disciplines. Indeed, the Fastest Free Server discipline gives
the best performance, whatever the class of customers and for all values of primary arrival and retrial rates. It is also worth
noticing that the best response times correspond to the third class of customers, whose intensity of repeated calls is relatively
high. This coincide with the results obtained above in the previous examples.
On the other hand, it can be seen that the mean response times of the three classes of customers converge when the
generation rate of primary calls is low. However, when more and more primary requests arrive, the difference is more
significant. Hence, customers with low arrival rate and high retrial rate have the best mean response times, particularly
under the Fastest Free server discipline.
1448 N. Gharbi et al. / Mathematical and Computer Modelling 49 (2009) 14361448

7. Conclusion

In this paper, we proposed an approach for modelling and evaluating the performance of finite-source retrial systems
with several classes of customers and classes of servers, by means of the colored generalized stochastic Petri nets model.
We showed that this model makes the description of such systems easy and we conducted a complete performance
analysis, thus proving that colored Petri nets are suitable for analyzing complex systems like heterogeneous retrial systems
under Random Server discipline and Fastest Free Server discipline.
We now plan to extend this work to the investigation of unreliable multiclass retrial systems, in which servers are subject
to random breakdowns.

References

[1] V.G. Kulkarni, H.M. Liang, Retrial queues revisited, in: J.H. Dshalalow (Ed.), Frontiers in Queueing, CRC Press, Boca Raton, FL, 1997.
[2] J.R. Artalejo, G.I. Falin, Standard and retrial queueing systems: A comparative analysis, Revista Matematica Complutense XV (2002) 101129.
[3] G.I. Falin, J.G.C. Templeton, Retrial Queues, Chapman and Hall, London, 1997.
[4] J.R. Artalejo, A classified bibliography of research in retrial queues: Progress in 19901999, Top 7 (1999) 187211.
[5] J.R. Artalejo, Accessible bibliography on retrial queues, Mathematical and computer Modelling 30 (1999) 16.
[6] B.D. Choi, Y. Chang, Single server retrial queues with priority calls, Mathematical and Computer Modelling 30 (1999) 732.
[7] B.D. Choi, Y. Chang, B. Kim, MAP1, MAP2/M/c retrial queue with guard channels and its application to cellular networks, Top 7 (1999) 231248.
[8] B.D. Choi, Y. Chang, MAP1, MAP2/M/c retrial queue with the retrial group of finite capacity and geometric loss, Mathematical and Computer Modelling
30 (1999) 99113.
[9] P. Tran-Gia, M. Mandjes, Modeling of customer retrial phenomenon in cellular mobile networks, IEEE Journal on Selected Areas in Communications
15 (1997) 14061414.
[10] G.I. Falin, On a multiclass batch arrival retrial queue, Advances in Applied Probability 20 (1988) 483487.
[11] S.A. Grishechkin, Multiclass batch arrival retrial queues analyzed as branching processes with immigration, Queueing Systems 11 (1992) 395418.
[12] C. Langaris, E. Moutzoukis, Non-pre-emptive priorities and vacations in a multiclass retrial queueing system, Communications in Statistics Stochastic
Models 12 (1996) 455472.
[13] G. Bolch, B. Almasi, J. Sztrik, Heterogeneous finite-source retrial queues, Journal of Mathematical Sciences 121 (2004) 25902596.
[14] J. Sztrik, J. Roszik, Retrial queues for performance modelling and evaluation of heterogeneous networks, in: Proc. of Conf. on Performance Modelling
and Evaluation of Heterogeneous Networks, HET-NET04, Ilkey, England, 2004.
[15] G. Bolch, J. Roszik, J. Sztrik, Heterogeneous finite-source retrial queues in the analysis of communication systems with CSMA/CD protocols, in: Proc.
of the Inter. Conf. on Modern Mathematical Methods of Analysis and Optimization of Telecommunication Networks, Gomel, Belarus, 2003, pp. 3945.
[16] J. Sztrik, J. Roszik, B. Almasi, Multiserver retrial queues with finite number of heterogeneous sources, in: 6th Inter. Conf. on Applied Informatics, Eger,
Hungary, 2004.
[17] D. Efrosinin, L. Breuer, Threshold policies for controlled retrial queues with heterogeneous servers, Annals of Operations Research 141 (2006) 139162.
[18] J. Sztrik, G. Bolch, H.de. Meer, J. Roszik, P. Wuechner, Modeling finite-source retrial queueing systems with unreliable heterogeneous servers and
different service policies using MOSEL, in: Proc. of 14th Inter. Conf. on Analytical and Stochastic Modelling Techniques and Applications, ASMTA07,
Pargue, Czech Republic, 2007, pp. 7580.
[19] J. Sztrik, J. Roszik, Performance analysis of finite-source retrial queues with non-reliable heterogeneous servers, Journal of Mathematical Sciences 146
(2007) 60336038.
[20] J.R. Artalejo, Retrial queues with a finite number of sources, Journal of Korean Mathematical Society 35 (1998) 503525.
[21] D.J. Houck, W.S. Lai, Traffic modeling and analysis of hybrid fiber-coax systems, Computer Networks and ISDN systems 30 (1998) 821834.
[22] J. Sztrik, J. Roszik, C.S. Kim, Retrial queues in the performance modeling of cellular mobile networks using MOSEL, International Journal of Simulation:
Systems Science & Technology 6 (2005) 3847.
[23] G.K. Janssens, The quasi-random input queueing system with repeated attempts as a model for collision-avoidance star local area network, IEEE
Transactions on Communications 45 (1997) 360364.
[24] G. Chiola, D. Dutheillet, G. Franceschinis, S. Haddad, Stochastic Well-Formed Colored nets and symmetric modeling applications, IEEE Transactions on
Computers 42 (1993) 13431360.
[25] D. Dutheillet, S. Haddad, Aggregation and disaggregation of states in colored stochastic Petri nets: Application to a multiprocessor architecture, in: Proc.
3rd Inter. Workshop on Petri Nets and Performance Models, IEEE-CS Press, Japan, 1989.
[26] N. Gharbi, M. Ioualalen, Performance analysis of retrial queueing systems using Generalized Stochastic Petri nets, Electronic Notes in Theoretical
Computer Science 65 (2002).
[27] N. Gharbi, M. Ioualalen, GSPN Analysis of retrial systems with servers breakdowns and repairs, Applied Mathematics and Computation 174 (2006)
11511168.
[28] M. Ajmone Marsan, G. Balbo, G. Conte, S. Donatelli, G. Franceschinis, Modelling with Generalized Stochastic Petri Nets, John Wiley and Sons, New
York, 1995.
[29] K. Jensen, An introduction to the practical use of coloured Petri Nets, in: Lectures on Petri Nets II: Applications, in: LNCS, vol. 1492, 1998, pp. 237292.
[30] G. Chiola, C. Franceschinis, R. Gaeta, M. Ribaudo, GreatSPN 1.7: Graphical editor and analyzer for timed and stochastic Petri nets, Performance
Evaluation 24 (1995) 4768.
[31] G.I. Falin, A multiserver retrial queue with a finite number of sources of primary calls, Mathematical and Computer Modelling 30 (1999) 3349.