Fast and flexible forwarding for Internet subscription systems

ABSTRACT

This paper analyzes mechanisms for addressing and forwarding notifications in Internet subscription systems. The first section of the paper focuses on existing subscription systems, including single-identifier and content-based multicast approaches. It evaluates these systems on issues of subscription complexity, application-level flexibility, and efficiency and finds that both systems run into problems in these areas. The second section of the paper introduces an alternative to current approaches, called match-structure forwarding. In this approach, routers forward each message via a structure contained in the header of each message. These structures are specifically to reflect a variety of complex applications as well as for efficient forwarding by network routers. This paper proposes two alternative header formats for match-structure forwarding, called content lists and content graphs. The third section of the paper presents results from experiments that compared the performance of content lists and content graphs with other subscription systems. Results show that the match-structure forwarding approaches outperform other approaches in applications with large numbers of subscribers and overlapping subscription categories. Overall, these results suggest that match-structure forwarding systems are a promising development in the area of Internet Subscription Systems.

REFERENCES

• 1: Channelization Problem in Large Scale Data Dissemination, Proceedings of the Ninth International Conference on Network Protocols, p.100, November 11-14, 2001
• 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: Mehmet Altinel , Michael J. Franklin, Efficient Filtering of XML Documents for Selective Dissemination of Information, Proceedings of the 26th International Conference on Very Large Data Bases, p.53-64, September 10-14, 2000
• 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: Luis Felipe Cabrera , Michael B. Jones , Marvin Theimer, Herald: Achieving a Global Event Notification Service, Proceedings of the Eighth Workshop on Hot Topics in Operating Systems, p.87, May 20-22, 2001
• 6: A. Carzaniga, D. Rosenblum, and A. Wolf. Content-based addressing and routing: A general model and its application. Technical Report CU-CS-902-00, Department of Computer Science, University of Colorado, January 2000.
• 7: Antonio Carzaniga , David S. Rosenblum , Alexander L. Wolf, Achieving scalability and expressiveness in an Internet-scale event notification service, Proceedings of the nineteenth annual ACM symposium on Principles of distributed computing, p.219-227, July 16-19, 2000, Portland, Oregon, United States [doi>10.1145/343477.343622]
• 8: I. T. W. R. Center. Gryphon: publish/subscribe over public networks. Technical Report.
• 9: João Pereira , Françoise Fabret , François Llirbat , Dennis Shasha, Efficient Matching for Web-Based Publish/Subscribe Systems, Proceedings of the 7th International Conference on Cooperative Information Systems, p.162-173, September 06-08, 2000
• 10: Peter R. Pietzuch , Jean Bacon, Hermes: A Distributed Event-Based Middleware Architecture, Proceedings of the 22nd International Conference on Distributed Computing Systems, p.611-618, July 02-05, 2002
• 11: R. Preotiuc-Pietro, J. Pereira, F. Llirbat, F. Fabret, K. Ross, and D. Shasha. Publish/subscribe on the web at extreme speed. In Proc. of ACM SIGMOD Conf. on Management of Data, Cairo, Egypt, 2000.
• 12: 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
• 13: 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