% $Id: arch.tex 6501 2007-05-20 14:48:13Z gokhale $

\Section{Design of a Lightweight and Adaptive Real-time and
  Fault-Tolerant Middleware} 
\label{sec:arch}

This section focuses on the design of our adaptive and load-aware,
fault-tolerant and real-time middleware.  We begin by describing the
applications our middleware supports, the fault model we support,
followed by the design of the middleware architecture.

\SubSection{Real-time Application Model}
\label{appln-model}

Our XYZ fault tolerant and real-time middleware is geared to support
distributed real-time and embedded (DRE) systems comprising
predominantly soft real-time tasks, such as those found in domains
like shipboard computing.  We assume a resource rich environment for
the soft real-time tasks but not an overprovisioned system.
Applications comprising these tasks are generally software intensive.   
We assume that the soft real-time tasks illustrate periodic workloads
and hence soft deadlines associated with their periods.  Moreover, the
system tasks may illustrate different priorities relative to each
other.  These tasks are scheduled on different nodes of the DRE system
with tasks scheduled on each node using Rate Monotonic
Scheduling~\cite{LSD:89}, with higher rates mapped to higher
priorities.  We assume that each node has a single processor.  Any
hard real-time task within the DRE system is assumed to be provisioned
separately on dedicated hardware and software.   

We assume that the system tasks are deployed on a real-time CORBA
platform~\cite{CORBA:02c}, such as that provided by our TAO RTCORBA
middleware~\cite{Schmidt:02g}.  Since the client-side request rate
defines the priority at which the task will be executed at the server,
we use the RTCORBA's \texttt{CLIENT\_PROPAGATED} priority model.  This
is a reasonable assumption since we assume to know \emph{a priori} all
the soft real-time tasks in the DRE system and their rates.  As a
result, a global priority mapping can be realized based on all the
known rates.  Within RTCORBA, this implies the use of fixed priority
scheduling.  Since a single server process may handle multiple clients
with different priorities, we use the RTCORBA thread pool with lanes
feature supported by the TAO ORB.

\SubSection{Fault Model Assumptions}
\label{sec:fault-model}

Our research objective is to achieve fast failover trading off strong
replica consistency.  In this research we limit ourselves to
applications that are stateless though this restriction does not limit
the applicability of our research.

For our research on fault tolerant DRE systems described in this paper
we focus on fail stop models of failures.  We assume that both
processes and processors can fail, which can be detected by the system
components and the remainder of the system can continue executing.
Process faults are assumed to be more common caused primarily due to
some errors in the software.  Although we do tolerate processor
faults, we assume these are \emph{hard metal} faults \emph{i.e.}, it
is assumed that hardware faults are to be expected due to aging and
that such resources are periodically replaced.  Unpredictable behavior
of hardware is out of scope for our research.

We also assume that the distribution of faults is unpredictable.  We
assume that networks do not fail and that the networks provide
predictable performance in terms of network latencies.  This is a
reasonable assumption since the scale of our network is limited to the
size of a moderate metropolitan area sized network.

\SubSection{Fault Tolerance for Real-time CORBA Middleware}
\label{sec:ftrt_arch}

Our research objective was to develop middleware mechanisms that
provided fast failover after a failure in the system.  Since our DRE
applications were developed using RT-CORBA, our solutions were required
to integrate with the RT-CORBA specification.  In this section we
describe how we designed our solution.  We begin by discussing why
existing standard mechanisms, such as FT-CORBA~\cite{FTCORBA_chap:04}
have limitations when used in the context of real-time applications.
The limitations of FT-CORBA motivated our design described in
Section~\ref{sec:design}. 

\subsubsection{Limitations of Fault-tolerant CORBA}
\label{sec:ftcorba}

The Fault Tolerant CORBA (FT-CORBA)~\cite{FTCORBA_chap:04}
specification defines a standard set of interfaces, policies, and
services that provide robust support for applications requiring high
reliability.  The fault tolerance mechanism used to detect and recover
from failures is based on {\em entity redundancy}.  In FT-CORBA the
redundant entities are replicated CORBA objects.  Replicas of a CORBA
object are created and managed as a ``logical
singleton''~\cite{Vlissides:94} composite object. 

