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

From: Mukul Goyal <[email-masked]>
Date: Mon, 3 Aug 2009 18:50:20 -0500 (CDT)

Hi Jonathan

Again a very well-crafted explanation. My compliments.

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

So, I conjure the image of a network of RFDs (borrowing 802.15.4 terminology). An RFD, rather than having an FFD in its radio range, has the nearest FFD several hops away. Now, the FFD can serve as the DAG root and the RFDs around it can join this DAG. This allows the RFDs to reach the FFD which can do the further routing. For these RFDs, DAG is indeed a good way to reach the FFD. But why _force_ the FFDs to also become part of the DAGs to some other roots when they can participate in more stateful routing.

If the intent is that RPL provides default routing mechanism for resource contrained nodes, I support RPL. But, for not-so-resource-constrained nodes, there is no critical reason to participate in DAGs.
 
>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.

Jonathan, don't you think that this argument again applies to extreme resource-constrained devices only? For other devices, that can maintain much more state and perhaps have abundant battery power as well, isn't it that the broadcast of infrequent RAs is much more desirable than spread along possibly broken DAG?

Again it seems to me that having local DAGs of (may be a few dozen) RFDs around an FFD makes sense for the reasons you described. But requiring thousands of FFDs as well as RFDs to arrange themselves in a few global DAGs seems inefficient.

I guess one needs to analyze mathematically performance under DAGs as they become deeper. Performance parameters being:

1. the stretch introduced in P2P routes due to the need to travel along the DAG, especially when nodes at higher rank (lower depth) have memory constraints.
2. conversely, the amount of state nodes at higher ranks need to maintain to support optimal (within the DAG) P2P and P2MP routing. (note that if the closest DAG ancestor of a source and destination does not maintain state about the destination the packets will have to travel longer than necessary)
3. the latency to perform DAG operations, such as re-joining a DAG at a higher depth.

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

Great. Again the question is: why force global DAGs? I think that you have made strong arguments in favor of local DAGs. I still am not convinced about the need to have global DAGs. I think resourceful nodes should be allowed to participate in more stateful routing that does not involve DAGs.

Thanks
Mukul

>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

---

From: Jonathan Hui <[email-masked]>
Date: Mon, 3 Aug 2009 17:02:58 -0700

Hi Mukul,

We don't force the use of RPL globally. If we did, we'd force the  
entire Internet to run RPL - that's just not how successful IP  
networks operate. If you want, you can always run multiple routing  
protocols and redistribute routes across routing domains if you need  
to. That's common place with IP networks today.

In fact, I'd expect that the DAG root, in some configurations, will be  
a heavyweight device (linux, mains-powered, ethernet on the other  
side). While RPL may be used to communicate with LLN nodes, RPL does  
not necessarily have to be used to provide connectivity to other  
networks. That's fairly common with edge routers today.

--
Jonathan Hui

On Aug 3, 2009, at 4:50 PM, Mukul Goyal wrote:

> So, I conjure the image of a network of RFDs (borrowing 802.15.4  
> terminology). An RFD, rather than having an FFD in its radio range,  
> has the nearest FFD several hops away. Now, the FFD can serve as the  
> DAG root and the RFDs around it can join this DAG. This allows the  
> RFDs to reach the FFD which can do the further routing. For these  
> RFDs, DAG is indeed a good way to reach the FFD. But why _force_ the  
> FFDs to also become part of the DAGs to some other roots when they  
> can participate in more stateful routing.
>
> If the intent is that RPL provides default routing mechanism for  
> resource contrained nodes, I support RPL. But, for not-so-resource- 
> constrained nodes, there is no critical reason to participate in DAGs.
>
> Jonathan, don't you think that this argument again applies to  
> extreme resource-constrained devices only? For other devices, that  
> can maintain much more state and perhaps have abundant battery power  
> as well, isn't it that the broadcast of infrequent RAs is much more  
> desirable than spread along possibly broken DAG?
>
> Again it seems to me that having local DAGs of (may be a few dozen)  
> RFDs around an FFD makes sense for the reasons you described. But  
> requiring thousands of FFDs as well as RFDs to arrange themselves in  
> a few global DAGs seems inefficient.
>
> I guess one needs to analyze mathematically performance under DAGs  
> as they become deeper. Performance parameters being:
>
> 1. the stretch introduced in P2P routes due to the need to travel  
> along the DAG, especially when nodes at higher rank (lower depth)  
> have memory constraints.
> 2. conversely, the amount of state nodes at higher ranks need to  
> maintain to support optimal (within the DAG) P2P and P2MP routing.  
> (note that if the closest DAG ancestor of a source and destination  
> does not maintain state about the destination the packets will have  
> to travel longer than necessary)
> Great. Again the question is: why force global DAGs? I think that  
> you have made strong arguments in favor of local DAGs. I still am  
> not convinced about the need to have global DAGs. I think  
> resourceful nodes should be allowed to participate in more stateful  
> routing that does not involve DAGs.
>
> Thanks
> Mukul
>
>

---

From: "Don Sturek" <[email-masked]>
Date: Mon, 3 Aug 2009 17:22:49 -0700

Hi Mukul,

I would propose the opposite conjecture as well:
1)  Why should devices that predominantly communicate multi-point to point (many examples in LLNs where there is a central concentrator solution) need to try to employ a P2P solution for this communication?   The MANET distance vector routing solutions have historically not handled this communication in a way that avoids non-scalable resource requirements on devices in the routing path.
2)  Similarly, when responses are needed to MP2P messaging, the reverse path has proven to be problematic as well using MANET distance vector solutions.

