Networking Research Laboratory
Director: Simon S. Lam (more publications)
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.