Home

Research

Publications

Courses

Links

Overlay Mesh Construction Using Interleaved Spanning Trees

Authors

Abstract

In recent years, overlay networks have been used to deploy bandwidth-intensive applications like A/V broadcast, video conferencing, data collection, multi-path routing, and file mirroring/transfer. The performance of these applications is highly dependent on the ability to operate over good quality overlay paths. A richly connected overlay network comprised of high quality virtual paths provides the ideal setting for these applications; applications can then react quickly to fluctuating performance, use application-specific path selection criteria, and coordinate concurrent communication channels over multiple paths.

We have developed a mesh-first approach, where the dense graph of all possible overlay links is reduced to a minimal topology composed of k trees. In particular, we focus on a distributed algorithm to compute k Minimum Spanning Trees (k-MST), where edge weights correspond to any one of the standard performance metrics, such as latency, bandwidth, and loss rate. The mesh is constructed using initial estimates of network properties and refined over time. The primary motivation to construct an overlay mesh of k trees is to ensure the existence of k edge disjoint overlay paths between any two nodes, to promote fault- and performance-tolerance, and to enable path diversity. We have developed a prototype overlay routing infrastructure that utilizes a k-tree methodology for mesh construction that can be used in infrastructure-type settings like PlanetLab as well as in large corporations. In our PlanetLab implementation deployed over a 150-node overlay network, our prototype demonstrated reasonable bandwidth utilization during construction, low loss-rates for data streams, and high performance in a realistic multicast file transfer scenario.

Published

@InProceedings{YCMKPW04,
  author =	 {Anthony Young and Jiang Chen and Zheng Ma and Arvind Krishnamurthy and Larry Peterson and Randolph Y. Wang},
  title =	 {Overlay Mesh Construction Using Interleaved Spanning Trees},
  booktitle =	 {Proceedings of The 23rd Conference of the IEEE Communications Society({INFOCOM})},
  year =	 2004,
  address =	 {Hong Kong, China},
  month =	 {March},  
}