CHORD

CHORD
☰

Chord is a distributed lookup protocol, which implements a distributed hash table (DHT) and solves the fundamental issue in P2P applications of effectively locating the node that stores a particular data element. The algorithm uses consistent hashing to evenly distribute K objects across N nodes. It uses a hash function (usually SHA-1) to assign an m-bit identifier to each node (by hashing the IP and port number) and data key (by hashing the key). Identifiers are ordered on an identifier circle module 2m, the Chord ring, which is a circle of numbers of 0 to 2m-1. The data item with key k is assigned to the first node clockwise whose identifier is equal to or follows the identifier of k on the circle (successor(k)). For simple lookup, each node only needs to know its successor on Chord ring passing the query for identifier id around the ring until the successor(id) is found. In order to accelerate the lookup each node maintains additional routing info in a table, called finger table, with m entries: n.finger[i] = successor (n+2i-1).



How does this program work?

1. Insert m-Value and Node-IDs

  • Manually

    • You have to enter a value for the m-bit identifier and the identifiers of the nodes that are active in the network.

  • From file

    • You have to give only txt or xml file format. For convenience, you can download the example of file you want to see the template.

    • txt

      • The file should consist of all the vectors, each one of them must be in a line.

    • xml

      • This file should consist not only of all the vectors, but also: the number of execution iterations, the distance method (Euclidean or Manhattan) and the algorithm variant (Single link, Complete link, Centroid or Average). If the last is Centroid, the mode of calculations must be given (With/Without calculations of centroids).

You have to be careful when entering the node identifiers as the maximum number that you can use is 2m-1.
After you fill out everything you want, click on tab '2. Insert parameters'.



2. Insert parameters

This step is skipped by uploading an xml file!

At this point, all the parameters of the algorithm must be given except for the m-value and the active node IDs that have been already inserted.

  • Insert node’s Id for identifier of the data items

    • Enter the identifier of an active node in order to see the key identifiers for which this node is responsible.

  • Insert node’s Id for which you want to find the finger table

    • Enter the identifier of an active node for which you want the program to calculate the finger table. Every finger table maintains a number of m records such that the ith record of the table contains the identifier of the first node s:

    s = n.finger[i] = successor[(n + 2i-1 )mod2m], 1≤ i ≤m

    as well as the interval that is covered form each successor

    n.finger(i).interval = [(n + 2i-1) mod2m, (n + 2i) mod2m)

  • Insert node’s Id that searches for the item

    • Enter the identifier of an active node that searches for a particular data item.

  • Insert the item’s key

    • Enter the identifier of the data item which is being searched.

    Be careful: The identifier must be between 0 and 2m-1!

  • Insert the ID for the node that leaves the network

    • Enter the identifier of an active node that is going to leave the network.

    After leaving, the key identifiers for which the node was responsible will be assigned to the successor of the node.



After you fill out everything you want, click on tab '3. Results'.



3. Results

You see the results.