Subject: Re: [Roll] 8-bit DAG rank

From: Mukul Goyal <[email-masked]>
Date: Tue, 22 Sep 2009 09:31:32 -0500 (CDT)

Hi Pascal,

I am sorry I am not sure I understand your argument. The question at the table is why would we need to compare DAG ranks calculated using different OCPs. 

>They don't relate a lot but for the fact that a 'normal' hop costs 4. You need something, however arbitrary, to sort out your >routing when a node belongs to 2 DAGs that expose a same destination, default or other.

Suppose a node, that belongs to multiple DAGs exposing some destination X, receives a packet going to destination X. You seem to be suggesting that the node should compare its ranks in different DAGs and decide which DAG to use to forward the packet further. I would imagine that this decision will be based on some marking in the packet's IPv6 header. The node would maintain a table relating the packet's marking to an OCP. This relation will determine which DAG to use to forward the packet further. Is this understanding wrong?  

>For what it's worth making sure that the rank 'cost' to destination decreases at each hop gets you there without a loop, that's >the DV way for you.

I would imagine that loop avoidance in the presence of nodes belonging to multiple DAGs (using same or different OCPs) also requires strict adherence to the mapping between the packet's IPv6 header marking and an OCP. Such relationships between IPv6 header markings and OCPs need to be well known within the LLN. Then when a node receives a packet, it would be clear which DAG to use to forward the packet further.  

>Alternatively, you could tag the packets for a given topology, over always follow the least topoId ... but all those multi >topology routing techniques lead to complexity that we may not favor for the general case.

Could you please elaborate.

Thanks
Mukul
>Pascal

>-----Original Message-----
>From: Mukul Goyal [mailto:[email-masked]]
>Sent: lundi 21 septembre 2009 20:25
>To: Pascal Thubert (pthubert)
>Cc: roll
>Subject: Re: [Roll] 8-bit DAG rank
>
>Pascal
>
>I guess the first two reasons you mentioned:
>1)need to limit DAG depth; 2)desire to have more siblings
>make sense.
>
>However, I am not comfortable with the third reason.:
>DAG ranks calculated for different OCPs should be comparable.
>
>Comparing DAG ranks calculated for different OCPs is simply not apple-to-apple comparison.
>
>Thanks
>Mukul
>
>----- Original Message -----
>From: "Pascal Thubert (pthubert)" <[email-masked]>
>To: "Mukul Goyal" <[email-masked]>, "roll" <[email-masked]>
>Sent: Monday, September 21, 2009 5:21:44 AM GMT -06:00 US/Canada Central
>Subject: RE: [Roll] 8-bit DAG rank
>
>Hi Mukul:
>
>That is voluntary but maybe the reasons why it's done that way can be
>served some other fashion.
>
>Reason 1 is to limit the size of infinity. At the moment, it appears
>that we do not have a case where the protocol actually counts to
>infinity so this mostly places a barrier on how large we expect the
>network to be at most. Considering that a normal hop costs 4, that's 64
>hops deep.
>
>Reason 2 is that a coarse metric gives more chance to have siblings. In
>a triangle A (root) B, C, having B and C siblings optimizes the
>redundancy for all. Note that allowing the OF to be greedy enough to
>augment the rank in order to add siblings - but not parents! - seems an
>acceptable behavior.
>
>I'm not sure we can avoid severe restrictions on what the rank is as we
>abstract the rank into something that should be comparable between DAGs
>with completely different metrics and Objective Functions though. As it
>is defined now it appears to serve the purpose.
>
>Pascal
>
>>-----Original Message-----
>>From: [email-masked] [mailto:[email-masked]] On Behalf Of
>Mukul Goyal
>>Sent: vendredi 18 septembre 2009 18:40
>>To: roll
>>Subject: [Roll] 8-bit DAG rank
>>
>>Hi all,
>>
>>I was just wondering if 8-bit is too small a width for the DAG rank. I
>guess the small width puts severe
>>restrictions on what rank calculation functions could be used and how
>big a DAG can exist for a particular
>>rank calculation function. The constraints may be severe for LLNs
>consisting of thousands of nodes.
>>
>>Thanks
>>Mukul
>>
>>"DAGRank:  8-bit unsigned integer.  The DAG rank of the DAG root is 0.
>>         The DAG Rank of a node attached to the DAG should be greater
>>         than rank of its deepest DAG parent, as computed by an
>>         implementation specific routine.  All nodes in the DAG
>>         advertise their DAG rank in the DAG Information Options that
>>         they append to the RA messages over their LLN interfaces as
>>         part of the propagation process." (from rpl-01)
>>_______________________________________________
>>Roll mailing list
>>[email-masked]
>>https://www.ietf.org/mailman/listinfo/roll

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Tue, 22 Sep 2009 17:13:02 +0200

>Suppose a node, that belongs to multiple DAGs exposing some destination X, receives a packet going to
>destination X. You seem to be suggesting that the node should compare its ranks in different DAGs and decide
>which DAG to use to forward the packet further. I would imagine that this decision will be based on some
>marking in the packet's IPv6 header. The node would maintain a table relating the packet's marking to an OCP.
>This relation will determine which DAG to use to forward the packet further. Is this understanding wrong?

Well, it's either or. 

If you do Multi Topology Routing (MTR) as you seem to be suggesting here, then you need to match a marking in the packet (tag) with a topology (DAG). Or in the absence of marking you may follow the 'best' DAG using some strictly ordered graph of topologies. MTR leads to complexities that you might consider for the purpose of traffic engineering, but in not the general case.

Alternatively, you could make a single topology out of multiple DAGs. Preferably, you'd set things so up as to avoid prefix collisions. A prefix collision happens when a route appears along multiple DAGs. So you could avoid a collision by having only one DAG for default routes and all the other DAGs leading to more specific and mutually exclusive prefixes. But it's very hard to enforce such mutual exclusiveness rule in the general case. Soon enough, you might see a prefix exposed by a root for its own DAG also popping up in a DAO for another DAG in which that root is in your subDAG. Arglll.

So prefix collisions will happen and we have to deal with them. When a route appears along multiple DAGs, you need a common metric to always select within those DAGs a feasible successor for which the common metric decreases, and preferably follow the DAG with the steepest gradient for that destination. The rank is designed to be used as that common, Esperanto metric, whether you use it within a DAG with multiple OF or between DAGs.

This is why it's important that the rank increment is meaningful and compares to the default operation in OF/OCP 0. At the moment, the spec defines a normal hop as an increment of 4 - whatever normal means for a given deployment - and the range of increment is 1..16 for any given hop.

I hope this helps...

Pascal

>Sent: mardi 22 septembre 2009 16:32
>I am sorry I am not sure I understand your argument. The question at the table is why would we need to compare
>DAG ranks calculated using different OCPs.
>
>>They don't relate a lot but for the fact that a 'normal' hop costs 4. You need something, however arbitrary,
>to sort out your >routing when a node belongs to 2 DAGs that expose a same destination, default or other.
>
>Suppose a node, that belongs to multiple DAGs exposing some destination X, receives a packet going to
>destination X. You seem to be suggesting that the node should compare its ranks in different DAGs and decide
>which DAG to use to forward the packet further. I would imagine that this decision will be based on some
>marking in the packet's IPv6 header. The node would maintain a table relating the packet's marking to an OCP.
>This relation will determine which DAG to use to forward the packet further. Is this understanding wrong?
>
>>For what it's worth making sure that the rank 'cost' to destination decreases at each hop gets you there
>without a loop, that's >the DV way for you.
>
>I would imagine that loop avoidance in the presence of nodes belonging to multiple DAGs (using same or
>different OCPs) also requires strict adherence to the mapping between the packet's IPv6 header marking and an
>OCP. Such relationships between IPv6 header markings and OCPs need to be well known within the LLN. Then when
>a node receives a packet, it would be clear which DAG to use to forward the packet further.
>
>>Alternatively, you could tag the packets for a given topology, over always follow the least topoId ... but
>all those multi >topology routing techniques lead to complexity that we may not favor for the general case.
>

---

From: [email-masked]
Date: Tue, 22 Sep 2009 11:28:51 -0500

Pascal,

I thought the whole concept of multiple DAGs was to support different use 
cases.  For example, there may be a multiple DAGs defined on the LLN 
optimized for 1) ETX, 2) RSSI, 3) lowest latency or 4) minimal battery 
usage. These definitions seem to be independent; hence a given packet 
would need to use the same DAG for its complete transaction across the 
DAG.  The node sourcing the packet would seem to be the one that best 
knows the application at hand and best to set the DAG of choice for the 
transmission.  I can't see where the sourcing node decides that it needs 
to transmit a packet (say a Fire Alarm) using the 'lowest latency' DAG, 
and the node it sends it to decides that 'minimal battery usage' is a 
better approach and changes to that DAG.  Can you give an example of a use 
case where DAGs change midstream?

Jerry

"Pascal Thubert (pthubert)" <[email-masked]> 
Sent by: [email-masked]
09/22/2009 10:13 AM

To
"Mukul Goyal" <[email-masked]>
cc
roll <[email-masked]>
Subject
Re: [Roll] 8-bit DAG rank

Well, it's either or. 

If you do Multi Topology Routing (MTR) as you seem to be suggesting here, 
then you need to match a marking in the packet (tag) with a topology 
(DAG). Or in the absence of marking you may follow the 'best' DAG using 
some strictly ordered graph of topologies. MTR leads to complexities that 
you might consider for the purpose of traffic engineering, but in not the 
general case.

Alternatively, you could make a single topology out of multiple DAGs. 
Preferably, you'd set things so up as to avoid prefix collisions. A prefix 
collision happens when a route appears along multiple DAGs. So you could 
avoid a collision by having only one DAG for default routes and all the 
other DAGs leading to more specific and mutually exclusive prefixes. But 
it's very hard to enforce such mutual exclusiveness rule in the general 
case. Soon enough, you might see a prefix exposed by a root for its own 
DAG also popping up in a DAO for another DAG in which that root is in your 
subDAG. Arglll.

So prefix collisions will happen and we have to deal with them. When a 
route appears along multiple DAGs, you need a common metric to always 
select within those DAGs a feasible successor for which the common metric 
decreases, and preferably follow the DAG with the steepest gradient for 
that destination. The rank is designed to be used as that common, 
Esperanto metric, whether you use it within a DAG with multiple OF or 
between DAGs.

This is why it's important that the rank increment is meaningful and 
compares to the default operation in OF/OCP 0. At the moment, the spec 
defines a normal hop as an increment of 4 - whatever normal means for a 
given deployment - and the range of increment is 1..16 for any given hop.

I hope this helps...

Pascal

---

From: "Don Sturek" <[email-masked]>
Date: Tue, 22 Sep 2009 09:45:58 -0700

Hi Jerry,

I was assuming a device can be a member of multiple DAGs.  Those DAGs would
not necessarily have different cost metrics but may simply be different ways
to get to a rank 0 device (which presumably has connectivity and routing
capabilities that devices of in the DAG or higher rank do not).

Don

From: [email-masked] [mailto:[email-masked]] On Behalf Of
[email-masked]
Sent: Tuesday, September 22, 2009 9:29 AM
To: Pascal Thubert (pthubert)
Cc: roll; [email-masked]
Subject: Re: [Roll] 8-bit DAG rank

Pascal, 

I thought the whole concept of multiple DAGs was to support different use
cases.  For example, there may be a multiple DAGs defined on the LLN
optimized for 1) ETX, 2) RSSI, 3) lowest latency or 4) minimal battery
usage. These definitions seem to be independent; hence a given packet would
need to use the same DAG for its complete transaction across the DAG.  The
node sourcing the packet would seem to be the one that best knows the
application at hand and best to set the DAG of choice for the transmission.
I can't see where the sourcing node decides that it needs to transmit a
packet (say a Fire Alarm) using the 'lowest latency' DAG, and the node it
sends it to decides that 'minimal battery usage' is a better approach and
changes to that DAG.  Can you give an example of a use case where DAGs
change midstream? 

Jerry 

09/22/2009 10:13 AM 

To

cc

roll <[email-masked]> 

Subject

		

Well, it's either or. 

If you do Multi Topology Routing (MTR) as you seem to be suggesting here,
then you need to match a marking in the packet (tag) with a topology (DAG).
Or in the absence of marking you may follow the 'best' DAG using some
strictly ordered graph of topologies. MTR leads to complexities that you
might consider for the purpose of traffic engineering, but in not the
general case.

Alternatively, you could make a single topology out of multiple DAGs.
Preferably, you'd set things so up as to avoid prefix collisions. A prefix
collision happens when a route appears along multiple DAGs. So you could
avoid a collision by having only one DAG for default routes and all the
other DAGs leading to more specific and mutually exclusive prefixes. But
it's very hard to enforce such mutual exclusiveness rule in the general
case. Soon enough, you might see a prefix exposed by a root for its own DAG
also popping up in a DAO for another DAG in which that root is in your
subDAG. Arglll.

So prefix collisions will happen and we have to deal with them. When a route
appears along multiple DAGs, you need a common metric to always select
within those DAGs a feasible successor for which the common metric
decreases, and preferably follow the DAG with the steepest gradient for that
destination. The rank is designed to be used as that common, Esperanto
metric, whether you use it within a DAG with multiple OF or between DAGs.

I hope this helps...

Pascal

---

From: Mukul Goyal <[email-masked]>
Date: Tue, 22 Sep 2009 12:20:06 -0500 (CDT)

Pascal,

So, the rules seem to be:

1) if a node belongs to multiple DAGs that expose a packet's destination, the node has two choices regarding packet forwarding:
a) use the packet tag to determine which DAG to use
b) use a common/default metric to decide which DAG is best for the purpose

2) if the node belongs to just one DAG exposing a packet's destination, forward the packet to a DAG parent (chosen based on a metric that could be very different than the common/default metric)

So it seems that, in order to avoid loops in the case when some nodes belong to one DAG and others belong to multiple DAGs exposing the packet's destination, all nodes should ensure that its DAG parents have lower ranks than itself for both DAG-specific metric as well as the common/default metric.

Is this correct?

Thanks
Mukul  
----- Original Message -----
From: "Pascal Thubert (pthubert)" <[email-masked]>
To: "Mukul Goyal" <[email-masked]>
Cc: "roll" <[email-masked]>
Sent: Tuesday, September 22, 2009 10:13:02 AM GMT -06:00 US/Canada Central
Subject: RE: [Roll] 8-bit DAG rank

Well, it's either or. 

I hope this helps...

Pascal

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Mon, 28 Sep 2009 13:37:04 +0200

Hi Jerry

Do I have use cases for the DV based multiDAG? Probably. They provide a
faster backup while simplifying the topology vs. one big stuff with so
many links and exits. You could start a DAG from the 4 angles of a
football field and span the spectators in a more efficient fashion than
a current protocol would.

But this was not the point. I was listing options for clarity and to
make sure we agreed on the routing concepts that sustain this
discussion.

The current draft does not support multiple DAGs and we'll have to make
a conscious decision of which complexity we're willing to add to the
protocol to include this, as a base or an optional feature.

Pascal

From: [email-masked] [mailto:[email-masked]] 
Sent: mardi 22 septembre 2009 18:29
To: Pascal Thubert (pthubert)
Cc: Mukul Goyal; roll; [email-masked]
Subject: Re: [Roll] 8-bit DAG rank

Pascal, 

I thought the whole concept of multiple DAGs was to support different
use cases.  For example, there may be a multiple DAGs defined on the LLN
optimized for 1) ETX, 2) RSSI, 3) lowest latency or 4) minimal battery
usage. These definitions seem to be independent; hence a given packet
would need to use the same DAG for its complete transaction across the
DAG.  The node sourcing the packet would seem to be the one that best
knows the application at hand and best to set the DAG of choice for the
transmission.  I can't see where the sourcing node decides that it needs
to transmit a packet (say a Fire Alarm) using the 'lowest latency' DAG,
and the node it sends it to decides that 'minimal battery usage' is a
better approach and changes to that DAG.  Can you give an example of a
use case where DAGs change midstream? 

Jerry 

09/22/2009 10:13 AM 

To

cc

roll <[email-masked]> 

Subject

		

Well, it's either or. 

If you do Multi Topology Routing (MTR) as you seem to be suggesting
here, then you need to match a marking in the packet (tag) with a
topology (DAG). Or in the absence of marking you may follow the 'best'
DAG using some strictly ordered graph of topologies. MTR leads to
complexities that you might consider for the purpose of traffic
engineering, but in not the general case.

Alternatively, you could make a single topology out of multiple DAGs.
Preferably, you'd set things so up as to avoid prefix collisions. A
prefix collision happens when a route appears along multiple DAGs. So
you could avoid a collision by having only one DAG for default routes
and all the other DAGs leading to more specific and mutually exclusive
prefixes. But it's very hard to enforce such mutual exclusiveness rule
in the general case. Soon enough, you might see a prefix exposed by a
root for its own DAG also popping up in a DAO for another DAG in which
that root is in your subDAG. Arglll.

So prefix collisions will happen and we have to deal with them. When a
route appears along multiple DAGs, you need a common metric to always
select within those DAGs a feasible successor for which the common
metric decreases, and preferably follow the DAG with the steepest
gradient for that destination. The rank is designed to be used as that
common, Esperanto metric, whether you use it within a DAG with multiple
OF or between DAGs.

This is why it's important that the rank increment is meaningful and
compares to the default operation in OF/OCP 0. At the moment, the spec
defines a normal hop as an increment of 4 - whatever normal means for a
given deployment - and the range of increment is 1..16 for any given
hop.

I hope this helps...

Pascal

>I am sorry I am not sure I understand your argument. The question at
the table is why would we need to compare

---

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

Hi Mukul,

Pretty much if we go down that path.

>1) if a node belongs to multiple DAGs that expose a packet's destination, the node has two choices regarding

It is not a node choice, it has to be common to all nodes in a deployment

>a) use the packet tag to determine which DAG to use

That would be MTR

>b) use a common/default metric to decide which DAG is best for the purpose

That would be DV multiDAG. The packets are forwarded along the DAG that provides the shortest path for the Esperanto metric; if the DAGs were built for different purposes, the goal might not be achieved.

>2) if the node belongs to just one DAG exposing a packet's destination, forward the packet to a DAG parent
>(chosen based on a metric that could be very different than the common/default metric)

If we decide that a node can only belong to one DAG exposing a destination that's correct. That would guarantee the mutual exclusion and thus avoid the need for the Esperanto metric. 

Note that the issue also arises between DAO routes.

Pascal

>Sent: mardi 22 septembre 2009 19:20
>2) if the node belongs to just one DAG exposing a packet's destination, forward the packet to a DAG parent
>(chosen based on a metric that could be very different than the common/default metric)
>
>So it seems that, in order to avoid loops in the case when some nodes belong to one DAG and others belong to
>multiple DAGs exposing the packet's destination, all nodes should ensure that its DAG parents have lower ranks
>than itself for both DAG-specific metric as well as the common/default metric.
>
>Is this correct?
>
>Thanks
>Mukul
>If you do Multi Topology Routing (MTR) as you seem to be suggesting here, then you need to match a marking in
>the packet (tag) with a topology (DAG). Or in the absence of marking you may follow the 'best' DAG using some
>strictly ordered graph of topologies. MTR leads to complexities that you might consider for the purpose of
>traffic engineering, but in not the general case.
>
>Alternatively, you could make a single topology out of multiple DAGs. Preferably, you'd set things so up as to
>avoid prefix collisions. A prefix collision happens when a route appears along multiple DAGs. So you could
>avoid a collision by having only one DAG for default routes and all the other DAGs leading to more specific
>and mutually exclusive prefixes. But it's very hard to enforce such mutual exclusiveness rule in the general
>case. Soon enough, you might see a prefix exposed by a root for its own DAG also popping up in a DAO for
>another DAG in which that root is in your subDAG. Arglll.
>
>So prefix collisions will happen and we have to deal with them. When a route appears along multiple DAGs, you
>need a common metric to always select within those DAGs a feasible successor for which the common metric
>decreases, and preferably follow the DAG with the steepest gradient for that destination. The rank is designed
>to be used as that common, Esperanto metric, whether you use it within a DAG with multiple OF or between DAGs.
>
>This is why it's important that the rank increment is meaningful and compares to the default operation in
>OF/OCP 0. At the moment, the spec defines a normal hop as an increment of 4 - whatever normal means for a