Subject: [Roll] Local repair

From: Ulrich Herberg <[email-masked]>
Date: Thu, 27 Jan 2011 10:20:18 +0100

Hi,

I have some questions about the local repair mechanism, in particular the
poisoning mechanism. How exactly would the mechanism work? As said in the
spec, there is a risk that a node's sub-DODAG does not receive the DIOs that
advertise a rank of INIFINITY, and thus the node may attach to its sub-DODAG
(and thus causing loops). Would it make sense for a node, that starts
poisoning, to wait for a certain time before parsing any DIOs? That could
increase the chance that any of the poisoned DIOs are received by the
children of the node. Not only could the poisoned DIOs be lost, it could
also happen that one child happens to submit its DIO first, even before the
poisoned DIO is sent.
Another question: When a node starts poisoning, will it reset somehow its
state, i.e. remove part of the neighbor set, start sending DIS messages,
etc? What happens if the node cannot attach to any parent (because there is
none) and does not create a floating DODAG? Will it send the poisoned DIOs
forever, or will it stop sending them after some number of DIOs?

A question about DIS messages. There is a difference how multicast and
unicast DIS messages are treated. In my Java-based implementation (used for
simulations), I cannot discern whether an incoming packet is multicast or
unicast (there are no raw sockets in Java, and no access to the IP header).
Of course, one may say that Java is not typically used for real
implementations (and I agree), but there might be other operating systems or
programming languages that make it difficult to access any information other
than the payload of a packet. Adding a single bit in the flags field would
help to easily decide whether an incoming DIS should reset the trickle timer
or not, without inspection of the IP header.

I still hope that my questions about the DAO/DAOACK mechanism (email from
January 12) would be answered by someone... :-)

Thanks
Ulrich

---

From: "KELLIL Mounir" <[email-masked]>
Date: Thu, 27 Jan 2011 17:30:10 +0100

Dear all,

