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

From: "Charles E. Perkins" <[email-masked]>
Date: Mon, 16 Feb 2004 11:24:44 -0800

Hello folks,

After a long gestation, an initial revision of our
proposal for more scalable flooding has finally made
it into the Internet Drafts directory.

MPRF ("Multi-point Relay Flooding") has the following
goals:
- Scalable flooding
- Intended to work with AODV, OLSR, DSR, and TBRPF
  albeit with perhaps some minor modifications
- Works in networks that contain nodes that are not
  MPRF-aware
- Fits well within IP, allowing forwarding for TTL>1
  without requiring application processing
- Allows layer-2 broadcast (instead of iterated
  unicast tunneling) when possible
- Allows for parametrizable redundant coverage
  to help overcome the deficiencies of unreliable
  broadcast
- Works for all upper layer protocols without
  requiring IP to make decisions based on the
  payload.

It is the authors' intention that even this fairly
rough initial draft may help to ease future protocol
convergence within [manet].

A significant difficulty with the current algorithm
is that a node may be a MPR for some of its neighbors
but not for other neighbors.  It would greatly
simplify the algorithm if we could identify a
useful mechanism by which a node is either a MPR
or not, and all of its neighbors would agree on
that status.  If that happens, then there will no
longer be a need for the MPR node to determine which
of its neighbors transmitted the flooded packet.
As it is, we need this determination.  When the
identification cannot be made by inspecting the
source address in the MAC header, the flooded
packet has to be tunneled.

Comments will, as always, be appreciated.  If it
is found to be useful, we would like to see this
protocol document be considered as a working group
draft.

Regards,
Charlie P.

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

---

From: "Charles E. Perkins" <[email-masked]>
Date: Mon, 16 Feb 2004 11:45:10 -0800

Hello again,

I should have mentioned, that the draft is available
now at:
   http://people.nokia.net/charliep/txt/mprf/mprf.txt

Regards,
Charlie P.

---

From: Richard Ogier <[email-masked]>
Date: Mon, 16 Feb 2004 13:18:34 -0800

Hello Charlie,

>of its neighbors transmitted the flooded packet.

As you know, there exist algorithms for selecting a connected
dominating set (CDS) based on 2-hop neighbor information. (Some
of these are cited in draft-ogier-manet-ospf-extension-00.txt.)
This would result in MPRs that all neighbors agree on,
i.e., source-independent MPRs.
Although none of the published CDS algorithms appears to be
ideal for this purpose, I have been experimenting with some
variations that appear promising. (These are not yet published
but I can email you their descriptions if you want to
experiment with them.)

But I wonder whether a CDS (or source-independent MPRs)
is really appropriate for AODV, since it does not provide
a min-hop path whose intermediate nodes are all MPRs.
I.e., if route discovery in AODV were done by flooding
a Route Request via CDS nodes, then you discover a path
that uses only CDS nodes, but the path could have much more
than the minimum number of hops.  A CDS is most useful if
you want to flood efficiently (with minimum number of
transmissions) and don't care if the flooded packet
reaches each node in the minimum number of hops. Therefore,
I think a CDS is useful for link-state routing (to flood
link states efficiently) and for general flooding purposes,
but am not sure if it is appropriate for AODV and DSR.

Also, I am still wondering whether MPRs should be selected
by neighbors (as in OLSR) or whether each MPR should select
itself based on 2-hop neighbor information (as in TBRPF).
The latter approach has some potential advantages which have
been discussed on this mailing list, such as faster convergence
following link failures, and avoiding the overhead of reporting
MPRs to neighbors. I think the relative performance of the
two approaches should be compared in simulations before deciding
which approach to use.

Regard,
Richard

---

From: Joe Macker <[email-masked]>
Date: Tue, 17 Feb 2004 12:27:46 -0500

>packet has to be tunneled.

We prototyped a working approach for modified-MPR flooding.
We use side information from the 2-hop neighbor management process
requiring no previous hop information for forwarding. (its unpublished as of now).

But we might have source code soon on-line.

Yes there are lots of algorithms for this.

-Joe

---

From: Justin Lipman <[email-masked]>
Date: Wed, 18 Feb 2004 12:21:59 +1100

Hi Charles et al,

