Subject: [manet] OLSR implementation help

From: manet user <[email-masked]>
Date: Wed, 24 Mar 2004 13:18:08 -0800 (PST)

Hi,
 
I am trying to implement OLSR according to RFC 3626. I have couple of doubts during implementation. Any comment or suggestion will be helpful.
 
1) While populating 2 hop neighbor table, according to RFC, if "interface address" listed in Hello message does not belong to me, add it in 2 hop neighbor table. There is no check if that address belongs to 1 hop neighbor (i.e. listed in neighbor table). Is it correct or i am missing something ?
 
2) In terms of "associated neighbor/link tuples" concept, each neighbor set entry will point to the list of corresponding "list of link set entries" (under the name of associated link tuples) ?? 
Similarly, each link set entry will point to corresponding "neighbor set entry" (under assocaited neighbor set name) ?
 
This may be implementation detail, but just wanted to know if this will address the expected concept of associated nbr/link tuples.
 
3) In case of addition of a link to an existing neighbor, does neighborhood changes (leading to routing table recomputation)?
 
Your comments will be greatly appreciated. Thanks in advance.
 
-MS

Do you Yahoo!?
Yahoo! Finance Tax Center - File online. File on time.

---

From: Cedric Adjih <[email-masked]>
Date: Thu, 25 Mar 2004 09:14:46 +0100

Hello, 

On Wednesday 24 March 2004 22:18, manet user wrote:
> Hi,
>
> I am trying to implement OLSR according to RFC 3626. I have couple of
> doubts during implementation. Any comment or suggestion will be helpful.
>
> 1) While populating 2 hop neighbor table, according to RFC, if "interface
> address" listed in Hello message does not belong to me, add it in 2 hop
> neighbor table. There is no check if that address belongs to 1 hop neighbor
> (i.e. listed in neighbor table). Is it correct or i am missing something ?

This was intentional, although the reason is not laid out clearly:
the reason is that if one of your neighbors moves slightly, your link 
to it may break, but it would still likely be a two-hop neighbor.
The bet was that some two-hop neighbor relationships would still
be valid in that case, so 
instead of waiting for the HELLOs of all neighbors in order fill
the two-hop table with information about the moving previous-neighbor;
proactively, the two-hop neighbor sets are made to include one-hop
neighbor information.
Of course, you probably noted that, then, the requirement of the RFC
to ignore them, for instance in MPR calculation, would need to
be implemented explicitly. Extra work ;-)

> 2) In terms of "associated neighbor/link tuples" concept, each neighbor set
> entry will point to the list of corresponding "list of link set entries"
> (under the name of associated link tuples) ?? Similarly, each link set
> entry will point to corresponding "neighbor set entry" (under assocaited
> neighbor set name) ?
>
> This may be implementation detail, but just wanted to know if this will
> address the expected concept of associated nbr/link tuples.

Yes indeed, this is exactly the idea.

Ah but also, when implementing the association that way, the only
possible difficulty is handling main address change of a neighbor:
if you were to create a new neighbor tuple with the new main
address, the older link tuples might not point back to new neighbor
tuple, which may, or may not create troubles later, depending
on the implementation (been there, done that).

For inquirying minds, the case of main address change is not as
obscure as it may sounds, since it occurs when you are hearing a
neighbor from one of its interface which has not the main address
- that is, you should expect to met this case, as soon as you have
one node with several interfaces in your network.

> 3) In case of addition of a link to an existing neighbor, does neighborhood
> changes (leading to routing table recomputation)?

Yes, it's a good idea to consider that the neighborhood
has changed (and to recompute MPRs and routing table).
After all, that's what really happened :-)

Happy to see there is even more interest in OLSR implementation,
Regards,
-- Cedric

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

---

From: Cedric Adjih <[email-masked]>
Date: Thu, 25 Mar 2004 14:17:14 +0100

Hello Ignacy,

On Thursday 25 March 2004 12:38, Ignacy Gawedzki wrote:
> On Thu, Mar 25, 2004 at 09:14:46AM +0100, thus spake Cédric Adjih:
> This is wrong.  Unless a node changes its main address itself, you would
> never add a tuple in any 1-hop neighbor set with the main address not
> being the actual main address of the node.  A new link to a 1-hop
> neighbor is added upon reception of a HELLO message from that neighbor.
> But the HELLO message, as well as any other OLSR message, contains the
> originator address, which is *always* a node's main address.  As a side
> note, this information could be used to populate the Interface
> Association Set for 1-hop neighbors, in addition to MID messages.

This is perfectly true, it could be used. I forgot this important idea,
I stand corrected, thank you for clearing this :-)
But still, the problem, is twofolds:
- we didn't precise that this (using HELLO to populate Multiple
Interface Association Information Base) should be done in the RFC. A
RFC-compliant implementation might choose to not to do that.
- if you use HELLOs to populate the Multiple Interface  Association
Information Base, now the subtle issue is the following: what
expire time do you use? 
  . It would make sense to use the vtime of the HELLO.
  . But if the vtime of the MID are lesser, really what you'd
