Subject: [Roll] no-Path DAO and fan-out

From: "Navneet Agarwal (navagar)" <[email-masked]>
Date: Fri, 9 Jul 2010 22:55:34 +0530

Hi WG:
I am trying to get some clarifications on expected behavior. Have read
the Path Control document on path ctl field usage (attached). I have put
several setups and flows, assuming storing nodes but should apply for
non-storing scenario as well. I could not figure out from the reading
the doc or the RFC.
 
Scenario-1:
 
A     B
\      /
 \   /
   C
  /  \
 /    \
D     E
 
A, B - DAO Parents.....C - Node........D,E- nodes in subdag.
Assume path control allows two paths.
D and E have learnt a common prefix for a node below them, Pfx
D will set x10 in Path control of DAO sent to C
E will set x01 in Path control of DAO sent to C
C will set x10 in Path control of DAO sent to A
C will set x01 in Path control of DAO sent to B
 
Suppose E sends a no-Path DAO to C for Pfx with path control x01. What
does C do? I would think that C will need to send a no-Path. But it has
to remember that it had sent a DAO with path control x01 to B. If this
has to happen then C would have to remember for each prefix what path
control was sent to which parent, which does not seem correct as it
would not scale as the prefixes at C scale, each having its own path
control settings.
 
Scenario-2:
 
F     G
\    /
 \  /
   A
    |
    |
   C
  /  \
 /    \
D     E
 
D will set x10 in Path control of DAO sent to C
E will set x01 in Path control of DAO sent to C
C will send a DAO with path control x11 to A
A will send a DAO with path control x01 to F
A will send a DAO with path control x10 to G
 
Suppose E sends a no-Path to C (path control x01). What does C do? It
will likely send a DAO to A with path control x10. What will A do when
it receives a DAO with this path control when its previous path control
was x11?
 
I see couple of other flows where path control settings may change due
to sub-nodes going away and coming back up...for example:
 
Scenario-3
 
F     G
\    /
 \  /
   A
    |
    |
   C
  /  \
 /    \
D     E
 
Suppose G is preferred over F.
Suppose path from E to D is down.
D sends DAO with path control x10 to C
C sends DAO with path control x10 to A
A sends DAO with path control x10 to G
 
After some time E comes up and sends a DAO with path control x01 (higher
path preference than D to C) to C.
C merges this and sends a DAO with path control x11 to A. What does A do
since is has indicated a path control of x10 to G. In normal terms, if A
had received a DAO with path control x11 from C, it would have notified
DAO to F with path control x10 and DAO to G with path control x01 but
due to transient conditions it could be reversed.
 
Will appreciate if it can be clarified if the above flows are reasonable
and what should happen...in general I dont think path control should
mandate which path control bits are tied to which DAO parent etc...
 
Thanks
 
Regards,
Navneet

---

From: "Alexander, Roger" <[email-masked]>
Date: Mon, 12 Jul 2010 18:55:59 -0400

Hi Navneet,

Thanks for the scenario examples which provide a good opportunity to
highlight/clarify the role of the Path Sequence in the DAO exchanges.
Below is an explanation of how I envisaged it would/should operate and
would also be interested in the WG's feedback. (Note: I am assuming your
reference to Prefix is as used in the generic RPL sense of identifying
an IPv6 destination address, prefix, or multicast group).

One advantage accruing to storing nodes, in addition to DAO aggregation,
is the ability to further reduce routing overhead by removing the
requirement for sub-DAG changes to always be conveyed all the way to the
root. In all of the scenarios you have defined, when a common ancestor
receives a no-Path DAO that is not originated by the Prefix owner (and
hence should not carry an incremented Path Sequence), there is no
requirement for that information to be conveyed beyond the common
ancestor (node C in your examples). Loss of downward path diversity
below the common ancestor does not mean that path diversity above needs
to be eliminated. Since the common ancestor still has a downward table
entry to the Prefix via alternate path(s), its ancestors do not need to
be further updated. With the maintained Path Sequence in the no-Path
DAO, only nodes that have a singular downward route to the affected
Prefix need to update their individual DAO Parent(s). Correspondingly,
only new or changed routing/path information that originates from the
Prefix owner and hence indicated by an incremented Path Sequence number
must always be passed along to the root. 

Note: The implementation option of limiting when the Path Sequence
number is incremented by a Prefix owner provides a capability to further
reduce routing overhead for storing nodes - though the few bits needed
to fully support incremental/partial updates within the DAO would be
still needed.

Where the transmission of the no-Path DAO is being proactively initiated
by a DAO Parent or other intermediate ancestor node that discovers the
loss of connectivity (neighbor unreachability detection, NUD) to the
node that owns the Prefix, the Path Sequence used in the no-Path DAO
will be the one maintained by the ancestor node (only the owner of the
Prefix can increment the Path Sequence for that Prefix). This would be
the same as the Path Sequence maintained by all nodes along the path to
the common ancestor. The first common ancestor receiving such a no-Path
DAO should mark the affected downward path for deletion and should take
no further action with regard to upward forwarding of the DAO. 

If the owner of the Prefix discovers the loss of connection to an
existing DAO Parent and wishes to update its path connections, including
potentially re-selecting a different preference set of DAO Parents, the
node must increment the Path Sequence and transmit DAOs to new desired
DAO Parents - a no-Path DAO is not required. The incremented Path
Sequence will necessitate that the updated DAOs be conveyed all the way
to the root - in the process updating routing tables at intermediate
nodes. Where new downward paths are established as a result of the
updated DAOs, existing intermediate routing tables are directly updated.
Routing table entries that are no longer on the re-established downward
paths will be purged through the normal expiration of the associated
downward route entries. 

Note: If the node that owns the Prefix chooses to maintain its existing
DAO Parents and preferences (even with the lost connectivity to, or
desired removal of, a single DAO Parent), it can do so by sending normal
periodic or triggered DAO updates to the connected DAO Parents without
incrementing the Path Sequence in the DAO updates. Where connectivity
exists, the owner of the Prefix may also send a no-Path DAO to delete
the path through a given DAO Parent. By not incrementing the Path
Sequence the path through the particular DAO Parent will be removed only
to the first common ancestor.

To redefine DAO Parents and preferences (including where necessary to
maintain fan-out limits), DAOs must be sent with an incremented Path
Sequence number to the newly desired/re-ordered DAO Parents. The
incremented Path Sequence DAOs will ensure that the routing change is
conveyed to the root and recognized by ancestor nodes that can delete
downward path entries. Where the updated DAOs are received at nodes that
do not currently have routing entries for the particular Prefix, the
information is cached and the new DAO information conveyed towards the
root.

Based on the above defined operation there is no benefit to the node
owner of the Prefix sending a no-Path DAO with an incremented Path
Sequence. This will travel all the way to the root and will have the
effect of outdating and marking for deletion all existing downward
routes for that Prefix. Instead, to re-establish desired downward paths,
DAOs with incremented Path Sequences should be sent to the
desired/maintained DAO Parents. 

There would be some benefit to being able to send a no-Path DAO to
delete a single DAO Parent path all the way to the root but the
incremented Path Sequence will make stale all other valid routing paths
(as well as introduce the difficulties raised in your assessments). Note
once again that multiple DAO Parents guarantee only local diversity.
Therefore the fact that deleting a single DAO Parent using an
un-incremented Path Sequence removes diversity only to a common ancestor
should be seen in the context of the local guarantees that are provided.

