Subject: [manet] OLSR questions

From: [email-masked] (Ioannis C Avramopoulos)
Date: Mon, 11 Mar 2002 22:29:44 -0500 (EST)

Dear MANET Researchers,

I have some questions on OLSR and I would greatly appreciate it if any of
you took the time to answer. My questions are the following:

- What are the advantages of having a LOST_LINK type over having no such
type (version 4 for example did not have such link type)?

- Why should a node have multiple interfaces all running the OLSR protocol?

- Does the IEEE 802.11 specification make any provision for the scenario of
a node possessing multiple interfaces?

- Are MPRs elected per interface or per node? In other words is it possible
for a node that possesses multiple interfaces to elect a different MPR-set
for each of its interfaces? If MPRs are elected per interface what is the
point of doing so?

- It is stated in the draft that the MPR-set is constructed such that any
symmetric 2-hop interface is reached. Why is it desirable to reach any
symmetric 2-hop interface and not just any node possessing at least one
symmetric 2-hop interface?

- How does a node determine which interfaces should be used to (re)transmit
network-wide broadcast messages?

- It is stated that HELLO messages are transmitted on all interfaces. Isn't
this a waste of resources?

Thank you in advance.
Ioannis Avramopoulos

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

---

From: Laurent Viennot <[email-masked]>
Date: Tue, 12 Mar 2002 13:53:09 +0100

Dear Ioannis,

Comments bellow.

laurent

 > type (version 4 for example did not have such link type)?

It allows quicker update of one hop and especially two hop
neighborhood. A node announcing a neighbor loss allows its neighbors
to remove the link (without waiting for expiration) from their 2-hop
neighbor set.

Notice that the use of LOST_LINK was already mentioned in version 2 of
the draft and included in the implementation code, see:

http://hipercom.inria.fr/olsr/

 > - Why should a node have multiple interfaces all running the OLSR protocol?

It may have several radio interfaces with different radio channels, or
several radio interfaces with directional antennas (and possibly same
radio channel). It may even have a wire interface running OLSR if the
network is hybrid radio/wire.  Running OLSR on all of them allows to
connect everything in a straight forward manner.

 > a node possessing multiple interfaces?

No. It is in charge of the routing layer.

 > for each of its interfaces? If MPRs are elected per interface what is the

MPRs are elected per node (the basic rule is that any control packet
broadcasted by a node is emitted on each of its OLSR interfaces).  It
would be easy to allow MPR-set election per interface as you propose,
we could also envision to specify on which interfaces a MPR should
forward a broadcast packet but it would make the protocol more complex
for an optimization that is useful only when many nodes have multiple
interfaces. We felt keeping the protocol simple was more important.

 > symmetric 2-hop interface?

The formal rule is what you propose: any 2-hop neighbor must have an
interface covered by some MPR. But the proposed heuristic selects an
MPR set such that any 2-hop interface is covered.

This is again for the sake of simplicity versus complex optimization
not so useful. Notice that you have to be careful to avoid a chicken
and egg problem if your computation of MPRs depend from the reception
of MID messages when the forwarding of MID messages depends on MPR
election. (You need to receive a MID message from a 2-hop neighbor to
know all its interfaces.)
 
An optimized implementation could however modify the heuristic such
that at least one interface is covered for 2-hop neighbors for which
the node has received a recent MID message. It should still allow to
cover all 2-hop interfaces of other 2-hop neighbors to avoid the
chicken and egg problem.

 > network-wide broadcast messages?

As mentioned above, all interfaces retransmit.

 > this a waste of resources?

Hello messages are transmitted on all OLSR interfaces. It is necessary
to monitor connectivity on all interfaces. To allow 2-hop neighbor
knowledge, all the information has to be transmitted on all interfaces
from time to time. However, we could easily allow to send different
messages per interface (it would naturally fit with partial Hellos)
but again we preferred simplicity rather than a minor optimization.

 > Ioannis Avramopoulos

Thanks for you remarks, we are very interested in your feedback.

Laurent

---

From: Laurent Viennot <[email-masked]>
Date: Tue, 12 Mar 2002 13:53:09 +0100

Dear Ioannis,

Comments bellow.

laurent

 

Laurent

---

