Modeling epidemic information dissemination on mobile devices with finite buffers

ABSTRACT

Epidemic algorithms have recently been proposed as an effective solution for disseminating information in large-scale peer-to-peer (P2P) systems and in mobile ad hoc networks (MANET). In this paper, we present a modeling approach for steady-state analysis of epidemic dissemination of information in MANET. As major contribution, the introduced approach explicitly represents the spread of multiple data items, finite buffer capacity at mobile devices and a least recently used buffer replacement scheme. Using the introduced modeling approach, we analyze seven degrees of separation (7DS) as one well-known approach for implementing P2P data sharing in a MANET using epidemic dissemination of information. A validation of results derived from the analytical model against simulation shows excellent agreement. Quantitative performance curves derived from the analytical model yield several insights for optimizing the system design of 7DS.

REFERENCES

• 1: N.T. Bailey, The Mathematical Theory of Infectious Diseases and its Applications, 2nd Edition, Hafner 1975.
• 2: Christian Bettstetter, On the minimum node degree and connectivity of a wireless multihop network, Proceedings of the 3rd ACM international symposium on Mobile ad hoc networking & computing, June 09-11, 2002, Lausanne, Switzerland [doi>10.1145/513800.513811]
• 3: F. Chinchilla, M. Lindsey, and M. Papadopouli, Analysis of Wireless Information Locality and Association Patterns in a Campus, Proc. IEEE INFOCOM 2004, Hong Kong, 2004.
• 4: Asit Dan , Daniel M. Dias , Philip S. Yu, The Effect of Skewed Data Access on Buffer Hits and Data Contention an a Data Sharing Environment, Proceedings of the 16th International Conference on Very Large Data Bases, p.419-431, August 13-16, 1990
• 5: Asit Dan , Don Towsley, An approximate analysis of the LRU and FIFO buffer replacement schemes, Proceedings of the 1990 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.143-152, April 1990, Univ. of Colorado, Boulder, Colorado, United States
• 6: P. Eugster, R. Guerraoui, A-M. Kermarrec, and L. Massoulie, Epidemic Information Dissemination in Distributed Systems, IEEE Computer, 37, 60--67, 2004.
• 7: D.J. Goodman, J. Borras, N.B. Mandayam, and R.D. Yates, Infostations: A New system for Data and Messaging Services, Proc. IEEE Vehicular Technology Conference (VTC Fall), 969--973, 1997.
• 8: Matthias Grossglauser , David N. C. Tse, Mobility increases the capacity of ad hoc wireless networks, IEEE/ACM Transactions on Networking (TON), v.10 n.4, p.477-486, August 2002 [doi>10.1109/TNET.2002.801403]
• 9: M. Grossglauser and M. Vetterli, Locating Nodes with EASE: Mobility Diffusion of Last Encounters in Ad Hoc Networks. Proc. IEEE INFOCOM 2003, San Francisco, 2003.
• 10: Xiaoyan Hong , Mario Gerla , Guangyu Pei , Ching-Chuan Chiang, A group mobility model for ad hoc wireless networks, Proceedings of the 2nd ACM international workshop on Modeling, analysis and simulation of wireless and mobile systems, p.53-60, August 20-20, 1999, Seattle, Washington, United States [doi>10.1145/313237.313248]
• 11: J.-Y. Le Boudec, Understanding the Simulation of Mobility Models with Palm Calculus, Technical Report IC/2004/53, EPF Lausanne, 2004.
• 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: Tara Small , Zygmunt J. Haas, The shared wireless infostation model: a new ad hoc networking paradigm (or where there is a whale, there is a way), Proceedings of the 4th ACM international symposium on Mobile ad hoc networking & computing, June 01-03, 2003, Annapolis, Maryland, USA [doi>10.1145/778415.778443]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Modeling techniques

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication; Distributed networks
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Design studies

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.5 Model Development
          Subjects: Modeling methodologies

General Terms:
Algorithms, Design, Experimentation, Performance

Keywords:
analytical performance modeling, mobile ad hoc networks, peer-to-peer data sharing, performance-oriented design and evaluation studies of distributed systems