Subject: Manet flooding / broadcasting....

From: [email-masked]
Date: Thu, 17 Jan 2002 16:07:25 +0100 (CET)

Dear All,

On the topic of broadcasting/flooding, would one starting point not be for
the working group to work on a common document in order to address common
basic issues such as addressing, duplication detection, classical
flooding, etc? This document could also provide a general framework for
utilizing optimizations of the flooding mechanism, derived from the
various unicast protocols.

The WG could take the proposal from Perkins
(draft-ietf-manet-bcast-00.txt) as a starting point, and elaborate on some
ideas which may be able to incooporate various of the ideas floating
around.

Basically, the flooding mechanism proposed by Perkins goes as follows
(ignoring addressing issues etc. for now): when a packet is received, it
is forwarded under the condition that:

	1) the packet destination is ALL_IPv4_MANET_NODES (corr. for IPv6)

     	   AND

	2) the packet hasn't been received before (transmission duplicate
	   elimination)

The virtue of this approach is that no further information about the
network is required. Likewise, each node is relatively free to choose how
to make transmission duplicate elimination.

There have, however, been concerns about the fact that e.g. nodes "on the
edge" of the network would also retransmit a broadcast message, and that
this may be undesireable.

draft-ietf-manet-bcast-00.txt opens the possibility (in section 5) that
selective retransmissions are possible as a way for a node to modify the
conditions under which a packet is forwarded. This can easilly translate
into a third condition, in addition to the two above. Thus, when a packet
is received, it is forwarded under the condition that:

	1) the packet destination is ALL_IPv4_MANET_NODES

           AND

	2) the packet hasn't been received before

           AND

	3) there are no further constraints specifying that a packet
	   should not be forwarded.

This would be a very generic way of allowing different optimizations
(perhaps in the draft?) to be specified as constraints on the packet
forwarding.

As an _example_, if the unicast routing protocol OLSR
(draft-ietf-manet-olsr-05.txt) is in place in the network, the notion of
MPR's can be used to provide such a constraint in different ways. One
possible way would be to put the constraint that:

 "a node is allowed to forward a broadcast packet iff it has forwarded the
  last received TC-message from the node with the lowest IP-address in the
  network"

This would utilize the MPR-optimized flooding and provide a smaller number
of retransmissions in the network than that of "classical flooding"
(indeed, the nodes on the "edge" would not be forwarding broadcast
traffic).

I am sure, that there are ideas like that which would take advantage of
features of the other proposed unicast protocols in the wg, as well as
from other sources.

Any thoughts on this, anyone?

-- 

-------------------------------------------
  Thomas Heide Clausen
  Civilingeniør i Datateknik (cand.polyt)
  M.Sc in Computer Engineering

  E-Mail: [email-masked]
  WWW:    http://www.cs.auc.dk/~voop
-------------------------------------------

---

From: [email-masked]
Date: Thu, 17 Jan 2002 16:17:50 -0800

To Thomas, Charlie, and all:

Please see my comments below.

Thomas Clausen wrote:

<snip>

> (perhaps in the draft?) to be specified as constraints on the packet

We are considering a flooding mechanism that does not require duplicate detection, 
so condition (2) may be too restrictive.  (This mechanism is the third one
presented below.) I agree that it would be good to describe routing-protocol 
dependent flooding mechanisms in the general flooding draft, but some of those
mechanisms might not require condition (2).  Maybe we can discuss whether
condition (2) should be a requirement for all proposed flooding mechanisms.

>   last received TC-message from the node with the lowest IP-address in the

An equivalent constraint for TBRPF could be the following:

  "a node is allowed to forward a flooded packet only if the node with the
  smallest router ID in the network belongs to RN (the "reportable node set"
  computed by TBRPF)."

An alternative constraint is to use the source node of the packet instead
of the node with smallest RID:

  "a node is allowed to forward a flooded packet iff the source node for the 
  packet belongs to RN (the "reportable node set" computed by TBRPF)."

