Yi-Min Wang
Paul Larson
Skip Abstract Section
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.
- A. Adya, P. Bahl, and L. Qiu. Characterizing alert and browse services for mobile clients. In Proc. of USENIX Annual Conference, Jun. 2002. Google Scholar
Digital Library
- M. K. Aguilera, R. E. Strom, D. C. Sturman, M. Astley, and T. D. Chandra. Matching events in a content-based subscription system. In Symposium on Principles of Distributed Computing, pages 53--61, 1999. Google ScholarDigital Library
- M. F. Arlitt and C. L. Williamson. Internet Web Servers: Workload Characterization and Performance Implications. In IEEE/ACM Transactions on Networking, pages 631--645, 1997. Google ScholarDigital Library
- G. Banavar, T. D. Chandra, B. Mukherjee, J. Nagarajarao, R. E. Strom, and D. C. Sturman. An efficient multicast protocol for content-based publish-subscribe systems. In International Conference on Distributed Computing Systems, pages 262--272, 1999. Google ScholarDigital Library
- 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.Google ScholarDigital Library
- B. H. Bloom. Space/time trade-offs in hash coding with allowable errors. Communications of the ACM, 13(7):422--426, 1970. Google ScholarDigital Library
- 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.Google ScholarCross Ref
- 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.Google ScholarCross Ref
- A. Carzaniga, D. S. Rosenblum, and A. L. Wolf. Design and evaluation of a wide-area event notification service. ACM Transactions on Computer Systems, 19(3):332--383, 2001. Google ScholarDigital Library
- C. Y. Chan, M. Garofalakis, and R. Rastogi. RE-Tree: An efficient index structure for regular expressions. In Proc. of VLDB '2002, 2002. Google ScholarDigital Library
- F. Fabret, H. A. Jacobsen, F. Llirbat, J. Pereira, K. A. Ross, and D. Shasha. Filtering algorithms and implementation for very fast publish/subscribe. In Proc. of SIGMOD Conference, 2001. Google ScholarDigital Library
- C. E. Ferreira, A. Martin, C. C. de Souza, R. Weismantel, and L. A. Wolsey. The node capacitated graph partitioning problem: A computational study. In Mathematical Programming, 1996. Google ScholarDigital Library
- 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.Google Scholar
- 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.Google Scholar
- 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.Google ScholarCross Ref
- A. Guttman. R-trees: A dynamic index structure for spatial searching. In Proc. of ACM SIGMOD Conference, 1984. Google ScholarDigital Library
- B. Hendrickson and R. Leland. A multilevel algorithm for partitioning graphs. In Proc. of Supercomputing, 1995. Google ScholarDigital Library
- A. K. Jain and Dubes. Algorithms for clustering data. 1988. Google ScholarDigital Library
- Weighted min cut. http://riot.ieor.berkeley.edu/riot/Applications/WeightedMinCut/.Google Scholar
- L. Opyrchal, M. Astley, J. S. Auerbach, G. Banavar, R. E. Strom, and D. C. Sturman. Exploiting IP multicast in content-based publish-subscribe systems. In Proc. of Middleware, pages 185--207, 2000. Google ScholarDigital Library
- V. N. Padmanabhan and L. Qiu. The Content and Access Dynamics of a Busy Web Site: Findings and Implications. In Proceedings ACM SIG-COMM 2000, August 2000. Google ScholarDigital Library
- S. Ratnasamy, M. Handley, R. Karp, and S. Shenker. Topologically-aware overlay construction and server selection. In Proc. of IEEE INFOCOM, Jun. 2002.Google ScholarCross Ref
- A. Riabov, Z. Liu, J. L. Wolf, P. S. Yu, and L. Zhang. Clustering algorithms for content-based publication-subscription systems. In Proc. of ICDCS, 2002. Google ScholarDigital Library
- A. I. T. Rowstron, A. M. Kermarrec, M. Castro, and P. Druschel. SCRIBE: The design of a large-scale event notification infrastructure. In International Workshop on Networked Group Communication, pages 30--43, 2001. Google ScholarDigital Library
- B. Segall and D. Arnold. Elvin has left the building: A publish /subscribe notification service with quenching. In Proc. of AUUG, 1997.Google Scholar
- Alex C. Snoeren, Kenneth Conley, and David K. Gifford. Mesh-based content routing using xml. In ACM Symposium on Operating System Principles, Oct. 2001. Google ScholarDigital Library
- Y. M. Wang, P. Bahl, and W. Russell. The SIMBA user alert service architecture for dependable alert delivery. In IEEE Int. Conf. on Dependable Systems and Networks (DSN), 2001. Google ScholarDigital Library
- 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.Google Scholar
- 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.Google Scholar
- Web Services standards. http://www.webservices.org/index.php/standards/.Google Scholar
- H. Yu, D. Estrin, and R. Govindan. A hierarchical proxy architecture for internet-scale event services. In Proc. of WETICE, 1999. Google ScholarDigital Library
Recommendations
On-demand dynamic summary-based points-to analysis
CGO '12: Proceedings of the Tenth International Symposium on Code Generation and OptimizationStatic analyses can be typically accelerated by reducing redundancies. Modern demand-driven points-to or alias analysis techniques rest on the foundation of Context-Free Language (CFL) reachability. These techniques achieve high precision efficiently ...
Rethinking Soot for summary-based whole-program analysis
SOAP '12: Proceedings of the ACM SIGPLAN International Workshop on State of the Art in Java Program analysisWhole-program static analysis has been extensively studied and widely used in the past few decades. For modern object-oriented programs, scalability has become an important issue for using whole-program analysis in real-world tools. In addition, the ...
Comments