Subject: [manet] Flooding via MPRs

From: Richard <[email-masked]>
Date: Tue, 03 Sep 2002 08:43:20 -0700

All,

I would like to suggest some ideas for possible inclusion
in the MPRF (Flooding via Multipoint Relays) draft that
Charlie Perkins presented at the Japan meeting, and hopefully
to stimulate some discussion.
For reference, here is a link to the MPRF presentation:
http://www.ietf.org/proceedings/02jul/slides/manet-1/sld001.htm

I have exchanged some emails with Charlie regarding these ideas,
and he agreed with me that it would be a good idea to post my
suggestions to the manet list.

First, I want to point out that Charlie and I are using a more
general definition for MPR than the one given in the OLSR draft.
In particular, the OLSR draft defines an MPR as "a node which is 
selected by its one-hop neighbor...", whereas the more general
definition allows an MPR to select itself, either with respect 
to one or more neighbors called "MPR sources" (instead of 
"MPR selectors") or independent of the source (in which case the 
decision to forward a flooded packet is independent of the neighbor 
from which the packet was received).  

Under this more general definition, the "parents" of TBRPF 
(which select themselves) can now be called MPRs.
Thus, OLSR and TBRPF both select MPRs, but in different ways.
I think this simplifies the discussion (instead of saying
that "parents" are analogous to MPRs).

The rule for forwarding a flooded packet based on MPRs is as follows: 
a non-duplicate flooded packet with nonzero TTL is forwarded if the 
router is an MPR w.r.t. the neighbor from which the packet was received 
(previous hop), or (when the previous hop is not known) if the router 
is a source-independent MPR.  
The previous hop can be known if layer-2 addresses are accessible, 
or if the packet is tunneled/encapsulated at each hop.  

Knowing the previous hop is likely to make the flooding more efficient
(since fewer nodes will forward each packet), which might justify
the additional overhead of tunneling.

To provide some more background, I will quote some excerpts from
Charlie's emails to me (with his permission):

Charles Perkins wrote:

> Right. The decision _could_ be based on options depending on
> accessibility of layer-2 addresses, and _should_ be smoothly
> selectable so that the same algorithm works whether or not the
> decision is source dependent.

...

> I guess that the point of doing an MPR draft is that
> there needs to be a way of finding MPRs.  It does not
> mean that every ad-hoc networking protocol has to be
> able to follow that particular algorithm/protocol, but
> I think that the MPR draft should be ABLE to be
> applied to the four protocols of current interest.

> It looks like a sure bet that MPRF won't resemble
> very closely what's in OLSR, for a variety of reasons
> mainly centering around my demand for maximal simplicity.
> Whether the result is "closer" to OLSR or TBRPF depends
> on the typical array of considerations, including your
> own suggestions, whatever ideas we can come up with,
> working group consensus, and pure luck.

> I'm still puzzling over whether a node should tell its
> neighbors whether it wants them to be MPRs, or instead
> whether every node should decide for itself whether it
> wants to be an MPR.  The latter, of course, immediately
> solves the tunneling problem.  I like it.  When I get
> past my current backlog of things to do yesterday, I'll
> try to figure it out the rest of the way.

The TBRPF method in which nodes select themselves as MPRs
is one possible solution to this problem.  Although the method
is source-dependent, it is easily modified to be source-independent
(see below). 

We are not claiming any IPR for this technique: we have not submitted
a patent application and do not plan to.  (In fact, due to recent
developments, IPR is not likely to be an issue for TBRPF in general,
but this is another topic.)

The TBRPF method is as follows: Based on 2-hop information, each
node computes the min-hop path (up to 2 hops) from each neighbor
to each other neighbor, using min node ID as a tie breaker.
If the 2nd node of any such path is the node itself, then the node 
selects itself as MPR for the neighbor that is the 3rd (last) node 
of the 2-hop path.  A node selects itself as a *source-independent*
MPR if it has selected itself as an MPR for *any* neighbor.

Note that using min node ID reduces the number of MPRs.
Of course, hysteresis can be used so that only high quality
neighbors are considered.

