Subject: Re: [Roll] Mixed mode operation

From: "Anders Brandt" <[email-masked]>
Date: Wed, 7 Apr 2010 13:14:29 +0200

Pascal wrote:

> -----Original Message-----
> From: [email-masked] [mailto:[email-masked]] On 
> Behalf Of Pascal Thubert (pthubert)
> Sent: Thursday, April 01, 2010 08:35
> To: Mukul Goyal; Owen Kirby
> Cc: roll
> Subject: Re: [Roll] Mixed mode operation
> 
> 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 

Home users do no planning and dimensioning.
They plug in stuff and push buttons.
We better have a strategy for unappropriate network topologies.

(Sorry. Couldn't help commenting on this one!)

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

RF is inherently unreliable. Unless I receive an end-to-end ack
I must assume that my message was lost.
Relying on a message telling me that delivery failed at repeater
#4 is wishfull thinking. That message may be lost as well.
Thus the answer is yes.

> I see what Owen is proposing. What do others think?
> 
> Pascal
> 
> 
> > -----Original Message-----
> > From: [email-masked] [mailto:[email-masked]] On Behalf
> Of
> > Mukul Goyal
> > Sent: Wednesday, March 31, 2010 10:29 PM
> > To: Owen Kirby
> > Cc: roll
> > Subject: Re: [Roll] Mixed mode operation
> > 
> > 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,
> > 
> > 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
> > >
> > 
> > _______________________________________________
> > 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: Philip Levis <[email-masked]>
Date: Wed, 7 Apr 2010 08:35:38 -0700

> (Sorry. Couldn't help commenting on this one!)

Agreed. But we also need to acknowledge that at some point things have to give. Vendors will sell devices that have the range and resources to work in expected configurations. E.g., we can't expect RPL to work in a typical home automation setting if the radio range is 1 inch or if the nodes have 1 byte of RAM. Nor can we expect RPL to work well when there are 1 billion nodes in a cubic meter. Of course, the more robust and flexible (in the sense of network topologies, not software options and knobs), RPL is, the broader the set of expected configurations under a set of resources will be.

The unconstrained task is impossible: a network of tiny microcontrollers that always works with low latency in all possible configurations, densities, and environments.

Phil

---

From: [email-masked]
Date: Wed, 7 Apr 2010 11:58:39 -0500

Hi Phil,

Agreed,  However, I think we (ROLL
WG) must provide a solution that works at least as well as the wireless
sensor implementations we already market; and at the same labor and product
cost point.  Otherwise, our customers question our use of the technology.
Unfortunately, (at least in the commercial market) there is currently
little sway we get from our customers simply because the solution is IP
based.  My customers are only interested in controlling the environment
in their buildings.

I know the commercial building requirement
draft (and I believe Ander's Home Requirement Draft) clearly quantifies
these requirements.  Here are some snippets of the draft that we should
be designing the router protocol toward:

.

It must be possible to fully commission
network devices without requiring any additional commissioning device (e.g.,
laptop). From the ROLL perspective, zero-configuration means that a node
can obtain an address and join the network on its own, without human intervention.

HVAC room applications typically have
sensors/actuators and controllers spaced about 50 ft apart.
Lighting is also very uniformly
installed with ballasts installed approximately every 10 feet.

The routing protocol must be able to
support networks with at least 2000 nodes where 1000 nodes would act as
routers and the other 1000 nodes would be hosts.

The software size requirements for routing
devices (e.g., room controllers) should be implementable in 8-bit devices
with no more than 256KB of flash memory.  The software size requirement
for non-routing devices (e.g., sleeping sensors and actuators) should be
implementable in 8-bit devices with no more than 128KB of memory.

A node transmitting a ‘request with
expected reply’ to another node must send the message to the destination
and receive the response in not more than 120ms.  This response time
should be achievable with 5 or less hops in each direction.
When
I drafted these requirements, I simply documented the empirical performance
as measured on our existing products.  If RPL implementations meet
these capacity and performance measures my customers will be satisfied;
if not, I'm not sure RPL will be successful in the commercial market.

Jerry

From:

Philip Levis <[email-masked]>

To:

Anders Brandt <[email-masked]>

Cc:

roll <[email-masked]>

Date:

04/07/2010 11:14 AM

Subject:

Re: [Roll] Mixed mode operation

> (Sorry. Couldn't help commenting on this one!)

Agreed. But we also need to acknowledge that at some point things have
to give. Vendors will sell devices that have the range and resources to
work in expected configurations. E.g., we can't expect RPL to work in a
typical home automation setting if the radio range is 1 inch or if the
nodes have 1 byte of RAM. Nor can we expect RPL to work well when there
are 1 billion nodes in a cubic meter. Of course, the more robust and flexible
(in the sense of network topologies, not software options and knobs), RPL
is, the broader the set of expected configurations under a set of resources
will be.

The unconstrained task is impossible: a network of tiny microcontrollers
that always works with low latency in all possible configurations, densities,
and environments.

Phil

Roll mailing list

[email-masked]

---

From: Philip Levis <[email-masked]>
Date: Wed, 7 Apr 2010 10:36:03 -0700

On Apr 7, 2010, at 9:58 AM, [email-masked] wrote:

> 
> 
> Hi Phil, 
> 
> Agreed,  However, I think we (ROLL WG) must provide a solution that works at least as well as the wireless sensor implementations we already market; and at the same labor and product cost point.  Otherwise, our customers question our use of the technology.  Unfortunately, (at least in the commercial market) there is currently little sway we get from our customers simply because the solution is IP based.  My customers are only interested in controlling the environment in their buildings.   
> 
> I know the commercial building requirement draft (and I believe Ander's Home Requirement Draft) clearly quantifies these requirements.  Here are some snippets of the draft that we should be designing the router protocol toward: 
> .  
> It must be possible to fully commission network devices without requiring any additional commissioning device (e.g., laptop). From the ROLL perspective, zero-configuration means that a node can obtain an address and join the network on its own, without human intervention.
> HVAC room applications typically have sensors/actuators and controllers spaced about 50 ft apart.  Lighting is also very uniformly installed with ballasts installed approximately every 10 feet.
> The routing protocol must be able to support networks with at least 2000 nodes where 1000 nodes would act as routers and the other 1000 nodes would be hosts.  
> The software size requirements for routing devices (e.g., room controllers) should be implementable in 8-bit devices with no more than 256KB of flash memory.  The software size requirement for non-routing devices (e.g., sleeping sensors and actuators) should be implementable in 8-bit devices with no more than 128KB of memory.  
> A node transmitting a ‘request with expected reply’ to another node must send the message to the destination and receive the response in not more than 120ms.  This response time should be achievable with 5 or less hops in each direction.  
> When I drafted these requirements, I simply documented the empirical performance as measured on our existing products.  If RPL implementations meet these capacity and performance measures my customers will be satisfied; if not, I'm not sure RPL will be successful in the commercial market. 

Jerry,

This is fantastic. Nice, precise requirements.

Phil

---

From: Richard Kelsey <[email-masked]>
Date: Wed, 07 Apr 2010 22:00:27 -0400

> Date: Wed, 7 Apr 2010 13:14:29 +0200
> From: "Anders Brandt" <[email-masked]>
>
> Pascal wrote:
> 

I agree with Anders on this.  There needs to be at least
the option of an end-to-end ack for source route mode.
This ack could be implicit, in that receiving a source
routed message can tell you that the sender has a source
route to you.
                            -Richard Kelsey