Subject: Re: Manet Flooding

From: [email-masked]
Date: Tue, 08 Jan 2002 09:55:05 -0800

>  dumber question.  Reverse path forwarding is the RFC-authorized (forget
> which at the moment) method for distributing a directed broadcast.  This
> relies on a unicast routing protocol that has determined "best" paths, is
> simple, yet significantly more efficient than flooding.  Why doesn't it
> apply? 

Douglas,

Reverse-path forwarding (RPF) is simply the concept of forwarding 
data packets in the reverse direction along the paths computed 
by a unicast routing algorithm, i.e., a packet with source u that is 
received by node i from the next hop (parent) on the path to u is
forwarded to the neighbors that selected node i as parent for u
(these neighbors are called children).  RPF is most useful
for proactive routing protocols.

RPF can be used in many ways. It is the basis for RPB (Reverse 
Path Broadcast) and TRPB (Truncated RPB), which was combined with 
RIP to create DVMRP (Distance-Vector Multicast Routing Protocol).

IP multicast routing protocols (e.g., DVMRP and PIM) are not
appropriate for MANET networks because they generate too much 
control traffic in highly dynamic networks (there are other
reasons but that is not the focus of this message).
Thus, several new multicast routing protocols (e.g., ODMRP) 
have been developed for MANETs.

The RPF in TBRPF stands for Reverse-Path Forwarding, since
TBRPF uses the parent-child relationship to propagate topology 
updates in the direction opposite to that of data packets. 
Since MANET networks have a broadcast capability, instead of
propagating updates to all children, a TBRPF node propagates 
an update for link (u,v) only if it has at least one child for u
(and only if it results in a change to its source tree), i.e.,
only if the node is a parent (for u) of some neighbor.

My main point is that the parent-child relationship already provided 
by TBRPF can also be used for the efficient broadcast/flooding
of data packets to all nodes in the MANET domain, using reverse-path
forwarding.  In fact, we have designed and implemented a 
*multicast* extension to TBRPF that uses this capability.

It is posible to use RPF with *any* proactive routing protocol
to provide network-wide broadcast, but this would require 
additional overhead since each node would have to send messages
updating its parent selection.  (These were called NEW PARENT 
and CANCEL PARENT messages in previous versions of TBRPF, but
we have eliminated them.)

> simple, yet significantly more efficient than flooding.  Why doesn't it

Regarding terminology, you and I seem to agree that the term
"flooding" refers to the inefficient method in which each packet
is transmitted by every node in the network.  Some MANET folks
use the term to include more efficient methods for network-wide
broadcast, since the term "broadcast" is often used to mean local 
(single-hop) broadcast.  Maybe some discussion is needed on this.

Richard

-----------------------
Richard Ogier
Sr. Research Engineer
SRI International
333 Ravenswood Ave.
Menlo Park, CA 94025
Tel: 650-859-4216
Fax: 650-859-4812
Email: [email-masked]
------------------------

---

From: Fred Baker <[email-masked]>
Date: Tue, 08 Jan 2002 13:41:28 -0800

I guess a big part of this discussion comes back to "what do you mean by 
'flood'", which I think paraphrases the original question. To my thinking, 
the fundamental questions come down to "who are you talking to" and "what 
are your requirements for saying things to them."

In routing protocols like OSPF or IS-IS, you are talking to "all routers in 
a domain", and the requirement is that they all maintain consistent routing 
databases, and that any material changes to that routing database be 
propagated in as timely a manner as possible. So it is perfectly acceptable 
to have multiple deliveries of the same information element - if it gets 
lost somewhere, this results in a variety of retransmission.

