The search functionality is under construction.
The search functionality is under construction.

Open Access
Broadcast with Tree Selection from Multiple Spanning Trees on an Overlay Network

Takeshi KANEKO, Kazuyuki SHUDO

  • Full Text Views

    170

  • Cite this
  • Free PDF (5.1MB)

Summary :

On an overlay network where a number of nodes work autonomously in a decentralized way, the efficiency of broadcasts has a significant impact on the performance of distributed systems built on the network. While a broadcast method using a spanning tree produces a small number of messages, the routing path lengths are prone to be relatively large. Moreover, when multiple nodes can be source nodes, inefficient broadcasts often occur because the efficient tree topology differs for each node. To address this problem, we propose a novel protocol in which a source node selects an efficient tree from multiple spanning trees when broadcasting. Our method shortens routing paths while maintaining a small number of messages. We examined path lengths and the number of messages for broadcasts on various topologies. As a result, especially for a random graph, our proposed method shortened path lengths by approximately 28% compared with a method using a spanning tree, with almost the same number of messages.

Publication
IEICE TRANSACTIONS on Communications Vol.E106-B No.2 pp.145-155
Publication Date
2023/02/01
Publicized
2022/08/16
Online ISSN
1745-1345
DOI
10.1587/transcom.2022EBP3007
Type of Manuscript
PAPER
Category
Network

Authors

Takeshi KANEKO
  Tokyo Institute of Technology
Kazuyuki SHUDO
  Tokyo Institute of Technology

Keyword