In the last version of RPL draft, it is mentioned that an RPL node (a
router) forwards multicast data to the preferred parents and to the
children that have subscribed to the multicast group. Yet, it is not
clear whether this packet forwarding is achieved through IP tunnelling
(multicast-in-unicast) or using L2 (unicast) relaying? (I'd say the
second is right, but I'm not sure). And, the same question arises for
the case of the multicast source within the DODAG..

Best regards

Mounir

---

From: Philip Levis <[email-masked]>
Date: Thu, 27 Jan 2011 09:29:22 -0800

On Jan 27, 2011, at 1:20 AM, Ulrich Herberg wrote:

> Hi,
> 
> I have some questions about the local repair mechanism, in particular the poisoning mechanism. How exactly would the mechanism work? As said in the spec, there is a risk that a node's sub-DODAG does not receive the DIOs that advertise a rank of INIFINITY, and thus the node may attach to its sub-DODAG (and thus causing loops). Would it make sense for a node, that starts poisoning, to wait for a certain time before parsing any DIOs? That could increase the chance that any of the poisoned DIOs are received by the children of the node. Not only could the poisoned DIOs be lost, it could also happen that one child happens to submit its DIO first, even before the poisoned DIO is sent. 

Think of what the cost here: you're preventing a node from having a route in order to prevent the possible creation of a loop. But you can detect and repair a loop immediately, so what's the harm? I realize it's a bit weird to wrap your head around, but take a look at the CTP paper. If you have datapath validation, you don't need to poison (CTP doesn't). The only one danger is the count-to-infinity problem, but poisoning will only reduce, not solve, that problem due to the lossy nature of LLNs. That's why there the configuration option for max rank increase within an iteration.

> Another question: When a node starts poisoning, will it reset somehow its state, i.e. remove part of the neighbor set, start sending DIS messages, etc? What happens if the node cannot attach to any parent (because there is none) and does not create a floating DODAG? Will it send the poisoned DIOs forever, or will it stop sending them after some number of DIOs?

No. Removing part of your neighbor set could be a disastrously expensive decision (a node has spent a good deal of effort to build up link and route estimates). If the poisoning spreads correctly, then neighbors which are in the sub-DODAG and have no other routes available will advertise a rank of infinity. Note that this process may be very slow, as nodes in the sub-DODAG select each other as preferred parents and detect loops.

> A question about DIS messages. There is a difference how multicast and unicast DIS messages are treated. In my Java-based implementation (used for simulations), I cannot discern whether an incoming packet is multicast or unicast (there are no raw sockets in Java, and no access to the IP header). Of course, one may say that Java is not typically used for real implementations (and I agree), but there might be other operating systems or programming languages that make it difficult to access any information other than the payload of a packet. Adding a single bit in the flags field would help to easily decide whether an incoming DIS should reset the trickle timer or not, without inspection of the IP header.

I am not 100% up-to-date on the Java API, but can't you create two sockets, one for the global unicast address and one for the link-local multicast address? If Java doesn't give you raw sockets, how do you send DIS/DIO/etc. messages? Maybe you could sketch things out a bit better.

The argument for putting this bit in the DIS has come up before; the issue that arises is when an implementation sends a DIS with the bit configured to not reset the trickle timer, but does so to a multicast address. There will be DIO implosion as a result.

Phil

---

From: Ulrich Herberg <[email-masked]>
Date: Fri, 28 Jan 2011 14:28:39 +0100

Philip,

On Thu, Jan 27, 2011 at 6:29 PM, Philip Levis <[email-masked]> wrote:

> Think of what the cost here: you're preventing a node from having a route
> in order to prevent the possible creation of a loop. But you can detect and
> repair a loop immediately, so what's the harm?

I mostly agree, but there is some cost: First, the data packet would be
delayed if for each data packet loop freeness is tested, and possibly routes
repaired. That may be tolerable for some applications (collection of data
from sensors, such as temperature), but for other applications (home
automation: light switch) that may be less tolerable. Also, that would
require a mixture of data plane and control plane, since for each data
packet, the routing protocol has to be notified about the direction of the
packet, and verify the rank of the previous hop. If this datapath loop
correction is executed for each data packet, that process may also cost more
energy than having some more clever repair mechanism now and then.
So, while I agree that it may be easier to fix loops when data packets
arrive, I claim that it is not for "free". Maybe such a description of the
tradeoff could be added to the RPL spec?

> I realize it's a bit weird to wrap your head around, but take a look at the
> CTP paper.

Could you please send me a reference?

> If you have datapath validation, you don't need to poison (CTP doesn't).

If we don't need to poison, why is it specified in RPL then?

> The only one danger is the count-to-infinity problem, but poisoning will
> only reduce, not solve, that problem due to the lossy nature of LLNs. That's
> why there the configuration option for max rank increase within an
> iteration.
>

I agree.

> No. Removing part of your neighbor set could be a disastrously expensive
> decision (a node has spent a good deal of effort to build up link and route
> estimates).

Yes, I assumed that. I had spoken with a colleague who is working with the
ContikiRPL implementation. They are throwing away the information about all
parents, if a loop between a router and one of its parents is detected.
That's why I asked, but I assume it would be better to just throw away the
one parent where the loop has been detected.

> If the poisoning spreads correctly, then neighbors which are in the
> sub-DODAG and have no other routes available will advertise a rank of
> infinity. Note that this process may be very slow, as nodes in the sub-DODAG
> select each other as preferred parents and detect loops.
>

Yes.

> I am not 100% up-to-date on the Java API, but can't you create two sockets,
> one for the global unicast address and one for the link-local multicast
> address?

Yes, you are fully right... I was not thinking about that. Stupid me... ;-)

> If Java doesn't give you raw sockets, how do you send DIS/DIO/etc.
> messages? Maybe you could sketch things out a bit better.
>

I encapsulate the payload in UDP, since to my knowledge Java cannot send
ICMPv6 messages, unless some native code is used (e.g. using jpcap).

>
> The argument for putting this bit in the DIS has come up before; the issue
> that arises is when an implementation sends a DIS with the bit configured to
> not reset the trickle timer, but does so to a multicast address. There will
> be DIO implosion as a result.
>

