Chord

Chord

Chord is a scalable peer to peer lookup service. Its main function is giving a key to map it to a node. The structured approach appeared due to the problems posed by already existing unstructured peer to peer systems, in which the placement of content was completely unrelated to the overlay topology. This unstructured solution meant that for content location a searching mechanism needed to be developed and usually it was not possible without implications regarding availability, scalability and persistence of the overlay network.

Structured systems try to address the scalability issues that unstructured systems were faced with. In a structured network the overlay topology is tightly controlled and files (sometimes pointers to files) are placed at specified locations. This means that the system provides a way of associating the content and location (usually a node address) in a form of a distributed route table so that queries can be efficiently routed to the node with the desired content. However the cost of providing a scalable solution for exact queries (this means a user should know the identifier of the requested data, it's not easy to search based on key terms) lies in the difficulty posed when maintaining the structure needed for efficiently routing messages when the leaving and joining rates for nodes are quite high.

Chord (and Pastry) is a representative of structured peer to peer systems ( Chord maintains also an associated finger table besides the distributed routing table). In Chord data location is implemented by identifying data items (files) with keys and by storing the (key, data) pairs at the node that the key maps to. Nodes are also identified by keys. So both nodes and files have keys associated by means of a deterministic function. Node identifiers are ordered in an identifier circle modulo 2^m. A key k is assigned to the first node whose identifier is equal to or follows k in the identifier space. Consistent hashing allows for load balancing as each node receives close to the same number of keys. Using this mode of assigning keys to nodes the only routing information needed is for each node to know its successor node on the circle. So when a query for a given key is made, it is passed around the circle via successor pointers until a node containing the key is encountered. This is actually the node the query maps to. In order to maintain load balance, in Chord (beside the map function) when a new node joins the network, a part of the keys previously assigned to new node's successor will become assigned to the new node. When a node leaves the network all the keys assigned to it will be reassigned to its successor.

One of the main advantages of Chord it's the simplicity. Only one data element per node needs to be correct for Chord to guarantee correct routing. However this does not mean fast routing. Further research papers proved that performance degrades gracefully when routing information becomes obsolete due to nodes joining and leaving and availability remains high, but only if nodes fail independently. There are some problems as even though the overlay topology is not based on the underlying IP network it is still possible for a single failure in the IP network to cause multiple links failure in the Chord overlay.

As said, Chord only needs the successor of a node for correct routing. To increase the speed Chord maintains additional routing information, a "finger table" in which each entry x in this table points to the successor n + 2x. So when a node n tries to perform a lookup for key k the finger table is read to identify the highest node n^next who?s ID is between n and k. If Chord can find it the lookup is repeated from node n^next. Otherwise it is repeated from n's successor.

From EDOS point of view, DHTs like Chord are needed to support KadoP because the functionality we need to provide regarding querying cannot be easily provided by the DHT (Chord only provides looking up data given a key). Chord appears less complex and needs less state information per node compared with other solutions but it does not consider network proximity when routing. And not least Chord has a high maintenance cost as each join/leave will induce state change on other nodes.

Links:

• http://pdos.csail.mit.edu/papers/chord:sigcomm01/chord_sigcomm.pdf
• Java implementation: https://accord.dev.java.net/
• http://cgi.cs.duke.edu/~priya/HyperNews/get.cgi/eval7.html

Type Software

Topics Wp4 Peer To Peer

About? http://www.pdos.lcs.mit.edu/chord/

{metadata}