Subject: Re: [Roll] Why a DAG? (was Re: Moving forward with the protocol work)

From: Alexandru Petrescu <[email-masked]>
Date: Mon, 03 Aug 2009 11:12:04 +0200

Jonathan,

Could it be that the physical topology on which RPL acted were an 
arbitrary graph, but the view of that topology (view maintained at each 
node) were a DAG?

Or is it a MUST that the topology and interface directionality to be a 
physical DAG?

Alex

Jonathan Hui a écrit :
> 
> Don correctly highlights and important reasons for the DAG that I want 
> to expand a bit more.
> 
> A DAG is necessary in resource constrained environments. Using a DAG 
> allows us the LLN to provide basic P2P connectivity while maintaining 
> hard bounds on the amount of memory each LLN node can maintain. It has 
> been mentioned many times that a DAG does not provide an "optimal" P2P 
> solution. If memory is constrained such that each LLN node is only 
> capable of maintaining a few routes at any time, then a DAG does provide 
> an "optimal" P2P solution given the state constraints. This is 
> fundamental and a protocol should allow for operation under such memory 
> constraints.
> 
> Using a DAG allows us to guide and constrain the communication of 
> routing information as well. It ensures that state maintenance and 
> exchange only occurs on a small subgraph of nodes toward the DAG root - 
> rather than and unstructured "flooding" of the entire DAG with such 
> information. While DAG construction uses broadcast RAs to communication 
> information, establishing routes that flow away from the root need only 
> rely on unicast communication. I'd like to stress the importance of 
> broadcast vs. unicast communication. While both are logically one 
> transmission, the two have very different costs in environments where 
> the radio is duty cycled. Depending on the duty-cycled link protocol, 
> broadcast can by orders of magnitude more expensive in channel 
> utilization, energy consumption, and communication delay. Again, this is 
> fundamental and a protocol should allow for operation under severe 
> channel capacity and energy constraints.
> 
> These fundamental limits require the use a hierarchical structure - a 
> DAG. A common misconception is that we chose a DAG because of the MP2P 
> and P2MP requirement. The real reason is that a DAG allows for operation 
> under severe resource constraints - not because traffic typically flows 
> through some edge router. A DAG orients the connectivity graph in a way 
> to constrain the routing problem. It's just a nice-to-have if the DAG is 
> rooted at the "edge router" when you do have MP2P and P2MP flows.
> 
> Of course, we have mentioned that a DAG can be used for avoiding and 
> detecting cycles, but that is not the fundamental reason for using the 
> DAG. The need for attending to loops and the count-to-infinity problem 
> is an important side effect of using the DV class of protocols.
> 
> Again, people need to be more concrete when saying "optimal", because 
> such a notion is not well defined without clarity in the problem's 
> constraints and goals. What people seem to mean when they say they want 
> more "optimal" mechanisms is really to be able to make use of more 
> resources when they are available. Specifically, if a node can maintain 
> more routes and communicate more routing information, it should be able 
> to reduce overall routing stretch. That I strongly agree with.
> 
> But the protocol needs to have a baseline to allow operation with severe 
> resource constraints and for that reason, I'd argue that the reliance on 
> a DAG provides that capability.
> 
> -- 
> Jonathan Hui
> 
> On Jul 31, 2009, at 6:10 AM, Don Sturek wrote:
> 
>> Hi Mukul,
>>
>> The part of RPL that I liked is the P2MP support (where once a device 
>> is part of a DAG, it need only promote packets upward to reach a 
>> concentrator device denoted as the DAG-root).   There seems to be 
>> little requirement for any state information in RPL to get this 
>> feature (quite nice).  Also no flooding!
>>
>> There is clearly work to be done to get a usable P2P mechanism running 
>> using RPL (and it is definitely needed even for Smart Metering).  It 
>> would be good to see if the RPL DAG feature could be retained and 
>> those that want P2P would be provided that capability (understanding 
>> they may be required to store state information in their devices to 
>> use P2P if that is the solution we end up with).
>>
>> By the way, most Smart Metering applications are relatively few 
>> devices (25 or so).  The problem comes in when supporting 
>> Multi-dwelling units (one of our use cases).   There we could have 
>> thousands of devices but with relatively few concentrators (really 
>> seems to map to RPL fairly well!)
>>
>> We have been struggling for some time to come up with elegant routing 
>> solutions over ad hoc networks and RPL seems to be the first one that 
>> doesn't fall apart in scenarios like:    many to one (MP2P), many 
>> devices in the network (more than a couple hundred), etc.
>>
>> Best Regards,
>>
>> Don Sturek
>>
>> -----Original Message-----
>> From: Mukul Goyal [mailto:[email-masked]]
>> Sent: Friday, July 31, 2009 5:55 AM
>> To: d sturek
>> Cc: ROLL WG; [email-masked]; Jerald P Martocci
>> Subject: Re: [Roll] Moving forward with the protocol work
>>
>> Don
>>
>> I will get back to the list regarding the scalability and flooding 
>> (BTW, the solution I proposed does not involve flooding, which I 
>> abhore with same vengeance as you) argument you made in favor of RPL 
>> and again the alternate solutions. Also, I will wait for DT solution 
>> for good P2P routing in RPL, but it seems to me that it has to involve 
>> some state maintenance in nodes.
>>
>> But, for a moment, lets forget about the alternate solutions. Lets 
>> just focus on RPL.
>>
>> All I am saying is that RPL, at present, is too tightly coupled with 
>> DAGs, which is a loop prevention mechanism as I understand it. Putting 
>> a specific loop prevention mechanism, a non-essential requirement, in 
>> the _foundation_ does not sound like a good idea to me.
>>
>> Thanks
>> Mukul
>>
>> ----- Original Message -----
>> From: "Don Sturek" <[email-masked]>
>> To: "Mukul Goyal" <[email-masked]>, "Jerald P Martocci" 
>> <[email-masked]>
>> Cc: "ROLL WG" <[email-masked]>, [email-masked]
>> Sent: Friday, July 31, 2009 7:11:38 AM GMT -06:00 US/Canada Central
>> Subject: RE: [Roll] Moving forward with the protocol work
>>
>> Hi Mukul,
>>
>> I don't agree that the alternate solutions proposed for ROLL scale and 
>> could support requirements outside building controls.  Specifically, I 
>> believe that the non-DAG solutions will require state information 
>> retention which will limit deployment beyond a modest number of nodes 
>> in the network.
>>
>> I believe the opposite as to what is proposed below.  I would propose 
>> using the RPL proposal as the baseline and provide some mechanisms to 
>> support optimization of P2P traffic.
>>
>> Best Regards,
>>
>> Don Sturek
>>
>>
>> -----Original Message-----
>> From: [email-masked] [mailto:[email-masked]] On Behalf 
>> Of Mukul Goyal
>> Sent: Friday, July 31, 2009 4:27 AM
>> To: Jerald P Martocci
>> Cc: ROLL WG; [email-masked]
>> Subject: Re: [Roll] Moving forward with the protocol work
>>
>> I absolutely support the approach Jerry suggested:
>>
>> 1) The foundation should be as simple as possible - a simple distance 
>> vector approach (I hope there is an agreement on this) describing 
>> next-hop selection based on routing metrics defined in the routing 
>> metrics draft, constraints and strategies (OCP) and basic rules to 
>> decide when to generate RAs. The foundation should not include any 
>> mechanism to deal with loops (so, it should not include DAGs unless 
>> DAGs can be shown to be critical in meeting other essential 
>> requirements).
>>
>> 2) Additional document(s) suggesting solutions catered towards MP2P 
>> and/or P2P routing using different mechanisms to deal with loops 
>> (including DAGs).
>>
>> Thanks
>> Mukul
>>
>> ----- Original Message -----
>> From: "Jerald P Martocci" <[email-masked]>
>> To: "Zach Shelby" <[email-masked]>
>> Cc: "Mukul Goyal" <[email-masked]>, "ROLL WG" <[email-masked]>, 
>> [email-masked]
>> Sent: Thursday, July 30, 2009 3:59:30 PM GMT -06:00 US/Canada Central
>> Subject: Re: [Roll] Moving forward with the protocol work
>>
>>
>>
>> Zach,
>>
>> When the design team was formed it stated its plan was to develop a 
>> core routing specification that met the needs of all the requirement 
>> specifications and then ancillary specifications to meet the specific 
>> needs for each of the requirements.  RPL as currently written seems 
>> perfectly suitable for the MP2P requirement, yet not too suitable for 
>> P2P requirement.  Could we repackage RPL so that its base spec 
>> contains only the generic routing requirements such as 1) using varied 
>> metrics to define path preferences, 2) OCP to advertise path strategy 
>> and 3) trickle to cleanly vary periodic requirements.  Then RPL-1 
>> could be then enhancements for MP2P applications and would include the 
>> DAG.  This would allow us to define a different extension, RPL-2, for 
>> P2P requirements that need not be DAG based.
>>
>> JP has promised that if I just shut-up and give the DT some time, they 
>> will provide a solid P2P solution.  I am willing to do that.  However, 
>> I would hate to start compromising the MP2P solution to wedge in a 
>> sub-optimal P2P solution.  Maybe we can have our cake and eat it too 
>> if we simply repackage the specs a bit.
>>
>> Jerry
>>
>>
>>
>>
>> Zach Shelby <[email-masked]>
>> Sent by: [email-masked]
>>
>> 07/30/2009 10:02 AM    
>> To     Mukul Goyal <[email-masked]>
>>
>> cc     ROLL WG <[email-masked]>
>>
>> Subject     Re: [Roll] Moving forward with the protocol work
>>     
>>
>>
>>
>> Hi,
>>
>> Mukul Goyal wrote:
>>> Mischa,
>>>
>>>> We should use this early design stage to come up with one solution - 
>>>> one
>>> solution which is not necessarily optimum for all cases but for the
>>> (e.g.) 95% quantile. The PHY guys learned to live with such an approach.
>>> The MAC folks are getting there and we should take our chance now. 95%
>>> means clearly to concentrate on the core issues, of which loop
>>> detection/avoidance, p2p and security are somehow still open.
>>>
>>> When you say a solution, it seems that you want one particular 
>>> protocol. I am OK with RPL as a protocol even though it has 
>>> deficiencies (such as
>> P2P routing). But, the implication of giving it the WG status seems to
>> be that RPL would be the _framework_ on which all future ROLL work would
>> be based. I am not in support of the use of RPL as a framework unless it
>> eliminates its current tight coupling with DAGs (a, rather heavy duty,
>> loop prevention mechanism).
>>
>> The goal of the WG from my understanding, is to produce *one* protocol
>> in the current charter. RPL is definitely suitable as a starting point
>> for that protocol (JP said foundation, not framework). I completely
>> support this approach.
>>
>> From the industry point of view we need a single solution, which
>> fulfills application requirements sufficiently and thus can be widely
>> deployed commercially.
>>
>> Regarding loop prevention, so what if RPL does a better job than is
>> necessary? Does it break some requirement doing that? If so, we should
>> fix it. There are other reasons for using DAGs than just loop prevention.
>>
>> Zach
>>
>> -- 
>> http://www.sensinode.com
>> http://zachshelby.org - My blog “On the Internet of Things”
>> Mobile: +358 40 7796297
>>
>> Zach Shelby
>> Head of Research
>> Sensinode Ltd.
>> Kidekuja 2
>> 88610 Vuokatti, FINLAND
>> _______________________________________________
>> Roll mailing list
>> [email-masked]
>> https://www.ietf.org/mailman/listinfo/roll
>>
>> _______________________________________________
>> Roll mailing list
>> [email-masked]
>> https://www.ietf.org/mailman/listinfo/roll
>>
>> _______________________________________________
>> Roll mailing list
>> [email-masked]
>> https://www.ietf.org/mailman/listinfo/roll
> 
> _______________________________________________
> Roll mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/roll
>

