Summary-based routing for content-based event distribution networks

ABSTRACT

Providing scalable distributed Web-based eventing services has been an important research topic. It is desirable to have an effective mechanism for the servers to summarize their filters for in-network preprocessing in order to optimize system performance. In this paper, we propose a summary-based routing mechanism and introduce the notion of imprecise summaries to provide a trade-off between routing overhead and event traffic. Our system uses similarity-based filter clustering to reduce overall event traffic and performs self-tuning summary precision selection to optimize throughput. We have implemented summary-based routing on top of an XML-based infrastructure that closely follows the proposed Web services standards. Measurements from the actual implementation validate our analytical and simulation results, and demonstrate the practical benefits of the proposed techniques.

REFERENCES

• 1: Atul Adya , Paramvir Bahl , Lili Qiu, Characterizing Alert and Browse Services of Mobile Clients, Proceedings of the General Track: 2002 USENIX Annual Technical Conference, p.343-356, June 10-15, 2002
• 2: Marcos K. Aguilera , Robert E. Strom , Daniel C. Sturman , Mark Astley , Tushar D. Chandra, Matching events in a content-based subscription system, Proceedings of the eighteenth annual ACM symposium on Principles of distributed computing, p.53-61, May 04-06, 1999, Atlanta, Georgia, United States [doi>10.1145/301308.301326]
• 3: Martin F. Arlitt , Carey L. Williamson, Internet Web servers: workload characterization and performance implications, IEEE/ACM Transactions on Networking (TON), v.5 n.5, p.631-645, Oct. 1997 [doi>10.1109/90.649565]
• 4: An Efficient Multicast Protocol for Content-Based Publish-Subscribe Systems, Proceedings of the 19th IEEE International Conference on Distributed Computing Systems, p.262, May 31-June 04, 1999
• 5: R. Bayer and E. McCreight. Organization and maintenance of large ordered indices. In Proc. 1970 ACM-SIGFIDET Workshop on Data Description and Access, Nov. 1970.
• 6: Burton H. Bloom, Space/time trade-offs in hash coding with allowable errors, Communications of the ACM, v.13 n.7, p.422-426, July 1970 [doi>10.1145/362686.362692]
• 7: L. Breslau, P. Cao, L. Fan, G. Phillips, and S. Shenker. Web Caching and Zipf-like Distributions: Evidence and Implications. In Proceedings of INFOCOMM '99, March 1999.
• 8: A. Carzaniga, J. Deng, and A. L. Wolf. Fast forwarding for content-based networking. In Technical Report CU-CS-922-01, Department of Computer Science, University of Colorado, Nov. 2001.
• 9: Design and evaluation of a wide-area event notification service, ACM Transactions on Computer Systems (TOCS), v.19 n.3, p.332-383, Aug. 2001 [doi>10.1145/380749.380767]
• 10: C. Y. Chan, M. Garofalakis, and R. Rastogi. RE-Tree: An efficient index structure for regular expressions. In Proc. of VLDB '2002, 2002.
• 11: Françoise Fabret , H. Arno Jacobsen , François Llirbat , Joăo Pereira , Kenneth A. Ross , Dennis Shasha, Filtering algorithms and implementation for very fast publish/subscribe systems, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.115-126, May 21-24, 2001, Santa Barbara, California, United States
• 12: C. E. Ferreira , A. Martin , C. C. de Souza , R. Weismantel , L. A. Wolsey, The node capacitated graph partitioning problem: a computational study, Mathematical Programming: Series A and B, v.81 n.2, p.229-256, April 1, 1998 [doi>10.1007/BF01581107]
• 13: Y. J. Garcia, M. A. Lopez, and S. T. Leutenegger. A greedy algorithm for bulk loading R-trees. In Univ. of Denver Computer Science Tech. Report #97-02, 1997.
• 14: J. Gough and G. Smith. Efficient recognition of events in a distributed system. In Proc. of the 18 th Australasian Computer Science Conference, Feb. 1995.
• 15: R. Gruber, B. Krishnamurthy, and E. Panagos. The architecture of the ready event notification service. In Proc. of the 19th IEEE International Conference on Distributed Computing Systems Middleware Workshop, 1999.
• 16: Antonin Guttman, R-trees: a dynamic index structure for spatial searching, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
• 17: Bruce Hendrickson , Robert Leland, A multilevel algorithm for partitioning graphs, Proceedings of the 1995 ACM/IEEE conference on Supercomputing (CDROM), p.28-es, December 04-08, 1995, San Diego, California, United States [doi>10.1145/224170.224228]
• 18: Anil K. Jain , Richard C. Dubes, Algorithms for clustering data, Prentice-Hall, Inc., Upper Saddle River, NJ, 1988
• 19: Weighted min cut. http://riot.ieor.berkeley.edu/riot/Applications/WeightedMinCut/.
• 20: Lukasz Opyrchal , Mark Astley , Joshua Auerbach , Guruduth Banavar , Robert Strom , Daniel Sturman, Exploiting IP multicast in content-based publish-subscribe systems, IFIP/ACM International Conference on Distributed systems platforms, p.185-207, April 03-07, 2000, New York, New York, United States
• 21: Venkata N. Padmanabhan , Lili Qiu, The content and access dynamics of a busy Web site: findings and implications, Proceedings of the conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, p.111-123, August 28-September 01, 2000, Stockholm, Sweden
• 22: S. Ratnasamy, M. Handley, R. Karp, and S. Shenker. Topologically-aware overlay construction and server selection. In Proc. of IEEE INFOCOM, Jun. 2002.
• 23: Anton Riabov , Zhen Liu , Joel L. Wolf , Philip S. Yu , Li Zhang, Clustering Algorithms for Content-Based Publication-Subscription Systems, Proceedings of the 22 nd International Conference on Distributed Computing Systems (ICDCS'02), p.133, July 02-05, 2002
• 24: Antony I. T. Rowstron , Anne-Marie Kermarrec , Miguel Castro , Peter Druschel, SCRIBE: The Design of a Large-Scale Event Notification Infrastructure, Proceedings of the Third International COST264 Workshop on Networked Group Communication, p.30-43, November 07-09, 2001
• 25: B. Segall and D. Arnold. Elvin has left the building: A publish /subscribe notification service with quenching. In Proc. of AUUG, 1997.
• 26: Alex C. Snoeren , Kenneth Conley , David K. Gifford, Mesh-based content routing using XML, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 27: Yi-Min Wang , Paramvir Bahl , Wilf Russell, The SIMBA User Alert Service Architecture for Dependable Alert Delivery, Proceedings of the 2001 International Conference on Dependable Systems and Networks (formerly: FTCS), p.463-474, July 01-04, 2001
• 28: Y. M. Wang, L. Qiu, D. Achlioptas, G. Das, P. Larson, and H. J. Wang. Subscription partitioning and routing in content-based publish/subscribe networks (Brief Announcement). In Proc. of DISC, Oct. 2002.
• 29: T. Wong, R. H. Katz, and S. McCanne. An evaluation on using preference clustering in large-scale multicast applications. In Proc. of INFOCOM, pages 451--460, 2000.
• 30: Web Services standards. http://www.webservices.org/index.php/standards/.
• 31: Haobo Yu , Deborah Estrin , Ramesh Govindan, A Hierarchical Proxy Architecture for Internet-Scale Event Services, Proceedings of the 8th Workshop on Enabling Technologies on Infrastructure for Collaborative Enterprises, p.78-83, June 16-18, 1999