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

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

Hi Jonathan

Please see inline.

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

But these nodes belong to the LLN. The LLN may have been designed to have a backbone of such nodes. These nodes are not as constrained resource-wise but they use 802.15.4 (or similar) low-power, low-data rate protocol for communication among themselves and with constrained devices around them. This is often the case in atleast some of the commercial building networks I am aware of. I imagine home environment also has a similar situation.

Can ROLL specify a more stateful, more general routing solution for this backbone? Or folks think that this backbone should simply not be part of the LLN? Note that these nodes are not really MANET nodes. They generally dont move (or their movement does not change the underlying logical connectivity significantly). They can't handle network-wide (or backbone-wide) broadcasts because they use a low data rate protocol (like 802.15.4). But they need general point-to-point routing, which needs to be (close to) optimal.
 
>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.

I agree with this argument. Again thanks for this explanation.

Thanks
Mukul

>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