InTechOpen uses cookies to offer you the best online experience. By continuing to use our site, you agree to our Privacy Policy.

Computer and Information Science » Theory of Computation » "Petri Nets - Manufacturing and Computer Science", book edited by Pawel Pawlewski, ISBN 978-953-51-0700-2, Published: August 29, 2012 under CC BY 3.0 license. © The Author(s).

Chapter 14

A Petri Net-Based Approach to the Quantification of Data Center Dependability

By Gustavo Callou, Paulo Maciel, Dietmar Tutsch, Julian Araújo, João Ferreira and Rafael Souza
DOI: 10.5772/47829

Article top


Petri net basic elements.
Figure 1. Petri net basic elements.
Compact representation of a PN
Figure 2. Compact representation of a PN
Mathematical formalism; (b) Graphical representation before the firing oft0; (c) Graphical representation after the firing oft0.
Figure 3. Mathematical formalism; (b) Graphical representation before the firing oft0; (c) Graphical representation after the firing oft0.
a) Sourcetransitions; (b) Sinktransitions.
Figure 4. a) Sourcetransitions; (b) Sinktransitions.
PN with an inhibitor arc.
Figure 5. PN with an inhibitor arc.
Figure 6. Self-Loop.
Elementary PN Structures.
Figure 7. Elementary PN Structures.
a) symmetric confusion; (b) asymmetric confusion.
Figure 8. a) symmetric confusion; (b) asymmetric confusion.
A Petri net representing parallel activities.
Figure 9. A Petri net representing parallel activities.
Mutual Exclusion.
Figure 10. Mutual Exclusion.
Dataflow example.
Figure 11. Dataflow example.
Generic simple model - SPN
Figure 12. Generic simple model - SPN
Hyperexponential Model
Figure 13. Hyperexponential Model
Hypoexponential Model
Figure 14. Hypoexponential Model
Generic simple model - RBD
Figure 15. Generic simple model - RBD
Reliability Block Diagram
Figure 16. Reliability Block Diagram
Simple component model
Figure 17. Simple component model
Cold standby model.
Figure 18. Cold standby model.
Data Center Power Architectures.
Figure 19. Data Center Power Architectures.
RBD of Architecture A1.
Figure 20. RBD of Architecture A1.
SPN of Architectures A2.
Figure 21. SPN of Architectures A2.
RBD of Architectures A2.
Figure 22. RBD of Architectures A2.
Reliability Comparison of Architectures A1 and A2.
Figure 23. Reliability Comparison of Architectures A1 and A2.

A Petri Net-Based Approach to the Quantification of Data Center Dependability

Gustavo Callou1, Paulo Maciel1, Julian Araújo1, João Ferreira1 and Rafael Souza2

1. Introduction

Data center availability and reliability have accomplished greater concern due to increased dependence on Internet services (e.g., Cloud computing paradigm, social networks and e-commerce). For companies that heavily depend on the Internet for their operations, service outages can be very expensive, easily running into millions of dollars per hour [15]. A widely used design principle in fault-tolerance is to introduce redundancy to enhance availability. However, since redundancy leads to additional use of resources and energy, it is expected to have a negative impact on sustainability and the associated cost.

Data center designers need to verify several trade-offs and select the feasible solution considering dependability metrics. In this context, formal models (e.g., Stochastic Petri nets and Reliability Block Diagrams) are important to provide estimates before implementing the data center system. Additionally, a growing concern of data center designers is related to the identification of components that may cause system failure as well as systems parts that must be improved before implementing the architecture.

In this work, we propose a set of formal models for quantifying dependability metrics for data center power infrastructures. The adopted approach takes into account a hybrid modeling technique that considers the advantages of both stochastic Petri nets (SPN) [22] and reliability block diagrams (RBD) [10] to evaluate system dependability. An integrated environment, namely, ASTRO [20] has been developed as one of the results of this work to automate dependability evaluation of data center architectures.

2. Preliminaries

This section briefly touches some fundamental concepts as a basis for a better understanding of this work.

2.1. Petri nets

Petri nets (PN) were introduced in 1962 by the PhD dissertation of Carl Adams Petri [16], at Technical University of Darmstandt, Germany. The original theory was developed as an approach to model and analyze communication systems. Petri Nets (PNs) [14] are a graphic and mathematical modeling tool that can be applied in several types of systems and allow the modeling of parallel, concurrent, asynchronous and non-deterministic systems. Since its seminal work, many representations and extensions have been proposed for allowing more concise descriptions and for representing systems feature not observed on the early models. Thus, the simple Petri net has subsequently been adapted and extended in several directions, in which timed, stochastic, high-level, object-oriented and coloured nets are a few examples of the proposed extensions.

2.2. Place-Transition nets

Place/Transition Petri nets are one of the most prominent and best studied class of Petri nets, and it is sometimes called just by Petri net (PN). A marked Place/Transition Petri net is a bipartite directed graph, usually defined as follows:

Definition 2.1 (Petri net) A Petri net [14] is a 5-tuple:


  1. P={p1,p2,...,pm} is a finite set of places;
  2. T={t1,t2,...,tn} is a finite set of transitions;
  3. F(P×T)(T×P)is a set of arcs (flow relation);
  4. W:F{1,2,3,...} is a weight function;
  5. M0:P{0,1,2,3,...} is the initial marking;

This class of Petri net has two kinds of nodes, called places (P) represented by circles and transitions (T) represented by bars, such that PT=ØandPTØ. Figure 1 depicts the basic elements of a simple PN. The set of arcs Fis used to denote the places connected to a transition (and vice-versa). Wis a weight function for the set of arcs. In this case, each arc is said to have multiplicity k, where k represents the respective weight of the arc. Figure 2 shows multiple arcs connecting places and transitions in a compact way by a single arc labeling it with its weight or multiplicity k.


