Subject: Re: [manet] MPRF [flooding protocol] document initial revision

From: "Charles E. Perkins" <[email-masked]>
Date: Wed, 25 Feb 2004 15:00:24 -0800

Hello again Richard

Looking again, I see that I made an obvious
error.  The first clause of the re-revised 5.2
should read as follows in order to handle the
case of a graph with a single MPR:

          5.2  If this node is MPR for the sending node, or for any
               neighboring MPR, and if the time to live of the
               message is greater than '1', the message MUST be
               forwarded according to the following by broadcasting
               it on all interfaces that have symmetric neighbors
               other than the sender, with the TTL of the message
               reduced by one.

Regards,
Charlie P.

"Charles E. Perkins" wrote:
> 
> Hello Richard,
> 
> I did go back and look over the discussion that
> you cited.  It was very interesting work.  I have
> some further comments.
> 
> I suppose I have been assuming that the MPRs
> themselves form a connected dominating set.
> This provides assurance that a message
> transmitted by all MPRs goes everywhere.
> I believe this assumption is justified by
> the selection algorithm.
> 
> Suppose that an MPR is taken as a "guaranteed"
> relay for a flooded message.  By that, I mean the
> node _will_ transmit a flooded message if that
> flooded message is sent by its MPR selector.
> 
> My suggested change amounts to a "premature"
> scheduling of this guaranteed relay operation.
> In other words, I _claim_ that it "cannot" produce
> _more_ transmissions, if the MPR selector itself
> is an MPR.
> 
> If my _claim_ is correct, then I can't see how
> Cedric's simulations would show that more packets
> were sent.  Perhaps the aforementioned step 5.2
> needs one further refinement:
> 
>           5.2  If this node is MPR for any neighboring MPR, and if the
>                time to live of the message is greater than '1', the mes-
>                sage MUST be forwarded according to the following by
>                broadcasting it on all interfaces that have symmetric
>                neighbors other than the sender, with the TTL of the mes-
>                sage reduced by one.
> 
> If my claim is incorrect, it would be very
> helpful for me if you might explain why.
> 
> Regards,
> Charlie P.
> 
> Richard Ogier wrote:
> >
> > Yes, I recall that this method was discussed on the list about
> > a year ago, and Cedric ran some simulations showing that
> > it resulted in a large number of transmissions (in one case
> > about 50% of the nodes transmitted a given flooded packet).
> > So let's not forget about efficiency.
> >
> > There are several other methods that avoid having to know
> > the previous hop, including one suggested by Thomas Clausen
> > or Philippe Jacquet about a year ago in which a node relays a flooded
> > packet if and only if the minimum ID neighbor is an MPR selector,
> > or the node has smaller ID than all neighbors.  I am comparing
> > several of these via simulations and will announce the results
> > in a few weeks.
> >
> > Richard
> >
> > ----- Original Message -----
> > From: "Joe Macker" <[email-masked]>
> > To: "Charles E. Perkins" <[email-masked]>; "Richard Ogier"
> > <[email-masked]>
> > Cc: "Mobile Ad Hoc IETF working group" <[email-masked]>
> > Sent: Wednesday, February 25, 2004 10:43 AM
> > Subject: Re: [manet] MPRF [flooding protocol] document initial revision
> >
> > > At 12:37 PM 2/25/2004, Charles E. Perkins wrote:
> > >
> > > >Hello Richard,
> > > >
> > > >Taking your suggestions out of order, I'd first agree
> > > >with your proposed terminology.  I have noticed many
> > > >times that the terminology surrounding the flooding
> > > >discussion can be very confusing.  I will try to go
> > > >through the MPRF draft to make the indicated revisions
> > > >to our terminology.
> > > >
> > > >The example you give is, I think, applicable to other
> > > >situations where an MPR node receives a flooded
> > > >packet from other neighbors first.  It seems to me
> > > >that a very simple fix would work, though.
> > > >
> > > >If a MPR node receives a flooded packet from ANY
> > > >neighbor, it should go ahead and transmit the
> > > >packet again to its neighbors, and mark the
> > > >packet as already processed.
> > > Charlie:
> > >
> > > Several of us have been talking about and actually implementing
> > > that for quite awhile. The previous hop state is also not required.
> > > The election heuristics can also be tweaked in simple ways
> > > to have more common or less common MPR sets.
> > >
> > > We have this MPR-F option functional in a
> > > working implementation (providing generic multicast MANET forwarding).
> > > We are presently examining its robustness and performance in a
> > > few scenarios against other more stateful approaches.
> > >
> > > I must confess I haven't read the ID in detail yet, we're just busy
> > > implementing things.
> > >
> > > -Joe
> > >
> > >
> > >
> > > _______________________________________________
> > > manet mailing list
> > > [email-masked]
> > > https://www1.ietf.org/mailman/listinfo/manet
> > >
> 
> _______________________________________________
> manet mailing list
> [email-masked]
> https://www1.ietf.org/mailman/listinfo/manet

_______________________________________________
manet mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/manet

---

From: "Richard Ogier" <[email-masked]>
Date: Wed, 25 Feb 2004 15:05:28 -0800

Charlie,

> flooded message is sent by its MPR selector.

Then the nodes that relay the packet are the MPRs of the originator,
the MPRs of the MPRs of the originator, etc.

However, I don't think this set of nodes includes every node that
is an MPR of some neighboring MPR (as in your
modified step 5.2).   The difference is that there has to be
a sequence of nodes u_1,..., u_n where u_n is the originator
and each node is an MPR of the next node in the sequence.
The difference is that the sequence must lead to the originator,
and it might not.