This method has the following advantages:

  - Avoids overhead for sending messages to update MPRs.
  - Faster response to failures since MPRs select themselves
    without having to wait for neighbors to select them.
  - Both source-dependent and source-independent MPRs are selected,
    and using node ID is a good way to reduce the number of
    source-independent MPRs.

That's all for now.

Regards,
Richard

P.S. The source-independent version of the method described above
is similar (but not equivalent) to the distributed algorithm
in the following paper for finding a connected dominating set:

Jie Wu, Hailan Li: A Dominating-Set-Based Routing Scheme in Ad Hoc 
Wireless Networks. Telecommunication Systems 18(1-3): 13-36 (2001)

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

---

From: "Tao Lin" <[email-masked]>
Date: Tue, 3 Sep 2002 12:01:29 -0400

Richard,

Our research group already worked on this topic. A paper regarding this idea
is submitted recently. Once it is accepted I will give a reference link to
it. Hope it can bring more ideas to MANET group.

Thanks,

 Tao

---

From: "Tao Lin" <[email-masked]>
Date: Tue, 3 Sep 2002 12:01:29 -0400

Richard,

Thanks,

 Tao

---

From: [email-masked]
Date: Tue, 03 Sep 2002 10:49:42 -0700

> it. Hope it can bring more ideas to MANET group.

Tao,

Are you computing MPRs similarly to the method I described
(similar to TBRPF)?  Except for the extension involving
source-independent MPRs, the idea has already appeared
in the TBRPF drafts for some time (via the selection of
"parents" and the use of this information for flooding), so I 
don't see how it can be published as a new idea, unless you have
some variation not included in the TBRPF draft.
If you have simulation results (e.g., comparing the performance
of TBRPF flooding to OLSR flooding) then I would be very interested
to see them, since I was planning to conduct my own simulations.

Regards,
Richard

---

From: [email-masked]
Date: Tue, 03 Sep 2002 10:49:42 -0700

Tao,

Regards,
Richard

---

From: "Philippe Jacquet" <[email-masked]>
Date: Wed, 4 Sep 2002 18:36:54 +0200

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

---

From: "Philippe Jacquet" <[email-masked]>
Date: Wed, 4 Sep 2002 18:36:54 +0200

Richard,

Philippe

---

From: [email-masked]
Date: Wed, 04 Sep 2002 12:06:16 -0700

> too large dominating sets (almost all nodes involved).

Philippe,

That is true for the way OLSR selects MPR nodes, because each
node selects its MPR neighbors independently from the other nodes.

That is one of the advantages of having MPRs select themselves.
Also, using node ID as a tie breaker reduces the number of 
selected MPRs, since only the lowest ID nodes become MPRs.  

I ran some simulations this morning to check this out.
For 100 nodes in a 500m x 500m area with a transmit radius of 250m
and a max speed of 20 m/s, I found that 35% of nodes are MPRs 
for at least one neighbor (i.e., are in the dominating set).

It may be possible to improve on this result by making better 
use of the 2-hop information to eliminate redundant nodes from
the dominating set.

Regards,
Richard

---

From: [email-masked]
Date: Wed, 04 Sep 2002 12:06:16 -0700

Philippe,

Regards,
Richard

---

From: "Amir Qayyum <"<[email-masked]>
Date: Thu, 5 Sep 2002 11:13:33 +0500

Richard,

I feel that with this approach we will end up making clusters, with
cluster heads selecting themselves, breaking the tie with the lowest
ID etc. The beauty of the current MPR scheme is that it spreads the
MPR functionality (load ?) over all the willing nodes of a network and
mostly a node is an MPR of not all but some of its neighbors. In this
way, no hierarchical structure is formed where certain nodes are
"designated" as MPRs.

(You may argue that forming a hierarchical structure would be better
but this is another discussion).

May not be exactly, but your idea may be followed in the current MPR
scheme. If a node "feels" that it "should" be the MPR of its neighbors,
it may increase its willingness to the highest value (currently 7).
That node will be selected as MPR by its neighbors with a very high
probability. This is similar to selecting itself as MPR for others
while leaving the "decision process" on the selecting node itself
(distributed control). Though currently the willingness is not a
dynamically changing parameter for a node, but it may be thought of.

Amir

Avaz Networks Inc.
www.avaznet.com

