Distributed event aggregation for content-based publish/subscribe systems

ABSTRACT

Modern data-intensive applications handling massive event streams such as real-time traffic monitoring require support for both rich data filtering and aggregation. While the pub/sub communication paradigm provides an effective solution for the sought semantic diversity of event filtering, the event processing capabilities of existing pub/sub systems are restricted to singular event matching without support for stream aggregation, which so far can be accommodated only at the subscriber edge brokers.

In this paper, we propose the first systematic solution for supporting distributed aggregation over a range of time-based aggregation window semantics in a content-based pub/sub system. In order to eschew the need to disseminate a large number of publications to subscribers, we strive to distribute the aggregation computation within the pub/sub overlay network. By enriching the pub/sub language with aggregation semantics, we allow pub/sub brokers to aggregate incoming publications and forward only results to the next broker downstream. We show that our baseline solutions, one which aggregates early (at the publisher edge) and another which aggregates late (at the subscriber edge), are not optimal strategies for minimizing bandwidth consumption. We then propose an adaptive rate-based heuristic solution which determines which brokers should aggregate publications. Using real datasets extracted from our traffic monitoring use case, we show that this adaptive solution leads to improved performance compared to that of our baseline solutions.

References

1. S. F. Abelsen, H. Gjermundrd, D. E. Bakken, and C. H. Hauser. Adaptive data stream mechanism for control and monitoring applications. In Proc. of ADAPTIVE, pages 86--91, 2009.
2. B. Arai, G. Das, D. Gunopulos, and V. Kalogeraki. Efficient approximate query processing in peer-to-peer networks. IEEE Trans. on Knowl. and Data Eng., 19(7):919--933, 2007.
3. A. Arasu, M. Cherniack, E. Galvez, D. Maier, A. S. Maskey, E. Ryvkina, M. Stonebraker, and R. Tibbetts. Linear road: a stream data management benchmark. In Proc. of VLDB, pages 480--491, 2004.
4. R. Baldoni, L. Querzoni, S. Tarkoma, and A. Virgillito. Distributed event routing in publish/subscribe systems. Chapter 10 in the book MiNEMA, pages 219--244, 2009.
5. S. Biswas, M. Taghizadeh, and F. Dion. Vehicle-to-vehicle wireless communication protocols for enhancing highway traffic safety. IEEE comm. mag., 44(1):74--82, 2006.
6. L. Brenna, J. Gehrke, M. Hong, and D. Johansen. Distributed event stream processing with non-deterministic finite automata. In Proc. of DEBS, pages 1--12, 2009.
7. A. Carzaniga, D. S. Rosenblum, and A. L. Wolf. Design and evaluation of a wide-area event notification service. ACM Tran. on Computer Systems, 19(3):332--383, 2001.
8. B. Chandramouli and J. Yang. End-to-end support for joins in large-scale publish/subscribe systems. VLDB Endowment, 1(1):434--450, 2008.
9. J. Chen, L. Ramaswamy, and D. Lowenthal. Towards efficient event aggregation in a decentralized publish-subscribe system. In Proc. of DEBS, pages 1--11, 2009.
10. A. Demers, J. Gehrke, M. Hong, M. Riedewald, and W. White. Towards expressive publish/subscribe systems. In Proc. of EDBT, pages 627--644, 2006.
11. T. Fawcett and F. Provost. Activity monitoring: noticing interesting changes in behavior. In Proc. of SIGKDD, pages 53--62, 1999.
12. E. Fidler, H.-A. Jacobsen, G. Li, and S. Mankovski. The padres distributed publish/subscribe system. In Proc. of ICFI, pages 12--30, 2005.
13. S. Frischbier, A. Margara, T. Freudenreich, P. Eugster, D. Eyers, and P. Pietzuch. ASIA: application-specific integrated aggregation for publish/subscribe middleware. In Proc. of Middleware (Poster Paper), pages 1--2, 2012.
14. S. Frischbier, A. Margara, T. Freudenreich, P. Eugster, D. Eyers, and P. Pietzuch. Aggregation for implicit invocations. In Proc. of AOSD, pages 109--120, 2013.
15. L. Golab, K. G. Bijay, and M. T. Özsu. Multi-query optimization of sliding window aggregates by schedule synchronization. In Proc. of CIKM, pages 844--845, 2006.
16. IBM Corp. An architectural blueprint for autonomic computing. IBM White Paper, 2004.
17. N. Jain, D. Kit, P. Mahajan, P. Yalagandula, M. Dahlin, and Y. Zhang. STAR: self-tuning aggregation for scalable monitoring. In Proc. of VLDB, pages 962--973, 2007.
18. K. R. Jayaram, C. Jayalath, and P. Eugster. Parametric subscriptions for content-based publish/subscribe networks. In Proc. of Middleware, pages 128--147, 2010.
19. M. Jelasity, A. Montresor, and O. Babaoglu. Gossip-based aggregation in large dynamic networks. ACM Trans. Comput. Syst., 23(3):219--252, 2005.
20. Z. Jerzak and C. Fetzer. Handling overload in publish/subscribe systems. In Proc. of ICDCSW, pages 32--37, 2006.
21. P. Jesus, C. Baquero, and P. S. Almeida. A survey of distributed data aggregation algorithms. Technical report, University of Minho, 2011.
22. R. S. Kazemzadeh and H.-A. Jacobsen. Opportunistic multipath forwarding in content-based publish/subscribe overlays. In ACM Middleware, pages 249--270, 2012.
23. I. Koenig. Event processing as a core capability of your content distribution fabric. In Gartner Event Processing Summit, 2007.
24. A. Koulakezian and A. Leon-Garcia. CVI: Connected vehicle infrastructure for ITS. In Proc. of PIMRC, pages 750--755, 2011.
25. S. Krishnamurthy, C. Wu, and M. Franklin. On-the-fly sharing for streamed aggregation. In Proc. of SIGMOD, pages 623--634, 2006.
26. G. Li, V. Muthusamy, and H.-A. Jacobsen. A distributed service-oriented architecture for business process execution. ACM Trans. Web, 4(1):2:1--2:33, Jan. 2010.
27. V. Muthusamy, H.-A. Jacobsen, T. Chau, A. Chan, and P. Coulthard. SLA-driven business process management in SOA. In CASCON, pages 86--100, 2009.
28. T. Repantis and V. Kalogeraki. Hot-spot prediction and alleviation in distributed stream processing applications. In Proc. of DSN, pages 346--355, 2008.
29. I. Rose, R. Murty, P. Pietzuch, J. Ledlie, M. Roussopoulos, and M. Welsh. Cobra: content-based filtering and aggregation of blogs and RSS feeds. In Proc. of NSDI, 2007.
30. A. Schröter, D. Graff, G. Mühl, J. Richling, and H. Parzyjegla. Self-optimizing hybrid routing in publish/subscribe systems. In Proc. of DSOM, pages 111--122, 2009.
31. V. Setty, G. Kreitz, R. Vitenberg, M. van Steen, G. Urdaneta, and S. Gimåker. The hidden pub/sub of Spotify: (industry article). In Proc. of DEBS, pages 231--240, 2013.
32. J. Sventek and A. Koliousis. Unification of publish/subscribe systems and stream databases: the impact on complex event processing. In Proc. of Middleware, pages 292--311, 2012.
33. Y. Tock, N. Naaman, A. Harpaz, and G. Gershinsky. Hierarchical clustering of message flows in a multicast data dissemination system. In Proc. of PDCS, pages 320--326, 2005.
34. R. Van Renesse, K. P. Birman, and W. Vogels. Astrolabe: A robust and scalable technology for distributed system monitoring, management, and data mining. ACM Trans. Comput. Syst., 21(2):164--206, 2003.
35. R. van Renesse and A. Bozdog. Willow: DHT, aggregation, and publish/subscribe in one protocol. In Proc. of IPTPS, pages 173--183, 2004.
36. M. Wood and K. Marzullo. The design and implementation of Meta. In Reliable Distributed Computing with the Isis Toolkit, pages 309--327, 1994.
37. S. Wu, B. C. Ooi, and K.-L. Tan. Continuous sampling for online aggregation over multiple queries. In Proc. of SIGMOD, pages 651--662, 2010.
38. P. Yalagandula and M. Dahlin. A scalable distributed information management system. SIGCOMM Comput. Commun. Rev., 34(4):379--390, 2004.
39. P. Yalagandula and M. Dahlin. Shruti: A Self-Tuning Hierarchical Aggregation System. In Proc. of SASO, pages 141--150, 2007.

Index Terms

• Software and its engineering

  • Software organization and properties

    • Software system structures

      • Distributed systems organizing principles

        • Organizing principles for web applications