Subject: Re: [Roll] Loop detection between sibling

From: JP Vasseur <[email-masked]>
Date: Fri, 7 Aug 2009 10:25:44 +0200

Hi,

On Jul 27, 2009, at 1:01 PM, Mukul Goyal wrote:

> JP,
>
> Please give more explanation. I did not understand at all.
>

You basically flag the packet when you forward to a sibling since you  
know that
there might be a risk of loops. If the flagged packet comes back you  
detect the
loop, simple, no overhead.

Cheers.

JP.

> Thanks
> Mukul
>
> ----- Original Message -----
> From: "JP Vasseur" <[email-masked]>
> To: "ROLL WG" <[email-masked]>
> Sent: Sunday, July 26, 2009 11:42:51 PM GMT -06:00 US/Canada Central
> Subject: [Roll] Loop detection between sibling
>
> Instead of explicit probing when sending to sibling another option  
> is to
> flag the Flow Label field with a pseudo random number to detect more
> than 2-hop loops. Simple and efficient with no extra overhead and new
> mechanisms.
>
> Cheers.
>
> JP.
> _______________________________________________
> Roll mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/roll

---

From: Henning Rogge <[email-masked]>
Date: Fri, 7 Aug 2009 10:35:04 +0200

> loop, simple, no overhead.
If every node has to do this you need a variable number of flags in each 
packet, which can be an MTU problem.

Henning Rogge

*************************************************
Diplom Informatiker Henning Rogge
Forschungsgesellschaft für
Angewandte Naturwissenschaften e. V. (FGAN) 
Neuenahrer Str. 20, 53343 Wachtberg, Germany
Tel.: 0049 (0)228 9435-961
Fax: 0049 (0)228 9435-685
E-Mail: [email-masked]
Web: www.fgan.de
************************************************
Sitz der Gesellschaft: Bonn
Registergericht: Amtsgericht Bonn VR 2530
Vorstand: Dr. rer. nat. Ralf Dornhaus (Vors.), Prof. Dr. Joachim Ender 
(Stellv.)

---

From: JP Vasseur <[email-masked]>
Date: Fri, 7 Aug 2009 11:09:26 +0200

> packet, which can be an MTU problem.

not is you use an existing field or even a new short one with a  
reasonably good
pseudo-random generator (there are many) (collisions probability will  
be extremely
low).

JP.

---

From: Henning Rogge <[email-masked]>
Date: Fri, 7 Aug 2009 12:42:04 +0200

> pseudo-random generator (there are many) (collisions probability will
I'm not sure I understand your idea...

let's assume we have a chain of 10 nodes which forward traffic towards a 
target. Each of the nodes have to mark the package in a unique way without 
erasing other marks to be able to detect a routing loop.

How do you plan to use a random number generator to compress the "mark" 
information down to a static field ?

Henning

---

From: JP Vasseur <[email-masked]>
Date: Fri, 7 Aug 2009 13:39:36 +0200

> erasing other marks to be able to detect a routing loop.

Just the first node sending the packet to the sibling does.

> information down to a static field ?

There is a plethora of algorithm to do this

---

From: Philip Levis <[email-masked]>
Date: Tue, 25 Aug 2009 10:02:15 -0700

> There is a plethora of algorithm to do this

Even you have a perfect randomization function, this requires O(n)  
bits, where n is the length of the route. In contrast, if you use a  
gradient, it requires O(log(n)) bits, with no dependence on random  
number generators for compression.

Furthermore, adding a tag requires keeping track of outstanding tags.  
If they are deterministic than you can have deterministic (repeated)  
failures; if they are randomized then you need to store state. The  
chance of collision in tag field is inversely proportional to its size.

This seems like design that looks good on paper but is impractical. Or  
am I missing something?

Phil

---

From: Henning Rogge <[email-masked]>
Date: Tue, 25 Aug 2009 19:51:04 +0200

> This seems like design that looks good on paper but is impractical. Or
Just adding a cyclic sequence number at the sender (or the gateway into the 
ROLL network) will do the job of well. Source IP and sequence number will be a 
unique pair unless the sequence number is not too short.

Of course each node still have to track lot's of IP/seqno pairs.
---------
What would do you think about just using doing duplicate detection link based 
instead of end2end based (at least for the RPL protocol). If each nodes add 
it's "depth" to the package on a link base, you can easily detect when a 
package goes "upwards" on the receiver side. Maybe it would be even better to 
add your own depth and the depth of the next hop (as you know it), would make 
it easier to detect errors in the acyclic graph.

Henning Rogge

---

From: Philip Levis <[email-masked]>
Date: Tue, 25 Aug 2009 11:02:06 -0700

> Of course each node still have to track lot's of IP/seqno pairs.

Right -- and this goes against the need for very limited state. If you  
assume very low utilization (queues are empty), then a node doesn't  
need to track lots of pairs. But if you have a burst of traffic it  
needs to maintain ~H*Q pairs, where H is number of hops in the loop  
and Q is the queue depth.

> it easier to detect errors in the acyclic graph.

I'm not sure I understand: are you describing something like CTP's  
datapath validation or a different mechanism?

Phil

---

From: Henning Rogge <[email-masked]>
Date: Tue, 25 Aug 2009 20:12:40 +0200

> and Q is the queue depth.
And the queue depth must be corresponding to the maximum livetime of a 
packet... not good for small routers.

> datapath validation or a different mechanism?
Don't know (can you give me a link to CTPs datapath validation?).

The idea is to have some integrated checking of the "increasing depth" while 
packets travel along the acyclic tree.

Henning

---

From: Philip Levis <[email-masked]>
Date: Tue, 25 Aug 2009 11:18:23 -0700

On Aug 25, 2009, at 11:12 AM, Henning Rogge wrote:

> packets travel along the acyclic tree

Section 3.1 of this paper: http://sing.stanford.edu/pubs/sing-09-01.pdf

Section 3.2 describes how CTP responds when it detects a potential loop.

Phil

---

From: Henning Rogge <[email-masked]>
Date: Tue, 25 Aug 2009 20:25:33 +0200

> Section 3.2 describes how CTP responds when it detects a potential loop.
Okay, that sounds like the same idea.

Henning

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Wed, 26 Aug 2009 11:04:01 +0200

Hi Phil and Henning,

We have 3 sorts of loops in RPL (that I know of ;) )

