Subject: [manet] OLSR: RFC 3626 observations.

From: "Dearlove, Chris (UK)" <[email-masked]>
Date: Mon, 03 Nov 2003 15:38:07 +0000

I have a number of observations regarding OLSR, as
currently defined by RFC 3626. Whether any of them
are ever taken on board depends on future plans for
OLSR and the manet group. (I note that post-RFC work
has already started on AODV.)

First nit-packing comments on the RFC.

- There are some erroneous references to the advertised
  link set that should be the advertised neighbor set in
  sections 9.2 (page 44), 9.3 (page 45), 15 (page 59),
  15.1 (page 60) and 15.2 (page 60) - multiple times in
  some cases.

- In section 9.3 (page 45) it should be a change to the
  advertised neighbor set, rather than the MPR selector
  set that provokes an additional TC message. (Of course
  by default the two are the same, but in general it is
  the advertised neighbor set which matters.)

Second some specific comments on the protocol. (Note that
these have been informed by having implemented the latest
version of the protocol, as now defined by the RFC.) Note
that any suggested changes are backward compatible (and
could interwork with the current version of the protocol).

- When considering neighbourhood changes, there is the
  case of two nodes each using the same two interfaces.
  If the nodes are symmetrically connected using one
  interface, and then the second interface link becomes
  symmetric, or if symmetrically connected using both
  interfaces and then the connection through one interface
  becomes asymmetric or lost, this does not count as a
  neighbourhood change as defined in Section 8.5 (page 42);
  in fact these cases are explicitly excluded there. This is
  appropriate for MPR Set recalculation, but not for Routing
  Table recalculation, although Section 10 (page 47) does not
  make this distinction. To illustrate the problem consider
  an example starting with a symmetric link using the first
  interface, but not using the second interface, one node
  (the first node) will route to either interface of the
  other node (the second node) using the first interface.
  Now add the parallel link using the second interface. If
  this is not regarded as a neighbour appearance then there
  will be no Routing Table change, and the Routing Table
  will use the slightly odd, but acceptable, route to the
  second interface address on the second node via the
  first interface. Now break the link using the first
  interface. If this is not a neighbourhood loss then again
  there will be no Routing Table change - but there is an
  invalid entry in the Routing Table.

  This suggests that a modification to sections 8.5 and
  section 10 would be appropriate.

- Section 10 point 2 (page 48) refers to main address without
  specifying where to get it from. The RFC defines main address
  in section 5.5 (page 27) and hence that definition should be
  used. However in the indicated point this is a 1-hop neighbour,
  hence the main address is also available in the associated
  Neighbour Tuple. Since the 1-hop link must be established
  before a MID message is received and the Interface Association
  Set is updated, not using the Neighbour Tuple will result in
  an unnecessary delay. Since the procedure in Section 10 is
  an example, it is not necessary to change the RFC to use the
  Neighbour Set at this point. However there are other circumstances
  where this additional information may be used. The protocol could
  be modified to add that an entry may be added to the Interface
  Association Set whenever a HELLO message's originator address and
  source address differ (the former is the main address, the latter
  is the interface address).

- On receipt of a MID message and update of the Interface
  Association Set to add a new entry, one or more interface
  addresses which were previously assumed to be main addresses
  will no longer be main addresses. There may then be two hop
  tuples each containing an interface, rather than a main, address
  of a two hop neighbours. This has the drawbacks both of having
  entries which are incorrect, and not having entries which are
  wanted, and losing the opportunity to "merge" entries. The
  absence of any wanted entries lasts until the next appropriate
  HELLO message, the unwanted entries last until they expire.

  The protocol could be modified such that if a MID message
  is received (may qualify to only consider the case where it
  adds a new entry to the Interface Association Set) and if
  there are any two hop tuples with neighbour address contained
  in the MID message then replace all of these two hop tuples
  with a single two hop tuple using the MID message originator
  address. The new tuple's expiry time should be the latest of
  all the replace tuples expiry times.

