Subject: [Roll] Simplifying RPL: (1) multiple DAGs

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

[this e-mail is part 2/3 of the thread “Simplifying RPL”]

__Background__:
A DAG is defined as a group of nodes communicating using the same OCP. 
Multiple DAGs may exist inside a LLN, some may have a single DAG root, 
some may have multiple DAG root, and a single node may be the root of 
multiple DAGs.

As an example, used throughout this thread, consider the case of a 
building equipped with a LLN:
- some nodes monitor the power consumption of appliances in the 
building. These nodes report to a single intelligent meter M in a way so 
as the extend the network lifetime;
- other nodes are attached to smoke detectors, and report alarms to 
either one of two fire-monitoring hubs H1 or H2 (able to communicate 
with the fire brigade). Communication between the smoke detectors and 
the hubs needs to happen with lowest possible latency.

This LLN thus features two DAGs:
- DAG 1 is rooted at M, OCP defines ETX as a metric for the network, 
such that optimization goal is to minimize ETX, that DAG Rank is 
equivalent to ETX, and that RA-DIO propagation entails adding the 
advertised ETX of the most preferred parent to the ETX of the link to 
the most preferred parent.
- DAG 2 is rooted at H1 ad H2, OCP defines link latency as a metric for 
the network, such that optimization goals is to minimize latency, that 
DAG Rank is equivalent to smallest E2E latency to either root, and that 
RA-DIO propagation entails adding the latency of the most preferred 
parent to the latency of the link to the most preferred parent.

__current state__:
-02 enables *nodes* to join/leave DAGs. Because a node forwards data for 
all the nodes in its sub-DAG, these actions need to be closely 
coordinated (through the use of held-up/hold-down states, the creation 
of frozen floating sub-DAGs, the use of DAG Hop and Held-Down timers). 
We believe that close coordination is hard to achieve in the presence of 
lossy links, and that the use of many states/timers leads to state 
inconsistencies and race conditions.

Furthermore, it is not clear in the document what happens when nodes of 
a given DAG are separated by nodes of another DAG. Consider the topology 
attached (example_multiple_dags.jpg): nodes A, B, C, D, E report to M 
(DAG 1); nodes F and G report to roots H1 and H2 (DAG 2). Because DAG1 
nodes are not carrying any traffic over DAG2, -02 suggests that they 
leave DAG2. This, in turn, breaks connectivity of DAG2. If this is not 
the case, this should be made clear in the draft.

__proposed simplification__:
We suggest choosing a DAG on a per-packet basis, rather than on a 
per-node basis. As a result, all the nodes in the LLN participate in all 
the DAGs from an administrative point of view. Note that this does *not* 
mean that nodes are required to relay packet from all DAGs, as whether 
to do so depends solely on the node’s OCP policy. When a node forwards a 
packet, it indentifies which of the available DAGs satisfy the packet 
requirements best (e.g. destination address), and sends the packet to 
the corresponding next hop. As stated before, this removes the need for 
held-up/hold-down states, frozen floating sub-DAGs, and DAG 
Hop/Held-Down timers.

Consider the example in the attached figure (example_multiple_dags.jpg). 
Each node has two ranks, one for each DAG. Red nodes are the fire alarms 
(red squares the fire hubs); blue nodes are the energy monitoring nodes. 
The policy enforced is that blue motes can relay fire traffic, but not 
vice-versa. In the OCP, this means that red nodes set their ETX rank to 
infinity, hence avoiding energy monitoring traffic (note that 
[draft-ietf-roll-routing-metrics] specifies that metrics can be attached 
to nodes also, so if node G does not wish to relay traffic from DAG1, it 
sets a high node metric).

When node F reports a fire alarm, the packet goes through the 
lowest-latency path F-A-B-H1. When node A reports the energy consumption 
of the appliance it is attached to, its packet goes through A-C-M.

The cost of this technique is that a node needs to keep track of all the 
DAGs in the LLN, i.e. its own rank and its neighbors ranks need to be 
stored in RAM. The benefit is that it removes the need for 
held-up/hold-down states, frozen floating sub-DAGs, and DAG 
Hop/Held-Down timers. We believe that the benefits outweigh the cost.

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Tue, 29 Sep 2009 18:31:39 +0200

Hi Thomas:

Supporting multiple DAG (mDAG) is actually complex enough since you need
to understand the status of each parent for each DAG. 

Like joining a new DAG does not mean leaving the old one anymore. Then
you have to compare costs from DAOs coming from multiple DAGs (DV mDAG)
or build multiple topologies (MTR mDAG). 

With MTR, the topologies (DAGs) must be form a hierarchical structure
with a default (IOW a DAG of DAGs). A packet follows the topology that
matches a tag in the packet that indicates what you call a requirement;
when the match does not exist, the packet follows the best topology in
the order. 

Your example is a MTR case. You need tags to identify the type of
packets and route along the right color. Otherwise how foes a blue node
know to route a red packet towards H rather than M?

The blue appears to be the default; the default topology must be
spanning. Otherwise what if you have a blue guy on the bottom left?

There must be a way to support mDAG. We have to draw a line on the cases
we support to keep the cost acceptable.

Finally I fail to see the relation between mDAG and savings states. I
guess there are too many shortcuts for me to validate the logic. 

