Subject: RE: Manet flooding / broadcasting....

From: [email-masked]
Date: Mon, 21 Jan 2002 17:07:00 +0100 (CET)

> > mechanisms might not require condition (2).  Maybe we can 
> > discuss whether
> > condition (2) should be a requirement for all proposed 
> > flooding mechanisms.
>
> I agree that (2) is unnecessarily restrictive, and could be viewed as a
> *constraint* within the flooding policy used in (3).

I am not sure that (2) is entirely uncessary. The aim is basically to
avoid redundant retransmissions in order to save bandwidth. 

One proposed way of going about this is, as is suggested in
draft-ietf-manet-bcast-00.txt, to use some sort of duplicate table to
ensure that a given packet is not emitted more than once from a node.

Another proposal is to use previous-hop information and for a node to only
forward a packet if it is received from a node (previous hop) which is on
the shortest path to the originator of the packet.

I have concerns about the second proposal for two reasons. Firstly, it is
very "proactively oriented": it assumes that a given node has sufficient
information to be able to derive the shortest path to the source. This
approach would, therefore, be hard to apply in a broadcast protocol for
DSR and AODV and as such, it would be hard to arrive at one common MANET
flooding protocol. Secondly, getting the "previous hop" information is not
trivial. While it might be possible to realize (depending on the link
layer and os used) through looking at the hw-address and perform
arp-lookups, I would consider that it is preferable if a flooding protocol
does not depend on such 'hacks'.

-- 

-------------------------------------------
  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: Mon, 21 Jan 2002 18:52:43 -0800

Thomas,

>   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.

I wrote:

> > > 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.

> does not depend on such 'hacks'.

I agree with your second point, although I think the "hack" would be simple 
and useful.  Another argument against the second proposal is that it is probably 
not as reliable (as I mentioned before), since it requires that the flooded 
packet be received from a particular neighbor.
So I agree with you that the first proposal is *probably* better.

But I also agree with Scott that we should not prohibit protocols that
do not have this characteristic, so I would not want to rule out the second 
method (and other methods) before I am sure that the first method is better.

Also, we are not really talking about a *single* common MANET flooding protocol,
but a class of protocols, since condition (3) depends on the routing protocol.
So we could simply expand this class by letting condition (2) also depend on 
the routing protocol. However, this will probably not be necessary since we 
agree that the first method is probably better.

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: "Fred L. Templin" <[email-masked]>
Date: Tue, 22 Jan 2002 11:25:15 -0800

Thomas,
 
> the shortest path to the originator of the packet.

We have been experimenting with this method for some time, but in a way that
coexists with multicast protocols for broadcast media and MANET protocols that
require duplicate checks. Consider that multicast forward cache entries in
reference implementations such as the Linux kernel check received packets
based on tuples of the form:

  (source, group, interface)

This check is sufficient to reject duplicates on broadcast media
(e.g. Ethernet) since multicast routing protocols enforce a single active
parent for (source, group) on a paticular broadcast interface. But, the
check is insufficient for multi-hop media (e.g. MANETs).

We propose a simple extension to the API and a new element to multicast
forward cache entries to provide tuples of the following form:

  (source, group, interface, parent)

and specify the following behavior based on 'parent':

  - when parent = 0.0.0.0, behavior is exactly as in current
    reference implementations

  - when parent = 255.255.255.255, duplicate detection is performed
    (i.e., received packets are checked against a duplicate cache)

  - any other value for parent is interpreted as the IPv4 address
    of the previous hop from which the packet MUST originate 

Thus, this simple extension to the API and multicast forwarding cache
entry supports legacy behavior for broadcast media, duplicate table
checks for protocols that require such, and duplicate check avoidance
for protocols that choose to use that function. (All three functions
are supported simultaneously within the same multicast forwarding cache.)

> flooding protocol.

I believe this concern is alleviated by the above specification.

> Secondly, getting the "previous hop" information is not

Getting the previous hop requires a simple lookup in the neighbor cache.
In Linux, this can be done using the same mechanisms employed for sending
redirects, so there is existing precedent, i.e. it is not a hack. Duplicate
check avoidance can provide benefits for performance and reducing the amount
of multicast forwarding cache state required. The fact that it can coexist
seamlessly with other approaches seems to argue in favor of further
consideration. (Note that we are not committing to adopt the duplicate check
avoidance approach at this time, but are conducting further investigation.)

Fred
[email-masked]

---

From: "Philippe Jacquet" <[email-masked]>
Date: Wed, 23 Jan 2002 15:44:47 +0100

----- Original Message -----
From: "Fred L. Templin" <[email-masked]>
To: <[email-masked]>
Cc: <[email-masked]>; <[email-masked]>
Sent: Tuesday, January 22, 2002 8:25 PM
Subject: Re: Manet flooding / broadcasting....

> avoidance approach at this time, but are conducting further
investigation.)

Is neighbor cache not built only from ARP packets? Broadcast (multicast)
packets are not caught. How can you get the last hop IP addresses of a
broadcast packet this way?

Philippe

---

From: "Fred L. Templin" <[email-masked]>
Date: Wed, 23 Jan 2002 10:25:02 -0800

Phillipe,

> broadcast packet this way?

There will NEVER be a case of consulting the neighbor cache for a
broadcast/multicast address. The following clarifications to my

>     (i.e., received packets are checked against a duplicate cache)

When parent = 0.0.0.0 (respectively, 255.255.255.255), previous-hop
verification is NOT performed; instead, these values for parent
indicate to the kernel multicast forwarding cache that no checks
(respectively, duplicate packet checks) are used for received
packets for this particular cache entry.

>     of the previous hop from which the packet MUST originate

Only IPv4 *unicast* addresses are accepted for 'parent' by the API
that creates multicast forwarding cache entries. The following note
should be added to the above:

      (Note: implementations MUST verify that 'parent' encodes an
       IPv4 unicast address when the multicast forwarding cache entry
       is created)

Finally, the algorithm for previous-hop verification when 'parent'
encodes an IPv4 unicast address is as follows:

 - Compare the MAC (layer-2) source address of the received packet with
   the MAC address resolution for 'parent'. If the two addresses match,
   ACCEPT the packet; else, REJECT

Fred
[email-masked]

---

From: "Fred L. Templin" <[email-masked]>
Date: Wed, 23 Jan 2002 12:53:44 -0800

Phillipe,

> broadcast packet this way?

It's possible I may have mis-interpreted your concern; are you asking about
the case when a node receives only broadcast/multicast (and not unicast)
packets from a particular previous hop? In that case, you are right that
there may be no pre-existing neighbor cache entry for the previous hop.
The receiving node corrects this by issuing an on-demand neighbor
resolution for the previous hop's IPv4 address (in this case, by
sendig an  'ARPOP_REQUEST'). Muticast packets received while the resolution
is in-progress are temporarily cached by the node in the same manner as when
a multicast forwarding cache entry for (source, group, interface) does not
yet exist in the current model.

Note that, if the node is performing explicit neighbor cache management
based on received neighbor discovery messages, the neighbor cache entry
may be maintained proactively, rather than on-demand based on unicast
packet arrivals; thus avoiding the above scenario. We believe proactive
neighbor cache mangement (when possible) can provide the important
benefit of increasing packet delivery ratio; the above scenario is
just one example where this is true.

Fred
[email-masked]