Subject: RE: Manet Flooding

From: "Nast, Douglas P" <[email-masked]>
Date: Mon, 7 Jan 2002 21:46:11 -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? 

> -----Original Message-----
> From:	Fred Baker [SMTP:[email-masked]]
> Sent:	Monday, January 07, 2002 4:18 PM
> To:	Scott Corson
> Cc:	Manet (E-mail)
> Subject:	Re: Manet Flooding
> 
> At 02:38 PM 1/7/2002, Scott Corson wrote:
> >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.
> 
> dumb question: is this significantly different from some form of IP 
> Multicast, either reliable or unreliable?

---

From: Fred Baker <[email-masked]>
Date: Tue, 08 Jan 2002 01:15:08 -0800

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

because it doesn't work very well. The RFC you're mentioning is RFC 1812, 
and as of that date the IETF believed what it says. But there are some 
serious looping and multiple delivery issues in the algorithms, which don't 
happen in IP Multicast.

---

From: Darrell Shane <[email-masked]>
Date: Tue, 8 Jan 2002 16:17:43 -0800

Scott I agree with your suggestion, flooding needs to be 
defined so that various techniques (protocols) can be 
objectively evaluated, measured and compared.  

From a "top-down" view, flooding can be controlled, both in 
terms of direction of progression and duplication of dissemination.  
The opposing tension to flood control is stated as three objectives:
	(1) duplication -- more than one attempt should be made to 
		disseminate data to each node in the flood area 
		(in case the target(s) are busy and not listening 
		during the first attempt)
	(2) obstacle circumvention -- attempts to disseminate 
		data to a node should come from different 
		directions (in case one direction is obstructed)
	(3) coverage maximization -- flood progression should 
		be resilient so that sparsely populated (but 
		connected) regions are still covered

Regards,
Darrell Shane
> From:	Scott Corson [SMTP:[email-masked]]
> Sent:	Monday, January 07, 2002 2:39 PM
> To:	Manet (E-mail)
> Subject:	Manet Flooding
> 
> 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.
> 
> 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: "Nast, Douglas P" <[email-masked]>
Date: Thu, 10 Jan 2002 09:32:13 -0800

I agree with Miguel.  

Earlier Joe pointed out that my previous definition of flooding: 

>... "flooding" to me is sending a packet out on every
>interface but the one you received it on.  

was wrong because of the implications of the term "interface".

I agree.  Here's what I meant to say:

"Flooding is sending a packet out on every link (potentially logical) but
the one you recieved it on".

Of course distinct logical links are often realized using a common physical
interface.  I also appreciate Joe's mention of heterogeneity.  One logical
link might represent a broadcast network, another a connection to one
partner in a NBMA network.

I expect each of these logical links to have their own queues, and be
candidates for the forwarding process mechanized by the manet LSRP.  I think
this is what Miguel suggests too.

Also, flooding can occur at either layer 2 or layer 3, and specifying which
we are talking about should be high on the priority list.  So please don't
complain about my use of the word "packet" in my new and improved definition
:-).

Doug

-----Original Message-----
From: Miguel Sanchez Lopez [mailto:[email-masked]]
Sent: Thursday, January 10, 2002 9:17 AM
To: Philippe Jacquet; Fred Baker; [email-masked];
[email-masked]
Subject: Re: Manet Flooding

Hi all,

However as I see it, if you only have one interface but you do have a
routing 
table you can mimic each of your first-hop nodes (neighbors) as being 
different interfaces. Then you can do RPF given you have a metric for each 
neighbor and forwarding direction (i.e. you only retransmit a packet if it 
arrived from a neigbor who is the best route to the source of the flooding).

Only one interface per node should no be a problem then.

Regards,

Miguel Sanchez
Universidad Politecnica de Valencia, Spain

El Jue 10 Ene 2002 14:08, Philippe Jacquet escribió:
> 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: Scott Corson <[email-masked]>
Date: Sun, 13 Jan 2002 15:05:59 -0500

Some reactions to these suggestions.

> 1. Layer 3 protocol, I guess this is obvious.
SC> yes

> 2. Best Effort only.
SC> as is traditionally known...yes

> 3. Distributed in nature.
SC> not really a requirement, but likely required of any useful protocol, at
the designer's discretion IMO

> 4. Highest priority should be to maximize delivery ratio 
> (percent of network
> nodes that receive a given flooded packet).
SC> unneeded requirement, again at designer's discretion

> 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.
SC> designer's discretion

