Subject: flooding (Epidemic Routing)

From: Amin Vahdat <[email-masked]>
Date: Mon, 05 Jun 2000 12:07:21 -0400

In the context of flooding protocols in ad hoc networks, we recently
conducted a study on the effectiveness of "controlled" flooding for
partially connected ad hoc networks.  In the paper, we outline a number
of scenarios where a connected path from source to destination is
potentially never available, making traditional ad hoc routing protocols

inappropriate.  The idea is to use epidemic algorithms and logical time
vectors to exchange unseen messages among connected neighbors, and using

eventual connectivity among "connected" islands to deliver messages to
their
destination.  For the set of experiments we conducted, our algorithms
show
excellent delivery rates, average delivery times that scale with how
"unconnected" the network is, and moderate per-node resource
consumption.

One direction we are pursuing is the applicability of the algorithms to
multicast
in ad hoc networks.

The paper is available at:

     http://www.cs.duke.edu/~vahdat/ps/epidemic.pdf

The title and abstract are included below.  I would appreciate any
comments on the paper.

--
Amin Vahdat
Assistant Professor
Duke University
http://www.cs.duke.edu/~vahdat

Title: Epidemic Routing for Partially-Connected Ad Hoc Networks

Abstract:

Mobile ad hoc routing protocols allow nodes with wireless adaptors to
communicate with one another without any pre-existing network
infrastructure.  Existing ad hoc routing protocols, while robust to
rapidly changing network topology, assume the presence of a connected
path from source to destination.  Given power limitations, the advent
of short-range wireless networks, and the wide physical conditions
over which ad hoc networks must be deployed, in some scenarios it is
likely that this assumption is invalid.  In this work, we develop
techniques to deliver messages in the case where there is never
a connected path from source to destination or when a network
partition exists at the time a message is originated.  To this end, we
introduce Epidemic Routing, where random pair-wise exchanges of
messages among mobile hosts ensure eventual message delivery.  The
goals of Epidemic Routing are to: i) maximize message delivery rate,
ii) minimize message latency, and iii) minimize the total resources
consumed in message delivery.  Through an implementation in the
Monarch simulator, we show that Epidemic Routing achieves eventual
delivery of 100% of messages with reasonable aggregate resource
consumption in a number of interesting scenarios.

---

From: "A. Bruce McDonald" <[email-masked]>
Date: Mon, 5 Jun 2000 15:03:30 -0400 (EDT)

I think that most people would agree that even the *best* routing algorithm 
will eventually break if the topology changes rapidly enough (it would be 
interesting to learn what the *fundamental* limitations are---if we could 
characterize such a thing).  I would hasten to add that even the simplest 
of all routing algorithms, flooding, will itself break down without
considerable control. This seems to be an often overlooked reality of 
routing under extreme conditions. Flooding reliably in the best of 
circumstances can be difficult. Hence, even flooding may not be as simple 
as we'd like it to be under these circumstances. 

--Bruce McDonald
University of Pittsburgh