Show simple item record

dc.contributor.authorXu, Junen_US
dc.date.accessioned2005-06-17T17:41:15Z
dc.date.available2005-06-17T17:41:15Z
dc.date.issued2002en_US
dc.identifier.urihttp://hdl.handle.net/1853/6547
dc.description.abstractIn this work, we study a fundamental tradeoff issue in designing dynamic hash table (DHT) in peer-to-peer networks: the size of the routing table v.s. the network diameter. It was observed in Ratnasamy et al. that existing DHT schemes either (a) have a routing table of size of O(log₂n) and network diameter of O(log₂n), or (b) have a routing table of size d and network diameter of O(n [superscript 1/d]). They asked whether this represents the best asymptotic "state-efficiency" tradeoffs. Our first major result is to show that there are routing algorithms which achieve better asymptotic tradeoffs. However, such algorithms all cause severe congestion on certain network nodes, which is undesirable in a P2P network. We then define the notion of "congestion-free" and conjecture that the above tradeoffs are asymptotically optimal for a congestion-free network. Though we are not able to prove (or disprove) this conjecture in full generality, our rigorous formulation of the problem and techniques introduced in proving slightly weaker results serve as the basis for further exploration of this problem. Our second major result is to prove that, if the routing algorithms are symmetric, the aforementioned tradeoffs are asymptotically optimal. Furthermore, for symmetric algorithms, we find that O(log₂n) is a magic threshold point for routing table size as follows. The "congestion" factor dominates the "reachability" factor in determining the minimum network diameter when the routing table size is asymptotically smaller than or equal to O(log₂ n), and it is the other way around when the routing table size is asymptotically larger than O(log₂n). Our third and final major result is to study the exact (instead of asymptotic) optimal tradeoffs. We propose a new routing algorithm that reduces the routing table size and the network diameter of Chord both by 21.4% without introducing any other overhead, based on a novel number-theoretical technique.en_US
dc.format.extent268457 bytes
dc.format.mimetypeapplication/pdf
dc.language.isoen_US
dc.publisherGeorgia Institute of Technologyen_US
dc.relation.ispartofseriesCC Technical Report; GIT-CC-02-40en_US
dc.subjectPeer-to-peer networks
dc.subjectRouting
dc.subjectHashing
dc.subjectAlgorithms
dc.subjectOptimization
dc.titleOn the Fundamental Tradeoffs between Routing Table Size and Network Diameter in Peer-to-Peer Networksen_US
dc.typeTechnical Reporteng_US


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record