Subject: [Roll] [roll] #5: DODAG

From: Tim Winter <[email-masked]>
Date: Sat, 07 Nov 2009 13:54:34 -0500

Hi Julien, WG,

roll issue tracker wrote:
> #5: DODAG
> --------------------------------+-------------------------------------------
>  Reporter:  jpv@…               |       Owner:  wintert@…      
>      Type:  defect              |      Status:  new            
>  Priority:  major               |   Milestone:                 
> Component:  rpl                 |     Version:                 
>  Severity:  Active WG Document  |    Keywords:                 
> --------------------------------+-------------------------------------------
>  * This is currently being discussed by the RPL Author team *
> 
>  Email from Julien
> 
>  Is there a distinction between DAG and destination oriented DAG. From what
>  I read I feel all DAGs are destination oriented. If this is correct I
>  propose to remove the destination oriented DAG concept.
> 

The intent for -05 will be to make the unqualifed use of `DAG' in the text
consistent with `DODAG Iteration', as outlined below.  So in this use, a
`DAG' is a `DODAG' snapshotted by a single sequence number -- a `DODAG
Iteration'.  There may be cases in -04 where the text reads `DAG' and is in
fact referring to `DODAG'- we will be sure to clean these up.  Here below is
some additional explanation prepared by the author team-

Does this help to clarify?

Regards,

-Tim

Instance

     +----------------------------------------------------------------+
     |                                                                |
     |      (R1)                   (R2)                   (Rn)        |
     |      /  \                   /| \                  / |  \       |
     |     /    \                 / |  \                /  |   \      |
     |   (A)    (B)             (M) |  (N)     ...    (X) (Y)  (Z)    |
     |   /|\     |\             /   |   |\             |   |    |     |
     |  : : :    : :            :  (O)  : :            :   :    :     |
     |                             / \                                |
     |                            :   :                               |
     |                                                                |
     |                          Instance ID                           |
     |                                                                |
     +----------------------------------------------------------------+

                                 Instance

   An Instance is a routing topology over an LLN, optimized for a
   particular objective/application.  Discrete Instances may also be set
   up to offer optimized connectivity to different destinations when
   appropriate, for example to differentiate a Home Network LLN from a
   Utility Network LLN in a smart metering application where a meter may
   be configured to join both Instances.

   It consists of one or more Destination Oriented DAGs (DODAGs).

   It is uniquely identified by an InstanceID.

   Each instance is operated independently of other instances, and RPL
   defines operation over only one instance.  Operation among multiple
   instances is to be expanded upon in a future revision or companion
   specification.

Destination Oriented DAG (DODAG)

     +----------------+
     |                |
     |      (R1)      |            (R2)                   (Rn)
     |      /  \      |            /| \                  / |  \
     |     /    \     |           / |  \                /  |   \
     |   (A)    (B)   |         (M) |  (N)     ...    (X) (Y)  (Z)
     |   /|\     |\   |         /   |   |\             |   |    |
     |  : : :    : :  |         :  (O)  : :            :   :    :
     |                |            / \
     |     DAGID      |           :   :
     |                |
     +----------------+

                                   DODAG

   A Destination Oriented DAG is a DAG rooted at a single root node,
   which is a node with no outgoing edges.

   In the case where multiple nodes in the LLN coordinate over a
   backbone and expose the same DAGID (to support the same DODAG), it is
   conceptually as if there is a single virtual root over the backbone
   (not illustrated).  In some applications/implementations this may be
   a desired architecture; in other applications each DODAG may operate
   with indpendent uncoordinated roots exposing different DAGIDs.

   A DODAG is uniquely identified over the LLN by the tuple (InstanceID,
   DAGID).

   In RPL a node may belong to only one DODAG per Instance at a time.

DODAG Iteration

           +----------------+                +-----------------+
           |                |                |                 |
           |      (R1)      |                |      (R1)       |
           |      /  \      |         \      |     / |  \      |
           |     /    \     |    ------\     |    /  |   \     |
           |   (A)    (B)   |           \    |  (A)  (C)  (B)  |
           |   /|\     |\   |           /    |  /|\        |\  |
           |  : : :    : :  |    ------/     | : : :       : : |
           |                |         /      |                 |
           |   Sequence N   |                |  Sequence N+1   |
           |                |                |                 |
           +----------------+                +-----------------+

                              DODAG Iteration

   A DODAG Iteration is the DODAG that results from the iterative
   process that reshapes the DODAG as stimulated by the root.  It is a
   DAG as constrained by operation of RPL over a fixed Sequence Number.

   As the root node increments the Sequence Number, different types of
   node movement are allowed (e.g. moving `down') and a new DODAG
   Iteration is formed.

   A DODAG Iteration is uniquely identified over the LLN by the tuple
   (InstanceID, DAGID, SequenceNumber).