---

From: Jonathan Hui <[email-masked]>
Date: Mon, 3 Aug 2009 13:00:12 -0700

Hi Alex,

On Aug 3, 2009, at 2:12 AM, Alexandru Petrescu wrote:
> arbitrary graph, but the view of that topology (view maintained at  
> each node) were a DAG?

Yes. This is my view as well.

> Or is it a MUST that the topology and interface directionality to be  
> a physical DAG?

This is not a MUST in my mind.

--
Jonathan Hui

>
> Alex
>
> Jonathan Hui a écrit :
>> Don correctly highlights and important reasons for the DAG that I  
>> want to expand a bit more.
>> A DAG is necessary in resource constrained environments. Using a  
>> DAG allows us the LLN to provide basic P2P connectivity while  
>> maintaining hard bounds on the amount of memory each LLN node can  
>> maintain. It has been mentioned many times that a DAG does not  
>> provide an "optimal" P2P solution. If memory is constrained such  
>> that each LLN node is only capable of maintaining a few routes at  
>> any time, then a DAG does provide an "optimal" P2P solution given  
>> the state constraints. This is fundamental and a protocol should  
>> allow for operation under such memory constraints.
>> exchange only occurs on a small subgraph of nodes toward the DAG  
>> root - rather than and unstructured "flooding" of the entire DAG  
>> with such information. While DAG construction uses broadcast RAs to  
>> communication information, establishing routes that flow away from  
>> the root need only rely on unicast communication. I'd like to  
>> stress the importance of broadcast vs. unicast communication. While  
>> both are logically one transmission, the two have very different  
>> costs in environments where the radio is duty cycled. Depending on  
>> the duty-cycled link protocol, broadcast can by orders of magnitude  
>> more expensive in channel utilization, energy consumption, and  
>> communication delay. Again, this is fundamental and a protocol  
>> should allow for operation under severe channel capacity and energy  
>> constraints.
>> These fundamental limits require the use a hierarchical structure -  
>> a DAG. A common misconception is that we chose a DAG because of the  
>> MP2P and P2MP requirement. The real reason is that a DAG allows for  
>> operation under severe resource constraints - not because traffic  
>> typically flows through some edge router. A DAG orients the  
>> connectivity graph in a way to constrain the routing problem. It's  
>> just a nice-to-have if the DAG is rooted at the "edge router" when  
>> you do have MP2P and P2MP flows.
>> Of course, we have mentioned that a DAG can be used for avoiding  
>> and detecting cycles, but that is not the fundamental reason for  
>> using the DAG. The need for attending to loops and the count-to- 
>> infinity problem is an important side effect of using the DV class  
>> of protocols.
>> Again, people need to be more concrete when saying "optimal",  
>> because such a notion is not well defined without clarity in the  
>> problem's constraints and goals. What people seem to mean when they  
>> say they want more "optimal" mechanisms is really to be able to  
>> make use of more resources when they are available. Specifically,  
>> if a node can maintain more routes and communicate more routing  
>> information, it should be able to reduce overall routing stretch.  
>> That I strongly agree with.
>> But the protocol needs to have a baseline to allow operation with  
>> severe resource constraints and for that reason, I'd argue that the  
>> reliance on a DAG provides that capability.
>> -- 
>> Jonathan Hui
>>> The part of RPL that I liked is the P2MP support (where once a  
>>> device is part of a DAG, it need only promote packets upward to  
>>> reach a concentrator device denoted as the DAG-root).   There  
>>> seems to be little requirement for any state information in RPL to  
>>> get this feature (quite nice).  Also no flooding!
>>>
>>> There is clearly work to be done to get a usable P2P mechanism  
>>> running using RPL (and it is definitely needed even for Smart  
>>> Metering).  It would be good to see if the RPL DAG feature could  
>>> be retained and those that want P2P would be provided that  
>>> capability (understanding they may be required to store state  
>>> information in their devices to use P2P if that is the solution we  
>>> end up with).
>>>
>>> devices (25 or so).  The problem comes in when supporting Multi- 
>>> dwelling units (one of our use cases).   There we could have  
>>> We have been struggling for some time to come up with elegant  
>>> routing solutions over ad hoc networks and RPL seems to be the  
>>> first one that doesn't fall apart in scenarios like:    many to  
>>> one (MP2P), many devices in the network (more than a couple  
>>> hundred), etc.
>>>
>>> Best Regards,
>>>
>>> Don Sturek
>>>
>>> abhore with same vengeance as you) argument you made in favor of  
>>> RPL and again the alternate solutions. Also, I will wait for DT  
>>> solution for good P2P routing in RPL, but it seems to me that it  
>>> has to involve some state maintenance in nodes.
>>>
>>> All I am saying is that RPL, at present, is too tightly coupled  
>>> with DAGs, which is a loop prevention mechanism as I understand  
>>> it. Putting a specific loop prevention mechanism, a non-essential  
>>> requirement, in the _foundation_ does not sound like a good idea  
>>> to me.
>>>
>>> Thanks
>>> Mukul
>>>
>>> To: "Mukul Goyal" <[email-masked]>, "Jerald P Martocci" <[email-masked] 
>>> >
>>> I don't agree that the alternate solutions proposed for ROLL scale  
>>> and could support requirements outside building controls.   
>>> Specifically, I believe that the non-DAG solutions will require  
>>> state information retention which will limit deployment beyond a  
>>> modest number of nodes in the network.
>>>
>>> I believe the opposite as to what is proposed below.  I would  
>>> propose using the RPL proposal as the baseline and provide some  
>>> mechanisms to support optimization of P2P traffic.
>>>
>>> Best Regards,
>>>
>>> Don Sturek
>>>
>>>
>>> From: [email-masked] [mailto:[email-masked]] On  
>>> Behalf Of Mukul Goyal
>>> 1) The foundation should be as simple as possible - a simple  
>>> distance vector approach (I hope there is an agreement on this)  
>>> describing next-hop selection based on routing metrics defined in  
>>> the routing metrics draft, constraints and strategies (OCP) and  
>>> basic rules to decide when to generate RAs. The foundation should  
>>> not include any mechanism to deal with loops (so, it should not  
>>> include DAGs unless DAGs can be shown to be critical in meeting  
>>> other essential requirements).
>>>
>>> 2) Additional document(s) suggesting solutions catered towards  
>>> MP2P and/or P2P routing using different mechanisms to deal with  
>>> loops (including DAGs).
>>>
>>> Thanks
>>> Mukul
>>>
>>> Cc: "Mukul Goyal" <[email-masked]>, "ROLL WG" <[email-masked]>, [email-masked]
>>> When the design team was formed it stated its plan was to develop  
>>> a core routing specification that met the needs of all the  
>>> requirement specifications and then ancillary specifications to  
>>> meet the specific needs for each of the requirements.  RPL as  
>>> currently written seems perfectly suitable for the MP2P  
>>> requirement, yet not too suitable for P2P requirement.  Could we  
>>> repackage RPL so that its base spec contains only the generic  
>>> routing requirements such as 1) using varied metrics to define  
>>> path preferences, 2) OCP to advertise path strategy and 3) trickle  
>>> to cleanly vary periodic requirements.  Then RPL-1 could be then  
>>> enhancements for MP2P applications and would include the DAG.   
>>> This would allow us to define a different extension, RPL-2, for  
>>> JP has promised that if I just shut-up and give the DT some time,  
>>> they will provide a solid P2P solution.  I am willing to do that.   
>>> However, I would hate to start compromising the MP2P solution to  
>>> wedge in a sub-optimal P2P solution.  Maybe we can have our cake  
>>> and eat it too if we simply repackage the specs a bit.
>>>
>>> Jerry
>>>
>>>
>>>
>>>
>>> 07/30/2009 10:02 AM    To     Mukul Goyal <[email-masked]>
>>>
>>>>> We should use this early design stage to come up with one  
>>>>> solution - one