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

From: "Henderson, Thomas R" <[email-masked]>
Date: Mon, 20 Dec 2004 13:03:44 -0800

I have forwarded this to Tao Lin, who has agreed to participate
in our discussions on this topic.  

-----Original Message-----
From: Madhavi W. Chandra [mailto:[email-masked]]
Sent: Monday, December 20, 2004 10:21 AM
To: [email-masked]
Subject: [Ospf-wireless-design] Tao Lin paper

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

_______________________________________________
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:49:27 -0800

>in our discussions on this topic.
In that case, I will repeat my message so Tao can see it.
Tao, Please let me know if you agree or disagree.

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: Tao Lin <[email-masked]>
Date: Mon, 20 Dec 2004 16:28:48 -0500 (EST)

Hi All,

I didn't register in the OSPF-wireless-design email
list so I think I missed previous discussions.  Based
on Madhavi's email, I would like to share some of my
quick thought.

The willingness is the same in that paper and the MPR
sets are minimized since MPR_Coverage=1.

Finding a small CDS for a connected network is an NP
problem.  Therefore, people proposed approximation
algorithms to find small CDSs.  Generally, the more
complicated the algorithm is, the smaller size of CDS
it can get.  The MPR selection algorithm in OLSR
requires O(n), here n is the node degree.  And the
algorithm I proposed at least requires O(n^2).  So
this causes the difference.  If the number of
neighbors is a huge number, then the MPR algorithm can
run faster than O(n^2) algorithms.  However, the size
of a connected wireless network over one wireless
channel is limited.  So there is no big difference
between the algorithm in my paper and the MPR
algorithm introduced by OLSR.

Source dependent CDS algorithms usually need to
exchange some kind of decisions so that all
neighboring nodes will decide to be in the final CDS
or not.  For example, in the MPR algorithm proposed by
OLSR, nodes select MPR sets first and exchange their
MPR sets with neighbors.  After that, a node becomes a
CDS node if its MPRS is non-empty.  So, there is a
delay in this decision making procedure.  On the other
hand, those source independent CDS algorithms in which
nodes make decisions by themselves do not have this
delay.  Thus, when the network topology changes, a
routing protocol running over a source dependent
algorithm requires longer converge time than the one
running over a source independent algorithm.

Corret me if what I said is wrong and welcome more
discussions.

  Tao

 --- "Henderson, Thomas R"

______________________________________________________________________ 
Post your free ad now! http://personals.yahoo.ca

---

From: Tao Lin <[email-masked]>
Date: Mon, 20 Dec 2004 17:43:04 -0500 (EST)

Please see my in-line comments below.

> nodes that actually forward the LSA when forwarding

I would have to say that my original statement on MPR
selection based CDS is not accurate enough (and thanks
to OLSR group for pointing this out in my discussions
with them).  In fact, if a node receives a broadcast
message that is received from an MPR selector and is
the "first-seen" message, this node will do the
re-broadcast.  So I should say in the MPR-based CDS
algorithm, a node becomes a potential CDS if it has a
non-empty MPR selector set.  Whether or not it is a
real CDS depends on the order of broadcasts in the
wireless network.  This is what really happens in
OLSR-enabled network.

Still, the complexity of MPR-based algorithm is O(n)
and usually, a O(n^m) algorithm may generate smaller
size of CDSs (m>1).

Have a nice day!

 Tao

---

From: Richard Ogier <[email-masked]>
Date: Mon, 20 Dec 2004 19:17:05 -0800

Please see my comments below.

>this causes the difference.  If the number of
O(n^2) should be acceptable, where n is the number of neighbors,
since Dijkstra's algorithm already requires more than this.
However, I would not be happy with O(n^3) or higher.

>running over a source independent algorithm.
Right. I have been pointing this out as an advantage
of SI-CDS algorithms. (Faster recovery from link failures.)
However, this delay can also be avoided by
using self-selected MPRs, in which MPRs select
themselves based only on 2-hop neighbor information.
This is closely related to self-selected CDS nodes.
(The same algorithm can be used, except that the
router maintains the set of neighbors that depend
on the router to relay advertisements.)
This is also how TBRPF nodes decide which advertisements
to forward, i.e., TBRPF uses self-selected MPRs.

Richard

---

From: Acee Lindem <[email-masked]>
Date: Mon, 20 Dec 2004 23:19:14 -0500

See my comments inline.

> since Dijkstra's algorithm already requires more than this.