> 6. Protocol should attempt to minimize redundant 
> retransmissions (ie leaf nodes
> don't retransmit).
SC> designer's discretion

> 7. Protocol should be robust given common MANET conditions 
> (ie high channel
> congestion,  frequently changing topologies).
SC> designer's discretion

> 8.  Protocol should be easily interfaced by other network 
> layer routing
> protocols.
SC> unclear requirement, this is certainly a goal

> 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.
SC> mechanism-dependent, not a requirement

> 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.
SC> mechanism again, not requirement

> 11. Allow payloads of various sizes.
SC> yes

> 12. Must have the means to prevent loops/replication.
SC> designer's discretion

> 13. Should attempt to minimize node resource by having low 
> order algorithms and
> low state requirements.
SC> designer's discretion

> 14. Should allow aggregation of payloads at the source node.
SC> designer's discretion

As you can see, my input as a WG member is not to specify or even bias the
manner in which the service is delivered.  Well-conceived, useful protocols
will find users, others will not.  

What is the minimal specification required to design a best efforts manet
flooding service? I think the addressing scheme needs agreement.  Anything
else?

-Scott

---

From: [email-masked]
Date: Sun, 13 Jan 2002 14:54:08 -0800

Hi Doug,

I would like to comment on your definition of classical flooding.

> this is what Miguel suggests too.

I will use Joe's terminology "semi-broadcast" to describe a 
non-broadcast wireless interface.  

Applying your definition to a MANET network in which each node
has a single interface, each node has a separate logical link to
each neighbor, and the definition therefore seems to imply that a 
separate transmission is required to each neighbor (except the
neighbor from which the packet was received).  Of course, if several
neighbors can be reached on a single interface, only one transmission
is needed.  

I suggest the following definition of classical flooding for
multiple interfaces:

"If a non-duplicate flooded packet is received on interface I, 
then the packet is sent (retransmitted) on every interface other 
than I, and is also sent on interface I if it is a semi-broadcast 
interface."

I was thinking of saying "if interface I is a semi-broadcast interface
with at least one neighbor other than the one from which the packet
was received", but it is possible that we want to reach nodes that are 
not known to be neighbors.

Regards,
Richard

---

From: [email-masked]
Date: Fri, 18 Jan 2002 10:04:02 +0100 (CET)

On Sun, 13 Jan 2002, Scott Corson wrote:

<SNIP>
 
> flooding service? I think the addressing scheme needs agreement.  Anything

Scott and others,

Isn't the addressing isue somewhat independant of the flooding issue? If a
mechanism is in place to perform "flooding" in general terms, then
addressing becomes just a way of deciding which traffic to flood?

As has been suggested before on the list, let's define some multicast
address, ALL_MANET_NODES, as the address of the group containing all
nodes in a given manet. Thus "flooding" is the objective that all
members in that ALL_MANET_NODES group recieve a given piece of data. (In
the same way, let's define an ALL_NEIGHBORS address such that a
packet transmitted will be received only by all nodes in the originators
neighborhood.) 

Thinking about a "manet" as a cloud of related nodes, in much the same way
as an Ethernet segment is, and (trying to) keep the spirit of the
definitions of RFC1812 in mind, I'd say that:

 	- the equivalent of the ALL_MANET_NODES is the limited
   	  broadcast address (255.255.255.255)

Now, RFC1812 also explicitly prohibits that any router forwards any packet
which have the destination address set to the limited broadcast address.
Thus to support existing applications which use broadcasts (e.g. service
discovery protocols), a MANET node could intercept transmissions
originated by itself and sent to the limited broadcast address somewhere
in the networking stack and rewrite the header to contain the destination
address ALL_MANET_NODES (i.e. convert a limited broadcast into a
"multicast" to ALL_MANET_NODES).

Thoughts, 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: "Manfredi, Albert E" <[email-masked]>
Date: Fri, 18 Jan 2002 10:46:14 -0500

> which have the destination address set to the limited 

This is not a big deal, mostly philosophy, but I would have equated the "all
MANET nodes" multicast address to the "all routers" multicast address
(224.0.0.2), or perhaps even more precisely, "all RIP2 routers" multicast
(224.0.0.9). Seems to fit this description more perfectly?

> "multicast" to ALL_MANET_NODES).

In my mind, the idea of the "all 1s" broadcast address is to keep that
broadcast inside the IP subnet only. The most obvious example of this being
ARP. Seems to me that in the spirit of IP, and RFC 1122, broadcasting to all
anything (all nodes, all hosts) in an internet is sort of verboten. We are
talking here about flooding information, for the purposes of route creation,
only to a set of manet routers. A good application for a well-known IP
multicast address?

Bert
[email-masked]