Subject: [Roll] FW: outward routes and Destination Advertisements

From: "Roger K. Alexander" <[email-masked]>
Date: Wed, 9 Sep 2009 12:48:37 -0400

Some general thoughts...

Roger K Alexander

> -----Original Message-----
> From: [email-masked] [mailto:[email-masked]] On Behalf Of
> Richard Kelsey
> Sent: Tuesday, September 08, 2009 10:55 PM
> To: [email-masked]
> Subject: [Roll] outward routes and Destination Advertisements
> 
> RPL discovers outward routes by way of Destination
> Advertisements passed up the DAG.  Nodes that lack
> sufficient route storage add themselves to a route stack (a
> kind of route record).  Nodes that do have sufficient
> storage store the route stack and do not forward it upwards.
> 
> One issue is the potential for an explosion of Destination
> Advertisements if each router forwards each advertisement it
> receives to all of its parents.  Even if each node only
> forwards advertisements to a single parent the root may
> receive a great deal of redundant information, as the same
> links may appear in many route stacks.

I would assume that this is a desirable result so that there are redundant
outward routes from the root just as there are alternate routes from a node
to the root via multiple parents. Nodes receiving multiple DAs for a given
destination will filter the individual info received and advertised to their
associated parents.

> There are fundamentally three scenarios:
>   (1) root cannot store outward routes to all nodes
>   (2) sufficent route storage only on root
>   (3) route storage on root and possibly intermediate nodes
> The networks that I am familiar fall into either (1) or (2).
> 
> For (1), I think the only solution is to unicast record
> route/destination advertisements as needed.  It would be
> good if a DAG root could indicate that it was only capable
> of storing routes temporarily and that they should be
> reported on demand and as needed.

Since parents are explicitly selected, unicast DAs can be supported. Adding
capability info in the routing exchanges increases state and complexity. It
would be preferably to have a scheme in which the sending node's behavior in
uniform, though that could of course add unduly to overhead if the receiving
node cannot make use of the information. A general concern is the increasing
complexity of the protocol due to the accommodation of more and less capable
nodes. It would be better to have a means of defining more general
'application-specific (urban, industrial, etc.) domains' in which there is
an accepted framework for the capabilities of nodes. A personal worry is the
'all things to all domains' approach will continue to drive up protocol
complexity.

> 
> For (2), it would be more efficient for each node to send
> its set of parents to the root, rather than enumerating some
> or all of the possible paths using route stacks.  Changes in
> the parent set could be sent directly, without including any
> redundant, unchanged links.  This would eliminate the need
> for the Path Digest in RA-DIOs.
> 
> There is a problem with this approach in scenario (3), in
> that the parent information may be routed past intermediate
> nodes that would otherwise be able to store it.  This is
> very similar to the problem of deciding which parent to use
> when forwarding advertisements or P2P messages inward along
> a DAG.  You would like to make use of any intermediate route
> storage, but there is currently no way of determining which
> parent may have it.  It should be possible to indicate in
> the RA-DIO which parents should be sent Destination
> Advertisements, perhaps by including the depth of the
> deepest ancestor capable of storing routes.
> 
> In summary, I think we should:
>   - Replace the Destination Advertisement route stack with
>     a list of parents.  Destination Advertisements would be
>     sent to only a single parent.

Nodes should be allowed to maintain one or more ('explicit') parents to
which Destination Advertisements would be sent. This becomes the basis of
the DAG. It is not necessary to restrict to one parent. Nodes of course can
maintain one or more 'implicit' parents for purpose of DAG attachment but
these do not receive Das.

>   - Remove the Path Digest from RA-DIOS.
>   - Add an RA-DIO flag to indicate that the root does not
>     want Route Advertisements sent proactively.
>   - Add an RA-DIO field giving the depth of the deepest
>     ancestor capable of storing routes and preferentially
>     forward Route Advertisements via the parent with the
>     deepest such ancestor.
> 
> Yes?  No?  Thoughts?
>                               -Richard Kelsey
> _______________________________________________
> Roll mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/roll

---

From: Richard Kelsey <[email-masked]>
Date: Wed, 09 Sep 2009 13:11:22 -0400

From: "Roger K. Alexander" <[email-masked]>
   Date: Wed, 9 Sep 2009 12:48:37 -0400

   > links may appear in many route stacks.

   I would assume that this is a desirable result so that there is redundant
   outward routes from the root just as there are alternate routes from a node
   to the root via multiple parents. Nodes receiving multiple DAs for a given
   destination will filter the individual info received and advertised to their
   associated parents.

Nodes that do not have sufficient memory to store the routes
do not have sufficient memory to store the DAs needed to do
the filtering.  Such nodes just pass up the DAs as they
receive, after adding themselves to the route stacks.

Consider a DAG with two nodes at each level, each of which
chooses both nodes on the previous level as a parent.  The
two leaf nodes send a Destination Advertisement to both of
their parents.  Those parents each send 3 DAs to each of
their parents (their own plus the two received from the next
level down).  The next level sends 7 DAs each parent (their
own plus the 6 they each received).  It could quickly get
out of hand.

While I generally agree with you, I think that adding a
flag that suppresses the Routing Advertisements adds very
little overhead.

My preference would be to leave the Routing Advertisements
out of the core protocol entirely, as they are often not
needed.

I don't mean that nodes should only have one parent, just
that they should only send Destination Advertisements to
only one of their parents.
                                -Richard Kelsey

---

From: "Roger K. Alexander" <[email-masked]>
Date: Wed, 9 Sep 2009 13:27:48 -0400

> From: Richard Kelsey [mailto:[email-masked]]
> Sent: Wednesday, September 09, 2009 1:11 PM
> To: Roger K. Alexander
> Cc: [email-masked]
> Subject: Re: [Roll] FW: outward routes and Destination Advertisements
> 
Understood. The idea of filtering was for the nodes capable of maintaining
state. That is what would allow for the reduction in the DA overhead. If
nodes do not maintain state then indeed the flood of DAs does become an
issue.

> own plus the 6 they each received).  It could quickly get
With state information maintained, information aggregation and the phasing
with which DAs are received will avoid each DA at a leaf node resulting in a
DA to its parent and subsequent DAs further on to the root. Unless there is
a change of destination address there is no need for a DA to be passed up
towards the root. The lack of state information is in part what is driving
up the overhead. This is where my concern is with regard to RPL being so
universal in its applicability. It may be more efficient to consider domain
modes where these issues can be more appropriately addressed.