Peer-to-Peer Epidemic Algorithms for Reliable Multicasting in Ad Hoc Networks

Authors: Zülküf Genç, Öznur Özkasap

Abstract:

Characteristics of ad hoc networks and even their existence depend on the nodes forming them. Thus, services and applications designed for ad hoc networks should adapt to this dynamic and distributed environment. In particular, multicast algorithms having reliability and scalability requirements should abstain from centralized approaches. We aspire to define a reliable and scalable multicast protocol for ad hoc networks. Our target is to utilize epidemic techniques for this purpose. In this paper, we present a brief survey of epidemic algorithms for reliable multicasting in ad hoc networks, and describe formulations and analytical results for simple epidemics. Then, P2P anti-entropy algorithm for content distribution and our prototype simulation model are described together with our initial results demonstrating the behavior of the algorithm.

Keywords: Ad hoc networks, epidemic, peer-to-peer, reliablemulticast.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1069985

References:

[1] M. Frodigh, et al, "Wireless Ad Hoc Networking: The Art of Networking without a Network," Ericsson Review, No. 4, 2000.
[2] E. Pagani and G. P. Rossi, "Providing reliable and fault tolerant broadcast delivery in mobile ad-hoc networks,"Mobile Networks and Applications, vol. 5, no. 4, pp. 175- 192, 1999.
[3] S.K.S. Gupta and P.K. Srimani, "An adaptive protocol for reliable multicast in mobile multi-hop radio networks," in IEEE Workshop on Mobile Computing Systems and Applications, 1999, pp. 111-122.
[4] J. Luo, P.Th Eugster, and J.-P. Hubaux, "Route Driven Gossip: Probabilistic Reliable Multicast in Ad Hoc Networks," Proc. INFOCOM, pp. 2229-2239, 2003.
[5] R. Chandra, V. Ramasubramanian, and K. Birman, "Anonymous gossip: Improving multicast reliability in mobile ad-hoc networks". In Proc. 21st International Conference on Distributed Computing Systems (ICDCS), pages 275-283, 2001.
[6] VINT Project. The UCB/LBNL/VINT network simulator-ns (Version 2).http://www.isi.edu/nsnam/ns.
[7] J. Luo, P.Th Eugster, and J.-P. Hubaux, "Pilot: Probabilistic Lightweight Group Communication System for Ad Hoc Networks," IEEE Transactions on Mobile Computing, Vol. 3, No.2, April-June 2004.
[8] Haas, J. Halpern, and L. Li, "Gossip-based Ad Hoc Routing,"Proc. of IEEE INFOCOM 2002.
[9] A. Vahdat and D. Becker. "Epidemic routing for partiallyconnected ad hoc networks". Duke Technical Report CS- 2000-06, July 2000.
[10] Demers, A., Greene, D., Hauser, C., Irish, W., Larson, J., Shenker, S., Sturgis, H., Swinehart, D. and Terry, D., "Epidemic Algorithms for Replicated Database Maintenance", Proc. of the Sixth ACM Symp. on Principles of Distributed Computing, 1-12p, 1987.
[11] Birrell, A.D., Levin, R., Needham, R.M. and Schroeder, M.D., "Grapevine, An Exercise in Distributed Computing", Communications of the ACM, 25(4), 260-274p, 1982.
[12] Golding, R.A. and Taylor K., "Group Membership in the Epidemic Style", Technical Report, UCSC-CRL-92-13, University of California at Santa Cruz, 1992.
[13] Ladin, R., Lishov, B., Shrira, L. and Ghemawat, S., "Providing Availability using Lazy Replication", ACM Transactions on Computer Systems, 10(4), 360-391p, 1992.
[14] Guo, K., "Scalable Message Stability Detection Protocols", Ph.D. dissertation, Cornell University Dept. of Computer Science, 1998.
[15] van Renesse, R., Minsky, Y. and Hayden, M., "A Gossip-style Failure Detection Service", Proceedings of Middleware-98, 55-70p, 1998.
[16] Xiao, Z. and Birman, KP., "A Randomized Error Recovery Algorithm for Reliable Multicast", Proceedings, IEEE Infocom 2001.
[17] van Renesse, R., Birman, K.P., Vogels, W., "Astrolabe: A Robust and Scalable Technology for Distributed System Monitoring, Management, and Data Mining", ACM Transactions on Computer Systems, Vol. 21, No. 2, pp. 164-206, May 2003.
[18] Bailey, N.T.J., "The Mathematical Theory of Infectious Diseases and its Applications", second edition, Hafner Press, 1975.