Enhancing stabilization of chord protocol using replicated wheel nodes

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.