%% $Id: mc-nd.tex,v 1.2 2005/04/29 15:16:41 gokhale Exp $

\section{Performability Model of the Reactor Pattern}
\label{sec:reactor_perf}

In this section we describe the process of constructing a SRN
model for the reactor pattern. Towards this end, we first describe
the characteristics of the reactor pattern and the relevant 
performance measures. A SRN model of the reactor pattern is then 
presented along with a discussion of how the performance measures
can be obtained by assigning reward rates at the net level. We 
conclude the section with a discussion of possible extensions to
the SRN model. 

\subsection{Characteristics of the Reactor Pattern}
\label{sec:reactor_modeling}

In our performability model of the reactor, we consider a 
single-threaded, select-based implementation of the reactor
pattern with the following characteristics, as shown in 
Figure~\ref{fig:reactor_model_params}:  

\begin{figure}[ht]
\center{\includegraphics[width=3.2in]{eps/reactor_perf_model.eps}}
\bfcaption{Characteristics of the Reactor}
\label{fig:reactor_model_params}
\end{figure}

\begin{itemize}%\crunchlist
\item The reactor receives two types of input events with one
      event handler for each type of event registered with the reactor.
\item Each event type has a separate queue, which holds the incoming
      events of that type. The buffer capacity for the queue of type
      \#1 events is denoted $N_1$ and of type \#2 events is denoted $N_2$.
\item Event arrivals for both types of events follow a Poisson
      distribution with rates $\lambda_1$ and $\lambda_2$, while the
      service times of the events are exponentially distributed with
      rates $\mu_1$ and $\mu_2$. 
\item In a given snapshot, if the event handles corresponding to both 
      the event types are enabled, then they are serviced in no particular
      order. In other words, the order in which the events are handled 
      is non-deterministic.  
\item The failures in the reactor are assumed to occur only in the
      event handlers (e.g., due to memory corruption), in which case
      the event is simply purged from the system. The 
      failure rates when handling events of type \#1 and type \#2 are 
      $\gamma_1$ and $\gamma_2$, respectively. Other kinds of
      failures not considered here will cause the entire application
      to fail due to the single thread model.
\end{itemize}

The following performance metrics are of interest for each one of
the event types in the reactor pattern described in
Section~\ref{sec:reactor_modeling}: 

\begin{itemize}%\crunchlist
\item {\bf Expected throughput} -- which provides an estimate of the number
      of events that can be processed by the single threaded event
      demultiplexing framework. These estimates are important for
      many applications, such as telecommunications call processing.
\item {\bf Expected queue length} -- which provides an estimate of the
      queuing for each of the event handler queues. These estimates are
      important to develop appropriate scheduling
      policies for applications with real-time requirements.
\item {\bf Expected total number of events} -- which provides an estimate of
      the total number of events in a system. These estimates are also
      tied to scheduling decisions. In addition, these
      estimates will determine the right levels of resource
      provisioning required to sustain the system demands.
\item {\bf Probability of event loss} -- which indicates how many events
      will have to be discarded due to lack of buffer space. These
      estimates are important particularly for safety-critical
      systems, which cannot afford to lose events. These
      also provide an estimate on the desired levels of resource
      provisioning. 
\end{itemize}

\subsection{SRN Model of the Reactor Pattern}
\label{sec:srn}
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 a 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. An overview of SRNs can be
found in ~\cite{evol-spn}. 
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 our work is reported by Ramani {\em
et al.}~\cite{corba-perf}, where SRNs are used for the performance
analysis of the CORBA event service. The CORBA event service is 
yet another pattern that provides publish/subscribe services.   

{\bf Description of the net:} Figure~\ref{fig:pn_non_det} shows the 
SRN model for the Reactor pattern described in
Section~\ref{sec:reactor}. The net comprises of two parts. Part (a)
models the arrival, queuing, service and failures of the two types of events.
as explained below. Transitions $A1$ and $A2$ represent the  
arrivals of the events of types one and two, respectively. 
Places $B1$ and $B2$ represent the queue for the two
types of events. Transitions $Sn1$ and $Sn2$ are immediate transitions
which are enabled when a snapshot is taken. Places $S1$ and $S2$ 
represent the enabled handles of the two types of events, whereas 
transitions $Sr1$ and transition $Sr2$ represent the execution of
the enabled event handlers of the two types of events. An inhibitor
arc from place $B1$ to transition $A1$ with multiplicity $N1$ prevents 
the firing of transition $A1$ when there are $N1$ tokens in the 
place $B1$. The presence of $N1$ tokens in the place $B1$ indicates
that the buffer space to hold the incoming input events of the first
type is full, and no additional incoming events can be accepted.
The inhibitor arc from place $B2$ to transition $A2$ achieves
the same purpose for type two events.

