Modeling Background

From Mobius Wiki
Jump to: navigation, search

Möbius Tool

Motivation

Performance and dependability modeling is an integral part of the design process of many computer and communication systems. A variety of techniques have been developed to address different issues of modeling. For example, combinatorial models were developed to assess reliability and availability under strong independence assumptions; queuing networks were developed to assess system performance; and Markov process-based approaches have become popular for evaluating performance with synchronization or dependability without independence assumptions. Finally, simulation has been used extensively when other methods fail.

As techniques for solving models advanced, formalisms (or formal languages for expressing models) were also developed. Each formalism has its own merits. Some formalisms afford very efficient solution methods; for example, BCMP[1] queuing networks admit product-form solutions, while superposed generalized stochastic Petri nets (SGSPNs)[2] afford Kronecker-based solution methods, and colored GSPNs (CGSPNs)[3] yield state-space reductions. Other formalisms, such as SPNs[4] and SPAs[5], provide a simple elegance in their modeling primitives, while a number of extensions, such as stochastic activity networks (SANs)[6], were developed for compactly expressing complex behaviors.

Along with formalisms, tools have been developed. A tool is generally built around a single formalism and one or more solution techniques, with simulation sometimes available as a second solution method. [7] lists a number of such tools, such as DyQN-Tool+[8], which uses dynamic queuing networks as its high-level formalism; GreatSPN[9], which is based on GSPNs[10]; UltraSAN[11], which is based on SANs[6]; SPNP[12], which is based on stochastic reward networks[13]; and TANGRAM-II[14], which is an object- and message-based formalism for evaluating computer and communication systems. While all of these tools are useful within the domains for which they were intended, they are limited in that all parts of a model must be built in the single formalism that is supported by the tool. Thus, it is difficult to model systems that cross different domains and would benefit from multiple modeling techniques.

Möbius takes an integrated multi-formalism, multi-solution approach; the goal was to build a tool in which each model formalism or solver was, to the extent possible, modular, in order to maximize potential interaction. A modular modeling tool is possible because many operations on models, such as composition (described later), state-space generation, and simulation are largely independent of the formalism being used to express the model.

This approach has several advantages. First, it allows for novel combinations of modeling techniques. For example, to the best of our knowledge, the Replicate/Join model composition approach of [15] has been used exclusively with SANs. This exclusivity is artificial, and in the Möbius tool, Replicate/Join can be used with virtually any formalism that can produce a labeled transition system, such as PEPA[16].

The ability to add new components benefits researchers and users alike. Researchers can add a new component to the tool and expect it to be able to interact immediately with other components. Additionally, researchers have access to the work of others, and are able to extend and compare techniques. Users benefit by having access to the most recent developments in conjunction with previously existing techniques. They also benefit from having a modular, “toolbox” approach that allows them to choose the most appropriate tool or tools for the job.


Möbius Overview

The Möbius tool is an environment for supporting multiple modeling formalisms1. For a formalism to be compatible with Möbius, the developer must be able to translate a model built in his/her formalism into an equivalent model that uses Möbius components. Since models are constructed in specific formalisms, the expressive advantages of the particular formalisms are preserved. Because all models are transformed into Möbius components, all models and solution techniques in Möbius with compatible properties are able to interact with each other.

1 Technically speaking, the given definition is the definition of the Möbius framework, which is described in detail in [17]. However, for the sake of simplicity, we use the terms Möbius tool and Möbius framework interchangeably.

Framework components

To define the framework, it is necessary to identify and abstract the common concepts found in most formalisms. It is also necessary to generalize the process of building and categorizing models. The model’s construction process has been divided into several steps. Each step in the process generates a new type of model. The illustration shown in <xr id="fig:components" /> highlights the various model types and other components within the Möbius framework.


<figure id="fig:components">

Ct.svg


<xr id="fig:components" nolink />: Möbius framework components.
</figure>


The first step in the model construction process is to generate a model using some formalism. The most basic model in the framework is called an atomic model, and is made up of state variables and actions. State variables (for example, places in the various stochastic extensions to Petri nets, or queues in queuing networks) hold state information about a model, while actions (such as transitions in SPNs or servers in queuing networks) are the mechanism for changing model state.

If the model being constructed is intended to be part of a larger model, then the next step is to compose it with other models (i.e., atomic or composed models) to form a larger model. This is sometimes used as a convenient technique to make the model modular and easier to construct; at other times, the ways that models are composed can lead to efficiencies in the solution process. Examples include the Replicate/Join composition formalism[15], in which symmetries may be detected and state lumping may be performed. Although a composed model is a single model with its own state space, it is not a “flat” model. It is hierarchically built from submodels, which largely preserve their formalism-specific characteristics so that the composed model does not destroy the structural properties of the submodels. Note that the compositional techniques do not depend on the particular formalism of the atomic models that are being composed.

After a composed model is created, the next step is to specify some measures of interest on the model using some reward specification formalism, e.g., that is described in [18]. The Möbius tool captures this pattern by having a separate model type, called reward models, that augments composed models with reward variables.

The next step is typically to apply some solver to compute a solution to the reward model. We call any mechanism that calculates the solution to reward variables a solver. The calculation method could be exact, approximate, or statistical. Consequently, a solver may operate on a model independent of the formalism in which the model was constructed, so long as the model has the properties necessary for the solver.

