Constructing scalable overlays for pub-sub with many topics

ABSTRACT

We investigate the problem of designing a scalable overlay network to support decentralized topic-based pub/sub communication. We introduce a new optimization problem, called Minimum Topic-Connected Overlay (Min-TCO), that captures the tradeoff between the scalability of the overlay (in terms of the nodes' fanout) and the message forwarding overhead incurred by the communicating parties. Roughly, the Min-TCO problem is as follows: Given a collection of nodes and their subscriptions, connect the nodes using the minimum possible number of edges so that for each topic t, a message published on t could reach all the nodes interested in t by being forwarded by onlythe nodes interested in t.

We show that the decision version of Min-TCO is NP-complete, and present a polynomial algorithm that approximates the optimal solution within a logarithmic factor with respect to the number of edges in theconstructed overlay. We further prove that this approximation ratio is almost tight by showing that no polynomial algorithm can approximate Min-TCO within a constant factor (unless P=NP). We show experimentally that on typical inputs, the fanout of the overlay constructed by our approximation algorithm is significantly lower thanthat of the overlays built by the existing algorithms, and that its running time is just a small fraction of the analytical worst case bound. As Min-TCO can be shown to capture several important aspects of most known overlay-based pub/sub implementations, our study sheds light on the inherent limitations of the existing systems as well asprovides an insight into the best possible feasible solution.

Finally, we introduce a flexible framework that generalizes Min-TCO and formalizes most similar overlay design problems that occur in scalable pub/sub systems. We also briefly discuss several examples of such problems, and show some results with respect to their complexity.

References

1. Oracle9i Application Developers GuideAdvanced Queuing. Oracle, Redwood Shores, CA.
2. E. Anceaume, M. Gradinariu, A. K. Datta, G. Simon, and A. Virgillito. A semantic overlay for self-* peer-to-peer publish/subscribe. In ICDCS, 2006.
3. S. Baehni, P. T. Eugster, and E. Guerraoui. Data-aware multicast. In DSN, 2004.
4. R. Baldoni, R. Beraldi, V. Quema, L. Querzoni, and S. T. Piergiovanni. TERA: Topic-based Event Routing for Peer-to-Peer Architectures. In 1th International Conference on Distributed Event-Based Systems (DEBS). ACM, 6 2007.
5. R. Baldoni, R. Beraldi, L. Querzoni, and A. Virgillito. Efficient publish/subscribe through a self-organizing broker overlay and its application to SIENA. The Computer Journal, 2007.
6. S. Banerjee, B. Bhattacharjee, and C. Kommareddy. Scalable application layer multicast. SIGCOMM Comput. Commun. Rev., 32(4):205--217, 2002.
7. S. Bhola, R. Strom, S. Bagchi, Y. Zhao, and J. Auerbach. Exactly-once delivery in a content-based publish-subscribe system. In DSN, 2002.
8. A. Carzaniga, M. J. Rutherford, and A. L. Wolf. A routing scheme for content-based networking. In Proceedings of IEEE INFOCOM 2004, Hong Kong, China, Mar. 2004.
9. M. Castro, P. Druschel, A.-M. Kermarrec, and A. Rowstron. SCRIBE: a large-scale and decentralized application-level multicast infrastructure. IEEE J. Selected Areas in Comm. (JSAC), 20(8):1489--1499, 2002.
10. R. Chand and P. Felber. Semantic peer-to-peer overlays for publish/subscribe networks. In Euro-Par 2005 Parallel Processing, Lecture Notes in Computer Science, volume 3648, pages 1194--1204. Springer Verlag, 2005.
11. G. Chockler, R. Melamed, Y. Tock, and R. Vitenberg. Constructing scalable overlay networks for pub/sub with many topics. Manuscript in progress, 2007.
12. G. Chockler, R. Melamed, Y. Tock, and R. Vitenberg. SpiderCast: A Scalable Interest-Aware Overlay for Topic-Based Pub/Sub Communication. In 1th International Conference on Distributed Event-Based Systems (DEBS). ACM, 6 2007.
13. P. T. Eugster, P. A. Felber, R. Guerraoui, and A.-M. Kermarrec. The many faces of publish/subscribe. ACM Computing Surveys, 35(2):114--131, 2003.
14. R. Guerraoui, S. Handurukande, and A.-M. Kermarrec. Gosskip: a gossip-based structured overlay network for efficient content-based filtering. Technical Report IC/2004/95, EPFL, Lausanne, 2004.
15. R. Lewis. Advanced Messaging Applications with MSMQ and MQSeries. QUE, 1999.
16. H. Liu, V. Ramasubramanian, and E. G. Sirer. Client behavior and feed characteristics of rss, a publish-subscribe system for web micronews. In Internet Measurement Conference (IMC), Berkeley, California, October 2005.
17. V. Ramasubramanian, R. Peterson, and E. G. Sirer. Corona: A high performance publish-subscribe system for the world wide web. In NSDI, 2006.
18. D. Sandler, A. Mislove, A. Post, and P. Druschel. Feedtree: Sharing web micronews with peer-to-peer event notification. In International Workshop on Peer-to-Peer Systems (IPTPS), 2005.
19. D. Tam, R. Azimi, and H.-A. Jacobsen. Building content-based publish /subscribe systems with distributed hash tables. In 1st Intl. Workshop on Databases, Information Systems, and P2P Computing (DBISP2P), Berlin, Germany, 2003.
20. Y. Tock, N. Naaman, A. Harpaz, and G. Gershinsky. Hierarchical clustering of message flows in a multicast data dissemination system. In 17th IASTED Int'l Conf. Parallel and Distributed Computing and Systems, pages 320--327, 2005.
21. S. Voulgaris, E. Riviere, A.-M. Kermarrec, and M. van Steen. Sub-2-sub: Self-organizing content-based publish subscribe for dynamic large scale collaborative networks. In IPTPS, 2006.
22. S. Zhuang, B. Zhao, A. Joseph, R. Katz, and J. Kubiatowicz. Bayeux: An architecture for scalable and fault tolerant wide-area data dissemination. In 11th International Workshop Network and Operating System Support for Digital Audio and Video (NOSSDAV), pages 11--20, June 2001.

Index Terms

• Mathematics of computing

  • Discrete mathematics

    • Graph theory

      • Network flows

• Networks

  • Network properties

    • Network structure

• Theory of computation

  • Design and analysis of algorithms

    • Graph algorithms analysis

      • Network flows