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

[Cedric Adjih <[e-mail]>]

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" <[e-mail]>
> To: "Richard Ogier" <[e-mail]>
> Cc: "Mobile Ad Hoc IETF working group" <[e-mail]>
> 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
> > > [e-mail]
> > > https://www1.ietf.org/mailman/listinfo/manet
> >
> > _______________________________________________
> > manet mailing list
> > [e-mail]
> > https://www1.ietf.org/mailman/listinfo/manet
>
> _______________________________________________
> manet mailing list
> [e-mail]
> https://www1.ietf.org/mailman/listinfo/manet

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