From: [email-masked]
Date: Wed, 13 Mar 2002 11:42:47 -0800

I urge everyone to read this message.
It presents perhaps the clearest argument so far that 
OLSR's lack of separation between neighbor sensing and
topology discovery results in increased complexity.

By lack of separation, I mean that OLSR HELLOs are used not 
only for neighbor sensing, but also for discovering paths to 
nodes that are 2 hops away (and also for selecting MPRs),
which to me is part of topology discovery.

Please see my comments below.

> Ioannis C Avramopoulos wrote (referring to OLSR):
>  > 

Yes, I think it is a waste of resources. In both TBRPF and OSPF, each HELLO
message is sent only on one interface, i.e., neighbor sensing is performed
separately on each interface.  

The reason OLSR sends HELLOs on all interfaces is because HELLOs 
are used not only for neighbor sensing, but also for discovering nodes
that are 2 hops away.  Since different interfaces might be used for the 
2 hops, HELLOs must be sent on all interfaces. 

> know all its interfaces.)

Laurent talks about simplicity, but here is one way in which OLSR is more
complex than TBRPF.  TBRPF does not have such a chicken-egg problem, i.e., 
parent selection does not depend on multiple interface information. 

Laurent may argue that TBRPF must still report all neighbors on all interfaces
in Topology Update messages, but not only are these sent less often than
HELLO_INTERVAL, it provides a clean separation between HELLOs (which are sent
on one interface) and Topology Updates (which are sent on all interfaces).

> but again we preferred simplicity rather than a minor optimization.

Laurent suggests the possibility of sending some HELLOs on all interfaces
and others on a single interface, to improve efficiency, but avoids this
approach for simplicity. Note that TBRPF achieves this efficiency
(by sending each HELLO on a single interface) as well as simplicity.

I am confident that anyone who reads and understands these arguments will
see that TBRPF is the better approach.  I only hope that enough people
will read and understand these arguments.

Since this message is about separation between neighbor sensing and
topology discovery, I would like to summarize other advantages that
TBRPF has in this regard:

1. If neighbor sensing is already provided in the link/mac layer (and I
know of at least two companies that do this), then TBRPF can be used
without HELLO messages, thus saving overhead.  

2. Since TBRPF neighbor sensing performs *only* neighbor sensing, it can 
be used with other routing protocols.  Conversely, other neighbor sensing
protocols can be used with TBRPF.

3. Because OSLR uses HELLOs to provide 2-hop information, each HELLO must
be sent on all interfaces (as discussed above).

Richard

---

From: [email-masked]
Date: Wed, 13 Mar 2002 11:42:47 -0800

Richard

---

From: Joe Macker <[email-masked]>
Date: Wed, 13 Mar 2002 16:56:20 -0500

>separately on each interface.  

Can you clarify your statement in relationship to OSPF..

from RFC2328, OSPFv2
"...9.5. Sending Hello packets Hello packets are sent out each functioning router interface. They are used to discover and maintain neighbor relationships...."

RFC2740, OSPF for IPv6, has "multiple interfaces to single link" modifications where one interface Hello is only used ... BUT that is for "multiple interfaces to a single link"

---

From: Joe Macker <[email-masked]>
Date: Wed, 13 Mar 2002 16:56:20 -0500

from RFC2328, OSPFv2

---

From: [email-masked]
Date: Wed, 13 Mar 2002 14:45:10 -0800

> "...9.5. Sending Hello packets Hello packets are sent out each functioning router i
nterface. They are used to discover and maintain neighbor relationships...."

Joe,

It is true that Hello packets are sent out each functioning router interface
in OSPF. The question is whether *each* Hello packet is sent out on *all* 
interfaces (as in OLSR), versus sending *different* Hellos on different 
interfaces (where the Hellos sent on a given interface describe only that 
interface, as in TBRPF).

RFC2328 is not very clear about this, but you can tell from the HELLO
packet format that a HELLO sent on a given interface contains only
neighbors for that interface.  For example, a HELLO contains only one
network mask, and the list of neighbors in a HELLO is described as follows,
where a "network" (equivalent to "link" in OSPF for IPv6) corresponds
to a single interface:

    Neighbor
       The Router IDs of each router from whom valid Hello packets have
       been seen recently on the network.  Recently means in the last
       RouterDeadInterval seconds.