The computed solution to a reward variable is called a result. Since the reward variable is a random variable, the result is expressed as some characteristic of a random variable. This may be, for example, the mean, variance, or distribution of the reward variable. The result may also include any solver-specific information that relates to the solution, such as any errors, the stopping criterion used, or the confidence interval. A solution calculated in this way may be the final desired measure, or it may be an intermediate step in further computation. If a result is intended for further computation, then the result may capture the interaction among multiple reward models that together form a connected model.

Tool description

The Möbius tool ensures that all formalisms translate model components into framework components through the use of the abstract functional interface (AFI)[19]. The AFI provides the common interface between model formalisms and solvers that allows formalism-to-formalism and formalism-to-solver interactions. It uses abstract classes to implement Möbius framework components. The AFI is built from three main base classes: one for state variables, one for actions, and one that defines overall atomic model behavior. Each of these classes defines an interface used by the Möbius tool when building composed models, specifying reward variables, and solving models.

The various components of a model formalism must be presented as classes derived from the Möbius AFI classes in order to be implemented in the Möbius tool. Other model formalisms and model solvers in the tool are then able to interact with the new formalism by accessing its components through the Möbius abstract class interfaces.

The main user interface for the Möbius tool presents a series of editors that are classified according to model type. Each formalism or solver supported by Möbius has a corresponding editor in the main interface. These editors are used to construct and specify the model, possibly performing some formalism-specific analysis and property discovery, and to define the parameters for the solution techniques. The tool dynamically loads each formalism-specific editor from a java archive (jar file) at startup. This design allows new formalisms and their editors to be incorporated into the tool without modification or recompilation of the existing code, thus supporting the extensibility of the Möbius tool.

Models can be solved either analytically/numerically or by simulation. From each model, C++ source code is generated and compiled, and the object files are packaged to form a library archive. These libraries are linked together along with the tool’s base libraries to form the executable for the solver. The executable is run to generate the results. The base libraries implement the components of the particular model formalism, the AFI, and the solver algorithms. The organization of Möbius components to support this model construction procedure is shown in <xr id="fig:architecture" />.


<figure id="fig:architecture">

Architecture.svg


<xr id="fig:architecture" nolink />: Möbius tool architecture.
</figure>


We believe that the majority of modeling techniques can be supported within the Möbius tool. By making different modeling processes (such as adding measures, composing, solving, and connecting) modular, we can maximize the amount of interaction allowable between these processes. That approach also makes it possible for the tool to be extensible, in that new atomic modeling formalisms, reward formalisms, compositional formalisms, solvers, and connection formalisms may be added independently. All of these features will be discussed in more detail in the remainder of this manual.

The atomic model represents a generalization of multiple modeling formalisms and is one of the main contributions of Möbius. The key elements of atomic models are state variables and actions, which are the subjects of the next two sections.

State variables

A state variable typically represents some portion of the state of a model, and is a basic component of a model. It can represent something as simple as the number of jobs waiting in a queue, or as complex as the state of an ATM switch.

Different formalisms represent state variables differently. For example, SPNs and extensions have places that contain tokens, so the set of values that a place can take on is the set of natural numbers. Colored GSPNs (CGSPNs)[3] have been extended so that tokens can take on a number of different colors at a place, making the value of a colored place a bag or multi-set. Queuing networks with different customer classes can have more complicated notions of state, such as those found in extended queuing networks[20], in which each job (customer) may have an associated job variable, which is typically implemented as an array of real numbers.

To capture and express all state variable types in existing formalisms in Möbius, we must create a generalized state variable that can be used to create specific state variables. By using a generalized state variable, we enjoy all the benefits of a framework we discussed earlier. Specifically, solvers or higher-level model types can interact with Möbius state variables (in the framework or the tool), instead of with the variety of different formalism state variables. Finally, any efficiencies that may be gained through any structural knowledge can be preserved through the use of properties.

Actions

An action is the basic model unit that changes the value of state variables in the Möbius framework, and is therefore the basic model unit that changes model state. An action corresponds to a transition in SPNs[4], GSPNs[10], and other extensions; to an action of an SPA (e.g., [5]); to an activity of a SAN[6]; or to a server of a queuing network (e.g., [1]), for example.

Actions are similar to state variables in the framework, in that their goal is to provide an abstraction of the various concepts of actions present in most formalisms. State-change mechanisms of atomic model formalisms in the Möbius framework may be implemented using a subset of the functionality provided by actions. Note that it is the restriction of the possible generality that often allows for efficiencies in solution methods. For example, restricting the delay times to be zero or exponential is useful because the underlying stochastic process is then Markovian. If the restrictions include restriction of the queuing formalism to “remove one job from one queue and add one job to another queue,” then a product form solution is possible.

Finally, like state variables, the action provides a common interface by which other model components (possibly of different formalisms) and solvers may interact in the Möbius framework. This allows for composition by synchronization, as is found in SPAs, stochastic automata networks (e.g., [21]), and superposed GSPNs (e.g., [2], [22]).


Enabling and completion rules for actions

The action chosen to complete in a certain configuration is based upon the action’s time distribution function for all the actions that are currently enabled, along with the fact that instantaneous actions have priority over timed actions. Currently Möbius supports the distribution functions discussed in Section 1.2.5.

<xr id="fig:action" /> shows the four possible time lines for the execution of a timed action. The shaded areas represent time during which the action is enabled. Each time line shows the action being enabled initially and an action time being scheduled. After the action time in (a), the action completes, and the new configuration of the model is such that the action is not enabled. After the action time in (b), the action completes, and the new configuration of the model is such that the action is still enabled. Before the action can complete in (c), the enabling conditions become false, and the action is aborted. Finally, before the activity can complete in (d), the activity is reactivated and therefore does not complete until its new activity time has elapsed.