SUMMARY: If a no-Path DAO is sent by the Prefix owner to a connected DAO
Parent to delete the single downward path while maintaining the others,
the Path Sequence should be maintained (not incremented) indicating that
all established paths (and preferences) with the exception of the
identified DAO Parent path is being maintained. The path through the
particular DAO Parent, only to the first common ancestor, will be
deleted. Where the no-Path DAO is being proactively sent by an ancestor
node due to recognition of NUD, the same would apply as the Path
Sequence number will be the one currently maintained by the ancestor
node. The prefix owner should never send a no-Path DAO with an
incremented Path Sequence but should instead send updated DAOs with
incremented Path Sequence to re-establish or re-order DAO Parents and
downward paths.

The operation for non-storing nodes would be the same. However, in the
case of non-storing nodes the first common ancestor is always the root
node. If in the non-storing case a no-path DAO is issued by the owner of
the Prefix or by a DAO Parent (due to proactive response to NUD), the
no-Path DAO with an un-incremented Path Sequence will directly allow the
root to update existing downward paths (removing the identified DAO
Parent while maintaining ordering of remaining DAO Parents). As in the
storing case, a no-Path DAO with an incremented Path Sequence would mark
all other downward paths from the root as potentially outdated (and
marked for deletion) and so should similarly not be issued.

This is the operation as I believe it should work but I look forward to
understanding whether this envisaged operation can fit within the model
given in -10. 

Make sense? See also a specific related comment below.

Regards,

Roger

From: [email-masked] [mailto:[email-masked]] On Behalf Of
Navneet Agarwal (navagar)
Sent: Friday, July 09, 2010 1:26 PM
To: ROLL WG
Subject: [Roll] no-Path DAO and fan-out

Hi WG:

Scenario-1:

A     B

\      /

 \   /

   C

  /  \

 /    \

D     E

Scenario-2:

F     G

\    /

 \  /

   A

    |

    |

   C

  /  \

 /    \

D     E

Scenario-3

F     G

\    /

 \  /

   A

    |

    |

   C

  /  \

 /    \

D     E

 

[RA] In the case of receipt of the first updated DAO (with incremented
Path Sequence) only the new information with single path control should
be forwarded since all prior path information is effectively obsolete by
the incremented Path Sequence. When subsequent DAO updates are received
with the new, incremented Path Sequence, only then can the combined path
control information be forwarded.

[RA] Hopefully the above discussion supports the view that Path Control
can operate as specified without the need to maintain state on which DAO
with which Path Control was sent to which DAO Parent.

Thanks

Regards,

Navneet

---

From: "Navneet Agarwal (navagar)" <[email-masked]>
Date: Tue, 13 Jul 2010 22:46:43 +0530

Hi Alexander:
Thanks a lot for the detailed explanation...appreciate it...this helps
clears the path control operation.
 
I think it would be good if some additional text related to below is
added to the RFC.
 
Some comments:
 
1.  "Correspondingly, only new or changed routing/path information that
originates from the Prefix owner and hence indicated by an incremented
Path Sequence number must always be passed along to the root." 
I guess this should apply to all DAOs (Path as well as no-Path). I do
see some issues when a node has multiple DAO parents and they are
received and processed at a common ancestor.
2. On a related topic, since there is a preference associated with each
path for a prefix, a node does not allow for loadbalancing if there are
multiple paths reported for a prefix. Right?
 
Thx
 
Regards,
Navneet

________________________________

	From: Alexander, Roger
[mailto:[email-masked]] 
	Sent: Tuesday, July 13, 2010 8:25 AM
	To: Navneet Agarwal (navagar); ROLL WG
	Subject: RE: [Roll] no-Path DAO and fan-out

	Hi Navneet,

	Thanks for the scenario examples which provide a good
opportunity to highlight/clarify the role of the Path Sequence in the
DAO exchanges. Below is an explanation of how I envisaged it
would/should operate and would also be interested in the WG's feedback.
(Note: I am assuming your reference to Prefix is as used in the generic
RPL sense of identifying an IPv6 destination address, prefix, or
multicast group).  
	
	One advantage accruing to storing nodes, in addition to DAO
aggregation, is the ability to further reduce routing overhead by
removing the requirement for sub-DAG changes to always be conveyed all
the way to the root. In all of the scenarios you have defined, when a
common ancestor receives a no-Path DAO that is not originated by the
Prefix owner (and hence should not carry an incremented Path Sequence),
there is no requirement for that information to be conveyed beyond the
common ancestor (node C in your examples). Loss of downward path
diversity below the common ancestor does not mean that path diversity
above needs to be eliminated. Since the common ancestor still has a
downward table entry to the Prefix via alternate path(s), its ancestors
do not need to be further updated. With the maintained Path Sequence in
the no-Path DAO, only nodes that have a singular downward route to the
affected Prefix need to update their individual DAO Parent(s).
Correspondingly, only new or changed routing/path information that
originates from the Prefix owner and hence indicated by an incremented
Path Sequence number must always be passed along to the root.

	Note: The implementation option of limiting when the Path
Sequence number is incremented by a Prefix owner provides a capability
to further reduce routing overhead for storing nodes - though the few
bits needed to fully support incremental/partial updates within the DAO
would be still needed.

	Where the transmission of the no-Path DAO is being proactively
initiated by a DAO Parent or other intermediate ancestor node that
discovers the loss of connectivity (neighbor unreachability detection,
NUD) to the node that owns the Prefix, the Path Sequence used in the
no-Path DAO will be the one maintained by the ancestor node (only the
owner of the Prefix can increment the Path Sequence for that Prefix).
This would be the same as the Path Sequence maintained by all nodes
along the path to the common ancestor. The first common ancestor
receiving such a no-Path DAO should mark the affected downward path for
deletion and should take no further action with regard to upward
forwarding of the DAO.

	If the owner of the Prefix discovers the loss of connection to
an existing DAO Parent and wishes to update its path connections,
including potentially re-selecting a different preference set of DAO
Parents, the node must increment the Path Sequence and transmit DAOs to
new desired DAO Parents - a no-Path DAO is not required. The incremented
Path Sequence will necessitate that the updated DAOs be conveyed all the
way to the root - in the process updating routing tables at intermediate
nodes. Where new downward paths are established as a result of the
updated DAOs, existing intermediate routing tables are directly updated.
Routing table entries that are no longer on the re-established downward
paths will be purged through the normal expiration of the associated
downward route entries.

	Note: If the node that owns the Prefix chooses to maintain its
existing DAO Parents and preferences (even with the lost connectivity
to, or desired removal of, a single DAO Parent), it can do so by sending
normal periodic or triggered DAO updates to the connected DAO Parents
without incrementing the Path Sequence in the DAO updates. Where
connectivity exists, the owner of the Prefix may also send a no-Path DAO
to delete the path through a given DAO Parent. By not incrementing the
Path Sequence the path through the particular DAO Parent will be removed
only to the first common ancestor.

	To redefine DAO Parents and preferences (including where
necessary to maintain fan-out limits), DAOs must be sent with an
incremented Path Sequence number to the newly desired/re-ordered DAO
Parents. The incremented Path Sequence DAOs will ensure that the routing
change is conveyed to the root and recognized by ancestor nodes that can
delete downward path entries. Where the updated DAOs are received at
nodes that do not currently have routing entries for the particular
Prefix, the information is cached and the new DAO information conveyed
towards the root.

	Based on the above defined operation there is no benefit to the
