InfoVis CyberInfrastructure - Chord Network Model

Chord [1] is another self-organizing structured P2P system model. This algorithm provides an implementation of the Chord primitive for the modeling of peer-to-peer networks and to perform search on such topologies. Chord provides a flexible, high-performance lookup primitive upon which functionality for efficient data location, anonymity, search, server selection, authentication etc. can be layered.

Chord uses consistent hashing to map nodes onto a circular identifier space (see Figure below). Nodes in a Chord graph have, as an additional attribute, a coordinate in a 1-dimensional virtual space (called a ring). When a new node N is added to the graph, the attributes of the nodes adjacent to N on the ring are used to add edges between N and k other nodes distributed in the space. Every node also keeps track of its predecessor and successor nodes. This provides significant advantage over standard consistent hashing which requires every node to track almost all other nodes.

Search in a Chord Graph

Performing efficient decentralized search is a fundamental problem in Peer-to-Peer systems. An effective search facility that uses only local information is essential for their scalability and, ultimately, their success. It is suggested that there is a strong relationship between network topology and search algorithms.

Chord provides an efficient method of locating documents while placing few constraints on the application that use it. Since each node maintains information about only a subset of the nodes in the graph, search moves progressively closer to identifying the successor with each step.

By search, we mean looking up a node given a start (source) node. The algorithm outputs the search cost involved in performing the search. The search cost refers to the number of messages passed in the system to find the target node. As explained above, a Chord graph consists of a virtual ring where every node knows how to reach its predecessor and k successor nodes on the identifier circle. To lookup the target node, message is passed to a node's successor which is closest to the destination node on the ring. Message is propagated progressively until the target node is found.

Applicable to network graphs only. Since placement of system resources at nodes is strictly controlled in a centralized fashion, network evolution has costly overhead. Centralized control limits network robustness and node autonomy.

Chord model is advantageous for building systems where controlled resource placement is a high priority, such as distributed file storage. Chord model provides sub-linear search mechanisms.

The algorithm can be used to generate Chord structured P2P graphs. These graphs can then be visualized and analyzed using Pajek or any other network visualization program.

In the IVC Software Framework, simply select Modeling > P2P > Structured > CHORD to generate a network. Recommended number of edges = log M, where M is the size of the network. Use Analysis > Search > CHORD Search to analyze the network.

This package was developed by George Fletcher and Hardik Sheth. Hardik Sheth integrated the code into the IVC Software Framework.