Subject: [Roll] draft-ietf-roll-rpl, draft-ietf-roll-p2p-rpl : Selectively repairing downward routes

From: Vincent Brillault <[email-masked]>
Date: Tue, 3 May 2011 13:45:15 +0200

Dear ROLL WG,

I'm hoping that I did not miss an earlier discussion on the topic. Feel free to point me to earlier posts if I did.

The problem that this mail tackles is that of selectively repairing downward routes

Consider the following situation, in storing mode configuration :

      DODAGroot
          |
          |
        Node 1
          |
      ____|____
      |       |
    Node 2    |
      |     Node 3
      |      (/)
      |     (/)
       Node 4

Suppose that the OF function create the following situation :
- N4 uses N2 as its preferred parent
- N4 knows about N3 but does not consider it as a "DAO parent"

Whenever Node 2 increases its DTSN, N4 sends an unicast DAO.

Now if Node 2 suddently dies. Node 4 would not hear anymore DIOs from N2...

That looks perfectly fine, given the behavior of the trickle algorithm : Maybe N2 doesn't emit anything because the situation is consistent... The current specification says that a "node is responsible to emit DAO messages in order to provision the downward route". But in this situation, N4 doesn't know that the downward route is broken.

Suppose now that the DODAGroot wants to send a message to N4. As N2 is dead, N1 sends a DAOnopath back to the root.
At first sight, there are two solutions to obtain a new path to N4:

- The root can increase its DTSN, hoping that its descendants do the same. This is seems overkill as this may trigger all descendants to resend DAOs. Moreover, if Node 4 effectively gets the DIO with a DTSN increase, this latter does not come from its own DAO parent (it's dead), so N4 will ignore it.

- Otherwise, the root can increase its DODAGVersion, which rebuilds the whole DODAG. Node 4 hears the global repair from Node 3 and choose this parent. This seems very much overkill. 

So for now a broken downward route can only be repaired by global rebuild. 

In fact, there seems to be a lightweight solution to this problem: in the RPL p2p specification, there is a "Route Discovery Option", which allows a node to search for another Node.

Unfortunately, usage of this option is restricted : "RPLInstanceID MUST be a local value". Without this limitation, a DODAGroot could add such a "Route Discovery Option" in the DIO it sends. The resulting DIO is inconsistent with the previous one and will be broadcast within all the LLN.

The benefits of using this option for this purpose are:
- Use of the structure of the existing DODAG, without any calculations (not a global repair);
- Only the targeted DAO will get generated; 
- Allow on-demand routing for particular LLN with small memory footprint

Drawbacks may be:
- response with a DAO to a Route Discovery Option (instead of a DRO);
- the Metric Container of the Route DIscovery Option doesn't seem really usefull in that case.

Perhaps, the limitation of a single RDO per DIO should be lifted in this case.

Thank you in advance,

Vincent Brillault

---

From: Mukul Goyal <[email-masked]>
Date: Tue, 3 May 2011 07:10:28 -0500 (CDT)

Vincent

I think using the RDO in the manner you described would lead to as much overhead as incrementing the Version Number for the DAG.
Incrementing the Version Number seems like the right solution for this case. The P2P mechanism is not designed to repair existing DAGs.

Thanks
Mukul

----- Original Message -----
From: "Vincent Brillault" <[email-masked]>
To: [email-masked]
Sent: Tuesday, May 3, 2011 6:45:15 AM
Subject: [Roll] draft-ietf-roll-rpl, draft-ietf-roll-p2p-rpl : Selectively repairing downward routes

Dear ROLL WG,

      DODAGroot
          |
          |
        Node 1
          |
      ____|____
      |       |
    Node 2    |
      |     Node 3
      |      (/)
      |     (/)
       Node 4

Drawbacks may be:

Thank you in advance,

Vincent Brillault

_______________________________________________
Roll mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/roll

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Tue, 3 May 2011 14:52:25 +0200

Mukul:

I had in mind that the DIO with a target option would be useful for such
a repair. And I thought that this mechanism would come with P2P
additions.

Basically the idea is that when the root is missing a route to a
destination then it issues a DIO with a target that points to that
destination within the current version. 
In this case, node 4 would  see the DIO from node 3, and would trying
DAO / ack to node 2. Failing, it would fall back to node 3.

Do I miss something?

Pascal
http://www.xtranormal.com/watch/7011357/

> -----Original Message-----
> From: [email-masked] [mailto:[email-masked]] On Behalf
Of
> Mukul Goyal
> Sent: Tuesday, May 03, 2011 2:10 PM
> To: Vincent Brillault
> Cc: [email-masked]
> Subject: Re: [Roll] draft-ietf-roll-rpl, draft-ietf-roll-p2p-rpl :
Selectively
> repairing downward routes
> 
> Vincent
> 
> I think using the RDO in the manner you described would lead to as
much
> overhead as incrementing the Version Number for the DAG.
> Incrementing the Version Number seems like the right solution for this
case.
> The P2P mechanism is not designed to repair existing DAGs.
> 
> Thanks
> Mukul
> 
> Subject: [Roll] draft-ietf-roll-rpl, draft-ietf-roll-p2p-rpl :
Selectively repairing
> downward routes
> 
> Dear ROLL WG,
> 
> I'm hoping that I did not miss an earlier discussion on the topic.
Feel free to
> point me to earlier posts if I did.
> 
> The problem that this mail tackles is that of selectively repairing
downward
> routes
> That looks perfectly fine, given the behavior of the trickle algorithm
: Maybe
> N2 doesn't emit anything because the situation is consistent... The
current
> specification says that a "node is responsible to emit DAO messages in
order
> to provision the downward route". But in this situation, N4 doesn't
know that
> the downward route is broken.
> 
> Suppose now that the DODAGroot wants to send a message to N4. As N2 is
> dead, N1 sends a DAOnopath back to the root.
> - The root can increase its DTSN, hoping that its descendants do the
same.
> This is seems overkill as this may trigger all descendants to resend
DAOs.
> Moreover, if Node 4 effectively gets the DIO with a DTSN increase,
this latter
> does not come from its own DAO parent (it's dead), so N4 will ignore
it.
> 
> - Otherwise, the root can increase its DODAGVersion, which rebuilds
the
> whole DODAG. Node 4 hears the global repair from Node 3 and choose
this
> parent. This seems very much overkill.
> 
> In fact, there seems to be a lightweight solution to this problem: in
the RPL
> p2p specification, there is a "Route Discovery Option", which allows a
node to
> search for another Node.
> 
> Unfortunately, usage of this option is restricted : "RPLInstanceID
MUST be a
> local value". Without this limitation, a DODAGroot could add such a
"Route
> Discovery Option" in the DIO it sends. The resulting DIO is
inconsistent with
> the previous one and will be broadcast within all the LLN.
> 
> - Use of the structure of the existing DODAG, without any calculations
(not a
> global repair);
> - the Metric Container of the Route DIscovery Option doesn't seem
really
> usefull in that case.

---

From: Mukul Goyal <[email-masked]>
Date: Tue, 3 May 2011 08:56:19 -0500 (CDT)

Pascal

Route Discovery option is not meant for the purpose you described. It is meant for discovery of new source/HbH routes. We will need a new option if you want to repair an existing DAG in the manner you specified.

Thanks
Mukul

----- Original Message -----
From: "Pascal Thubert (pthubert)" <[email-masked]>
To: "Mukul Goyal" <[email-masked]>, "Vincent Brillault" <[email-masked]>
Cc: [email-masked]
Sent: Tuesday, May 3, 2011 7:52:25 AM
Subject: RE: [Roll] draft-ietf-roll-rpl, draft-ietf-roll-p2p-rpl : Selectively repairing downward routes

Mukul:

Do I miss something?

Pascal

Of
Selectively
much
case.
Selectively repairing
Feel free to
downward
: Maybe
current
order
know that
same.
DAOs.
this latter
it.
the
this
the RPL
node to
MUST be a
"Route
inconsistent with
(not a
really

---

From: Emmanuel Baccelli <[email-masked]>
Date: Tue, 3 May 2011 16:06:25 +0200

Hi Pascal,
I agree with Mukul. We do not want to overload the P2P spec with too many
options. On the other hand, maybe a side spec could provide what you
propose?
regards
Emmanuel

On Tue, May 3, 2011 at 3:56 PM, Mukul Goyal <[email-masked]> wrote:

> Pascal
>
> Route Discovery option is not meant for the purpose you described. It is
> meant for discovery of new source/HbH routes. We will need a new option if
> you want to repair an existing DAG in the manner you specified.
>
> Thanks
> Mukul
>
>

---

From: "Popa, Daniel" <[email-masked]>
Date: Tue, 3 May 2011 09:00:17 -0700

Hi Vincent, 

You bring up an interesting example. I think that we can have a third option: 

In LLNs, you should rely on the MAC layer also to provide a way to detect (one-hop) neighborhood connectivity. By doing so, the Node 4 can detect that the link to Node 2 is "dead" and decide to switch to the next available uplink, the link to Node 3; (by analogy, think at this as some handover mechanism, because you should take this action when link quality goes down). Therefore, Node 4 can decide to use Node 3 as parent - instead of Node 2 - and send a DAO to the root, indicating the new downward path to reach it. 

What do you think?

All the best, 
Daniel

> From: [email-masked] [mailto:[email-masked]] On Behalf Of
> Vincent Brillault
> Sent: Tuesday, May 03, 2011 1:45 PM
> To: [email-masked]
> Selectively repairing downward routes
> 
> Dear ROLL WG,
> 
> I'm hoping that I did not miss an earlier discussion on the topic. Feel
> free to point me to earlier posts if I did.
> 
> : Maybe N2 doesn't emit anything because the situation is consistent...
> The current specification says that a "node is responsible to emit DAO
> messages in order to provision the downward route". But in this
> situation, N4 doesn't know that the downward route is broken.
> 
> same. This is seems overkill as this may trigger all descendants to
> resend DAOs. Moreover, if Node 4 effectively gets the DIO with a DTSN
> increase, this latter does not come from its own DAO parent (it's
> dead), so N4 will ignore it.
> 
> - Otherwise, the root can increase its DODAGVersion, which rebuilds the
> whole DODAG. Node 4 hears the global repair from Node 3 and choose this
> the RPL p2p specification, there is a "Route Discovery Option", which
> allows a node to search for another Node.
> 
> Unfortunately, usage of this option is restricted : "RPLInstanceID MUST
> be a local value". Without this limitation, a DODAGroot could add such
> a "Route Discovery Option" in the DIO it sends. The resulting DIO is
> inconsistent with the previous one and will be broadcast within all the
> LLN.
> 
> (not a global repair);
> really usefull in that case.
>

---

From: C Chauvenet <[email-masked]>
Date: Wed, 4 May 2011 00:47:28 -0700

Hi all, 

I agree that vincent brings an interesting point.

As Daniel pointed out, this is related to Neighbor Unreachability Detection (NUD).
Even if RPL doesn't specify a strict mechanism to maintain the connectivity with (at least) a parent,  a node should attach itself to an alternative parent if it detects that its best parent is no more reachable.
So in your case, N4 should detect that N2 died and select N3 as its new best parent and send a DAO to N3.
N4 can detect N2 loss by periodic metric updating (for example, due to many fails to reach N2,  the ETX on the link from N4 to N2 will increase to a value that will overstep a threshold to trigger a parent switching).

Best,
Cédric.

-----Message d'origine-----
De : [email-masked] [mailto:[email-masked]] De la part de Popa, Daniel
Envoyé : mardi 3 mai 2011 18:00
À : Vincent Brillault; [email-masked]
Objet : Re: [Roll] draft-ietf-roll-rpl, draft-ietf-roll-p2p-rpl : Selectively repairing downward routes

Hi Vincent, 

What do you think?

All the best,
Daniel

> Of Vincent Brillault
> Feel free to point me to earlier posts if I did.
> 
> the whole DODAG. Node 4 hears the global repair from Node 3 and choose 
> this parent. This seems very much overkill.
> 
> MUST be a local value". Without this limitation, a DODAGroot could add 
> such a "Route Discovery Option" in the DIO it sends. The resulting DIO 
> is inconsistent with the previous one and will be broadcast within all 
> the LLN.
>

---

From: Vincent Brillault <[email-masked]>
Date: Thu, 5 May 2011 11:06:24 +0200

Hi Daniel, Hi Cédric,

As both of you pointed out, this example is related to NUD, if there is such information (from ACKs or beacons) from the MAC layer, then the problem is much simpler.
Still, it seems that RPL should be able to repair the downward routes by itself, in the case the NUD done by the MAC layer is not efficient.

Otherwise, let's consider another example.
Let's call the Nodes M[1-9]* so that we won't mix up anything.

Consider a simple network, stabilized :
root -- M1 -- M2 -- M3 -- M4 -- M5

Suppose that M3 suddently reboots and loses all states. When it comes back to life, M3 hears a DIO from M2 and re-attaches the DODAG, emmiting it's own DIO.

If we suppose the network was really stabilized, I think that the only information we have are :
- M2 & M4 : some NS (DAD), but that's not RPL-related.
- M2 : new DAO from M3, perhaps inconsistent (DAOSequence lower than the previous one -- but we don't know it, as we dont have to store it).
- M4 : perhaps an inconsistent DIO (DTSN lower than the previous one).

On the current draft, I don't see anything that deals with this issue. I may have missed something on how to handle a inconsistent DTSN (incrementing its own DTSN should do the trick), but the main idea is :
If one node on the dodag forgets one downward route, what should we do ?

On this example, if the root sends a packet for M5, M3 will send back a DAOnopath. As Mukul pointed out, the root should increase the Version Number. Every node will change its version, but as it won't change its preferred parent, there are no reason for sending a DAO and the downward route won't be repaired.

It's possible that there is a way to handle such downward route destruction, and in that case the selective repair is useless. But perhaps there are other issues that RPL doesn't handle. As a border effect such a selective repair will handle them.

What do you think ?

Sincerely,

Vincent

PS : In section 7.1, which deals with "Sequence Counter", I see no references to the DTSN. Shouldn't it appear here ?