Distributed Computing Вычислительная теория и математика

Demand-aware plane Spanners of Bounded Degree

Ceylan, Esra, Foerster, Klaus-Tycho, Schmid, Stefan, Zaitsava, Katsiaryna
Springer Nature · 2026-08-08 · DOI 10.1007/s00446-026-00513-2

Аннотация

Plane spanners of bounded degree are efficient communication backbones for networks. As the performance requirements of applications are becoming increasingly stringent, it is crucial to design networks in a way that data transmissions and latency are optimized, also on a topological level. Traditional approaches often utilize geometric structures known as ’spanners’ to streamline network topologies and reduce travel distances, but they typically overlook specific traffic demands, which can lead to suboptimal performance. While existing spanners provide attractive guarantees in the worst-case, they are demand-oblivious and may hence be suboptimal under specific traffic demands. This paper, for the first time, presents demand-aware plane spanners of bounded degree, geometric spanners whose topology accounts for the actual communication traffic. Our research introduces a novel framework for creating spanners that integrate demand-awareness, enhancing efficiency under realistic communication scenarios. This approach preserves essential properties, such as constant stretch and bounded degree, while adapting to traffic patterns. We show that demand-awareness can significantly reduce the distance travelled per bit, and present a spanner which exploits topological flexibilities to account for the demand, without losing desirable guarantees of demand-oblivious spanners, namely constant stretch and degree. We complement our analytical results with heuristic improvements and a simulation study exploring how demand-awareness benefits under realistic traffic traces.

Читать у издателя →