\begin{figure*}[htb]
\centerline{\includegraphics[width=4.5in]{eps/srn-non-det.eps}}
\caption{SRN model of the Reactor pattern}
\label{fig:pn_non_det}
\end{figure*}

Part (b) models the process of taking successive snapshots and
non-deterministic service of event handles in each snapshot 
as explained below. Transition $Sn1$ is enabled when there 
are one or more tokens in place 
$B1$, a token in place $StSnpSht$, and no token in place $S1$. Similarly,
transition $Sn2$ is enabled when there are one or more tokens in place 
$B2$, a token in place $StSnpSht$ and no token in place $S2$. Transition
$T\_StSnp1$ and $T\_StSnp2$ are enabled when there is a token in either
place $S1$ or place $S2$ or both. Transitions $T\_EnSnp1$ and $T\_EnSnp2$
are enabled when there are no tokens in both places $S1$ and $S2$. 
Transition $T\_ProcSnp2$ is enabled when there is no token in place $S1$,
and a token in place $S2$. Similarly, transition $T\_ProcSnp2$ is enabled
when there is no token in place $S2$ and a token in place $S1$.
Transitions $Sr1$ and $TFail1$ are enabled when there is a token 
in place $SnpInProg1$,
and transitions $Sr2$ and $TFail2$ are enabled when there is a token in place 
$SnpInProg2$. Table~\ref{table:enable1} summarizes
the enabling functions for the transitions in the net shown in 
Figure~\ref{fig:pn_non_det}.         

