Paper 5             One Hop has similar ring-like structure as Chord. One Hop
maintains a routing table size of all the members to achieve lookup time of
one hop. In order to reduce bandwidth in the keep-alive messages, One Hop
uses a three-tier hierarchical structure to disseminate membership changes.
The circular identification space is divided into slices, and there is a
slice leader in each of them. Slices are partitioned into units with unit
leader in the middle of each unit. Slice leader aggregates all the membership
changes and periodically sends to other slice leader. Once the slice leader
receives the membership changes, it forwards the changes to all the unit
leaders in the slice. Finally unit leader will propagate the changes to the
successor and predecessor. The paper analyzes the bandwidth cost of the
system and reasons the systems can scale more than 10^5 nodes. However, with
the hierarchical structure, the leaders will have a higher load than other
nodes. Also, if the leader is attacked or malicious, a large potion of the
nodes will be affected.

            Instead of using hierarchical structure to disseminate membership
changes, Kelips uses gossip protocol instead. Kelips divides the
identification space into n^(1/2) affinity groups. A node is mapped to an
affinity group, and the node in the affinity group will have knowledge about
the location of files in the group. The membership changes is spread using
two-level gossiping scheme. Kelips average lookup time is also O(1). However,
it takes some times to propagate changes in the affinity group using gossip
protocol, which can lead to result inconsistency. 

 

