Essay: Chord Algorithm
Essay: Chord Algorithm
The Chord algorithm is based on a single Hash function. All files and data in the Chord network have an identifier attached to it, which will be hashed by the function and the result will be attached to them in form of keys. Whenever a node needs file/data, it will use the hashing function to send a request. All participating nodes use this function to also hash their IP address and form a ring in ascending order of their hashed IP.
All existing nodes deal with the requests of any nodes before them. When a node wants to share a file or some data, it hashes the identifier to generate a key and sends its IP and the file to the next existing node. This information is then stored in that node. In this ways, all resources are indexed in a large distributed hash table across all participating nodes. When a node requests any data from its successor node the successor node replies with the IP of the node that holds the actual data in the form of key. In Chord, this key is then used by nodes to find out the actual IP address by using a finger table that each node maintains. It contains a list of keys and their relevant IPs and is organized in such a way that each of the nodes holds the IP of an exponential sequence of nodes that follow it.
Searching for a node is in Chord networks is a log(n) process. Since each node already knows the IP address of the next existing node in the ring, if the key it receives lies between k and the next existing node, then the successor is the next node. Otherwise, the finger table is searched to find out the closest predecessor of the key and the request is then moved to this node, which repeats the same procedure until the node containing the requested data of the file is found. The request contains the IP address of the requesting node so that the requested node can reply directly to the requesting node.
Whenever a node leaves or joins a network, a number of message transfers take place to re-distribute parts of the hash table. When a node joins a network, it hashes its own IP address and sends out a requested to any node to find its successor. It then sends a message to its predecessor node to inform it of the new successor. When a node leaves the networks, it informs the predecessor of its departure and sends its table to its successor. Since in both of these events, the values in the finger table will be wrong, therefore, each node in the ring, sends out a periodic message around the ring to find out about new nodes (Park, Yang, Park, Kang and Choi 2008).