Richard

> 
> RFC2740, OSPF for IPv6, has "multiple interfaces to single link" modifications wher
e one interface Hello is only used ... BUT that is for "multiple interfaces to a sing
le link"

---

From: [email-masked]
Date: Wed, 13 Mar 2002 14:45:10 -0800

Joe,

    Neighbor

Richard

---

From: "Philippe Jacquet" <[email-masked]>
Date: Thu, 14 Mar 2002 15:09:12 +0100

People interested can read this email but we don't feel this is THAT
important to urge everyone;-)

Dear Richard,

I think your points are not a big deal. The same number of hellos will be
sent on each interface anyhow.

In order to improve the tunability of partial hellos we have introduced the
possibility of refreshing neighborhood at a possibly smaller rate than hello
rate, i.e. using partial hellos (ref to REFRESH_PERIOD and HELLO_PERIOD
parameters). This should answer the core of your remark.

One last point, OLSR protocol architecture is based on 1-hop discovery +
2-hop discovery + topology discovery. Including 2-hop discovery in neighbor
discovery or in topology discovery is just a matter of semantics.  In OSPF,
DR selection belongs to hello's protocol and is based on 2-hop informations
directly collected from Hellos, I think to remember.

Philippe

---

From: "Philippe Jacquet" <[email-masked]>
Date: Thu, 14 Mar 2002 15:09:12 +0100

Dear Richard,

Philippe

---

From: [email-masked]
Date: Thu, 14 Mar 2002 08:40:29 -0800

TBRPF has other features that are shared by OSPF but not by OLSR
(in addition to sending each HELLO on a single interface). For example, 
neither TBRPF nor OSPF use HELLOs to discover 2-hop neighbors.
Also, both TBRPF and OSPF include only neighbor RIDs in HELLOs, 
not neighbor interfaces. This greatly improves efficiency for IPv6, 
since RIDs remain at 32 bits in OSPF for IPv6.

Richard

---

From: [email-masked]
Date: Thu, 14 Mar 2002 08:40:29 -0800

Richard

---

From: [email-masked]
Date: Thu, 14 Mar 2002 10:55:49 -0800

Philippe,

> sent on each interface anyhow.

But the HELLOs can be much larger, since they report all neighbors
on all interfaces.  For example, if a node has 5 interfaces, and
there are 100 neighbors on each interface, then 500 neighbors will have 
to be reported on each interface every HELLO_INTERVAL.  Also, this is 
likely to require more than one HELLO due to message size limitations.

> parameters). This should answer the core of your remark.

For example, you can set REFRESH_INTERVAL to be 5 seconds, the 
same as TC_INTERVAL, and partial/differential HELLOs can be sent more
frequently (like TBRPF). In this case, each node would need to report 
each neighbor every 5 seconds (like TBRPF).  It seems you have found
a way to incorporate TBRPF neighbor sensing without admitting it!

The OLSR draft does not mention any use for partial HELLOs
other than "due to message size limitations".  Do you expect the 
implementor to figure out that they should implement partial/differential
HELLOs similar to TBRPF?  I have a better solution.  :-)

Another disadvantage is that OLSR computes MPRs to cover all 2-hop
interfaces (which is redundant), whereas TBRPF computes parents based 
only on router IDs (equivalent to the "main address" in OLSR), 
not interfaces.

> discovery or in topology discovery is just a matter of semantics.  In OSPF,

It is not just a matter of semantics; modularity of (1-hop) neighbor 
discovery is very important, as I have already discussed.  

> directly collected from Hellos, I think to remember.

I don't see how this is possible, since DRs are elected only in broadcast
and NBMA networks, in which all nodes are (logically) 1 hop from each other.

You seem to be introducing/exploring lots of new ideas to improve OLSR.  
But simulation code is available only for version 03.
I hope that you will release ns2 code soon that includes the new 
features, and that also includes link-layer notification. This will 
allow the working group to evaluate the new, improved OLSR.

Richard

---

From: Joe Macker <[email-masked]>
Date: Thu, 14 Mar 2002 13:57:57 -0500