node owner of the Prefix sending a no-Path DAO with an incremented Path
Sequence. This will travel all the way to the root and will have the
effect of outdating and marking for deletion all existing downward
routes for that Prefix. Instead, to re-establish desired downward paths,
DAOs with incremented Path Sequences should be sent to the
desired/maintained DAO Parents.

	There would be some benefit to being able to send a no-Path DAO
to delete a single DAO Parent path all the way to the root but the
incremented Path Sequence will make stale all other valid routing paths
(as well as introduce the difficulties raised in your assessments). Note
once again that multiple DAO Parents guarantee only local diversity.
Therefore the fact that deleting a single DAO Parent using an
un-incremented Path Sequence removes diversity only to a common ancestor
should be seen in the context of the local guarantees that are provided.

	SUMMARY: If a no-Path DAO is sent by the Prefix owner to a
connected DAO Parent to delete the single downward path while
maintaining the others, the Path Sequence should be maintained (not
incremented) indicating that all established paths (and preferences)
with the exception of the identified DAO Parent path is being
maintained. The path through the particular DAO Parent, only to the
first common ancestor, will be deleted. Where the no-Path DAO is being
proactively sent by an ancestor node due to recognition of NUD, the same
would apply as the Path Sequence number will be the one currently
maintained by the ancestor node. The prefix owner should never send a
no-Path DAO with an incremented Path Sequence but should instead send
updated DAOs with incremented Path Sequence to re-establish or re-order
DAO Parents and downward paths.

	The operation for non-storing nodes would be the same. However,
in the case of non-storing nodes the first common ancestor is always the
root node. If in the non-storing case a no-path DAO is issued by the
owner of the Prefix or by a DAO Parent (due to proactive response to
NUD), the no-Path DAO with an un-incremented Path Sequence will directly
allow the root to update existing downward paths (removing the
identified DAO Parent while maintaining ordering of remaining DAO
Parents). As in the storing case, a no-Path DAO with an incremented Path
Sequence would mark all other downward paths from the root as
potentially outdated (and marked for deletion) and so should similarly
not be issued.

	This is the operation as I believe it should work but I look
forward to understanding whether this envisaged operation can fit within
the model given in -10.

	
	Regards,

	Roger

	From: [email-masked] [mailto:[email-masked]
<mailto:[email-masked]> ] On Behalf Of Navneet Agarwal (navagar)
	Sent: Friday, July 09, 2010 1:26 PM
	To: ROLL WG
	Subject: [Roll] no-Path DAO and fan-out

	Hi WG:
	I am trying to get some clarifications on expected behavior.
Have read the Path Control document on path ctl field usage (attached).
I have put several setups and flows, assuming storing nodes but should
apply for non-storing scenario as well. I could not figure out from the
reading the doc or the RFC.

	Scenario-1:

	A     B
	
	\      /
	
	 \   /
	
	   C
	
	  /  \
	
	 /    \
	
	D     E

	

	

	
	Suppose E sends a no-Path DAO to C for Pfx with path control
x01. What does C do? I would think that C will need to send a no-Path.
But it has to remember that it had sent a DAO with path control x01 to
B. If this has to happen then C would have to remember for each prefix
what path control was sent to which parent, which does not seem correct
as it would not scale as the prefixes at C scale, each having its own
path control settings.

	Scenario-2:

	F     G
	
	\    /
	
	 \  /
	
	   A
	
	    |
	
	    |
	
	   C
	
	  /  \
	
	 /    \
	
	D     E

	

	

	Suppose E sends a no-Path to C (path control x01). What does C
do? It will likely send a DAO to A with path control x10. What will A do
when it receives a DAO with this path control when its previous path
control was x11?

	I see couple of other flows where path control settings may
change due to sub-nodes going away and coming back up...for example:

	Scenario-3

	F     G
	
	\    /
	
	 \  /
	
	   A
	
	    |
	
	    |
	
	   C
	
	  /  \
	
	 /    \
	
	D     E

	

	

	After some time E comes up and sends a DAO with path control x01
(higher path preference than D to C) to C.
	
	C merges this and sends a DAO with path control x11 to A. What
does A do since is has indicated a path control of x10 to G. In normal
terms, if A had received a DAO with path control x11 from C, it would
have notified DAO to F with path control x10 and DAO to G with path
control x01 but due to transient conditions it could be reversed.

	[RA] In the case of receipt of the first updated DAO (with
incremented Path Sequence) only the new information with single path
control should be forwarded since all prior path information is
effectively obsolete by the incremented Path Sequence. When subsequent
DAO updates are received with the new, incremented Path Sequence, only
then can the combined path control information be forwarded.

	Will appreciate if it can be clarified if the above flows are
reasonable and what should happen...in general I dont think path control
should mandate which path control bits are tied to which DAO parent
etc...

	[RA] Hopefully the above discussion supports the view that Path
Control can operate as specified without the need to maintain state on
which DAO with which Path Control was sent to which DAO Parent.

	Thanks

	Regards,
	
	Navneet

---

From: "Alexander, Roger" <[email-masked]>
Date: Tue, 13 Jul 2010 23:29:58 -0400

Hi Navneet,

See additional comments below.
 
Regards,

Roger 

-----Original Message-----
From: Navneet Agarwal (navagar) [mailto:[email-masked]]
Sent: Tue 7/13/2010 1:16 PM
To: Alexander, Roger; ROLL WG
Subject: RE: [Roll] no-Path DAO and fan-out
 
Hi Alexander:
Thanks a lot for the detailed explanation...appreciate it...this helps clears the path control operation.
 
I think it would be good if some additional text related to below is added to the RFC.
 
Some comments:
 
1.  "Correspondingly, only new or changed routing/path information that originates from the Prefix owner and hence indicated by an incremented Path Sequence number must always be passed along to the root." 

[RA] Agreed. More generally “any new or changed routing/path information that is received at a node must be passed to its DAO Parent(s)”. In addition to incremented Path Sequence that new information may include an existing Prefix with an unchanged Path Sequence but with different Path Control bits.

I guess this should apply to all DAOs (Path as well as no-Path). 
[RA] Agreed.

I do see some issues when a node has multiple DAO parents and they are received and processed at a common ancestor.

[RA] There may be issues related to dynamic changes in the DAO Parent set of an ancestor node but these should be transient and normalized in the course of subsequent DAO updates (with and without incremented Path Sequence) - where a common ancestor receiving the very same DAO information from multiple children maintains the most recent update.
 
Where a common ancestor receives DAOs along different paths from a node with multiple DAO Parents a consistent rule will ensure that assignments can be made without needing to maintain per-DAO state information. As an implementation choice, a node can maintain a fixed-assignment rule in which DAOs with particular path control bits set are always divided across the existing DAO Parent set in a given way. For example, if the node has 2 DAO Parents and a maximum path control size (PCS) of 4 is configured for the DODAG, any DAO with one or more of the two highest preference path control bits set are always assigned to the higher preference DAO Parent; DAOs with the lower preference path control bits sets are propagated to the other DAO Parent. Correspondingly, DAOs with more than 2 path control bits set will be split across the two DAO Parents with higher order path control bits set in the DAO send to the higher preference DAO Parent. Each node will apply a fixed-assignment rule according to its current number of DAO Parents and the DODAG PSC. Thus even as multiple DAOs arrive with different delays at a common ancestor, each is received and asynchronously assigned according to the fixed-assignment rule. Where a later arriving DAO is to be sent to a DAO Parent to which an earlier DAO has been propagated, the path control bits are aggregated representing the new combined information and the new DAO propagated forward.
    
