%% $Id: mc.tex,v 1.11 2005/04/25 12:45:56 gokhale Exp $


\section{Performability Model of the Reactor}
\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, {\em 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=5in]{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 snapshot, when event handles corresponding to both event 
      types are enabled, the event handle corresponding to type \#1 event
      is serviced with a priority over event handle of type \#2 event. 
\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}

\subsection{Desired Performance Metrics}
\label{sec:reactor_metrics}

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}
\begin{figure*}[htb]
\centering\includegraphics[width=4.5in]{eps/pn.eps}
\caption{SRN Model of the Reactor Pattern}
\label{fig:srn}
\end{figure*}

\paragraph*{Description of the net:} Figure~\ref{fig:srn} shows the 
SRN model for the reactor pattern with the characteristics described 
in Section~\ref{sec:reactor_modeling}.
The top net models the arrival, queuing, service and 
failures of the two types 
of events. Transitions $A1$ and $A2$
represent the arrival of the events of type \#1 and \#2, respectively. 
Places $B1$ and $B2$ represent the queue for the two
types of events. Transitions $Sn1$ and $Sn2$ are immediate transitions
that are enabled when a snapshot is taken. Places $S1$ and $S2$ 
represent the enabled event handles of the two types of events, whereas 
transitions $Sr1$ and $Sr2$ represent the execution of
the enabled event handlers of the two types of events. Transitions
$TFail1$ and $TFail2$ represent the failures that may occur
during the service of the enabled event handles 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 
place $B1$. The presence of $N1$ tokens in 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 \#2 events. The inhibitor arcs from place 
$S1$ to transition $Sr2$ and $TFail2$ 
prevent the firing of transitions of $Sr2$ and $TFail2$ 
when there is a token in place $S1$. 
This models prioritized service for the events of
type \#1 over events of type \#2.

The bottom net models the process of taking successive snapshots.
Transition $Sn1$ is enabled when there is a token in place $StSnpSht$, 
at least one token in place $B1$, and no tokens in place $S1$. 
Similarly, transition $Sn2$ is enabled when there is a token 
in place $StSnpSht$, at least one token in place $B2$, and 
no tokens in place $S2$. Transition $T\_SrvSnpSht$ is enabled 
when there is a token in either one of the places $S1$ and 
$S2$, and the firing of this transition deposits a token in
place $SnpShtInProg$. Transitions $Sn1$ and $Sn2$ are assigned 
the same priority, and the priority of $Sn1$ and $Sn2$ is higher
than the priority assigned to transition $T\_SrvSnpSht$. 

The presence of a token in the place 
$SnpShtInProg$ indicates that the event handles that were enabled 
in the current snapshot are being serviced. After these event
handles complete execution, the current snapshot is 
complete and it is time to take another snapshot.
This is accomplished by enabling the transition $T\_EndSnpSht$.
Transition $T\_EndSnpSht$ is enabled when there are no tokens
in both places $S1$ and $S2$. Firing of the transition $T\_EndSnpSht$
deposits a token in place $StSnpSht$, indicating that the service
of the enabled handles in the present snapshot is complete,
which marks the initiation of the next snapshot. Table~\ref{table:enable} 
summarizes the enabling/\-guard functions for the transitions in the net.    