---

From: "Amir Qayyum <"<[email-masked]>
Date: Thu, 5 Sep 2002 11:13:33 +0500

Richard,

Amir

Avaz Networks Inc.
www.avaznet.com

---

From: Cedric Adjih <[email-masked]>
Date: Thu, 5 Sep 2002 17:51:35 +0200

Hello, Richard.

On Wednesday 04 September 2002 21:06, you wrote:
> > 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
>
> Philippe,
>

  Yes indeed, at least in the "proposed heuristic for selection of MPRs"
of the OLSR draft. One can also implement different algorithms,
including the new one with willingness of draft-06 (as noted by Amir),
yours, and others.

> selected MPRs, since only the lowest ID nodes become MPRs.

  Yes we may think so, but the simulation does not confirm it. It's
because on the other hand your algorithm tends to select more MPR per
node.
  Locally, the "min-id" algorithm tend to cover the 2 hop neighborhood by 
taking 1 hop neighbors as if at random ; while the OLSR proposed
heuristic is a greedy heuristic with good assymptotical performance
(about the number of MPRs per node), which is confirmed by simulation.

> for at least one neighbor (i.e., are in the dominating set).

  The problem with those parameters is that the range of one center node
can cover ~78% of the surface: thus 2 hop neighborhoods are really
limited, and MPRs are far less numerous.

  I ran a transliteration of your algorithm (which I hope is faithful):
"a node considers each of its 2-hop neighbors and it chooses as MPR
covering it, the 1-hop neighbor with the lowest id possible.", and
got the following results with static nodes in a square of width = 1.0:

With parameters close to yours, results are:
| #node | range | avg Neig. | %DS-min | %DS-heur | avg min | avg heur |
|   100 | 0.498 |    49.9   |  34.00% |  34.00%  |   5.57  |    2.88  |

But, with other parameters: 
| #node | range | avg Neig. | %DS-min | %DS-heur | avg min | avg heur |
|  1000 | 0.040 |     5.6   |  62.10% |  59.80%  |   2.64  |    2.25  |
|  1000 | 0.056 |    10.3   |  77.40% |  75.10%  |   5.41  |    4.06  |
|  1000 | 0.080 |    19.6   |  82.70% |  81.90%  |   8.93  |    5.46  |
|  1000 | 0.098 |    28.6   |  83.40% |  82.10%  |  11.20  |    6.17  |
|  1000 | 0.113 |    37.3   |  81.90% |  82.70%  |  13.04  |    6.66  |
|  1000 | 0.126 |    45.8   |  83.20% |  82.50%  |  14.38  |    7.01  |
|  1000 | 0.138 |    54.1   |  81.30% |  81.40%  |  15.55  |    7.22  |
|  1000 | 0.149 |    62.3   |  81.70% |  82.10%  |  16.84  |    7.50  |
|  1000 | 0.169 |    78.5   |  80.70% |  81.20%  |  18.22  |    7.76  |
|  1000 | 0.178 |    86.4   |  79.00% |  78.90%  |  18.81  |    7.84  |
|  1000 | 0.203 |   109.5   |  78.50% |  77.70%  |  20.17  |    8.05  |
|  1000 | 0.233 |   138.8   |  73.30% |  73.00%  |  20.88  |    8.12  |
|  1000 | 0.252 |   160.3   |  71.90% |  71.60%  |  21.86  |    8.00  |
|  1000 | 0.282 |   193.6   |  67.90% |  68.60%  |  21.88  |    7.79  |

Columns:
 - #node = number of nodes in the square
 - range 
 - avg Neig. = average number of neighbors of the nodes
 - %DS-min = percentage of nodes in the Dominating Set, taking
   any node which is MPR, using your "minimum id algorithm"
 - %DS-heur = percentage of nodes in the Dominating Set, taking
   any node which is MPR using the heuristic in the OLSR draft
 - avg min = average number of MPR of one node
             using the "minimum id algorithm"
 - avg heur = average number of MPR of one node
              using the OLSR draft algorithm

About 75% of nodes are MPR (of some other node) with both algorithms, 
that's why we rejected this dominating set algorithm.
The slower growth of the average number of MPR per node for the OLSR
heuristic is also illustrated.