Note: Other fixed-assignment rules may also be possible. For example, the highest preference path control DAO assigned to the highest preference DAO Parent and all other PSC-allowed path control DAOs distributed across the remaining DAO Parents. 

2. On a related topic, since there is a preference associated with each path for a prefix, a node does not allow for loadbalancing if there are multiple paths reported for a prefix. Right?

[RA] Downward path load balancing at a common ancestor is still possible for a given prefix though that load balancing need not be uniform. It can be weighted where the preferred path (single Parent, tree-equivalent path) is one of the next hop options, or it can be uniform where the preferred path is not a member of the next hop options. Load balancing can also consider diversity that may be derived from the number of paths (path control bits) associated with a given next hop route.  As indicated in the original note, path control only guarantees that the preferred path can always be distinguished from others. Th preference ordering of other paths are softer and more loosely maintained as a function of the local application of preference.

Thx
 
Regards,
Navneet

	From: Alexander, Roger [mailto:[email-masked]] 
	Sent: Tuesday, July 13, 2010 8:25 AM
	To: Navneet Agarwal (navagar); ROLL WG
	Subject: RE: [Roll] no-Path DAO and fan-out

	Hi Navneet,

	Thanks for the scenario examples which provide a good opportunity to highlight/clarify the role of the Path Sequence in the DAO exchanges. Below is an explanation of how I envisaged it would/should operate and would also be interested in the WG's feedback. (Note: I am assuming your reference to Prefix is as used in the generic RPL sense of identifying an IPv6 destination address, prefix, or multicast group).  
	
	One advantage accruing to storing nodes, in addition to DAO aggregation, is the ability to further reduce routing overhead by removing the requirement for sub-DAG changes to always be conveyed all the way to the root. In all of the scenarios you have defined, when a common ancestor receives a no-Path DAO that is not originated by the Prefix owner (and hence should not carry an incremented Path Sequence), there is no requirement for that information to be conveyed beyond the common ancestor (node C in your examples). Loss of downward path diversity below the common ancestor does not mean that path diversity above needs to be eliminated. Since the common ancestor still has a downward table entry to the Prefix via alternate path(s), its ancestors do not need to be further updated. With the maintained Path Sequence in the no-Path DAO, only nodes that have a singular downward route to the affected Prefix need to update their individual DAO Parent(s). Correspondingly, only new or changed routing/path information that originates from the Prefix owner and hence indicated by an incremented Path Sequence number must always be passed along to the root.

	Note: The implementation option of limiting when the Path Sequence number is incremented by a Prefix owner provides a capability to further reduce routing overhead for storing nodes - though the few bits needed to fully support incremental/partial updates within the DAO would be still needed.

	Where the transmission of the no-Path DAO is being proactively initiated by a DAO Parent or other intermediate ancestor node that discovers the loss of connectivity (neighbor unreachability detection, NUD) to the node that owns the Prefix, the Path Sequence used in the no-Path DAO will be the one maintained by the ancestor node (only the owner of the Prefix can increment the Path Sequence for that Prefix). This would be the same as the Path Sequence maintained by all nodes along the path to the common ancestor. The first common ancestor receiving such a no-Path DAO should mark the affected downward path for deletion and should take no further action with regard to upward forwarding of the DAO.

	If the owner of the Prefix discovers the loss of connection to an existing DAO Parent and wishes to update its path connections, including potentially re-selecting a different preference set of DAO Parents, the node must increment the Path Sequence and transmit DAOs to new desired DAO Parents - a no-Path DAO is not required. The incremented Path Sequence will necessitate that the updated DAOs be conveyed all the way to the root - in the process updating routing tables at intermediate nodes. Where new downward paths are established as a result of the updated DAOs, existing intermediate routing tables are directly updated. Routing table entries that are no longer on the re-established downward paths will be purged through the normal expiration of the associated downward route entries.

	Note: If the node that owns the Prefix chooses to maintain its existing DAO Parents and preferences (even with the lost connectivity to, or desired removal of, a single DAO Parent), it can do so by sending normal periodic or triggered DAO updates to the connected DAO Parents without incrementing the Path Sequence in the DAO updates. Where connectivity exists, the owner of the Prefix may also send a no-Path DAO to delete the path through a given DAO Parent. By not incrementing the Path Sequence the path through the particular DAO Parent will be removed only to the first common ancestor.

	To redefine DAO Parents and preferences (including where necessary to maintain fan-out limits), DAOs must be sent with an incremented Path Sequence number to the newly desired/re-ordered DAO Parents. The incremented Path Sequence DAOs will ensure that the routing change is conveyed to the root and recognized by ancestor nodes that can delete downward path entries. Where the updated DAOs are received at nodes that do not currently have routing entries for the particular Prefix, the information is cached and the new DAO information conveyed towards the root.

	Based on the above defined operation there is no benefit to the node owner of the Prefix sending a no-Path DAO with an incremented Path Sequence. This will travel all the way to the root and will have the effect of outdating and marking for deletion all existing downward routes for that Prefix. Instead, to re-establish desired downward paths, DAOs with incremented Path Sequences should be sent to the desired/maintained DAO Parents.

	There would be some benefit to being able to send a no-Path DAO to delete a single DAO Parent path all the way to the root but the incremented Path Sequence will make stale all other valid routing paths (as well as introduce the difficulties raised in your assessments). Note once again that multiple DAO Parents guarantee only local diversity. Therefore the fact that deleting a single DAO Parent using an un-incremented Path Sequence removes diversity only to a common ancestor should be seen in the context of the local guarantees that are provided.

	SUMMARY: If a no-Path DAO is sent by the Prefix owner to a connected DAO Parent to delete the single downward path while maintaining the others, the Path Sequence should be maintained (not incremented) indicating that all established paths (and preferences) with the exception of the identified DAO Parent path is being maintained. The path through the particular DAO Parent, only to the first common ancestor, will be deleted. Where the no-Path DAO is being proactively sent by an ancestor node due to recognition of NUD, the same would apply as the Path Sequence number will be the one currently maintained by the ancestor node. The prefix owner should never send a no-Path DAO with an incremented Path Sequence but should instead send updated DAOs with incremented Path Sequence to re-establish or re-order DAO Parents and downward paths.

	The operation for non-storing nodes would be the same. However, in the case of non-storing nodes the first common ancestor is always the root node. If in the non-storing case a no-path DAO is issued by the owner of the Prefix or by a DAO Parent (due to proactive response to NUD), the no-Path DAO with an un-incremented Path Sequence will directly allow the root to update existing downward paths (removing the identified DAO Parent while maintaining ordering of remaining DAO Parents). As in the storing case, a no-Path DAO with an incremented Path Sequence would mark all other downward paths from the root as potentially outdated (and marked for deletion) and so should similarly not be issued.

	This is the operation as I believe it should work but I look forward to understanding whether this envisaged operation can fit within the model given in -10.

	
	Regards,

	Roger

	From: [email-masked] [mailto:[email-masked] <mailto:[email-masked]> ] On Behalf Of Navneet Agarwal (navagar)
	Sent: Friday, July 09, 2010 1:26 PM
	To: ROLL WG
	Subject: [Roll] no-Path DAO and fan-out

	Hi WG:
	I am trying to get some clarifications on expected behavior. Have read the Path Control document on path ctl field usage (attached). I have put several setups and flows, assuming storing nodes but should apply for non-storing scenario as well. I could not figure out from the reading the doc or the RFC.

	Scenario-1:

	A     B
	
	\      /
	
	 \   /
	
	   C
	
	  /  \
	
	 /    \
	
	D     E

	

	

	
	Suppose E sends a no-Path DAO to C for Pfx with path control x01. What does C do? I would think that C will need to send a no-Path. But it has to remember that it had sent a DAO with path control x01 to B. If this has to happen then C would have to remember for each prefix what path control was sent to which parent, which does not seem correct as it would not scale as the prefixes at C scale, each having its own path control settings.

	Scenario-2:

	F     G
	
	\    /
	
	 \  /
	
	   A
	
	    |
	
	    |
	
	   C
	
	  /  \
	
	 /    \
	
	D     E

	

	

	Suppose E sends a no-Path to C (path control x01). What does C do? It will likely send a DAO to A with path control x10. What will A do when it receives a DAO with this path control when its previous path control was x11?

	I see couple of other flows where path control settings may change due to sub-nodes going away and coming back up...for example:

	Scenario-3

	F     G
	
	\    /
	
	 \  /
	
	   A
	
	    |
	
	    |
	
	   C
	
	  /  \
	
	 /    \
	
	D     E

	

	

	After some time E comes up and sends a DAO with path control x01 (higher path preference than D to C) to C.
	
	C merges this and sends a DAO with path control x11 to A. What does A do since is has indicated a path control of x10 to G. In normal terms, if A had received a DAO with path control x11 from C, it would have notified DAO to F with path control x10 and DAO to G with path control x01 but due to transient conditions it could be reversed.

	[RA] In the case of receipt of the first updated DAO (with incremented Path Sequence) only the new information with single path control should be forwarded since all prior path information is effectively obsolete by the incremented Path Sequence. When subsequent DAO updates are received with the new, incremented Path Sequence, only then can the combined path control information be forwarded.

	Will appreciate if it can be clarified if the above flows are reasonable and what should happen...in general I dont think path control should mandate which path control bits are tied to which DAO parent etc...

	[RA] Hopefully the above discussion supports the view that Path Control can operate as specified without the need to maintain state on which DAO with which Path Control was sent to which DAO Parent.

	Thanks

	Regards,
	
	Navneet

