Subject: Re: [Roll] Mixed mode operation

From: Mukul Goyal <[email-masked]>
Date: Wed, 31 Mar 2010 14:51:40 -0500 (CDT)

Hi Owen

This makes sense to me.

Thanks
Mukul

----- Original Message -----
From: "Owen Kirby" <[email-masked]>
To: "Mukul Goyal" <[email-masked]>
Cc: "Pascal Thubert (pthubert)" <[email-masked]>, "roll" <[email-masked]>
Sent: Wednesday, March 31, 2010 2:40:09 PM GMT -06:00 US/Canada Central
Subject: Re: [Roll] Mixed mode operation

Mukul, Pascal,

Please correct me if I'm wrong, but are we really sure a *negative* ack 
is what we need in this case?

It seems to me that if the root needs to send a negative ack because the 
routing tables are full, then the root could be in a state where it's 
unable to route the NACK to the node that sent the DAO in the first 
place. In which case, the node never gets a NACK and will assume that 
the reverse route is being stored on the root.

To illustrate how this might happen on a non-caching network:

A -> B -> C -> ...   -> Root

1) C sends a DAO, and fills up the routing table on the DAG root so it 
can't accept any more DAOs.
2) B sends a DAO to the root. The root can route a NACK back because it 
knows how to route to C, and the parent set in B's DAO contains C.
3) A sends a DAO to the root, but the root doesn't have a route to B and 
thus can't find a route back to A.

It seems to me that a positive ack would be more appropriate in this 
case. This would also prevent inconsistencies if the DAO or NACK gets 
lost due to interference.

Thanks,
Owen

