On the Convergence of Chord Network

Due to the churn, the P2P overlay network can not be static. The dynamic environment may degrade the services provided by distributed hash table (DHT), then the convergence of the overlay is very important. In this paper, we try to analyze the convergence of Chord network. We prove that the generic...

Full description

Saved in:
Bibliographic Details
Main Authors: Nie Xiao-wen, Lu Xian-liang, Duan Han-cong, Li Lin, Pu Xun
Format: Conference Proceeding
Language:English
Subjects:
Computer science
Convergence
Data structures
Degradation
Fingers
Graph theory
Intrusion detection
Network topology
Protocols
Routing
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Due to the churn, the P2P overlay network can not be static. The dynamic environment may degrade the services provided by distributed hash table (DHT), then the convergence of the overlay is very important. In this paper, we try to analyze the convergence of Chord network. We prove that the generic structures of Chord network is a pseudo-tree, which can be converged to a circle by algorithm stabilize. The ring in Chord has more meanings than a circle in graph theory, and the ring requires all nodes in the network permuted by their ids. An efficient strong_stabilize algorithm is proposed to make the network converge to a ring rapidly.
ISSN:2160-4908
DOI:10.1109/GCC.2007.90