---

From: "Navneet Agarwal (navagar)" <[email-masked]>
Date: Wed, 14 Jul 2010 22:09:26 +0530

Hi Roger:
Pls see my comments below...
 
Thanks
 
Regards,
Navneet

	From: Alexander, Roger
[mailto:[email-masked]] 
	Sent: Wednesday, July 14, 2010 9:00 AM
	To: Navneet Agarwal (navagar); ROLL WG
	Subject: RE: [Roll] no-Path DAO and fan-out

	Hi Navneet,

	Regards,
	
	Roger

	-----Original Message-----
	From: Navneet Agarwal (navagar) [mailto:[email-masked]
<mailto:[email-masked]> ]
	Sent: Tue 7/13/2010 1:16 PM
	To: Alexander, Roger; ROLL WG
	Subject: RE: [Roll] no-Path DAO and fan-out
	
	Hi Alexander:
	Thanks a lot for the detailed explanation...appreciate it...this
helps clears the path control operation.
	
	I think it would be good if some additional text related to
below is added to the RFC.
	
	Some comments:
	
	1.  "Correspondingly, only new or changed routing/path
information that originates from the Prefix owner and hence indicated by
an incremented Path Sequence number must always be passed along to the
root."
	
	[RA] Agreed. More generally "any new or changed routing/path
information that is received at a node must be passed to its DAO
Parent(s)". In addition to incremented Path Sequence that new
information may include an existing Prefix with an unchanged Path
Sequence but with different Path Control bits.

	I do see some issues when a node has multiple DAO parents and
they are received and processed at a common ancestor.
	
	[RA] There may be issues related to dynamic changes in the DAO
Parent set of an ancestor node but these should be transient and
normalized in the course of subsequent DAO updates (with and without
incremented Path Sequence) - where a common ancestor receiving the very
same DAO information from multiple children maintains the most recent
update.
	
	Where a common ancestor receives DAOs along different paths from
a node with multiple DAO Parents a consistent rule will ensure that
assignments can be made without needing to maintain per-DAO state
information. As an implementation choice, a node can maintain a
fixed-assignment rule in which DAOs with particular path control bits
set are always divided across the existing DAO Parent set in a given
way. For example, if the node has 2 DAO Parents and a maximum path
control size (PCS) of 4 is configured for the DODAG, any DAO with one or
more of the two highest preference path control bits set are always
assigned to the higher preference DAO Parent; DAOs with the lower
preference path control bits sets are propagated to the other DAO
Parent. Correspondingly, DAOs with more than 2 path control bits set
will be split across the two DAO Parents with higher order path control
bits set in the DAO send to the higher preference DAO Parent. Each node
will apply a fixed-assignment rule according to its current number of
DAO Parents and the DODAG PSC. Thus even as multiple DAOs arrive with
different delays at a common ancestor, each is received and
asynchronously assigned according to the fixed-assignment rule. Where a
later arriving DAO is to be sent to a DAO Parent to which an earlier DAO
has been propagated, the path control bits are aggregated representing
the new combined information and the new DAO propagated forward.
	   
	Note: Other fixed-assignment rules may also be possible. For
example, the highest preference path control DAO assigned to the highest
preference DAO Parent and all other PSC-allowed path control DAOs
distributed across the remaining DAO Parents.
	NAV>  I think there may be a need for defining a mask to
identify the fixed-assignment rule you described above, especially in
cases where a node is more than 1-bit in the path control set. This
would help the common ancestor node receiving the individual DAO
messages from the nodes below to figure out the width of the path
control bits in the received DAO(s) for aggregation. For example, if
there are two nodes below a common ancestor and are using 2-bits per DAO
parent as the assignment rule, they may send DAOs with bit settings as
b'01' and b'10'. The common ancestor would somehow need to know to
aggregate this as b'1001' otherwise it may just aggregate it as b'01' |
b'10' == b'11'.
	
	2. On a related topic, since there is a preference associated
with each path for a prefix, a node does not allow for loadbalancing if
there are multiple paths reported for a prefix. Right?
	
	[RA] Downward path load balancing at a common ancestor is still
possible for a given prefix though that load balancing need not be
uniform.  

	NAV> I see...makes sense.

	 It can be weighted where the preferred path (single Parent,
tree-equivalent path) is one of the next hop options, or it can be
uniform where the preferred path is not a member of the next hop
options. Load balancing can also consider diversity that may be derived
from the number of paths (path control bits) associated with a given
next hop route.  As indicated in the original note, path control only
guarantees that the preferred path can always be distinguished from
others. Th preference ordering of other paths are softer and more
loosely maintained as a function of the local application of preference.
	 NAV> I did not understand this part....are you saying that load
balancing can be weighted along the lines of the path preference or it
can be made uniform across all paths, ignoring the path preference?

	Thx

	Regards,

	Navneet 

	Thx
	
	Regards,
	Navneet

	        From: Alexander, Roger
[mailto:[email-masked]
<mailto:[email-masked]> ]
	        Sent: Tuesday, July 13, 2010 8:25 AM
	        To: Navneet Agarwal (navagar); ROLL WG
	        Subject: RE: [Roll] no-Path DAO and fan-out

	        Hi Navneet,

	       
	        One advantage accruing to storing nodes, in addition to
DAO aggregation, is the ability to further reduce routing overhead by

	        Note: The implementation option of limiting when the
