Subject: Manet Flooding

From: Scott Corson <[email-masked]>
Date: Mon, 7 Jan 2002 17:38:31 -0500

Folks,

Another topic broached at the last meeting was the sometimes confusing topic
of Manet Flooding.

Nearly every manet protocol uses some form of flooding to disseminate
control information.  That is NOT what I am talking about.

A "Manet Flooding" protocol is a protocol that can be used to disseminate
*data* traffic throughout a manet domain.  It may subsequently be used by
other protocols for their own internal purposes, but that is a separate
matter.

We (the chairs) are suggesting that this is a fundamental protocol
capability useful for the operation of manets, and are looking for WG
feedback.  We feel such a capability can be used by applications as well as
other protocols.

So I would like to begin discussion of what exactly it means (technically)
to flood information throughout a manet domain.  We have had some discussion
on this subject already on the list.  This discussion could hopefully lead
to the publishing of a manet flooding requirements document that specifies
this capability, co-authored by a small team of interested folks.
Subsequently this flooding capability could be supported by/incorporated
into existing protocols, or specific flooding protocol proposals could be
considered.

Thoughts?

-Scott

---

From: Fred Baker <[email-masked]>
Date: Mon, 07 Jan 2002 16:18:08 -0800

>other protocols for their own internal purposes, but that is a separate

dumb question: is this significantly different from some form of IP 
Multicast, either reliable or unreliable?

---

From: Brad Williams <[email-masked]>
Date: Tue, 08 Jan 2002 12:57:29 -0700

Scott,

You can count me as being a little confused as well.  By MANET Flooding are you
referring to the generic process of a node sending a packet to all other nodes
in the network?  Some recent publications have referred to this as network wide
broadcasting.  In my opinion, the term Flooding indicates the specific protocol

in which each node rebroadcasts each originated flooded packet exactly one
time  (Internet Draft - A Simple Protocol for Multicast and Broadcast in Mobile
Ad Hoc Networks, 2001 -  provides the details).

My recent research is in the area of efficient network
wide broadcasting schemes (like Multipoint Relaying used in OLSR).  Generally
speaking, Flooding is overly congestive and wastes node resources.  Recently
proposed efficient network wide broadcast schemes reduce redundant
retransmissions.   It is my opinion that the community should try to
standardize an efficient network wide broadcasting scheme.  To this end, I have
a submission pending regarding a simulation based comparitive analysis of a
number of different network wide broadcasting protocols.   Obviously, our paper
doesn't bear the benefit of the requirements you describe below; we were forced
to make assumptions regarding applicability in order to choose simulation
parameters.  However, you may find those assumptions useful.

I've included the abstract below.  If you or anyone else is interested, I'd be
happy to email a full copy of the paper.

Regards,
Brad Williams
[email-masked]

submission abstract -

Network wide broadcasting in Mobile Ad Hoc Networks
(MANETs) provides important control and route
establishment functionality for a number of unicast
and multicast protocols.  Considering its wide use
as a building block for other network layer protocols,
the MANET community needs to standardize a single
methodology that efficiently delivers a packet from
one node to all other network nodes. Despite a
considerable number of proposed broadcasting schemes,
no comprehensive comparative analysis has been
previously done.  This paper provides such analysis by
classifying existing broadcasting schemes into
categories and simulating a subset of each category,
thus supplying a condensed but comprehensive side by
side comparison.  The simulations are designed to
pinpoint, in each category, specific failures to
network conditions that are relevant to MANETs, e.g.,
bandwidth congestion and dynamic topologies.  Protocol
extensions using adaptive responses to network
conditions are proposed, implemented and analyzed for
one broadcasting scheme that performs well in the
comparative study.  Two protocols utilizing neighbor
knowledge are shown to be most applicable for a wide
range of network conditions.  Areas of future research
are defined to perfect these two protocols, in the
hopes that one will be chosen as a standard
broadcasting scheme by the MANET community.

---

From: Brad Williams <[email-masked]>
Date: Fri, 11 Jan 2002 18:24:27 -0700

From <draft-manner-seamoby-terms-03.txt>  as proposed by Charlie Perkins:

Flooding:

       The process of delivering data or control messages to every node
       within the network under consideration.

I'm happy to use this definition (and I will in this email).

Back to Scott Corson's original request:

> to flood information throughout a manet domain.  ..... This discussion could
> hopefully lead to the publishing of a manet flooding requirements document
> that specifies
> this capability .....  Thoughts?

These are the requirements I would choose for a MANET Flooding protocol.
Hopefully, this isn't too basic for the group.  Also, some might be a little
optimistic:

1. Layer 3 protocol, I guess this is obvious.
2. Best Effort only.
3. Distributed in nature.
4. Highest priority should be to maximize delivery ratio (percent of network
nodes that receive a given flooded packet).
5. Protocol should attempt to minimize end-end delay (time for all nodes to
receive the packet), but should not sacrifice delivery ratio.  This means that
the Flooding protocol would not be recommended for time sensitive routing.
6. Protocol should attempt to minimize redundant retransmissions (ie leaf nodes
don't retransmit).
7. Protocol should be robust given common MANET conditions (ie high channel
congestion,  frequently changing topologies).
8.  Protocol should be easily interfaced by other network layer routing
protocols.
9.  If the Protocol uses "Hello" packets, allow other routing protocols access
to neighbor topology information and also allow the other protocols to put
payload in the "Hello" packets.
10. "Hello" packets require node resources, so a Flooding protocol should
attempt to maximize the beaconing period given both utilization and topology
change rate constraints.
11. Allow payloads of various sizes.
12. Must have the means to prevent loops/replication.
13. Should attempt to minimize node resource by having low order algorithms and
low state requirements.
14. Should allow aggregation of payloads at the source node.

I'm interested in what others think.

Thanks,
Brad