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