A distributed hash table (DHT) is a type of peer-to-peer (P2P) network that, like
traditional hash tables, maps keys to values. Unlike traditional hash tables, however, the
data is distributed across a network with each node being responsible for a particular range
of keys. Numerous other DHTs have been presented and have become the cornerstone of
wildly popular P2P file-sharing applications, such as BitTorrent. Each of these DHTs
trades-off the number of pointers maintained per node with the overhead and lookup time;
storing more pointers decreases the lookup time at the expense of increased overhead.
A Grouped Hamming Network (GHN), the overlay network presented in this thesis,
allows for the number of pointers per node to be any increasing function of n, P(n) =
Ω(log n). The system presented assumes that nodes fail independently and uniformly at
random with some probability q = 1 − p. Three different schemes for routing in a GHN
are presented. For each routing scheme a theoretical estimate on the probability of failure
is given and optimal configurations in terms of n and P(n) are given. Simulations of
GHNs with various configurations indicate that the given estimates are indeed accurate
for reasonable values of q and that the optimal configurations are accurate.
| Identifer | oai:union.ndltd.org:WATERLOO/oai:uwspace.uwaterloo.ca:10012/5411 |
| Date | January 2010 |
| Creators | Logan, Bryan |
| Source Sets | University of Waterloo Electronic Theses Repository |
| Language | English |
| Detected Language | English |
| Type | Thesis or Dissertation |
Page generated in 0.0374 seconds