Figure 1.

Petri net basic elements.


Figure 2.

Compact representation of a PN

Places and transitions may have several interpretations. Using the concept of conditions and events, places represent conditions, and transitions represent events, such that, an event may have several pre-conditions and post-conditions. For more interpretations, Table 1 shows other meanings for places and transitions [14].

Input Places Transitions Output Places
input data
input signals
resource needed
computation step
signal processor
logical clauses
output data
output signals
resource releasing

Table 1.

Interpretation for places and transitions.

It is important to show that there are another way to represent PN’s elements. As an example, the set of input and output places of transitions is shown in Definition 2.2. Similarly, the set of input and output transitions of determinate place is shown in Definition 2.3.

Definition 2.2 (Input and Output Transitions of a place) The set of input transitions (also called pre-set) of a place piPis:

 label =pi={tjT|(tj,pi)F}.

and the set of output transitions (also called post-set) is:

 label =pi={tjT|(pi,tj)F}.

Definition 2.3 (Input and output places of a transition) The set of input places of a transition tjTis:

 label =tj={piP|(pi,tj)F}.

and the set of output places of a transition tjTis:

 label =tj={piP|(tj,pi)F}.

2.2.1. Marked Petri nets

A marking (also named token) has a primitive concept in PNs such as place and transitions. Markings are information attributed to places; the number and mark distributions consist of the net state in determined moment. The formal definitions are presented as follows.

Definition 2.4 (Marking) Considering the set of places Pin a netN, the formal definition of marking is represented by a function that maps the set of places P into non negative integersM:PN.

Definition 2.5 (Marking vector) Considering the set of places Pin a netN, the marking can be defined as a vectorM=(M(p1),...,M(pn)), where n=#(P), piP/M(pi)N. Thus, such vector gives the number of tokens in each place for the markingMi.

Definition 2.6 (Marked net) A marked Petri net is defined by a tuplaNM=(N;M0), where Nis the net structure and M0 is the initial marking.

A marked Petri net contains tokens, which reside in places, travel along arcs, and their flow through the net is regulated by transitions. A peculiar distribution (M) of the tokens in the places, represents a specific state of the system. These tokens are denoted by black dots inside the places as shown in Figure 1 (d).

2.2.2. Transition enabling and firing

The behavior of many systems can be described in terms of system states and their changes. In order to simulate the dynamic behavior of a system, a state (or marking) in a Petri net is changed according to the following firing rule:

  1. A transition tis said to be enabled, if each input place pof tis marked with at least the number of tokens equal to the multiplicity of its arc connecting p witht. Adopting a mathematical notation, an enabled transition tfor given marking mi is denoted by mi[t>, ifmi(pj)W(pj,t),pjP.

  2. An enabled transition may or may not fire (depending on whether or not the respective event takes place).

  3. The firing of an enabled transition tremoves tokens (equal to the multiplicity of the input arc) from each input placep, and adds tokens (equal to the multiplicity of the output arc) to each output placep'. Using a mathematical notation, the firing of a transition is represented by the equationmj(p)=mi(p)-W(p,t)+W(t,p),pP. If a marking mj is reachable from mi by firing a transitiont, it is denoted bymi[t>mj.

Figure 3 (a) shows the mathematical representation of a Petri net model with three places (p0, p1,p2) and one transition (t0). Besides, there is one arc connecting the place p0 to the transition t0 with weight two, one arc from the place p1 to the transition t0 with weight one, and one arc connecting the transition t0 to the place p2 with weight two. The initial marking (m0) is represented by three tokens in the place p0 and one token in the placep1. Figure 3 (b) outlines its respective graphical representation, and Figure 3 (c) provides the same graphical representation after the firing oft0. For this example, the set of reachable markings is m = {m0=(3,1,0),m1=(1,0,2)}. The marking m1 was obtained by firingt0, such that, m1(p0)= 3 - 2 + 0, m1(p1)= 1 - 1 + 0, and m1(p2) = 0 - 0 + 2.


Figure 3.

Mathematical formalism; (b) Graphical representation before the firing oft0; (c) Graphical representation after the firing oft0.

There are two particular cases which the firing rule happens differently. The first one is a transition without any input place that is called as a sourcetransition, and the other one is a transition without any output place, named sinktransition. A sourcetransition is unconditionally enabled, and the firing of a sinktransition consumes tokens, but does not produce any. Figure 4 (a) shows a sourcetransition, and Figure (b) 4 depicts a sinktransition. In both, the markings are represented before and after their respective firing.


Figure 4.

a) Sourcetransitions; (b) Sinktransitions.

Definition 2.7 (Source transitions) A transition is said to be source if, and only if, I(p,t)=0,pP.

Definition 2.8 (Sink transitions) A transition is said to be sink if, and only if, O(p,t)=0,pP.

Definition 2.9 (Inhibitor arc) Originally not present in PN, the introduction of the concept of inhibitor arc increases the modeling power of PN, adding the ability of testing if a place does not have tokens. In the presence of an inhibitor arc, a transition is enabled to fire if each input place connected by a normal arc has a number of tokens equal to the arc weight, and if each input place connected by an inhibitor arc has no tokens. Figure 5 illustrates an inhibitor arc connecting the input place p0 to the transitiont0, which is denoted by an arc finished with a small circle. In such Figure, the transition t0 is enabled to fire.


Figure 5.

PN with an inhibitor arc.