I published a small paper in ICON 2003 which describes Utility Based Flooding 
(UBF) - a more generic approach to selecting MPRs, based soley upon 
forwarding utilities. 

http://www.titr.uow.edu.au/~justin/raid_icon03.pdf

I also have a version, not yet published, which allows nodes to be self 
selecting (in terms of MPR status) during a flood given minimal prior 
broadcast information. Both approaches have equivalent performance to MPR.

However the biggest difference is that UBF is "Resource Aware"!
Thus UBF is able to account for a node's battery power or even user based 
constraints. I think this is really very important in ad hoc network 
environments that consist of heterogenous nodes and definitely useful in 
reactive protocols for route discovery.

kind regards,
Justin

Ps. Below is a short description of UBF. Sorry for the latex...

\cite{LBCJ1} describe a distributed optimised broadcasting mechanism for ad 
hoc networks called Utility Based Flooding (UBF). UBF unlike existing 
optimised broadcasting mechanisms is fully resource aware. UBF selects relays
based solely upon a forwarding utility ($U_f = BU_pU_n$). The utility 
$U_p=1/1+e^{-P+s}$ is a sigmoid function where $P$ is the remaining energy at 
a node while $s=MaxEnergy/2$ is half the maximal energy. $U_n$ is the ratio 
of unallocated (uncovered) local two hop neighbours and the total number of 
two hop neighbours. The significant point in UBF, is that the selection of 
nodes with unique neighbours is not a priority as in MPR.  In this way the 
coverage provided by those best nodes (in terms of resources) is accounted 
for irrespective of unique neighbours as is done in MPR. $U_n$ increases the 
utility of possible relays that may have unique neighbours. However, if a 
node with a unique neighbour is not suitable because of constraints or low 
resources, then its utility will remain low such that it may only be selected 
after all other possible relays are selected. The benevolence ($B$) is used 
to represent any constraints imposed upon a device.  A user may allow a 
device attached to a reliable power source to fully participate in network 
activities. However, if the device is mobile and the battery power drops 
below a specified limit, the user may not wish the device to participate. 
Existing broadcasting mechanisms do not account for this type of behaviour. 
Thus their performance will be degraded in such a network as they may select 
restricted nodes as relays which will not rebroadcast messages. UBF is 
compared, through simulation, to existing flooding mechanisms in
a constrained environment. Nodes are assigned varying degrees of remaining 
battery power and user based constraints that limit a nodes benevolence based 
upon its remaining battery power. UBF is shown to: significantly improve
broadcast reachability over successive broadcasts, not adversely affect 
performance and extend the lifetime of both nodes participating in the ad hoc 
network and the network itself.

-- 
Research Associate
Smart Internet Technology Cooperative Research Centre
http://www.titr.uow.edu.au/~justin

---

From: Richard Ogier <[email-masked]>
Date: Sat, 21 Feb 2004 08:47:15 -0800

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

---

From: "Charles E. Perkins" <[email-masked]>
Date: Wed, 25 Feb 2004 09:37:57 -0800

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.

---

From: Joe Macker <[email-masked]>
Date: Wed, 25 Feb 2004 13:43:46 -0500

>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

---

From: Charlie P <[email-masked]>
Date: Wed, 25 Feb 2004 10:56:52 -0800

Hello Joe,

I'm delighted to hear that you are creating the
implementations.  I'd like to find out whether
you think we could use your experiences to
improve the existing draft, and your suggestion
about how to eliminate the need for knowing
the previous hop.  That would be a great
simplification.

I remember a probabilistic MPR selection
algorithm that I wasn't too fond of.  It seems
to me that, if a broadcast failure occurs, it
should be allowable only because of problems
with the medium (or level of congestion), not
probabilistically disfavored layouts.  Do you
have an opinion about this?

Regards,
Charlie P.

---

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

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

---

From: Einar Vollset <[email-masked]>
Date: Wed, 25 Feb 2004 20:31:12 +0000

As this vaguely within my field I thought I'd pipe up.

> have an opinion about this?

In general, I think it might not be as straight forward as that. The 
choice might be as follows:

1) a deterministic broadcast algorithm which leads to failures as the 
overhead of constructing
the MPR means that the medium is congested.

