Position-based distributed hash tables

Abstract

In this thesis we want to create scalable, fault-tolerant and self-configuring dictionaries that can be deployed in a wide range of networks, including highly dynamic networks with frequent membership changes, like peer-to-peer overlay networks or wireless ad hoc networks. In recent years, distributed hash tables (DHTs) have emerged as a solution to implement large-scale dictionaries. However, given the existing bandwidth limitations, updating routing information in DHTs remains a challenge. Position-based routing schemes arise as an attractive solution to this problem, due to inexpensive and ubiquitous localization mechanisms. Positional information enables the creation of oblivious (or memoryless) routing schemes, where the coordinates of the current forwarding node, of its neighbors and of the destination, suffice to determine the next hop. Such routing schemes are very suitable to rapidly changing networks, because they require very little control information. We argue in this thesis that we can use positional information to efficiently support routing and DHT operation in wireless ad hoc and in wired networks, whenever position of nodes reflects network topology. To support this claim, we create and evaluate a number of algorithms that simultaneously support routing and DHT operation in both types of networks.