Regards,
-- Cedric

---

From: Cedric Adjih <[email-masked]>
Date: Thu, 5 Sep 2002 17:51:35 +0200

Hello, Richard.

Columns:

Regards,
-- Cedric

---

From: Joe Macker <[email-masked]>
Date: Thu, 05 Sep 2002 13:15:49 -0400

>selected MPRs, since only the lowest ID nodes become MPRs. 

Richard:

You may be aware, but early cluster-based routing (Ephremides, etal) work in the 80s took a similar approach and broke ties that way.

Just to add to the discussion, I have been adding MPR preference election options to some experimental code where MPRs can provide some indications to help elect themselves (in this case it was still like OLSR in that these preferences where still indicated to the upstream node..who made the ultimate election). This can provide some hybrid capability during election, it can be as simple as a 1 bit indicator or more complicated.  My motivation was initially other than graph theory in that there are often other factors of interest (e.g., management issues, hybrid backbone infrastructure, local node energy, local node resources, predicted long term node stability)..

---

From: Joe Macker <[email-masked]>
Date: Thu, 05 Sep 2002 13:15:49 -0400

Richard:

---

From: "Philippe Jacquet" <[email-masked]>
Date: Fri, 6 Sep 2002 14:33:07 +0200

For pure data broadcast without last hop information we are studying the MPR
dominating set defined by
the following:

A node belongs to the MPR dominating set if it satisfies either one of the
following conditions:
(i) the node has the smallest ID in its neighborhood;
(ii) the node is MPR of the neighbor with the smallest ID.

Of course the principle of "smallest ID" can be turned into a more
sophisticated statement, for example "highest relay willingness then
smallest ID", or the "highest relay willingness then smallest MPR set size
then smallest ID".

We have a proof that the MPR dominating set is actually a connected
dominating set.

Contrary to the dominating sets recently discussed on the mailing list, the
MPR dominating set is an efficient dominating in the sense that it has a
significantly smaller size than the total size of the network. It is anyhow
outperformed by MPR flooding which needs last hop information. Cedric has
run simulations with 1,000 nodes and 10,000 nodes that compare the size of
the MPR dominating set with the number of retransmissions in a classical MPR
flooding.

*******simulation results*******
N = 1000
square field, border length 5.6 times radio range such that Avg_neighbor
size (for a node in the center) = 100

MPR Dominating Set, average size=97.2
MPR Flooding, average nb transmit= 78.4
***************
N=10000
square field, border length 15 times radio range such that Avg_neighbor size
(for a node in the center) = 140

MPR Dominating Set average size=850
MPR Flooding average nb transmit=450

Philippe

---

From: "Philippe Jacquet" <[email-masked]>
Date: Fri, 6 Sep 2002 14:33:07 +0200

Philippe

---

From: [email-masked]
Date: Mon, 09 Sep 2002 06:04:29 -0700

Hello Cedric,

Thank you for your helpful simulation results.
See my comments below.

> because on the other hand your algorithm tends to select more MPR per

Yes, I have always known that the "minimum ID" algorithm selects more 
MPRs per node.  On the other hand, this algorithm has some advantages 
(as already stated) due to the fact that MPRs select themselves,
which is the main reason why TBRPF uses this algorithm.

It is interesting that OLSR and TBRPF compute about the same
number of nodes that are MPRs for at least one neighbor
(as shown by your simulation results below).
I agree with you that since the dominating set consisting
of all MPRs is typically 70-80% of all nodes for both OLSR
and TBRPF, this is not a good algorithm for computing a dominating set.
(However, see below.)

> (about the number of MPRs per node), which is confirmed by simulation.

I see what you mean by randomness - random from the point of view of 
the MPR source, since the MPRs are not selected to maximize the 
number of 2-hop neighbors covered.  However, it is NOT random from 
a more global point of view, since using min ID results in a lot of 
commonality in the MPRs selected by nodes that are close together.
This commonality contributes significantly to the efficiency of TBRPF 
routing because of the way topology updates are disseminated.
More generally, it improves the efficiency of source-dependent flooding
when duplicate suppression is used, since a duplicate packet visiting
the *same* MPR is suppressed while a duplicate packet visiting a
*different* MPR is not.  Your performance measures do not measure this.
(You need to actually measure the number of retransmissions per
packet using source-dependent flooding and duplicate suppression.)