In a routing protocol like RIP etc, you are talking to "all routers that 
are or should be depending on me for a route". Duplicate deliveries of new 
information are acceptable, and may constitute delivery of information 
("there are multiple paths with the same metric, which might be used for 
load spreading") in their own right.

In a teleconference, you are talking to "all members of the conversation", 
which probably isn't related to the number or location of devices in the 
domain in any sense, and multiple deliveries are somewhere between not 
required and required to not happen due to bandwidth issues.

So I think a key lemma is "what is it that you are talking about flooding?"

There is no "one size" that "fits all" for manet networks, but I think the 
most demanding flooding applications in a manet network are likely to be in 
military applications. I am told that a typical military manet network 
might contain O(10K) components, many of which have internal complexity - a 
vehicle has addressable objects inside of it, for example. Any given node 
has various levels of "membership" and "interest" relationships: a vehicle 
is "interested" in any vehicle it might encounter within the next minute, 
perhaps; as it proceeds down a road, it has a position in an ellipse of 
interest. A person has various command relationships, and an "interest" in 
friendly forces that are located in his or her geographical region (for 
some definition of that term), regardless of type or hierarchy. In such a 
case, I would expect that you want something that looks a lot like 
multicast groups, both of a static and of a dynamic nature.

When you talk about flooding, in that case, it seems like you are trying to 
get messages from yourself to anyone who has a legitimate interest in you, 
whether for command or tactical reasons. Flooding routing information is an 
interesting special case of this sort of thing.

Hence my question about IP Multicast. Note I didn't specifically mention a 
protocol; I think ssm has some specific things to bring to the party here, 
and that's far from done.

---

From: Charlie Perkins <[email-masked]>
Date: Tue, 08 Jan 2002 17:32:24 -0800

Hello Fred,

We have a document (draft-ietf-manet-bcast-02.txt)
that proposes a couple of multicast addresses for
use when flooding data packets.  These multicast
addresses are not supposed to require a multicast
tree to be maintained.  Is this the kind of multicast
transmission that you were thinking of?

It has been pointed out to me that we could use
the IPv6 fragment header instead of the unique
identifier option that we suggested in this draft,
but I have not gotten around to updating the draft
yet with that suggestion.

Regards,
Charlie P.

---

From: Fred Baker <[email-masked]>
Date: Tue, 08 Jan 2002 17:59:30 -0800

At 05:32 PM 1/8/2002, Charlie Perkins wrote:
>These multicast

As I tried to say, the issue is the application. If there is no tree 
maintained, you have no assurance that they did or did not get to any given 
receiver, as there is the possibility that a given station moves while the 
multicast is in progress, so that when it comes time for its neighbor to 
deliver the message to it, the station now appears to be on the reverse 
path. If that's OK with the application (the application has some way to 
recover, or loss is expected and normally not recovered from), it's OK with 
me. If it's not OK with the application, we need to think again.

The advantage to maintaining some form of tree is that you're not dependent 
on those particular vagaries. You have other bugs to work around, and with 
any luck you might have a tool to work around them.

---

From: Charlie Perkins <[email-masked]>
Date: Tue, 08 Jan 2002 19:38:06 -0800

Hello Fred,

Fred Baker wrote:

> As I tried to say, the issue is the application.

Yes.  I will presume here that we are discussing applications
that want to deliver some payload to every node in the ad hoc
network (i.e., "flooding" applications).  Then we can still
distinguish between reliable flooding and "best-effort"
flooding.  Our proposal is for the latter.  For reliable flooding
in an ad hoc network, there would be a lot of bookkeeping
and maybe a tree would after all be the right thing, or else
just flood unreliable N times.  I reckon it's a lot harder
problem.

> any luck you might have a tool to work around them.

But the disadvantage is that maintaining a tree for a lot of nodes is
quite expensive.  Elizabeth Belding-Royer got some results for multicast
tree maintenance during the process of testing MAODV.  It works O.K.,
but not great.  There needs to be more development.

I think there should be two work items for the manet working group:
1) Unreliable, "best-effort" flooding
2) Multicast.

Using the latter for a multicast tree that contains every node in the
network could _probably_ use the same multicast algorithms as for
multicast trees that just have "lots" of nodes (not all of them).

Regards,
Charlie P.

---

From: "Jim Fleming" <[email-masked]>
Date: Wed, 9 Jan 2002 09:44:45 -0800

----- Original Message ----- 
From: "Charlie Perkins" <[email-masked]>
> just flood unreliable N times.  I reckon it's a lot harder

The 6-way ClusterBus of IPv8 and IPv16 keeps things manageable.
Six is a good number because 2 and 3 are commonly used to build
reliable and ultra-reliable systems. Sailors take 3 clocks to sea to
make sure they have a better chance of knowing the time. With 6,
the Any SRC and All Cast features are bounded.

http://www.dot-biz.com/INFO/Papers/

Jim Fleming
2002:[IPv4]:000X:03DB
http://www.IPv8.info

---

From: Joe Macker <[email-masked]>
Date: Wed, 09 Jan 2002 14:55:00 -0500