I think DAGs handle both the MP2P and P2MP in a scalable way.  By scalable, I believe a wide range of network sizes are supported without scaling the resources in these devices according to the size of the network and sizing all routing devices in the network for the worst case.

The assumption below that we are designing for resource constrained RFDs with DAGs and not taking advantage of added processing resources in FFDs is really not true.   The real problem is that the FFDs need to be resourced in a manner tied to the worst case routing requirements for a network with assumed device membership size.    

Don

-----Original Message-----
From: Mukul Goyal [mailto:[email-masked]] 
Sent: Monday, August 03, 2009 4:50 PM
To: Jonathan Hui
Cc: ROLL WG; [email-masked]; d sturek
Subject: Re: Why a DAG? (was Re: [Roll] Moving forward with the protocol work)

Hi Jonathan

 

Thanks
Mukul

--
Jonathan Hui

---

From: Mukul Goyal <[email-masked]>
Date: Mon, 3 Aug 2009 19:48:14 -0500 (CDT)

Hi Jonathan

By globally I meant globally within the LLN. LLN will consist of resourceful and resource-constrained devices. I think local DAGs connecting some resource-constrained devices to one or more resourceful devices makes sense. But requiring resourceful LLN nodes to also use RPL/DAGs for communication with each other seems unnecessary (to me so far).

Thanks
Mukul

----- Original Message -----
From: "Jonathan Hui" <[email-masked]>
To: "Mukul Goyal" <[email-masked]>
Cc: "ROLL WG" <[email-masked]>, [email-masked], "d sturek" <[email-masked]>
Sent: Monday, August 3, 2009 7:02:58 PM GMT -06:00 US/Canada Central
Subject: Re: Why a DAG? (was Re: [Roll] Moving forward with the protocol work)

Hi Mukul,

--
Jonathan Hui

---

From: Jonathan Hui <[email-masked]>
Date: Mon, 3 Aug 2009 19:01:29 -0700

Hi Mukul,

I understood what you were trying to get at. My basic point was that  
RPL, like any other routing protocol, does not preclude you from using  
additional routing protocols to provide connectivity between networks.  
Now there are two cases:

1) More privileged nodes that can communicate with each other through  
a network other than the LLN network.

In this case, run whatever routing protocol that best fits your needs  
outside the LLN network - redistribute routes across the LLN boundaries.

2) More privileged nodes in memory or energy that can only communicate  
with each other through the LLN network.

In this case, what you're really trying to get at is some style of  
landmark routing. But the very fact that these more privileged nodes  
must communicate through the LLN places constraints on how they can  
communicate with each other. Just because some nodes are privileged  
doesn't mean they can freely communicate without worrying about  
resource constraints within the network. Running some RIP-like or DSDV- 
like protocol is not much different than building DAGs rooted at each  
of these more privileged nodes. Two feasible solutions are (a) build  
completely overlapping DAGs rooted at each landmark or (b) utilize a  
"primary" DAG to help guide and constrain the construction of routes  
between "landmarks". For (a), you reduce the amount of state each LLN  
node maintains by pushing state to the landmarks, but it is still  
dependent on the number of landmarks you have. For (b), that is just  
an extension of "routing-along-a-DAG". One nice property of routing  
along a DAG is that you can place hard bounds on the state  
requirements of LLN nodes.

Note that any DV-style protocol is equivalent to building DAGs. RIP  
builds a DAG rooted at every node within the network. DSDV builds a  
DAG rooted at each destination in the network. Every DAG incurs some  
amount of state and control overhead. RPL proposes a solution that  
requires building only a single DAG and mechanisms to avoid and detect  
loops that are well-known problems with DV-style protocols.

--
Jonathan Hui

On Aug 3, 2009, at 5:48 PM, Mukul Goyal wrote:

> Hi Jonathan
>
> By globally I meant globally within the LLN. LLN will consist of  
> resourceful and resource-constrained devices. I think local DAGs  
> connecting some resource-constrained devices to one or more  
> resourceful devices makes sense. But requiring resourceful LLN nodes  
> to also use RPL/DAGs for communication with each other seems  
> unnecessary (to me so far).
>
> Thanks
> Mukul
>
> Cc: "ROLL WG" <[email-masked]>, [email-masked], "d sturek" <[email-masked] 
> >

---

From: Mukul Goyal <[email-masked]>
Date: Tue, 4 Aug 2009 07:56:16 -0500 (CDT)

Don

I agree with suitability of RPL for MP2P and P2MP routing. I also agree with the argument that RPL allows hard bounds on state.

Thanks
Mukul
 
----- Original Message -----
From: "Don Sturek" <[email-masked]>
To: "Mukul Goyal" <[email-masked]>, "Jonathan Hui" <[email-masked]>
Cc: "ROLL WG" <[email-masked]>, [email-masked]
Sent: Monday, August 3, 2009 7:22:49 PM GMT -06:00 US/Canada Central
Subject: RE: Why a DAG? (was Re: [Roll] Moving forward with the protocol work)

Hi Mukul,

Don

-----Original Message-----
From: Mukul Goyal [mailto:[email-masked]] 
Sent: Monday, August 03, 2009 4:50 PM
To: Jonathan Hui
Cc: ROLL WG; [email-masked]; d sturek
Subject: Re: Why a DAG? (was Re: [Roll] Moving forward with the protocol work)

Hi Jonathan

 

Thanks
Mukul

--
Jonathan Hui