Abstract
Content-based publish/subscribe (CPS) is an appealing abstraction for building scalable distributed systems, e.g., message boards, intrusion detectors, or algorithmic stock trading platforms. Recently, CPS extensions have been proposed for location-based services like vehicular networks, mobile social networking, and so on.
Although current CPS middleware systems are dynamic in the way they support the joining and leaving of publishers and subscribers, they fall short in supporting subscription adaptations. These are becoming increasingly important across many CPS applications. In algorithmic high frequency trading, for instance, stock price thresholds that are of interest to a trader change rapidly, and gains directly hinge on the reaction time to relevant fluctuations rather than fixed values. In location-aware applications, a subscription is a function of the subscriber location (e.g. GPS coordinates), which inherently changes during motion.
The common solution for adapting a subscription consists of a resubscription, where a new subscription is issued and the superseded one canceled. This incurs substantial overhead in CPS middleware systems, and leads to missed or duplicated events during the transition. In this article, we explore the concept of parametric subscriptions for capturing subscription adaptations. We discuss desirable and feasible guarantees for corresponding support, and propose novel algorithms for updating routing mechanisms effectively and efficiently in classic decentralized CPS broker overlay networks. Compared to resubscriptions, our algorithms significantly improve the reaction time to subscription updates without hampering throughput or latency under high update rates. We also propose and evaluate approximation techniques to detect and mitigate pathological cases of high frequency subscription oscillations, which could significantly decrease the throughput of CPS systems thereby affecting other subscribers.
We analyze the benefits of our support through implementations of our algorithms in two CPS systems, and by evaluating our algorithms on two different application scenarios.
- Marcos K. Aguilera, Robert E. Strom, Daniel C. Sturman, Mark Astley, and Tushar D. Chandra. 1999. Matching events in a content-based subscription system. In Proceedings of the 18th Annual ACM Symposium on Principles of Distributed Computing (PODC). ACM, New York, NY, 53--61. DOI: http://dx.doi.org/10.1145/301308.301326. Google ScholarDigital Library
- AITE. 2005. Algorithmic trading: Hype or reality? http://www.aitegroup.com/reports/20050328.php.Google Scholar
- Amazon.com. 2013a. Amazon simple notification service (SNS). http://aws.amazon.com/sns/.Google Scholar
- Amazon.com. 2013b. Amazon simple queue service (SQS). http://aws.amazon.com/sqs/.Google Scholar
- Antonio Carzaniga, David S. Rosenblum, and Alexander L. Wolf. 2001. Design and evaluation of a wide-area event notification service. ACM Trans. Comput. Syst. 19, 3, 332--383. DOI: http://dx.doi.org/10.1145/380749.380767. Google ScholarDigital Library
- Stefano Castelli, Paolo Costa, and Gian Pietro Picco. 2008. HyperCBR: Large-scale content-based routing in a multidimensional space. In Proceedings of the 27th IEEE International Conference on Computer Communications, Joint Conference of the IEEE Computer and Communications Societies (INFOCOM). IEEE Computer Society, Los Alamitos, CA. 1714--1722. DOI: http://dx.doi.org/10.1109/INFOCOM.2008.233.Google ScholarCross Ref
- Miguel Castro, Peter Druschel, Anne-Marie Kermarrec, and Ant Rowstron. 2006. Scribe: A large-scale and decentralized application-level multicast infrastructure. IEEE J. Sel. Areas Commun. 20, 8, 1489--1499. DOI: http://dx.doi.org/10.1109/JSAC.2002.803069. Google ScholarDigital Library
- Gregory Chockler, Roie Melamed, Yoav Tock, and Roman Vitenberg. 2007. SpiderCast: A scalable interest-aware overlay for topic-based pub/sub communication. In Proceedings of the Inaugural International Conference on Distributed Event-Based Systems (DEBS). ACM, 14--25. DOI: http://dx.doi.org/10.1145/1266894.1266899. Google ScholarDigital Library
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. 2009. Introduction to Algorithms 3rd Ed. The MIT Press. Google ScholarDigital Library
- Gianpaolo Cugola, Alessandro Margara, and Matteo Migliavacca. 2009. Context-aware publish-subscribe: Model, implementation, and evaluation. In Proceedings of the 14th IEEE Symposium on Computers and Communications (ISCC). IEEE Computer Society, 875--881. DOI: http://dx.doi.org/10.1109/ISCC.2009.5202277.Google ScholarCross Ref
- Stephen E. Deering and David R. Cheriton. 1990. Multicast routing in datagram Internetworks and extended LANs. ACM Trans. Comput. Syst. 8, 2, 85--110. DOI: http://dx.doi.org/10.1145/78952.78953. Google ScholarDigital Library
- The Economist. 2006. Moving markets: Shifts in trading patterns are making technology ever more important. http://www.economist.com/business-finance/displaystory. cfm?story_id=E1 VQSVPRT.Google Scholar
- Patrick Eugster and K. R. Jayaram. 2009. EventJava: An extension of Java for event correlation. In Proceedings of the 23rd European Conference on Object-Oriented Programming (ECOOP). Springer-Verlag, Berlin, 570--594. DOI: http://dx.doi.org/10.1007/978-3-642-03013-0.26. Google ScholarDigital Library
- Patrick Th. Eugster and Rachid Guerraoui. 2002. Probabilistic multicast. In Proceedings of the International Conference on Dependable Systems and Networks (DSN). IEEE Computer Society, 313--324. http://dl.acm.org/citation.cfm?id=647883.738400. Google ScholarDigital Library
- Fernando, Stephen. 2013. Marketcetera trading platform. http://www.marketcetera.com/site/.Google Scholar
- Ludger Fiege, Felix C. Gärtner, Oliver Kasten, and Andreas Zeidler. 2003. Supporting mobility in content-based publish/subscribe middleware. In Proceedings of the ACM/IFIP/USENIX International Conference on Middleware (Middleware). Springer-Verlag, Berlin, 103--122. http://dl.acm.org/citation.cfm?id=1515915.1515923. Google ScholarDigital Library
- Fiorano. 2013. FioranoMQ JMS server. http://www.fiorano.com/products/Enterprise-Messaging/JMS/Java-Message-Service/FioranoMQ.php.Google Scholar
- Charles Lanny Forgy. 1979. On the efficient implementation of production systems. Ph.D. dissertation, AAI7919143, Carnegie Mellon University, Pittsburgh, PA.Google Scholar
- Apache Software Foundation. 2013. ActiveMQ. http://activemq.apache.org/.Google Scholar
- Abhishek Gupta, Ozgur D. Sahin, Divyakant Agrawal, and Amr El Abbadi. 2004. Meghdoot: Content-based publish/subscribe over P2P networks. In Proceedings of the 5th ACM/IFIP/USENIX International Conference on Middleware (Middleware). Springer-Verlag, Berlin, 254--273. http://dl.acm.org/citation.cfm?id=1045658.1045677. Google ScholarDigital Library
- Adrian Holzer, Saida Maaroufi, and Samuel Pierre. 2010. DYMES: A dynamic messaging service for VANETs. In Proceedings of IEEE 6th International Conference on Wireless and Mobile Computing, Networking and Communications (WiMob). IEEE Computer Society, 513--520. DOI: http://dx.doi.org/10.1109/WIMOB.2010.5645017.Google ScholarCross Ref
- Yongqiang Huang and Hector Garcia-Molina. 2007. Parameterized subscriptions in publish/subscribe systems. Data Knowl. Eng. 60, 3, 435--450. : http://dx.doi.org/10.1016/j.datak.2006.03.010. Google ScholarDigital Library
- IBM. 2013. Websphere MQ. http://www-01.ibm.com/software/integration/wmq/.Google Scholar
- Hojjat Jafarpour, Bijit Hore, Sharad Mehrotra, and Nalini Venkatasubramanian. 2008. Subscription subsumption evaluation for content-based publish/subscribe systems. In Proceedings of the 9th ACM/IFIP/USENIX International Conference on Middleware (Middleware). Springer-Verlag, Berlin, 62--81. http://dl.acm.org/citation.cfm?id=1496950.1496955. Google ScholarDigital Library
- Hojjat Jafarpour, Bijit Hore, Sharad Mehrotra, and Nalini Venkatasubramanian. 2009. CCD: Efficient customized content dissemination in distributed publish/subscribe. In Proceedings of the 10th ACM/IFIP/USENIX International Conference on Middleware (Middleware). Springer-Verlag, Berlin, Article 4. http://dl.acm.org/citation.cfm?id=1656980.1656986. Google ScholarDigital Library
- Zbigniew Jerzak and Christof Fetzer. 2008. Bloom filter based routing for content-based publish/subscribe. In Proceedings of the 2nd International Conference on Distributed Event-based Systems (DEBS). ACM, 71--81. DOI: http://dx.doi.org/10.1145/1385989.1385999. Google ScholarDigital Library
- Yuhui Jin and Rob Strom. 2003. Relational subscription middleware for Internet-scale publish-subscribe. In Proceedings of the 2nd International Workshop on Distributed Event-Based Systems (DEBS). ACM, 1--8. : http://dx.doi.org/10.1145/966618.966638. Google ScholarDigital Library
- Rob Lati. 2009. The real story of trading software espionage. http://advancedtrading.com/algorithms/showArticle.jhtml?articleID=21840150.Google Scholar
- Guoli Li, Shuang Hou, and Hans-Arno Jacobsen. 2005. A unified approach to routing, covering and merging in publish/subscribe systems based on modified binary decision diagrams. In Proceedings of the 25th IEEE International Conference on Distributed Computing Systems (ICDCS). IEEE Computer Society, 447--457. DOI: http://dx.doi.org/10.1109/ICDCS.2005.8. Google ScholarDigital Library
- René Meier and Vinny Cahill. 2010. On event-based middleware for location-aware mobile applications. IEEE Trans. Softw. Eng. 36, 3, 409--430. DOI: http://dx.doi.org/10.1109/TSE.2009.90. Google ScholarDigital Library
- NYSE. 2013. NYSE technologies and Marketcetera launch new era software-as-a-service trading platform. http://www.nyse.com/press/1245924443893.html.Google Scholar
- Nathaniel Nystrom, Michael R. Clarkson, and Andrew C. Myers. 2003. Polyglot: An extensible compiler framework for Java. In Proceedings of the 12th International Conference on Compiler Construction (CC). Springer-Verlag, Berlin, 138--152. http://dl.acm.org/citation.cfm?id=1765931.1765947. Google ScholarDigital Library
- OpenJMS. 2013. An open source implementation of Sun’s JMS specification. http://openjms.sourceforge.net/index.html.Google Scholar
- Oracle. 2013a. Java Message Service (JMS). http://www.oracle.com/technetwork/java/index-jsp-142945.html.Google Scholar
- Oracle. 2013b. Oracle WebLogic (formerly BEA WebLogic). http://www.oracle.com/us/products/middleware/application-server/index.htm.Google Scholar
- Peter R. Pietzuch and Jean Bacon. 2002. Hermes: A distributed event-based middleware architecture. In Proceedings of the 22nd International Conference on Distributed Computing Systems (ICDCSW). IEEE Computer Society, 611--618. http://dl.acm.org/citation.cfm?id=646854.708058. Google ScholarDigital Library
- RedHat. 2013. JBoss Messaging. http://www.jboss.org/jbossmessaging.Google Scholar
- Stan Schneider. 2013. The data-centric future. http://www.rti.com/whitepapers/Data-Centric_Future_Pt1.pdf.Google Scholar
- Scarlet Schwiderski-Grosche and Ken Moody. 2009. The SpaTeC composite event language for spatio-temporal reasoning in mobile systems. In Proceedings of the 3rd ACM International Conference on Distributed Event-Based Systems (DEBS). ACM, Article 11. DOI: http://dx.doi.org/10.1145/1619258.1619273. Google ScholarDigital Library
- SpringSource 2013. RabbitMQ: Messaging that just works. SpringSource. http://www.rabbitmq.com/.Google Scholar
- Peter Triantafillou and Andreas Economides. 2004. Subscription summarization: A new paradigm for efficient publish/subscribe systems. In Proceedings of the 24th International Conference on Distributed Computing Systems (ICDCS). IEEE Computer Society, 562--571. http://dl.acm.org/citation.cfm?id=977400.977996. Google ScholarDigital Library
- Robbert Van Renesse, Kenneth P. Birman, and Werner Vogels. 2003. Astrolabe: A robust and scalable technology for distributed system monitoring, management, and data mining. ACM Trans. Comput. Syst. 21, 2, 164--206. DOI: http://dx.doi.org/10.1145/762483.762485. Google ScholarDigital Library
- Praveen Yalagandula and Mike Dahlin. 2004. A scalable distributed information management system. SIGCOMM Comput. Commun. Rev. 34, 4, 379--390. DOI: http://dx.doi.org/10.1145/1030194.1015509. Google ScholarDigital Library
- Chi Zhang, Arvind Krishnamurthy, Randolph Y. Wang, and Jaswinder Pal Singh. 2005. Combining flexibility and scalability in a peer-to-peer publish/subscribe system. In Proceedings of the ACM/IFIP/USENIX International Conference on Middleware (Middleware). Springer-Verlag, Berlin, 102--123. http://dl.acm.org/citation.cfm?id=1515890.1515896. Google ScholarDigital Library
Index Terms
- Parametric Content-Based Publish/Subscribe
Recommendations
Securing Broker-Less Publish/Subscribe Systems Using Identity-Based Encryption
The provisioning of basic security mechanisms such as authentication and confidentiality is highly challenging in a content-based publish/subscribe system. Authentication of publishers and subscribers is difficult to achieve due to the loose coupling of ...
Total Order in Content-Based Publish/Subscribe Systems
ICDCS '12: Proceedings of the 2012 IEEE 32nd International Conference on Distributed Computing SystemsTotal ordering is a messaging guarantee increasingly required of content-based pub/sub systems, which are traditionally focused on performance. The main challenge is the uniform ordering of streams of publications from multiple publishers within an ...
Geographical distribution of subscriptions for content-based publish/subscribe in MANETs
Companion '08: Proceedings of the ACM/IFIP/USENIX Middleware '08 Conference CompanionEstablishing content-based publish/subscribe in the resource constrained and failure prone environment of Mobile Ad-Hoc Networks (MANETs) is a highly challenging task. Movement of nodes and network partitioning can require frequent and possibly ...
Comments