Third some points where protocol behaviour is not ideal, but
changes might not be 100% compatible.

- In point 2 of section 13 (page 56) and point 2 of section
  14.3 (page 58) the parameter NEIGHB_HOLD_TIME is used to
  define new link time(s). However all other entries in the
  Link Set use the NEIGHB_HOLD_TIME of the other end of the
  link, as reported in the Vtime field of a HELLO message.
  It would be more appropriate to save this Vtime value (in
  the same way that the Htime field is already saved) and
  use that rather than NEIGHB_HOLD_TIME. Note that this
  avoids (among other issues) a tuple's expiry time ever
  becoming earlier as could otherwise occur.

- The protocol contains features (in section 9.5, page 46)
  to handle out of order TC messages. However these features
  are imperfect, they rely on the physically first/logically
  second TC message adding an entry to the Topology Set
  so that the physically second/logically first TC message
  may be recognised as such and discarded. However if the
  physically first/logically second TC message is empty
  then no such entry will be added and the physically
  second/logically first TC message will not be discarded.
  It will add entries to the Topology Set, which defeats
  the object of the empty TC message, at least partially.

  I can see one easy, but ugly, fix. This is that an
  empty TC message could add a "dummy" entry to the
  Topology Set. This could be one where both T_dest_addr
  and T_last_addr are set to the originator address,
  and T_seq is set to the ANSN. (T_time would be set as
  usual.) The Routing Table update process would have to
  be modified to disregard entries with T_last_addr equal
  to T_dest_addr. However a cleaner approach would be
  better.

  This is not just a hypothetical case, we have observed
  it in simulation, albeit in circumstances which would
  be better removed by another approach. (However removal
  of the observed circumstances still leaves the case able
  to happen in other ways.) In the observed case an
  intermediate node first received a TC message. After
  processing it, it decided to forward it. It therefore
  scheduled a retransmission at a time delayed by a random
  jitter duration. Shortly thereafter (before the
  retransmission) it received another TC message, from the
  same originating node. It did the same, but scheduling it
  before the other message (owing to using a smaller random
  number).

  There are at least two possible fixes to prevent this
  occurring, but neither is suggested by the RFC

  - Discard the earlier TC message when queuing the
    later TC message. (This would be limited to
    messages from the same originating node with
    earlier ANSN.) This contradicts section 9.4 (page 45)
    which mandates use of the standard forwarding algorithm
    for TC messages.

  - Ensure that queued messages order is maintained. This
    could apply to all messages, all messages from the
    same origin, or all messages of the same type from the
    same origin. Technically it violates section 3.5
    (page 21) by using a different random delay distribution
    than that suggested. If adopted section 3.5 should be
    modified to indicate this.

Fourth an observation, without a specific suggestion here
(although I have considered some specifics I omit here as
the principles are more important).

- OLSR timing for tuple expiry etc. is now defined using the
  Vtime (and for a HELLO message Htime) fields of a message,
  i.e. timing is based on the message originator's parameter
  settings. In addition to the case noted above, there are
  two other cases where timing is not taken from the originator
  and where significantly different values of parameters on
  different nodes could interact badly.

  - Jitter delay, based on parameter MAXJITTER. Note that it
    is possible, as currently defined, for a message to be
    delayed by more than the interval between messages.
    Ideally use of the message interval would be preferable
    to use of the hold time (Vtime) but typically these will
    be related.

  - Duplicate hold time. In this case basing hold time on Vtime
    would also provide greater extensibility to new message
    types that might be significantly more or less frequent.

********************************************************************
This email and any attachments are confidential to the intended
recipient and may also be privileged. If you are not the intended
recipient please delete it from your system and notify the sender.
You should not copy it or use it for any purpose nor disclose or
distribute its contents to any other person.
********************************************************************

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

---

From: Andreas Tønnesen <[email-masked]>
Date: Mon, 3 Nov 2003 18:32:49 +0100 (MET)