I will have additional suggestions soon.

Regards,
Richard

---

From: "Richard Ogier" <[email-masked]>
Date: Wed, 25 Feb 2004 15:04:35 -0800

Charlie,

Regards,
Richard

---

From: "Richard Ogier" <[email-masked]>
Date: Wed, 25 Feb 2004 12:00:20 -0800

Charlie and all,

The discussion we had regarding the flooding method you
are suggesting can be found here
ftp://ftp.ietf.org/ietf-mail-archive/manet/2002-09.mail

Search for "Cedric", who ran the simulations.
Here is what Philippe Jacquet said about the approach:

> Richard,

> If you mean to include all MPR nodes in the dominating set, we have
already
> thought about it sometimes ago. We gave up this idea because it creates
much
> too large dominating sets (almost all nodes involved).

> Philippe

As Joe suggests, it is possible to reduce the size of the CDS by making
the MPR sets overlap more, e.g., by preferring min ID neighbors as MPRs.
In the extreme case, each step of the MPR selection algorithm selects
the min ID neighbor that covers some 2-hop neighbor that is not yet
covered.  In this case, you don't even use degree, and thus it becomes
possible for nodes to select *themselves* as MPRs or CDS nodes.
(This is similar to how nodes select themselves as MPRs in TBRPF.)

Having nodes select themselves as CDS nodes may also help reliability
and robustness, since a node can select itself immediately as a CDS
node following a link failure.  It would be nice to have simulation results
that measure how much this improves performance.

Richard

----- Original Message -----
From: "Charles E. Perkins" <[email-masked]>
To: "Richard Ogier" <[email-masked]>
Cc: "Mobile Ad Hoc IETF working group" <[email-masked]>
Sent: Wednesday, February 25, 2004 9:37 AM
Subject: Re: [manet] MPRF [flooding protocol] document initial revision

> This can be accomplished by modifying step 5.2
> to read as follows:
>
>           5.2  If this node is MPR for any of its neighbors, and if the
> I must admit that I have only been puzzling over your
> observation for a little while, so I might have missed
> something. But even without the problem you raised,
> this approach would be better for two reasons:
> - Reduced broadcast latency, and
> - Better robustness when the MPR selector's local
>   (typically unreliable!) broadcast is lost for some reason.
> Lastly, I think I like this approach because I seem to
> remember wanting to put it in a long time ago and I just
> forgot to do so.
>
> Regards,
> Charlie P.
>
>
> Richard Ogier wrote:
> >
> > Here is an example where the MPRF protocol does not work.
> > (Although it can be fixed as explained below.)
> >
> >       8
> >     /   \
> >    2-----5
> >   / \   / \
> >  /   \ /   \
> > 1     /     7
> >  \   / \   /
> >   \ /   \ /
> >    3-----6
> >     \   /
> >       9
> >
> > Node 1 is the source (originator of flooded packets),
> > and its MPRs are nodes 2 and 3.
> > Node 2 selects node 6 as MPR (to cover 3, 7, and 9)
> > Node 3 selects node 5 as MPR (to cover 2, 7, and 8).
> >
> > Node 1 originates a packet, which is relayed by nodes 2 and 3.
> > Suppose node 5 receives the packet first from node 2, then from node 3.
> > Suppose node 6 receives the packet first from node 3, then from node 2.
> > (I explain below how this is possible.)
> > Since node 2 is not an MPR selector of node 5, node 5 does not relay
> > the packet when it is received from node 2, but creates an entry
> > in the Flooding History (step 5.1 in the draft).
> > Then, when node 5 receives the packet from node 3 (its MPR selector),
> > node 5 ignores the packet (step 2 in the draft).
> > Therefore, node 5 does not relay the packet.
> > Similarly, node 6 does not relay the packet.
> > Therefore, node 7 never receives the packet.
> >
> > I think the solution is for each node to remember
> > which flooded packets it has already transmitted.
> > If a node receives a flooded packet from an MPR selector,
> > and has not yet transmitted the same packet, then it
> > should relay the packet.
> >
> > I think the same problem exists in
> >   draft-spagnolo-manet-ospf-wireless-interface-00
> >
> > I can think of 3 situations that can result in the
> > above example (in which node 5 receives the packet first from
> > node 2, and node 6 receives the packet first from node 3):
> >
> >   1. Very long propagation delays.
> >   2. As stated in the Introduction of the draft, link layer
> >      broadcast can be accomplished using iterated unicast.
> >   3. If the flooded packet is sent reliably to all neighbors using
> >      ACKs with retransmissions, then the first transmission from
> >      node 2 (resp. 3) might be received only by node 5 (resp. 6).
> >
> > Regards,
> > Richard
> >
> > P.S. Regarding the terms "reflood" and "retransmit".
> >
> > "Reflood" means to flood the packet again to all nodes.
> > RFC 2328 for OSPF uses this term correctly, but some
> > people have recently used it to mean "relay".
> >
> > "Retransmit" means for the same node to transmit the packet again,
> > usually because an ACK was not received.
> > It will be very confusing when we talk about reliable flooding
> > with ACKs, if we use the word "retransmit" to mean both
> > retransmission from the same node, and relaying a packet
> > received from another node.
> >
> > When talking about a node relaying a packet, I suggest using
> > either the term "relay" or "transmit".
> >