Anthony Young, Jiang Chen, Zheng Ma, Arvind Krishnamurthy, Larry
Peterson, and Randolph Y. Wang.
Overlay Mesh Construction Using Interleaved Spanning Trees.
Proc. INFOCOM 2004. March 2004.
In this paper we evaluate a method of using interleaved spanning trees to compose a resilient, high performance overlay mesh. Though spanning trees of arbitrary type could be used to construct an overlay mesh, we focus on a distributed algorithm that computes k minimum spanning trees on an arbitrary graph. The principal motivation behind this strategy is to provide applications with a k-redundant, high quality mesh suitable for demanding applications like A/V broadcast, video conferencing, data collection, multi-path routing, and file mirroring/transfer. We elaborate details of k-MST, pointing out advantages and potential problem points of the protocol, and then analyze its performance using a variety of metrics with simulation as well as a functional PlanetLab implementation.