Subject: [Roll] [RPL] multiple roots in a DAG

From: <[email-masked]>
Date: Fri, 3 Jul 2009 18:39:31 +0200

Hello all,

Many thanks to the Design Team for having released the RPL draft,
providing us with material to ponder upon.
Among others, we have a question about the use of multiple roots in a
DAG.

If I understand the draft correctly, multiple roots shall send
"identical" DIOs with synchronized sequence numbers.
Therefore, nodes will only know of one root (because they discard DIOs
with same or lower seqnum).
Most nodes will likely hear from only one root anyway, since
intermediate nodes only propagate *one* DIO per DAGID.
This results in a watershed effect.
The routing algorithm at a node can therefore only chose among parents
that lead to the same root in that DAG.
Was there any consideration given to nodes knowing about several roots?
Or is the use of multiple DAGs recommended instead : this would go
counter the advocated intention of using multiple DAGs for serving
competing constraints (3.3.1.2)... 

Best regards,

Dominique

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Sat, 4 Jul 2009 15:23:43 +0200

Salut Dominique 

Exactly. Only nodes on the ridges might hear of 2 roots. The interesting
part is that the ridges define themselves by the choice of nodes on the
ridges. 

Having multiple DAGs with as many DAGIDs is what we expect in general
(divide and conquer) so that problem is isolated within its drainage
basin. For instance, the loss of a sink only impacts nodes in that basin
that have to migrate to the nearest next one.

I understand that you're really talking about, though, is multiple sinks
for a same DAGID, what I'd call a delta in a watershed analogy.

The only use case for a delta that I have in mind for this is a 6LoWPAN
backbone. What's required there is, as you indicate, a sync of the
"roots" so that they used consistent sequence numbers and DAGIDs. This
can be seen as a single root (the backbone itself ) of a single DAG and
the multiple secondary roots advertise depth 1 in that same DAG. What
I'd do there is use one of the root to source the protocol over the
backbone. I think we had good text on that in the fundamentals draft,
maybe we should integrate some of that in RPL.

There's really one DAG per DAGID. A delta is still one DAG with the
first hop in a backbone. I see multiple DAGs as multiple routing
topologies. Whether that's needed is a use case thing, but we allow it.
That multiplies the cost of control though. Not recommended for every
simple destination but useful for a few well chosen ones like gateways.

Cheers,

Pascal

Best regards, 

Dominique

---

From: <[email-masked]>
Date: Fri, 10 Jul 2009 18:27:16 +0200

Hello Pascal, all,

>> Therefore, nodes will only know of one root (because they discard
DIOs with same or lower seqnum). 
> Exactly. Only nodes on the ridges might hear of 2 roots. The
interesting part is that the ridges define themselves by the choice of
nodes on the ridges. 
> I understand that you're really talking about, though, is multiple
sinks for a same DAGID, what I'd call a delta in a watershed analogy.

This is exactly what I was refering to.

> The only use case for a delta that I have in mind for this is a
6LoWPAN backbone. What's required there is, as you indicate, a sync of
the "roots" so that they used consistent sequence numbers and DAGIDs.
This can be seen as a single root (the backbone itself ) of a single DAG
and the multiple secondary roots advertise depth 1 in that same DAG.
What I'd do there is use one of the root to source the protocol over the
backbone. I think we had good text on that in the fundamentals draft,
maybe we should integrate some of that in RPL.

The point is that, with the current draft, there is no delta possible.
If I understand correctly, all DIOs with same or earlier sequence
numbers are discarded, so a node hardly ever knows about other roots
than the closest one. Which amounts to watersheds separated by ridges,
not a delta. Am I mistaken here?

In an outdoor WSN, I could think of LLNs with multiple exit points that
use different technologies, (cellular on one side, wired on another one,
for example. That would not be a backbone, and synchronizing the roots
would be less obvious. If the exit points belong to different telcos,
they would even advertize different prefixes. Currently, nodes are
prevented from knowing all of these different prefixes. (a quick fix
might seem to propagate DIOs coming from various roots even if seqnum is
older, but that alone wouldn't work : since we don't have root IDs in
the DIOs, there's no way to differentiate an old DIO by the same root
from a new DIO by a different root).
BTW, adding RootIDs in the DIOs would eliminate the need for
synchronizing the roots, wouldn't it?
Any comment?

Cheers
Quentin & Dominique

>> The routing algorithm at a node can therefore only chose among
parents that lead to the same root in that DAG.

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Fri, 24 Jul 2009 16:07:56 +0200

Hi Dominique:

Sorry for being late on this

>not a delta. Am I mistaken here?

Same sequence should be accepted because we are doing a DAG, whether we
do a delta or not.

As you figure, there is a need to coordinate between the multiple sinks
of the delta to obtain the sequence and DAGID synchronization.

Say we drain a sensor network into a 6LoWPAN backbone. In that case, the
backbone is a virtual sink and one edge router would play the role of
the root over that backbone, so the edge routers would really advertize
a depth of 1 over the LLN even though they act as sinks there.

>from a new DIO by a different root).

In this case they should really form multiple DAGs. They will have
different capabilities and security models so they might drain different
information.

>synchronizing the roots, wouldn't it?

I think I miss this point. The DAGID is already a unique root ID. Could
you please elaborate?

All the best,

Pascal