We present a new approach for designing reliable and scalable overlay networks to support topic-based pub/sub communication. We propose the${{\mathsf {MinAvg}}-{k}{\mathsf {TCO}}}$problem parameterized by${k}$: use the minimum number of edges to create a${k}$k-topic-connected overlay(${{k}TCO}$) 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${{\mathsf {MinAvg}}-{k}{\mathsf {TCO}}}$and show a lower-bound for the hardness of its approximation. For${{\mathsf {MinAvg}}-{2}{\mathsf {TCO}}}$, we present GM2, the first polynomial-time algorithm with an approximation ratio. For${{\mathsf {MinAvg}}-{k}{\mathsf {TCO}}}$, where${k} \geq {2}$, we propose HararyPT, a simple and efficient heuristic that aligns nodes across different sub-overlays. We experimentally demonstrate the scalability of GM2 and HararyPT with regards to overlay quality under representative pub/sub workloads. GM2 outputs${{2}TCO}$with an empirically insignificant increase in the average node degree, e.g., an increase by 4 in a 1000-node network, as compared to the baseline${{1}TCO}$produced by the best-known algorithm. Moreover, GM2 reduces the topic diameters by around 50 percent with respect to those in${{1}TCO}$.

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.

Overlay design for topic-based publish/subscribe (pub/sub) systems is of primary importance because the overlay forms the basis for the system and directly impacts its performance. This paper focuses on the MinAvg-TCO problem: Use the minimum number of edges to construct a topic-connected overlay (TCO) such that all nodes that are interested in the same topic are organized in a directly connected dissemination suboverlay. Existing algorithms for MinAvg-TCO suffer from three key drawbacks: 1) prohibitively high runtime cost; 2) reliance on global knowledge and centralized operation; and 3) nonincremental operation by reconstructing the TCO from scratch. From a practical point of view, these are all severe limitations. To address these concerns, we develop algorithms that dynamically join multiple TCOs. Inspired by the divide-and-conquer character of this idea, we derive a number of algorithms for the original MinAvg-TCO problem that accommodate a variety of practical pub/sub workloads. Both theoretical analysis and experimental evaluations demonstrate that our divide-and-conquer algorithms seek a balance between time efficiency and the number of edges required: Our algorithms cost a fraction (up to 1.67%) of the runtime cost of their greedy alternatives, which come at the expense of an empirically insignificant increase in the average node degree. Furthermore, in order to reduce the probability of poor partitioning at the divide phase, we develop a bulk-lightweight partitioning scheme on top of random partitioning. This more refined partitioning imposes a marginally higher runtime cost, but leads to improvements in the output TCOs, including average node degrees and topic diameters.

We incorporate underlay information into overlay design for topic-based publish/subscribe (pub/sub) systems on geo-distributed data centers. We propose the MinAvg-WTCO problem that optimizes the weighted average node degree while constructing a topic-connected overlay (TCO), i.e., Each topic induces a connected sub-overlay among all nodes interested in this topic. Most existing TCO designs are oblivious to the low-level network infrastructure and assume edge equivalence. We prove that MinAvg-WTCO is NP-complete and difficult to approximate within a logarithmic factor with regard to the number of nodes. We devise several approximation algorithms for MinAvg-WTCO using different design techniques. Both theoretical analysis and empirical evaluation show that our designed algorithms tread the balance between overlay quality and runtime cost. Our algorithms significantly outperform the state of the art for TCO design that ignores edge differences.

We incorporate fault tolerance in designing reliable and scalable overlay networks to support topic-based pub/sub communication. We propose the MinAvg- kTCO problem parameterized by k: 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.

It is a key challenge and fundamental problem in the design of distributed publish/subscribe systems to construct the underlying dissemination overlay. In this paper, we focus on effective practical solution for the Min Max-TCO problem: Create a topic-connected pub/sub overlay in which all nodes interested in the same topic are organized in a directly connected dissemination sub-overlay while keeping the maximum node degree to the minimum. Previously known solutions provided an extensive analysis of the problem and an algorithm that achieves a logarithmic approximation for Min Max-TCO. Yet, they did not focus on efficiency of the solution or feasibility of decentralized operation that would not require full knowledge of the system. Compared to these solutions, our proposed algorithm produces an overlay with marginally higher degrees. At the same time, it has drastically reduced runtime cost, which is corroborated by both theoretical analysis and empirical evaluation. The latter shows a speedup by a factor of more than 25 on average for typical pub/sub workloads.

Overlay network design for topic-based publish/subscribe systems is of primary importance because the overlay directly impacts the system's performance. Determining a topic-connected overlay, in which for every topic the graph induced by nodes interested in the topic is connected, is a fundamental problem. Existing algorithms for this problem suffer from three key drawbacks: (1) prohibitively high running time cost, (2) requirement of full system knowledge and centralized operation, and (3) constructing overlay from scratch. From a practical point of view, these are all significant limitations. To address these concerns, in this paper, we develop novel algorithms that efficiently solve the problem of dynamically joining two or more topic-connected overlays. Inspired from the divide-and-conquer character of our approach, we derive an algorithm that solves the original problem at a fraction (up to 1.7\%) of the running time cost of alternative solutions, but at the expense of an empirically insignificant increase in the average node degree.