<figure id="fig:action">

Actions.svg


<xr id="fig:action" nolink />: Execution of timed action in an atomic model.
</figure>


Firing time distributions for actions

This section describes the delay distributions that Möbius currently supports for actions. In the context of the Möbius tool, the random variables in this discussion can be thought of as describing the time until an action fires after becoming enabled, assuming the action is not aborted or reactivated.

For each distribution, you will find a table listing some relevant properties of the distribution, such as its mean and variance. For a given family of distributions (e.g., normal or gamma), there are usually several different ways to define, or parameterize, the density function. Thus, because there is often no universally accepted set of parameters for a given distribution, its parameterization may differ from source to source. For this reason, each table includes a listing of alternative parameters that may be used; if it is not readily clear, a mapping from one parameterization to another is also provided to show how to convert between the two. Finally, each table includes the parameters used by Möbius, and how these parameters map to other common parameterizations.

It is worth mentioning that some confusion over a continuous distribution’s parameters may be eliminated if the parameters are identified with their affect on the distribution rather than just with standard Greek letters. That is, if the parameters are defined correctly, regardless of the symbols they are given, they can be classified, on the basis of their physical or geometric interpretation, as being either scale or shape parameters. A scale parameter determines the unit of measurement of the values in the range of the distribution. A change in the scale parameter compresses or expands the density of the corresponding distribution without affecting its general form. A shape parameter, on the other hand, determines the basic form or shape of a distribution within the general family of distributions. A change in the shape parameter fundamentally affects a distribution’s properties (e.g., skewness). Some distributions, such as the exponential and normal, do not have a shape parameter, while others may have several (the beta has two).

More information about these distributions can be found in [23].


Binomial

A discrete random variable has a binomial distribution with parameters (n,p), where n is a positive integer and 0<p<1, if it represents the number of successes that occur in n independent trials, each of which results in a success with probability p and in a failure with probability 1-p. The probability mass function of a binomial random variable is given by

f(k)=\binom{n}{k}p^k(1-p)^{n-k}\quad k=0,1,\dots,n

As k goes from 0 to n, f(k) first increases monotonically and then decreases monotonically, reaching a maximum when k=\lfloor(n+1)p\rfloor. Also, note that when p=\frac{1}{2}, the distribution is symmetric about its mean (i.e., f(k)=f(n-k)). When p>\frac{1}{2}, the distribution is skewed to the right; it is skewed to the left when p<\frac{1}{2}.

When n is large, a binomial random variable with parameters (n,p) can be approximated by a continuous random variable having a normal distribution with the same mean and variance. This is known as the DeMoivre-Laplace limit theorem, and is actually a special case of the Central Limit Theorem. The normal approximation to the binomial will, in general, be quite good for n large enough that np(1-p)\ge 10.


<figtable id="tab:binomial">

<xr id="tab:binomial" nolink />: Summary of binomial distribution.
Mean Variance Alternative Parameters Parameters in Möbius
np np(1-p) (t,p) (T, P)\to(n,p)
</figtable>


Deterministic

An action with a deterministic delay will fire at the time indicated by its parameter, with probability 1. That is, there is no randomness to the firing time. Formally, if this deterministic time is T>0, the density function could be written as

f(x)=\delta(x-T)


where \delta is the Dirac delta function.


<figtable id="tab:deterministic">

<xr id="tab:deterministic" nolink />: Summary of deterministic action.
Mean Variance Alternative Parameters Parameters in Möbius
T 0 none Value \to T
</figtable>


Gamma

A random variable is said to have a gamma distribution with shape parameter and rate parameter (\alpha,\lambda), both positive, if its density function is given by