- DAG loops. A parent detaches and reattaches to a child that has missed the whole sequence and kept advertising the original DAG all this time. This happens when RA-DIOs are missed. The current draft avoids those loops using the sequence number. Without the seq number, the protection is limited (repeat DIOs during DAG hop timer), and temporary loops might occur. CTP/iRPF will not work (unless I miss something) if the loop involves at least 3 nodes. RPL eliminates the loop as soon as a DIO is received from a parent that appears to be going down, as the child has to detach from it immediately. The alternate of staying attached and following the parent in its fall would have counted to infinity and rapidly caused to detach too.

- DAO loops, that's when the parent has a route installed by a DAO to a child, but the child has cleaned up the state. This loop happens when a no-DAO was missed till a heartbeat cleans up all states. The current draft does not do a thing yet. RPF, CTP or split horizon apply well. IOW, drop a packet from a parent that you could have routed back to. The technique used for a packet from a sibling could apply too depending on how we do it.

- Sibling loops, and I thought this thread was specifically about those ones. Clearly iRPF cannot apply there since the hops do not make any fwd progress. Current draft limits those loops by split horizon -do not send back to the same sibling) and parent preference (always prefer parents vs. siblings). There are ideas floating around about:
  * aggressively dropping the TTL to limit the impact of the loops
  * randomizing the next hop to exit the loop if there's one
  * maintaining per packet states.
  * tunneling (a la CAPWAP) or source routing (path vector)

Maintaining states might work in very specific cases with very low traffic. It might be used as a hint if only some packets are sampled. But being L3 also means being generic and that technique hardly works on the general case so it can at best be an option.

Another aspect is that the hosts themselves should not be aware of the routing games. So I cannot see RPL asking hosts to sequence their packets.

Note that if there's a loop then a packet will exhaust TTL. There's little point doing anything until then. When that happen, the node that exhaust the TTL is within a loop for packets to that destination. Poisoning self as a next hop for that destination to the router that passed the packet should break the loop. This creates states per destinations as opposed to per packet.

We could also do more complex stuff like explore the path to that destination with a record route message that might trigger updates (trickle, DIOs, the whole 9 yards), and/or learn the path along the loop (source route). But is that necessary?

Pascal

>-----Original Message-----
>From: [email-masked] [mailto:[email-masked]] On Behalf Of Henning Rogge
>Sent: mardi 25 août 2009 20:13
>To: Philip Levis
>Cc: [email-masked]
>Subject: Re: [Roll] Loop detection between sibling
>
>And the queue depth must be corresponding to the maximum livetime of a packet... not good for small routers.
>
>The idea is to have some integrated checking of the "increasing depth" while packets travel along the acyclic
>tree.
>
>Henning