Scope

   o  The scope of an InstanceID is the whole network and it defines an
      instance

   o  The scope of a DAGID is an instance and it defines a DODAG within
      that instance

   o  The scope of a Sequence Number is a DODAG and it defines an
      iteration of that DODAG (DODAG Iteration)

   o  The scope of a rank is a DODAG Iteration and it defines a position
      of a node within that iteration.

---

From: "Julien Abeille (jabeille)" <[email-masked]>
Date: Mon, 9 Nov 2009 11:11:45 +0100

Hi Tim,

My question is: are there DAGs that are not DODAGs in RPL? My feeling is
no. Hence I would suppress the DODAG instead of turning all "DAG" into
"DODAG".
Best,
Julien 

> -----Original Message-----
> From: [email-masked] [mailto:[email-masked]] On 
> Behalf Of Tim Winter
> Sent: samedi 7 novembre 2009 19:55
> To: ROLL WG
> Subject: [Roll] [roll] #5: DODAG
> 
> Hi Julien, WG,
> 
> 
> --------------------------------+-------------------------------------
> > --------------------------------+------
> >  Reporter:  jpv@...               |       Owner:  wintert@...      
> --------------------------------+-------------------------------------
> > --------------------------------+------
> >  Is there a distinction between DAG and destination 
> oriented DAG. From 
> > what  I read I feel all DAGs are destination oriented. If this is 
> > correct I  propose to remove the destination oriented DAG concept.
> > 
> 
> 
> The intent for -05 will be to make the unqualifed use of 
> `DAG' in the text consistent with `DODAG Iteration', as 
> outlined below.  So in this use, a `DAG' is a `DODAG' 
> snapshotted by a single sequence number -- a `DODAG 
> Iteration'.  There may be cases in -04 where the text reads 
> `DAG' and is in fact referring to `DODAG'- we will be sure to 
> clean these up.  Here below is some additional explanation 
> prepared by the author team-
> 
>      |                                                        
>         |
>      |      (R1)                   (R2)                   
> (Rn)        |
>      |      /  \                   /| \                  / |  
> \       |
>      |     /    \                 / |  \                /  |  
>  \      |
>      |   /|\     |\             /   |   |\             |   |  
>      |                             / \                        
>         |
>      |                            :   :                       
>         |
>      |                                                        
>         |
>      |                          Instance ID                   
>         |
>      |                                                        
>         |
> _______________________________________________
> Roll mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/roll
>

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Mon, 9 Nov 2009 12:17:50 +0100

Hi Julien:

In classical terms, an instance really defines a DAG. So if you have
multiple roots then RPL partitions that DAG into a set of
Destination-Oriented DAGs, also called DAG Rooted at a Destination in
the art. All those terms exist with a specific load and the wisdom we
hear from Phil and Dave is not to overload / redefine / restrict those
terms. 

The most useful object is the DODAG iteration. A node moves within one
and jump between 2. This is the object for which we should find cool
name. DODAGI is certainly pronounceable by many of us, but it looks a
lot like a WG name in mobility. Any idea?

Cheers,

Pascal

>From: [email-masked] [mailto:[email-masked]] On Behalf Of
Julien Abeille (jabeille)
>Sent: lundi 9 novembre 2009 11:12
>To: Tim Winter; ROLL WG
>Subject: Re: [Roll] [roll] #5: DODAG
>
>Hi Tim,
>

---

From: "Julien Abeille (jabeille)" <[email-masked]>
Date: Mon, 9 Nov 2009 13:26:11 +0100

Hi Pascal, all,

