Estimating the Size of a Chord Ring

The Chord system is a decentralized peer-to-peer mechanism designed to store and search key/value pairs. The peers in a Chord overlay network are represented on a circle, whereas each peer has to maintain log2(n) neighbors to guarantee a stable overlay structure in the presence of high churn rates. A single peer, however, does not know the current size n of the Chord ring. Choosing a constant value for the number of neighbors does not scale to large networks and involves unnecessary overhead in small networks. In this paper we therefore introduce an estimator for the current size of the Chord ring based on a peer's neighbor- and fingerlists. To be able to rate the goodness of the estimator we show how to calculate the corresponding confidence intervals. Estimating the Size of a Chord Ring