Path Sequence number is incremented by a Prefix owner provides a
capability to further reduce routing overhead for storing nodes - though
the few bits needed to fully support incremental/partial updates within
the DAO would be still needed.

	        Where the transmission of the no-Path DAO is being
proactively initiated by a DAO Parent or other intermediate ancestor
node that discovers the loss of connectivity (neighbor unreachability
detection, NUD) to the node that owns the Prefix, the Path Sequence used
in the no-Path DAO will be the one maintained by the ancestor node (only
the owner of the Prefix can increment the Path Sequence for that
Prefix). This would be the same as the Path Sequence maintained by all
nodes along the path to the common ancestor. The first common ancestor
receiving such a no-Path DAO should mark the affected downward path for
deletion and should take no further action with regard to upward
forwarding of the DAO.

	        If the owner of the Prefix discovers the loss of
connection to an existing DAO Parent and wishes to update its path
connections, including potentially re-selecting a different preference
set of DAO Parents, the node must increment the Path Sequence and
transmit DAOs to new desired DAO Parents - a no-Path DAO is not
required. The incremented Path Sequence will necessitate that the
updated DAOs be conveyed all the way to the root - in the process
updating routing tables at intermediate nodes. Where new downward paths
are established as a result of the updated DAOs, existing intermediate
routing tables are directly updated. Routing table entries that are no
longer on the re-established downward paths will be purged through the
normal expiration of the associated downward route entries.

	        Note: If the node that owns the Prefix chooses to
maintain its existing DAO Parents and preferences (even with the lost
connectivity to, or desired removal of, a single DAO Parent), it can do
so by sending normal periodic or triggered DAO updates to the connected
DAO Parents without incrementing the Path Sequence in the DAO updates.
Where connectivity exists, the owner of the Prefix may also send a
no-Path DAO to delete the path through a given DAO Parent. By not
incrementing the Path Sequence the path through the particular DAO
Parent will be removed only to the first common ancestor.

	       
	        Based on the above defined operation there is no benefit
to the node owner of the Prefix sending a no-Path DAO with an
incremented Path Sequence. This will travel all the way to the root and
will have the effect of outdating and marking for deletion all existing
downward routes for that Prefix. Instead, to re-establish desired
downward paths, DAOs with incremented Path Sequences should be sent to
the desired/maintained DAO Parents.

	        There would be some benefit to being able to send a
no-Path DAO to delete a single DAO Parent path all the way to the root
but the incremented Path Sequence will make stale all other valid
routing paths (as well as introduce the difficulties raised in your
assessments). Note once again that multiple DAO Parents guarantee only
local diversity. Therefore the fact that deleting a single DAO Parent
using an un-incremented Path Sequence removes diversity only to a common
ancestor should be seen in the context of the local guarantees that are
provided.

	        SUMMARY: If a no-Path DAO is sent by the Prefix owner to
a connected DAO Parent to delete the single downward path while

	        The operation for non-storing nodes would be the same.
However, in the case of non-storing nodes the first common ancestor is
always the root node. If in the non-storing case a no-path DAO is issued
by the owner of the Prefix or by a DAO Parent (due to proactive response
to NUD), the no-Path DAO with an un-incremented Path Sequence will
directly allow the root to update existing downward paths (removing the
identified DAO Parent while maintaining ordering of remaining DAO
Parents). As in the storing case, a no-Path DAO with an incremented Path
Sequence would mark all other downward paths from the root as
potentially outdated (and marked for deletion) and so should similarly
not be issued.

	        This is the operation as I believe it should work but I
look forward to understanding whether this envisaged operation can fit
within the model given in -10.

	       
	        Regards,

	        Roger

	        From: [email-masked]
[mailto:[email-masked] <mailto:[email-masked]>
<mailto:[email-masked] <mailto:[email-masked]> > ] On
Behalf Of Navneet Agarwal (navagar)
	        Sent: Friday, July 09, 2010 1:26 PM
	        To: ROLL WG
	        Subject: [Roll] no-Path DAO and fan-out

	        Hi WG:
	        I am trying to get some clarifications on expected
behavior. Have read the Path Control document on path ctl field usage
(attached). I have put several setups and flows, assuming storing nodes
but should apply for non-storing scenario as well. I could not figure
out from the reading the doc or the RFC.

	        Scenario-1:

	        A     B
	       
	        \      /
	       
	         \   /
	       
	           C
	       
	          /  \
	       
	         /    \
	       
	        D     E

	        A, B - DAO Parents.....C - Node........D,E- nodes in
subdag.

	        D and E have learnt a common prefix for a node below
them, Pfx

	       

	       
	        Suppose E sends a no-Path DAO to C for Pfx with path
control x01. What does C do? I would think that C will need to send a
no-Path. But it has to remember that it had sent a DAO with path control
x01 to B. If this has to happen then C would have to remember for each
prefix what path control was sent to which parent, which does not seem
correct as it would not scale as the prefixes at C scale, each having
its own path control settings.

	        Scenario-2:

	        F     G
	       
	        \    /
	       
	         \  /
	       
	           A
	       
	            |
	       
	            |
	       
	           C
	       
	          /  \
	       
	         /    \
	       
	        D     E

	       

	       

	        Suppose E sends a no-Path to C (path control x01). What
does C do? It will likely send a DAO to A with path control x10. What
will A do when it receives a DAO with this path control when its
previous path control was x11?

	        I see couple of other flows where path control settings
may change due to sub-nodes going away and coming back up...for example:

	        Scenario-3

	        F     G
	       
	        \    /
	       
	         \  /
	       
	           A
	       
	            |
	       
	            |
	       
	           C
	       
	          /  \
	       
	         /    \
	       
	        D     E

	       

	       

	        After some time E comes up and sends a DAO with path
control x01 (higher path preference than D to C) to C.
	       
	        C merges this and sends a DAO with path control x11 to
A. What does A do since is has indicated a path control of x10 to G. In
normal terms, if A had received a DAO with path control x11 from C, it
would have notified DAO to F with path control x10 and DAO to G with
path control x01 but due to transient conditions it could be reversed.

	        [RA] In the case of receipt of the first updated DAO
(with incremented Path Sequence) only the new information with single
path control should be forwarded since all prior path information is
effectively obsolete by the incremented Path Sequence. When subsequent
DAO updates are received with the new, incremented Path Sequence, only
then can the combined path control information be forwarded.

	        Will appreciate if it can be clarified if the above
flows are reasonable and what should happen...in general I dont think
path control should mandate which path control bits are tied to which
DAO parent etc...

	        [RA] Hopefully the above discussion supports the view
that Path Control can operate as specified without the need to maintain
state on which DAO with which Path Control was sent to which DAO Parent.

	        Thanks

	        Regards,
	       
	        Navneet

---

From: "Alexander, Roger" <[email-masked]>
Date: Wed, 14 Jul 2010 16:27:01 -0400

Hi Navneet,

See below. 

Regards,

Roger

From: Navneet Agarwal (navagar) [mailto:[email-masked]] 
Sent: Wednesday, July 14, 2010 12:39 PM
To: Alexander, Roger; ROLL WG
Subject: RE: [Roll] no-Path DAO and fan-out

Hi Roger:

Thanks

Regards,

Navneet

	From: Alexander, Roger

	Hi Navneet,

	Regards,
	
	Roger

	-----Original Message-----
	
	Hi Alexander:

	Some comments:

	

	

	[RA] The selection of a particular fixed-assignment rule versus
