Subject: RE: Manet Flooding

From: Fred Baker <[email-masked]>
Date: Thu, 10 Jan 2002 11:43:23 -0800

At 09:32 AM 1/10/2002, Nast, Douglas P wrote:
>"Flooding is sending a packet out on every link (potentially logical) but
>the one you recieved it on".

I think you have to decide whether "flooding" is something you are trying 
to do, or an algorithm for doing it. "flooding", to me, means "getting 
something to every node in a domain." The above is an algorithm for doing 
it, and works correctly if, for every two nodes using a communication 
channel, every node that one can exchange with is one that the other can 
exchange with.

In an Ethernet network, if I send a broadcast on a LAN, every node on the 
LAN will receive it. If another resends the broadcast, the resend is 
superfluous; every node will already have received it. I am told that in 
radio domains, this is not necessarily true. the fact that you and I can 
communicate by radio does not imply that you can communicate with every 
neighbor that I can communicate with. There may be a hill or tree in your 
path that is not in mine.

Hence, your proposed algorithm will get a message distributed to every node 
in an Ethernet-based network. It may not get the information to every node 
in a radio-based network.

The problem with RPF as an algorithm here is route asymmetry in a network 
that is in the process of changing. One does not accept a packet from *any* 
interface and forward it away from the source (else you would expect to 
forward as many copies as you have interfaces to receive it on less one), 
one accepts a packet from one's routing next hop and forwards it away from 
the source. If routes are symmetrical, that plays. However, if routes are 
not symmetrical (and when routing is changing, which I understand to be 
constantly true in a mobile ad hoc network, some routers have different 
information than others and so by definition routes are not symmetrical) 
the guy I want to accept the packet from may not be someone who wants to 
forward the packet to me. While the route momentarily loops, in a short 
period of time one would expect it to get sorted out. But with respect to 
the particular bit of information that you're trying to flood throughout 
the network, *at*the*instant*its*packet*is*being*looked*at*, the 
relationships are shot, and the forward progress of information 
distribution stops. I therefore am unable to guarantee that "every node in 
the network obtains the information."

---

From: [email-masked]
Date: Thu, 10 Jan 2002 14:17:15 -0800

Fred,

Please see my comments below.

> channel, every node that one can exchange with is one that the other can 

If "flooding" is something you are trying to do, then what should we
call the above algorithm for doing it?  
I know that several papers since the 1980s have called the algorithm "flooding".
That is why I prefer to use the term "network-wide broadcast" to describe
what you are trying to do.

> the network obtains the information."

You *can* guarantee that every node in the network obtains the information
if you modify RPF to use sequence numbers.  The following references prove this:

B. Awerbuch and S. Even. "Reliable Broadcast in Unreliable Networks", Networks,
Vol. 16, 1986, p. 381-396.

B. Bellur and R.G. Ogier. "A Reliable, Efficient Topology Broadcast Protocol
for Dynamic Networks", INFOCOM '99.

Richard

P.S. for Charlie and Thomas.  I looked at draft-manner-seamoby-terms-00.txt 
and it does not contain the word "flooding".

---

From: Fred Baker <[email-masked]>
Date: Thu, 10 Jan 2002 16:53:58 -0800

At 02:17 PM 1/10/2002, [email-masked] wrote:
>If "flooding" is something you are trying to do, then what should we call 
>the above algorithm for doing it?

"RPF" and "copying to every interface but the one we received it on" 
(VTEIBTOWRIO) come quickly to mind.

Consider AODV's requirement (on which I have commented to the authors) for 
AODV that it send on every interface, not every interface except that which 
it was received on or every interface except that which I consider to be my 
next hop, and ask yourself why?

I was asking a slightly higher level question. To me, "flooding" refers to 
the result, not the algorithm for achieving it.

>if you modify RPF to use sequence numbers.

Sequence numbers refer to the subset of the information you receive. RPF 
refers to the subset of interfaces to which I send. The former will be a 
subset of the latter. Think about it. If I don't send to you, what you 
think about sequence numbers may or may not be relevant.

---

From: [email-masked]
Date: Thu, 10 Jan 2002 17:58:00 -0800

> think about sequence numbers may or may not be relevant.

I see what you are saying.  The methods below assume that each
broadcast packet is stored at each node for some time, and has a 
sequence number.  If you don't send to me (as you say) because nodes
moved around, in RPF terminology you are my new parent (i.e.,
next hop to the broadcast source), and I will send you a NEW PARENT
message with a sequence number which refers to the subset of
information that I have received.  You will then send me 
the information that I have not yet received.

> To me, "flooding" refers to the result, not the algorithm for achieving it.

That is true for many people.  But for many other people
(I know of at least 5 now), "flooding" is a mechanism for achieving 
the result, and some call the result "network-wide broadcast".
It seems to me that everyone agrees on what "network-wide broadcast"
means, whereas people are split on what "flooding" means.
Wouldn't it be best to use the term that is unambiguous?

Richard

---

From: Charlie Perkins <[email-masked]>
Date: Thu, 10 Jan 2002 19:42:25 -0800

Hello Richard,

> and it does not contain the word "flooding".

It's there.  I guess you should search for "Flooding" instead of "flooding".

Regards,
Charlie P.

---

From: Fred Baker <[email-masked]>
Date: Thu, 10 Jan 2002 19:48:16 -0800

