Subject: flooding

From: Dmitri Deshun Perkins <[email-masked]>
Date: Thu, 1 Jun 2000 18:19:00 -0400 (EDT)

Can anyone comment on the relative performance of "flooding" 
as a routing algorithm in ad hoc networks? Have any studies
been done that discuss when(under what conditions) it might 
be advantageous to simply use flooding(at least for control
pkts)?

Please point me to any papers that discuss this topic.
I briefly searched the archives and did not locate a discussion
directly related to the above questions. Please excuse me if 
this topic has already been discussed. Feel free to point me
to the correct archives.

Thanks for your time,
DDP

---

From: Anis LAOUITI <[email-masked]>
Date: Fri, 02 Jun 2000 12:05:00 +0200

> this topic has already been discussed. Feel free to point me

Hi
You can take a look to this Research Report
"Multipoint relaying : An efficient technique  for flooding in mobile
wireless networks"
ftp://ftp.inria.fr/INRIA/publication/publi-ps-gz/RR/RR-3898.ps.gz

This technique is used in OLSR protocol (Optimzed Link State Routing) to
flood control information
in the network by reducing the number of retransmissions while
forwarding a broadcast packet.

http://www.ietf.org/internet-drafts/draft-ietf-manet-olsr-01.txt

Anis LAOUITI

---

From: Richard <[email-masked]>
Date: Sun, 04 Jun 2000 17:30:25 -0700

> Please point me to any papers that discuss this topic.

A simulation study comparing flooding (for disseminating link-state
updates) to TBRPF (Topology Broadcast based on Reverse Path Forwarding)
and to some other routing protocols was presented in the following paper:

R.G. Ogier, ``Efficient Routing Protocols for Packet-Radio
Networks Based on Tree Sharing,''  Proc. Sixth IEEE Intl. Workshop
on Mobile Multimedia Communications (MOMUC'99), November 1999.

TBRPF was originally presented in the following paper, but the
above paper used more accurate simulation models.

B. Bellur and R. G. Ogier, ``A Reliable, Efficient Topology
Broadcast Protocol for Dynamic Networks,'' Proc. IEEE INFOCOM '99, 
New York, March 1 999.

These papers can be found at http://www.erg.sri.com/publications.html

TBRPF and flooding both provide each node with the state of
every link in the network (or within a cluster if hierarchical
routing is used), but TBRPF does it more efficiently by sending
each update along a min-hop tree rooted at the source of the update.
(Thus, for example, leaves of the tree need not forward updates.)
TBRPF dynamically updates these broadcast trees using the link-state 
information that is received along the trees.

The simulation results in the MOMUC'99 paper show that TBRPF
generates between 36% and 85% less update/control traffic 
than flooding, depending on the density of the network topology and 
on whether unicast or broadcast link-level transmissions are used.

The MOMUC paper also presents a protocol called FTSP (Full Tree-Sharing
Protocol), which is very similar to the ORA (optimal routing) version
of STAR.  The simulation results also show that TBRPF generates
between 14% and 58% less update/control traffic than FTSP,
despite the fact that FTSP provides each node with only partial 
topology information.  (TBRPF has not yet been compared to other 
MANET protocols such as TORA, DSR, and AODV.)  

Richard Ogier