Routing schemes for hybrid communication networks
Routing schemes for hybrid communication networks
复制标题
混合通信网络的路由方案
DOI：
10.1016/j.tcs.2023.114352
复制
发表时间：
2024
影响因子：
1.1
通讯作者：
Coy S
中科院分区：
文献类型：
--
作者：
Coy S
我们考虑在分布式计算的混合模型中计算路由方案的问题，其中节点可以访问两种根本不同的通信模式。在这个问题中，节点必须计算小标签和路由表，以允许在本地网络中高效地路由消息，而本地网络通常提供了大部分吞吐量。最近的研究表明，与单独使用任何一种通信模式相比，使用混合模式可以显著提高速度。尽管如此，如果使用普通图作为输入图，在混合模型中，路由方案的计算仍然需要多项式轮数。我们通过将局部图限制为单位圆盘图来绕过这个下界，并用运行时间O(|H|2+LOGn)、标签大小O(LOGn)和路由表的大小O(|H|2⋅n)来确定地解决这个问题，其中|H|是网络中的“无线空洞”的数目。我们的工作建立在Coy等人最近的工作基础上，他们在输入图没有无线电洞的简单得多的设置下获得了这一结果。我们开发了新的技术来实现这一点，包括将局部图分解为路径凸区域，每个区域包含其中任何节点对的最短路径。
We consider the problem of computing routing schemes in the HYBRID model of distributed computing where nodes have access to two fundamentally different communication modes. In this problem nodes have to compute small labels and routing tables that allow for efficient routing of messages in the local network, which typically offers the majority of the throughput. Recent work has shown that using the HYBRID model admits a significant speed-up compared to what would be possible if either communication mode were used in isolation. Nonetheless, if general graphs are used as the input graph the computation of routing schemes still takes polynomial rounds in the HYBRID model. We bypass this lower bound by restricting the local graph to unit-disc-graphs and solve the problem deterministically with running time O (| H| 2+ log n), label size O (log n), and size of routing tables O (| H| 2⋅ log n) where| H| is the number of “radio holes” in the network. Our work builds on recent work by Coy et al., who obtain this result in the much simpler setting where the input graph has no radio holes. We develop new techniques to achieve this, including a decomposition of the local graph into path-convex regions, where each region contains a shortest path for any pair of nodes in it.