Effects of routing computations in content-based routing networks with mobile data sources

ABSTRACT

This paper presents the first quantitative evaluation of the role of routing computations on performance when mobility is introduced to a content-based routing network. Additionally, the paper identifies the factors that affect the performance of a distributed publish/subscribe architecture supporting mobile publishers, formalizes publisher mobility protocols for distributed publish/subscribe systems, and develops and evaluates protocols that reduce the costs associated with supporting mobile publishers in publish/subscribe systems. Our results show that ignoring route computation time paints a false picture of the scalability of content-based routing networks, but that with appropriate protocols the adverse effects can be mitigated.

REFERENCES

• 1: 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]
• 2: 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
• 3: 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
• 4: Lee Breslau , Deborah Estrin , Kevin Fall , Sally Floyd , John Heidemann , Ahmed Helmy , Polly Huang , Steven McCanne , Kannan Varadhan , Ya Xu , Haobo Yu, Advances in Network Simulation, Computer, v.33 n.5, p.59-67, May 2000 [doi>10.1109/2.841785]
• 5: I. Burcea, H.-A. Jacobsen, E. de~Lara, V. Muthusamy, and M. Petrovic. Disconnected Operation in Publish/Subscribe Middleware. In International Conference on Mobile Data Management (MDM), 2004.
• 6: 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]
• 7: Antonio Carzaniga , Alexander L. Wolf, Forwarding in a content-based network, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863975]
• 8: Gianpaolo Cugola , Elisabetta Di Nitto , Alfonso Fuggetta, The JEDI Event-Based Infrastructure and Its Application to the Development of the OPSS WFMS, IEEE Transactions on Software Engineering, v.27 n.9, p.827-850, September 2001 [doi>10.1109/32.950318]
• 9: Y. Diao and M. Franklin. Query processing for high-volume xml message brokering. In International Conference on Very Large Databases (VLDB), Berlin, Germany, September 2003.
• 10: Patrick Th. Eugster , Pascal A. Felber , Rachid Guerraoui , Anne-Marie Kermarrec, The many faces of publish/subscribe, ACM Computing Surveys (CSUR), v.35 n.2, p.114-131, June 2003 [doi>10.1145/857076.857078]
• 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: Hubert Ka Yau Leung, Subject space: a state-persistent model for publish/subscribe systems, Proceedings of the 2002 conference of the Centre for Advanced Studies on Collaborative research, p.7, September 30-October 03, 2002, Toronto, Ontario, Canada
• 13: Guoli Li , Shuang Hou , Hans-Arno Jacobsen, A Unified Approach to Routing, Covering and Merging in Publish/Subscribe Systems Based on Modified Binary Decision Diagrams, Proceedings of the 25th IEEE International Conference on Distributed Computing Systems (ICDCS'05), p.447-457, June 06-10, 2005 [doi>10.1109/ICDCS.2005.8]
• 14: Haifeng Liu , Hans-Arno Jacobsen, Modeling Uncertainties in Publish/Subscribe Systems, Proceedings of the 20th International Conference on Data Engineering, p.510, March 30-April 02, 2004
• 15: G. Mühl , L. Fiege , F. C. Gärtner , A. Buchmann, Evaluating Advanced Routing Algorithms for Content-Based Publish/Subscribe Systems, Proceedings of the 10th IEEE International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunications Systems (MASCOTS'02), p.167, October 11-16, 2002
• 16: V. Muthusamy and H.-A. Jacobsen. Small-scale peer-to-peer publish/subscribe. In P2P Knowledge Management Workshop at MobiQuitous, July 2005.
• 17: Vinod Muthusamy , Milenko Petrovic , Dapeng Gao , Hans-Arno Jacobsen, Publisher Mobility in Distributed Publish/Subscribe Systems, Proceedings of the Fourth International Workshop on Distributed Event-Based Systems (DEBS) (ICDCSW'05), p.421-427, June 06-10, 2005 [doi>10.1109/ICDCSW.2005.116]
• 18: Charles E. Perkins , David B. Johnson, Mobility support in IPv6, Proceedings of the 2nd annual international conference on Mobile computing and networking, p.27-37, November 1996, Rye, New York, United States [doi>10.1145/236387.236400]
• 19: M. Petrovic, I. Burcea, and H.-A. Jacobsen. S-ToPSS -- a semantic publish/subscribe system. In International Conference on Very Large Databases (VLDB), Berlin, Germany, September 2003.
• 20: Milenko Petrovic , Haifeng Liu , Hans-Arno Jacobsen, G-ToPSS: fast filtering of graph-based metadata, Proceedings of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan [doi>10.1145/1060745.1060824]
• 21: M. Petrovic, V. Muthusam, and H.-A. Jacobsen. Content-based routing in mobile ad hoc networks. In MobiQuitous, July 2005.
• 22: Gian Pietro Picco , Gianpaolo Cugola , Amy L. Murphy, Efficient Content-Based Event Dispatching in the Presence of Topological Reconfiguration, Proceedings of the 23rd International Conference on Distributed Computing Systems, p.234, May 19-22, 2003
• 23: Peter Sutton , Rhys Arkins , Bill Segall, Supporting Disconnectedness-Transparent Information Delivery for Mobile and Invisible Computing, Proceedings of the 1st International Symposium on Cluster Computing and the Grid, p.277, May 15-18, 2001
• 24: Talarian Inc. Publish-subscribe middleware helps direct traffic of Olympic proportions. http://messageq.ebizq.net/communications_middleware/talarian_2.html.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Distributed applications

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS

General Terms:
Algorithms, Design, Experimentation, Performance

Keywords:
mobility, multicast, publish/subscribe, routing