%% $Id: background.tex,v 1.9 2005/02/15 09:47:44 gokhale Exp $

\section{Background and Related Work}
\label{sec:background}

This section provides an overview of the Stochastic Reward Nets (SRN)
analytical modeling techniques we have used for performance modeling
of DHPS systems. We also describe the related work in this area.

\subsection{Stochastic Reward Nets (SRNs)}
\label{sec:srn_back}

This section describes the background on the Stochastic Reward
Net (SRN) modeling paradigm~\cite{evol-spn} used for performance analysis of
the Reactor pattern. SRNs represent a powerful
modeling technique that is concise in its specification and whose form
is closer to a designer's intuition about what a model should look
like. Since SRN specification is
closer to a designer's intuition of system behavior, it is also easier
to transfer the results obtained from solving the models and interpret
them in terms of the entities that exist in the system being
modeled. 

SRNs are an extension to Petri nets~\cite{peterson81}. 
Petri nets were proposed to represent formally the flow of control in a 
system. A Petri net is a directed graph which comprises two types of
elements, namely, {\em places} and {\em transitions}. A directed arc
connecting a place to a transition is called an {\em input arc}. 
Conversely, an {\em output arc} connects a transition to a place. Arcs
have a positive integer number called {\em multiplicity} associated 
with them, with the default multiplicity associated with an arc being 1.
Places can contain {\em tokens} that move from one place to another
through transitions. A transition is enabled when each of the places
connected to it by its input arcs have at least the number of tokens 
equal to the multiplicity of those arcs. When an enabled transition
fires, a number of tokens equal to the input arc multiplicity is 
removed from each one of the corresponding input places and a 
number of tokens equal to the output arc multiplicity is deposited 
in each one of the corresponding output places. The state of a 
Petri net with $p$ places is represented by a vector $(m_1,m_2,\dots,m_p)$,
where $m_i$ is the number of tokens in place $i$. The state of a 
Petri net is often referred to as its marking. When a Petri net is specified,
it can be made to start at a particular marking called the 
{\em initial marking}. Subsequently, the net evolves by the successive
enabling and firing of transitions which causes the tokens to flow
among places.

Stochastic Petri nets~\cite{evol-spn} extend Petri nets by allowing timed 
transitions that have {\em exponentially distributed} firing times. 
Generalized stochastic Petri nets (GSPNs)~\cite{evol-spn} also allow {\em
immediate} transitions which fire instantaneously. GSPNs include
an {\em inhibitor arc} which can also have a multiplicity 
associated with it. An inhibitor arc inhibits the transition 
it is connected to if the place it is connected to at its other end has a 
number of tokens equal to at least its multiplicity. The default
multiplicity is 1. A GSPN marking with at least one immediate transition
enabled is called a {\em vanishing marking}, and a marking
with no immediate transitions enabled is called a {\em tangible
marking}. 

Stochastic reward nets (SRNs) extend GSPNs further by allowing the association
of a reward rate to each tangible marking. The SRN models allow the concise 
specification of various reward functions. To extend the power of 
specification, SRN includes specification of {\em enabling (or guard)
functions} for each transition. The transition is enabled only if
the enabling function returns ``1.'' SRNs also allow marking dependent
arc multiplicities and enabling functions. Another feature of SRNs
is the provision of priorities and probabilities to determine which
of a set of simultaneously enabled transitions will fire first: the
transition with the highest priority is fired first. If the competing
transitions have the same priority the one to fire first is chosen
probabilistically. 

In a graphical representation of a SRN, a place
is represented as a circle, $n$ tokens in a place are represented by
$n$ dots or the number $n$ within the place, immediate transitions are
represented by thin lines, and exponentially distributed timed transitions
are represented by empty rectangles. An inhibitor arc is represented by a 
circle instead of an arrow at the terminating end. An arc with
multiplicity $m$ is represented by a ``$| m$'' on the arc, and an
arc with a marking dependent multiplicity function is indicated by
a ``N'' or an inverted ``N'' in it. The number of tokens in 
place $p$ is indicated as $p$. 

\subsection{Related Work}
\label{sec:relwork}
Stochastic reward nets have been extensively used for performance,
reliability and performability analysis of a variety of
systems~\cite{corba-perf,avail-vax,poll-perf,man-perf,queue-perf,rel-srn}.
The work closest to the proposed research is reported by Ramani {\em
et al.}~\cite{corba-perf}, where SRNs are used for the performance
analysis of the CORBA event service. UML representations of
application architecture have been mapped to Queuing
networks~\cite{williams98,hoeben00,menasce98,petriu00,pooley99} and
Petri nets~\cite{king99,bonda98}.

Several other analysis tools exist. The Virginia Embedded System
Toolkit (VEST)~\cite{VEST:03} is a model-based embedded system
composition tool that checks whether certain real-time, memory, power,
and cost constraints of DPSS applications are satisfied. The
Cadena~\cite{Hatcliff:03} tool suite provide static analysis,
model-checking, and other light-weight formal methods for component
middleware-based DPSS systems. While these tools are important, they
either deal with other systems features ({\em e.g.}, power
consumption) or have a narrow focus ({\em e.g.}, embedded
systems). Moreover, these tools are applicable once the system
composition decisions are made.