The addressing of this logical singleton is achieved using a FT-CORBA
standardized mechanism called the \emph{interoperable object group
reference} (IOGR), which is a collection of interoperable object
references (IORs).  The IOGR contains multiple
\texttt{tag\_internet\_iop} profiles any of which may be used to reach
individual replicas.  

FT-CORBA servers publish IOGRs that are used by clients.  Clients use
these IOGRs to invoke operations on servers.  The client ORB transmits
the request to the appropriate server object that handles the
request.  The client application need not be aware of the existence of
server object replicas.  If a server object fails, the client ORB
cycles through the object references contained in the IOGR until the
request is handled successfully by a replica object.  The references
in the IOGR are considered invalid only if all server replica objects
fail, in which case an exception is propagated to the client
application. 

Although FT-CORBA and its IOGR mechanism provides a standardized,
transparent mechanism for client-side failover in the event of a
server replica failure, there are a number of shortcomings with this
scheme:
\begin{BulletList}
  \item \emph{Heavy-weight solution} -- the FT-CORBA standard requires
  multiple different infrastructure artifacts to be present
  simultaneously to provide a full fault tolerance solution to
  applications.  This makes the solution heavy weight.  Additionally,
  it is possible that not all ORBs will implement the mechanisms, such
  as IOGRs, specified by the standard.  The heavy weight mechanisms
  provided by FT-CORBA adds an unpredictable overhead on the real-time
  system execution, which makes it difficult to schedule system tasks
  and may result in deadline misses.

  \item \emph{No seamless integration with RT-CORBA} -- the FT-CORBA
  standard was developed independently of the RT-CORBA standard.  For
  example there are no guidelines that describe how features in
  RT-CORBA, such as the priority models, the thread pool with lanes
  and banded connections, should be integrated with the FT-CORBA
  mechanisms, such as the IOGRs, the fault detection and state
  synchronization mechanisms.  As a result, it is extremely tedious
  and non intuitive to integrate the FT-CORBA mechanisms with the
  RT-CORBA mechanisms.

  \item \emph{Fixed and load-unaware replica selection} -- the FT-CORBA
  standard provides the IOGR mechanism for client-side transparent
  failover to server replicas.  Without any policy framework that
  provides a replica selection algorithm, however, ORBs tend to use a
  fixed scheme that cycles through the list of IORs in an IOGR in an
  \emph{ad hoc} manner \emph{e.g}, linear order.  It is conceivable
  that the failover target that the client uses from the IOGR does not
  provide a near-optimal choice in terms of resultant resource
  utilization on the server, which in turn may adversel affect the
  resulting system schedulability after failover.  Our empirical
  evaluation in Section~\ref{sec:eval} illustrates this case.  The
  load-unaware replica selection mechanisms in FT-CORBA result in
  these undesired consequences. 

  \item \emph{Non adaptive IOGR refresh} -- after recovery from
  failures, the FT-CORBA standard requires the replication manager
  entity to reestablish a new IOGR corresponding to the reconfigured
  server replication group.  Due to lack of any load-aware mechanisms
  and policies for replica selection, the new IOGR formed and pushed
  to the client-side ORB continues to incur the same limitations as
  discussed above.  
\end{BulletList}

These shortcomings of FT-CORBA for real-time applications motivated a
lightweight solution, which takes into account current and historical
load averages on the system resources to decide the selection of the
failover target.  Moreover, since our scheme is dependent on runtime
system utilization parameters, the solution uses an adaptive mechanism
to proactively inform the client-side ORB of the failover target
refreshing this information periodically.

\subsubsection{Design of XYZ}
\label{sec:design}

