\chapter{Two Rings}
\pagestyle{myheadings}
\markright{}

\label{tworings}
%\section{Two Rings}
The problem with the spatial approach as discussed earlier is that it might affect the load distribution. So using a completely spatially aware architecture to replace the existing mechanism of generating node identifiers using consistent hashing will not work because a few nodes will be extremely overloaded as compared to the rest of the nodes in the system. However, the scheme of having nodes arranged on the ring according to their actual locations such that nodes that are close to each other in Euclidean space will also be close to each other on the Chord ring, has some obvious advantages of lesser \textit{distance} to traverse for answering a query. This translates into better performance since now the query will be traversing lesser distances in the underlying real inter-network. This also means that a request packet will stay in the network for a smaller period of time, which eventually will lead to fewer packets being routed through the network at any given time. 

And so what we are proposing is a novel scheme which improves the performance of the system as a whole by incorporating the 'spatially-aware' scheme as a component. This is achieved in the following manner. 

Instead of having a system with just one ring with node identifiers that are generated using a consistent hashing, we now require all nodes to be a part of two rings. One of the rings is the one mentioned above, which we will refer to from this point on as the \emph{consistently hashed ring} or simply as the \emph{plain ring}. The other ring has the nodes arranged according to their actual locations, by using identifiers that are spatially aware. In the rest of the thesis we will refer, to this ring as the \emph{spatially aware ring} or just the \emph{spatial ring}.

The spatially aware ring is intended to be used as a cache. The purpose of this cache is to speed up access to documents that are frequently requested for by other nodes in the system. 

The protocols to handle nodes joining, leaving or failing have to be extended to incorporate this important change of the addition of another logical ring.

\section{Changes to Basic Chord Protocols}
\subsection{Joins}
Every node in the system is a part of these two virtual rings, which means that when a node \textit{joins} the system it acquires a pair of identifiers. One is the Chord identifier generated using consistent hashing. The other identifier is the one that will be used in the spatially aware ring and is generated by using a transformation on the actual location of the node. The protocol by which a node joins a Chord P2P system is then run twice for this new node, once for each of the 2 virtual rings using the respective identifier that this node is assigned for that ring. In this manner this node becomes a part of each of the two rings. Each node will therefore have to maintain complete local information, viz successor pointers, predecessor pointers and finger table and finger cache for each of the two rings that it is a part of. The relative positions of two nodes will more often than not be completely different for the two different rings.

\subsection{Leaves}
Similarly, when a node \emph{leaves} the system, the pointers to it in both rings will have to be updated. The leave operations in Chord will happen as usual in both the rings. These include moving of documents in the plain ring to their new successors and updating the successor and predecessor pointers for the neighbors of the node leaving the system in both the rings. The documents on the spatial ring are not moved to their successors since they are essentially replicas and are expendable.

All the system maintenance messages like \emph{stabilize, replace successor}, etc will always be between two nodes in the same ring.

A document when inserted in the system is placed only on the plain Chord ring. The spatially aware ring essentially serves as a \textit{cache}. Documents are moved over to this ring as and when they are accessed. 

When a query for a document is initiated, first the spatially aware ring is searched for it. If this document is present on its successor on the spatial ring, the request is served from this ring itself. If this document is not present on its successor on the spatially aware ring, the query is forwarded to the plain ring. The document will always be present on its successor on the plain chord ring because this ring holds \textit{all} the documents. The request is now served from the successor of the document in the plain ring, and the fact that there was a request for this particular document is recorded on the spatial ring. This information will be used later to possibly make copy of the requested document on its successor node on the spatial ring.

\section{Making Copies on the Spatial Ring}
This is done by periodically running a protocol on each node. Each node has an indication of the average load in the system. This average load is used to decide the threshold load on that node. It is typically within a constant number of standard deviations of the mean load. Now, if the load (number of requests serviced) of this node in the last period is lesser than the threshold load, it is considered to be a lightly loaded node. It can now make replicas of documents on its spatial part, based on the number of requests it has forwarded for each of them. The expected increase in the load on this node due to the creation of a replicas is taken to be the number of requests this node has forwarded for this replica. Replicas are created on the node in this manner for as long as the threshold set at the node allows. For example, if the creation of a copy on the spatial part of a node will send its expected usage for the next period to above the threshold, that copy is not created. This replication function is run on every node periodically, and replicas are created based on the requests forwarded by the successors of the original documents on the spatial ring and also the available capacity of the node to handle additional requests.\\

When this protocol is run again on a node that already has some replicas on it, first all the replicas are deactivated. A replica that is not active cannot be used to answer a request for the document it is the replica for. The mechanism that will be used to create replicas is almost exactly the same. The only difference is that the documents currently cached are also considered in the calculation of which documents should be placed on the spatial node. The counts used are the number of times these documents were accessed from the spatial part. If a document that is already present on a node needs to be cached, it is merely \emph{activated} and now it can be used to respond to queries.

\begin{figure*}[!tb]
\input epsf
\setlength{\epsfysize}{57mm}
\centerline{\epsffile{Figures/FindIn2Rings.eps}}
\caption{A \textit{find} query switching rings, because of a \textit{miss} in the spatial ring }
\label{findin2rings}
\end{figure*}

\section{Non-Uniform Distribution of Requests - Popularity of Documents}
The system that we are proposing can be especially useful in a system where there is a non-uniform distribution of requests for documents. 

Data access patterns for certain class of systems suggest that a very small portion of the data is accessed very frequently and most of the data is accessed very rarely. This means that, if we manage to keep the frequently accessed documents in the spatially aware ring, there will be sufficient improvement in the performance for most requests to overcome the occasional extra overhead of a document being needed to be fetched from the other ring. This overhead is obviously due to the prolonged search procedure that will have to be executed for such requests. The above statements can be verified using experiments based on simulations.

For example, for a sequence of $n$ requests, let $r$ be the hit ratio for requests being served from the spatial ring. Let the average distance traveled by a query in the spatial ring and the plain ring be $d_s$ and $d_p$, respectively. The sum of the distances traveled by all $n$ requests, in a system with 2 rings, will therefore be 
\begin{center}
$d_T = n*(r*d_s + (1 - r)*(d_s + d_p)) = n*(d_s + (1 - r)*d_p)$
\end{center}

The sum of the distances traveled by $n$ requests in a system with only a plain ring will be

\begin{center}
$d_T = n*d_p$
\end{center}

As is obvious from the above equations, for the system with two rings, every request has to go around the spatial ring. To make our technique effective, the hit ratio should be high enough such that $d_s - r*d_p < 0$ . If $d_s = r*d_p$, this means that there is no improvement in the performance and so all the extra effort being expended in maintaining two rings is not yielding any benefits. To make the extra work worthwhile, we need $d_s << r*d_p$, and thus $r$ should be sufficiently high. 

Preliminary experiments suggest that $d_s/d_p$ is approximately $0.5$ and so if we are able to realize a hit rate of about 80\%, we should be able to extract a significant improvement in performance.

Therefore, if trends for accesses on documents stored in this system are based on \textit{popularity of documents}, and most of the popular documents have replicas in the spatially aware ring, there will be an improvement in the performance of the system, because most of the requests will now be served off the spatially aware component of the system. 