One drawback of the "minimum ID" algorithm (as mentioned by Amir)
is that the low ID nodes have most of the burden for relaying
packets.  Of course, this can be fixed by basing the selection
on a dynamically changing parameter (relay priority) in addition
to router ID.

I am very curious what the performance is if you apply the 
following two conditions given by Philippe to the "minimum ID" algorithm, 
and compare this to the same two conditions applied to the OLSR heuristic.
Can you run simulations for this and post the results?

>  (ii) the node is MPR of the neighbor with the smallest ID.

It should be noted that the size of the dominating set is
only one performance measure.  Other performance measures also
need to be considered, such as overhead and reliability (average
percentage of flooded packets delivered successfully to each node),
assuming a mobility model.  For example, if MPRs are not updated 
quickly enough following a link failure, this may affect the 
reliability.

Regards,
Richard

---

From: [email-masked]
Date: Mon, 09 Sep 2002 06:04:29 -0700

Hello Cedric,

Regards,
Richard

---

From: "David Simplot" <[email-masked]>
Date: Mon, 9 Sep 2002 09:49:19 +0200

Philippe,

In order to compare with existing solutions, do you have evaluation of
MPR dominating set size for (strongly connected) graph with smaller
average degree (d ~= 10 or 12)? (As a remark, if we have to deal with
very dense networks - average degree > 30 for instance -, perhaps it is
better to consider transmission power adjustment... but it is another
story...)

Regarding to dominating sets, I see why it is interesting to have
self-selecting forwarding neighbors as presented by Richard. But I do
not understand why it is better to have a source independent dominating
set. Nodes in this dominating set have to bear all the flooding cost for
each broadcast in the network (until topology modifications of course).
It is not clear that it is a benefit.

David.

--
David SIMPLOT, Ph.D
LIFL, Fundamental Computer Science Lab. Univ. Lille 1, France
http://www.lifl.fr/~simplot 

> -----Message d'origine-----
> De : [email-masked] [mailto:[email-masked]] De la 
> part de Philippe Jacquet
> Envoyé : vendredi 6 septembre 2002 14:33
> À : [email-masked]
> Cc : [email-masked]; [email-masked]
> Objet : Re: [manet] Flooding via MPRs 
> Importance : Haute
> 
>

---

From: "David Simplot" <[email-masked]>
Date: Mon, 9 Sep 2002 09:49:19 +0200

Philippe,

David.

---

From: Charlie Perkins <[email-masked]>
Date: Mon, 09 Sep 2002 11:08:17 -0700

Hello David,

The reason for having a source-independent set is that
a source-dependent set places one of the following two
requirements:
- tunneling for all data packets, or
- a way for a receiver to determine the
  identity of the node that had forwarded
  the data.

If these penalties are judged to be worth the gain
in performance, then we should allow source-dependent
processing.

Up until now, I thought it would be better to allow for
source independence, with smooth transition into
source-dependent processing when the gain is known
to exceed the cost.

Your point about spreading the cost is understood, but it
seems unclear whether or not source-dependent processing
is the best way to achieve the goal.

Regards,
Charlie P.

David Simplot wrote:

> > Envoyi : vendredi 6 septembre 2002 14:33
> > @ : [email-masked]

---

From: Charlie Perkins <[email-masked]>
Date: Mon, 09 Sep 2002 11:08:17 -0700

Hello David,

Regards,
Charlie P.

---

From: [email-masked]
Date: Mon, 09 Sep 2002 06:04:29 -0700

Hello Cedric,

Regards,
Richard

---

From: [email-masked]
Date: Mon, 09 Sep 2002 11:45:45 -0700

I previously wrote:

> ...using min ID results in a lot of 

I would like to present an example to make the above statement more clear,
and to show that the average number of MPRs assigned to each node is
NOT a good indicator of the number of retransmissions required
for source-dependent flooding with duplicate suppression.

In the following example, node 1 is the source with neighbors 2 and 3,
who both have neighbors 4 and 5, etc.

