DHT routing analysis in a logarithmically transformed space

This paper presents an analytical model that helps understanding the common foundations of routing in DHTs and provides means for analytical comparison of different systems and different parameter combinations. In the proposed model, a logarithmic transformation is applied to the metric space embedding node identifiers. We show that in this transformed space - similarly to short-range connections in the real metric space - long-range connections have linear properties: connections are uniformly distributed and routing via long-range contacts progresses linearly toward the target. Using this transformation model, we introduce a λ long-range connection density parameter to characterize DHT routing and analyze common properties and differences between existing DHT routing mechanisms. For the the two extreme DHT families (“most random” and completely deterministic), we also present a detailed stochastic analysis of routing in the transformed space and express analytically the expected value of the number of routing hops.

Róbert SzabóEmail:

---

Peter Kersch   has received MSc degree in computer science from Budapest University of Technology and Economics in 2003. He is currently a PhD candidate in the same institution. His main research interests include modelling, performance analysis and design of self-organizing algorithms, P2P networks and ad hoc networks. Dr. Robert Szabo   is an associate professor at the Department of Telecommunication and Media Informatics, Budapest University of Technology (BME). He is the head of the High Speed Networks Laboratory at BME; and is the president of the Telecommunications Section of the Scientific Association for Infocommunications, Hungary. His main research interests are architectures, protocols and performance of communication networks.