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

From: Mukul Goyal <[email-masked]>
Date: Sat, 26 Sep 2009 14:14:30 -0500 (CDT)

Thomas

Please see my comments inline.

>__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.

Do you mean one DAG per OCP in the LLN? Or in other words, no need for DAG ID. That seems like an interesting idea with which I cant find any fault as long as it is allowed for a DAG (for a particular OCP) to have unconnected fragments spread throughout the LLN.
 
>__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.

I agree.

>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.

Although I dont remember if the rpl draft mandates a node to leave a DAG if it does not generate traffic for it, the draft does not specify any mechanism to guide a node whether it should join a particular DAG. That's why I had suggested Need_Route option and source-initiated route discovery. As per this mechanism, nodes F and G can mention in the Need_Route option carried in their RAs that they need to join DAG2. When nodes A,C, M receive these RAs, they know that a neighbor wants to join DAG2. Now they MAY further propagate Need_Route option (seeking to join DAG2 or seeking routes to destinations H1/H2) to their neighbors or join DAG2 if they already know how to join it. The Need_Route option need not be in the basic protocol as long as it is available as an add-on feature.

>__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.

I am not comfortable with the idea of requiring a node to join all the DAGs. This is simply not scalable in terms of memory. I am in favor of a node joining DAGs based on its own needs and the needs of its neighbors (which it comes to know via Need_Route options in the neighbor RAs).

I am not sure if we can eliminate held-up/hold-down states and DAG Hop/Held-Down timers by requiring a node to join all the DAGs. These timers/states are designed to avoid loops. In addition to avoiding loops during joining of new DAGs, these timers/states help avoid loops during movement (ie change of rank) within a DAG. Taking loop avoidance out of basic protocol automatically makes these states/timers redundant in the basic protocol.

Thanks
Mukul

>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.

[image/jpeg:example_multiple_dags.jpg]

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

---

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

Hi Mukul, Richard,

[inline]

> Do you mean one DAG per OCP in the LLN? Or in other words, no need for DAG ID. That seems like an interesting idea with which I cant find any fault as long as it is allowed for a DAG (for a particu…
Hm, not really. With multiple DAGs in the LLN, I believe that having a 
unique identifier for each one of them is quite mandatory. I would leave 
DAGIDs just like they are.
>> held-up/hold-down states, frozen floating sub-DAGs, and DAG 
Mukul, you state that RPL "allows for a DAG (for a particular OCP) to 
have unconnected fragments spread throughout the LLN". I agree with you 
as I don't think RPL enforces to have connected DAGs. In fact, does 
RPL-02 states anything on what should happen when a packet needs to 
bridge multiple fragments? If we come to an agreement that it does not, 
we should definitely specify something (either through Need_Route 
packets, or by asking all nodes to be administratively part of all DAGs).