Improving Delaunay triangulation for application-level multicast

In recent years, there has been increasing interest in application-level multicast (ALM), where the multicast related functionalities are moved to end-hosts. One of the promising ALM protocols is Delaunay triangulation (DT), which constructs an overlay mesh using 2-D Delaunay triangulation (DT) and makes use of compass routing to forward packets. However, DT protocol as it is originally proposed suffers from several weaknesses: 1) it requires users to input its geographic location, and assumes that the location correlates well with network distance; 2) it tends to form multiple connections across two domains, and hence has a high usage of long delay (interdomain) links; 3) it does not consider the fanout of a host, therefore some less-powerful hosts may serve too many users, leading to degradation of service. To address these problems, we propose to use global network positioning (GNP) for host location estimation and forward delegation to limit the fanout of a host explicitly and efficiently trade off the network resource usage with latency. Using Internet-like topologies, we show that our scheme, as compared to the original DT protocol, can substantially reduce average relative delay penalty, physical link stresses and network resource usage while meeting the processing capability of the hosts in the network.