More Web Proxy on the site http://driver.im/

research-article

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

Authors:

Hans-Arno JacobsenAuthors Info & Claims

Middleware '15: Proceedings of the 16th Annual Middleware Conference

Pages 13 - 24

https://doi.org/10.1145/2814576.2814801

Published: 24 November 2015 Publication History

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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[4]

C. Canas, K. Zhang, B. Kemme, J. Kienzle, and H.-A. Jacobsen. Publish/Subscribe network designs for multiplayer games. In ACM Middleware, 2014.

Digital Library

[5]

F. Cao and J. P. Singh. Medym: Match-early with dynamic multicast for content-based publish-subscribe networks. In Middleware, 2005.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[11]

P. Costa and G. P. Picco. Semi-probabilistic content-based publish-subscribe. In ICDCS'05, 2005.

Digital Library

[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.

Digital Library

[13]

S. E. Deering and D. R. Cheriton. Multicast routing in datagram internetworks and extended lans. ACM TOCS, 1990.

Digital Library

[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.

Digital Library

[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.

Digital Library

[17]

G. Li, V. Muthusamy, and H.-A. Jacobsen. Adaptive content-based routing in general overlay topologies. In Middleware, 2008.

Digital Library

[18]

G. Li, V. Muthusamy, and H.-A. Jacobsen. A distributed service-oriented architecture for business process execution. ACM TWEB, 2010.

Digital Library

[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.

Digital Library

[20]

J. Martins and S. Duarte. Routing algorithms for content-based publish/subscribe systems. IEEE CST, 2010.

Digital Library

[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.

Digital Library

[22]

B. Mukherjee, L. T. Heberlein, and K. N. Levitt. Network intrusion detection. Network, IEEE, 1994.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[31]

Y. Yoon, V. Muthusamy, and H.-A. Jacobsen. Foundations for highly available content-based publish/subscribe overlays. In ICDCS'11, 2011.

Digital Library

[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.

Digital Library

Cited By

Ji STang ZWang WLi HYao JJacobsen HSchiavoni VEdinger JCao JJin Z(2024)Ripple: Large-Scale Service and Configuration Management in the CloudProceedings of the 25th International Middleware Conference10.1145/3652892.3700777(354-366)Online publication date: 2-Dec-2024
https://dl.acm.org/doi/10.1145/3652892.3700777
Ramprasad BMishra PPeixoto MDe Lara E(2024)StreamBucket: In-Network Adaptation for Late-Binding Stream Processing Systems2024 IEEE 13th International Conference on Cloud Networking (CloudNet)10.1109/CloudNet62863.2024.10815795(1-9)Online publication date: 27-Nov-2024
https://doi.org/10.1109/CloudNet62863.2024.10815795
Nguyen HUddin MVenkatasubramanian N(2019)Multistage Adaptive Load Balancing for Big Active Data Publish Subscribe SystemsProceedings of the 13th ACM International Conference on Distributed and Event-based Systems10.1145/3328905.3329508(43-54)Online publication date: 24-Jun-2019
https://dl.acm.org/doi/10.1145/3328905.3329508
Show More Cited By

Index Terms

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

Recommendations

A Content-Based Publish/Subscribe over Two-Tier DHT Utilizing Domain Ontology
AINA '11: Proceedings of the 2011 IEEE International Conference on Advanced Information Networking and Applications

Several design alternatives have been advocated for content-based publish subscribe communication infrastructure over structured peer to peer networks. These efforts have contributed significantly towards efficient implementations of subscription ...
Infrastructure-free content-based publish/subscribe

Peer-to-peer (P2P) networks can offer benefits to distributed content-based publish/subscribe data dissemination systems. In particular, since a P2P network's aggregate resources grow as the number of participants increases, scalability can be achieved ...
Clustering mechanism for content-based system in DHT-based overlay networks
ACOS'06: Proceedings of the 5th WSEAS international conference on Applied computer science

A generic pub/sub communication system (often referred to in the literature as Event Service or Notification Service) is composed of a set of nodes distributed over a communication network. Clients to the systems are divided according to their role into ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

Middleware '15: Proceedings of the 16th Annual Middleware Conference

November 2015

295 pages

ISBN:9781450336185

DOI:10.1145/2814576

General Chairs:
Rodger Lea
The University of British Columbia, Canada
,
Sathish Gopalakrishnan
The University of British Columbia, Canada
,
Program Chairs:
Eli Tilevich
Virginia Tech, USA
,
Amy L. Murphy
Bruno Kessler Foundation, Italy
,
Publications Chair:
Michael Blackstock
The University of British Columbia, Canada

Copyright © 2015 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

ACM: Association for Computing Machinery
USENIX Assoc: USENIX Assoc
IFIP: International Federation for Information Processing

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 24 November 2015

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed limited

Funding Sources

Alexander von Humboldt Foundation
NSERC Discovery Grant
National Natural Science Foundation of China

Conference

Middleware '15

Sponsor:

ACM
USENIX Assoc
IFIP

Middleware '15: 16th International Middleware Conference

December 7 - 11, 2015

BC, Vancouver, Canada

Acceptance Rates

Middleware '15 Paper Acceptance Rate 23 of 118 submissions, 19%;

Overall Acceptance Rate 203 of 948 submissions, 21%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
184
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)0

Reflects downloads up to 21 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Ji STang ZWang WLi HYao JJacobsen HSchiavoni VEdinger JCao JJin Z(2024)Ripple: Large-Scale Service and Configuration Management in the CloudProceedings of the 25th International Middleware Conference10.1145/3652892.3700777(354-366)Online publication date: 2-Dec-2024
https://dl.acm.org/doi/10.1145/3652892.3700777
Ramprasad BMishra PPeixoto MDe Lara E(2024)StreamBucket: In-Network Adaptation for Late-Binding Stream Processing Systems2024 IEEE 13th International Conference on Cloud Networking (CloudNet)10.1109/CloudNet62863.2024.10815795(1-9)Online publication date: 27-Nov-2024
https://doi.org/10.1109/CloudNet62863.2024.10815795
Nguyen HUddin MVenkatasubramanian N(2019)Multistage Adaptive Load Balancing for Big Active Data Publish Subscribe SystemsProceedings of the 13th ACM International Conference on Distributed and Event-based Systems10.1145/3328905.3329508(43-54)Online publication date: 24-Jun-2019
https://dl.acm.org/doi/10.1145/3328905.3329508
Ji SJacobsen H(2018)PS-tree-based efficient boolean expression matching for high-dimensional and dense workloadsProceedings of the VLDB Endowment10.14778/3291264.329127012:3(251-264)Online publication date: 1-Nov-2018
https://dl.acm.org/doi/10.14778/3291264.3291270
Dulay NMicheletti MMostarda LPiermarteri A(2018)PICO-MP: De-centralised Macro-Programming for Wireless Sensor and Actuator Networks2018 IEEE 32nd International Conference on Advanced Information Networking and Applications (AINA)10.1109/AINA.2018.00052(289-296)Online publication date: May-2018
https://doi.org/10.1109/AINA.2018.00052
Doblander CGhinaiya TZhang KJacobsen HGal AWeidlich MKalogeraki VVenkasubramanian N(2016)Shared dictionary compression in publish/subscribe systemsProceedings of the 10th ACM International Conference on Distributed and Event-based Systems10.1145/2933267.2933308(117-124)Online publication date: 13-Jun-2016
https://dl.acm.org/doi/10.1145/2933267.2933308
Bhowmik STariq MHegazy LRothermel K(2016)Hybrid Content-Based Routing Using Network and Application Layer Filtering2016 IEEE 36th International Conference on Distributed Computing Systems (ICDCS)10.1109/ICDCS.2016.16(221-231)Online publication date: Jun-2016
https://doi.org/10.1109/ICDCS.2016.16

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents