Fixed Interval Nodes Estimation: An accurate and low cost algorithm to estimate the number of nodes in Distributed Hash Tables

Peer to Peer (P2P) systems have shown to be a good solution to build self-organized large scale distributed information systems. Within Peer to Peer overlays, Distributed Hash Tables (DHTs) offer strong fault tolerance properties as well as efficient object look-up algorithms. Even if the essence of a P2P system is to provide to each node a restricted local view of the whole system, it is often useful to have some global knowledge of the system, such as knowing the DHT size. The DHT size is relevant, as this information is used to adapt some parameters of the system (the number of replicas of a given object, the depth for epidemic algorithms, the potential number of clients for a given service). Computing the number of nodes in a DHT is a difficult task as it requires the best possible accuracy at the lowest achievable cost in terms of messages overhead. In this paper, we propose a new algorithm to estimate the number of nodes in a DHT called Fixed Interval Nodes Estimation (FINE). Our approach is fairly accurate for the estimation, and has a very low overhead in the number of generated messages. We give a complete set of results from simulations as well as a statistical study to demonstrate the accuracy of FINE and that it does not depend either on the DHT size, nor on the hash function used to build the DHT.