\begin{table*}[hbt]
\begin{center}
\caption{Guard functions}
\label{table:enable}
\begin{tabular}{|c|c|} \hline
Transition & Guard function \\ \hline 
$Sn1$ & $((\#StSnpShot == 1) \&\& (\#B1 >= 1) \&\& (\#S1 == 0)) ? 1:0$ \\ \hline 
$Sn2$ & $((\#StSnpShot == 1) \&\& (\#B2 >= 1) \&\& (\#S2 ==0)) ? 1:0$ \\ \hline 
$T\_StSnp1$ & $((\#S1 == 1) || (\#S2 == 1)) ? 1:0$ \\ \hline 
$T\_StSnp2$ & $((\#S1 == 1) || (\#S2 == 1)) ? 1:0$ \\ \hline 
$T\_ESnpSht1$ & $((\#S1 == 0 \&\& (\#S2 == 0)) ? 1:0$ \\ \hline 
$T\_ESnpSht2$ & $((\#S1 == 0 \&\& (\#S2 == 0)) ? 1:0$ \\ \hline 
$T\_ProcSnp1$ & $((\#S1 == 1 \&\& (\#S2 == 0)) ? 1:0$ \\ \hline 
$T\_ProcSnp2$ & $((\#S1 == 0 \&\& (\#S2 == 1)) ? 1:0$ \\ \hline 
$Sr1$ & $(\#SnpInProg1 == 1) ? 1:0$ \\ \hline 
$Sr2$ & $(\#SnpInProg2 == 1) ? 1:0$ \\ \hline 
$TFail1$ & $(\#SnpInProg1 == 1) ? 1:0$ \\ \hline 
$TFail2$ & $(\#SnpInProg2 == 1) ? 1:0$ \\ \hline 
\end{tabular}
\end{center}
\end{table*}

\noindent
{\bf Dynamic evolution of the net:} We explain the process of taking a 
snapshot and servicing the enabled
event handles in the snapshot with the help of an example. We consider
a scenario where there is one token each in places $B1$ and $B2$. 
Due to the presence of tokens in places $B1$ and $B2$, and a token in
place $StSnpSht$, transitions $Sn1$ and $Sn2$ are enabled. Both these
transitions are assigned the same priority, and hence either one of
them can fire. Without loss of generality, we assume that transition
$Sn1$ fires first, which deposits a token in place $S1$. The presence
of a token in place $S1$ and place $StSnpSht$ enables transition  
$T\_StSnp1$. Also, transition $Sn2$ is already enabled. If transition
$T\_StSnp1$ were to fire before transition $Sn2$, the firing of
transition $Sn2$ would be precluded. In order to prevent this from
happening, transition $Sn2$ is assigned a higher priority than transition
$T\_StSnp1$, so that transition $Sn2$ fires before $T\_StSnp1$ when
both are enabled. Firing of transition $Sn2$ deposits a token in place
$S2$ which enables transition $T\_StSnp2$. Transitions $T\_StSnp1$
and $T\_StSnp2$ are both enabled, corresponding to the event handles
of both types of events. If transition $T\_StSnp1$ fires before 
$T\_StSnp2$, then event handle for the first type of event will
be executed prior to event handle for the second type of event.
On the other hand, $T\_StSnp2$ fires before 
$T\_StSnp1$, then event handle for the second type of event will
be executed prior to event handle for the first type of event.
Both the transitions $T\_StSnp1$ and $T\_StSnp2$ have an equal
chance of firing, and this represents the non-determinism in the
execution of the enabled event handles. Without loss of generality,
we assume transitions $T\_StSnp1$ fires depositing a token in 
place $SnpInProg1$, which enables transitions $Sr1$ and $TFail1$. 
Additionally, firing of transition $T\_StSnp1$ precludes the
firing of transition $T\_StSnp2$ and vice versa. 
Once transition $Sr1$ fires, a token is removed from 
place $S1$. If transition $TFail1$ fires prior to the
firing of transition $Sr1$, it indicates that a failure occurred 
before the event handle could complete execution, and this 
also removes a token from place $S1$. Thus, either transition
$Sr1$ and $TFail1$ fire and remove a token from place $S1$,
after which transition $T\_ProcSnp2$ fires and deposits
a token in place $SnpInProg2$.  A token in place $SnpInProg2$ enables
transition $Sr2$ and $TFail2$. $TFail2$ plays the same role
in the service of the event type \#2, as played by $TFail1$ in 
the service of the event type \#1. Firing of $Sr2$ or $TFail2$
removes the token from place
$S2$. Once $Sr2$ fires, there are no tokens in places $SnpInProg1$
and $SnpInProg2$, which enables transition $T\_EnSnp2$. The firing
of $T\_EnSnp2$ marks the completion of the present snapshot, and 
the beginning of the next one.  

\noindent
{\bf Assignment of reward rates:} The performance measures described in
Section~\ref{sec:reactor_metrics} can be computed  
by assigning reward rates at the net level as summarized in 
Table~\ref{table:rr}. The throughputs $T_1$ and $T_2$ are respectively
given by the rate at which transitions $Sr1$ and $Sr2$ fire. 
The queue lengths $Q_1$ and $Q_2$ are given by the average number 
of tokens in places $B1$ and $B2$, respectively. The total number of events
$E_1$ is given by the sum of the number of tokens in places $B1$ and $S1$.
Similarly, the total number of events $E_2$ is given by the sum of the
number of tokens in places $B2$ and $S2$. The loss 
probability $L_1$ is given by the probability of $N1$
tokens in place $B1$. Similarly, the loss probability $L_2$ is given by
the probability of $N2$ tokens in place $B2$.  

\begin{table}[htb]
\begin{center}
\caption{Reward assignments to obtain performance measures}
\label{table:rr}
\begin{tabular}{|c|c|} \hline
Performance metric & Reward rate \\ \hline 
$T_1$ & return rate($Sr1$) \\ \hline 
$T_2$ & return rate($Sr2$)  \\ \hline 
$Q_1$ & return ($\#B1$)  \\ \hline 
$Q_2$ & return ($\#B2$)  \\ \hline 
$L_1$ & return ($\#B1 == N1 ? 1:0$) \\  \hline 
$L_2$ &  return ($\#B2 == N2 ? 1:0$) \\ \hline 
$E_1$ & return($\#B1 + \#S1$) \\ \hline 
$E_2$ & return($\#B2 + \#S2$) \\ \hline 
\end{tabular}
\end{center}
\end{table}
