University of Toronto & University of Oslo, 2013.
We incorporate fault tolerance in designing reliable and scalable overlay networks to support topic-based publish/subscribe communication. We propose a new family of optimization problems, named MinAvg-kTCO, that captures the trade-offs among several key dimensions including fault tolerance, scalability, performance, and message dissemination. Roughly speaking, the MinAvg-kTCO problem is: use the minimum number of edges to create a k-topic-connected overlay} (kTCO) for pub/sub systems, i.e., for each topic the sub-overlay induced by nodes interested in the topic is k-connected.
We prove the NP-completeness of MinAvg-kTCO and show a lower-bound for the hardness of its approximation. With regard to the MinAvg-2TCO problem, we present the first polynomial time algorithm, namely GM2, with a guaranteed approximation factor relative to the optimum. %approximation ratio. We show experimentally that on representative publish/subscribe workloads, the GM2 algorithm outputs 2TCO at the cost of an empirically insignificant increase in the average node degree, which is around $1.65$ times that of 1TCO produced by the algorithm with the best known approximation ratio. Besides, GM2 reduces the topic diameters around $50\%$ as compared to those in the baseline 1TCO.
With regards to the MinAvg-kTCO problem, where $k >= 2$, we propose a simple and efficient heuristic algorithm, namely HararyPT, that aligns nodes across different sub-overlays. We show the practical scalability of HararyPT for highly correlated pub/sub workloads in terms of the number of nodes, the number of topics, and the number of subscriptions per node.