I'm not sure that this is a case where all N are created equal :^). When
you are computing the shortest path (as opposed to all non-looping
paths) the Dijkstra algorithm is O(m + nlog(n)) where m and n are
respectively the number of nodes and edges in the graph. Can
anyone point to code implementing the SI-CDS O(n^2) algorithm?

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

---

From: Richard Ogier <[email-masked]>
Date: Mon, 20 Dec 2004 22:02:58 -0800

Hi Acee,

> anyone point to code implementing the SI-CDS O(n^2) algorithm? 

Let's denote the degree by d, so that we are talking about O(d^2).
One possible CDS algorithm computes min-hop paths from the maximum
RID neighbor to each other neighbor, using only neighbors (or the router 
itself)
as intermediate nodes, giving preference to intermediate nodes with 
larger RIDs.
(Node degree can be used instead of RID.)  The router selects itself as a
CDS node if it belongs to one of the computed paths.
This can be done using BFS with running time O(d^2).
This is at most O(m) since d^2 < d * n = m.

Now, whether a CDS computed in this way is adequate is another
question.  I am sure simulations will be conducted to investigate this.
If a CDS algorithm that requires O(d^3) results in better performance,
the question will be whether O(d^3) is too much.

Richard

>>>> in our discussions on this topic. -----Original Message-----

---

From: "Madhavi W. Chandra" <[email-masked]>
Date: Tue, 21 Dec 2004 12:46:12 -0500

HI All,

> Corret me if what I said is wrong and welcome more

OK...this helps.  I was trying to understand why the CDS set was
showing to be so much smaller than the MPR set...but, I guess the
comparison was skewed.

In any case, as with most things, it's always a tradeoff...and we need
to investigate it more.  I'm not convinced that we should trade off
complexity for convergence, especially when we can mitigate the effect
of delayed convergence.  With overlapping relays, the backup relays
would go into action if the active overlapping relays do not transmit
or ACKs are not heard.  So, convergence is not as delayed...and
complexity is still linear.  It's not clear to me that the
CDS is significantly smaller than an overlapping set to warrant the
added complexity.  Actually, in many/most cases it seems that it would
be the same, especially with the pruning in the overlapping relay
algorithm or MPR algorithm. 

Anyway, simulations can help us see this more clearly. 

On another note, is it fair to say that a source-independent CDS
algorithm is actually more *dependent* on all of the nodes behaving
'ideally'...running the same selection algorithm, agreeing on their
IDs, etc....whereas a source-dependent overlapping relays/MPR
algorithm is more flexible?  

Regards,
Madhavi

> > than the

---

From: Tao Lin <[email-masked]>
Date: Tue, 21 Dec 2004 13:05:47 -0500 (EST)

Hi Madhavi,

Just one comment on the paragraph in your email (see
below). 

If a CDS algorithms only requires that all nodes are
broadcasting their neighbor lists to their neighbors,
we can 99.99% sure that all nodes work 'ideally'. 
This is because the information it requires is the
minimized information set (which is also included in
the information required for source dependent CDS
algorithms).  If this cannot be guaranteed, those
source dependent algorithms will also fail. 
Furthermore, even if somehow a hello message is lost,
neighboring nodes can recover from that lost at the
next hello time. 

Therefore, the source-independent algorithm using only
2-hop neighbor information can work at least as
'independently' as other source-dependent algorithms.

 Have a great day!

   Tao

---

From: Richard Ogier <[email-masked]>
Date: Tue, 21 Dec 2004 12:36:07 -0800

Madhavi W. Chandra wrote:

>complexity is still linear.
>
The complexity must be at least O(d^2)where d is the degree,
since it takes that much time just to look at each neighbor's
neighbors.  Some CDS algorithms also have this complexity.
But you are right that the MPR algorithm is linear in the
number of links, rather than nodes.

Also, the additional burden put on backup relays due to
the slower convergence might result in increased overhead
due to retransmissions.

But I agree that simulations will help us answer some
of these questions.

Richard

>It's not clear to me that the

---

From: "Joe Macker" <[email-masked]>
Date: Wed, 22 Dec 2004 11:29:38 -0500

On another note, is it fair to say that a source-independent CDS algorithm
is actually more *dependent* on all of the nodes behaving
'ideally'...running the same selection algorithm, agreeing on their IDs,
etc....whereas a source-dependent overlapping relays/MPR algorithm is more
flexible?  

Regards,
Madhavi

------------------------------
Madhavi:

There are many tradeoffs, I would agree you point out one.  For instance,
you can easily have difference election heuristics at different nodes
assuming you meet the basic requirements of a localized 2-hop CDS.

