Abstract
dc:description.abstractA 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.
Degree
thesis:*- Grantor dc:publisher
- University of Waterloo
- Year dc:date.issued
- 2010
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Logan, Bryan
Subjects
dc:subject × 3Rights
- Language dc:language.iso
- en
Identifiers
dc:identifier.*- Handle dc:identifier.uri
- http://hdl.handle.net/10012/5411