or

2) a probabilistic protocol which has a high (possibly _very_ high) 
likely hood of not failing,
partly because there is less overhead due to constructing the MPR.

I don't think discarding probabilistic approaches is necessarily the 
best approach. For example, alot
of good work has been done by Luo, Eugster and Hubaux at EPFL as well 
as Ken Birman's group at Cornell
in arguing the merits of probabilistic approaches. One of their main 
arguments is scalability, which is
particularly timely with the formation of the ANS IRTF group (though 
perhaps less so now with the renaming ;-)

p.s. Out of interest, what are the parameters used for the simulations 
which the decisions are being made on?

Cheers,

Einar

----------------------------------------
Einar Vollset
PhD Student
School of Computing Science
University of Newcastle, UK
http://vollset.org
-----------------------------------------

---

From: "Charles E. Perkins" <[email-masked]>
Date: Wed, 25 Feb 2004 13:36:54 -0800

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

If my claim is incorrect, it would be very
helpful for me if you might explain why.

Regards,
Charlie P.

---

From: "Richard Ogier" <[email-masked]>
Date: Wed, 25 Feb 2004 15:03:10 -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:06:56 -0800

Charlie,

Regards,
Richard

---

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

Charlie,

Regards,
Richard

---

From: Cedric Adjih <[email-masked]>
Date: Thu, 26 Feb 2004 03:29:17 +0100

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
>
>
>
> Sent: Wednesday, February 25, 2004 9:37 AM

---

From: Justin Lipman <[email-masked]>
Date: Thu, 26 Feb 2004 14:11:45 +1100

Hi all,

I wonder if there has been some consideration as to the performance of 
optimised flooding mechanisms in the presence of background traffic. 

From my own simulations results in Glomosim... MPR and other optimised 
flooding mechanisms performed very badly as increasing CBR background traffic 
was introduced, especially compared to Blind flooding. This makes their use 
very limited. 

The following is a paper on reliable optimised flooding that shows some 
results for MPR, LMST, Blind flooding vs a more reliable version of LMST that 
uses unicast packet transmission instead of broadcast packet transmission.

http://www.cse.unsw.edu.au/~justinl/rmst.pdf

Kind regards,
Justin

On Thu, 26 Feb 2004 10:09 am, Richard Ogier wrote:
> > > > working implementation (providing generic multicast MANET
> > > > forwarding). We are presently examining its robustness and
> > > > performance in a few scenarios against other more stateful
> > > > approaches.
> > > >

---

From: "Charles E. Perkins" <[email-masked]>
Date: Thu, 26 Feb 2004 09:48:29 -0800

Hello Richard,

If the MPR algorithm works, it has the following
property:
	For any node X, if X floods a packet, then
	the packet is transmitted to every other node
	in the network either by X or by some MPR in
	the MPR tree rooted at X.

So, away from node X, and under the assumption
that flooding works algorithmically, the task
is to get the MPRs to transmit packets to their
neighbors.

Another way to say this is that, assuming a
correct selection algorithm, we get flooding if
every MPR transmits the flooded packet once
(disregarding errors).

Since I claim that my suggestion still fulfills
this condition, I believe it still is correct.
And, since we are "expecting" one transmission
from each MPR, I believe also that it does not
increase the number of expected transmissions.

To your point:

Richard Ogier wrote:

> ... the nodes that relay the packet are the MPRs of the originator,

Check.

> modified step 5.2).

I believe this set includes all MPRs in the dominating set which is
the MPR tree rooted at the originator of the packet -- otherwise
the algorithm is broken.

>                        The difference is that there has to be

Look at it the other way around, and it's easier to see.
The originator has one or more MPRs.  Every node has one
or more MPRs, including all MPRs in the MPR tree rooted
at the originator of the packet.  Every MPR tree forms a
connected dominating set.

If these statements are incorrect, then I believe the algorithm
is broken.  However, I believe the statements are in fact
correct, and thus it is impossible to identify a scenario in
which no sequence ever leads back to the originator.

What's needed is proof, I guess, and not intuition.
For that, I reckon I need to read the Inria research
report.  But some kind soul may reproduce the proof
for us here, who can tell?

Regards,
Charlie P.