Networking Research Laboratory
Department of Computer Sciences
The University of Texas at Austin

Director: Simon S. Lam (more publications)

Practical applications of distributed Delaunay triangulation

Protocol design for distributed Delaunay triangulation

Delaunay triangulation (DT) is a useful geometric structure that has a long history and many applications in different fields of science and engineering.  Consider a set of nodes (points) that form a DT.  Each node is identified by its location specified by coordinates.  For nodes in a 2D space, Bose and Morin (2004) proved that greedy routing on a DT always succeeds to find a given destination node.  We extended their result and proved that given a destination location p in a d-dimensional Euclidean space (d > 1), greedy routing on a DT always finds a DT node that is closest to p.  More specifically, if a node exists at location p, it is found; else, a node closest to p is found.  Note that greedy routing on a DT does not always find the shortest route, but the quality of the greedy route is very good, i.e., within a constant of the direct distance.

It is also interesting to note that greedy routing on a DT always succeeds even if node locations are specified by inaccurate or even arbitrary coordinates. Our goal is to exploit this and other properties of DT for its use in wireless mesh networks, p2p networks, and distributed virtual environments. Towards this goal, we first define a distributed DT and present a necessary and sufficient condition for a distributed DT to be correct.

Using the necessary and sufficient condition for correctness as a guide, we design a protocol suite for a set of nodes in d-dimension (d > 1) to construct and maintain a distributed DT in a dynamic environment. The join, leave, and failure protocols in the suite are proved to be correct for a single join, leave, and failure, respectively. For a system under churn, it is impossible to maintain a correct distributed DT continually. We define an accuracy metric such that accuracy is 100% if and only if the distributed DT is correct. The suite also includes a maintenance protocol designed to recover from incorrect system states and to improve accuracy.  Experimental results show that our new suite of protocols maintains high accuracy for systems under churn and each system converges to 100% accuracy after churning stopped.

We design several application protocols, in addition to greedy routing, which run on top of a correct distributed DT to support networking and simulation-type applications. They include protocols for finding a closest existing node, broadcast, and geocast. We prove that our broadcast and geocast protocols always deliver a message to every target node. Our broadcast and geocast protocols are also efficient in the sense that very few target nodes receive duplicate messages, and non-target nodes receive no message.  We evaluate their performance characteristics using simulation experiments, and investigate the impact of inaccurate coordinates, as well as "virtual coordinates," on the performance of greedy routing, broadcast, and geocast.