one of the main challenges in Large P2P systems is the lookup problem without a centralized server. Many algorithms have been developed based on DHT interface while the algorithm must be able to locate the node that is responsible to store the data associated with a specific key. This requires that each node has to maintain IP address of neighbors to form an overlay network. DHT implementation includes that keys and node are identified using a number of m-bits, and each key is associated to data stored in node with ID close to that key. The paper discusses recent scalable algorithms with low latency and balanced distribution of keys among the nodes.
In Chord, each node has a finger table based on power of two data structure such that- a query for a key k is forwarded to the node in finger table with the highest ID not exceeding k and at least half of the remaining ID-space distance to k. the distance function is unidirectional and asymmetric. It depends on the numeric difference between two ID.
Pastry, Tapesry and Kademlia based on tree-like data structure. In Pastry and Tapesry, each node maintains a the location of some node with each prefix such that the distance function is symmetric but not unidirectional. The correctness requires that each node has a leaf set (nodes closest smaller and larger than the node). Pastry optimize the forwarding performance by maintaining a routing table that will be used to find a node has a longer shared prefix (than current node or at least equal) with the queried key.
Pastry, Tapesry and Kademlia based on tree-like data structure. In Pastry and Tapesry, each node maintains a the location of some node with each prefix such that the distance function is symmetric but not unidirectional. The correctness requires that each node has a leaf set (nodes closest smaller and larger than the node). Pastry optimize the forwarding performance by maintaining a routing table that will be used to find a node has a longer shared prefix (than current node or at least equal) with the queried key.
Kademlia's distance function depends on XOR of two ID that means it is symmetric and unidirectional.
In CAN, each node is responsible for a rectangular zone and it maintains a routing table of the neighbors in coordinate space. The lookup is performed by forwarding the query in straight path roughly to the neighbor to the node storing the key.
Each of the aforementioned algorithms involves a procedure to adapt to node's arrival and departure with a a key difference in the data structure they use as a routing table. However, these P2P lookup algorithms have been analyzed under static conditions only. As it is obvious, they have many common and different aspects and they need further work to get more strength one.
No comments:
Post a Comment