The limitations of the FT-CORBA solution described in
Section~\ref{sec:ftcorba} required us to design a solution that was
proactive, load-aware and did not statically fix the replica selection
order within a heavy weight IOGR mechanism.  Instead we decided to use
the simpler IOR mechanism in conjunction with the \emph{Portable
  Interceptors}~\cite{CorbaPI-Adopted:00} mechanism provided by all
CORBA compliant ORBs to provide a lightweight scheme.  By using an
interceptor mechanism, we continue to provide the client-side
transparency in the failover mechanism.  At the same time, the
interceptor mechanism is used in an intelligent manner to adaptively
refresh the failover target.

\paragraph{XYZ Architecture:}

\begin{figure}[htb]
  \centering
  \includegraphics[width=\columnwidth]{ftrt_arch}
  \caption{XYZ FT-RT Middleware Architecture}
  \label{fig:arch}
\end{figure}

Figure~\ref{fig:arch} depicts the XYZ architecture.  Our architecture
uses a variant of the \emph{Semi-active} replication model we
originally developed for FT-CORBA~\cite{Schmidt:02h}.  The different
components of the XYZ architecture are described below: 

\begin{BulletList}
  
 \item \emph{Client:} A client-side process consists of the client
 application developed using RT-CORBA.  Collocated with the client
 application is a client request interceptor developed using the
 portable interceptors and a forwarding agent running in a separate
 thread but same process.  The job of the forwarding agent is to find
 an appropriate server replica to failover when the client request
 interceptor catches a server failure exception.  Client requests are
 sent using RT-CORBA's \texttt{CLIENT\_PROPAGATED} priority model.

 \item \emph{Server:} A server-side process can contain one or more
 server CORBA objects, each performing a separate function, and is
 implemented using RT-CORBA.  Each server process is configured with
 RT-CORBA \emph{thread pools with lanes}.  The priority of the lanes
 correspond to the execution priorities for incoming client requests.
 Each of these server objects can be primaries or secondaries of their
 respective replication group.  Multiple such server processes can be
 deployed on a single host.

 \item \emph{Utilization monitor:} Every host runs a process called
 the utilization monitor.   The job of the utilization monitor is to
 monitor the host utilization as well as determine if the server-side
 processes are alive.  The utilization monitor opens a local socket
 connection to all the server processes on that host.  A failure of
 the connection is considered to indicate the failure of the process
 it is monitoring.  The utilization monitor periodically updates a
 middleware replication manager with the host utilization information
 as well as the liveness of the server processes hosted on that server
 host.  This periodic update with a minimum inter-update time serves
 as the heartbeat period for the middleware replication manager to
 detect the failure of the utilization monitor.  Additionally, if the
 utilization on that host goes beyond a set threshold, the utilization
 monitor will asynchronously inform the replication manager of the
 overload condition.

 \item \emph{Middleware replication manager:} The job of the
 middleware replication manager is to determine if any server process
 dies, and in turn keep track of the objects within that server that
 died and if any of them were primary replicas of their replica
 groups.  The replica manager uses the host utilization information it
 receives from individual utilization monitors to determine the right
 failover target for each replica group it manages.  In making such a
 decision, the replication manager ensures that after failover the
 client requests are schedulable on the failover target and that the
 overall utilization of operational resources in the system remains
 nearly uniform.  The middleware replication manager sends information
 about the appropriate failover object reference to the forwarding
 agents on the client-side whenever the information changes because of
 overload conditions or failures.

 \item \emph{Middleware replication manager backup:}  To handle
 failures of the replication manager, our design requires a
 replication manager backup.  Since the replication manager and its
 backup are deployed on dedicated resources, the load-agnostic and
 non-adaptive shortcomings of FT-CORBA do not manifest in this case.
 As a result it is reasonable to implement the fault tolerance of the
 replication manager using FT-CORBA mechanisms.  Thus, every
 utilization monitor maintains an IOGR for the replication manager
 group reference.  The communication between the forwarding agent and
 the middleware replication manager is also done using an IOGR.  The
 middleware replication manager follows semi-active replication, and
 the state of the middleware replication manager is synchronized
 across the middleware replication manager backups.  

