Filipe João Boavida de Mendonça Machado Araújo

Position-Based Distributed Hash Tables.

Dissertação submetida para provas de doutoramento em Engenharia Informática, Departamento de Informática, Faculdade de Ciências da Universidade de Lisboa, Outubro de 2005.

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. As an interesting result of our work, we can combine solutions into a single architecture that spans wired and wireless networks. This architecture can provide a seamless integration and use of a position-based DHT, despite the access network of the peer nodes.

KEY WORDS: Distributed Hash Table, Overlay Network, Position-Based Routing Scheme, Delaunay Triangulation, Long Range Contact

Selected Publications

Position-Based Distributed Hash Tables
F. Araújo
PhD Thesis. Departamento de Informática da Faculdade de Ciências da Universidade de Lisboa
October, 2005.
Available pdf.
On the Monitoring Period for Fault-Tolerant Sensor Networks
F. Araújo and L. Rodrigues
Proceedings of the Second Latin-American Symposium on Dependable Computing, Salvador, Bahia, Brazil, October 2005
Available BibTeX, abstract (html) and report (pdf).
Long Range Contacts in Overlay Networks
F. Araújo and L. Rodrigues
Proceedings of the Euro-Par 2005, Lisboa, Portugal, August 2005
Available BibTeX, abstract (html) and report (pdf).
Scalable QoS-Based Event Routing in Publish-Subscribe Systems
N. Carvalho, F. Araújo and L. Rodrigues
Proceedings of the 4th IEEE International Symposium on Network Computing and Applications (IEEE NCA05), July, 2005, Cambridge, MA, USA
Available BibTeX, abstract (html) and report (pdf).
A Distributed Hash Table for Wireless Ad Hoc Networks
F. Araújo, L. Rodrigues, J. Kaiser, C. Liu, and C. Mitidieri.
Proceedings of the Fourth International Workshop on Distributed Event-Based Systems (DEBS'05), in conjuction with the 25th International Conference on Distributed Computing Systems (ICDCS-25), Columbus, Ohio, USA, June 2005.
Available BibTeX, abstract (html) and report (pdf).
Fast Localized Delaunay Triangulation
F. Araújo and L. Rodrigues
Proceedings of the 8th International Conference on Principles of Distributed Systems (OPODIS), December 2004, Grenoble, France.
Available BibTeX, abstract (html) and report (gzip postscript), (pdf).
GeoPeer: A Location-Aware Peer-to-Peer System
F. Araújo and L. Rodrigues.
Proceedings of the 3rd IEEE International Symposium on Network Computing and Applications (IEEE NCA04), pp. 39-46, August, 2004, Cambridge, MA, USA.
Available BibTeX, abstract (html) and report (gzip postscript), (pdf).
On QoS-Aware Publish-Subscribe.
F. Araújo and L. Rodrigues.
In Proceedings of the International Workshop on Distributed Event-Based Systems, Vienna, Austria, July, 2002. (Proceedings the 22nd International Conference on Distributed Computing Systems Workshops, pp 511-515).
Available BibTeX, abstract (html) and extended report(gzip postscript), (pdf).

Contact

Luís Rodrigues