>since RIDs remain at 32 bits in OSPF for IPv6.

For historical accuracy, early versions of OLSR ( built on IMEP) used RIDs   ...perhaps before you were tracking things... .  but your comment is a good question for clarification to the OLSR authors as I would also encourage taking lessons learned from OSPF evolution, especially discussing the RID usage issue and IPv6 adaptation.

In <draft-ietf-manet-olsr-06.txt>, the originator address could be interpreted as an "old style" OSPF RID (I actually think that might have been the author's intent from a rereading, but i would refer to them to clarify)...I would recommend IPv6 considerations might also need to be updated to consider 32 bit RID use.

-joe

---

From: [email-masked]
Date: Thu, 14 Mar 2002 10:55:49 -0800

Philippe,

Richard

---

From: Joe Macker <[email-masked]>
Date: Thu, 14 Mar 2002 13:57:57 -0500

-joe

---

From: Laurent Viennot <[email-masked]>
Date: Fri, 15 Mar 2002 10:46:07 +0100

Richard,

The problem with advertising RIDs in Hello is that it is not
sufficient for detecting uni-directional links in some weird
situations with wireless connections.

Suppose for example the following scenario :

        ______________            _____________
       |              |     /--= |I1           |
       | Main ->   J1 |=<--/   = |I2   <- Main |
       |              |  \__-->= |I3           |
        --------------            -------------

There are two unidirectional links between I and J: one from interface
J1 to I3 and the other from interface I1 to J1.

If J1 anounces "I hear node I" then the node I thinks it has a
bi-directional link between I3 and J1 which is false.
To deal with such weird cases, J1 has to announce "I hear I1" as
proposed in MESH.

Such a situation may occur with directional antennas for example. With
IEEE 802.11, nodes I and J cannot communicate since ACKs for unicast
transmissions will always be lost.

I agree this could be optimized for IPv6 support.

laurent

---

From: [email-masked]
Date: Fri, 15 Mar 2002 11:28:17 +0100 (CET)

Dear Richard,

OLSR has been based on the same stable core algorithm and functionality
since the very first versions. Our recent changes have merely concirned
maturing the details and ensure that the protocol are flexible enough not
to lock implementations into optimizations for specific scenarios.

You say, that you find the neighbor sensing of OLSR to be mature and
flexible enough to support the mechanisms and optimizations of the TBRPF
neighbor sensing. I am glad that you think so, and I take that this is an
indication that OLSR has matured in a good way.

--thomas

-- 

-------------------------------------------
  Thomas Heide Clausen
  Civilingeniør i Datateknik (cand.polyt)
  M.Sc in Computer Engineering

  E-Mail: [email-masked]
  WWW:    http://www.cs.auc.dk/~voop
-------------------------------------------

---

From: Laurent Viennot <[email-masked]>
Date: Fri, 15 Mar 2002 10:46:07 +0100

Richard,

laurent

---

From: [email-masked]
Date: Fri, 15 Mar 2002 11:28:17 +0100 (CET)

Dear Richard,

--thomas

--

---

From: Joe Macker <[email-masked]>
Date: Fri, 15 Mar 2002 10:53:42 -0500

>Suppose for example the following scenario :

True, you lose the bidirectionality test for the separate interfaces and this is outlined in RFC 2328 also.

>transmissions will always be lost.

Right, if one wanted to support unidirectionality per interface, interface type is an issue.

>I agree this could be optimized for IPv6 support.

o.k., that seems important as the design progresses and was worth pointing out.

---

From: Joe Macker <[email-masked]>
Date: Fri, 15 Mar 2002 10:53:42 -0500

---

From: "Philippe Jacquet" <[email-masked]>
Date: Fri, 15 Mar 2002 16:47:02 +0100

Richard,

OSPF has good things and some other things that need adaptation to MANET.
Among the good things I think there are the sequence numbers that allow
obsolete informations to be removed from databases. Something worrying with
the absence of sequence numbers in TBRPF is that some obsolete information
could circulate around the network endlessly when there is mobility (not
covered by your proof).  Below is a short example of what I mean

u
|
|
v
|
|
w
|\
| \
i--j

Links i--w and j--w are alternatively alive: when link i--w is alive, link
j--w is down and vice-versa. To simplify let us assume that this switch
occur after each full update from w.

Link u--v definitively breaks when i--w is alive and let's assume that none
among i and j receive the differential update.

As you suggested, link u--v remains in TG(i) a few seconds - even if it is
not reported by w. Link u--v is thus updated in TG(j) by i, since p(u)=i at
that time for j. Then, i receives the update of w (and removes u--v) but
link i--w breaks and j--w comes up before any update from j.

Then j--w is active and link u--v is still reported by j. Now u--v is
updated in TG(i) since reported by j=p(u) for i. Again, suppose j receives
the update of w (and removes u--v) but link j--w breaks and i--w comes up
before any update from i.

The false information about the validity of the link of u--v thus endlessly
circulates between i and j.

I don't claim that this is an actual counter-example to your protocol
functionning because I don't master very well your optimizations (such as
the use of NON_TREE_PENALTY, and other penalties, etc), but I do believe
that without sequence numbers it will imply a non trivial proof of
correctness.