like to do is to take the vtime of the MID (because there might
a very good reason why the other node set the MID to a low value).

In practice using the vtime of the HELLO, is no problem, but this
can lead to the theoritical following scenario, where an "unoptimized"
implementation would have performed better, unless I am 
mistaken:
- a neighbor sends one HELLO with a big vtime (possible if it 
relies on the "LOST" status to remove links if necessary later)
- a multiple interface association entry is added with 
  expire time = big vtime of the HELLO + current time
- the neighbor changes its main address (for instance it was
performing IPv4/IPv6 autoconfiguration on a temporary main
address, in a scheme similar to the one proposed for AODV).
- the multiple interface association base is still polluted for
a *big* time, with bogus multiple interface association tuples
(which will be bogus competitors of the new ones, thus with
implementation dependant results :-( ).
-> Note while this may not be clever behavior from the part of the
neighbor, this is still RFC-compliant behavior.

What pyOLSR does for instance, on the other hand, is to
add the multiple interface association (MIA) tuple from the HELLO,
only for the duration, the processing of the HELLO, but as you noticed 
then, the MIA tuples won't be there for processing of other messages.
Maybe qolyester had already choosen to do the same :-)
Or you can play adding min(...)+flags in the MIAB.

>
> The only time where some confusion is possible between interface
> address and main address is when populating the 2-hop neighbor set.  For
> example, consider the current node A, a 1-hop neighbor B and a 2-hop
> neighbor C that has two interfaces with addresses C1 and C2, C1 being
> its main address.  Say that B hears C through interface C2, then a HELLO
> message from B contains an entry with address C2 and A has no way to
> know that in fact C1 and C2 belong to the same node.  There are two ways
> to deal with that:
>
>   1) Correct the 2-hop tuple upon reception of the MID message. I.e.
>   replace any (*, C2) with (*, C1).
>
>   2) Ignore the confusion until another HELLO message from B is
>   received.  Before updating the 2-hop neighbor set, check if the 2-hop
>   address resolves to another main address (because a MID message has
>   arrived in the meantime) and if so, remove explicitly the 2-hop tuple
>   (B, C2).  Then update the 2-hop neighbor set as usually: add (B, C1)
>   in the set with a new validity time.
>
> Solution 1 should be avoided, since a lot of computation is required for
> a pretty rare case.
>
> Solution 2 is in fact the preferred one,  since the false information in
> the 2-hop neighbor set would only bias MPR computation a bit until
> another HELLO is received after the reception of the MID message.

Good idea!

>
> Important remark: 2-hop addresses in the 2-hop tuples are main addresses
> of the nodes.  Consider now the following scenario:  A HELLO from B
> makes A put (B, C2) in its 2-hop neighbor set.  Then a MID message from
> C informs A that C has two interfaces C1 and C2, with C1 being the main
> address.  Then the arrival of a TC message at A triggers an MPR
> computation.  Since 2-hop addresses in 2-hop tuples are main addresses,
> there is no apparent reason to resolve these while doing MPR
> computation, thus A "doesn't see" C1 and C2 as the same 2-hop neighbor.
> This remains so until A receives a HELLO message from B and then removes
> (B, C2) from the 2-hop neighbor set and inserts (B, C1).  Since the
> 2-hop neighbor set has been changed, an MPR computation is triggered.
>
> I suppose that keeping 2-hop neighbor's interface addresses in 2-hop
> tuples instead of main addresses and performing main address resolution
> at MPR selection time would lead to more accurate behavior.  This would
> have a negative impact on performance though, since address resolution
> would not be "cached" into the 2-hop tuples.

Regards,
-- Cedric

---

From: Cedric Adjih <[email-masked]>
Date: Fri, 26 Mar 2004 01:11:10 +0100

On Thursday 25 March 2004 16:12, Ignacy Gawedzki wrote:
> [...snip..]
> Hmmm, right, the RFC says that a node SHOULD keep the same main address.
> =)
>
> I don't quite get the use of that.  If the MIA tuple is available only
> during the processing of the HELLO message, it won't be used.  

Well it will be used during the processing of the HELLO message
which is enough to have now a Neighbor Tuple with the proper
main address (along with MPR Selector Tuples, thus it should 
generate proper TCs...).

> It would 
> have been used during the processing of *another* HELLO message, where
> an interface's address belonging to the originator of the first HELLO
> would need resolution.

Which is the point :-) In the scenario I gave, the MIA tuple becomes
incorrect, and still stays for a long time. So I do not want to
use it. Of course then the two hop neighbor set is less correct.
Pick your poison :-)

Now I see that you could also try to detect that case and
explictly remove that bogus MIA tuple, but notice this is not done by
step 2 of "5.4 MID Message Processing".

Regards,
-- Cedric