% -*- TeX-master: "report.tex" -*-

% Evaluation

This section presents performance evaluations for the two search
algorithms used in our system. 

\subsection{Consistent Hashing Comparison}
In order to compare consistent hashing with full membership against
data-oriented Chord with partial membership, we implemented a
simulation of each algorithm. Each simulation can show nodes joining,
inserting keys, searching for keys and failing or leaving. The
simulations record a number of performance measurements: the number of
messages sent and received by each node, the amount of routing data
stored by each node and the number of hops needed for each search.

For the lookup performance and bandwidth measurements shown in Figures
\ref{fig:Comp_Hops} and \ref{fig:Comp_Bandwidth}, the simulation
created $n$ nodes and picked random nodes to insert $n\cdot m$
objects, where $m$ is the average number of objects per node. Then,
each simulation had different randomly chosen nodes run a total of
$n\cdot s$ key lookups, where $s$ is the average number of searches
each node runs. The simulations used varying numbers of nodes with
$m=10$ and $s=10$. No nodes leave or fail throughout the experiment.

Figure \ref{fig:Comp_Hops} shows the average number of hops per search
for different membership sizes. As expected, the consistent hashing
algorithm has lower latency lookups than data-oriented Chord because
each node has full membership information. When each node has global
knowledge, the node performing the lookup can go directly to the
responsible node in one hop. With partial membership information like
in data-oriented Chord, lookups have to be routed to different nodes
that have more information in order to finally find the responsible
node. 

\begin{figure}[t]
  \centering
  \includegraphics[scale=0.3,angle=270]{figures/hops.ps}
  \caption{A comparison of the average number of hops a search takes
    as membership size grows for consistent hashing with full
    membership and data-oriented Chord.}
  \label{fig:Comp_Hops}
\end{figure}

Figure \ref{fig:Comp_Bandwidth} shows the bandwidth consumed by
consistent hashing with full membership and data-oriented Chord for
different membership sizes.  The advantage of data-oriented Chord can
be seen in the bandwidth usage graph; data-oriented Chord uses
significantly less bandwidth as the number of nodes increases than
regular consistent hashing. Consistent hashing with full membership
has a linear increase in traffic because each node that joins has to
notify every other node in the system. Failing or leaving nodes are
not included in the measurements.

\begin{figure}[t]
  \centering
  \includegraphics[scale=0.3,angle=270]{figures/messages.ps}
  \caption{A comparison of the average number of messages sent per
    node as the membership size grows for consistent hashing with full
    membership and data-oriented Chord. }
  \label{fig:Comp_Bandwidth}
\end{figure}

Another advantage of data-oriented Chord as compared to consistent
hashing with full membership is that data-oriented Chord has fate
sharing. Lookups only fail when they are for data stored on a failed node because there is no additional indirection. In contrast, in the full membership consistent hashing scenario, upon a
node failure, the files that become unreachable are not only the ones that it stores locally, but
also the files for which it keeps the metadata. This means that
even if a client storing a particular file is live, that file may
still not be reachable because the consistent hashing client who
stored the binding for the file failed. 

Figure \ref{fig:Cons_Failure} shows the hit rate for the files that were inserted in the system as the failure rate of the clients increases. The data was obtained by running simulations of our consistent hashing with full membership protocol on $1,000$ clients and $10,000$ files with random id-s. For each failure rate, we lookup all the files we inserted. We consider a lookup for a file to be successful if the metadata node storing the binding is alive. We measure the hit rate as the number of files with successful lookups divided by the total number of files in the system. We can see that the hit rate decreases linearly in the failure rate. This is obviously an undesired
behavior. One can mitigate the problem by using replication of the
bindings in the system, although the problem would not fully
disappear.

\begin{figure}[tp]
  \centering
  \includegraphics[scale=0.3,angle=270]{figures/rate-fail.ps}
  \caption{Hit rate depending on failure rate. }
  \label{fig:Cons_Failure}
\end{figure}


% fate sharing in chord whereas we do not have fate sharing in consistent
% hashing, percentage found
% message in, message out, nr of hops

\subsection{Data-oriented Chord Evaluation}

Using the simulation of data-oriented Chord, we measured the lookup
performance and bandwidth usage of the protocol as the number of
objects increases. The simulation used 100 physical nodes with varying
amounts of data. The simulation inserted $100\cdot n$ objects in total
on random physical nodes, where $n$ is the average number of objects
per node. The simulation then performed 100 searches for random keys.

Figure \ref{fig:Chord_Hops} shows the lookup performance of
data-oriented Chord as the number of objects in the system
increases. As expected, the latency stays about constant because
search latency depends on the number of physical nodes, which is
constant in this test. 

\begin{figure}[tp]
  \centering
  %will fix this graph
  \includegraphics[scale=0.3,angle=270]{figures/hops-load.ps}
  \caption{Lookup latency}
  \label{fig:Chord_Hops}
\end{figure}

Figure \ref{fig:Chord_Bandwidth} shows the bandwidth usage of
data-oriented Chord. The bandwidth measurements include 10 cycles of
stabilize and 100 random key searches. A stabilize cycle runs the
Chord stabilize algorithm on a virtual node on each physical node.
The bandwidth measurements do not include the amount of bandwidth
consumed inserting the objects.

\begin{figure}[tp]
  \centering
  %will fix this graph
  \includegraphics[scale=0.3,angle=270]{figures/messages-load.ps}
  \caption{Bandwidth}
  \label{fig:Chord_Bandwidth}
\end{figure}