Philippe

---

From: "Philippe Jacquet" <[email-masked]>
Date: Fri, 15 Mar 2002 16:47:02 +0100

Richard,

u
|
|
v
|
|
w
|\
| \
i--j

Philippe

---

From: [email-masked]
Date: Sat, 16 Mar 2002 10:16:46 -0800

Philippe,

The example you gave assumes that links go up and down in 
synchrony with the transmission of topology update messages.
This would require an intelligent jammer who knows how the
protocol works and can tell when a node transmits a topology
update despite random jitter.

Under these assumptions, OLSR cannot be proven to be correct either,
as the example below shows.  If we wanted to resist such intelligent
jamming attacks (for either OLSR or TBRPF), other techniques can be 
used so that an adversary cannot observe when a node is transmitting 
topology updates.

Nonetheless, your example is interesting and shows that you understand
TBRPF very well.  I think that reading the correctness proof helps to 
understand TBRPF and shows that it is not so complex after all.  

The main reason for avoiding sequence numbers in TBRPF is to reduce
overhead.  Although sequence numbers are a very small percentage of 
overhead in OSPF, they would be a much larger percentage in TBRPF
because each node reports much less information. 
(However, it would not be hard to incorporate sequence numbers if 
they were found to be beneficial.)

You mentioned that mobility is not covered by my proof, which is not 
correct.  Mobility is allowed, but the proof assumes that the protocol 
is given sufficient time to converge following the last topology change.
(After all, we cannot expect all nodes to have the correct paths
immediately following a topology change.)

Richard

Example for OLSR:

x 
| \
|  \
v   w
|   |
|   |
i   j
|  /
| /
u

Links (v,i) and (w,j) are alternately alive: when link (v,i) is alive,
link (w,j) is down and vice versa.  Node v always generates a TC message 
reporting link (v,x) while (v,i) is down, and node w always generates
a TC message reporting link (w,x) while (w,j) is down.
As a result, node u never discovers a path to x, even though 
such a path always exists.

---

From: [email-masked]
Date: Sat, 16 Mar 2002 10:16:46 -0800

Philippe,

Richard

Example for OLSR:

x 
| \
|  \
v   w
|   |
|   |
i   j
|  /
| /
u

---

From: [email-masked]
Date: Sat, 16 Mar 2002 18:15:38 -0800

Laurent,

> Suppose for example the following scenario :

OK. If this is a realistic scenario, then including neighbor interface
addresses instead of RIDs in HELLOs makes sense.  Another approach
that allows more efficient operation in IPv6 is to include, for
each neighbor, a 32-bit RID *and* Interface ID (which can be 8 bits).
Perhaps the latter should be done *only* for IPv6.

Since OSPF includes only RIDs in HELLOs, and not neighbor interface 
addresses (or neighbor interface IDs), OSPF would also have to be 
modified to do this.

Including neighbor interface addresses instead of RIDs in HELLOs is just 
a simple substitution in TBRPF and does not affect parent selection,
since topology updates will still contain RIDs.  Each HELLO would still
be sent on a single interface.  

Richard

---

From: [email-masked]
Date: Sat, 16 Mar 2002 18:15:38 -0800

Laurent,

Richard