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

From: "Dearlove, Christopher \(UK\)" <[email-masked]>
Date: Mon, 16 Apr 2007 09:17:03 +0100

> So jitter introduced by
> draft-clausen-manet-jitter emphasizes the routing loop problem.

The purpose of such jitter is to reduce the probability of
collisions. Collisions cause packet loss which increase the
time to achieve a (quasi) steady state without looping. The
timescale of the latter is significantly greater than the
former, so if collisions are a problem it's worth taking
the downside of jitter in return for reduced collisions. If
collisions aren't a problem then it's not - as the document
says. There are however real systems in widespread use where
collisions are a problem, and jitter does help. There are
doubtless others where it doesn't. In the latter case, don't
use jitter.

********************************************************************
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-dt mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/manet-dt

---

From: Teco Boot <[email-masked]>
Date: Fri, 20 Apr 2007 21:58:58 +0200

[Oeps, I mailed before with wrong account and mail didn´t get ML, therefore
resent]

I am aware the routing loop occurs only during transition.
The question is: accept or work on a remedy.

Some thoughts, also mentioned before:
- Tuning timers could speed up convergence but cannot eliminate the loop. As
Justin mentioned, slow down reaction time could have better overall
performance at costs of increasing duration of the loop. 
- DPD will stop ping-pong forwarding, which helps saving spectrum usage,
battery life etc.
- RPF check could be hard to implement, as it requires information about the
forwarder, which is not available in the IP header. Layer-2 information
could be used, but then we are on track of designing a L2.5 MANET protocol.
- Incorporating layer-2 metrics could prevent the loop. In the example R1
would select the path via R2 and R3 to R5, as the metric via R4 is
increasing to a high value before the link breaks. This follows the "make
before brake concept". But at costs of increased routing update traffic.

IMHO leaving choices up to the implementator is not acceptable for a
standard track routing protocol.

Teco

> -----Original Message-----
> From: Justin Dean [mailto:[email-masked]]
> Sent: vrijdag 13 april 2007 22:03
> To: [email-masked]
> Subject: RE: [Manet-dt] Routing loops in proactive protocols, 
> including OLSR
> 
> 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:[email-masked]]
> Sent: Friday, April 13, 2007 7:58 AM
> To: [email-masked]
> 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 
> Teco