RE: [Manet-dt] Routing loops in proactive protocols, including OLSR

["Justin Dean" <[e-mail]>]

I would like to point out proactive protocols need not function in a
completely proactive manor.  NHDP specifically allows for timers to fire on
specific events, such as a link breaking.  In this case a link breaking
between r4 and r5 could cause a HELLO and a TC (in the case of OLSRv2) to be
sent from r4 and r5 informing the network as soon as possible of the no
longer available link.  In fact this behavior is already implimented in many
OLSR implimentations.  This would not eliminate all routing loops but would
provide better routing than just dropping looping packets.  A minimum wait
time variable is given in NHDP to prevent this type of reactive behavior
from causing more harm than good when many changes are taking place. 

Another method to reduce routing loops (although not eliminate them) would
be to forbid unicast packets to be sent to the previous hop.  This method
should prevent most routing loops caused by stale data from multiple
transmissions.  It would also be easier to implement: unicast packets
wouldn't require packet ids; kernels would not be required to keep track of
packets and packet ids once they were resent; previous hop information in
the form of mac addresses are already available to kernels.

Justin Dean


-----Original Message-----
From: Teco Boot [mailto:[e-mail]] 
Sent: Friday, April 13, 2007 7:58 AM
To: [e-mail]
Subject: [Manet-dt] Routing loops in proactive protocols, including OLSR

Once more on routing loops. I suggested DPD for unicast, for reducing impact
of a routing loop. I didn't receive any response on it. Perhaps the problem
is not known or impact is not fully understood. Please react on this problem
and suggest next steps.

Loops in unicast routing takes place when interface state changes. When an
interface goes down, the routing table is adjusted quickly for removing
entries with a next hop via this interface. Alternative routes could be used
quickly also. Other router routing tables are updated after routing protocol
activity; this could take milliseconds up to minutes, depending on protocol
and timer settings. During this convergence, routing loops can occur and
packet starvation is handled by TTL mechanism.

On wireless media, using TTL for starvation could have a high impact on
radio resources and spectrum utilization, and IMHO the behavior is
unacceptable. For this reason I suggested using DPD for unicast also.

Scenario with a routing loop problem in MANET topology:

+----+        +----+        +----+
| R1 |--------| R2 |--------| R3 |
+----+        +----+        +----+
   |                          | 
   |    =+=+= obstacle =+=+   |
   |                          |
+----+                      +----+
| R4 |----------------------| R5 |  R5 moves this way --->
+----+                      +----+

I assume a hop-count based metric (although I reject this approach due to
the WPF syndrome problem) and I focus on the link between R1 and R4, for
traffic from R4 to R5. R4 selects R5 as next-hop. Now the link between R4
and R5 breaks:

+----+        +----+        +----+
| R1 |--------| R2 |--------| R3 |
+----+        +----+        +----+
   |                           \ 
   |    =+=+= obstacle =+=+     \
   |                             \
+----+                         +----+
| R4 |                         | R5 |  R5 moves this way --->
+----+                         +----+

R4 and R5 detect the change due to the hello mechanism or L2 triggers. After
R4 is aware of the failure, it immediately adjusts its routing table. It
uses R1 as next hop for traffic to R5. However, R1 is still not aware of the
topology change and uses R4 as next hop for traffic towards R5. Now the
routing loop occurs:

     +----+        +----+        +----+
     | R1 |--------| R2 |--------| R3 |
     +----+        +----+        +----+
      ^ |                           \ 
Loop: | |    =+=+= obstacle =+=+     \
      | v                             \
     +----+                          +----+
     | R4 |                          | R5 |  R5 moved
     +----+                          +----+

The loop is solved as soon as R1 is aware of the new topology. Delay is
caused by routing protocol packet transfer, timers and processing time.
Protocol timers that slow down packet transfer or introduce jitter in SPF
calculation increase loop duration. So jitter introduced by
draft-clausen-manet-jitter emphasizes the routing loop problem.

Teco


_______________________________________________
Manet-dt mailing list
[e-mail]
https://www1.ietf.org/mailman/listinfo/manet-dt



_______________________________________________
Manet-dt mailing list
[e-mail]
https://www1.ietf.org/mailman/listinfo/manet-dt