CRONets: Cloud-Routed Overlay Networks
Chris X. Cai, Franck Le, et al.
ICDCS 2016
It is important to build overlays for topic-based publish/subscribe (pub/sub) under resource constraints. In a topic-connected overlay (TCO), each topic t induces a connected sub-overlay among all nodes interested in t. Existing work merely consider how to optimize a complete TCO and implicitly commit the unrealistic assumption of unlimited resources. In contrast, we make maximum use of restricted node degree budgets to build a partial TCO. We formalize the notion of TCO support to capture the quality of the pub/sub overlay. Furthermore, we demonstrate that partial TCOs usually exhibit significantly better cost-effectiveness in practice. We propose two problems of maximizing TCO support in a partial TCO: (1) PTCOA with a bounded average node degree and (2) PTCOM under the maximum node degree constraint. We design two greedy algorithms, which achieve the constant approximation ratios of (1-e-1) for PTCOA and (1-e-1/6) for PTCOM, respectively. Empirical evaluation demonstrates the scalability of our algorithms under a variety of pub/sub workloads. Given practical data sets extracted from Facebook and Twitter, our algorithms produce an 80% TCO with fewer than 20% of the node degree budget as a complete TCO. We also show experimentally that it is promising to design decentralized protocols to compute a partial TCO for pub/sub.
Chris X. Cai, Franck Le, et al.
ICDCS 2016
Chen Chen, Yoav Tock, et al.
DEBS 2018
A. Manzalini, R. Minerva, et al.
ICIN 2013
Artem Barger, Liran Funaro, et al.
ICBC 2023