MERC: Match at Edge and Route intra--Cluster for Content-based Publish/Subscribe Systems

ABSTRACT

Despite suffering from inefficiency and flexibility limitations, the filter-based routing (FBR) algorithm is widely used in content-based publish/subscribe (pub/sub) systems. To address its limitations, we propose a dynamic destination-based routing algorithm called D-DBR, which decomposes pub/sub into two independent parts: Content-based matching and destination-based multicasting. D-DBR exhibits low event matching cost and high efficiency, flexibility, and robustness for event routing in small scale overlays. To boost scalability, we further complement D-DBR with a new routing algorithm called MERC. MERC divides the overlay into interconnected clusters and applies content-based and destination-based mechanisms to route events inter- and intra-cluster, respectively. We implemented all algorithms in the PADRES pub/sub system. Experimental results show that our algorithms outperform FBR in terms of improving event dissemination throughput by up to 700% and reducing the end-to-end latency by up to 55%.

References

1. M. Adler, Z. Ge, J. F. Kurose, D. Towsley, and S. Zabele. Channelization problem in large scale data dissemination. In ICNP'01, 2001.
2. G. Banavar, T. Chandra, B. Mukherjee, J. Nagarajarao, R. E. Strom, and D. C. Sturman. An efficient multicast protocol for content-based publish-subscribe systems. In ICDCS'99, 1999.
3. L.-F. Cabrera, M. B. Jones, and M. Theimer. Herald: Achieving a global event notification service. In Hot Topics in Operating Systems Workshop, 2001.
4. C. Canas, K. Zhang, B. Kemme, J. Kienzle, and H.-A. Jacobsen. Publish/Subscribe network designs for multiplayer games. In ACM Middleware, 2014.
5. F. Cao and J. P. Singh. Medym: Match-early with dynamic multicast for content-based publish-subscribe networks. In Middleware, 2005.
6. A. Carzaniga, C. Hall, and A. L. Wolf. Practical high-throughput content-based routing using unicast state and probabilistic encodings. Faculty of Informatics, University of Lugano, Tech. Rep, 2009.
7. A. Carzaniga, D. S. Rosenblum, and A. L. Wolf. Design and evaluation of a wide-area event notification service. ACM TOCS, 2001.
8. D. D. Clark. Policy routing in internet protocols. Policy, 1989.
9. M. Costa, J. Crowcroft, M. Castro, A. Rowstron, L. Zhou, L. Zhang, and P. Barham. Vigilante: End-to-end containment of Internet worm epidemics. ACM TOCS, 2008.
10. P. Costa, M. Migliavacca, G. P. Picco, and G. Cugola. Introducing reliability in content-based publish-subscribe through epidemic algorithms. In DEBS workshop, 2003.
11. P. Costa and G. P. Picco. Semi-probabilistic content-based publish-subscribe. In ICDCS'05, 2005.
12. G. Cugola, E. Di Nitto, and A. Fuggetta. The jedi event-based infrastructure and its application to the development of the opss wfms. IEEE TSE, 2001.
13. S. E. Deering and D. R. Cheriton. Multicast routing in datagram internetworks and extended lans. ACM TOCS, 1990.
14. E. Fidler, H.-A. Jacobsen, G. Li, and S. Mankovskii. The PADRES distributed publish/subscribe system. pages 12--30, July 2005.
15. H. Jafarpour, S. Mehrotra, and N. Venkatasubramanian. Dynamic load balancing for cluster-based publish/subscribe system. In SAINT'09, 2009.
16. G. Li, S. Hou, and H.-A. Jacobsen. A unified approach to routing, covering and merging in publish/subscribe systems based on modified binary decision diagrams. In ICDCS'05, 2005.
17. G. Li, V. Muthusamy, and H.-A. Jacobsen. Adaptive content-based routing in general overlay topologies. In Middleware, 2008.
18. G. Li, V. Muthusamy, and H.-A. Jacobsen. A distributed service-oriented architecture for business process execution. ACM TWEB, 2010.
19. H. Liu, V. Ramasubramanian, and E. G. Sirer. Client behavior and feed characteristics of rss, a publish-subscribe system for web micronews. In IMC'05, 2005.
20. J. Martins and S. Duarte. Routing algorithms for content-based publish/subscribe systems. IEEE CST, 2010.
21. G. Muhl, L. Fiege, F. C. Gartner, and A. Buchmann. Evaluating advanced routing algorithms for content-based publish/subscribe systems. In MASCOTS'02, 2002.
22. B. Mukherjee, L. T. Heberlein, and K. N. Levitt. Network intrusion detection. Network, IEEE, 1994.
23. U. of Toronto SciNet Consortium. http://www.scinet.utoronto.ca.
24. L. Opyrchal, M. Astley, J. Auerbach, G. Banavar, R. Strom, and D. Sturman. Exploiting ip multicast in content-based publish-subscribe systems. In Middleware, 2000.
25. PADRES. Available: www.msrg.org/projects/padres/.
26. C. Raiciu, D. S. Rosenblum, and M. Handley. Revisiting content-based publish/subscribe. In ICDCS Workshops 2006, 2006.
27. A. Riabov, Z. Liu, J. L. Wolf, P. S. Yu, and L. Zhang. Clustering algorithms for content-based publication-subscription systems. In ICDCS'02, 2002.
28. M. Sadoghi, M. Jergler, H.-A. Jacobsen, R. Vaculin, and R. Hull. Safe distribution and parallel execution of data-centric workflows over the publish/subscribe paradigm. IEEE TKDE, 2015.
29. Y. Tock, N. Naaman, A. Harpaz, and G. Gershinsky. Hierarchical clustering of message flows in a multicast data dissemination system. In IASTED PDCS'05, 2005.
30. R. Van Renesse, K. Birman, and W. Vogels. Astrolabe: A robust and scalable technology for distributed system monitoring, management, and data mining. ACM TOCS, 2003.
31. Y. Yoon, V. Muthusamy, and H.-A. Jacobsen. Foundations for highly available content-based publish/subscribe overlays. In ICDCS'11, 2011.
32. Y. Yoon, N. Robinson, V. Muthusamy, S. McIlraith, and H.-A. Jacobsen. Towards planning the transformation of distributed messaging middleware. In IEEE ICDCS, June 2015.
33. E. W. Zegura, K. L. Calvert, and S. Bhattacharjee. How to model an internetwork. In INFOCOM'96, 1996.

Index Terms

• Computer systems organization

  • Architectures

    • Distributed architectures

• Information systems

  • Information retrieval

• Software and its engineering

  • Software organization and properties

    • Software system structures

      • Distributed systems organizing principles