Okay, I see.

Thanks
Ulrich

---

From: Philip Levis <[email-masked]>
Date: Fri, 28 Jan 2011 09:21:22 -0800

On Jan 28, 2011, at 5:28 AM, Ulrich Herberg wrote:

> > I have some questions about the local repair mechanism, in  
> particular the poisoning mechanism. How exactly would the mechanism  
> work? As said in the spec, there is a risk that a node's sub-DODAG  
> does not receive the DIOs that advertise a rank of INIFINITY, and  
> thus the node may attach to its sub-DODAG (and thus causing loops).  
> Would it make sense for a node, that starts poisoning, to wait for  
> a certain time before parsing any DIOs? That could increase the  
> chance that any of the poisoned DIOs are received by the children  
> of the node. Not only could the poisoned DIOs be lost, it could  
> also happen that one child happens to submit its DIO first, even  
> before the poisoned DIO is sent.
>
> Think of what the cost here: you're preventing a node from having a  
> route in order to prevent the possible creation of a loop. But you  
> can detect and repair a loop immediately, so what's the harm?
>
>
> I mostly agree, but there is some cost: First, the data packet  
> would be delayed if for each data packet loop freeness is tested,  
> and possibly routes repaired. That may be tolerable for some  
> applications (collection of data from sensors, such as  
> temperature), but for other applications (home automation: light  
> switch) that may be less tolerable. Also, that would require a  
> mixture of data plane and control plane, since for each data  
> packet, the routing protocol has to be notified about the direction  
> of the packet, and verify the rank of the previous hop. If this  
> datapath loop correction is executed for each data packet, that  
> process may also cost more energy than having some more clever  
> repair mechanism now and then.

Generally, no -- the cost of executing a few instructions is  
inconsequential in comparison to sending a packet (generally by > 6  
orders of magnitude). The energy costs of any not ridiculous (solve  
equations on each packet) packet processing are typically irrelevant  
in LLNs. We can start exploring really hypothetical points in the   
energy/capability space, but there's no evidence I've seen that such  
a point might ever appear, and it's probably useful to instead focus  
on more pressing concerns.

> So, while I agree that it may be easier to fix loops when data  
> packets arrive, I claim that it is not for "free". Maybe such a  
> description of the tradeoff could be added to the RPL spec?

It's been studied. Take a look at the CTP paper below.

> Could you please send me a reference?

http://sing.stanford.edu/gnawali/ctp/

and the paper:

http://sing.stanford.edu/gnawali/ctp/sensys09-ctp.pdf

>
> Yes, I assumed that. I had spoken with a colleague who is working  
> with the ContikiRPL implementation. They are throwing away the  
> information about all parents, if a loop between a router and one  
> of its parents is detected. That's why I asked, but I assume it  
> would be better to just throw away the one parent where the loop  
> has been detected.

This is a terrible idea -- you should instead just mark the parent's  
new Rank/Metrics etc. Whether or not the parent is evicted from the  
neighbor table should be independent of whether its change is due to  
a possible loop. E.g., it could be that the parent is currently  
looping through this node, but after loops are repaired this node  
will need to route through that neighbor (which chooses a different  
route).

Phil

---

From: Ulrich Herberg <[email-masked]>
Date: Fri, 28 Jan 2011 18:39:52 +0100

Phil,

> http://sing.stanford.edu/gnawali/ctp/sensys09-ctp.pdf

Thanks.

> This is a terrible idea -- you should instead just mark the parent's new
> Rank/Metrics etc. Whether or not the parent is evicted from the neighbor
> table should be independent of whether its change is due to a possible loop.
> E.g., it could be that the parent is currently looping through this node,
> but after loops are repaired this node will need to route through that
> neighbor (which chooses a different route).
>

I agree with you. What I wonder is whether this shouldn't be a bit explained
in the RPL spec (e.g. in sections like "Local Repair Mechanism" / "Poisoning
a sub-DODAG", that explain what an implementation should do, and what it
should not do) . The fact that implementations do the local repair wrongly,
may indicate that it is not always clear for implementers.

Ulrich