Definition 2.10 (Pure net) A Petri net is said to be pure if it has no self-loops. A pair of a place pand transition tis called a self-loop if pis both an input and output place oft. Figure 6 shows a self-loop net.


Figure 6.


2.3. Elementary structures

Elementary nets are used as building blocks in the specification of more complex applications. Figure 7 shows five structures, namely, (a) sequence, (b) fork, (c) synchronization, (d) choice, and (e) merging.


Figure 7.

Elementary PN Structures.


Sequence structure represents sequential execution of actions, provided that a condition is satisfied. After the firing of a transition, another transition is enabled to fire. Figure 7(a) depicts an example of this structure in which a mark in place p0 enables the transitiont0. The firing of transition t0 enables the transition t1 (p1is marked).


Figure 7(b) shows an example of a fork structure that allows the creation of parallel processes.


Generally, concurrent activities need to synchronize with each other. This net (Figure 7(c)) combines two or more nets, allowing that another process continues this execution only after the end of predecessor processes.


Figure 7(d) depicts a choice model, in which the firing of the transition t0disables the transitiont1. This building block is suited for modeling if-then-else statement, for instance.


The merging is an elementary net that allows the enabling of the same transition by two or more processes. Figure 7(e) shows a net with two independent transitions (t0andt1) that have an output place in common (P2). Therefore, firing of any of these two transitions, a condition is created (p2is marked) which allows the firing of another transition (not shown in the figure).


The mixing between conflict and concurrency is called confusion. While conflict is a local phenomenon in the sense that only the pre-sets of the transitions with common input places are involved, confusion involves firing sequences. Figure 8 depicts two types of confusions: (a) symmetric confusion, where two transitions t1 and t3 are concurrent while each one is in conflict with transitiont2; and (b) asymmetric confusion, where t1 is concurrent witht2, but will be in conflict with t3 if t2 fires first.


Figure 8.

a) symmetric confusion; (b) asymmetric confusion.

2.4. Petri nets modeling examples

In this section, several simple examples are given in order to introduce how to model some basic concepts such as parallel process and mutual exclusion in Petri nets.

Parallel processes

In order to represent parallel processes, a model may be obtained by composing the model for each individual process with a fork and synchronization models. Two transitions are said to be parallel (or concurrent), if they are causally independent, i.e., one transition may fire either before (or after) or in parallel with the other.

Figure 9 depicts an example of parallel process, where transitions t1 and t2 represent parallel activities. When transition t0 fires, it creates marks in both output places (p0andp1), representing a concurrency. When t1 and t2 are enabled for firing, each one may fire independently. The firing of t3 depends on two pre-conditions, p2andp3, implying that the system only continues if t1 and t2 have been fired.

Figure 9 presents a net in which each place has exactly one incoming arc and exactly one outgoing arc. Thus, such model represents a sub-class of Petri nets known as marked graphs. Marked graphs allow representation of concurrency but not decisions or conflicts.


Figure 9.

A Petri net representing parallel activities.

Mutual exclusion

The sharing of resources and/or data are common in many system applications, in which most of resources and data should be accessed in a mutual exclusive way. Resources (or data variable) may be modeled by a place with tokens representing the amount of resources. This place is seen as pre-conditions for all transitions that need such resource. After the use of one resource, it must be released. Figure 10 depicts an example of a machine that is accessed in a mutual exclusive way.


Figure 10.

Mutual Exclusion.

Dataflow computation

Petri nets can be used to represent not only the control-flow but also the data-flow. The net shown in Figure 11 is a Petri net representation of a dataflow computation. A dataflow is characterized by the concurrent instruction execution (or transitions firing) as soon as the operands (pre-conditions) are available. In the Petri net representation, tokens may denote values of current data as well as the availability of data. The instructions are represented by transitions such as Addand Subtractthat can be executed in parallel. After that, if the activity Subtracthas computed a result different from zero, meaning that the pre-conditions to perform divideoperation were satisfied. Afterwards, when the transition divideoccur, the dataflow computation is completed.


Figure 11.

Dataflow example.

2.5. Petri nets properties

The PN properties allow a detailed analysis of the modeled system. For this, two types of properties have been considered in a Petri net model: behavioral and structural properties. Behavioral properties are those which depend on the initial marking. Structural properties, on the other hand, are those that are marking-independent.

2.5.1. Behavioral properties

This section, based on [14], describes some behavioral properties, since such properties are very important when analyzing a given system.


The firing of an enabled transition changes the token marking in a Petri net, and a sequence of firings results in a sequence of markings. A marking Mn is said to be reachable from a marking M0 if there exists a sequence of firings that transforms M0 toMn.

