% $Id: placement.tex 5107 2007-01-07 20:28:40Z gokhale $

\subsection {Improving Availability via Effective Replica Placement}
\label{sec:placement}

Requirement (3) in Section~\ref{sec:factors} states that the
dependability solution for enterprise DRE systems must minimize the
risk of simultaneous failures of replicated functionality.  This
requires effective replica placement algorithms, where replication is
provided for protection units that are modeled as failover units
described in Section~\ref{sec:modeling}.  

MDDPro uses GME's plugin capabilities to add model interpreters.  One
such model interpreter addresses the replica placement problem.  The
placement model interpreter provides a strategizable framework that
can use different constraint-based algorithms to determine an
effective replica placement plan to minimize the co-failure
probability of the system as a whole. 

\paragraph*{Formulation of replica placement problem instance in
  MDDPro.} 

In one instantiation of the formulation of the replica placement
problem within our strategizable model interpreter, we use
mathematical vectors to represent the distance of the replicas from
the primary component.  If the primary component has $N$ replicas,
then we form $N$ orthogonal vectors of $N$ dimensions, where each
vector represents the distance from the primary component node in
terms of hops captured in the shared risk group hierarchy.  The
magnitude of the resultant vector of the $N$ orthogonal vectors is
used to compare different deployment configurations and to find the
one that satisfies the constraints.

In this formulation of the placement problem algorithm, we have taken
care to avoid generation of some obviously undesirable deployment
configurations of the system.  For example, it does not allow
deployment configuration where all the replicas of a component are
located in the same host.  This is obviously undesirable in dependable
enterprise DRE systems because placing  multiple replicas in the same
host increases the risk of simultaneous failure of replicas.

\paragraph*{Prototype heuristic algorithm using distance metric.}

The prototype placement algorithm we have developed maximizes the
distance of the replicas from the primary replica but the pair-wise
distance between replicas themselves can be as small as just a single
hop.  Such a deployment configuration is skewed and
undesirable.  To alleviate the problem we apply a penalty function
to the resultant magnitude of the vector.  The penalty function gives
precedence to uniform deployment more than highly skewed deployment.
The penalty function that we have used is a simple standard deviation
of the distances of individial replicas from the primary component. 
We can generate better configurations by penalizing highly skewed
deployment configurations heavily compared to the more uniform
deployment configurations.  

For example, consider two resultant vectors $v1\{4, 4, 4\}$ and
$v2\{1, 1, 8\}$ having 3 dimensions.  Although the magnitude of v2 is
much greater than v1, the deployment configuration captured in v1 is
more resilient to failures than v2 because the replicas are spread
more uniformly around the primary unlike v2.   The heuristic algorithm
for the prototype implementation of the deployment algorithm is
illustrated in Listing~\ref{lst:heuristics}. 

\begin{Listing}
  \begin{singlespace}%
    \begin{Verbatim}[frame=single,fontsize=\relsize{-2}]

     1. Compute the distance from each of the replicas to the primary for a placement.   

     2. Record each distance as a vector, where all vectors are orthogonal. 

     3. Add the vectors to obtain a resultant.

     4. Compute the magnitude of the resultant.

     5. Use the resultant in all comparisons (either among placements or against a threshold) 

     6. Apply a penalty function to the composite distance (e.g. pairwise replica distance or uniformity)  

    \end{Verbatim}
    \caption{Replica Placement Heuristics}
    \label{lst:heuristics}
  \end{singlespace}
\end{Listing}

