Subject: Re: [Roll] RPL behaviour with routing table overflow

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Wed, 2 Nov 2011 13:14:13 +0100

Hello Cedric:

This question was discussed but proposals to actually do something were rejected. The point was that the devices are supposed to have 'enough' memory. We can probably dig in the ML archive but my memory tells me that you already went as far as the discussion ever did.

In your thinking you need to remember that RPL is still building a DODAG. So if all devices are equal and a node has a memory issue, then its parent's memory is even more of an issue. And the problem goes down very rapidly has the number of hops augments from the root. IOW, very generally it is a first hop problem, just as most of the sorts of congestion that could probably happen. So before we make the protocol very complex, there's a minimum of deployment best practice to ensure that as many nodes as possible are one hop away from the root.

>From there, one could probably include the residual memory in the exposed metrics so that the OF accounts for it in the parent computation. Same goes for residual battery if you look at it, or for bandwidth for mesh networks where that's the most critical constraints. But you'll recognize the risk of Arpanet-like oscillations if nodes blindly move to the least loaded parent, and you'll have to figure ways to filter/dampen them out.

Finally you'll note that if you follow that path, a node might have children that also injected routes into it. So the node might need a certain amount of resources (bandwidth, battery, memory...) available from the parent in order to be able to attach to that parent with all its own children. If none of the parents have enough resources, what will the node do? Spread the load, probably? Drop/ push back some children as well? You see that rapidly, the complexity and potential instabilities overwhelm the benefits.

Cheers,

Pascal

From: [email-masked] [mailto:[email-masked]] On Behalf Of C Chauvenet
Sent: mercredi 2 novembre 2011 11:21
To: [email-masked]
Subject: [Roll] RPL behaviour with routing table overflow

Hi all, 

A question raised my mind  : How is RPL coping with downward routing table overflow ?

I think upward routing cannot lead to memory issues because we just need at least 1 entry for the best parent.

I think it is a strong point of the RPL design.

But we may have some memory issues with downward routing.

If we are using non storing mode, it is the DAGRoot job's and I assume DAGRoot of non storing RPL network won't have the memory limitations of LLNs.

But if we are using storing mode, what happen if my downward routing table is full, and I receive a DAO from a new Node ?

The first option I see is in the DAO-ACK, where the Status field could indicate that the requested node cannot act as a DAO Parent.

Then the DAO originator sends out another DAO to its 2nd best parent, and so on until its DAO is successfully acklowledged.

But then, how could that node know when there will be some space for it in the routing table of its best parent (Which should be the best route for downward routing) ? Do it need to send periodic DAO to its best parent ?

The second option I see is the use of the "O" flag in nthe NSA metric object defined in the RPL routing metric document.

This flag is used to advertise an Overflow, without too much precision about the meaning. I guess it is up to the implementor, which is flexible enough to handle various cases. Using this flag, nodes could know that a node advertising DIO with this flag set to 1 has no more space in its routing table and so prune it from their possible DAO parent list (thus saving useless DAO sendings).

The extreme case is : if I have no alternative DAO parent or No parent has some space for me, What should I do ??

Let expand this routing overflow issue to global downward routing : If I select a DAO parent which has some space for me in its routing table, what happen if my grand parent has not ? My grand parent will reject the DAO of my parent. My parent will follow the previous rules and try an alternative parent, but if it has no alternative parent what happen ? How could I know that my DAO has not been successfully delivered until the DAGroot (and so that I won't be reachable from the Root)? If I know it, I may be able to select an alternative DAO parent that could successfully registered my path until the DAGroot.

Of course one simple hypothesis could cope with these memory issues : Having a routing table size for each RPL router >= Total Number of  Nodes in the RPL network. But I guess this narrow the scalability to the most memory-limited router in the network...

I would enjoy to know what people do with these routing overflow, and have some guidelines about the RPL behaviour.

Best,

Cédric.

---

From: C Chauvenet <[email-masked]>
Date: Wed, 2 Nov 2011 06:19:50 -0700

Hi Pascal,

Thank you for your answer.

I think the final decision regarding this issue will be :

                - Do storing mode if you have enough memory
                - Do non storing mode if you don't or can't predict the number of Nodes in your network

Again, this is related to downward routing only, which is an optional feature of RPL.

Cédric.

De : Pascal Thubert (pthubert) [mailto:[email-masked]]
Envoyé : mercredi 2 novembre 2011 13:14
À : C Chauvenet; [email-masked]
Objet : RE: [Roll] RPL behaviour with routing table overflow

Hello Cedric:

Cheers,

Pascal

Hi all,

Best,
Cédric.

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Wed, 2 Nov 2011 15:02:53 +0100

Hello Cedric;

That's certainly right for an autonomic network that might take any form and shape.

For a more engineered network and operation, there are several aspects to the memory utilization, linked to how diversity is handled.

- Root diversity creates more and smaller DODAGS, each of which will require less memory. Can you throw more roots in? Where can they be placed to optimize distribution and reduce hops? If the distribution is perfect, the size of the routing table in each first hop router is divided by the number of roots.

- First hop diversity. You want to have enough first hop routers (FHR) so that the total number of routes gets divided between those. Can you make it so that the first hop is distributed well-enough that second hop routers have multiple potential parents and entries are fairly distributed between the first hop parents?

The size of the routing table in each first hop router is probably divided by a good portion of the number of first hop routers that depends for one thing on the fan out of the DAO routes.

- Time diversity. Do you need all entries all the time? If there's a sort of schedule by which meters can know when they should be reachable, then the meters only need to inject DAOs during that period. Again, in a perfect distribution, the size of the routing table in each first hop router is divided by the ratio of time that the end devices need to be reachable.

Talking an example to illustrate this; say you have 2400 devices that expect to be polled within a time window of less than one hour per day. As a result the address of a device needs only be present in the network for a 24th of the time. So at a given point of time there are only 100 routes in the network. Say you have 10 first hop routers and an expected fan out of 2, which means that there will be 2 first hop routers with a given DAO route. You can end up with 20 routes per FHR, if the distribution is perfect, and 10 routes if you add an second root.

Finally there are cases where aggregation can work for you. I think that there is a good opportunity for this group to work on aggregation schemes that would map existing deployments and would enable to compress either the RIBs or the advertisements.

Cheers,

Pascal

From: C Chauvenet [mailto:[email-masked]] 
Sent: mercredi 2 novembre 2011 14:20
To: Pascal Thubert (pthubert); [email-masked]
Subject: RE: [Roll] RPL behaviour with routing table overflow

Hi Pascal,

Cédric.

Hello Cedric:

Cheers,

Pascal

Hi all, 

Best,

Cédric.