Abstract:
Peer-to-Peer (P2P) network is a logical overlay constructed on top of physical networks,
in which participant nodes are assigned logical identifiers (Ids) (in most cases flat names) and
messages are routed among these nodes exploiting a certain structure of these Ids. P2P systems
popularized wide scale file sharing applications, for example BitTorrent. P2P overlays can be
unstructured, such as Napster and Gnutella, and structured such as Chord, CAN, Tapestry, Pastry
etc. where nodes organized themselves in an orderly fashion. In Chord, nodes self-organize
themselves in a ring in ascending order of their Ids. Each node keeps a link in the ring to the next
immediate node, called successor, to the previous immediate node, called predecessor, and a
short list of other peers, called finger table that are exponentially further away from that node in
Chord Id space. A process, called stabilization, maintains the Chord ring in the presence of
concurrent joining and leaving of nodes (churns) which is reportedly expensive involving
numerous message exchanges among peers. We analyze the stabilization algorithm of Chord and
then attempt to enhance it by using a light weight central coordination on top Chord’s pure
distributed operations. In our scheme, we decouple the complexity of self-organization amid of
churn by introducing a few designated nodes—we call them “wheel” nodes—that maintain an
updated list of current nodes in the ring and allow other nodes to update their finger entries by
exchanging messages with them. Wheel nodes provide a global view of the network and thus
reduce the remote procedure calls for Chord ring maintenance. This significantly simplifies the
whole stabilization process of Chord at the cost of some additional storage at the wheel nodes.
To this end, we propose Chordels, Chord with wheels. We simulated Chordels as well as the
original Chord in PeerSim simulator and show that Chordels indeed has magnitude order of less
number of remote procedure calls than the original Chord, while the lookup success rates remain
quite the same.
