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

From: Richard Ogier <[email-masked]>
Date: Thu, 26 Feb 2004 08:55:38 -0800

The INRIA simulation study that Cedric pointed to is interesting
and should be useful in helping to decide which way to go.
I will try to summarize how those results (and Cedric's message)
relate to our discussion of the last few days.

First, the CDS that Charlie has been suggesting, i.e., the
set of all MPR nodes, is found to include about 80% of the
nodes in the INRIA report.

But the "guaranteed" MPR forwarding rule that requires a node
to relay any packet that is received from an MPR selector,
is also very inefficient (according to my own simulations),
and the  MPR forwarding rule assumed in the INRIA report
is much more efficient - the packet is relayed only if the
*first* neighbor it was received from is an MPR selector.

As I pointed out, and (not surprisingly) INRIA knew a long
time ago, the "first arrival" rule does not always work
(which makes me wonder why it was in the MPRF draft).
Cedric agrees with me that my suggestion to use the
rule involving the pair (TTL, neighbor address) is
an efficient solution to this problem, and (not surprisingly)
INRIA already thought of this rule without the TTL.
I think the use of TTL is necessary to make the flooding
as efficient as the "first arrival" rule.

But this solution does not really address Charlie's concern
regarding reliability, and the desire to have a forwarding rule
that is independent of the previous hop.

Now, the *efficient* CDS used in the INRIA report is defined as follows.
A node decides that it is in the connected dominating set if:
Rule 1: the node has a smaller ID than all its neighbors,
Rule 2: or it is an MPR of its neighbor with the smallest ID.

This is certainly an efficient way to make the forwarding rule
independent of the previous hop, but it does not provide
min-hop paths (using only CDS nodes as intermediate nodes)
and therefore is probably not very useful for route discovery
in AODV.  Maybe I am wrong about this.

Also, the INRIA report considers two methods for selecting MPRs:
the greedy algorithm (as in OLSR), and the min ID algorithm.
The min ID algorithm allows nodes to select themselves
as MPRs (similar to TBRPF), and therefore has some advantages,
although it results in more transmissions (and a larger CDS).

In summary, maybe a combination of the methods discussed above
is a good solution, but I am still looking for a better solution.

Regards,
Richard

> Hello everyone,
>
> Sorry to jump in this discussion which I didn't follow, but my filter 
> detected
> a reference to my name :-)
>
> Regarding the MPR flooding, the MPR retransmission problem was known:
> the MPR flooding proof, found, for instance in INRIA RR 4260, pages 8-9.
> (http://www.inria.fr/rrrt/rr-4260.html) implicitly relies on a total 
> order of
>  transmissions (by considering the "first" transmission).
> This assumption is reasonnable on a single channel interface.
> When you have multiple interfaces each respecting this assumption,
> a proven MPR flooding algorithm is the one found in the OLSR RFC.
>
> Then, long ago, we thought of the same idea independantly found by 
> Richard,
> of using a "global order" on packets to retransmit, that is:
>   - retransmit a packet iff
>     . it has not been retransmitted
>     . and it has been just received from an MPR selector
>     . and it had been received only from nodes with greater ID than
>       the MPR selector (or never been received).
>
> I note that Richard added the very interesting novelty of using TTL
> in the ordering which would improve results.
>
> [Note also, that if the only reason messages cannot be ordered, is
> because they are repeated on a link, then you can use the
> "retransmission count", to order them, if this information is available.]
>
> Now for some results:
>
> Some simulations results for the Dominating Set based on MPR are
> available in INRIA Research Report 4597
> (http://www.inria.fr/rrrt/rr-4597.html).
> The important result is that the performance of dominating set based on
> MPRs, is very close to the performance of MPR flooding (see figure 6).
> This is expected.
>
> Some simulations results (some unpublished) we had are the following:
> |NeiCe| AvgNei | AllMPR | DomSet |MPRFlood|LO flood|LO+flood|Avg#MPR|
> |   7 |    7.6 | 67.30% | 54.24% | 48.48% | 56.05% | 53.59% |   3.1 |
> |   8 |    8.4 | 72.70% | 54.52% | 50.90% | 60.98% | 57.31% |   3.5 |
> |  10 |   10.3 | 75.10% | 50.43% | 47.55% | 59.99% | 54.80% |   4.1 |
> |  12 |   12.2 | 79.30% | 46.74% | 44.84% | 61.35% | 54.33% |   4.6 |
> |  15 |   15.0 | 80.20% | 40.05% | 38.35% | 57.31% | 48.41% |   4.9 |
> |  20 |   19.6 | 81.90% | 33.15% | 32.14% | 54.29% | 43.65% |   5.5 |
> |  30 |   28.6 | 82.10% | 24.68% | 24.05% | 46.84% | 34.66% |   6.2 |
> |  40 |   37.3 | 82.70% | 20.41% | 19.36% | 41.83% | 29.59% |   6.7 |
> |  50 |   45.8 | 82.50% | 16.84% | 15.66% | 36.84% | 23.86% |   7.0 |
>
> with 1000 nodes, uniform distribution in a square, "unit graph"
> and with:
>  - NeiCe : expected #neighbor of a central node
>  - AvgNei: avg number of neighbors on all the nodes
>  - AllMPR: % of nodes which are MPR of some other node
> - DomSet: % of nodes in the MPR-based dominating set
>  - MPRFlood: % of retransmitters in an MPR flooding
>  - LO flood:  % of retransmitters in an MPR flooding when
>   "logical order" is used (the algorithm given above)
>  - LO+flood: same as before, but with jitter delay
>  proportional to node ID (and no longer random).
>  - Avg#MPR: average number of MPR per node
>  
> Notes:
> . LO+flood, is using the idea that the jitter delay can be
> a function of the node ID. Now, it can be a function of hop count,
> node ID, sender  node ID, etc...
> . I did not test the following optimisation: if a node scheduled a
>   retransmission, and is now waiting for the jitter delay to
>   expire, but now if it receives the same message coming
>   from a node with lower ID than the MPR selector which caused
>   the scheduling retransmission, the node could cancel the
>   retransmission.
>
> I hope it might be of some interest to you, and I didn't
> flood you with irrelevant technical details...
>
> Best regards,
> -- Cedric
>
> On Wednesday 25 February 2004 21:00, Richard Ogier wrote:
> > 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
> >
> > > 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.
> > >
> > > 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
> > >                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.
> > >
> > > 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".
> > > >
> > > > _______________________________________________
> > > > 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: "Charles E. Perkins" <[email-masked]>
Date: Thu, 26 Feb 2004 10:04:47 -0800

Hello Richard,

> nodes in the INRIA report.

On the other hand, the number of MPRs selected by a node is
always far less than the number of neighbors for a node.

> *first* neighbor it was received from is an MPR selector.

O.K.  I am convinced that I have to re-think this.  It means
that many MPRs are _not_ on the MPR tree rooted at the source
of a packet, which I guess I should have realized before.
It would be bad to make MPRs remember which source trees
they are on (as opposed to just which neighbors they serve).

> in AODV.  Maybe I am wrong about this.

I reckon that the advantages of reduced congestion from
flooding can, in many circumstances, outweigh the advantages
of discoverying minimum-hop paths.  Plus, it matters
how far away from minimum the CDS paths are, on average.
Do you happen to have statistics for that?

Regards,
Charlie P.

---

From: Richard Ogier <[email-masked]>
Date: Thu, 26 Feb 2004 10:28:06 -0800

Charlie,

Here is an example that shows not all MPRs are on the MPR "tree"
rooted at the originator (although I see that you are now convinced of 
this):

    2-----5
   /|\   /|\
  / | \ / | \
 1  |  /  |  7
  \ | / \ | /
   \|/   \|/
    3-----6

Node 1 is the originator.
MPR of 1 is 3.
MPR of 3 is 6.
MPR of 7 is 5.
MPR of 5 is 2.

Of course, nodes 3 and 6 relay the packet sent by 1.
But according to your modified step 5.2, node 2 also
relays the packet, since 2 is an MPR of 3, which is
an MPR of 5 (which is an MPR of 7, which is not an MPR
of any neighbor).

Here is a quick idea that will result in a smaller CDS
and will solve all of the concerns.
The idea is to combine the "first arrival" rule with INRIA's CDS.
Thus a node forwards a received flooded packet if:

Rule 1: the node has a smaller ID than all its neighbors,
Rule 2: or it is an MPR of its neighbor with the smallest ID.
Rule 3: or it is an MPR of the first neighbor from which the
packet was received.

Rule 3 can be dropped if the node cannot determine the previous hop.
so this combination of rules works in all cases.
I see only two possible drawbacks:
  1. A larger number of nodes transmit each packet (although much
     less than the CDS consisting of all MPRs).
  2. If nodes cannot determine the previous hop, then the packet
     may be flooded along paths that are not (nearly) min-hop.

Again, this is just a quick thought, probably not the best solution.

Regards,
Richard

---

From: Richard Ogier <[email-masked]>
Date: Thu, 26 Feb 2004 10:34:08 -0800

A correction to my example:

Of course, nodes 3 and 6 relay the packet sent by 1.
But according to your modified step 5.2, node 2 also
relays the packet, since 2 is
an MPR of 5 (which is an MPR of 7, which is not an MPR
of any neighbor).

Regards,
Richard