This discussion is getting to the point of diminishing returns.

---

From: [email-masked]
Date: Thu, 10 Jan 2002 20:09:40 -0800

> This discussion is getting to the point of diminishing returns.

I agree. My main point was that RPF can be done reliably in MANETs,
and I cited two papers that prove this.  People can read those papers 
for more information.

Richard

---

From: [email-masked]
Date: Fri, 11 Jan 2002 08:49:19 -0800

Charlie,

> It's there.  I guess you should search for "Flooding" instead of "flooding".

My search was not case sensitive.  Check for yourself:

http://www.alternic.org/drafts/drafts-m-n/draft-manner-seamoby-terms-00.txt

Regards,
Richard

---

From: "Charles E. Perkins" <[email-masked]>
Date: Fri, 11 Jan 2002 11:44:37 -0800

Hello folks,

Sorry for the confusion.  I don't know what had gone wrong with
this.  It could have to do with problems with late submission on
the last day before IETF deadlines.

The latest version of this draft that I have is available at:
	http://people.nokia.net/~charliep/txt/seamoby/term.txt

If there is interest here, I would be happy to update the text
and have it for consideration as a working group document.  I think
it may also be under consideration within [seamoby].  I reckon that
both groups "ought" to be using the terms to mean the same thing.
I don't think that Jukka Manner or the other co-authors would mind,
but I have CC:'d them on this note in case they wish to offer
more thoughts on the issue.

Regards,
Charlie P.

---

From: Hridesh Rajan <[email-masked]>
Date: Fri, 11 Jan 2002 16:11:04 -0500 (EST)

Hello, 

Quoting Fred Baker <[email-masked]>:

> trying to do, or an algorithm for doing it. "flooding", to me, means "getting 
> something to every node in a domain." 

I agree to the above definition completely but I think in order to 
keep the efficiency in mind we should modify this a bit to say 
"Best effort service of getting something to every node in the domain."

Also when you say flooding, in *classical ways* it means to me as follows:  
"Request for a remote node to propagate the information along with flooding
request (I am avoiding other terms to keep conflict of layers at a minimum) 
contained in the flooding request to as many nodes as it can (best efforts 
service), while taking care to avoid replication using local information."

I do not understand why this classical way of definition is not fitting in Ad 
Hoc Mobile Networks? Clarifications please!!

Thanks,
Hridesh

---

From: Joe Macker <[email-masked]>
Date: Fri, 11 Jan 2002 16:46:41 -0500

Richard:

You inadvertently pulled up an older copy 00 of the ID. A definition of flooding is indeed in there. http://www.ietf.org/internet-drafts/draft-manner-seamoby-terms-03.txt

-Joe

---

From: Fred Baker <[email-masked]>
Date: Fri, 11 Jan 2002 13:44:16 -0800

>service), while taking care to avoid replication using local information."

in some applications, that may be what it means.

In classical routing, there is no attempt to limit replication, and it is 
not something *requested*, it is something *done*. When OSPF, for example, 
decides that a link has changed state or a neighbor has changed state, it 
generates a new LSA and floods it throughout its area. The node itself 
decided that, replication is a non-issue, and getting it to every node is 
of paramount importance, and so it uses an acknowledged protocol to ensure 
the distribution.

---

From: Hridesh Rajan <[email-masked]>
Date: Fri, 11 Jan 2002 17:17:53 -0500 (EST)

> not something *requested*, it is something *done*. When OSPF, for example,

When I defined flooding as a request above I was talking about the nodes which
are not the source of the information. For them I consider flooding as a
request. For the source node as well we can consider it as a request by
the local host.

> of paramount importance, and so it uses an acknowledged protocol to ensure

Whether in case of Ad Hoc Mobile Network getting the message to every node
will still be of paramount importance ? In fixed network its valid, but in
the case of Ad Hoc Mobile Networks in most cases its true that if a node
doesn't receives a packet it won't need that packet. I am assuming a situation
such as generation of a new LSA in OSPF. Lets assume a node A is trying to send
a new LSA to node B. This packet is of use to B dependent upon the connectivity
of A and B. I believe that in most cases if B doesn't receives this packet A can
safely assume that B can't use this information and so avoid using acknowledged
protocol for flooding.

Hridesh

---

From: [email-masked]
Date: Fri, 11 Jan 2002 17:15:44 -0800

> Richard:
> 
> You inadvertently pulled up an older copy 00 of the ID. A definition 
> of flooding is indeed in there. 
> http://www.ietf.org/internet-drafts/draft-manner-seamoby-terms-03.txt

Thanks, Joe.  (I don't think "inadvertently" is the right word,
since I was just following the links people posted.)

So I guess the consensus is that flooding means
"the process of delivering data or control messages to every 
node within the network under consideration",
and is therefore synonymous with "network-wide broadcast".

The brute-force mechanism for doing this is called
"classical flooding" in draft-ietf-manet-bcast-00.txt 
(and some other drafts) and "pure flooding" in the OLSR draft.
So I guess all other mechanisms for flooding are "impure".  :-)

In the 1980s, what we now call "classical flooding" was
called "flooding", so the definition of "flooding" is now 
more general, and even includes tree-based broadcast.
That's OK with me if most people agree on this.
I know some people who still consider "flooding" to mean
classical (brute-force) flooding, but I guess they (and I) 
will have to change their thinking.

Richard