Subject: OLSR and link layer notification

From: [email-masked]
Date: Wed, 12 Dec 2001 14:42:21 -0800

Philippe,

I now understand why, in the results you presented yesterday,
using MPRs did not make a significant difference in the number 
of packets dropped by OLSR due to no route.

To provide others with some background, in the example I presented in 
London (included at the end of this message), node i might have no route 
to node l for as long as 15 seconds until it learns about the new MPR 
selected by node k.  This behavior can occur more generally in sparse 
networks.  However, in dense networks, it is very likely that another 
path via another existing MPR will be found (which explains your results).
If the nodes move slowly (you used a maximum speed of 5 m/s), so that
another MPR does not fail within the 15-second period, this increases
the likelihood.  However, there is a good chance that the new path is not a 
min-hop path, and this suboptimal path would be used until a new MPR is 
selected by node k.  So, in highly mobile networks, this could result in 
an average path length that is significantly longer than for TBRPF.
(Perhaps simulations will show this.)

Also, it is certainly desirable for a routing protocol to work well
in both sparse and dense networks, not just dense networks.

Thomas,

Regarding the message I sent earlier today, it occured to me that
you might have or meant (or said) that you did not use link-layer
detection because the OLSR (not AODV) code you had did not provide it.
That would make more sense, since it is optional in OLSR.
However, it is simple to add and greatly improves the delivery fraction,
so I am still wondering why it is not included in your ns-2 code.

Richard

----------------

Example:

    Suppose that node i is sending data packets to node l over a
    3-hop path i -> j -> k -> l, where (as required by OLSR)
    node j is an MPR of node k. Also suppose that node i knows of
    no other MPR of node k, but there is an alternate 2-hop path 
    to node k: i -> j' -> k (where j' is not an MPR of k).

               j (MPR of k)
              / \
             /   \
            i     k -- l
             \   /
              \ /
               j' (not MPR of k)

    Now suppose that node i receives a link-layer indication that link 
    (i,j) has failed.  

    In OLSR, if there is no data being sent on link (j,i), it can
    take node j three HELLO intervals (6 sec) to detect that link (j,i)
    has failed (is no longer symmetric). It can then take another 2 seconds 
    for node k to learn that link (j,i) has failed (via a HELLO from j 
    reporting the LOST neighbor), after which node k will select node j' as 
    a new MPR to replace j.  It can then take another 2 seconds for node k 
    to report this to node j' (in its next HELLO), and another 5 seconds 
    (TC_INTERVAL) for node j' to receive and forward a TC message including 
    link (k,l).  Thus, after node i has detected the failure of link (i,j),
    it can take 6 + 2 + 2 + 5 = 15 seconds for node i to obtain
    current information from node j' about the new route
    i -> j' -> k -> l.  

    In TBRPF, node i will immediately report the failure of link (i,j),
    and within 1 second (MIN_UPDATE_INTERVAL), node j' will select
    itself as parent and start to report link (k,l).  Thus, we have
    1 second for TBRPF vs. 15 seconds for OLSR.

---

From: Laurent Viennot <[email-masked]>
Date: Wed, 19 Dec 2001 18:20:06 +0100

Dear Richard,

I try to answer precisely one of your mails (about OLSR and sparse
networks). You seem to ignore that OLSR may also benefit from link
layer notification. In your scenario, TBRPF detects the link breakage
within 0 sec. thanks to link layer notification when you count for
OLSR the worst case of link breakage detection through hellos (6
sec.).

Of course, if link layer notification is available control messages
may be triggered immediately in OLSR and the route is repaired
immediately (almost 0 sec.) and not 15 sec. 

I now understand why you got strange simulation results for OLSR.

Sincerely,

Laurent

-------------------------------------

Laurent Viennot                         
Projet Hipercom
INRIA Rocquencourt 
F-78153 Le Chesnay (France)

---

From: [email-masked]
Date: Wed, 19 Dec 2001 12:07:32 -0800

Laurent,

No, I am assuming in the example, and in the simulations, that
both OLSR and TBRPF are using link-layer notification.