even the choice of maintaining assignment state should be left to
individual implementations. However, the rule for aggregation of DAO
path control bits is important to the RPL operation and is already
specified in the -10 version (Section 8.9) through the defined bit-wise
ORing.

	

	[RA] It can be either. Here again when a node has multiple
downward path next hop options for a given Prefix, the particular load
balancing approach, if any, can be left to individual implementations.
In some cases at a common ancestor the preferred path (as given by the
highest preference path control bit) does not pass through the given
node. Instead the next hop options may be for other paths. In that case
there can be weighted or uniform load balancing among paths. In other
cases the downward path from the common ancestor does include the
preferred path as well as other lower preference path. Again in this
case weighted load balancing in favor of the preferred path may be
applied. Alternatively, the node can implement uniform load balancing
independent of the presence of the preferred path within the next hop
options. A node selects multiple DAO Parents to gain some amount of
diversity (even though only guaranteed). The common ancestor knows the
preferred path from other paths and can make a choice on how to exercise
its local downward diversity to the target destination node. 

	Thx

	Regards,

	Navneet 

	Thx
	
	Regards,
	Navneet

	        From: Alexander, Roger

	        Hi Navneet,

	       

	       

	       

	       

	       

	       
	        Regards,

	        Roger

	       
	        Hi WG:

	        Scenario-1:

	        A     B
	       
	        \      /
	       
	         \   /
	       
	           C
	       
	          /  \
	       
	         /    \
	       
	        D     E

	       

	       

	       

	        Scenario-2:

	        F     G
	       
	        \    /
	       
	         \  /
	       
	           A
	       
	            |
	       
	            |
	       
	           C
	       
	          /  \
	       
	         /    \
	       
	        D     E

	       

	       

	       

	        Scenario-3

	        F     G
	       
	        \    /
	       
	         \  /
	       
	           A
	       
	            |
	       
	            |
	       
	           C
	       
	          /  \
	       
	         /    \
	       
	        D     E

	       

	       

	       

	       

	       

	        Thanks

	        Regards,
	       
	        Navneet

---

From: "Navneet Agarwal (navagar)" <[email-masked]>
Date: Thu, 15 Jul 2010 09:11:13 +0530

Hi Roger:
Thanks for the comments...it helped clear the issue.
 
So, every node operates on the full (PCS + 1) bit width and chooses to
set/reset the bits based on the fixed assignment rule (local
implementation) when sending DAOs. On reception, aggregation/processing
is done on the full (PCS + 1) set. Section 8.9 helped clarify it.
 
Regards,
Navneet

	From: Alexander, Roger
[mailto:[email-masked]] 
	Sent: Thursday, July 15, 2010 1:57 AM
	To: Navneet Agarwal (navagar); ROLL WG
	Subject: RE: [Roll] no-Path DAO and fan-out

	Hi Navneet,

	See below. 

	Regards,

	Roger

	Hi Roger:

	Thanks

	Regards,

	Navneet

		From: Alexander, Roger

		Hi Navneet,

		Regards,
		
		Roger

		-----Original Message-----
		From: Navneet Agarwal (navagar)
[mailto:[email-masked] <mailto:[email-masked]> ]
		Sent: Tue 7/13/2010 1:16 PM
		To: Alexander, Roger; ROLL WG
		Subject: RE: [Roll] no-Path DAO and fan-out
		
		Hi Alexander:
		Thanks a lot for the detailed explanation...appreciate
it...this helps clears the path control operation.
		
		I think it would be good if some additional text related
to below is added to the RFC.
		
		Some comments:

		[RA] Agreed. More generally "any new or changed
routing/path information that is received at a node must be passed to
its DAO Parent(s)". In addition to incremented Path Sequence that new
information may include an existing Prefix with an unchanged Path
Sequence but with different Path Control bits.

		I guess this should apply to all DAOs (Path as well as
no-Path).
		[RA] Agreed.

		I do see some issues when a node has multiple DAO
parents and they are received and processed at a common ancestor.
		
		[RA] There may be issues related to dynamic changes in
the DAO Parent set of an ancestor node but these should be transient and
normalized in the course of subsequent DAO updates (with and without
incremented Path Sequence) - where a common ancestor receiving the very
same DAO information from multiple children maintains the most recent
update.
		
		Where a common ancestor receives DAOs along different
paths from a node with multiple DAO Parents a consistent rule will
ensure that assignments can be made without needing to maintain per-DAO
state information. As an implementation choice, a node can maintain a
		   
		Note: Other fixed-assignment rules may also be possible.
For example, the highest preference path control DAO assigned to the
highest preference DAO Parent and all other PSC-allowed path control
DAOs distributed across the remaining DAO Parents.
		NAV>  I think there may be a need for defining a mask to
identify the fixed-assignment rule you described above, especially in
cases where a node is more than 1-bit in the path control set. This
would help the common ancestor node receiving the individual DAO
messages from the nodes below to figure out the width of the path
control bits in the received DAO(s) for aggregation. For example, if
there are two nodes below a common ancestor and are using 2-bits per DAO
parent as the assignment rule, they may send DAOs with bit settings as
b'01' and b'10'. The common ancestor would somehow need to know to
aggregate this as b'1001' otherwise it may just aggregate it as b'01' |
b'10' == b'11'.

		[RA] The selection of a particular fixed-assignment rule
versus even the choice of maintaining assignment state should be left to
individual implementations. However, the rule for aggregation of DAO
path control bits is important to the RPL operation and is already
specified in the -10 version (Section 8.9) through the defined bit-wise
ORing.

		2. On a related topic, since there is a preference
associated with each path for a prefix, a node does not allow for
loadbalancing if there are multiple paths reported for a prefix. Right?
		
		[RA] Downward path load balancing at a common ancestor
is still possible for a given prefix though that load balancing need not
be uniform.  

		 It can be weighted where the preferred path (single
Parent, tree-equivalent path) is one of the next hop options, or it can
be uniform where the preferred path is not a member of the next hop
options. Load balancing can also consider diversity that may be derived
from the number of paths (path control bits) associated with a given
next hop route.  As indicated in the original note, path control only
guarantees that the preferred path can always be distinguished from
others. Th preference ordering of other paths are softer and more
loosely maintained as a function of the local application of preference.
		 NAV> I did not understand this part....are you saying
that load balancing can be weighted along the lines of the path
preference or it can be made uniform across all paths, ignoring the path
preference?

		[RA] It can be either. Here again when a node has
multiple downward path next hop options for a given Prefix, the
particular load balancing approach, if any, can be left to individual
implementations. In some cases at a common ancestor the preferred path
(as given by the highest preference path control bit) does not pass
through the given node. Instead the next hop options may be for other
paths. In that case there can be weighted or uniform load balancing
among paths. In other cases the downward path from the common ancestor
does include the preferred path as well as other lower preference path.
Again in this case weighted load balancing in favor of the preferred
path may be applied. Alternatively, the node can implement uniform load
balancing independent of the presence of the preferred path within the
next hop options. A node selects multiple DAO Parents to gain some
amount of diversity (even though only guaranteed). The common ancestor
knows the preferred path from other paths and can make a choice on how
to exercise its local downward diversity to the target destination node.

		Thx

		Regards,

		Navneet 

		Thx
		
		Regards,
		Navneet

		        From: Alexander, Roger

		        Hi Navneet,

		        Thanks for the scenario examples which provide a
