Characterizing graph-theoretic properties of a large-scale DHT: Measurements vs. simulations

Abstract

The widely used distributed hash table (DHT) in KAD is commonly analyzed and optimized based on partial measurements and simulation results, which are limited in scope and subject to simplification. An accurate characterization, however, is vital for a thorough understanding and effective enhancement. Analyzing and comparing complete real graphs collected from a large-scale measurement campaign as well as synthetic graphs generated by a novel simulation model, we study their degree distributions as well as resilience in face of random departure and targeted attacks. Our results show that the online KAD graph, although scale-free, is highly robust not only to random departure, but also to targeted attacks, making it suitable for distributed applications requiring a high resilience. Resilience to random departure and shape of degree distribution are well modelled by the simulations. However, due to a greatly increased ratio of stale routing information, the complete graph in the real system is much more vulnerable to targeted attacks compared to estimations based on simulative results.