There is likely "no one size fits all" for every scenario, but I assume our
job is to converge on an approach.

There is alot to be said for "source dependent" approaches but this might
not be the goal for OSPF-MANET.

---

From: Abhay Roy <[email-masked]>
Date: Wed, 22 Dec 2004 12:18:35 -0800 (PST)

Hi Tao,

It's good to hear from you first hand on this topic. What may be 
useful to further this discussion is an example or two, where we 
can demostrate that the improved algorithm comes up with a smaller 
set. In my mind, it's still very fuzzy how this happens ;)

Also, since we are going to be doing simulations under Tom's 
GTNetS tool, we will need to include Tao's algorithm in there.

Regards,
-Roy-

---

From: "Joe Macker" <[email-masked]>
Date: Wed, 22 Dec 2004 17:18:15 -0500

Tao:

>From my reading of your paper, it counts the total MPR relay set (not what
set would be actually used in a single flodding instance).. This may have
been fair in context because your goal was developiong a source independent
variant, but it may confuse many readers since this is not the number of
relays used by a single flooding instance.  I verified some of this against
an analytical model we have of (total elected MPRs/independent of source)
vs. (average MPRs used per flooding instance) that we developed for one of
our flooding studies.

Am I off-base here?

-Joe

-----Original Message-----
From: [email-masked]
[mailto:[email-masked]] On Behalf Of Abhay Roy
Sent: Wednesday, December 22, 2004 3:19 PM
To: Tao Lin
Cc: [email-masked]
Subject: Re: FW: [Ospf-wireless-design] Tao Lin paper

Hi Tao,

It's good to hear from you first hand on this topic. What may be useful to
further this discussion is an example or two, where we can demostrate that
the improved algorithm comes up with a smaller set. In my mind, it's still
very fuzzy how this happens ;)

Also, since we are going to be doing simulations under Tom's GTNetS tool, we
will need to include Tao's algorithm in there.

Regards,
-Roy-

On 12/21/04-0500 at 1:05pm, Tao Lin writes:

> Hi Madhavi,
>
> Just one comment on the paragraph in your email (see below).
>
> If a CDS algorithms only requires that all nodes are broadcasting 
> their neighbor lists to their neighbors, we can 99.99% sure that all 
> nodes work 'ideally'.
> This is because the information it requires is the minimized 
> information set (which is also included in the information required 
> for source dependent CDS algorithms).  If this cannot be guaranteed, 
> those source dependent algorithms will also fail.
> Furthermore, even if somehow a hello message is lost, neighboring 
> nodes can recover from that lost at the next hello time.
>
> Therefore, the source-independent algorithm using only 2-hop neighbor 
> information can work at least as 'independently' as other 
> source-dependent algorithms.
>
> Have a great day!
>
>   Tao
>

---

From: Richard Ogier <[email-masked]>
Date: Thu, 23 Dec 2004 08:02:07 -0800

Hi Roy,

Here is an example where MPRs result in 3 times
as many transmissions as a SI-CDS.

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

Node 5 is the source.
The MPRs that forward LSAs from node 5 are {1, 6, 3, 2, 7, 4}.
The SI-CDS is {6, 7}, obtained using the algorithm below
which runs in O(d^2) time using a modified BFS algorithm,
where d is the number of neighbors.

The drawback of MPRs in this case is that they are required to provide
min-hop paths, whereas a SI-CDS does not have this requirement.
Of course, this is a special example, and simulations will tell us
what happens on average.

But even if the SI-CDS were the same size as the MPR set,
I would favor the SI-CDS because of several other advantages,
such as faster convergence. I plan to submit a draft next week that
presents a family of CDS algorithms, including the one below,
along with some simulation results.

Minimal CDS Algorithm

1. If node i has a larger value of (RtrPri, RID) than any of its
neighbors, then node i selects itself as a DR.
2. Else, let j be the neighbor of node i that has the largest
value of (RtrPri, RID).  If there exists a path (with one or more
hops, based on node i's 2-hop neighbor information) from node j to
each other neighbor of node i, using only intermediate nodes
that have a larger value of (RtrPri, RID) than node i,
then node i does not select itself as a DR; otherwise node i
selects itself as a DR.

Happy Holidays!
Richard

Abhay Roy wrote:

> useful to further this discussion is an example or two, where we can 
> demostrate that the improved algorithm comes up with a smaller set. In 
> my mind, it's still very fuzzy how this happens ;)
>
> Also, since we are going to be doing simulations under Tom's GTNetS 
> tool, we will need to include Tao's algorithm in there.
>
> Regards,
> -Roy-
>