Chord (peer-to-peer)

Chord is a structured peer-to -peer system, which in contrast to the majority of unstructured systems enables an efficient search for content. Like Gnutella is no Chord concrete implementation, but a protocol system. It is being developed at MIT and the source code of the current version is under the MIT license for free download and use available.

Structured Overlay Network

Above the actual transport layer ( TCP / IP) form a peer-to -peer systems, a so-called overlay network. Overlay network that describes the network topology of the individual peers, which are connected via the peer-to -peer system. The central question arises when adding and removing new peers ( network nodes): With whom the new node is to be connected? Just when deleting: War of the nodes may a connection between two others, so removing the node represents a deterioration of the quality of the overlay network?

In Gnutella, these questions are not asked, new nodes connect to indiscriminately with the nodes that can be determined by flooding the network. In contrast, a so-called Chord Chord ring is set up: All network nodes are arranged in a ring structure, where each node has connections with its predecessor, successor and of certain other nodes in the network. This ring structure allows (using a distributed hash table ) a binary search, which generally search cost of O ( log (n) ) is penalized in the search for content in the network. (In contrast, Gnutella eg caused immense search costs - about 70 % of the network load in Gnutella networks generated by searches. ) The downside is of course the more complex treatment of the ring structure - the addition and removal of network nodes in each case always ensure that the sure that the ring structure and the cross-references are maintained.

Content distribution

Only with the help of the ring structure no binary search is of course possible: In the naive approach would have - to search for content - the ring will run once in ascending order of GUIDs to an " exact match", ie a precise answer to a query to get. This is better than searching in an unstructured network, but still relatively " expensive".

Order, which is the identifying data the actual content to be broadcast in the network is correct, a global hash function is required. This assigns each data record ( for example, files in the case of file sharing ) is a unique ID that by using the SHA -1 hash function comes about (160 -bit key ). Now each node maintains a certain part of the global hash table, which is represented by an interval of the key. Each node that is now know for a portion of the data on which other nodes or intervals, these are respectively located.

The Chord network used for search and traversal of the ring references to remote nodes, called a finger table. The entries are set as follows: the i-th finger (i starts here with a 1 ) refers to the node that is responsible for the hash value of x 2 ( i -1). Thereby it is ensured that one can go much faster than a linear search for the desired item.