> From: Pascal Thubert (pthubert) 
> Sent: lundi 9 novembre 2009 12:18
> To: Julien Abeille (jabeille); Tim Winter; ROLL WG
> Subject: RE: [Roll] [roll] #5: DODAG
> 
> Hi Julien:
> 
> In classical terms, an instance really defines a DAG. 
If you have several roots with several DAG IDs, the DAGs are totally
disconnected. This is not one DAG, but several.
The differences we are talking about is "one vs several", not one kind
versus another DAG. 

> So if 
> you have multiple roots then RPL partitions that DAG into a 
> set of Destination-Oriented DAGs, also called DAG Rooted at a 
> Destination in the art. All those terms exist with a specific 
> load and the wisdom we hear from Phil and Dave is not to 
> overload / redefine / restrict those terms. 
All DAGs in RPL are destination oriented. I don't see the point of
adding as many adjectives as possible to the DAG term, especially since
we've been talking about DAGs since two years.

> 
> The most useful object is the DODAG iteration. A node moves 
> within one and jump between 2. This is the object for which 
> we should find cool name. DODAGI is certainly pronounceable 
> by many of us, but it looks a lot like a WG name in mobility. 
> Any idea?
DAG ;-)

Best,
Julien
> >My question is: are there DAGs that are not DODAGs in RPL? 
> My feeling 
> >is no. Hence I would suppress the DODAG instead of turning all "DAG" 
> >into "DODAG".
> >Best,
> >Julien
> >
> >> From: [email-masked] [mailto:[email-masked]] 
> On Behalf 
> >> Of Tim Winter
> --------------------------------+------------------------------------
> >> --------------------------------+-
> --------------------------------+------------------------------------
> >> --------------------------------+-
> `DAG' in the 
> >> text consistent with `DODAG Iteration', as outlined below.  So in 
> >> this use, a `DAG' is a `DODAG'
> >> snapshotted by a single sequence number -- a `DODAG Iteration'.  
> >> There may be cases in -04 where the text reads `DAG' and 
> is in fact 
> >> referring to `DODAG'- we will be sure to clean these up.  
> Here below 
> >> is some additional explanation prepared by the author team-
> >>
> >>    particular objective/application.  Discrete Instances 
> may also be 
> >> set
> >>    Utility Network LLN in a smart metering application 
> where a meter 
> >> may
> >>    backbone and expose the same DAGID (to support the same 
> DODAG), it 
> >> is
> >>    (not illustrated).  In some 
> applications/implementations this may 
> >> be
> >>    o  The scope of an InstanceID is the whole network and 
> it defines 
> >> an
> >>       instance
> >>

---

From: Philip Levis <[email-masked]>
Date: Mon, 9 Nov 2009 09:12:26 -0800

> no. Hence I would suppress the DODAG instead of turning all "DAG" into

I disagree -- Directed Acyclic Graph is a very well defined term in  
graph theory. We shouldn't redefine it. A DODAG is a particular kind  
of DAG, where there is one and only one node which has only incoming  
edges. We could maybe come up with a better term than DODAG, but DAG  
definitely isn't it. It will confuse readers tremendously.

Phil

---

From: "Julien Abeille (jabeille)" <[email-masked]>
Date: Mon, 9 Nov 2009 19:30:04 +0100

Hi Phil,

> From: Philip Levis [mailto:[email-masked]] 
> Sent: lundi 9 novembre 2009 18:12
> To: Julien Abeille (jabeille)
> Cc: Tim Winter; ROLL WG
> I disagree -- Directed Acyclic Graph is a very well defined 
> term in graph theory. We shouldn't redefine it. A DODAG is a 
> particular kind of DAG, where there is one and only one node 
> which has only incoming edges. We could maybe come up with a 
> better term than DODAG, but DAG definitely isn't it. It will 
> confuse readers tremendously.
Sorry, did not want to hurt graph theory specialists among IETF draft
readers. 

Seriously, what is confusing is to have DAGs and DODAGs everywhere in
the draft.
An instance is not as far as I understand a DAG. An instance is multiple
DODAGs. Hence either we use only DAG everywhere, or DODAG everywhere, no
mention of DAG. Thoughts?

Best,
Julien

---

From: Philip Levis <[email-masked]>
Date: Mon, 9 Nov 2009 10:50:36 -0800

> mention of DAG. Thoughts?

I totally agree - the mixed use of DODAG and DAG is confusing. I think  
we should use DODAG.

Phil