A distributed algorithm for constructing minimum delay spanning trees under bandwidth constraints on overlay networks
✍ Scribed by Thilmee M. Baduge; Akihito Hiromori; Hirozumi Yamaguchi; Teruo Higashino
- Publisher
- John Wiley and Sons
- Year
- 2006
- Tongue
- English
- Weight
- 787 KB
- Volume
- 37
- Category
- Article
- ISSN
- 0882-1666
No coin nor oath required. For personal study only.
✦ Synopsis
Abstract
In this paper, we propose a new protocol that constructs a spanning tree on an overlay network given by a complete graph, in a decentralized manner. This algorithm consists of two decentralized operations, which support joining of and leaving of the overlay network at any time in the session (though there are some constraints). Whenever a node joins or leaves, the rest of the nodes (or node itself in case of join) can be repositioned (or positioned) to minimize the maximum delay from a certain set of nodes in the current tree without violating the degree constraint at each node, by applying these operations. We have confirmed the usefulness of this algorithm by performing simulation and real‐world experiments. © 2006 Wiley Periodicals, Inc. Syst Comp Jpn, 37(14): 15–24, 2006; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/scj.20655