Exploiting epidemic data dissemination for consistent lookup operations in mobile applications

ABSTRACT

This paper presents a general-purpose distributed lookup service, denoted Passive Distributed Indexing (PDI). PDI stores entries in form of (key, value) pairs in index caches located at mobile devices. Index caches are filled by epidemic dissemination of popular index entries. By exploiting node mobility, PDI can resolve most queries locally without sending messages outside the radio coverage of the inquiring node. For keeping index caches coherent, configurable value timeouts implementing implicit invalidation and lazy invalidation caches implementing explicit invalidation are introduced. Inconsistency in index caches due to weak connectivity or node failure is handled by value timeouts. Lazy invalidation caches reduce the fraction of stale index entries due to modified data at the origin node. Similar to index caches, invalidation caches are filled by epidemic distributions of invalidation messages. We evaluate the performance of PDI for a mobile P2P file sharing a mobile instant messaging application. Simulation results show that with the suitable integration of both invalidation mechanisms, up to 80% of the lookup operations return correct results and more than 90% of results delivered by PDI index caches are up-to-date.

REFERENCES

• 1: Josh Broch , David A. Maltz , David B. Johnson , Yih-Chun Hu , Jorjeta Jetcheva, A performance comparison of multi-hop wireless ad hoc network routing protocols, Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking, p.85-97, October 25-30, 1998, Dallas, Texas, United States [doi>10.1145/288235.288256]
• 2: Alan Demers , Dan Greene , Carl Hauser , Wes Irish , John Larson , Scott Shenker , Howard Sturgis , Dan Swinehart , Doug Terry, Epidemic algorithms for replicated database maintenance, Proceedings of the sixth annual ACM Symposium on Principles of distributed computing, p.1-12, August 10-12, 1987, Vancouver, British Columbia, Canada [doi>10.1145/41840.41841]
• 3: K. Fall and K. Varadhan (editors), The ns-2 manual, Technical Report, "The VINT Project", UC Berkeley, LBL, and Xerox PARC, 2003.
• 4: S. Goel, M. Singh, D. Xu, and B. Li, "Efficient Peer-to-Peer Data Dissemination in Mobile Ad-Hoc Networks", Proc. Int. Workshop on Ad Hoc Networking (IWAHN 2002), Vancouver, BC, 2002.
• 5: Wendi Rabiner Heinzelman , Joanna Kulik , Hari Balakrishnan, Adaptive protocols for information dissemination in wireless sensor networks, Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking, p.174-185, August 15-19, 1999, Seattle, Washington, United States [doi>10.1145/313451.313529]
• 6: Katrina M. Hanna , Brian Neil Levine , R. Manmatha, Mobile Distributed Information Retrieval for Highly-Partitioned Networks, Proceedings of the 11th IEEE International Conference on Network Protocols, p.38, November 04-07, 2003
• 7: IEEE Computer Society LAN MAN Standards Committee, "Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications", IEEE Standard 802.11--1997, New York, NY, 1997.
• 8: Abdelmajid Khelil , Christian Becker , Jing Tian , Kurt Rothermel, An epidemic model for information diffusion in MANETs, Proceedings of the 5th ACM international workshop on Modeling analysis and simulation of wireless and mobile systems, September 28-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570758.570768]
• 9: Christoph Lindemann , Oliver P. Waldhorst, A Distributed Search Service for Peer-to-Peer File Sharing in Mobile Applications, Proceedings of the Second International Conference on Peer-to-Peer Computing, p.73, September 05-07, 2002
• 10: Internet Engeneering Task Force Working Group Mobile Ad hoc Networks (MANET). http://www.ietf.org/html.charters/ manetcharter.html.
• 11: P. Mockapetris, "Domain Names - Concepts and Facilities", IETF Request for Comments 1034, 1987.
• 12: Maria Papadopouli , Henning Schulzrinne, Effects of power conservation, wireless coverage and cooperation on data dissemination among mobile devices, Proceedings of the 2nd ACM international symposium on Mobile ad hoc networking & computing, October 04-05, 2001, Long Beach, CA, USA [doi>10.1145/501431.501433]
• 13: M. Papadopouli and H. Schulzrinne, "Performance of Data Dissemination and Message Relaying in Mobile Ad Hoc Networks", Technical Report CUCS-004-02, Columbia University, 2003. Under submission.
• 14: Sylvia Ratnasamy , Paul Francis , Mark Handley , Richard Karp , Scott Schenker, A scalable content-addressable network, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.161-172, August 2001, San Diego, California, United States
• 15: Ion Stoica , Robert Morris , David Karger , M. Frans Kaashoek , Hari Balakrishnan, Chord: A scalable peer-to-peer lookup service for internet applications, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.149-160, August 2001, San Diego, California, United States
• 16: K. Sripanidkulchai, "The Popularity of Gnutella Queries and its Implications on Scalability", Proc. O'Reilly Peer-to-Peer and Web Services Conf., 2001
• 17: Beverly Yang , Hector Garcia-Molina, Comparing Hybrid Peer-to-Peer Systems, Proceedings of the 27th International Conference on Very Large Data Bases, p.561-570, September 11-14, 2001
• 18: Y. Xie and D. O'Hallaron, "Locality in Search Engine Queries and Its Implications for Caching", Proc. IEEE INFOCOM 2002, New York, NJ, 2002.