\begin{table*}[htb]
\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\_SrvSnpSht$ & $((\#S1 == 1) || (\#S2 == 1)) ? 1:0$ \\ \hline 
$T\_EndSnpSht$ & $((\#S1 == 0 \&\& (\#S2 == 0)) ? 1:0$ \\ \hline 
\end{tabular}
\end{center}
\end{table*}

\paragraph*{Dynamic evolution of the net:} The process of 
taking a single snapshot is
represented by the SRN model presented in Figure~\ref{fig:srn} as
follows. We consider a scenario where there is one 
token in each one of the places $B1$ and $B2$, no tokens in places $S1$ 
and $S2$, and a token in place $StSnpSht$.  
In this scenario, transitions $Sn1$ and $Sn2$ are enabled. Because both 
these transitions are assigned the same priority, any
one of these transitions can fire first. Also, since these 
transitions are immediate, their firing occurs instantaneously. 
Without loss of generality, we assume that transition $Sn1$ 
fires before $Sn2$, and this deposits a token in place $S1$. 

When a token is deposited 
in place $S1$, transition $T\_SrvSnpSht$ is enabled. In addition, 
transition $Sn2$ is already enabled. If transition $T\_SrvSnpSht$ were
to fire before transition $Sn2$, it would disable transition
$Sn2$, and prevent the handle corresponding to the second event
type from being enabled. In order to prevent transition $T\_SrvSnpSht$
from firing before transition $Sn2$, transition $T\_SrvSnpSht$
is assigned a lower priority than transition $Sn2$. Because transitions
$Sn1$ and $Sn2$ have the same priority, this also implies that 
transition $T\_SrvSnpSht$ has a lower priority than transition
$Sn1$. This ensures that in a given snapshot, event handles corresponding
to each event type are enabled, before the service of any
enabled event handle begins, when there is at least one event in
the queue. 

After both event handles are enabled, transition 
$T\_SrvSnpSht$ fires and deposits a token in place $SnpShtInProg$. 
The presence of a token in place 
$SnpShtInProg$ indicates that the event handles that were enabled 
in the current snapshot are being serviced.
The event handle corresponding to a type \#1 event is serviced first,
which causes transition $Sr1$ to fire resulting in the removal of the token
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. The firing of
transition $TFail1$ also removes the token from place $S1$. 
Subsequently, transition $Sr2$ fires and the event
handle corresponding to the event of type \#2 is serviced. This
causes the removal of the token from place $S2$. Transition $TFail2$
plays the same role as $TFail1$ in the service of  
type \#2 events. After both events
are serviced and there are no tokens in places $S1$ and $S2$, transition
$T\_EndSnpSht$ fires, which marks the end of the present snapshot and
the beginning of the next. 

\paragraph*{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 
given by the rate at which transitions $Sr1$ and $Sr2$ fire. 
The queue lengths $Q_1$ and $Q_2$ are given by the 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|c|} \hline
Performance metric & Notation & Reward rate \\ \hline 
Throughput of event type \#1 & $T_1$ & return rate($Sr1$) \\ \hline 
Throughput of event type \#2 & $T_2$ & return rate($Sr2$)  \\ \hline 
Queue length of event type \#1 & $Q_1$ & return ($\#B1$)  \\ \hline 
Queue length of event type \#2 & $Q_2$ & return ($\#B2$)  \\ \hline 
Loss probability of event type \#1 & $L_1$ & return ($\#B1 == N1 ? 1:0$) \\  \hline 
Loss probability of event type \#2 & $L_2$ &  return ($\#B2 == N2 ? 1:0$) \\ \hline 
Total number of events of type \#1 & $E_1$ & return($\#B1 + \#S1$) \\ \hline 
Total number of events of type \#2 & $E_2$ & return($\#B2 + \#S2$) \\ \hline 
\end{tabular}
\end{center}
\end{table*}

The SRN model can be solved easily by tools such as the Stochastic
Petri Net Package (SPNP)~\cite{spnp-new} to obtain the expected performance
metrics for different values of the parameters. 

\subsection{Model Variations}
In the model of the reactor pattern described above, the arrival, 
service and failure distributions are assumed to be 
exponential. For certain types of applications, this assumption
may not hold. For example, for safety-critical applications, 
events may occur at regular intervals, in which case the arrival
process is deterministic. In addition to the deterministic
distribution, the arrival, service and failure
processes may also follow
any other non-exponential or general distribution. 
There are two ways to consider non-exponential distributions in
the SRN model. In the first method, a non-exponential 
distribution can be approximated 
using a phase-type approximation~\cite{evol-spn}, and the resulting SRN 
model can then be solved using SPNP.  In the second method, the model can be 
simulated using discrete-event simulation incorporated in 
SPNP~\cite{spnp-new}.  