f(x)=\left\{\begin{array}{ll}
\frac{\lambda e^{-\lambda x}(\lambda x)^{\alpha-1}}{\Gamma(\alpha)} & x\ge 0\\
0 & x<0\end{array}\right.


where \Gamma is the gamma function defined as

\Gamma(\alpha)=\int_0^\infty e^{-y} y^{\alpha-1}dy


The gamma distribution is often parameterized with a shape parameter and a scale parameter, which is the reciprocal of the rate parameter. Thus in <xr id="tab:gamma" />, \beta=s=b=\frac{1}{\lambda}.


<figtable id="tab:gamma">

<xr id="tab:gamma" nolink />: Summary of gamma distribution.
Mean Variance Alternative Parameters Parameters in Möbius
\frac{\alpha}{\lambda} \frac{\alpha}{\lambda^2} (\alpha,\beta);(a,s);(k,b);(\gamma,\beta) (Alpha,Beta)\to(\alpha,\frac{1}{\lambda})
</figtable>


Exponential

An exponential random variable with parameter \lambda>0 has a probability density function


<equation id="eqn:exp">

f(x)=\left\{\begin{array}{ll}
\lambda e^{-\lambda x} & x \ge 0\\
0 & x<0
\end{array}\right.

</equation>

<xr id="eqn:exp" nolink />


The exponential distribution often arises in practice as the distribution of the waiting time until some event occurs, when the time until the event occurs does not depend on how long the wait has been. This is known as the memoryless property. In the context of action firing, the memoryless property states that the probability that an action fires in the next s time units given that it has been enabled for t time units is the same as the initial probability that the action would fire in the first s time units. Mathematically, if X is an exponential random variable representing the time until an action fires after becoming enabled


P\{X<s+t|X>t\}=P\{X<s\}\quad \mathrm{for~all}~s,t\ge 0


The exponential distribution is unique in that it is the only continuous distribution possessing the memoryless property. It is this property that permits a Markovian solution of models whose actions are exponential. This will be discussed in more detail later. Note also that the exponential distribution is a special case of the gamma distribution when \alpha=1. As with the gamma distribution, the exponential may be parameterized with \beta=\frac{1}{\lambda} (see <xr id="tab:exponential" />). Here \beta is the reciprocal of the rate \lambda and represents the mean of the exponential random variable.


<figtable id="tab:exponential">

<xr id="tab:exponential" nolink />: Summary of exponential distribution.
Mean Variance Alternative Parameters Parameters in Möbius
\frac{1}{\lambda} \frac{1}{\lambda^2} \beta Rate \to\lambda
</figtable>


Erlang

The Erlang distribution with parameters (n,\lambda) is a special case of the gamma distribution when \alpha is a positive integer (\alpha=n). Since \Gamma(\alpha)=(\alpha-1)! for integral values of \alpha, it follows that the density function of the Erlang distribution is given by

f(x)=\left\{\begin{array}{ll}
\frac{\lambda e^{-\lambda x}(\lambda x)^{n-1}}{(n-1)!} & x\ge 0\\
0 & x<0\end{array}\right.


Note that when n=1 this distribution degenerates to the exponential distribution. This fact leads to another interpretation of the Erlang distribution. That is, it represents the distribution of the sum of n independent, identically distributed exponential random variables (with parameter \lambda). Thus, the Erlang distribution may arise as the waiting time until n events occur, when the time between events is exponentially distributed (e.g., a Poisson process).


<figtable id="tab:erlang">

<xr id="tab:erlang" nolink />: Summary of Erlang distribution.
Mean Variance Alternative Parameters Parameters in Möbius
\frac{n}{\lambda} \frac{n}{\lambda^2} (k,\lambda);(m,\beta) (M,Beta)\to(n,\frac{n}{\lambda})
</figtable>


Beta

A random variable has a beta distribution with parameters \alpha and \beta, both positive, if its probability density function is given by

f(x)=\left\{ \begin{array}{ll}
\frac{1}{B(\alpha, \beta)}x^{\alpha-1}(1-x)^{\beta-1} & 0<x<1\\
0 & \mathrm{otherwise}
\end{array}\right.


where B is the beta function given by

B(\alpha, \beta)=\int_0^1 x^{\alpha-1}(1-x)^{\beta-1}dx


The beta function can also be written in terms of the gamma function, which was defined previously.

B(\alpha,\beta)=\frac{\Gamma(\alpha)\Gamma(\beta)}{\Gamma(\alpha+\beta)}


The beta distribution can be used when the firing time of an action can take on values in some finite interval [c,d], which can be mapped to the interval [0,1] by letting c denote the origin and taking d-c as a unit length. When \alpha=\beta, the beta density is symmetric about \frac{1}{2}, putting more probability mass in the region about \frac{1}{2} as the common value for the parameters increases. When \alpha>\beta, the density is skewed to the right (meaning that larger values are more likely), and it is skewed to the left when \alpha<\beta.


<figtable id="tab:beta">

<xr id="tab:beta" nolink />: Summary of beta distribution.
Mean Variance Alternative Parameters Parameters in Möbius
\frac{\alpha}{\alpha+\beta} \frac{\alpha\beta}{(\alpha+\beta)^2(\alpha+\beta+1)} (a,b) (Alpha1, Beta1)\to(\alpha,\beta)
</figtable>


Hyperexponential

Let X_i, i=1,\dots,n, be n independent exponential random variables, each with parameter \lambda_i, where \lambda_i \neq \lambda_j for i \neq j. Suppose also that there are n positive constants p_i such that 0<p_i<1 for i=1,\dots,n and \sum_{i=1}^n p_i=1. If the random variable X=X_i with probability p_i, then X is a hyperexponential random variable with n exponential stages and parameters (p_i,\lambda_i), i=1,\dots,n. That is, a hyperexponential random variable is a probabilistic choice among exponentials with different rates. In Möbius, the hyperexponential distribution for actions has n=2.

Formally, a hyperexponential random variable X has a probability density function defined as

f_X(x) = \sum_{i=1}^n p_i f_{X_i}(x)


where f_{X_i} is the probability density function for an exponential random variable with parameter \lambda_i, given by <xr id="eqn:exp" />.

Finally, a note is in order about the variance of the hyperexponential distribution. In general, it is not a weighted sum of the variances, as it is for the mean (see <xr id="tab:hyperexponential" />). It can be calculated using the definition of variance as

Var(X)=\sum_{i=1}^n p_i E[(X_i-E[X])^2]


where E[X]=\sum_{i=1}^n \frac{p_i}{\lambda_i} as in <xr id="tab:hyperexponential" />. It is known, however, that the coefficient of variation (CV), C_X=\frac{\sqrt{Var(X)}}{E[X]}>1. Thus, one of the characteristics of the hyperexponential distribution is that it has higher variability than the exponential distribution, which has CV equal to 1.


<figtable id="tab:hyperexponential">

<xr id="tab:hyperexponential" nolink />: Summary of hyperexponential distribution.
Mean Variance Alternative Parameters Parameters in Möbius
\sum_{i=1}^n \frac{p_i}{\lambda_i} See text (p_i,\mu_i);(\alpha_i,\lambda_i) (Rate1,Rate2,P)\to(\lambda_1,\lambda_2,p_1)*
</figtable>
* Only one p parameter is needed, since p_2=1-p_1


Negative Binomial

A discrete random variable is said to have a negative binomial distribution with parameters (s,p), where s is a positive integer and 0<p<1, if it represents the number of independent trials, each of which has a probability p of success, that must be performed until a total of s successful trials have occurred. The probability mass function of a negative binomial random variable is

f(k)=\binom{k-1}{s-1}p^s(1-p)^{k-s} \quad k=s,s+1,\dots


<figtable id="tab:negbinomial">

<xr id="tab:negbinomial" nolink />: Summary of negative binomial distribution.
Mean Variance Alternative Parameters Parameters in Möbius
\frac{s}{p} \frac{s(1-p)}{p^2} (r,p) (S,P)\to(s,p)
</figtable>


Geometric

A random variable has a geometric distribution with parameter p, 0<p<1, if it represents the number of independent trials, each of which has a probability p of being a success, that must be performed until a success occurs. A geometric random variable has a probability mass function given by

f(k)=(1-p)^{k-1}p \quad k=1,2,\dots


Note that a geometric random variable is just a negative binomial with s=1.

The geometric distribution is the only discrete distribution with the memoryless property, and thus a geometric random variable can be thought of as a a "discretized" exponential random variable.


<figtable id="tab:geometric">

<xr id="tab:geometric" nolink />: Summary of geometric distribution.
Mean Variance Alternative Parameters Parameters in Möbius
\frac{1}{p} \frac{1-p}{p^2} none P \to p
</figtable>


Uniform

A random variable is uniform with parameters \alpha and \beta, 0\le\alpha < \beta, if its density function is constant over the interval (\alpha,\beta).

f(x)=\left\{\begin{array}{ll}
\frac{1}{\beta-\alpha} & \alpha < x < \beta\\
0 & \mathrm{otherwise}
\end{array}\right.

The uniform distribution can be used, for example, to model the lifetime of an item that is equally likely to fail at all points in some interval of time. More precisely, the probability that the item will fail in some subinterval (c,d) of (\alpha,\beta) depends only on the length of the subinterval, d-c. Thus, the probability mass is distributed "uniformly" over the interval (\alpha,\beta).


<figtable id="tab:uniform">

<xr id="tab:uniform" nolink />: Summary of uniform distribution.
Mean Variance Alternative Parameters Parameters in Möbius
\frac{\alpha+\beta}{2} \frac{(\beta-\alpha)^2}{12} (a,b) (LBound, UBound)\to(\alpha,\beta)
</figtable>


Triangular

A triangular random variable with parameters (a,b,c), 0\le a<c<b, has a triangle-shaped density function given by

f(x)=\left\{\begin{array}{ll}
\frac{2}{b-a}(\frac{x-a}{c-a}) & a \le x \le c\\
\frac{2}{b-a}(1-\frac{x-c}{b-c}) & c<x \le b\\
0 & \mathrm{otherwise}
\end{array}\right.

If c=\frac{a+b}{2}, the distribution is symmetric about c (i.e., there is equal probability mass to the left and right of c). However, if c<\frac{a+b}{2} or c>\frac{a+b}{2}, the distribution is skewed to the left or right, respectively.

The triangular distribution could arise, for example, as the sum of two independent uniform random variables. If X and Y are independent random variables, both uniformly distributed on (0,1), then X+Y has a triangular distribution with a=0, b=2, and c=1.


<figtable id="tab:triangular">

<xr id="tab:triangular" nolink />: Summary of triangular distribution.
Mean Variance Alternative Parameters Parameters in Möbius
\frac{a+b+c}{3} \frac{a^2+b^2+c^2-ab-bc-ac}{18} none (A,B,C)\to(a,b,c)
</figtable>


Weibull

A random variable whose density function is given by

f(x)=\left\{\begin{array}{ll}
\frac{\alpha}{\beta}(\frac{x}{\beta})^{\alpha-1}\exp\{-(\frac{x}{\beta})^\alpha\} & x \ge 0\\
0 & x<0
\end{array}\right.


is said to be a Weibull random variable with shape parameter and scale parameter (\alpha,\beta) where \alpha,\beta>0. When \alpha=1 this distribution reduces to the exponential distribution with parameter \lambda=\frac{1}{\beta}.

The Weibull distribution was originally developed for the interpretation of fatigue data, but now it is widely used in engineering practice. In particular, it can arise as the distribution of the lifetime of an object, especially when the "weakest link" model is appropriate for the object (meaning that the object fails when any of its parts fail).


<figtable id="tab:weibull">

<xr id="tab:weibull" nolink />: Summary of Weibull distribution.
Mean Variance Alternative Parameters Parameters in Möbius
\beta~\Gamma(1+\frac{1}{\alpha}) \beta^2[\Gamma(1+\frac{2}{\alpha})-\Gamma^2(1+\frac{1}{\alpha})] (\beta,\alpha);(k,b) (Alpha, Beta)\to(\alpha,\beta)
</figtable>


Conditional Weibull

A random variable whose density function is given by

f(x)=\left\{\begin{array}{ll}
\frac{\alpha}{\beta}(\frac{x+t}{\beta})^{\alpha-1}\exp\{-[(\frac{x+t}{\beta})^\alpha - (\frac{t}{\beta})^\alpha]\} & x \ge 0, t \ge 0\\
0 & x<0, t \ge 0
\end{array}\right.


is said to be a Conditional Weibull random variable with shape parameter, scale parameter and elapsed time (\alpha,\beta,t) where \alpha,\beta>0 and t \ge 0. It is said to be conditional because of the fact that the distribution has already accumulated t hours of operation successfully. When t = 0, this distribution reduces to Weibull distribution. When \alpha=1 and t = 0, this distribution reduces to the exponential distribution with parameter \lambda=\frac{1}{\beta}.


<figtable id="tab:condweibull">

<xr id="tab:condweibull" nolink />: Summary of Conditional Weibull distribution. Note \alpha \ne 1
Mean Variance Alternative Parameters Parameters in Möbius
\frac{1}{ e^{-\left( \frac{t}{\beta}\right)^\alpha}} 
	  	    \left[ 
	  	    	  \frac{\beta}{\alpha} \Gamma\left(\frac{1}{\alpha}, \left(\frac{2t}{\beta}\right)^\alpha\right) +
	  	    	     t e ^{-\left(\frac{2t}{\beta}\right) ^ \alpha }
  	    \right] - (\beta,\alpha,t);(k,b,t) (Alpha,Beta,t)\to(\alpha,\beta,t)
</figtable>


Normal

A random variable is normally distributed, with parameters (\mu,\sigma^2), if its density is given by


<equation id="eqn:norm">

f(x)=\frac{1}{\sqrt{2\pi}\sigma}e^{-(x-\mu)^2/2\sigma^2} \quad -\infty<x<\infty

</equation>

<xr id="eqn:norm" nolink />


This density function is a bell-shaped curve that is symmetric about \mu. The scale parameter \sigma>0 represents the spread of the distribution; smaller values of \sigma correspond to more probability mass around \mu.

An important fact about normal random variables is that if X is normally distributed with parameters (\mu,\sigma^2), then Y=aX+b is also normally distributed with parameters (a\mu +b,a^2\sigma^2). A special case of this observation is when a=\frac{1}{\sigma} and b=\frac{-\mu}{\sigma}. Then Z=\frac{X-\mu}{\sigma} is normally distributed with parameters (0,1). Such a random variable Z is said to have the standard normal distribution.

Many random phenomena obey, at least approximately, the normal distribution; thus it arises quite often in practice. Some examples of this behavior include errors of various types and quantities that are the sum of a large number of other quantities (by virtue of the central limit theorem).

One final note is in order about the range of the normal distribution. In general, a normal random variable can take on any real-numbered value, as in <xr id="eqn:norm" />. However, if the normal distribution is used to represent a nonnegative quantity (i.e., time), as in Möbius, then its density should be truncated at x=0 so that only positive quantities are generated. This is done by letting q=\int_0^\infty f(x)dx where f is the original density function given in <xr id="eqn:norm" />. Note that q will be less than 1. Then the truncated density function, with range [0,\infty), is given by

f^*(x)=\left\{\begin{array}{ll}
f(x)/q & x \ge 0\\
0 & \mathrm{otherwise}
\end{array}\right.


This truncated density function for X is just a conditional density, conditioned on the event that X is nonnegative. The bell-shaped curve of the original density function is preserved, but its mean and variance are changed.


<figtable id="tab:normal">

<xr id="tab:normal" nolink />: Summary of normal distribution.
Mean Variance Alternative Parameters Parameters in Möbius
\mu \sigma^2 none (Mean, Variance)\to(\mu,\sigma^2)
</figtable>


Lognormal

A random variable X is lognormally distributed if Y=\ln(X) is normally distributed. The general formula for the density function of the lognormal distribution is

f(x)=\frac{e^{-(\ln x-\mu)^2/(2\alpha^2)}}{x\alpha\sqrt{2\pi}} \quad x\ge 0

where \mu is the scale parameter and \alpha>0 is the shape parameter.

The lognormal distribution is commonly used to model the lifetime of objects whose failure modes are of a fatigue-stress nature. Consequently, the lognormal is a good companion to the Weibull distribution when modeling such objects.


<figtable id="tab:lognormal">

<xr id="tab:lognormal" nolink />: Summary of lognormal distribution.
Mean Variance Alternative Parameters Parameters in Möbius
e^{\mu+\alpha^2/2} e^{2\mu+\alpha^2}(e^{\alpha^2}-1) (m,\sigma);(\mu,\sigma) (Mu,Alpha_Squared)\to(\mu,\alpha^2)
</figtable>


Model Types and Model Solutions

Once the modeler has made a number of atomic models as the building blocks of a large, complex model, she/he should be able to combine these submodels in order to construct the whole model. The next step is to define a set of measures on the model of interest. Finally, several solution methods should be used to compute the value of the measures and how they are affected by the changes in the model parameters. In this section, we describe these essential features as realized in various parts of the framework and the tool.

Atomic models

Atomic models are the basic building blocks of a model. Since multiple formalisms can be supported in Möbius, the user can use different formalisms to model different aspects of his/her model. New formalisms are constantly added into the tool as needed.

Composed models

The Möbius framework allows the construction of composed models from previously defined models. That allows the modeler to adopt a hierarchical approach to modeling, by constructing submodels as meaningful units and then placing them together in a well-defined manner to construct a model of a system. This is accomplished by the state-sharing approach, which links submodels together by identifying sets of state variables. For example, it is possible to compose two Petri net models by holding a particular place in common. That allows for interaction between the submodels, since both can read from and write to the identified state variable. This form of state sharing is known as equivalence sharing, since both submodels have the same relationship to the shared state variable. Note that a composition formalism maintains the dependencies among the actions and the state variables in the composed model based on the sharing approach and dependencies in the underlying submodels. Currently, the Möbius tool features two composed model formalisms that use equivalence sharing: Replicate/Join[15] [24] and Graph composition[24] [25] [26].


Replicate/Join

The Replicate/Join composed model formalism was originally conceived for SAN models (see [15]). It enables the modeler to define a composed model in the form of a tree, in which each leaf node is a predefined atomic or composed model, and each non-leaf node is classified as either a Join node or a Replicate node.

A Join is used to compose two or more submodels using equivalence sharing. A Replicate is used to construct a model consisting of a number of identical copies of its single child. Each child node of a Replicate or Join node can be a Replicate, a Join, or a single atomic or composed model.

Since the instances of a Replicate composed model are indistinguishable, its state can be represented in a lumped way as a sequence of numbers, each denoting the number of instances in each component state. Since the composed model presents its state to the Möbius tool through the AFI, it can keep details of symmetry-based reductions private. The rest of the Möbius tool does not know, and has no need to know, the details of such optimizations.


Graph composition

The Möbius tool supports a second composed model formalism called Graph composition[25] [26]. Whereas the structure of a Replicate/Join composed model is a tree, the structure of a Graph composed model is a graph, in which an arc linking two models indicates an equivalence-sharing relationship between the two models. As with Replicate/Join composition, lumping techniques based on computational group theory can be used to find all symmetries in the graph structure of the model automatically[25].

Reward models

Reward models[18] build upon atomic and composed models, equipping them with the specification of a performance measure. At this time we have implemented one type of reward model in the Möbius tool: a performance variable (PV). A PV2 allows for the specification of a measure on one or both of the following:

  • the states of the model, giving a rate reward PV, or
  • action completions, giving an impulse reward PV.


A rate reward is a function of the state of the system at an instant of time. An impulse reward is a function of the state of the system and the identity of an action that completes, and is evaluated when that particular action completes. A PV can be specified to be measured at an instant of time, to be measured in steady state, to be accumulated over a period of time, or to be time-averaged over a period of time. Once the rate and impulse rewards are defined, the desired statistics on the measure must be specified. The options include solving for the mean, variance, or distribution of the measure, or for the probability that the measure will fall within a specified range.

2 Note that although these variables are called performance variables, they are generic and can be used to represent either dependability or performability measures.

Studies

During the specification of atomic, composed, and reward models in the tool, global variables can be used to parameterize model characteristics. A global variable is a variable that is used in one or more models, but not given a specific value. Models are solved after each global variable is assigned a specific value. One such assignment forms an experiment. Experiments can be grouped together to form a study.

Solution techniques

The Möbius tool currently supports two classes of solution techniques: discrete event simulation and state-based, analytical/numerical techniques. Any model specified using Möbius may be solved using simulation. Models that have delays that are exponentially distributed, or have no more than one concurrently enabled deterministic delay, may be solved using a variety of analytic techniques applied to a generated state space. The simulator and state-space generator operate on models only through the Möbius AFI. Formalism-specific analysis and property discovery are performed by the formalism editor. Möbius allows formalism-specific solution techniques in the form of property-specific solvers. In order to evaluate the overhead resulting from the generality of the Möbius framework, we have compared the performance of the simulators in UltraSAN and Möbius[27]. We observed that the amount of overhead is negligible compared to runtime differences caused by other factors, such as the algorithm used by the solver and the optimization techniques used in the implementation.


State-space generator

The Möbius tool also supports a variety of analytical/numerical solvers. The first step in analytic solution with the Möbius tool is the generation of a state space, done by the state-space generator. Note that symmetries in the model are detected and leveraged by the various composition formalisms, and since the state-space generator accesses the model only through the AFI, it need not and does not know the details of these reductions. Furthermore, the state-space generator may be employed on any Möbius model. This allows the state-space generator to be generic, so it need not understand the semantics of a model on which it is operating. Once the state space is generated, any of several implemented analytical/numerical methods may be employed to solve for the required performance variables.


Simulation

The Möbius tool currently supports two modes of discrete event simulation: transient and steady-state. In the transient mode, the simulator uses the independent replication technique to obtain statistical information about the specified reward variables. In the steady-state mode, the simulator uses batch means with deletion of an initial transient to solve for steady-state, instant-of-time variables. Estimates available during simulation include mean, variance, interval, and distributions. Confidence intervals are computed for all estimates.

The simulator may be executed on a single workstation, or distributed on a network of workstations. The network may be a mixture of any supported architectures or operating systems. We accomplish this parallelism by running different observations on different workstations in the case of transient simulation, or by running different trajectories in the case of batch means. We have observed that this level of parallelism yields near-linear speedup.


References

  1. 1.0 1.1 F. Baskett, K. M. Chandy, R. R. Muntz, and F. G. Palacios. Open, closed, and mixed networks of queues with different classes of customers. Journal of the Association for Computing Machinery, 22(2):248–260, April 1975.
  2. 2.0 2.1 S. Donatelli. Superposed generalized stochastic Petri nets: Definition and efficient solution. In R. Valette, editor, Application and Theory of Petri Nets 1994, LNCS 815 (Proc. 15th International Conference on Application and Theory of Petri Nets, Zaragoza, Spain), pages 258–277. Springer-Verlag, June 1994.
  3. 3.0 3.1 G. Chiola, G. Bruno, and T. Demaria. Introducing a color formalism into generalized stochastic Petri nets. In Proc. 9th European Workshop on the Application and Theory of Petri Nets, pages 202–215, Venice, Italy, June 1988.
  4. 4.0 4.1 M. K. Molloy. Performance analysis using stochastic Petri nets. IEEE Trans. on Comp., 31:913–917, September 1982.
  5. 5.0 5.1 J. Hillston. A Compositional Approach to Performance Modelling. Cambridge University Press, Cambridge, 1996.
  6. 6.0 6.1 6.2 J. F. Meyer, A. Movaghar, and W. H. Sanders. Stochastic activity networks: Structure, behavior, and application. In Proc. International Workshop on Timed Petri Nets, pages 106–115, Torino, Italy, July 1985.
  7. W. H. Sanders. Integrated frameworks for multi-level and multi-formalism modeling. In Proceedings of the 8th International Workshop on Petri Nets and Performance Models, pages 2–9, Zaragoza, Spain, September 1999.
  8. B. R. Haverkort. Performability evaluation of fault-tolerant computer systems using DyQN-Tool+. International Journal of Reliability, Quality, and Safety Engineering, 2(4):383–404, 1995.
  9. G. Chiola, G. Franceschinis, R. Gaeta, and M. Ribaudo. GreatSPN 1.7: Graphical Editor and Analyzer for Timed and Stochastic Petri Nets. Performance Evaluation, 24(1–2):47–68, November 1995.
  10. 10.0 10.1 M. Ajmone Marsan, G. Balbo, and G. Conte. A class of generalized stochastic Petri nets for the performance evaluation of multiprocessor systems. ACM Transactions on Computer Systems, 2:93–122, May 1984.
  11. W. H. Sanders, W. D. Obal II, M. A. Qureshi, and F. K. Widjanarko. The UltraSAN modeling environment. Performance Evaluation, 24(1):89–115, October 1995.
  12. G. Ciardo and K. S. Trivedi. SPNP: The stochastic Petri net package (version 3.1). In Proceedings of the 1st International Workshop on Modeling, Analysis and Simulation of Computer and Telecommunication Systems (MASCOTS’93), pages 390–391, San Diego, California, January 1993.
  13. G. Ciardo, A. Blakemore, P. F. J. Chimento, J. K. Muppala, and K. S. Trivedi. Automated generation and analysis of Markov reward models using stochastic reward nets. In C. Meyer and R. J. Plemmons, editors, Linear Algebra, Markov Chains, and Queueing Models, pages 141–191. Heidelberg: Springer-Verlag, 1993.
  14. R. M. L. R. Carmo, L. R. de Carvalho, E. de Souza e Silva, M. C. Diniz, and R. R. Muntz. TANGRAM-II. In Raymond Marie, Brigitte Plateau, Maria Calzarossa, and Gerardo Rubino, editors, Computer Performance Evaluation: Modelling Techniques and Tools: Proceedings of the 9th International Conference, pages 6–18, St. Malo, France, June 1997.
  15. 15.0 15.1 15.2 15.3 W. H. Sanders and J. F. Meyer. Reduced base model construction methods for stochastic activity networks. IEEE Journal on Selected Areas in Communications, special issue on Computer-Aided Modeling, Analysis, and Design of Communication Networks, 9(1):25–36, January 1991.
  16. G. Clark and W. H. Sanders. Implementing a stochastic process algebra within the Möbius modeling framework. In Process Algebra and Probabilistic Methods: Performance Modelling and Verification: Proc. of the Joint International Workshop, PAPM-PROBMIV 2001, volume 2165 of Lecture Notes In Computer Science, pages 200–215, Aachen, Germany, September 2001. Berlin: Springer.
  17. D. D. Deavours, G. Clark, T. Courtney, D. Daly, S. Derisavi, J. M. Doyle, W. H. Sanders, and P. G. Webster. The Möbius framework and its implementation. IEEE Transactions on Software Engineering, 28(10):956–969, October 2002.
  18. 18.0 18.1 W. H. Sanders and J. F. Meyer. A unified approach for specifying measures of performance, dependability, and performability. In A. Avizienis, J. Kopetz, and J. Laprie, editors, Dependable Computing for Critical Applications, volume 4 of Dependable Computing and Fault-Tolerant Systems, pages 215–237. Heidelberg: Springer-Verlag, 1991.
  19. J. M. Doyle. Abstract model specification using the Möbius modeling tool. Master’s thesis, University of Illinois at Urbana-Champaign, January 2000.
  20. C. H. Sauer and Edward A. MacNair. Simulation of Computer Communication Systems. Prentice-Hall, Inc., Englewood Cliffs, New Jersey, 1983.
  21. B. Plateau and K. Atif. A methodology for solving Markov models of parallel systems. IEEE Journal on Software Engineering, 17(10):1093–1108, Aug 1991.
  22. P. Kemper. Numerical analysis of superposed GSPNs. In Sixth International Workshop on Petri Nets and Performance Models (PNPM ’95), pages 52–61, Durham, North Carolina, October 1995.
  23. A. Law and W. D. Kelton. Simulation modeling and Analysis. McGraw-Hill, 1991.
  24. 24.0 24.1 G. Clark, T. Courtney, D. Daly, D. D. Deavours, S. Derisavi, J. M. Doyle, W. H. Sanders, and P. G. Webster. The Möbius modeling tool. In Proceedings of the Ninth International workshop on Petri Nets and Performance Models (PNPM 2001), pages 241–250, Aachen, Germany, September 2001.
  25. 25.0 25.1 25.2 W. D. Obal II and W. H. Sanders. Measure-adaptive state-space construction methods. Performance Evaluation, 44:237–258, April 2001.
  26. 26.0 26.1 A. J. Stillman. Model composition within the Möbius modeling framework. Master’s thesis, University of Illinois at Urbana-Champaign, 1999.
  27. A. Williamson. Discrete event simulation in the Möbius modeling framework. Master’s thesis, University of Illinois at Urbana-Champaign, 1998.