Tuesday, November 1, 2005

Implementation of distributed hash tables in mobile ad-hoc networks


By Humayun Bakht

Mobile ad-hoc networks are one of the latest developments, and an attractive addition, to the family of wireless networks. With the addition of mobile ad-hoc networks, we can broadly classify wireless networks into two types: wireless fixed and wireless ad-hoc networks. Wireless fixed networks are a collection of wireless nodes that communicate with each other with the aid of some fixed infrastructure. A wireless ad-hoc network operates in the absence of a centralized structure.

Mobile ad-hoc networks introduced a completely new art of networking and can be deployed in places where we lack supporting structures. Each and every bit of a mobile ad-hoc network is unique. While these networks are beneficial in many ways, they do require unique strategies to be developed for routine network controls. Connecting these networks with a larger network, such as the Internet, is a challenging issue.

Distributed hash tables

DHTs (Distributed Hash Tables) can be seen as a platform for building a variety of scalable and dynamic distributed applications for the Internet. Scalable applications include distributed storage systems and application level multi-cast. DHTs can be used to develop a common infrastructure for certain distributed applications. DHTs are similar as they have a file cabinet that spreads over numerous servers. Therefore, if one server goes down, it does not disturb the rest of the network communication. As in peer-to-peer or ad-hoc networks, there is no central server that contains a list of the stored data. Instead, each mobile node has a list, or a routing table, where data is stored in the system.

The current DHT structure poses many challenges, such as fault-tolerance, locating objects, scalability, availability, load balancing, and incremental deployment. It is possible to implement current DHT specifications in mobile ad-hoc networks. If their deployment in mobile ad-hoc networks is successful, it could provide a more efficient way to establish distributed applications and services for ad-hoc networking.

In mobile ad-hoc networks, applications such as file-sharing and resource discovery can benefit from the distributed insert/lookup convergence provided by DHTs. Research in this area suggests one of the two possible approaches -- layered and integrated -- that can be used for the deployment of DHTs in mobile ad-hoc networks provided using a proximity-aware DHT Pastry and DSR (Dynamic Source Routing) protocol.

In a layered approach (hence: "pastry"), a proximity-aware DHT Pastry is directly layered on the top of mobile ad-hoc networks very similarly to the way it's normally layered in the Internet. Pastry maintains its leaf set and routing table entries without source routes while DSR maintains source routes passively with respect to the demand of Pastry routing state. In mobile ad-hoc environment, it's difficult to accomplish straightforward layering. It requires some modifications to accomplish the shared medium access nature of ad-hoc networks.