1--2--4--6--8--10
 \  \/ \/ \/ \/
  \ /\ /\ /\ /\
   3--5--7--9--11

Consider two cases of MPR selection:
In both cases, node 2 is the MPR for node 1. 

CASE 1:  Only the upper (even numbered) nodes are MPRs. 
E.g., node 4 is MPR for both nodes 2 and 3 (to reach nodes 6 and 7).

CASE 2: The upper nodes are MPRs for the upper nodes, 
while lower nodes are MPRs for the lower nodes.  
E.g., node 4 is MPR for node 2 while node 5 is MPR for node 3.

Case 1 is the min ID algorithm.
In both cases, the number of MPRs assigned to each node is the same.
So one might think that the number of retransmissions for a packet
flooded by node 1 is the same in both cases.
However, in Case 1, only the upper nodes (2,4,6,8) must retransmit 
the packet, whereas in Case 2, both the upper and lower nodes 
(2,3,4,5,6,7,8,9) must retransmit the packet.  (Since duplicate
detection is used, each node transmits the packet only once.)

Therefore, the average number of MPRs assigned to each node is
not a good indicator of efficiency, and one needs to run simulations 
that actually count the number of retransmissions.

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: [email-masked]
Date: Mon, 09 Sep 2002 11:45:45 -0700

1--2--4--6--8--10
 \  \/ \/ \/ \/
  \ /\ /\ /\ /\
   3--5--7--9--11

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: "Philippe Jacquet" <[email-masked]>
Date: Tue, 10 Sep 2002 19:21:12 +0200

It seems to me that in case 2 only upper nodes will retransmit since node 3
won't retransmit (and activate
the lower node MPR chain). Or maybe I misunderstood your example.

Ph.

---

From: "Philippe Jacquet" <[email-masked]>
Date: Tue, 10 Sep 2002 19:21:12 +0200

Ph.

---

From: "Charles E. Perkins" <[email-masked]>
Date: Tue, 10 Sep 2002 12:09:06 -0700

Hello folks,

Isn't this example an argument for picking
source-independent MPR sets?  Is it possible
to offer a characterization of those graphs
for which source-dependent MPR sets offer a
really important advantage?

Regards,
Charlie P.

---

From: "Charles E. Perkins" <[email-masked]>
Date: Tue, 10 Sep 2002 12:09:06 -0700

Hello folks,

Regards,
Charlie P.

---

From: [email-masked]
Date: Tue, 10 Sep 2002 12:17:28 -0700

Philippe,

> the lower node MPR chain). Or maybe I misunderstood your example.

You are right. (I was thinking of the way TBRPF flooding works, 
which does not require the previous hop of the flooded packet to
be an MPR source.)

The example can be modified as follows to illustrate my point.

     12
     /
 1--2--4--6--8--10
  \  \/ \/ \/ \/
   \ /\ /\ /\ /\
    3--5--7--9--11
     \ 
     13

In the modified example, nodes 2 and 3 are both MPRs for node 1 in 
both cases, and the outcome is similar to what I previously described
(except that node 3 must retransmit the packet in both cases).

Again, my point is that the average number of MPRs assigned to each 
node is not a good indicator of efficiency (e.g., commonality of the
MPRs also affects efficiency), so one needs to run simulations that 
actually count the number of retransmissions.
Also, simulations need to consider mobility and performance measures
such as reliability and overhead.  I plan to conduct such simulations
in the near future. 

Regards,
Richard

> > CASE 1 (min ID algorithm):  Only the upper (even numbered) nodes are MPRs.

> > CASE 1 (min ID algorithm):  Only the upper (even numbered) nodes are MPRs.

---

From: [email-masked]
Date: Tue, 10 Sep 2002 12:17:28 -0700

Philippe,

     12
     /
 1--2--4--6--8--10
  \  \/ \/ \/ \/
   \ /\ /\ /\ /\
    3--5--7--9--11
     \ 
     13

Regards,
Richard

---

From: "Philippe Jacquet" <[email-masked]>
Date: Wed, 11 Sep 2002 15:26:13 +0200

Hi, Charlie,

