Design and quantitative analysis of protocols for epidemic information dissemination in mobile ad hoc networks
Loading...
Files
Date
2005-11-29T12:47:35Z
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
This thesis explores the field of protocols for epidemic information dissemination (EID) that constitute a novel way to implement peer-to-peer communication in Mobile Ad Hoc Networks (MANET). Such protocols exploit device mobility and transmit information when mobile devices encounter, similar to the spread of an infectious disease among individuals. The contribution of this thesis is three-fold. As first contribution, a general-purpose distributed lookup service for MANET is presented. The lookup service, denoted as Passive Distributed Indexing (PDI), builds upon epidemic dissemination of index information. It differs from previously proposed EID systems in three major aspects: (1) PDI can be employed for key-to-value lookups in arbitrary mobile applications. (2) PDI explicitly considers the limited availability of memory resources on mobile devices by using buffers of finite capacity and employing Least Recently Used (LRU) replacement when the buffer capacity is exceeded. (3) PDI provides consistency mechanisms for ensuring coherence of disseminated information. A comprehensive simulation study illustrates that PDI is well-suited to implement consistent lookup operations in various mobile applications.
As second contribution, this thesis presents a design study of mechanisms for disseminating frequently changing presence information in a mobile instant messaging system. The study extends previous work in three major aspects: (1) It introduces sustained consistency as a novel measure for the coherence of the disseminated presence information. (2) It evaluates different alternative approaches for disseminating presence information with respect to sustained consistency and control traffic and identifies an epidemic approach as the method of choice. (3) It proposes the System for Presence information Exchange by Epidemic Dissemination (SPEED). As illustrated in a comprehensive performance study, SPEED outperforms an approach based on optimized flooding of presence information with respect to sustained consistency and control traffic.
As third contribution, this thesis presents a novel stochastic modeling approach for EID systems in MANET that differs from previous approaches in three major aspects: (1) It explicitly considers the spread of multiple data items as well as buffers with finite capacity and LRU replacement. (2) The approach conducts steady-state analysis rather than transient analysis. (3) The approach does not require offline simulations to determine model parameters. It is shown that an EID system with finite buffer can be modeled by discrete-time Markov chains with a state space that grows exponentially with the number of nodes and data items in the EID system. Since a numerical steady-state solution with state-of-the-art methods is computationally infeasible, an approximate solution approach is presented and applied for modeling the Seven Degrees of Separation (7DS) EID system. A comparison of the approximate results to the results of a detailed simulation study shows an excellent agreement. Furthermore, a comprehensive performance study provides key insight into the steady-state behavior of 7DS.
Description
Table of contents
Keywords
Peer-to-Peer (P2P), Mobile Ad Hoc Networks (MANET), Protocols, Epidemic Algorithms, Mobile Applications, Consistency, Instant Messaging, Presence State Maintenance, Least Recently Used (LRU), Analytical Performance Modeling, Stochastic Models, Discrete Time Markov Chains (DTMC), Simulation