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

\section{Performance Evaluation 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 provide an overview of the Reactor pattern and describe its
characteristics and the relevant performance measures. A SRN model of
the Reactor 
pattern is 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 illustrative examples of how the
SRN model can be used to obtain an estimate of the performance metrics
as well as to analyze the sensitivity of the performance metrics 
for different values of the input parameters and configuration options. 

\input{reactor}

\subsection{Characteristics of the Reactor Pattern}
\label{sec:reactor_modeling}
We consider a single-threaded, {\em select}-based implementation of
the Reactor pattern with the following characteristics:

\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 Events of type \#1 are serviced with a higher priority over events of
      type \#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 corresponding to type \#1 is 
      serviced with a priority over event handle of type \#2 event. 
\end{itemize}

\subsection{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 since it is possible 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. Alternately, these
      also give an estimate on the desired levels of resource
      provisioning. 
\end{itemize}

\subsection{SRN Model}
\label{sec:srn}
\begin{figure*}[htb]
\centerline{\epsfig{figure=../Sigmetrics-2005/eps/srn.eps,width=4.5in}}
\caption{SRN model for the Reactor pattern}
\label{fig:srn}
\end{figure*}

Figure~\ref{fig:srn} shows the 
SRN model for the Reactor pattern with the characteristics described 
in Section~\ref{sec:reactor_modeling}.
Part (a) models the arrival, queuing and service of the two types 
of events, where 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 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 
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 arc from place 
$S1$ to transition $Sr2$
prevents the firing of transition $Sr2$ when there is a token in 
place $S1$. This models the prioritized service for the events of
type \#1 over events of type \#2.

Part (b) of the net models the process of taking successive snapshots and
prioritized service of the event handle corresponding to type \#1 events 
in each snapshot. 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$. 

The presence of a token in the place 
$SnpShtInProg$ indicates that the event handles that were enabled 
in the current snapshot are being serviced. Once 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*}

The process of taking a single snapshot is
modeled by the example SRN model presented in Figure~\ref{fig:srn}. 
The example figure considers the scenario where there is one token in each one of 
the places $B1$ and $B2$, and there is a token in the place 
$StSnpSht$. Also, there are no tokens in places $S1$ and $S2$.
In this scenario, transitions $Sn1$ and $Sn2$ are enabled. Both of
these transitions are assigned the same priority, and any
one of these transitions can fire first. Also, since these 
transitions are immediate, their firing occurs instantaneously. 
Without loss of generality, it can be assumed that transition $Sn1$ fires before 
$Sn2$, which 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 
the 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 when there is at least one event in
the queue. 

After both the event handles are enabled, transition 
$T\_SrvSnpSht$ fires and deposits a token in place $SnpShtInProg$. 
The presence of a token in the place 
$SnpShtInProg$ indicates that the event handles that were enabled 
in the current snapshot are being serviced.
The event handle corresponding to type one event is serviced first,
which causes transition $Sr1$ to fire and the removal of the token
from place $S1$. Subsequently, transition $Sr2$ fires and the event
handle corresponding to the event of type two is serviced. This
causes the removal of the token from place $S2$. 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 one. 

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$.  

%Jeff: For some reason, both of the tables that are references in section 4.3 appear
%on a different page in section 4.4. Can these be forced to be containedin secton 4.4?
\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*}

\subsection{Illustration}
This section illustrates how the SRN model presented in 
Section~\ref{sec:srn} can be used to determine the impact of
different parameters on the performance measures by careful
design of experiments. The SRN is solved using SPNP~\cite{spnp-new} to
obtain the expected values of the 
performance measures in all of the experiments described below. 

In the first experiment, the impact of 
buffer capacity is determined on the performance measures. For this experiment,
the values of the 
remaining parameters (except for the buffer capacities) are summarized 
in Table~\ref{table:param}. We consider two values of buffer capacities 
$N_1$ and $N_2$. In the
first experiment, there is a buffer capacity of $1$ for both types
of events, whereas the second experiment offers a buffer 
capacity of $5$ for both types of events. The performance metrics for 
both of the experiments are summarized in Table~\ref{table:perf}.  
Because the values of the parameters of the first type of events
($\lambda_1$, $\mu_1$ and $N_1$) are the same 
as the values of the parameters
for the second type of events ($\lambda_2$, $\mu_1$, and $N_2$), the
throughputs, queue lengths, and the loss probabilities are the same
for these two event types. 

The total number of events for the 
events of type \#2, denoted $E_2$ is slightly higher than the total 
number of events of type \#1, denoted $E_1$. Because the events of type \#1
are provided prioritized service over the events of type \#2,
on average it takes longer to service a type \#2 event 
than it takes to service a type \#1 event. This results
in a higher total number of events of the second type than of 
the first type. These observations hold for both values of maximum
buffer capacity. It can be observed that the loss 
probability is significantly higher when the buffer capacity is $1$ 
compared to the case when the buffer space is $5$. Also, due to the
higher loss probability, the throughput is slightly lower when
the maximum buffer capacity is $1$ than when the maximum buffer
capacity is $5$. 

