On the construction of the minimum cost content-based publish/subscribe overlays

Content-based publish/subscribe overlay is gaining popularity in large-scale content distribution applications for its flexibility and anonymity. Since such overlays are built on top of diverse infrastructures, minimizing the cost of using bandwidth in the overlays is a complicated task. In this paper, we tackle this task using a combinatorial optimization approach. We assume that each user can simultaneously be publisher and subscriber, and brokers are dedicated servers. We first formulate a two-stage optimization problem, which captures the cost of routing traffic in different parts of the overlay. Our solution is obtained by separately approximating the problem of each stage and then combining the results of sub-problems. In order to achieve better results, we further propose a novel formulation based on sub-channeling and Steiner tree/star problem, which simplifies the analysis of content-based routing and facilitate an intuitive randomized approximation algorithm. This algorithm is then translated into a decentralized one that dynamically adjusts the overlay connections when the network undergoes dynamisms. Simulation results demonstrate that our algorithms substantially reduce the cost of constructing content-based publish/subscribe overlay.