good opportunity to highlight/clarify the role of the Path Sequence in
the DAO exchanges. Below is an explanation of how I envisaged it
would/should operate and would also be interested in the WG's feedback.
(Note: I am assuming your reference to Prefix is as used in the generic
RPL sense of identifying an IPv6 destination address, prefix, or
multicast group). 
		       
		        One advantage accruing to storing nodes, in
addition to DAO aggregation, is the ability to further reduce routing
overhead by removing the requirement for sub-DAG changes to always be
conveyed all the way to the root. In all of the scenarios you have
defined, when a common ancestor receives a no-Path DAO that is not
originated by the Prefix owner (and hence should not carry an
incremented Path Sequence), there is no requirement for that information
to be conveyed beyond the common ancestor (node C in your examples).
Loss of downward path diversity below the common ancestor does not mean
that path diversity above needs to be eliminated. Since the common
ancestor still has a downward table entry to the Prefix via alternate
path(s), its ancestors do not need to be further updated. With the
maintained Path Sequence in the no-Path DAO, only nodes that have a
singular downward route to the affected Prefix need to update their
individual DAO Parent(s). Correspondingly, only new or changed
routing/path information that originates from the Prefix owner and hence
indicated by an incremented Path Sequence number must always be passed
along to the root.

		        Note: The implementation option of limiting when
the Path Sequence number is incremented by a Prefix owner provides a
capability to further reduce routing overhead for storing nodes - though
the few bits needed to fully support incremental/partial updates within
the DAO would be still needed.

		        Where the transmission of the no-Path DAO is
being proactively initiated by a DAO Parent or other intermediate
ancestor node that discovers the loss of connectivity (neighbor
unreachability detection, NUD) to the node that owns the Prefix, the
Path Sequence used in the no-Path DAO will be the one maintained by the
ancestor node (only the owner of the Prefix can increment the Path
Sequence for that Prefix). This would be the same as the Path Sequence
maintained by all nodes along the path to the common ancestor. The first
common ancestor receiving such a no-Path DAO should mark the affected
downward path for deletion and should take no further action with regard
to upward forwarding of the DAO.

		       
		        Note: If the node that owns the Prefix chooses
to maintain its existing DAO Parents and preferences (even with the lost
connectivity to, or desired removal of, a single DAO Parent), it can do
so by sending normal periodic or triggered DAO updates to the connected
DAO Parents without incrementing the Path Sequence in the DAO updates.
Where connectivity exists, the owner of the Prefix may also send a
no-Path DAO to delete the path through a given DAO Parent. By not
incrementing the Path Sequence the path through the particular DAO
Parent will be removed only to the first common ancestor.

		        To redefine DAO Parents and preferences
(including where necessary to maintain fan-out limits), DAOs must be
sent with an incremented Path Sequence number to the newly
desired/re-ordered DAO Parents. The incremented Path Sequence DAOs will
ensure that the routing change is conveyed to the root and recognized by
ancestor nodes that can delete downward path entries. Where the updated
DAOs are received at nodes that do not currently have routing entries
for the particular Prefix, the information is cached and the new DAO
information conveyed towards the root.

		        Based on the above defined operation there is no
benefit to the node owner of the Prefix sending a no-Path DAO with an
incremented Path Sequence. This will travel all the way to the root and
will have the effect of outdating and marking for deletion all existing
downward routes for that Prefix. Instead, to re-establish desired
downward paths, DAOs with incremented Path Sequences should be sent to
the desired/maintained DAO Parents.

		        There would be some benefit to being able to
send a no-Path DAO to delete a single DAO Parent path all the way to the
root but the incremented Path Sequence will make stale all other valid
routing paths (as well as introduce the difficulties raised in your
assessments). Note once again that multiple DAO Parents guarantee only
local diversity. Therefore the fact that deleting a single DAO Parent
using an un-incremented Path Sequence removes diversity only to a common
ancestor should be seen in the context of the local guarantees that are
provided.

		        SUMMARY: If a no-Path DAO is sent by the Prefix
owner to a connected DAO Parent to delete the single downward path while

		        The operation for non-storing nodes would be the
same. However, in the case of non-storing nodes the first common
ancestor is always the root node. If in the non-storing case a no-path
DAO is issued by the owner of the Prefix or by a DAO Parent (due to
proactive response to NUD), the no-Path DAO with an un-incremented Path
Sequence will directly allow the root to update existing downward paths
(removing the identified DAO Parent while maintaining ordering of
remaining DAO Parents). As in the storing case, a no-Path DAO with an
incremented Path Sequence would mark all other downward paths from the
root as potentially outdated (and marked for deletion) and so should
similarly not be issued.

		        This is the operation as I believe it should
work but I look forward to understanding whether this envisaged
operation can fit within the model given in -10.

		        Make sense? See also a specific related comment
below.

		        Regards,

		        Roger

		       
		        Hi WG:
		        I am trying to get some clarifications on
expected behavior. Have read the Path Control document on path ctl field
usage (attached). I have put several setups and flows, assuming storing
nodes but should apply for non-storing scenario as well. I could not
figure out from the reading the doc or the RFC.

		        Scenario-1:

		        A     B
		       
		        \      /
		       
		         \   /
		       
		           C
		       
		          /  \
		       
		         /    \
		       
		        D     E

		        A, B - DAO Parents.....C - Node........D,E-
nodes in subdag.

		        D and E have learnt a common prefix for a node
below them, Pfx

		       

		       
		        Suppose E sends a no-Path DAO to C for Pfx with
path control x01. What does C do? I would think that C will need to send
a no-Path. But it has to remember that it had sent a DAO with path
control x01 to B. If this has to happen then C would have to remember
for each prefix what path control was sent to which parent, which does
not seem correct as it would not scale as the prefixes at C scale, each
having its own path control settings.

		        Scenario-2:

		        F     G
		       
		        \    /
		       
		         \  /
		       
		           A
		       
		            |
		       
		            |
		       
		           C
		       
		          /  \
		       
		         /    \
		       
		        D     E

		       

		       

		        Suppose E sends a no-Path to C (path control
x01). What does C do? It will likely send a DAO to A with path control
x10. What will A do when it receives a DAO with this path control when
its previous path control was x11?

		        I see couple of other flows where path control
settings may change due to sub-nodes going away and coming back up...for
example:

		        Scenario-3

		        F     G
		       
		        \    /
		       
		         \  /
		       
		           A
		       
		            |
		       
		            |
		       
		           C
		       
		          /  \
		       
		         /    \
		       
		        D     E

		       

		       

		        After some time E comes up and sends a DAO with
path control x01 (higher path preference than D to C) to C.
		       
		        C merges this and sends a DAO with path control
x11 to A. What does A do since is has indicated a path control of x10 to
G. In normal terms, if A had received a DAO with path control x11 from
C, it would have notified DAO to F with path control x10 and DAO to G
with path control x01 but due to transient conditions it could be
reversed.

		        [RA] In the case of receipt of the first updated
DAO (with incremented Path Sequence) only the new information with
single path control should be forwarded since all prior path information
is effectively obsolete by the incremented Path Sequence. When
subsequent DAO updates are received with the new, incremented Path
Sequence, only then can the combined path control information be
forwarded.

		        Will appreciate if it can be clarified if the
above flows are reasonable and what should happen...in general I dont
think path control should mandate which path control bits are tied to
which DAO parent etc...

		        [RA] Hopefully the above discussion supports the
view that Path Control can operate as specified without the need to
maintain state on which DAO with which Path Control was sent to which
DAO Parent.

		        Thanks

		        Regards,
		       
		        Navneet