Mukul Goyal wrote:
> Pascal,
>
>   
>> If a parent can reject a DAO with a negative ack, then the child can
>>     
> select an alternate parent for that DAO and the light will come up. This
> is the bare minimum we can do. We already have an issue on this and I'm
> asking support on the proposal.
>
>
> I totally support the negative DAO ack. I think it is critical.
>
> Thanks
> Mukul
>
> ----- Original Message -----
> From: "Pascal Thubert (pthubert)" <[email-masked]>
> To: "Philip Levis" <[email-masked]>
> Cc: "roll" <[email-masked]>
> Sent: Wednesday, March 31, 2010 4:28:09 AM GMT -06:00 US/Canada Central
> Subject: Re: [Roll] Mixed mode operation
>
> Hi Phil:
>
> I do not think that we can live without enough capacity, trying to fix
> that is a nightmare. I just wish that a network with enough capacity
> works, and that is not obvious today. On the contrary, I'm afraid that
> if we do nothing, a well dimensioned network will randomly expose
> routing table capacity issues that will be difficult to justify.
>
> We seem to agree that the problem is mostly a deployment problem, add a
> root, right? That's certainly fine with the usual mesh problem when the
> weak link is the bandwidth at the root. That's probably failing short
> when the capacity problem is the routing table in a node hops away from
> the root.
>
> With the current spec, all the nodes around could select a same parent
> and overload it while alternates exist with plenty of room. This might
> push the capacity problem hops away from the root. If a candidate parent
> can hint that it is loaded and not willing to accept much more, then the
> parent selection in the children can load balance with other parents. So
> the problem is again pushed back to the root and we're safe again.
>
> If a parent can reject a DAO with a negative ack, then the child can
> select an alternate parent for that DAO and the light will come up. This
> is the bare minimum we can do. We already have an issue on this and I'm
> asking support on the proposal.
>
> Pascal
>
>
>   
>> -----Original Message-----
>> From: Philip Levis [mailto:[email-masked]]
>> Sent: Tuesday, March 30, 2010 7:03 PM
>> To: Pascal Thubert (pthubert)
>> Cc: Michael Richardson; roll
>> Subject: Re: [Roll] Mixed mode operation
>>
>> On Mar 29, 2010, at 11:35 PM, Pascal Thubert (pthubert) wrote:
>>
>>     
>>> Hi:
>>>
>>> As Phil said the anti-replay came up in Anaheim. This piece is to be
>>> covered in the security analysis. So I think we should only consider
>>> the saturation of routing tables in this thread.
>>>
>>> Also I do not believe in churn in routing tables to address capacity
>>> overload. We've seen in ND that a cache that's not dimensioned
>>> appropriately (too small) just  causes permanent look ups that
>>> multiply the traffic in the network, loss and latency.
>>>
>>> In classical mesh networking, what you do when the network gets
>>>       
> fully
>   
>>> busy is that you add another root. Capacity management becomes a
>>> deployment issue. Usually what we address there is the bandwidth
>>> capacity on the root radio space. In this thread, the problem is a
>>>       
> bit
>   
>>> different and the routing table overload might occur one or more
>>>       
> hops
>   
>>> away from the root. Still, the solution to increase capacity needs
>>>       
> is
>   
>>> probably divide and conquer, and nothing will replace a proper
>>> capacity planning overall.
>>>
>>> RPL enables DAGs that are made of multiple DODAGs. RPL enables the
>>> radio roots to be connected to a backbone, with a super-root there
>>>       
> if
>   
>>> you want a single DODAG. RPL dynamically adapts to the addition or
>>>       
> the
>   
>>> removal of a root in an instance so adapting the capacity to new
>>> requirements has only a local impact on the network. It also adapts
>>> dynamically to the addition of a parent in the DODAG to share the
>>>       
> load
>   
>> close to the root.
>>     
>>> So we can do divide and conquer dynamically.
>>>
>>> If there are enough parents and still one parent is overloaded
>>> somewhere, then we might have an issue with the parent selection. At
>>> the moment, a parent cannot indicate the capacity of its routing
>>> table, so a node might attach to parent that has no room for it.
>>>       
> Also,
>   
>>> one of the reasons for a DAO ack is for a parent to reject a DAO for
>>> lack of capacity.
>>>
>>> If there are enough roots and still one DODAG is overloaded
>>>       
> somewhere,
>   
>>> then we might have an issue with the DODAG selection. We need is to
>>> push nodes on the ridge between DADOGs to jump onto the other DODAG
>>>       
>> in
>>     
>>> order to balance the load between DODAGs. To do that, we need a
>>> pushback mechanism from the nodes where the capacity is reached to
>>>       
> the
>   
>>> nodes on the ridge that can jump elsewhere.
>>>
>>> I'm not saying that this is easy, but I think it can be done.
>>>       
>> I really think this is outside the protocol specification and is a
>>     
> non-issue. Does
>   
>> any other routing protocol specify what happens when there is
>>     
> insufficient
>   
>> space in a routing table? It's an implementation-specific decision. At
>>     
> the very
>   
>> least, it should be outside the core specification.
>>
>> It's an operational/administrative issue: if the network's routing
>>     
> tables are
>   
>> overloaded, add another root. Rank and incrementing DODAG sequence
>> numbers are a perfectly reasonable way to achieve this. We don't need
>> additional complexity.
>>
>> Phil
>>     
> _______________________________________________
> 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: Mukul Goyal <[email-masked]>
Date: Wed, 31 Mar 2010 15:28:45 -0500 (CDT)

Hi Owen

I guess one could argue that in a non-storing LLN the DAG root is the only storing node. So if it can not store a DAO, the DAO can not be stored at all. But still it is important for a node to know that its DAO can not be stored. It could use this information to decide whether to jump to (or join) another DAG. So, clearly a positive DAO ACK makes sense.

Now, in case of a storing LLN, a parent does not need to "route" a DAO ACK back. So, negative DAO ACKs would work fine. The benefit of negative DAO ACK is less message generation.

Thanks
Mukul
  
----- Original Message -----
From: "Mukul Goyal" <[email-masked]>
To: "Owen Kirby" <[email-masked]>
Cc: "roll" <[email-masked]>
Sent: Wednesday, March 31, 2010 2:51:40 PM GMT -06:00 US/Canada Central
Subject: Re: [Roll] Mixed mode operation

Hi Owen

This makes sense to me.

Thanks
Mukul

