TY - JOUR
T1 - Dynamic Multiple-Message Broadcast
T2 - Bounding Throughput in the Affectance Model
AU - Kowalski, Dariusz R.
AU - Mosteiro, Miguel A.
AU - Zaki, Kevin
N1 - Publisher Copyright:
© 2023, The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature.
PY - 2023/8
Y1 - 2023/8
N2 - We study a dynamic version of the Multiple-Message Broadcast problem, where packets are continuously injected in network nodes for dissemination throughout the network. Our performance metric is the ratio of the throughput of such protocol against the optimal one, for any sufficiently long period of time since startup. We present and analyze a dynamic Multiple-Message Broadcast protocol that works under an affectance model, which parameterizes the interference that other nodes introduce in the communication between a given pair of nodes. As an algorithmic tool, we develop an efficient algorithm to schedule a broadcast along a BFS tree under the affectance model. To provide a rigorous and accurate analysis, we define two novel network characteristics based on the network topology and the affectance function. The combination of these characteristics influence the performance of broadcasting with affectance (modulo a logarithmic function). We also carry out simulations of our protocol under affectance. To the best of our knowledge, this is the first dynamic Multiple-Message Broadcast protocol that provides throughput guarantees for continuous injection of messages and works under the affectance model.
AB - We study a dynamic version of the Multiple-Message Broadcast problem, where packets are continuously injected in network nodes for dissemination throughout the network. Our performance metric is the ratio of the throughput of such protocol against the optimal one, for any sufficiently long period of time since startup. We present and analyze a dynamic Multiple-Message Broadcast protocol that works under an affectance model, which parameterizes the interference that other nodes introduce in the communication between a given pair of nodes. As an algorithmic tool, we develop an efficient algorithm to schedule a broadcast along a BFS tree under the affectance model. To provide a rigorous and accurate analysis, we define two novel network characteristics based on the network topology and the affectance function. The combination of these characteristics influence the performance of broadcasting with affectance (modulo a logarithmic function). We also carry out simulations of our protocol under affectance. To the best of our knowledge, this is the first dynamic Multiple-Message Broadcast protocol that provides throughput guarantees for continuous injection of messages and works under the affectance model.
KW - Affectance model
KW - Multiple message broadcast
KW - Scheduling
KW - SINR model
UR - http://www.scopus.com/inward/record.url?scp=85164308349&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85164308349&partnerID=8YFLogxK
U2 - 10.1007/s00224-023-10131-1
DO - 10.1007/s00224-023-10131-1
M3 - Article
AN - SCOPUS:85164308349
SN - 1432-4350
VL - 67
SP - 825
EP - 854
JO - Theory of Computing Systems
JF - Theory of Computing Systems
IS - 4
ER -