In the example, both TBRPF and OLSR detect the link breakage
very quickly (say 0 sec).  However, in OLSR, node i cannot use link 
(j',k) immediately (see the example below) because OLSR allows only MPR 
links to be used beyond the first hop.  Before node i can use
link (j',k), node k must first select j' as an MPR, and node j'
must report the link (j',k) in a TC message.

The link-layer notification only informs node i that link (i,j) has failed,
but it still takes some time before node j knows that the reverse link 
(j,i) has failed.

Actually, now that the LOST state is reported in HELLOs, it is possible that 
this occurs more quickly, i.e., maybe it takes only 2 sec for node j to learn
that link (j,i) has failed (when node i sends its next HELLO).
This would reduce the total delay from 15 sec to 11 sec (2 + 2 + 2 + 5),
compared to 1 sec for TBRPF.

Please let me know if I made an error.

Richard

---

From: Laurent Viennot <[email-masked]>
Date: Thu, 20 Dec 2001 15:57:42 +0100

Dear Richard,

It was not clear in your mail that j does not get the link layer
notification. Anyway, your counts and your vision of the use of link
layer notification in OLSR are still contestable. However, the OLSR
draft may not be precise enough regarding the use of link layer
notification. Indeed, we have paid more attention to the use of link
hysteresis as link layer notification may not be available in a Manet.

Let me first clarify the use of link layer notification in OLSR since
you don't seem to use it as was envisioned. A link layer notification
of link breakage does not only inform that a neighbor is lost, but
also that data packets are being lost. In such a case OLSR encourages
to send immediately control packets for repairing the route without
waiting for the deadline. Recall that HELLO_INTERVAL for example is a
maximum delay before sending a new Hello message and not a minimum
bound as your analysis may let believe.

Your scenario includes two cases:
- 1 - i gets the link layer notification and not j
- 2 - j gets the link layer notification and not i

Regarding case 1, you can use the 2-hop neighborhood information to
allow to re-route packets. It is a nice feature of pro-active
protocols which allows a node to select valid next hops for reaching
2-hop neighbors. i can thus without any latency re-route through j'.

In case 2, upon receiving link layer notification, j immediately sends
a HELLO message reporting LOST_LINK status. Moreover, when k receives
the HELLO message and discovers a change in its MPR set, it
immediately sends a HELLO message reporting its new MPR set. Then j'
detects a change in its MPR selector set and sends immediately a new
TC.

This gives almost 0 sec. for OLSR.

However, a wise implementation of OLSR would certainly impose a
maximal rate r of control traffic per node. The response time of OLSR
would then be O(1/r) which should be much less than HELLO_INTERVAL.

Sincerely,

Laurent

---

From: [email-masked]
Date: Fri, 21 Dec 2001 09:11:16 -0800

Laurent,

See my comments below.

> notification. 
> Anyway, your counts and your vision of the use of link
> waiting for the deadline. 

I agree that it is possible to send a (full) HELLO sooner than the regular
interval if there is a link-layer notification, but the current OLSR
draft does not mention this, so naturally I assumed that HELLOs are
sent every HELLO_INTERVAL = 2 sec. (TBRPF actually sends a differential 
update immediately in this case, which is much smaller than a full HELLO;
this illustrates one advantage of using differential updates.)

> Recall that HELLO_INTERVAL for example is a

When I say "it can take 2 seconds" does this really sound like a minimum bound???
As I stated on the slide I presented in London, this is the worst-case delay 
assuming that each message is received successfully (for both OLSR and TBRPF).

> - 2 - j gets the link layer notification and not i

Actually, I was only considering the first case.
The second case occurs if node j is forwarding data packets to node i,
in which case node j is the one that needs to find a new route.

> 2-hop neighbors. i can thus without any latency re-route through j'.

OLSR as specified in the last several drafts does not use the 2-hop neighbor 
information for routing. As stated in Section 2.3 of the OLSR draft:

  "Routes are constructed through MPR-links and links with neighbors."

But let's suppose that OLSR were modified to allow this, and see what happens.
Let me modify the example a little by adding one node m:

               j (MPR of k)
              / \
             /   \
       m -- i     k -- l
             \   /
              \ /
               j' (not MPR of k)

Suppose that when link (i,j) fails, node i decides to immediately re-route 
packets to node l using the path i -> j' -> k -> l, where the link (j', k) 
is not yet an MPR link.  Node m will quickly learn that link (i,j) has failed,
but will NOT know about link (j', k) since it is not an MPR link.
Therefore, node m will not know a route to node l and therefore cannot
forward packets.  Thus, the problem still exists for node m.

This problem does not occur in TBRPF, since node i would immediately 
report that link (j',k) has been added to its source tree.

An interesting difference between OLSR and TBRPF is that in OLSR node i 
discovers the link (j',k) in it neighbor-sensing module, while in TBRPF 
node i discovers the link (j',k) in its topology-discovery module.  
This is because in TBRPF, the neighbor-sensing module does ONLY
neighbor sensing.  If OLSR also had this property, then it would
be possible to use either neighbor-sensing module with either protocol.
(However, modifying OLSR in this way would probably violate OLSR's
requirement for backward compatibility.)

> detects a change in its MPR selector set and sends immediately a new

As you imply below, it would generate a lot of overhead if a full HELLO 
or TC message were sent immediately whenever there is a change.
However, this would not be so bad if *differential* HELLOs and
topology update messages were used (as in TBRPF).

Richard

> would then be O(1/r) which should be much less than HELLO_INTERVAL.

This is certainly 

----------------

Example:

               j (MPR of k)
              / \
             /   \
            i     k -- l
             \   /
              \ /
               j' (not MPR of k)

    take node j one HELLO interval (2 sec) to learn that link (j,i)
    it can take 2 + 2 + 2 + 5 = 11 seconds for node i to obtain

    In TBRPF, node i will immediately report the failure of link (i,j),
    and within 1 second (MIN_UPDATE_INTERVAL), node j' will select
    itself as parent and start to report link (k,l).  Thus, we have
    1 second for TBRPF vs. 11 seconds for OLSR.

---

From: Laurent Viennot <[email-masked]>
Date: Fri, 21 Dec 2001 21:45:03 +0100

Dear Richard,

Comments to your comments.

 > this illustrates one advantage of using differential updates.)

It is specified in the draft that you must advertise a neighbor at
least once within any HELLO_INTERVAL period of time. This allows to
send Hellos at a higher rate and also to add some jitter if
necessary.  Moreover you can send partial Hellos as long as the above
condition is satisfied. For example, an additional HELLO sent in case
of link breakage would only contain information about the lost neighbor.

Partial HELLOs allow for example to refresh some neighbors at a higher
rate than some others.

 > forward packets.  Thus, the problem still exists for node m.

If you change the scenario as this, then j must select i as MPR (to
cover m). When detecting the link breakage, i will send an
additional Hello and also an additional TC (possibly in the same packet)
for invalidating the link (i,j) respectively locally and globally. 
Recall that MPR links are advertised to the whole network.
The additional TC will allow k to learn that link (i,j) has failed.
k then elects j' as MPR and j'.

With its full knowledge of 2 hop topology, OLSR has all means to make
fast re-routing.

Happy chrismas everybody,

laurent