At 01:41 PM 1/8/2002 -0800, Fred Baker wrote:
>I guess a big part of this discussion comes back to "what do you mean by 'flood'", which I think paraphrases the original question. To my thinking, the fundamental questions come down to "who are you talking to" and "what are your requirements for saying things to them."
>
>In routing protocols like OSPF or IS-IS, you are talking to "all routers in a domain", and the requirement is that they all maintain consistent routing databases, and that any material changes to that routing database be propagated in as timely a manner as possible. So it is perfectly acceptable to have multiple deliveries of the same information element - if it gets lost somewhere, this results in a variety of retransmission.
>

Yes, the application of what you mean by flooding is important to consider.  I believe Scott's note was trying to separate the discussion of mechanisms flooding "routing protocol data" from flooding "end user data".  

But back to "routing protocol data/control" flooding, manet unicast protocols have developed interesting and "wireless friendly" ways of flooding routing control for internal routing information. e.g., OLSR's use of Multipoint Relays to build a distributed, source specific flooding tree...hmmm.. (other protocols have their ways as well and I am just using this an example)...so there is not one size fits all as you indicate since different routing protocols may do different things here.  

In the past, authors have come in with ID proposals for manet multicast routing independent or in some cases dependent on a specific unicast routing mechanism (perhaps borrowing off some inherent efficiency mechanism designed into the protocol).  Being a member of the WG that is also interested in multicast, I have been debating whether it would be useful to potentially use efficient control flooding mechanisms (perhaps unique to a protocol) for also flooding application data when appropriate.  (there are both design advantages and disadvantages here).. 

If we eventually get into multi-hop autoconf issues,etc such mechanism(s) would be useful for more than user data as well.  So perhaps a question would be..if we feel something should be supported in this realm how much do we borrow from particular unicast protocol mechanisms already in place? Or do we design mechanisms that are more independent from particular manet unicast routing protocol techniques used for control flooding?

For one, I am fan of multiple approaches once we know what the scenario categories are, but I believe we should have simple and effective approaches available for less scaled manets. I am listening and interested in what others have to say here.

-Joe

>When you talk about flooding, in that case, it seems like you are trying to get messages from yourself to anyone who has a legitimate interest in you, whether for command or tactical reasons. Flooding routing information is an interesting special case of this sort of thing.
>
>Hence my question about IP Multicast. Note I didn't specifically mention a protocol; I think ssm has some specific things to bring to the party here, and that's far from done.

---

From: "Philippe Jacquet" <[email-masked]>
Date: Thu, 10 Jan 2002 14:08:23 +0100

Dear all,

Technically RPF is interface driven. You must know the input interface of
the incoming broadcast packet in order to decide retransmission. Flooding
(or at least one way to see it) is duplicate detection driven. In flooding,
you retransmit a broadcast packet at most once and you discard all
duplicates, otherwise you get a duplicate storm (possibly up to (N-1)^255
duplicates!). You can further optimize flooding by reducing the number of
nodes allowed to retransmit, but this is another part of the story.

There are several possibilities for performing duplicate detection (protocol
encapsulation sequence number, IP fragment identifier, packet CRC-like
signature...). However it seems easier than the interface detection needed
for RPF. The problem with MANET is that in general you have only one
interface and you generally retransmit the packet through the same interface
you have received it. This makes RPF difficult to implement in MANET.

Philippe

---

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

Thomas, Thanks for the pointer to the draft.

Philippe,

RPF may be interface driven in some protocols (e.g., DVMRP),
but if you look at the early papers on RPF, e.g.

Yogen K. Dalal, Robert Metcalfe: Reverse Path Forwarding of Broadcast Packets. 
CACM 21(12): 1040-1048(1978)

you will see that it is not interface driven - the decision of 
whether to retransmit (forward) the packet depends on the
node it was received from (i.e., it must be the parent node),
and also on whether the deciding node has any children (leaves
need not forward the packet).  This is easy to implement in a MANET.

Alternatively, RPF can be modified so that a packet is
forwarded even if received from a non-parent, as long
as it is not a duplicate.  (Fred Templin and I have discussed
these two variations of RPF or DVMRP.) This is different from 
flooding because in RPF leaves do not forward the packet, whereas 
in flooding all nodes forward the packet.  So RPF with
duplicate detection requires fewer transmissions than flooding, 
but requires knowing whether you are a leaf which may require
additional overhead.  On the other hand, RPF with duplicate
detection is more robust than the version of RPF that only
forwards packets received from the parent (since the parent's
transmission might not be heard).  But since duplicate detection
requires some effort, it is not clear to me which version of RPF
is preferable.

Richard