(14th MAY 2019)
AboutChord protocol, I will introduce one of traditional P2P protocol, Chord in today. It uses a flat key space to associate the mapping between network nodes and data objects/files/values. The node address as well as the data object/file/value is mapped to a logical identifier in the common key space using a consistent hash function. Both these mappings should ensure that the keys are distributed roughly equally among the nodes. This also insures that with high probability, the overhead of key management when nodes join or leave the P2P network is low. Specifically, when a node joins or leaves the network having n nodes, only O 1/n keys need to be moved from one location to another. The Chord key space is flat, thus giving applications flexibility in mapping their files/data to keys. Chord supports a single operation, lookup, which maps a given key x to a network node. Specifically, Chord stores a file/object/value at the node to which the file/object/value’s key maps.
There are two steps.
1. Map the object/file/value to its key in the common address space.
2. Map the key to the node in its native address space using lookup. The design of lookup is the main challenge.
In Chord, a node’s IP address is hashed to an m-bit identifier that serves as the node identifier in the common key space. Similarly, the file/data key is hashed to an m-bit identifier that serves as the key identifier. m is sufficiently large so that the probability of collisions during the hash is negligible. The Chord overlay uses a logical ring of size 2 powered m. The identifier space is ordered on the logical ring module O2 powered m.
📷
An example Chord ring with m=7, showing mappings to the Chord address space, and a query lookup using a simple scheme
Comments