A firing (or occurrence) sequence is denoted byσ=t1,t2,...,tn. In this case, miis reachable from m0 byσ, and it is denoted bym0[σ>mi. The set of all possible reachable markings from m0 in a net (PN,m0) is denoted by R(PN,m0), or simply R(m0). The set of all possible firing sequence from m0 in a net (PN,m0) is denoted by L(PN,m0), or simply L(m0).


A Petri net is said to be bounded if the number of tokens in each place does not exceed a finite number k for any marking reachable fromM0. In a formal way, M(p)k, pPandMR(M0).


When the number of tokens in each place does not exceed the number “1” (one), such Petri net is said to be safe. It is important to state that if a net is bounded or safe, it is guaranteed that there will be no overflows in any place, no matter the firing sequence adopted.

Deadlock freedom

A PN is said to be deadlock free if there is no reachable marking such that no transition is enabled.


In an informal way, a Petri net is said to be live if it is guaranteed that no matter what firing sequence is chosen, it continues in deadlock-free operation. The formal definition, a Petri net (N,M0) is said to be live if, no matter what marking has been reached fromM0, it is possible to ultimately fire any transition of the net.

Liveness is an ideal property for many real systems. However, it is very strong and too costly to verify. Thus, the liveness condition is relaxed in different levels. A transition tis said to be live at the following levels:

  • L0Live (dead), if tcan never be fired in any firing sequence in L(m0), it is a dead transition.
  • L1-Live (potentially firable), if it can be fired at least once in some firing sequence in L(m0).
  • L2-Live if, given any positive integer k, tcan be fired at least k times in some firing sequence in L(m0).
  • L3-Live if there is an infinite-length firing sequence in L(m0) in which tis fired infinitely.
  • L4-Live (or simply live), if it is L1-Live for every marking m in R(m0).


A Petri net is said to be persistent if, for any two enabled transitions, the firing of one transition will not disable the other. Once a transition is enabled in a persistent net, it is continue to be enabled until it fires. Persistency is closed related to conflict-free nets. It is worth noting that all marked graph are persistent, but not all persistent nets are marked graphs. Persistence is a very important property when dealing with parallel system design and speed-independent asynchronous circuits.

2.5.2. Structural properties

Structural liveness

A PN Nis said to be structurally live if there is a live initial marking forN.

Structural boundedness

A PN Nis said to be structurally bounded if it is bounded for any finite initial markingM0.

Structural conservativeness

A PN that provides a constant weighted sum of tokens for any reachable marking when considering any initial marking is said to be structural conservative.

Structural repetitiveness

A PN is classified as repetitive if there is an initial marking m0 and an enabled firing sequence from m0 such that every transition of the net is infinitely fired. On the other hand, if only some of these transitions are fired infinitely often in the sequenceσ, this net is called partially repetitive.


A net is classified as consistent if there is an initial marking m0 and an enabled firing sequence from m0 back to m0 such that every transition of the net is fired at least once. If only some of these transitions are not fired in the sequenceσ, this net is called partially consistent.

2.6. Stochastic Petri nets

Petri nets [17] are a classic tool for modeling and analyzing discrete event systems which are too complex to be described by automata or queueing models. Time (stochastic delays) and probabilistic choices are essential aspects for a performance evaluation model. We adopt the usual association of delays and weights with transitions [11] in this paper, and adopt the extended stochastic Petri net definition similar to [9]:

Let SPN=(P,T,I,O,H,Π,G,M0,Atts) be a stochastic Petri net, where

  • P={p1,p2,...,pn}is the set of places, which may contain tokens and form the discrete state variables of a Petri net.
  • T={t1,t2,...,tm}is the set of transitions, which model active components.
  • I(NnN)n×mis a matrix of marking-dependent multiplicities of input arcs, where ijk entry of Igives the (possibly marking-dependent) arc multiplicity of input arcs from place pj to transition tk[A(P×T)(T×P) — set of arcs]. A transition is only enabled if there are enough tokens in all input places.
  • O(NnN)n×mis a matrix of marking dependent multiplicities of output arcs, where ojk entry of Ospecifies the possibly marking-dependent arc multiplicity of output arcs from transition tj to placepk. When a transition fires, it removes the number of tokens specified by the input arcs from input places, and adds the amount of tokens given by the output arcs to all output places.
  • H(NnN)n×mis a matrix of marking-dependent multiplicities describing the inhibitor arcs, where hjk entry of Hreturns the possibly marking-dependent arc multiplicity of an inhibitor arc from place pjto transitiontk. In the presence of an inhibitor arc, a transition is enabled to fire only if every place connected by an inhibitor arc contains fewer tokens than the multiplicity of the arc.
  • ΠNmis a vector that assigns a priority level to each transition. Whenever there are several transitions fireable at one point in time, the one with the highest priority fires first and leads to a state change.
  • M0Nnis a vector that contains the initial marking for each place (initial state).
  • Atts:(Dist,W,G,Policy,Concurrency)mcomprises a set of attributes for the mtransitions, where
    • DistNmFis a possibly marking dependent firing probability distribution function. In a stochastic timed Petri net, time has to elapse between the enabling and firing of a transition. The actual firing time is a random variable, for which the distribution is specified byF. We differ between immediate transitions (F=0) and timed transitions, for which the domain of Fis(0,).

    • WR+is the weight function, that represents a firing weight wt for immediate transitions or a rate λt for timed transitions. The latter is only meaningful for the standard case of timed transitions with exponentially distributed firing delays. For immediate transitions, the value specifies a relative probability to fire the transition when there are several immediate transitions enabled in a marking, and all have the same probability. A random choice is then applied using the probabiliteswt.

    • GNn{true,false}is a function that assigns a guard condition related to place markings to each transition. Depending on the current marking, transitions may not fire (they are disabled) when the guard function returns false. This is an extension of inhibitor arcs.

    • Policy{prd,prs}is the preemption policy (prdpreemptive repeat different means that when a preempted transition becomes enabled again the previously elapsed firing time is lost;prspreemptive resume, in which the firing time related to a preempted transition is resumed when the transition becomes enabled again),

    • Concurrency{ss,is}is the concurrency degree of transitions, where ssrepresents single server semantics and isdepicts infinity server semantics in the same sense as in queueing models. Transitions with policy iscan be understood as having an individual transition for each set of input tokens, all running in parallel.

In many circumstances, it might be suitable to represent the initial marking as a mapping from the set of places to natural numbers (m0:PN), where m0(pi) denotes the initial marking of placepi. m(pi)denotes a reachable marking (reachable state) of placepi. In this work, the notation #pi has also been adopted for representingm(pi).

2.7. Dependability

Dependability of a computer system must be understood as the ability to deliver services with respect to some agreed-upon specifications of desired service that can be fully trusted [1, 13]. Indeed, dependability is related to disciplines such as fault tolerance and reliability. Reliability is the probability that the system will deliver a set of services for a given period of time, whereas a system is fault tolerant when it does not fail even when there are faulty components. Availability is also another important concept, which quantifies the mixed effect of both failure and repair process in a system. In general, availability and reliability are related concepts, but they differ in the sense that the former may consider maintenance of failed components [8] (e.g., a failed component is restored to a specified condition).

In many situations, modeling is the method of choice either because the system might not yet exist or due to the inherent complexity for creating specific scenarios under which the system should be evaluated. In a very broad sense, models for dependability evaluation can be classified as simulation and mathematical models. However, this does not mean that mathematical models cannot be simulated. Indeed, many mathematical models, besides being analytically tractable, may also be evaluated by simulation. Mathematical models can be characterized as being either state-based or non-state-based.

Dependability metrics (e.g., availability, reliability and downtime) might be calculated either by using RBD or SPN (to mention only the models adopted in this work). RBDs allow to one represent component networks and provide closed-form equations, so the results are usually obtained faster than using SPN simulation. Nevertheless, when faced with representing maintenance policies and redundant mechanisms, particularly those based on dynamic redundancy methods, such models experience drawbacks concerning the thorough handling of failures and repairing dependencies. On the other hand, state-based methods can easily consider those dependencies, so allowing the representation of complex redundant mechanisms as well as sophisticated maintenance policies. However, they suffer from the state-space explosion. Some of those formalism allow both numerical analysis and stochastic simulation, and SPN is one of the most prominent models of such class.

If one is interested in calculating the availability (A) of given device or system, he/she might need either the uptime and downtime or the time to failure (TTF) and time to repair (TTR). Considering that the uptime and downtime are not available, the later option is the mean. If the evaluator needs only the mean value, the metrics commonly adopted are Mean Time to Failure (MTTF) and Mean Time To Repair (MTTR) (other central values might also be adopted). However, if one is also interested in the availability variation, the standard deviation of time to failure (sd(TTF)), and the respective standard deviation of time to repair (sd(TTR)) allow one the estimate the availability variation.

The availability (A) is obtained by steady-state analysis or simulation, and the following equation expresses the relation concerning MTTFandMTTR:


Through transient analysis or simulation, the reliability (R) is obtained, and, then, the MTTFcan be calculated as well as the standard deviation of the Time To Failure (TTF):


Considering a given periodt, R(t)is the probability that the time to failure is greater than or equal to t. Regarding exponential failure distributions, reliability is computed as follows:


where λ(t')is the instantaneous failure rate.

One should bear in mind that, for computing reliability of a given system service, the repairing activity of the respective service must not be represented. Besides, taking into account UA=1-A(unavailability) and Equation 1, the following equation is derived


As well, the standard deviation of the Time To Repair (TTR) can be calculated as follows:


Next, MTTFsd(TTF)(andMTTRsd(TTR)) are computed for choosing the expolinomial distribution that best fits the TTFand TTRdistributions [6, 22].

Figure 12 depicts the generic simple component model using SPN, which provides a high-level representation of a subsystem. One should notice the trapezoidal shape of transitions (high-level transition named s-transition). This shape means that the time distributions of such transitions are not exponentially distributed, instead they should be refined by subnets. The delay assigned to s-transition fis the TTFand the delay of s-transition ris theTTR. If the TTFand TTRare exponentially distributed, the shape of the transitions should be the regular one (white rectangles) and TTFand TTRshould be summarized by the respective MTTFandMTTR.


Figure 12.

Generic simple model - SPN

A well-established method that considers expolynomial distribution random variables is based on distribution moment matching. The moment matching process presented in [6] takes into account that Hypoexponential and Erlangian distributions have the average delay (μ) greater than the standard-deviation (σ) -μ>σ -, and Hyperexponential distributions haveμ<σ, in order to represent an activity with a generally distributed delay as an Erlangian or a Hyperexponential subnet referred to as s-transition[1] - . One should note that in cases where these distributions haveμ=σ, they are, indeed, equivalent to an exponential distribution with parameter equal to1μ. Therefore, according to the coefficient of variation associated with an activity’s delay, an appropriate s-transition implementation model could be chosen. For each s-transition implementation model (see Figure 12), a set of parameters should be configured for matching their first and second moments. In other words, an associated delay distribution (it might have been obtained by a measuring process) of the original activity is matched with the first and second moments of s-transition (expolynomial distribution). According to the aforementioned method, one activity with μ<σis approximated by a two-phase Hyperexponential distribution with parameters

(7) (8)



where λis the rate associated to phase1, r1is the probability of related to this phase, and r2 is the probability assigned to phase2. In this particular model, the rate assigned to phase 2 is assumed to be infinity, that is, the related average delay is zero.


Figure 13.

Hyperexponential Model

Activities with coefficients of variation less than one might be mapped either to Hypoexponential or Erlangian s-transitions. IfμσN,μσ1,(μ,σ0), the respective activity is represented by a Hypoexponential distribution with parametersλ1, λ2(exponential rates); andγ, the integer representing the number of phases with rate equal toλ2, whereas the number of phases with rate equal to λ1 is one. In other words, the s-transition is represented by a subnet composed of two exponential and one immediate transitions. The average delay assigned to the exponential transition t1 is equal to μ1 (λ1=1/μ1), and the respective average delay assigned to the exponential transition t2 is μ2(λ2=1/μ2). γis the integer value considered as the weight assigned to the output arc of transition t1 as well as the input arc weight value of the immediate transition t3 (see Figure 13). These parameters are calculated by the following expressions:

λ1=1μ1  and 2=1μ2, 



IfμσN,μσ1,(μ,σ0), an Erlangian s-transition with two parameters, γ=(μσ)2is an integer representing the number of phases of this distribution; andμ1=μ/γ, where μ1(1/λ1) is the average delay value of each phase. The Erlangian model is a particular case of a Hypoexponential model, in which each individual phase rate has the same value.


Figure 14.

Hypoexponential Model

The reader should refer to [6] for details regarding the representation of expolinomial distributions using SPN. For the sake of simplicity, the SPN models presented in the next sections consider only exponential distributions.

Depending on the system characteristics, a RBD model (Figure 15) could be adopted instead of the SPN counterpart, whenever the former is more suitable.


Figure 15.

Generic simple model - RBD

3. Related works

In the last few years, some works have been developed to perform dependability analysis of data center systems [24][26][27]. Reliability (which encompasses both the durability of the data and its availability for access) correspond to the primary property that data center users desire [2].

Robidoux [28] proposes Dynamic RBD (DRBD) model, an extension to RBD, which supports reliability analysis of systems with dependence relationships. The additional blocks (in relation to RBD) to model dependence, turned the DRBD model complex. The DRBD model is automatic converted to CPN model in order to perform behavior properties analysis which may certify the correctness of the model [18]. It seems that an interesting alternative would be to model the system directly using CPN or any other formalism (e.g., SPN) which is able to perform dependability analysis as well as to model dependencies between components.

Wei [25] presents an hierarchical method to model and analyze virtual data center (VDC). The approach combines the advances of both RBD and General SPN (GSPN) for quantifying availability and reliability. Data center power architectures are not the focus of their research and the proposed models are specific for modeling VDC.

Additionally, redundancies on components to increase system reliability are costly. [7] propose an approach for reliability evaluation and risk analysis of dynamic process systems using stochastic Petri nets.

Different from previous works, this paper proposes a set of models to the quantification of dependability metrics in the context of data center design. Furthermore, the adopted methodology for the quantification of those values takes into account a hybrid modeling approach, which utilizes RBD and SPN whenever they are best suited. The idea of mixing state (SPN) and non-state (RBD) based models is not new (e.g., [23]), but, as far as we are concerned, there is no similar work that applies such technique on the evaluation of data center infrastructures. Besides, a tool is proposed to automate several activities.

4. Dependability models

The following sections presents the adopted dependability models.

RBD Models

Reliability Block Diagram (RBD) [8] is a combinatorial model that was initially proposed as a technique for calculating reliability of systems using intuitive block diagrams. Such a technique has also been extended to calculate other dependability metrics, such as availability and maintainability [10]. Figure 16 depicts two examples, in which independent blocks are arranged through series (Figure 16(a)) and parallel (Figure 16(b)) compositions.


Figure 16.

Reliability Block Diagram

In the series arrangement, if a single component fails, the whole system is no longer operational. Assuming a system with nindependent components, the reliability (instantaneous availability or steady state availability) is obtained by


where Pi is the reliability - Ri(t) (instantaneous availability (Ai(t)) or steady state availability (Ai)) of blockbi.

For a parallel arrangement (see Figure 16(b)), if a single component is operational, the whole system is also operational. Assuming a system with nindependent components, the reliability (instantaneous availability or steady state availability) is obtained by


where Pi is the reliability - Ri(t) (instantaneous availability (Ai(t)) or steady state availability (Ai)) of blockbi.

A k-out-of-n system functions if and only if kor more of its ncomponents are functioning. Let pbe the success probability of each of those blocks. The system success probability (reliability or availability) is depicted by:


For other examples and closed-form equations, the reader should refer to [10].

SPN Models

This section presents two proposed SPN building block for obtaining dependability metrics.

Simple Component. The simple component has two states: functioning or failed. To compute its availability, MTTFand MTTRshould be represented. Figure 17 shows the SPN model of the “simple component”, which has two parameters (not depicted in the figure), namely X_MTTFandX_MTTR, representing the delays associated to the transitions X_FailureandX_Repair, respectively.


Figure 17.

Simple component model

Places X_ONand X_OFFare the model component’s activity and inactivity states, respectively. The simple component also includes an arc from X_OFFto X_Repair with multiplicity depending on place marking. The multiplicity is defined through the expression IF(#X_Rel_Flag=1):2 ELSE 1, where place X_Rel_Flagmodels the evaluation of reliability/availability. Hence, if condition #X_Rel_Flag=1 is true, then the evaluation refers to reliability. Otherwise, the evaluation concerns availability.

Besides, although simple component model has been presented using the exponential distribution, other expolinomial distributions that best fits the TTFand TTRmay be adopted following the techniques presented in [22].

Cold standby. A cold standby redundant system is composed by a non-active spare module that waits to be activated when the main active module fails. Figure 18 depicts the SPN model of this system, which includes four places, namelyX_ON, X_OFF, X_Spare1_ON, X_Spare1_OFFthat represent the operational and failure states of both the main and spare modules, respectively. The spare module (Spare1) is initially deactivated, hence no tokens are initially stored in places X_Spare1_ONand X_Spare1_OFF. When the main module fails, the transition X_Activate_Spare1is fired to activate the spare module.


Figure 18.

Cold standby model.

Table 2 presents the attributes of each transition of the model. Once considering reliability evaluation (number of tokens (#) in the place X_Rel_Flag=1), theX_Repair, X_Activate_Spare1and X_Repair_Spare1transitions receive a huge number (many times larger than the associated MTTF or MTActivate) to represent the absence of repair. The MTActivate corresponds to the mean time to activate the spare module. Besides, when considering reliability, the weight of the edge that connects the place X_Wait_Spare1and the X_Activate_Spare1transition is two; otherwise, it is one. Both availability and reliability may be computed by the probability P{#X_ON=1 OR #X_Spare1_ON=1}.

Transition Priority Delay or Weight
X_Failure - X_MTTF
X_Repair - IF #X_Rel_Flag=1:(1013 x X_MTTF)
X_Activate_Spare1 - IF #X_Rel_Flag=1:(1013 x MTActivate)
ELSE MTActivate
X_Failure_Spare1 - X_MTTF_Spare1
X_Repair_Spare1 - IF #X_Rel_Flag=1:(1013 x X_MTTF_Spare1)
X_Desactivate_Spare1 1 1

Table 2.

Cold standby model - Transition attributes.

5. Applications

This section focuses in presenting the applicability of the proposed models to perform dependability analysis of real-world data center power architectures (from HP Labs Palo Alto, U.S. [12]). The environment ASTRO was adopted to conduct the case study. ASTRO was validated through our previous work [5] [3] [4].

5.1. Architectures


Figure 19.

Data Center Power Architectures.

Data center power infrastructure is responsible for providing uninterrupted, conditioned power at correct voltage and frequency to the IT equipments. Figure 19 (a) depicts a real-world power infrastructure. From the utility feed (i.e., AC Source), typically, the power goes through voltage panels, uninterruptible power supply (UPS) units, power distribution units (PDUs) (composed of transformers and electrical subpanels), junction boxes, and, finally, to rack PDUs (rack power distribution units). The power infrastructure fails (and, thus, the system) whenever both paths depicted in Figure 19 are not able to provide the power demanded (500 kW) by the IT components (50 racks). The reader should assume a path as a set of redundant interconnected components inside the power infrastructure. Another architecture is analyzed with an additional electricity generator (Figure 19 (b)) for supporting the system when both AC sources are not operational.

5.2. Models


Figure 20.

RBD of Architecture A1.

This work adopts a hierarchical methodology for conducting dependability evaluation of data center architectures. In general, the methodology aims at grouping related components in order to generate subsystem models, which are adopted to mitigate the complexity of the final system model evaluation. Thus, the final model is an approximation, but rather simpler, of a more intricate system model. One should bear in mind that the detailed model could be adopted instead, but at the expenses of complexity.

Following the adopted methodology, systems with no failure dependencies between components have been evaluated through RBD models. For instance, Figure 20 depicts the RBD model that represents the architecture A1.


Figure 21.

SPN of Architectures A2.


Figure 22.

RBD of Architectures A2.

In architecture A2, the generator is only activated when both AC sources are not available. Therefore, a model that deal with dependencies must be adopted. Figure 21 shows the SPN model considering cold standby redundance to represent the subsystem composed of generator and two AC sources. Besides, we assume that UPS’ batteries support the system during the generator activation. The reliability or availability is computed by the probability P{#ACSource1_ON=OR #ACSource2_ON=1 OR#Generator_ON=1}.

The other components of the architecture A2 are modeled using RBD as shown in Figure 22. Once obtained the results of both models (RBD and the SPN model with dependencies), a RBD model with two blocks (considering the results of those models) in a serial arrangement is created. The RBD evaluation provides the dependability results of the architecture A2 system.

Equipment MTTF (hs) MTTR (hs)
AC Source 4,380 8
Generator 2,190 8
STS 240,384 8
Subpanel 1,520,000 8
Transformer 1,412,908 8
UPS 250,000 8
Low Voltage Panel 1,520,000 8

Table 3.

MTTF and MTTR values for power devices.

The adopted MTTF and MTTR values for the power devices were obtained from [21] [29] [19] and are shown in Table 3.

5.3. Results

Figure 23 depicts a graphical comparison between the reliability results (in number of 9’s) of those two data center power architectures. The respective number of nines (-log[1 - A/100]) and the period of 8760 hours (1 year) are adopted. As the reader should note, the reliability of both architectures decreases when the time increases. Besides, it is also possible to notice that the generator has increased the reliability of the architecture A2. Considering the availability results, similar behavior happened. The availability has increased from 5.47 to 7.96 (in number of 9’s).


Figure 23.

Reliability Comparison of Architectures A1 and A2.

6. Conclusion

This work considers the advantages of both Stochastic Petri Nets (SPN) and Reliability Block Diagrams (RBD) formalisms to analyze data center infrastructures. Such approach is supported by an integrated environment, ASTRO, which allows data center designers to estimate the dependability metrics before implementing the architectures. The methodology proposes that the system should be evaluated piecewisely to allow the composition of simpler models representing a data center infrastructure appropriately. Moreover, experiments demonstrate the feasibility of the environment, in which different architectures for a data center power infrastructures have been adopted.


The authors would like to thank CNPQ for financing the project (290018/2011-0) and supporting the development of this work.


1 - A. Avizienis, J. Laprie, B. Randell, 2001Fundamental Concepts of Dependability,Technical Report Series-University of Newcastle upon Tyne Computing Science.
2 - P. Banerjee, C. Bash, R. Friedrich, P. Goldsack, B. A. Huberman, J. Manley, C. Patel, P. Ranganathan, Veitch, A. , 2011Everything as a service: Powering the new information economyIEEE Computer3643
3 - G. Callou, P. Maciel, F. Magnani, J. Figueiredo, E. Sousa, E. Tavares, B. Silva, F. Neves, C. Araujo, 2011Estimating sustainability impact, total cost of ownership and dependability metrics on data center infrastructures, Sustainable Systems and Technology (ISSST), 2011 IEEE International Symposium on, 16
4 - G. Callou, P. Maciel, E. Tavares, E. Sousa, B. Silva, J. Figueiredo, C. Araujo, F. Magnani, F. Neves, 2011Sustainability and dependability evaluation on data center architecturesSystems, Man, and Cybernetics (SMC), 2011 IEEE International Conference on, 398403
5 - G. Callou, E. Sousa, P. Maciel, E. Tavares, B. Silva, J. Figueirêdo, C. Araujo, F. Magnani, F. Neves, 2011A formal approach to the quantification of sustainability and dependability metrics on data center infrastructures, Proceedings of the 2011 Symposium on Theory of Modeling & Simulation: DEVS Integrative M&S Symposium, TMS-DEVS ‘11, Society for Computer Simulation International, San Diego, CA, USA, 274281URL:
6 - A. Desrochers, R. Al-Jaar, 1995Applications of Petri Nets in Manufacturing Systems: Modeling, Control, and Performance Analysis,IEEE Press.
7 - Y. Dutuit, E. Ch¯atelet, J. Signoret, P. Thomas, 1997Dependability modeling and evaluation by using stochastic Petri nets: application to two test cases, Reliability Engineering & System Safety 552117124
8 - C. Ebeling, 1997An Introduction to Reliability andMaintainability Engineering,Waveland Press.
9 - R. German, 2000Performance Analysis of Communication Systems with Non-Markovian Stochastic Petri Nets, JohnWileySons, Inc.,NewYork,NY,USA.
10 - W. Kuo, M. J. Zuo, 2003Optimal Reliability Modeling- Principles and Applications,Wiley.
11 - M. A. Marsan, G. Balbo, G. Conte, S. Donatelli, G. Franceschinis, 1995Modelling with Generalized Stochastic Petri NetsJohnWiley and Sons.
12 - M. Marwah, P. Maciel, A. Shah, R. Sharma, T. Christian, V. Almeida, C. Araújo, E. Souza, G. Callou, B. Silva, S. Galdino, J. Pires, 2010Quantifying the sustainability impact of data center availabilitySIGMETRICS Perform. Eval. Rev. 376468URL:
13 - J. F. Meyer, W. H. Sanders, 1993Specification and construction of performability models., Proceedings of the Second International Workshop on Performability Modeling of Computer and Communication Systems, Mont Saint-Michel, France.
14 - T. Murata, 1989Petri nets: Properties, analysis and applicationsProceedings of the IEEE774541580
15 - D. Patterson, 2002A simple way to estimate the cost of downtime, Proceedings of the 16th USENIX conference on System administration, LISA ‘02, USENIX Association, Berkeley, CA, USA, 185188URL:
16 - C. A. Petri, 1962Kommunikationmit Automaten, PhD Dissertation,Darmstad University, Germany.
17 - W. Reisig, 1985Petri nets: an introduction,Springer-Verlag New York, Inc., New York, NY, USA.
18 - R. Robidoux, H. Xu, S. Member, L. Xing, S. Member, M. Zhou, 2010Automated modeling of dynamic reliability block diagrams using colored petri netsIEEE Transactions on SystemsMan, and Cybernetics, Part A: Systems and Humans 402337351
19 - Service Level Agreement for Data Center Services2012
20 - B. Silva, P. Maciel, E. Tavares, C. Araujo, G. Callou, E. Sousa, N. Rosa, M. Marwah, R. Sharma, A. Shah, T. Christian, J. Pires, 2010Astro: A tool for dependability evaluation of data center infrastructuresSystems Man and Cybernetics (SMC), 2010 IEEE International Conference on, 783790
21 - std, I. , 1997Gold Book 473 Design of Reliable Industrial and Commercial Power Systems, IEEE.
22 - K. Trivedi, 2002Probability and Statistics with Reliability, Queueing, and Computer Science Applications, 2 edn, Wiley Interscience Publication.
23 - K. Trivedi, et al.1994Reliability analysis techniques explored through a communication network example, International Workshop on Computer-Aided Design, Test, and Evaluation for Dependability.
24 - S. A. Vilkomir, D. L. Parnas, V. B. Mendiratta, E. Murphy, 2006Segregated failures model for availability evaluation of fault-tolerant system,ACSC ‘06: Proceedings of the 29th Australasian Computer Science Conference, Australian Computer Society, Inc., Darlinghurst, Australia, Australia, 5561
25 - B. Wei, C. Lin, X. Kong, 2011Dependability modeling and analysis for the virtual data center of cloud computing, High Performance Computing and Communications (HPCC), 2011 IEEE 13th International Conference on, 784789
26 - M. Wiboonrat, 2008aAn empirical study on data center system failure diagnosis, Internet Monitoring and Protection, 2008. ICIMP ‘08. The Third International Conference on, 103108
27 - M. Wiboonrat, 2008bRisk anatomy of data center power distribution systems, ICSET’08.
28 - H. Xu, L. Xing, R. Robidoux, 2008Drbd: Dynamic reliability block diagrams for system reliabilitymodeling, International Journal of Computers and Applications.
29 - L. Zhou, W. Grover, 2005A EOFtheory for setting the "safety margin" on availability guarantees in an sla, Design of Reliable Communication Networks, 2005. (DRCN 2005). Proceedings.5th InternationalWorkshop on, p. 7 pp.


[1] - In this work, μ could be MTTF or MTTR and the σ could represent sd(TTF) or sd(TTR), for instance.