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 network resources in the overlays is challenging. In this paper, the authors tackle the problem using a combinatorial optimization approach. They assume that each user can simultaneously be publisher and subscriber, and brokers are dedicated servers. The problem is proved to be NP-hard and APX-complete. Therefore, the authors formulate an integer programming (ILP) problem, and design a two-stage optimization algorithm, which captures the cost of routing traffic in different parts of the overlay.