Subject: [Roll] Simplifying RPL: overview

From: Thomas Watteyne <[email-masked]>
Date: Fri, 25 Sep 2009 18:00:04 -0700

Dear ROLL WG,

In an attempt to kickstart the simplification process of RPL, what 
follows are the elements we consider could be simplified/removed from 
-02. Our goal is to open the discussion of what can be done to decrease 
code complexity (i.e. which consumes ROM), remove states (i.e. which 
consume RAM) and reduce the number of timers (limited on typical low-end 
devices). By all means, please *jump in* if you disagree, or if you have 
other items in mind.

In a nutshell, we suggest the following simplifications:
- [multiple DAGs] shift the DAG selection process from per-node to 
per-packet. As a beneficial side-effect, this removes the need for nodes 
to jump from DAG to DAG, and removes most of the related complexity 
(held-up/hold-down states, frozen floating sub-DAGs, DAG Hop and 
Held-Down timers);
- [relax loop avoidance] relax constraints on increasing DAG rank and 
loop avoidance, removing the need for coordinated sub-DAGs.

We have decided to send out one e-mail per item. While this increases 
the number of items in your inbox (apologies!), we feel it also 
increases ease of tracking and stimulates discussion.

Thomas

---

From: Richard Kelsey <[email-masked]>
Date: Sun, 27 Sep 2009 11:48:10 -0400

Thomas,

   Date: Fri, 25 Sep 2009 18:00:04 -0700
   From: Thomas Watteyne <[email-masked]>

I am also in favor of this.

The constraints on increasing DAG rank and loop avoidance do
not require coordinated sub-DAGs.  We have used trees and
DAGs based on increasing DAG rank and DAG sequence numbers
in many deployments without any form of coordinated
sub-DAGs.  There may be good reasons for relaxing the DAG
rank constraints, but their requiring coordinated sub-DAGs
is not one of them.

I am in favor of removing coordinated sub-DAGs.

                                   -Richard Kelsey

---

From: Mukul Goyal <[email-masked]>
Date: Sun, 27 Sep 2009 10:56:05 -0500 (CDT)

Richard, Thomas

Could you please elaborate what you mean by "coordinated sub-DAGs".

Thanks
Mukul

----- Original Message -----
From: "Richard Kelsey" <[email-masked]>
To: "Thomas Watteyne" <[email-masked]>
Cc: [email-masked]
Sent: Sunday, September 27, 2009 10:48:10 AM GMT -06:00 US/Canada Central
Subject: Re: [Roll] Simplifying RPL: overview

Thomas,

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

---

From: Richard Kelsey <[email-masked]>
Date: Sun, 27 Sep 2009 12:20:18 -0400

Mukul,

   Date: Sun, 27 Sep 2009 10:56:05 -0500 (CDT)
   From: Mukul Goyal <[email-masked]>

What I meant, which I think is also what Thomas meant,
is the detaching and reattaching of sub-DAGs as a method
of increasing the DAG ranks of nodes.  This results in
the Held-Up state and other complexities.  Allowing a
node to increase its DAG rank without first communicating
with the sub-DAG below is simpler, at least as far as
parent choice is concerned.
                                -Richard Kelsey

---

From: JP Vasseur <[email-masked]>
Date: Mon, 28 Sep 2009 12:18:35 +0200

Hi,

> I am also in favor of this.

Same here, this was one of the items that we had identified also.

> I am in favor of removing coordinated sub-DAGs.

Yes I would not relax the constraint on increasing DAG rank (for loop  
avoidance)

Cheers.

JP.

---

From: Thomas Watteyne <[email-masked]>
Date: Mon, 28 Sep 2009 07:40:19 -0700

That's what I meant, thank.
Thomas

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Mon, 28 Sep 2009 18:38:35 +0200

>(held-up/hold-down states, frozen floating sub-DAGs, DAG Hop and

At this point the proposal is too vague to really argue: 

- Already with RPL, nodes can make per packets forwarding decisions. How
that is done is not specified; there is a constraint that is imposed by
the routing decision but then any parent can be used for any packet, and
if there's none then a sibling may be used.

- Parents' reputation might be lowered for a destination or the parent
might be held down if something like DADR is utilized. Loop detection is
not yet fully designed nor described in the current draft. There must be
a tradeoff between the implementation and runtime savings we make by
leaving loops and the implementation and runtime cost of detecting them.

- Detecting loops does not mean that the protocol can afford to be too
dumb. Yes, we are ready to relax some usual rules. But first and
foremost is to implement the core requirements of battery efficiency and
scalability that RIP and the count to infinity that comes with it cannot
serve appropriately. Implementation cost is still secondary though
probably more important here than it ever was since it does give us hard
bound constraints like how many timers and states can be supported. 

- My take here is that the benefits of split/merge DAGs outweighs the
cost of the additional states introduced.
This inherits from a long history of improvements in the DV protocols.
RPL limits the required knowledge of the world drastically to only those
nodes inwards the same DAG. This filters out many events and states that
the node would have to process, with a direct impact on the battery,
memory and bandwidth. It is not just the topological simplification of
the event horizon but mostly the drastic flow reduction and convergence
time involved in restoring connectivity when one DAG is broken. 

- clearly we can discuss what-ifs like what-if we do not leave before
joining back at higher rank. Which loops we would introduce and which
loop detection would we have to provide to compensate. I think that it
is not the biggest fish we have to fry yet at this point. And note that
this is not the only reasons for those states; Held-up is used for
smoothly merging DAGs, something you'll have to do anyway.

The recent history of RPL over the WG ML is that on good faith we have
been adding complexity. Making the rank decimal. Adding DAOs routes and
DAO fanout - which we did not really solve yet. Adding DIO routes - not
in the draft (yet?). Adding multiple DAGS and multiDAG management. Each
time looked like a small increment, but, man, the devil in the
details...

Like Richard, I think we need to make the core rich enough so that nodes
do not have to manage the complexity of having every bit potentially an
option. Still we have to address incredibly constrained devices. The
optimum will be the most we can fit in the device and I'm pretty sure
that the multiple DAGs discussion went passed it. The redux we are
looking for can start by considering the value/cost ratio of all those
goodies we have introduced over the bare-bone protocol and see what's
really core. In other words ROLL BACK a bit, but certainly not restart
from scratch -or RIP.

I trust that this redux effort will be core to the meeting Wednesday. I
hope you can join/dial in :)

Pascal

---

From: Thomas Watteyne <[email-masked]>
Date: Mon, 28 Sep 2009 10:50:50 -0700

Hi Pascal,
Thank you for your detailed answer. I certainly agree with your 
comments, especially with "not restart from scratch -or RIP" ! I'm 
looking forward to dial into the Wednesday meeting.
Thomas