Let's discuss that tomorrow...

Pascal

>-----Original Message-----
>From: [email-masked] [mailto:[email-masked]] On Behalf Of
Thomas Watteyne
>Sent: samedi 26 septembre 2009 03:01
>To: IETF ROLL
>Subject: [Roll] Simplifying RPL: (1) multiple DAGs
>
>[this e-mail is part 2/3 of the thread "Simplifying RPL"]
>
>__Background__:
some may have multiple DAG root, and a
>single node may be the root of multiple DAGs.
>
>- some nodes monitor the power consumption of appliances in the
building. These nodes report to a single
>intelligent meter M in a way so as the extend the network lifetime;
either one of two fire-monitoring hubs H1
>or H2 (able to communicate with the fire brigade). Communication
between the smoke detectors and the hubs
>needs to happen with lowest possible latency.
>
such that optimization goal is to
>minimize ETX, that DAG Rank is equivalent to ETX, and that RA-DIO
propagation entails adding the advertised
>ETX of the most preferred parent to the ETX of the link to the most
preferred parent.
>- DAG 2 is rooted at H1 ad H2, OCP defines link latency as a metric for
the network, such that optimization
>goals is to minimize latency, that DAG Rank is equivalent to smallest
E2E latency to either root, and that RA-
>DIO propagation entails adding the latency of the most preferred parent
to the latency of the link to the most
>preferred parent.
>
>__current state__:
>-02 enables *nodes* to join/leave DAGs. Because a node forwards data
for all the nodes in its sub-DAG, these
>actions need to be closely coordinated (through the use of
held-up/hold-down states, the creation of frozen
>floating sub-DAGs, the use of DAG Hop and Held-Down timers).
>We believe that close coordination is hard to achieve in the presence
of lossy links, and that the use of many
>states/timers leads to state inconsistencies and race conditions.
>
a given DAG are separated by nodes of
>another DAG. Consider the topology attached
(example_multiple_dags.jpg): nodes A, B, C, D, E report to M (DAG
>1); nodes F and G report to roots H1 and H2 (DAG 2). Because DAG1 nodes
are not carrying any traffic over
>DAG2, -02 suggests that they leave DAG2. This, in turn, breaks
connectivity of DAG2. If this is not the case,
>this should be made clear in the draft.
>
per-node basis. As a result, all the nodes
>in the LLN participate in all the DAGs from an administrative point of
view. Note that this does *not* mean
>that nodes are required to relay packet from all DAGs, as whether to do
so depends solely on the node's OCP
>policy. When a node forwards a packet, it indentifies which of the
available DAGs satisfy the packet
>requirements best (e.g. destination address), and sends the packet to
the corresponding next hop. As stated
>before, this removes the need for held-up/hold-down states, frozen
floating sub-DAGs, and DAG Hop/Held-Down
>timers.
>Each node has two ranks, one for each DAG. Red nodes are the fire
alarms (red squares the fire hubs); blue
>nodes are the energy monitoring nodes.
vice-versa. In the OCP, this means that
>red nodes set their ETX rank to infinity, hence avoiding energy
monitoring traffic (note that [draft-ietf-
>roll-routing-metrics] specifies that metrics can be attached to nodes
also, so if node G does not wish to
>relay traffic from DAG1, it sets a high node metric).
>
lowest-latency path F-A-B-H1. When node A
>reports the energy consumption of the appliance it is attached to, its
packet goes through A-C-M.
>
>The cost of this technique is that a node needs to keep track of all
the DAGs in the LLN, i.e. its own rank
>and its neighbors ranks need to be stored in RAM. The benefit is that
it removes the need for held-up/hold-
>down states, frozen floating sub-DAGs, and DAG Hop/Held-Down timers. We
believe that the benefits outweigh the
>cost.

---

From: Thomas Watteyne <[email-masked]>
Date: Tue, 29 Sep 2009 11:55:10 -0700

Hi Pascal,

Thank you for your detailed answer! The point I try to make is that, in 
the current draft, there is quite some complexity associated with nodes 
joining and leaving DAGs. I also have some trouble figuring out what 
happens in case of DAG partitioning, i.e. when intermediate nodes decide 
to join a different DAG. I am convinced that some simplifications can be 
done in order to reduce the amount of shared state and the number of 
timers (my experience tells me that shared state leads to inconsistent 
states in lossy networks, and that the value of a timer - how long do I 
wait exactly? - is hard to choose).

For these reasons, I am wondering whether it wouldn't be simpler for all 
nodes to participate in all DAGs "administratively" (a node hence needs 
associates to each neighbor a rank value, for every DAG, not just one). 
Indeed, you need to tag the packet with a "color" so that it flows on 
the right DAG (thanks for making that clear to the list!). This does not 
change the core functioning of RPL, but would take the burden of 
choosing a DAG away from the node.

That being said, I certainly do not want to change the core of RPL! I'm 
just looking for ways of obtaining a simpler protocol. I'm sure you will 
do a great job at presenting RPL tomorrow, so most of the questions some 
of us have will be answered during your slot.

Thomas

Pascal Thubert (pthubert) wrote:
>> Consider the example in the attached figure
>>     
> (example_multiple_dags.jpg).
>