IEICE TRANSACTIONS on Communications
Open Access
Broadcast with Tree Selection from Multiple Spanning Trees on an Overlay Network
-
Full Text Views
104
- 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
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Takeshi KANEKO, Kazuyuki SHUDO, "Broadcast with Tree Selection from Multiple Spanning Trees on an Overlay Network" in IEICE TRANSACTIONS on Communications,
vol. E106-B, no. 2, pp. 145-155, February 2023, doi: 10.1587/transcom.2022EBP3007.
Abstract: 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.
URL: https://global.ieice.org/en_transactions/communications/10.1587/transcom.2022EBP3007/_p
Copy
@ARTICLE{e106-b_2_145,
author={Takeshi KANEKO, Kazuyuki SHUDO, },
journal={IEICE TRANSACTIONS on Communications},
title={Broadcast with Tree Selection from Multiple Spanning Trees on an Overlay Network},
year={2023},
volume={E106-B},
number={2},
pages={145-155},
abstract={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.},
keywords={},
doi={10.1587/transcom.2022EBP3007},
ISSN={1745-1345},
month={February},}
Copy
TY - JOUR
TI - Broadcast with Tree Selection from Multiple Spanning Trees on an Overlay Network
T2 - IEICE TRANSACTIONS on Communications
SP - 145
EP - 155
AU - Takeshi KANEKO
AU - Kazuyuki SHUDO
PY - 2023
DO - 10.1587/transcom.2022EBP3007
JO - IEICE TRANSACTIONS on Communications
SN - 1745-1345
VL - E106-B
IS - 2
JA - IEICE TRANSACTIONS on Communications
Y1 - February 2023
AB - 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.
ER -
English
