Overlay mesh construction using interleaved spanning trees

Anthony Young, Jiang Chen, Zheng Ma, Arvind Krishnamurthy, Larry Peterson, Randolph Y. Wang

Research output: Contribution to journalConference articlepeer-review

52 Scopus citations


In this paper we evaluate a method of using inter-leaved 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.

Original languageEnglish (US)
Pages (from-to)396-407
Number of pages12
JournalProceedings - IEEE INFOCOM
StatePublished - 2004
Externally publishedYes
EventIEEE INFOCOM 2004 - Conference on Computer Communications - Twenty-Third Annual Joint Conference of the IEEE Computer and Communications Societies - Hongkong, China
Duration: Mar 7 2004Mar 11 2004


  • Experimentation with real networks/Testbeds
  • System design

ASJC Scopus subject areas

  • General Computer Science
  • Electrical and Electronic Engineering


Dive into the research topics of 'Overlay mesh construction using interleaved spanning trees'. Together they form a unique fingerprint.

Cite this