%% $Id: mc-nd.tex,v 1.7 2005/12/09 12:39:19 gokhale Exp $

\section{Developing a Performance Model of a Middleware Building Block} 
\label{sec:reactor_perf}

In this section we describe the process of constructing a Stochastic
Reward Net (SRN)~\cite{rel-srn} model of a middleware building block.
We focus on the reactor pattern, which provides synchronous
demultiplexing and dispatching capabilities by decoupling these from
event handling.  Such decoupling is useful for building event-driven
systems. Initially we 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 the scalability
challenges involved in constructing the performance models.   

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

Event demultiplexing, dispatching and event handling is a hallmark of
event-driven systems.  The development of these systems is
increasingly relying on the use of well-documented
patterns~\cite{Vlissides:94,Schmidt:00a}.  The use of patterns offers
the potential for improving the reliability as well as enabling faster
time-to-market by fostering reuse.  Fundamental to the design and
development of event-driven systems is the Reactor
pattern~\cite{Schmidt:00a}.  Therefore, performance analysis of the
event-driven aspects of systems boils down to the performance analysis
of the reactor pattern.  This section therefore provides background
information on the reactor pattern and its dynamics.

Figure~\ref{fig:mw-demux} depicts a typical event demultiplexing and
dispatching mechanism documented in the reactor
pattern~\cite{Schmidt:00a}.  The application registers an event
handler with the event demultiplexer and delegates to it the
responsibility of listening to incoming events.  On the occurrence of
an event, the demultiplexer dispatches the event by making a callback
to the correct application-supplied event handler.  This is the idea
behind the reactor pattern, which provides synchronous event
demultiplexing and dispatching capabilities. 

\begin{figure}[htb]
\begin{center}
\includegraphics[width=2.3in]{../Sigmetrics-2005/eps/demux.eps}
\bfcaption{Event Demultiplexing Pattern}
\label{fig:mw-demux}
\end{center}
\end{figure}

Figure~\ref{fig:reactor_dynamics} illustrates the reactor pattern
dynamics. We categorize these dynamics into two phases described below.

\begin{figure}[htb]
\begin{center}
\includegraphics[width=3.3in]{eps/reactor_dynamics.eps}
\bfcaption{Reactor Pattern Dynamics}
\label{fig:reactor_dynamics}
\end{center}
\end{figure}

\begin{enumerate}
  \item {\bf Registration phase:} In this phase all the event handlers
  register with the reactor associating themselves with a particular
  event type they are interested in.  Event types usually supported by
  a reactor are input, output, timeout and exceptions.  The reactor
  will maintain a set of handles corresponding to each handler
  registered with it.
  \item {\bf Snapshot phase:} Once the event handlers have completed
  their registration, the main thread of control is passed to the
  reactor, which in turn listens for events to occur. A snapshot is
  then an instance in time wherein a reactor determines all the event
  handles that are enabled at that instant.  For all the event handles
  that are enabled in a given snapshot, the reactor proceeds to
  service each event by invoking the associated event handler. There
  could be different strategies to handle these events. For example, a reactor
  could handle all the enabled events sequentially in a single thread
  or could hand it over to worker threads in a thread pool. After all
  the events are processed, the reactor proceeds to take the next
  snapshot of the system.
\end{enumerate}

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

In our performance 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.  
\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 of 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{ramani00,avail-vax,poll-perf,man-perf,queue-perf,rel-srn}.
The work closest to our work is reported by Ramani {\em
et al.}~\cite{ramani00}, 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.   

\paragraph*{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, and service 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/pn-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$ is enabled when there is a token 
in place $SnpInProg1$, and transition $Sr2$ is enabled when there is 
a token in place $SnpInProg2$. Table~\ref{table:enable} 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 
\end{tabular}
\end{center}
\end{table*}

\paragraph*{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$.
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$, after which transition $T\_ProcSnp2$ fires and deposits
a token in place $SnpInProg2$. A token in place $SnpInProg2$ enables
transition $Sr2$. Firing of $Sr2$ 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.  

\paragraph*{Assignment of reward rates:} The performance measures
described in Section~\ref{sec:reactor_modeling} 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}

\subsection{Scalability Challenges}
\label{sec:srn-scalability}
The above sections describe the manual process of constructing a SRN
model for the reactor pattern and assigning reward rates to obtain the
different performance measures.  Many different variations of the
reactor pattern are possible depending on the configuration parameters
used.  These variations stem from the different event demultiplexing
and event handling strategies used in a reactor.  For example, in
network-centric applications, networking events can be demultiplexed
using operating system calls, such as {\tt select} or {\tt poll}.  For
graphical user interfaces (GUIs), these events could be due primarily
to mouse clicks and can be handled by GUI frameworks like Qt or Tk.
On the other hand, the event handling mechanisms could involve a
single thread of control that demultiplexes and handles an event, or
each event could be handled concurrently using worker threads in a
thread pool or by thread on demand. 

Other variations stem from the number of event types handled, the
buffer space available for queuing events, input workloads and event
service rates.  To enable design-time performance analysis for an
application employing a variant of the reactor pattern, the SRN model
of the variant needs to constructed manually.  This process is
cumbersome, tedious and time-consuming.  These challenges are further
complicated when systems are composed of several middleware building
blocks.  There is a need to automatically generate performance models
for different variants based on the performance model, which captures
the invariant characteristics of the pattern and specializing them
with the possible variations.  Section~\ref{sec:mdd} describes our
solution to address these challenges.
