Subject: [Ospf-wireless-design] Tao Lin paper

From: "Madhavi W. Chandra" <[email-masked]>
Date: Mon, 20 Dec 2004 13:21:02 -0500

Hi All,

I'm hoping one of you can shed some light on the Tao Lin paper,
section III-D.

In this paper, I'm assuming that the Willingness parameter for
MPRs is the same, so it doesn't come into play in the MPR
computation.  And as the paper says, MPR_Coverage=1, so there are
no redundant relays in the set.

But, why is the 'modified' OLSR set so much smaller than the 
MPR set?   Put another way, which nodes would be included in the
MPR set that wouldn't be included in the modified-OLSR set, especially
since the MPR set does an overall pruning at the end of its 
selection algorithm.

Thanks!
-Madhavi

_______________________________________________
Ospf-wireless-design mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/ospf-wireless-design

---

From: Richard Ogier <[email-masked]>
Date: Mon, 20 Dec 2004 13:28:37 -0800

> Madhavi W. Chandra wrote:
>
>Hi All,
>

Madhavi,

 From Lin's description of OLSR:

"The RNS for a source
node is the MPR set of that node, combined with the MPR sets
of nodes in the MPR set of that source node, and so on until
this RNS covers all the nodes in the network."

It looks like Lin is assuming that a node always forwards
an LSA that is received from an MPR selector, even if the same LSA
was previously received from a non-MPR selector, as long as the
node has not previously *forwarded* the same LSA.
As has been discussed on the OSPF list, this is not very efficient.
A node only needs to forward an LSA when its *first* (non-duplicate)
reception is from an MPR selector (except in some rare cases that
can be handled by having non-MPR nodes retransmit the LSA when
an ACK is not heard). I think OLSR does it the efficient way.
Thus, Lin's RNS (relay node set) is probably larger than the set of
nodes that actually forward the LSA when forwarding is done efficiently.

Another possible advantage of Lin's CDS is that nodes with the
smallest degree are preferred (with tie broken by node ID). Since
all neighbors agree on this degree, there is more agreement among
neighbors regarding the selection of CDS nodes.  Whereas in OLSR
each node selects MPRs independently, so that the total number of
MPRs is likely to be larger than the total number of CDS nodes.

Richard

---

From: "Joe Macker" <[email-masked]>
Date: Tue, 21 Dec 2004 10:13:59 -0500

Richard:

Good comments..

Re. Your last thought.  In the NRL OLSR implementation we broke ties via
degree so there was some potential correlation in the election process, this
is an old trick from the clustering work of the 1980s, it didn't seem to be
that significant in the more scaled case (20-100 nodes) still a good idea in
general. See the MILCOM 04 paper, that looks at RNS sizes for a few
algorithms. We had hoped some simple election heuristics would signficantly
reduce the common shared CDS set.  Perhaps there is more work to do here.

-----Original Message-----
From: [email-masked]
[mailto:[email-masked]] On Behalf Of Richard
Ogier
Sent: Monday, December 20, 2004 4:29 PM
To: Madhavi W. Chandra
Cc: [email-masked]
Subject: Re: [Ospf-wireless-design] Tao Lin paper

>I'm hoping one of you can shed some light on the Tao Lin paper, section 
>III-D.
>
>In this paper, I'm assuming that the Willingness parameter for MPRs is 
>the same, so it doesn't come into play in the MPR computation.  And as 
>the paper says, MPR_Coverage=1, so there are no redundant relays in the 
>set.
>
>since the MPR set does an overall pruning at the end of its selection 
>algorithm.
>
>Thanks!
>-Madhavi
>

Madhavi,

"The RNS for a source
node is the MPR set of that node, combined with the MPR sets of nodes in the
MPR set of that source node, and so on until this RNS covers all the nodes
in the network."

It looks like Lin is assuming that a node always forwards an LSA that is
received from an MPR selector, even if the same LSA was previously received
from a non-MPR selector, as long as the node has not previously *forwarded*
the same LSA.
As has been discussed on the OSPF list, this is not very efficient.
A node only needs to forward an LSA when its *first* (non-duplicate)
reception is from an MPR selector (except in some rare cases that can be
handled by having non-MPR nodes retransmit the LSA when an ACK is not
heard). I think OLSR does it the efficient way.
Thus, Lin's RNS (relay node set) is probably larger than the set of nodes
that actually forward the LSA when forwarding is done efficiently.

Another possible advantage of Lin's CDS is that nodes with the smallest
degree are preferred (with tie broken by node ID). Since all neighbors agree
on this degree, there is more agreement among neighbors regarding the
selection of CDS nodes.  Whereas in OLSR each node selects MPRs
independently, so that the total number of MPRs is likely to be larger than
the total number of CDS nodes.

Richard