I think the simulation results you are refering to basically show that
taking all MPRs as a source independent MPR set is not a good idea (80%
nodes in the source independent MPR set). Taking MPRs the way we proposed in
a previous mail provides a more optimized source independent MPR set.
However, the simulations show that in a square field network the
source-dependent MPR set (the classical MPR flooding) still outperforms the
optimized source independent MPR set (that I called MPR dominating set) by a
significant margin (25-50%) but to the cost of carrying last hop
information. Maybe one step further could be to try to identify which
traffic could go via independent source MPR set (eg data) and which traffic
could go via source dependent MPR set (eg control traffic).

Regards,
Philippe

---

From: "Philippe Jacquet" <[email-masked]>
Date: Wed, 11 Sep 2002 15:26:13 +0200

Hi, Charlie,

Regards,
Philippe

---

From: "Charles E. Perkins" <[email-masked]>
Date: Wed, 11 Sep 2002 09:45:48 -0700

Hello Philippe,

I'm feeling very skeptical about this.  It seems to me
that if nodes agree between themselves about which ones
will be MPRs, then the directionality becomes secondary.
Source dependence is probably more important if the nodes
do not cooperate.  Cooperation could happen by publishing
one's list of identified MPRs, and then workiing with
neighbors to decommission any MPRs that are extraneous.

I believe that for any source-dependent MPR set, one can
find a source-independent MPR set serving the same topology
that generates the same or fewer retransmissions and has
the same or fewer nudes in the set.  Then the difficulty
would be to do this by a robust distributed algorithm.

If you happen to have a counterexample, that would save me
a lot of wasted effort trying to find a solution.
Simulating a particular selection algorithm doesn't provide
a counterexample, because then one could imagine that the
algorithm was not quite right.  I would like to see the
graph and the distinguished directional MPR set that cannot
be equalled by a nondirectional set.

Regards,
Charlie P.

---

From: "Charles E. Perkins" <[email-masked]>
Date: Wed, 11 Sep 2002 09:45:48 -0700

Hello Philippe,

Regards,
Charlie P.

---

From: [email-masked]
Date: Wed, 11 Sep 2002 11:06:38 -0700

Charlie,

I agree with what Philippe wrote today, but have
some additional thoughts.

Whether source-dependent MPRs offers a big advantage
over source-independent MPRs (also called a connected
dominating set - CDS) depends on whether there exists
an algorithm that selects a CDS that performs almost
as well as source-dependent MPRs.  Philippe proposed a clever 
CDS algorithm which performs much better than taking all MPRs,
but does not perform as well as classical source-dependent MPRs 
in simulations. But that doesn't mean there does not exist
an algorithm that performs better than classical MPRs
(as discussed below).

Also, there is a question of how much information nodes
should exchange to select the CDS, and whether the CDS
should be derived from source-dependent MPRs even if
source-dependent flooding is not used.  Here are three 
possible information sets that can be used for selecting
the CDS:

1. Each node uses only 2-hop neighbor information to decide
whether it is in the CDS.  (The "min-ID" algorithm.)

2. Each node uses 2-hop neighbor information plus knowledge
of which neighbors are in the CDS.  (Considered in the paper
by Wu and Li that I cited earlier.)