The above two constraints assume that duplicate detection is used.
Duplicate detection can be avoided if, in addition to the above 
constraint, a node is allowed to forward a flooded packet only if the 
neighbor from which it was received is the next hop for the route to the 
source of the packet.  

An advantage of avoiding duplicate detection is that there is no need to
remember the Flooded Packet Identifier (FPI) for packets already received, 
and for IPv6 there is no need for the Unique Identifier Destination option.
However, avoiding duplicate detection may reduce reliability, since a node
might not receive a flooded packet from the next hop neighbor due to collision, 
but might receive it from another neighbor.
We plan to evaluate the above three alternatives (and other alternatives)
before deciding the best way to do flooding.

One other point is do we really want to require the first constraint?

> 	1) the packet destination is ALL_IPv4_MANET_NODES

Since multicasting is not yet a WG work item, it is possible that we will
have a standard flooding mechanism before we have a standard multicast protocol.
In that case, it might be good to use a flooding mechanism to deliver packets
to other multicast groups.  In fact, if the multicast group includes almost
all MANET nodes, it might be more efficient to use flooding than to use
tree-based multicasting (to avoid the overhead for maintaining trees).

Regards,
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: Charlie Perkins <[email-masked]>
Date: Thu, 17 Jan 2002 19:06:08 -0800

Hello Richard,

> tree-based multicasting (to avoid the overhead for maintaining trees).

Just because the destination is a multicast group, does not
mean that the delivery mechanism has to involve a multicast
tree.  In fact, I would say thta we should explicitly imagine
that the multicast address used for flooding would probably
not maintain a multicast tree.  There is no need to do so,
as far as I can tell.

Regards,
Charlie P.

---

From: Christian Tschudin <[email-masked]>
Date: Fri, 18 Jan 2002 10:07:51 +0100 (MET)

On Thu, 17 Jan 2002 [email-masked] wrote:

> > Thus, when a packet
> We are considering a flooding mechanism that does not require
> duplicate detection, so condition (2) may be too restrictive.

agreed - control traffic diffusion (setting up a tree, or a unicast path,
for example) might benefit from duplicate detection, but actual data
forwarding, even when "flooded", can work in a different mode. LUNAR has
this distinction: data packets travel in separate and transients delivery
conduits, for unicast as well as for flooding.

christian.

---
Christian Tschudin, Uppsala University, IT Dept., Box 325
S-75105 Uppsala, Sweden. http://www.docs.uu.se/~tschudin/

---

From: [email-masked]
Date: Fri, 18 Jan 2002 11:05:50 -0800

Charlie,

> not maintain a multicast tree.  There is no need to do so,

I agree.  But most of the multicast protocols proposed for
MANETs (including MAODV) create a tree regardless of the
multicast group, even if the group includes almost all
MANET nodes.  Currently, the assumption seems to be that a
*flooding* mechanism is used only for ALL_MANET_NODES, and that
a *multicast* protocol is needed for most other multicast addresses.
My main point is that it might be good to use a *flooding* mechanism to 
deliver packets to *other* multicast groups (not only to ALL_MANET_NODES)
especially if the group includes most (but not all) MANET nodes.   

I guess one answer is that the multicast protocol can decide
whether to simply use flooding (instead of creating a tree)
for a particular multicast group.  But if we have a standard flooding 
mechanism before we have a standard multicast protocol (for MANETs),
then we might want to allow the flooding mechanism to be used for
general multicasting.  

Regards,
Richard

P.S. Fred Templin and I previously proposed a method for flooding
packets having the limited broadcast address (255.255.255.255)
and low-numbered multicast addresses (224.0.0.x) to all MANET
nodes, by encapsulating into a packet having the ALL_MANET_NODES
address. (Search for message posted last March to May having
"MANET addressing" in the subject.) The above discussion does not 
include these addresses.