Design and evaluation of a wide-area event notification service

Abstract

The components of a loosely coupled system are typically designed to operate by generating and responding to asynchronous events. An event notification service is an application-independent infrastructure that supports the construction of event-based systems, whereby generators of events publish event notifications to the infrastructure and consumers of events subscribe with the infrastructure to receive relevant notifications. The two primary services that should be provided to components by the infrastructure are notification selection (i. e., determining which notifications match which subscriptions) and notification delivery (i.e., routing matching notifications from publishers to subscribers). Numerous event notification services have been developed for local-area networks, generally based on a centralized server to select and deliver event notifications. Therefore, they suffer from an inherent inability to scale to wide-area networks, such as the Internet, where the number and physical distribution of the service's clients can quickly overwhelm a centralized solution. The critical challenge in the setting of a wide-area network is to maximize the expressiveness in the selection mechanism without sacrificing scalability in the delivery mechanism. This paper presents SIENA, an event notification service that we have designed and implemented to exhibit both expressiveness and scalability. We describe the service's interface to applications, the algorithms used by networks of servers to select and deliver event notifications, and the strategies used to optimize performance. We also present results of simulation studies that examine the scalability and performance of the service.

References

1. AGUILERA, M. K., STROM, R. E., STURMAN,D.C.,ASTLEY, M., AND CHANDRA, T. D. 1999. Matching events in a content-based subscription system. In Eighteenth ACM Symposium on Principles of Distributed Computing (PODC '99) (Atlanta, GA, May 4-6 1999), pp. 53-61.]]
2. BANAVAR, G., CHANDRA,T.D.,MUKHERJEE, B., NAGARAJARAO, J., STROM,R.E.,AND STURMAN, D. C. 1999. An efficient multicast protocol for content-based publish-subscribe systems. In The 19th IEEE International Conference on Distributed Computing Systems (ICDCS '99) (Austin, TX, May 1999), pp. 262-272.]]
3. BIRMAN, K. P. 1993. The process group approach to reliable distributed computing. Communications of the ACM 36, 12 (Dec.), 36-53.]]
4. CAGAN, M. R. 1990. The HP SoftBench environment: An architecture for a new generation of software tools. Hewlett-Packard Journal: technical information from the laboratories of Hewlett- Packard Company 41, 3 (June), 36-47.]]
5. CARZANIGA, A. 1998. Architectures for an Event Notification Service Scalable to Wide-area Networks, Ph. D. thesis, Politecnico di Milano, Milano, Italy.]]
6. CARZANIGA, A., ROSENBLUM,D.S.,AND WOLF, A. L. 1999. Interfaces and algorithms for a widearea event notification service. Technical Report CU-CS-888-99 (Oct.), Department of Computer Science, University of Colorado, Revised May 2000.]]
7. CARZANIGA, A., ROSENBLUM,D.S.,AND WOLF, A. L. 2000a. Achieving scalability and expressiveness in an internet-scale event notification service. In Proceedings of the Nineteenth ACMSymposium on Principles of Distributed Computing (PODC 2000) (Portland, OR, July 2000), pp. 219-227.]]
8. CARZANIGA, A., ROSENBLUM,D.S.,AND WOLF, A. L. 2000b. Content-based addressing and routing: A general model and its application. Technical Report CU-CS-902-00 (Jan.), Department of Computer Science, University of Colorado.]]
9. CERI,S.AND WIDOM, J. 1996. Active Database Systems: Triggers and Rules for Advanced Database Processing. Morgan Kaufman, San Mateo.]]
10. CLARK, D. 1989. Policy routing in internet protocols. Internet Requests For Comments (RFC) 1102.]]
11. CUGOLA, G., DI NITTO, E., AND FUGGETTA, A. 1998. Exploiting an event-based infrastructure to develop complex distributed systems. In Proceedings of the 20th International Conference on Software Engineering (ICSE '98) (Kyoto, Japan, April 1998), pp. 261-270.]]
12. CUGOLA, G., DI NITTO, E., AND FUGGETTA, A. 2001. The JEDI event-based infrastructure and its application to the development of the OPSS WFMS. IEEE Transactions on Software Engineering.]]
13. DALAL,Y.K.AND METCALFE, R. M. 1978. Reverse path forwarding of broadcast packets. Communications of the ACM 21, 12 (Dec.), 1040-1048.]]
14. DEERING, S. E. 1991. Multicast Routing in a Datagram Internetwork. Ph. D. thesis, Stanford University.]]
15. DEERING,S.E.AND CHERITON, D. R. 1990. Multicast routing in datagram networks and extended LANs. ACM Transactions on Computer Systems 8, 2 (May), 85-111.]]
16. FENNER, W. 1997. Internet group management protocol, version 2. Internet Requests For Comments (RFC) 2236.]]
17. GOUGH,J.AND SMITH, G. 1995. Efficient recognition of events in a distributed system. In Proceedings of the 18th Australasian Computer Science Conference (Adelaide, Australia, Feb. 1995).]]
18. HART,R.O.AND LUPTON, G. 1995. DEC FUSE: Building a graphical software development environment from UNIX tools. Digital Technical Journal of Digital Equipment Corporation 7,2 (Spring), 5-19.]]
19. JULIENNE,A.M.AND HOLTZ, B. 1994. ToolTalk and open protocols, inter-application communication. Prentice-Hall, Englewood Cliffs, New Jersey.]]
20. KANTOR,B.AND LAPSLEY, P. 1986. Network news transfer protocol a proposed standard for the stream-based transmission of news. Internet Request For Comments (RFC) 977.]]
21. KRISHNAMURTHY,B.AND ROSENBLUM, D. S. 1995. Yeast: A general purpose event-action system. IEEE Transactions on Software Engineering 21, 10 (Oct.), 845-857.]]
22. MANSOURI-SAMANI,M.AND SLOMAN, M. 1997. GEM: A generalized event monitoring language for distributed systems. IEE/IOP/BCS Distributed Systems Engineering Journal 4, 2 (June), 96- 108.]]
23. OBJECT MANAGEMENT GROUP 1998a. CORBAservices: Common object service specification. Technical report (July), Object Management Group.]]
24. OBJECT MANAGEMENT GROUP 1998b. Notification service. Technical report (Nov.), Object Management Group.]]
25. OBJECT MANAGEMENT GROUP 1999. Notification Service. Technical report (Aug.), Object Management Group.]]
26. REISS, S. P. 1990. Connecting tools using message passing in the Field environment. IEEE- Software 7, 4 (July), 57-66.]]
27. ROSENBLUM,D.S.AND WOLF, A. L. 1997. A design framework for Internet-scale event observation and notification. In Proceedings of the Sixth European Software Engineering Conference, Number 1301 in Lecture Notes in Computer Science (1997), pp. 344-360, Springer-Verlag.]]
28. SEGALL,B.AND ARNOLD, D. 1997. Elvin has left the building: A publish/subscribe notification service with quenching. In Proceedings of AUUG97 (Brisbane, Australia), Sept. 3-5 1997), pp. 243- 255.]]
29. Sun Microsystems 1998. Java Distributed Event Specification, Mountain View, CA: Sun Microsystems, Inc.]]
30. Sun Microsystems 1999. Java Message Service. Mountain View, CA: Sun Microsystems, Inc.]]
31. TENNENHOUSE, D. L., SMITH, J. M., SINCOSKIE,W.D.,WETHERALL,D.J.,AND MINDEN, G. J. 1997. A survey of active network research. IEEE Communications Magazine 35, 1 (Jan.), 80-86.]]
32. WRAY,M.AND HAWKES, R. 1998. Distributed virtual environments and VRML: an event-based architecture. Computer Networks and ISDN Systems 1-7, 30 (April), 43-51.]]
33. YU, H., ESTRIN,D.,AND GOVINDAN, R. 1999. A hierarchical proxy architecture for Internet-scale event services. In Proceedings of WETICE '99, (Stanford, CA, June 1999).]]
34. ZEGURA,E.W.,CALVERT, K., AND DONAHOO, M. J. 1997. A quantitative comparison of graph-based models for internet topology. IEEE/ACM Transactions on Networking 5, 6 (Dec.), 770-783.]]
35. ZEGURA,E.W.,CALVERT,K.L.,AND BHATTACHARJEE, S. 1996. How to model an internetwork. In Proceedings of IEEE INFOCOM '96 (San Francisco, CA, April 1996), pp. 594-602.]]

Index Terms

• Computing methodologies

  • Modeling and simulation

    • Model development and analysis

      • Model verification and validation

      • Modeling methodologies

• Information systems

  • World Wide Web

    • Web applications

      • Internet communications tools

• Networks

  • Network components

    • Intermediate nodes

      • Routers

  • Network protocols

    • Network layer protocols

      • Routing protocols

    • Transport protocols

  • Network types

    • Public Internet

• Software and its engineering

  • Software organization and properties

    • Software system structures

      • Distributed systems organizing principles

        • Organizing principles for web applications