\end{BulletList}

\paragraph{Replica Selection Mechanism:}
Algorithm~\ref{alg:repl_sel} describes the algorithm used by our
middleware replication manager to proactively select the failover
target for every server object running in the DRE system.  Our
approach is based on monitoring host utilization for all the hosts in
the DRE system.

\begin{AlgoFig}
\begin{Verbatim}[frame=single,fontsize=\relsize{-2}]
for every host, do
  expected util = current util
  for every process on host, do
    for every object i running in the process, do
      failover target of object i =
         host j with min util;
      expected util of host j += object i's load
\end{Verbatim}
\caption{Replica Selection Algorithm}
\label{alg:repl_sel}
\end{AlgoFig}

%%% folks, we need to add more description to this algo - andy

\paragraph{System operation and failure handling:}
The system operation and handling of failures in XYZ is illustrated in
the steps outlined below:

\begin{NumList}

\item Assume that the system components are deployed including the
servers, their replicas, the clients, utilization monitors and the
replication managers.  Also assume that all clients maintain
pre-established connections to all its replica IORs so that the
unpredictability in runtime connection establishment is prevented. 

\item Assume that the system is operating.  Periodically the
utilization monitors in each host send the host utilization
information to the replication manager.

\item The replication manager uses the utilization information to
select a potential failover target in the form of the process and its
host on which the replica object runs.

\item Periodically the replication manager pushes a rank ordered list
of replica IORs to each forwarding agent of a client it manages.  The
rank order indicates the order in which the client-side should try
failover targets.  Since the replication manager periodically updates
this information, the client is proactively supplied with fresh
information. 

\item A client makes a request to the server.  Assume that the server
process or the processor that hosts the server replica crashes.  The
client-side request interceptor will receive a standard CORBA server
failure exception.

\item The client-side interceptor will contact the forwarding agent
locally to obtain the IOR of the failover target.
  
\item Since the forwarding agent has proactively obtained a rank
ordered list of failover targets, it does not have to make a remote
call to the replication manager.  Instead it supplies the locally
available information to the client-side interceptor, which then
updates the client-side ORB with the new IOR to whom the request is to
be forwarded.

\item The client request executes on the failover target.  Since the
chosen failover target is guaranteed to executed the request within
the deadline, the client applications continue to obtain real-time
performance along with transparent fault tolerance.

\end{NumList}

\paragraph{Handling failures in the replication manager:}

The steps involved in handling replication manager failures is
discussed below:

\begin{NumList}
  
\item As shown in Figure~\ref{fig:arch} each utilization monitor is
connected to the middleware replication manager replica group using a
IOGR.  If the primary middleware replication manager fails, the
utilization monitor is automatically connected to one of the replica
middleware replication manager using the standard FT-CORBA failover
mechanisms. 

\item The middleware replication manager replicas periodically send
heartbeat messages to their designated neighbor.  If any replica
detects a failure, it sends a notification to an external recovery
manager to restart the failed replica middleware replication manager. 

\item If the primary middleware replication manager fails, one of the
secondary replicas will be promoted to be the primary using a semi
active replication approach we developed
previously~\cite{Schmidt:02h}. 

\item Since the IOGR of the replication manager group published to all
utilization monitors has the failover order built in, the utilization
monitors simply failover to the next replica in the IOGR.  This
assumption is valid since the replication managers are deployed on
dedicated hardware.

\item Periodically, the primary middleware replication manager has to
synchronize its state with its replicas.  External mechanisms, such as
reliable multicast may be used for the state transfers.  In
particular, the state that is synchronized includes runtime
information on the hosts, the server processes (and hence the server
objects) they run, the uilization information, and decisions on
failovers for different application replica groups.

\end{NumList}

It is conceivable that individual utilization monitors may fail on a
processor.  The fault tolerance for utilization monitors can use a
simplified semi-active replication by running replicas of the
utilization monitor on the same host.

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: "rtss2007"
%%% End: 
