Demand-Aware Plane Spanners of Bounded Degree
2021
Plane spanners of bounded degree are efficient communication backbones for networks. However, 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 thus initiates the study of demand-aware plane spanners of bounded degree, geometric spanners whose topology accounts for the actual communication traffic. 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 the benefits of demand-awareness under realistic traffic traces.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
27
References
3
Citations
NaN
KQI