Subject: [Roll] RPL behaviour with routing table overflow

From: C Chauvenet <[email-masked]>
Date: Wed, 2 Nov 2011 03:20:49 -0700

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.