
% $Id: easm_replication.tex,v 1.3 2005/04/08 21:21:45 gokhale Exp $

\subsection{Fault-tolerance in EASM}
\label{sec:ft}

Till now we have considered that for an event type a sink sends requests
to a single rendezvous point which in turn forwards it to a source node
which contains the data. This approach has following problems:

\begin{itemize}
\item {\bf Hot-spot complexity:} Hot-spot complexity is the number of
         maximum of packets a single node handles in a WSN. If we have a 
         single rendezvous node handling data requests for a specific event
         type, the hot-spot complexity increases.
\item {\bf Rendezvous node energy depletion:} Like any other sensor node, 
         rendezvous nodes are energy-constrained and may not be able to carry 
         out routing functions if its energy level falls below a
         threshold. 
\item {\bf Node failure:} Rendezvous nodes might fail, data requests can not be
         routed to source node in this case.
\end{itemize}

We describe replication of rendezvous points that addresses each of the above
problems next. In replication we (1) identify the nodes which can serve
as rendezvous points, and (2) replicate the forwarding information to
the newly elected rendezvous points.  A rendezvous point replication
decision is taken by the current rendezvous point, which we call
initial rendezvous point.  It is based on its residual energy level
$e$, when the energy falls below $e/k$ (where $k$ is a configuration
parameter) the rendezvous point should be replicated since the current
point may not be able to perform the forwarding functions.

{\bf 1. Node identification:} The initial rendezvous point sends  
an {\em overload} message to all its one hop neighbors, indicating the start
of replication.  Each one hop neighbor conducts an election for identification 
of a node, which will be used as a new rendezvous point.  The election is an 
{\em n} hop broadcast starting from the node that initiated it, the nodes 
involved in the election respond with their residual energy level. Each
node participates in only one election to ensure one result per election.
Node with the highest energy level is elected as a rendezvous point, we call 
this node {\em forwarder}. All the other nodes that participated in
the election are called {\em interceptors}. The election result (the
node which was elected) is forwarded to the initial rendezvous point
as well as all the participating nodes. A participating node, which we
call an {\em interceptor} stores the election result (location of {\em
  forwarder}). 

{\bf 2. Node Replication:} On receiving the election result from each
one-hop neighbor, the initial rendezvous point sends the forwarding
information to the elected forwarders.  Thus each forwarder can
route the data requests it receives to appropriate source
node. Further, for each neighbor it sends the election results of all
the other neighbors which in turn is forwarded to the interceptor nodes.

Thus, we have interceptor nodes, which can intercept and send the data 
requests to their forwarder, and forwarders which have the 
forwarding information of source node they serve.  When an interceptor 
receives a packet (data request), the packet is forwarded to its forwarder
instead of the earlier initial rendezvous point. Since every node is an 
interceptor or a forwarder within {\em n - 1} hop radius of the
initial rendezvous point a packet is always intercepted and forwarded
before it can reach rendezvous point.  If a forwarder fails, the
interceptor chooses a new forwarder from its list making the scheme
robust and fault-tolerant.  The same approach can be used to handle
overloading of each forwarders. Thus the system can adapt scalably for
increased load conditions.  

Replication reduces hot-spot complexity as the total load gets divided between
as many newly elected forwarders. By ensuring that multiple forwarders
are maintained with each interceptor the system handles forwarder
failures by choosing a different forwarder.  The same replication
scheme may be used for replication of grid centers.
