Paper Info
Title
DHT routing analysis in a logarithmically transformed space
Abstract
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.
Year
DOI
Venue
2008
10.1007/s12083-007-0002-2
Peer-to-Peer Networking and Applications
Keywords
DocType
Volume
DHT routing,Metric space,Logarithmically transformed space
Journal
1
Issue
ISSN
Citations 
1
1936-6442
0
PageRank 
References 
Authors
0.34
6
2
Name
Order
Citations
PageRank
Peter Kersch1222.45
Róbert Szabó211616.29