\chapter{Design}
\pagestyle{myheadings}
\markright{}

\label{design}
In this chapter we introduce the preliminary design of our system. This explains in detail how we incorporate proximity information into Chord and also reveal some results that point to the tremendous potential of such a scheme. We also discuss how this first version of our system destroys the distribution of nodes about the Chord ring. This imbalance in node distribution leads to hot spots where some of the nodes are overloaded as compared to the rest of the nodes in the system. In the next chapter, we introduce our scheme where we have a system with 2 rings, one ring that incorporates proximity information (spatial ring) and the other that is similar to the one in chord (plain ring). This is intended to reduce the load on the hot-spots by delegating the responsibility to serve some requests to the plain ring. We present results that show that this method succeeds, in some cases, to alleviate the load imbalance created by the non uniform distribution of the node identifiers in the identifier space.

\section{Preliminary Design}
In the system we are proposing, the positions of the peer nodes along the circumference of the Chord ring should reflect their actual physical locations. Consequently, the distance between two nodes along the ring will be indicative of the real distance between the two peers in Euclidean space. This is achieved by using the location of the node to generate its identifier, which decides its placement on the Chord ring. Therefore, the only difference between Chord and the first version of the system we are proposing: instead of using consistent hashing on the address of the node, we use its physical location to generate its identifier which decides its place on the ring. All the other protocols for the working of the system and also the data structures used to accelerate routing will stay the same. This means that the performance guarantees that Chord gives will still be valid. Each request will be, on average, serviced within $O(logN)$ hops. But now the distance traveled in hops across the circumference of the ring is proportional to the actual distance between the source and destination of the hops. It is not any arbitrary distance as it is with Chord.

\subsection{Incorporating Proximity Information}
For our system, we have the location of a node specified as its coordinates on a plane. The identifiers for these nodes are generated using these coordinates. The two dimensional coordinates are mapped into a one dimensional scalar value which serves as its identifier. This mapping/transformation is done using methods such as bit interleaving or Hilbert Space filling curve. In our experiments we used the \textit{bit interleaving} to generate identifiers for the nodes in the system from their physical locations. For identifiers generated in this manner, nodes that are physically close to each other in space will have identifiers values that are close to each other. As a result, these nodes will be placed close to each other along the circumference of the ring. 

\subsection{Preliminary Results}
Preliminary experiments reveal that using geographical information to construct the Chord ring has a tremendous potential to improve performance of the protocol. For example, in our simulations we observed a performance gain of almost 100\% when we put the same event traces through the two systems and compared the results. But making this change also results in a severe load imbalance being introduced in the system. For details please refer to the \textbf{Experiments} chapter.

\section{The Problem}
The preliminary results reveal that simply incorporating proximity information in Chord will not be a complete solution. This is because of the fact that we are discarding the \textit{consistent hashing} approach of generating the node identifiers. Due to this change, the node identifiers are not evenly distributed throughout the identifier space. If the node identifiers are visualized as points along the circumference of a ring, there will be some parts of the ring that have a lot of points, and then there will be some parts that have no points at all. This in turn will affect how the resources these nodes are responsible for will be distributed among the nodes. For example, some nodes will be responsible for a lot of documents and others may have very few or no documents placed on them. This change may have adverse effects to the load balance in the system and cause it to deteriorate. This is one of the main concerns about such a system expressed by Ratnasamy et al in~\cite{openquestions}. Thus, there is a need for some load balancing mechanisms to be introduced to make the operation of the system feasible and at the same time retain a large percentage of the benefit that comes from making the system \textit{spatially aware}.

\section{Solutions based on Collision Avoidance (Reactive Load Balancing)}
Since Chord is based on a hashing scheme, the collision avoidance/ resolution schemes used normally in hashing would seem to offer promising solutions. But this is not the case. One would imagine schemes such as double hashing, or quadratic probing to work as follows. If a document arrives at a node that already has too many documents which means it is excessively loaded, because this node will now be serving requests for all these documents. The solution can be that some of these documents are moved to some other node. This other node will be found using the open addressing techniques used to resolve collisions during hashing. And if a query arrives at a node, which has moved some documents off to some other node, it will have to somehow forward the request to the node that actually stores that document. 

But this approach gives rise to a host of other problems. The first among these is keeping track of documents that have been moved off a node because of excessive load on that node. This means that either the loaded node keeps a pointer to the node that has the document or initiates the same collision resolution algorithm every time a query that comes to it finds that the resource (document) requested is not present. 

To do this in the presence of the possibility of all the nodes involved leaving and new nodes that might be successors of some of the documents joining the system make these possible solutions practically expensive to manage with strict requirements of correctness and consistency that this system has to live up to.

But on the other hand Chord as it is, without proximity awareness and without any kind of spatial information achieves a reasonably good balance of the load. This is done by taking advantage of the consistent hashing function in generating node and document identifiers.

Also this scheme does not accommodate the presence of an extremely popular document on a node. The rate of requests for this document at a single node may be sufficient to overload that node.

\section{Solutions based on a Single Spatially Aware Ring and Replication}
One more avenue we explored in attempting to come up with a load balancing scheme for the spatially aware system was {\it replication}.To relieve the load on the nodes that are overloaded, we could make replicas of documents that are stored on these nodes on other nodes that do not store too many documents and so are not inundated with queries. This would result in the load on the nodes that store a large number of documents being reduced, if the replicas of these documents were used to respond to a query.

The problem in this scheme is guaranteeing that if a replica of a document on an overloaded node cannot be found, it can still be served off its original location. Given the Chord routing protocol, there is no known set of nodes that a given request for a document always travels through. It is very hard, if not impossible, to place replicas of a document on some nodes other than the successor and then to guarantee that a replica will be used should the successor become overloaded. A request for a document may skip over all nodes that hold replicas and reach the successor of the document being queried. And if the successor is overloaded, it will not be able to serve this request.

The inherent problem with this scheme is the intention to use the successor of the document on the spatially aware ring, if a replica cannot be located. This successor may already be overloaded and unable to serve any more requests.