\begin{table}[htb]
\begin{center}
\caption{Values of parameters}
\label{table:param}
\begin{tabular}{|c|c|} \hline 
Parameter & Value \\ \hline 
$\lambda_1$ & $0.400$/sec. \\ \hline 
$\lambda_2$ & $0.400$/sec. \\ \hline 
$\mu_1$ & $2.000$/sec. \\ \hline 
$\mu_2$ & $2.000$/sec. \\ \hline 
\end{tabular}
\end{center}
\end{table}

\begin{table}[htb]
\begin{center}
\caption{Impact of buffer capacity on performance measures}
\label{table:perf}
\begin{tabular}{|c|c|c|} \hline 
Performance measure & \multicolumn{2}{|c|}{Buffer space} \\ 
                    & $N_1=1$, $N_2=1$ & $N_1=5$, $N_2 = 5$ \\ \hline 
$T_1$ & $0.37$/sec. & $0.40$/sec \\ \hline 
$T_2$ & $0.37$/sec. & $0.40$/sec \\ \hline 
$Q_1$ & $0.065$ & $0.12$ \\ \hline 
$Q_2$ & $0.065$ & $0.12$ \\ \hline 
$E_1$ & $0.25$ & $0.32$ \\ \hline 
$E_2$ & $0.27$ & $0.35$ \\ \hline 
$L_1$ & $0.065$ & $0.00026$ \\ \hline 
$L_2$ & $0.065$ & $0.00026$ \\ \hline
\end{tabular}
\end{center}
\end{table}

The sensitivity of the performance measures to
the arrival rate of the events of type \#1 and type \#2 can be determined;
i.e., $\lambda_1$ and $\lambda_2$. 
For sensitivity analysis, the maximum buffer capacity can be set
for both event types to be $5$. Variations can be applied to both $\lambda_1$ and
$\lambda_2$ one at a time 
in the range of $0.5$/sec. to $2.0$/sec. to obtain the 
expected values of the performance
metrics by solving the SRN model shown in Figure~\ref{fig:srn}. 
The remaining parameters are held at the values reported in 
Table~\ref{table:param}. 

Figure~\ref{fig:sens_lam} shows the performance measures as a
function of $\lambda_1$ and $\lambda_2$. The plots in the left
column show the variation of the performance measures with
respect to $\lambda_1$, whereas the plots in the right column
show the variation of the performance measures with respect
to $\lambda_2$. Referring to the topmost figure in the left 
column, it can be observed that initially, 
the throughput of type one events is nearly the same as the
arrival rate of the events, indicating that the events are serviced 
at the same rate at which they arrive. However, as 
$\lambda_1$ increases, the throughput starts lagging the arrival rate,
which indicates that the service rate $\mu_1$ is not sufficiently
high to process the events at the rate at which they arrive. This 
may cause the event queue for type \#1 events to operate at 
full capacity for an extended period of time, which results in a 
rejection of the incoming input events. 

%Jeff: Figure 5 appears at the end of the paper, and not in the proper
%section to which it is referenced.  
\begin{figure*}[h]
\centerline{\hbox{
\psfig{file=../Sigmetrics-2005/eps/tputlam1.ps,height=2.5in,angle=270}
\hspace*{0.0in}
\psfig{file=../Sigmetrics-2005/eps/tputlam2.ps,height=2.5in,angle=270}
}}
\centerline{\hbox{
\psfig{file=../Sigmetrics-2005/eps/totlam1.ps,height=2.5in,angle=270}
\hspace*{0.0in}
\psfig{file=../Sigmetrics-2005/eps/totlam2.ps,height=2.5in,angle=270}
}}
\centerline{\hbox{
\psfig{file=../Sigmetrics-2005/eps/losslam1.ps,height=2.5in,angle=270}
\hspace*{0.0in}
\psfig{file=../Sigmetrics-2005/eps/losslam2.ps,height=2.5in,angle=270}
}}
\centerline{\hbox{
\psfig{file=../Sigmetrics-2005/eps/quelam1.ps,height=2.5in,angle=270}
\hspace*{0.0in}
\psfig{file=../Sigmetrics-2005/eps/quelam2.ps,height=2.5in,angle=270}
}}
\caption{Sensitivity of performance measures to arrival rates $\lambda_1$ and $\lambda_2$}
\label{fig:sens_lam}
\end{figure*}

Thus, a decrease in the 
rate at which the throughput increases is marked by an increase in
the loss probability of the events (as shown in the third plot in 
the left column) and an increase in 
the queue length (as shown in the fourth plot in the left column) 
in Figure~\ref{fig:sens_lam}. The left plot in the bottom
row represents the total number of events of each type as a function
of $\lambda_1$. The plot indicates that the total number of type \#2
events in the system increases as $\lambda_1$ increases. When $\lambda_1$
increases, the probability of having to service a type \#1 
event prior to servicing a type \#2 event 
in a given snapshot increases. Because events of type \#1 have priority
over events of type \#2, the type \#2 events tend to reside longer in the
system as $\lambda_1$ increases. Thus, although the throughput of 
type \#2 events is unchanged with respect to $\lambda_1$, the 
response time of a type \#2 event may increase.  
The plots in the right column of Figure~\ref{fig:sens_lam} indicate
that similar trends can be observed in the performance measures with
respect to $\lambda_2$, except that the roles of the two types of 
events are reversed. 

Similar sensitivity analysis can also be conducted with respect to the 
service rates $\mu_1$ and $\mu_2$. 