3. Each node uses 2-hop neighbor information plus knowledge
of the source-dependent MPRs selected by each neighbor. 
(Philippe's method.)

The third case uses the most information and therefore naturally 
allows a smaller CDS.  However, it also has drawbacks 
(e.g., more overhead, slower response to link failures).  

The 2 conditions of Philippe's method (regarding min ID) can
also be applied to the "min ID" algorithm I suggested earlier,
in which each node selects itself as a source-dependent MPR for 
a subset of its neighbors. I ran some preliminary simulations that 
show that using these two conditions reduces the size of the CDS by
roughly 60%, but is still significantly larger than Phlippe's method
using classical MPRs (which is expected since the latter method
uses more information).

HOWEVER, I also thought of another algorithm based only on 2-hop
information that performs significantly better than applying
the 2 conditions of Philippe to the "min ID" algorithm.
I want to test it further before describing it, but my point is
that there are better algorithms based only on 2-hop information,
and there might be better algorithms based on knowing the MPRs
selected by each neighbor (the 3rd information set above).

We should also consider the reliability consequences of using
source-dependent MPRs.  Requiring the previous hop of a packet to 
be an MPR source/selector can reduce reliability (since a flooded 
packet might not be heard from an MPR source but might be heard 
from another neighbor which is MPR for another node).

I don't think we should jump to any decision before
conducting detailed simulations with mobility and performance
measures such as reliability, delay, and overhead.

Regards,
Richard

---

From: [email-masked]
Date: Wed, 11 Sep 2002 11:06:38 -0700

Charlie,

Regards,
Richard

---

From: [email-masked]
Date: Wed, 11 Sep 2002 13:59:29 -0700

Charlie,

> one's list of identified MPRs, and then working with

I just want to point out that the best source-independent MPR set
(i.e., connected dominating set - CDS) is not necessarily a subset
of the source-dependent MPRs.  It might be possible to find
a smaller CDS if this restriction is removed.
(I.e., if you only want source-independent MPRs, then maybe the 
best approach is not to first compute source-dependent MPRs.)

> the same or fewer nodes in the set.  Then the difficulty

I agree that one can probably find such a source-independent MPR 
set (CDS), but I am not sure how much topology information must 
be exchanged to find it.  There is a lot of literature on finding 
small connected dominating sets, so maybe the right algorithm is 
already out there.

Regards,
Richard

---

From: [email-masked]
Date: Wed, 11 Sep 2002 13:59:29 -0700

Charlie,

Regards,
Richard

---

From: [email-masked]
Date: Wed, 11 Sep 2002 17:17:43 -0700

> would be to do this by a robust distributed algorithm.

Actually, it is easy to prove that you are correct.
Given a set of source-dependent MPRs, consider the subset
of MPRs that retransmit a flooded packet originating
from the minimum-ID node in the network.
It is easy to show that this set, plus the minimum-ID node,
is a connected dominating set.
(This is related to an OLSR-based flooding method that Thomas
Clausen mentioned several months ago.)

One way to compute this set, given the source-dependent MPRs, 
is to have all nodes proactively maintain the min-hop path,
with minimum-ID next hop for consistency, to the min-ID node u.
(This is much less overhead than maintaining paths to all nodes.)
(Although the min-ID node is not known in advance, each node computes
a min-hop path to the min-ID node that it *knows* about and advertises
its route to this node, so that eventually all nodes will compute
a min-hop path to the min-ID node.)

Then a node joins the dominating set if its next hop to u is an 
MPR source/selector for the node, or if the node is the min-ID node
in the network.

I am not sure you want to proactively maintain a min-hop
path to the min-ID node, but my main point is that you are
correct that such a connected dominating set does exist.

Now, suppose you don't want to compute the min-hop path to
the min-ID node in the network.  Then each node can compute
the min-hop path (with min-ID next hop) to the min-ID
node that is at most 2 hops away. Then a node joins the
dominating set if its next hop to this node is an
MPR source/selector for the node, or if the node has the 
minimum ID among all nodes within 2 hops of the node.

This might be an improvement over Philippe's method, which 
is similar but only looks 1 hop away instead of 2 hops away.

Regards,
Richard

---

From: [email-masked]
Date: Wed, 11 Sep 2002 17:17:43 -0700

Regards,
Richard

---

From: Guillaume Chelius <[email-masked]>
Date: Thu, 12 Sep 2002 10:49:51 +0200

Hello,

 > [...] but to the cost of carrying last hop
 > information. [...]

I'd just like to precise that, in IPv6, IP encapsulation is not 
necessary for last hop information. An "ad hoc flooding" hop-by-hop 
extension can be used. Its length would be around 20 bytes. The cost of 
adding this extension is even lowered by the fact that it could also be 
used to allow packet duplication detection as it is envisaged in the 
flooding draft proposition I've seen.

Regards,
Guillaume Chelius
------------------------------------
ARES Inria, CITI Insa Lyon
email: [email-masked]
tel: (+33) 472 436 421
-------------------------------------

---

From: Guillaume Chelius <[email-masked]>
Date: Thu, 12 Sep 2002 10:49:51 +0200

Hello,

Regards,
Guillaume Chelius