Chen Chen, Roman Vitenberg, and HansArno Jacobsen.
University of Toronto & University of Oslo, 2013.
We incorporate fault tolerance in designing reliable and scalable overlay networks to support topicbased publish/subscribe communication. We propose a new family of optimization problems, named MinAvgkTCO, that captures the tradeoffs among several key dimensions including fault tolerance, scalability, performance, and message dissemination. Roughly speaking, the MinAvgkTCO problem is: use the minimum number of edges to create a ktopicconnected overlay} (kTCO) for pub/sub systems, i.e., for each topic the suboverlay induced by nodes interested in the topic is kconnected.
We prove the NPcompleteness of MinAvgkTCO and show a lowerbound for the hardness of its approximation. With regard to the MinAvg2TCO 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 MinAvgkTCO problem, where $k >= 2$, we propose a simple and efficient heuristic algorithm, namely HararyPT, that aligns nodes across different suboverlays. 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.
Readers who enjoyed the above work, may also like the following:
