Subject: [Roll] 8-bit DAG rank

From: Mukul Goyal <[email-masked]>
Date: Fri, 18 Sep 2009 11:39:30 -0500 (CDT)

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)

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Mon, 21 Sep 2009 12:21:44 +0200

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.
>_______________________________________________
>Roll mailing list
>[email-masked]
>https://www.ietf.org/mailman/listinfo/roll

---

From: Richard Kelsey <[email-masked]>
Date: Thu, 24 Sep 2009 10:17:58 -0400

Date: Mon, 21 Sep 2009 12:21:44 +0200
   From: "Pascal Thubert (pthubert)" <[email-masked]>

   >From: Mukul Goyal

   Mukul Goyal> I was just wondering if 8-bit is too small a width for the DAG
   Mukul Goyal> rank. I guess the small width puts severe restrictions on what rank
   Mukul Goyal> calculation functions could be used and how big a DAG can exist for
   Mukul Goyal> a particular rank calculation function. The constraints may be
   Mukul Goyal> severe for LLNs consisting of thousands of nodes.

If we don't count to infinity, why worry about how big it is?
It seems silly to cap the depth of networks unnecessarily.

We haven't established any particular benefit to having
more siblings.

If it turns out that we want more siblings, the size of the
sibling sets can be controlled independently of the size
of the DAG Rank.  Just ignore the one or more of the low bits
when comparing two DAG Ranks.

My experience is that one byte is a bit too small for the
value we are calling DAG Rank.  More precision here can
be very helpful.
                                    -Richard Kelsey

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Mon, 28 Sep 2009 14:11:55 +0200

Hi Richard

>It seems silly to cap the depth of networks unnecessarily.

The difference between count to infinity or not lies in details that are
not cast in stone yet :)
If you allow a child to follow a parent that's augmenting its rank, now
it might happen.
For RIP it is a critical feature. For us, something to keep in mind at
this point.
64 is a lot anyway. 3 times the maximum size envisioned in industrial
reqs RFC5673-to-be.

>We haven't established any particular benefit to having

I meant one sibling. Rather than be rank 16 with only one parent, it
would be acceptable to be greedy enough to be 17 and have also a
sibling, thus a backup path that would not be available without that
limited greediness.

>value we are calling DAG Rank.  More precision here can

Point Taken. This is in opposition with the traditional wisdom in DV
protocols but hey, this is a new domain.
We have yet some time before this decision is critical so let's keep
this in mind and give it more thought.