----- Original Message -----
From: "Owen Kirby" <[email-masked]>
To: "Mukul Goyal" <[email-masked]>
Cc: "Pascal Thubert (pthubert)" <[email-masked]>, "roll" <[email-masked]>
Sent: Wednesday, March 31, 2010 2:40:09 PM GMT -06:00 US/Canada Central
Subject: Re: [Roll] Mixed mode operation

Mukul, Pascal,

Thanks,
Owen

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Thu, 1 Apr 2010 08:34:43 +0200

Hi Owen and Mukul:

It seems that for every problem we should spell out the stateless and
the stateful models.

The NACK is a response to the stateful mode problem of the saturation of
the routing table in a parent that is an intermediate router somewhere
in the network. The NACK does not address the saturation of the root.
The problem cannot be addressed by simple planning because it has to do
with the parent selection algorithm. Upon a NACK, a node would select an
alternate parent as that is not saturated for its excess DAO. If the
network is appropriately planned and dimensioned, such a parent should
exist. This pushes the saturation problem back up to the root, where it
can be handled more easily.

At this point, the question is whether the root itself is saturated or
not. This problem is common to stateful and source route. And the answer
is, again, network planning. As a network evolves and grows, if a root
is getting close to capacity, the user needs to deploy an additional
root. We could do better than that in some future, by pushing nodes from
one DODAG to the next to improve the load balancing between roots. Like
I said, I think that can be done. But Phil and JP indicated their
reluctance to additional mechanisms, and certainly this has a lesser
degree of criticality. 

Finally, the NACK is just another ACK, with a failure Return code. What
the issue is about is having an ACK. I take it that Owen agrees with us
that it is useful for stateful?

Note that the ACK that is proposed in issue #27 is not end-to-end but
hop-by-hop. The biggest reason is to make the DAO more reliable. Once we
have it, then we can derive benefits like the NACK.

Whether there is a need for end-to-end ack for source route mode is TBD.
I see what Owen is proposing. What do others think?

Pascal

> From: [email-masked] [mailto:[email-masked]] On Behalf
Of
> Mukul Goyal
> Sent: Wednesday, March 31, 2010 10:29 PM
> To: Owen Kirby
> Cc: roll
> I guess one could argue that in a non-storing LLN the DAG root is the
only
> storing node. So if it can not store a DAO, the DAO can not be stored
at all.
> But still it is important for a node to know that its DAO can not be
stored. It
> could use this information to decide whether to jump to (or join)
another
> DAG. So, clearly a positive DAO ACK makes sense.
> 
> Now, in case of a storing LLN, a parent does not need to "route" a DAO
ACK
> back. So, negative DAO ACKs would work fine. The benefit of negative
DAO
> ACK is less message generation.
> 
> Thanks
> Mukul
> 
> Please correct me if I'm wrong, but are we really sure a *negative*
ack is
> what we need in this case?
> 
unable to
> route the NACK to the node that sent the DAO in the first place. In
which
> case, the node never gets a NACK and will assume that the reverse
route is
> being stored on the root.
> 
can't
> accept any more DAOs.
> 3) A sends a DAO to the root, but the root doesn't have a route to B
and thus
> can't find a route back to A.
> 
case.
> This would also prevent inconsistencies if the DAO or NACK gets lost
due to
> interference.
> > select an alternate parent for that DAO and the light will come up.
> > This is the bare minimum we can do. We already have an issue on this
> > and I'm asking support on the proposal.
> >
> >
> > We seem to agree that the problem is mostly a deployment problem,
add
> > a root, right? That's certainly fine with the usual mesh problem
when
> > the weak link is the bandwidth at the root. That's probably failing
> > short when the capacity problem is the routing table in a node hops
> > away from the root.
> >
> > push the capacity problem hops away from the root. If a candidate
> > parent can hint that it is loaded and not willing to accept much
more,
> > then the parent selection in the children can load balance with
other
> > parents. So the problem is again pushed back to the root and we're
safe
> again.
> > select an alternate parent for that DAO and the light will come up.
> > This is the bare minimum we can do. We already have an issue on this
> > and I'm asking support on the proposal.
> >
> > Pascal
> >
> >
> >