A distributed algorithm for constructing minimum delay spanning trees under bandwidth constraints on overlay networks

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...

Full description

Saved in:
Bibliographic Details
Published in:Systems and computers in Japan 2006-12, Vol.37 (14), p.15-24
Main Authors: Baduge, Thilmee M., Hiromori, Akihito, Yamaguchi, Hirozumi, Higashino, Teruo
Format: Article
Language:English
Subjects:
decentralized algorithm
minimum delay tree
overlay networks
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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
ISSN:0882-1666
1520-684X
DOI:10.1002/scj.20655