>   all the replace tuples expiry times.

A node must only use its main address as originator address in all
packages, so one would never register nodes with an address that is not
the main address of that node.
So if I didn't missunderstand you, the case you describe should not
occur.

Andreas Tønnesen
UniK University Graduation Center
University of Oslo
http://heim.ifi.uio.no/~andreto/uolsrd/index.cgi

---

From: Richard Ogier <[email-masked]>
Date: Mon, 03 Nov 2003 09:35:26 -0800

Chris,  

You made several good observations regarding OLSR, including the problem
regarding out of order TC messages.  Another fix to this problem is to 
do what
OSPF does, i.e., require each TC message (or LSA) to include the entire
neighbor set (which could be empty). An empty LSA also has a sequence 
number.
To limit the message size, an LSA can be divided into pieces as in OSPFv3,
each piece being identified by its Link State ID.

This also fixes another problem when TC messages are partial:
when the first TC message with a larger sequence number is received,
assuming this TC message is partial, then all of the old tuples with the
same originator are removed, and you are left with only a partial 
neighbor set
until the other partial TC messages with the same sequence number are 
received,
which may not happen for several seconds since flooding is not reliable.

Regards,
Richard

---

From: "Philippe Jacquet" <[email-masked]>
Date: Tue, 4 Nov 2003 17:08:40 +0100

Hello, Chris,

Below are my tentative comments and answers. Sorry for being late.

Best regards,
Philippe
----- Original Message -----
From: Dearlove, Chris (UK) <[email-masked]>
To: <[email-masked]>
Cc: <[email-masked]>; <[email-masked]>
Sent: Monday, November 03, 2003 4:38 PM
Subject: OLSR: RFC 3626 observations.

>   the advertised neighbor set which matters.)
In fact it seems that the connectivity is maintained when the MPR selector
set does not
change even if the advertized set changes; in this case ANSN is optionnal.
If a non MPR link breaks,
then there is always a path with MPR links with same length that is
available. This should be a way to
save some ANSN changes. Do you have a case where it should not work?

>   section 10 would be appropriate.

I agree that we have to recompute the routing table for neighbor nodes, when
the interface
set to this node changes. Notice that the neighbor set contains the
"associated link tuple", and a
change in this tuple is actually a change in the neighbor set and should
result in a routing table
recomputation. Maybe we should write down that any change in any routing
database results in a routing table
recomputation, although it looks over-redundant;-)
>   is the interface address).

The main address is mentioned in the originator address field in the header
of the HELLO. One should not need
to wait for an MID message to get it.

>   all the replace tuples expiry times.
Right, it looks more like an implementation issue, maybe
better to write it down.

>   becoming earlier as could otherwise occur.
You have a point, it should be Vtime of HELLO instead of NEIGH_HOLD_TIME.

>   to T_dest_addr. However a cleaner approach would be
Yes in this case, out of order TCs more or less result as if one of the TC
were lost. Next TCs should fix the misfit. Remembering the ANSN of
the empty TC seems to be a good implementation trick. Maybe one could
specify this in a cleaner way. For example to define T-Tuples as
(T_last_addr,T_ANSN, T_ANSN_Time,T_dest_tuple)
where T_dest_tuple is a set of (T_dest_addr, T_time) and empty sets are
permitted.
T-ANSN_time is refreshed at each TC reception from the same T_last
originator.

>     which mandates use of the standard forwarding algorithm

This is too much implementation oriented..
>     to use of the hold time (Vtime) but typically these will

But the interval between hellos should not be greater than the
neighb_hold_time.
>     types that might be significantly more or less frequent.
That is an interesting issue, one may store duplicate ID longer depending on
origin.
Notice that the duplicate hold time is a compromise on the speed  at which a
network
delivers all the copies of one packet and the time for a node to wrap around
packet
sequence number. Processing again a packet is not damageable but a packet
may
bounce several times if duplicate is not detected.