Subject: [Roll] Something to ADD

From: JP Vasseur <[email-masked]>
Date: Tue, 10 Nov 2009 12:43:37 +0100

We need to clarify that when a node jumps to a better parent (higher  
rank), it can of course jump at any time since there is no risk of  
loops, but it must also poison up (send a no-DIO) to the previous  
parent.

Thanks.

JP.

---

From: Richard Kelsey <[email-masked]>
Date: Tue, 10 Nov 2009 12:37:01 -0500

From: JP Vasseur <[email-masked]>
   Date: Tue, 10 Nov 2009 12:43:37 +0100

JP,

Unfortunately, it isn't that simple.  The problem is that
some nodes may be caching DIO data while others are not.
If a node jumps to a new parent, whether up or down, the
issue is whether or not this causes the moving node's DIO
to be cached by a different ancestor.

 - If the DIO is still cached by the same ancestor,
   then the moving node just has to send a new DIO
   to its new parent and all will be well.

 - If the DIO is now cached by a different ancestor,
   then the moving node needs to send a no-DIO before
   moving and it and all its descendants must send
   new DIOs after the move.

Not only is the second case potentially quite costly, but
there is currently no way for a node to know which case
applies to a given move.

                         -Richard Kelsey

---

From: "Julien Abeille (jabeille)" <[email-masked]>
Date: Tue, 10 Nov 2009 22:27:15 +0100

Hi all,

We are talking about DAOs I guess, not DIOs. I am not sure I understand
the issue Richard. To me the no-DAO should travel up following the
prefered parents path, removing all DAO states if any.

Julien  

> -----Original Message-----
> From: [email-masked] [mailto:[email-masked]] On 
> Behalf Of Richard Kelsey
> Sent: mardi 10 novembre 2009 18:37
> To: JP Vasseur (jvasseur)
> Cc: [email-masked]
> Subject: Re: [Roll] Something to ADD
> 
> 
> issue is whether or not this causes the moving node's DIO to 
> be cached by a different ancestor.
> 
> _______________________________________________
> Roll mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/roll
>

---

From: JP Vasseur <[email-masked]>
Date: Tue, 10 Nov 2009 23:02:17 +0100

rrr ... yes my bad, second time I make that typo, I meant DAO of course.

---

From: Richard Kelsey <[email-masked]>
Date: Tue, 10 Nov 2009 17:57:47 -0500

Date: Tue, 10 Nov 2009 22:27:15 +0100
   From: "Julien Abeille (jabeille)" <[email-masked]>

   We are talking about DAOs I guess, not DIOs.

Yes.

   I am not sure I understand
   the issue Richard. To me the no-DAO should travel up following the
   prefered parents path, removing all DAO states if any.

Yes, and then after the move the new DAO follows the
new prefered parents' path.  Neither has any affect
on nodes that do not cache DAO information.  If the
set of nodes that do cache DAO information does not
change, then there is no need for the no-DAO.

Here is an example.  We start with this, where A
is the root:

       A
      / \
     B   C
     |
     D
     |
     E

Now D moves to C as its parent:

       A
      / \
     B   C
         |
         D
         |
         E

If only A caches DAO data, then all D needs to do
is send a DAO after the move.  A receives it and
changes its next hop for D and E to be C.

If B and C both cache DAO data, then D needs to send
a no-DAO before the move, to update B, and both D
and E need to send DAOs after the move, so that C
knows that it has downward paths to both of them.

                            -Richard Kelsey

---

From: "Julien Abeille (jabeille)" <[email-masked]>
Date: Wed, 11 Nov 2009 09:42:45 +0100

Hi Richard,

I get your point. There may be cases where no DAO is not needed. However
in the example D cannot know this. Hence I guess we have to do it
anyway?

Best,
Julien 

> From: Richard Kelsey [mailto:[email-masked]] 
> Sent: mardi 10 novembre 2009 23:58
> To: Julien Abeille (jabeille)
> Cc: JP Vasseur (jvasseur); [email-masked]
> Yes, and then after the move the new DAO follows the new 
> prefered parents' path.  Neither has any affect on nodes that 
> do not cache DAO information.  If the set of nodes that do 
> cache DAO information does not change, then there is no need 
> for the no-DAO.
> 
> Here is an example.  We start with this, where A is the root:
> 
>        A
>       / \
>      B   C
>      |
>      D
>      |
>      E
> 
> If only A caches DAO data, then all D needs to do is send a 
> DAO after the move.  A receives it and changes its next hop 
> for D and E to be C.
> 
> If B and C both cache DAO data, then D needs to send a no-DAO 
> before the move, to update B, and both D and E need to send 
> DAOs after the move, so that C knows that it has downward 
> paths to both of them.
> 
>                             -Richard Kelsey
>

---

From: Richard Kelsey <[email-masked]>
Date: Wed, 11 Nov 2009 04:26:02 -0500

Date: Wed, 11 Nov 2009 09:42:45 +0100
   From: "Julien Abeille (jabeille)" <[email-masked]>

Julien,

If it were just one DAO it wouldn't matter much.  The
problem is that the entire sub-DAG under the moving node may
need to send new DAOs.  Or they may not.  That is too much
traffic to send after every move, just in case it is needed.

The easy situation is when only the root stores DAOs, because
then one new DAO is always enough.
                                     -Richard Kelsey

---

From: Michael Richardson <[email-masked]>
Date: Wed, 11 Nov 2009 10:05:43 -0500

{Richard, I wonder if you could use > or julien> when you quote, rather
 than three spaces?}

>>>>> "Richard" == Richard Kelsey <[email-masked]> writes:
   Julien>    I get your point. There may be cases where no DAO is not
   Julien> needed. However in the example D cannot know this. Hence I
   Julien> guess we have to do it anyway?

    Richard> Julien,

    Richard> If it were just one DAO it wouldn't matter much.  The
    Richard> problem is that the entire sub-DAG under the moving node
    Richard> may need to send new DAOs.  Or they may not.  That is too
    Richard> much traffic to send after every move, just in case it is
    Richard> needed.

    Richard> The easy situation is when only the root stores DAOs,
    Richard> because then one new DAO is always enough.  

And, I think that lower-down nodes do not know who is storing DAOs, correct?
Is this something that we should be adding to the protocol?  
Maybe it's enough for every node to increment a counter in the DIO if it
stores DAOs?

-- 
]       He who is tired of Weird Al is tired of life!           |  firewalls  [
]   Michael Richardson, Sandelman Software Works, Ottawa, ON    |net architect[
] [email-masked] http://www.sandelman.ottawa.on.ca/ |device driver[
   Kyoto Plus: watch the video <http://www.youtube.com/watch?v=kzx1ycLXQSE>
	               then sign the petition.

---

From: Richard Kelsey <[email-masked]>
Date: Thu, 12 Nov 2009 16:18:22 -0500

> From: Michael Richardson <[email-masked]>
> Date: Wed, 11 Nov 2009 10:05:43 -0500
> 
> Richard> The

Correct.

> Is this something that we should be adding to the protocol?

At a minimum there should be a method for indicating
when:
 - only the root stores DAOs
 - no node stores DAOs

> Maybe it's enough for every node to increment a counter in the DIO if it

The big issue is that having intermediate nodes store
DAOs can have a big impact on the cost of switching
parents.  Given a choice between two new parents, you
definitely want to pick the one that does not require
that your entire sub-DAG send new DAOs.

This has an impact for local repair, because the 'local'
repair can become much less local in its effects.

I think that we need to reexamine whether or not having
intermediate nodes store DAOs is something that we need
to support in the base protocol.
                                   -Richard Kelsey

---

From: Michael Richardson <[email-masked]>
Date: Thu, 12 Nov 2009 16:36:05 -0500

>> And, I think that lower-down nodes do not know who is storing

    Richard> Correct.

    >> Is this something that we should be adding to the protocol?

    Richard> At a minimum there should be a method for indicating when:
    Richard> - only the root stores DAOs
    Richard> - no node stores DAOs

    >> Maybe it's enough for every node to increment a counter in the
    >> DIO if it stores DAOs?

I guess it might be enough to have a bit that gets turned by the first
non-root node that stores DAOs.

    Richard> I think that we need to reexamine whether or not having
    Richard> intermediate nodes store DAOs is something that we need to
    Richard> support in the base protocol. 

If I understand correctly, if the intermediate nodes do not store DAOs,
then they won't have a routing table to other peers, so p2p traffic will
have to travel all the way up to the root and out again.

It seemed to me like a compromise that the root had to be able to create
source routes so that weaker intermediate nodes could avoid storing the
DAOs. That this wasn't the ideal situation, but was a compromise.

What happens if we insist all nodes store DAOs? (is it simpler?)
What happens if we insist that no nodes store DAOs? (is it simpler?)

- --

---

From: Richard Kelsey <[email-masked]>
Date: Fri, 13 Nov 2009 14:38:00 -0500

> Date: Thu, 12 Nov 2009 16:36:05 -0500
>

I think you need two bits.  One is turned on by the
root if it stores DAOs and the other is turned on by
any intermediate node that stores them.

> have to travel all the way up to the root and out again.

Yes.  On the other hand, the DAG formation mechanism works
to maximize downward fanout, which in turn maximizes the
number of P2P routes that go through the root even if all
nodes store DAOs.  For example, if the root has N children
with roughly equal subgraphs, then each node can reach only
1/N of the network without through the root.

> What happens if we insist all nodes store DAOs? (is it simpler?)

That uses too much RAM for us to require it.

> What happens if we insist that no nodes store DAOs? (is it simpler?)

Do you mean no nodes at all, or no nodes other than the
root?

If only the root stores DAOs, then most of the P2P traffic
will go through the root.  As I said above, this is often
the case even if all node's store DAOs.  I think this would
be OK.  Even without intermediate DAO storage, routing
packets directly to neighbors will reduce the P2P messages
traveling through the root.  Devices that require more
bandwidth (in or out) can become roots of their own DAGs,
as long as the number of such devices is limited.

                               -Richard Kelsey

---

From: JP Vasseur <[email-masked]>
Date: Fri, 13 Nov 2009 22:27:31 +0100

> That uses too much RAM for us to require it.

Yes I heard this for several chipsets too.

> as long as the number of such devices is limited.

Right. That said, there are other deployment models where installing  
some
nodes with more memory in the network significantly improves routes  
quality
for P2P.

Cheers.

JP.

---

From: Richard Kelsey <[email-masked]>
Date: Fri, 13 Nov 2009 16:56:39 -0500

> Date: Fri, 13 Nov 2009 22:27:31 +0100
> 
> Right. That said, there are other deployment models where
> installing some nodes with more memory in the network
> significantly improves routes quality for P2P.

Has this actually been tried?  I have to admit that
I am skeptical that the P2P routes would be very
good even if much of the network is storing DAOs,
for several reasons:

  - There is nothing in the DAG rules working to
    improve the quality of the P2P routes.  Only
    the up and down DAG costs are considered.  P2P
    routes are likely to be long.

  - Having intermediate nodes store DAOs can
    greatly increase the cost of changing parents.

  - Even if all nodes store DAOs, much if not most
    of the P2P traffic is likely to go through the
    root.

                         -Richard Kelsey

---

From: Michael Richardson <[email-masked]>
Date: Fri, 13 Nov 2009 21:44:12 -0500

>>>>> "Richard" == Richard Kelsey <[email-masked]> writes:
    mcr> I guess it might be enough to have a bit that gets turned by the
    mcr> first non-root node that stores DAOs.

    Richard> I think you need two bits.  One is turned on by the root if
    Richard> it stores DAOs and the other is turned on by any
    Richard> intermediate node that stores them.

  I didn't realize that the root could *not* store DAOs...!
  I'm trying to imagine how that works.
  I can perhaps see how this might be the case with an ungrounded DAG,
where some random DAO-incapable node decides to become the new root.

    mcr> If I understand correctly, if the intermediate nodes do not store
    mcr> DAOs, then they won't have a routing table to other peers, so p2p
    mcr> traffic will have to travel all the way up to the root and out
    mcr> again.

    Richard> Yes.  On the other hand, the DAG formation mechanism works
    Richard> to maximize downward fanout, which in turn maximizes the
    Richard> number of P2P routes that go through the root even if all
    Richard> nodes store DAOs.  For example, if the root has N children
    Richard> with roughly equal subgraphs, then each node can reach only
    Richard> 1/N of the network without through the root.

  Yeah, I can see how a relatively uniformly distributed DAG would have
this property.   I can also see where this would not be the case, such
as a long linear network, such as a series of lampposts or utility poles
along a rural road... where the grounded node is at one of the road.
  
    >> It seemed to me like a compromise that the root had to be able to
    >> create source routes so that weaker intermediate nodes could
    >> avoid storing the DAOs. That this wasn't the ideal situation, but
    >> was a compromise.
    >> 

    Richard> That uses too much RAM for us to require it.
  
  Yes, I understand why we can not do it.

  You see, I'm asking what the real tradeoff is about this. 
  If ram and CPU was free, but network bandwidth was not, would we
decide to force all nodes to store DAOs?  
  JP has suggested that it helps.

  I can see with a linear network where there is traffic up and down the
line, that without DAO storing nodes in the middle, traffic has to go
all the way to the end and back. 

    >> What happens if we insist that no nodes store DAOs? (is it

    Richard> Do you mean no nodes at all, or no nodes other than the
    Richard> root?

  No nodes other than the root....
  Nothing would work if nobody knew the routes, right.

    Richard> If only the root stores DAOs, then most of the P2P traffic
    Richard> will go through the root.  As I said above, this is often
    Richard> the case even if all node's store DAOs.  I think this would
    Richard> be OK.  Even without intermediate DAO storage, routing
    Richard> packets directly to neighbors will reduce the P2P messages
    Richard> traveling through the root.  Devices that require more
    Richard> bandwidth (in or out) can become roots of their own DAGs,
    Richard> as long as the number of such devices is limited.

  To summarize, forbidding intermediate nodes to store DAOs:
     - causes a loss in quality for p2p traffic for some topologies,
       but for many topologies has a neglible effect
     - causes no change for m2p
     - massively reduces traffic when there is a new parent chosen
     - simplifies the protocol (no need to record who records DAOs)
     - removes the need for code to do different things depending
     upon whether there are DAO storing nodes above, when changing
     parents.

  Or to be it another way, capable nodes that have the ram to store DAOs
are causing load on less capable nodes.   They aren't being very
helpful.

- --

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Mon, 16 Nov 2009 09:03:06 +0100

Hi Richard:

Note that LSRR is still workable even if the root does not store DAO
itself.

An example of that is found here:
http://tools.ietf.org/html/draft-thubert-nemo-reverse-routing-header

Note that in the RRH case, the 'multihop' DAO was carried with the
traffic as a routing header.

The reason being that the other end of the connection has to echo the
LSRR header.

Pascal

>From: [email-masked] [mailto:[email-masked]] On Behalf Of
Michael Richardson
>Sent: samedi 14 novembre 2009 03:44
>To: [email-masked]
>-----BEGIN PGP SIGNED MESSAGE-----
>Hash: SHA1
>
>
>   Kyoto Plus: watch the video
<http://www.youtube.com/watch?v=kzx1ycLXQSE>
>	               then sign the petition.
>
>
>
>-----BEGIN PGP SIGNATURE-----
>Version: GnuPG v1.4.9 (GNU/Linux)
>Comment: Finger me for keys
>
>iQEVAwUBSv4ZbYCLcPvd0N1lAQLyNQf+JhBgKbIXe/Fj9knKJwWuflxOwDndPzHF
>AiZIszE8gxjHKUyd7UPC/b7Mf/kQvIO9v05inqaUazjK4a1n9aY6J4/dKONGzpNl
>p+DO9LkBo5j9wnSdc6KU3YIgv2apznSxX6Q/FTIh6Jt9yPUcq9wyFUKAETrIqw67
>WGxqhkHq58xBWJD5SPfvvun2dnZMXWMOrQ1lICWFO3B14Z0F42wMAr06ZmcNk7ko
>xup7hh8HDe2QqJ504PKP9S9C5KrJpHWjEPmLvvJbqUumNnHPOkc5R39XKRNjH1bF
>YbuW4YqEixUrTooNjYRZ2s7M+Sv2rDbR4Vur+zXimFthXnWj3fsiKg==
>=slpm
>-----END PGP SIGNATURE-----

---

From: Roger Alexander <[email-masked]>
Date: Mon, 16 Nov 2009 15:33:33 -0800

>  JP has suggested that it helps.

It does help when intermediate nodes store DAOs since DAO information  
should only need to be passed further up towards the root when the  
info represents a change in outward (to leaves) connectivity. That is,  
if a node changes parent and reattaches to a new branch that  
information only needs to travel inward towards the root to the point  
in the tree that held an outward table containing the given node.  
Granted it may be in some cases that point is at the root itself.  
However, in the absence of DAO storage at intermediate nodes a node's  
change of parent must always be conveyed all the way to the root so  
that outward connectivity (via source routing) can be supported. For  
nodes not maintaining state, the change of parent information must  
always flow back to the root or otherwise to the first DAO storing  
node (which may then need to update it's parent(s) if the stateless  
node was not previuosly reachable via the stateful node).
>     - causes a loss in quality for p2p traffic for some topologies,

It also creates additional routing traffic towards the root which is  
needed so that the reverse path information from the root to the node  
can be conveyed to the root for subsequent outward routing.

>     - simplifies the protocol (no need to record who records DAOs)

Not clear why there is a need to know who records DAOs. In response to  
a new child a parent that does maintain state will add itself to the  
path information from the child and pass that information to it's  
parent. That information will pass inward towards the root until a  
node is encountered that can store the path information and previously  
supported connectivity to the node at the same cost.

>     upon whether there are DAO storing nodes above, when changing

The node that do not store
>   Kyoto Plus: watch the video <http://www.youtube.com/watch?v=kzx1ycLXQSE 
> >
>                   then sign the petition.
>
>
>

---

From: Roger Alexander <[email-masked]>
Date: Mon, 16 Nov 2009 15:42:42 -0800

Sorry for the earlier transmission of the incomplete email...(moving  
vehicle)...final thoughts completed below.

Thanks.

Roger

On Nov 16, 2009, at 3:33 PM, Roger Alexander <[email-masked] 

> It does help when intermediate nodes store DAOs since DAO  
> information should only need to be passed further up towards the  
> root when the info represents a change in outward (to leaves)  
> connectivity. That is, if a node changes parent and reattaches to a  
> new branch that information only needs to travel inward towards the  
> root to the point in the tree that held an outward table containing  
> the given node. Granted it may be in some cases that point is at the  
> root itself. However, in the absence of DAO storage at intermediate  
> nodes a node's change of parent must always be conveyed all the way  
> to the root so that outward connectivity (via source routing) can be  
> supported. For nodes not maintaining state, the change of parent  
> information must always flow back to the root or otherwise to the  
> first DAO storing node (which may then need to update it's parent(s)  
> if the stateless node was not previuosly reachable via the stateful  
> node).
>>
> needed so that the reverse path information from the root to the  
> node can be conveyed to the root for subsequent outward routing.
>
> Not clear why there is a need to know who records DAOs. In response  
> to a new child a parent that does maintain state will add itself to  
> the path information from the child and pass that information to  
> it's parent. That information will pass inward towards the root  
> until a node is encountered that can store the path information and  
> previously supported connectivity to the node at the same cost.
>
> The nodes that do not store DAOs can have a consistent behavior  
> while those that do can similarly also be consistent.
>>
It seems that the intermediate nodes that do maintain DAOs can limit  
overhead by avoiding the need for all changes in node connectivity to  
the DAG from having to always go all the way to the root to provide  
for maintaining an outward path. Furthermore if only the root stores  
DAOs the RPL reduces to a source routing protocol which may be an issue.

---

From: Richard Kelsey <[email-masked]>
Date: Tue, 17 Nov 2009 11:12:00 -0500

> From: Roger Alexander <[email-masked]>
> Date: Mon, 16 Nov 2009 15:33:33 -0800
> 

The difficulty is that, at present, there is no way of
determining how much information needs to be passed up after
a move.  Here is the example I posted earlier.  We start
with this, where A is the root:

       A
      / \
     B   C
     |
     D
     |
     E

       A
      / \
     B   C
         |
         D
         |
         E

If B and C both cache DAO data, then D needs to send a
no-DAO before the move, to update B, and both D and E need
to send DAOs after the move, so that C knows that it has
downward paths to both of them.

In the first case a single DAO needs to be sent.  In the
second case D has to send two DAOs and the nodes in its
subdag, just E here, each need to send one.  If only the
root caches DAOs then the first case always applies.  If
other nodes may cache DAOs, then we have to assume that we
are in the second case after every move.

                            -Richard Kelsey

---

From: Jonathan Hui <[email-masked]>
Date: Tue, 17 Nov 2009 08:38:03 -0800

On Nov 17, 2009, at 8:12 AM, Richard Kelsey wrote:

>> to

[nice example of what DAOs need to be sent]

> are in the second case after every move.

I was in the process of creating a similar example.  All I'll add is  
that, intuitively, the more places state gets "replicated" within the  
network, the more costly it is to maintain that state and the more you  
have to deal with inconsistencies between replicated instances.  Of  
course, the hope in replicating this routing state is that it creates  
shorter paths and ultimately offsets the cost of maintaining that state.

I'll have to admit that I'm not yet convinced of the benefits in  
storing DAO state as it currently exists in the draft.  It seems like  
a mediocre attempt to optimize point-to-point routing and something  
that folks wanting P2P support aren't satisfied with.  If that is the  
end-goal, then we should be developing better mechanisms.  For now, we  
are focusing on one-to-many and many-to-one.  And, I see more benefits  
to simply maintaining state at the root.

--
Jonathan Hui

---

From: Michael Richardson <[email-masked]>
Date: Tue, 17 Nov 2009 12:02:37 -0500

>>>>> "Jonathan" == Jonathan Hui <[email-masked]> writes:
    Jonathan> I'll have to admit that I'm not yet convinced of the
    Jonathan> benefits in storing DAO state as it currently exists in
    Jonathan> the draft.  It seems like a mediocre attempt to optimize
    Jonathan> point-to-point routing and something that folks wanting
    Jonathan> P2P support aren't satisfied with.  If that is the
    Jonathan> end-goal, then we should be developing better mechanisms.
    Jonathan> For now, we are focusing on one-to-many and many-to-one.
    Jonathan> And, I see more benefits to simply maintaining state at
    Jonathan> the root.

Thus, my proposal to forbid storing of state in intermediate nodes
(at least in the base protocol) since it causes externalities.  

Perhaps someone can some up with a way to store some state (but not the
DAOs) in such a way that does not impose externalities that need to be
communicated in the protocol.

---

From: Jonathan Hui <[email-masked]>
Date: Tue, 17 Nov 2009 09:06:37 -0800

> communicated in the protocol.

Yes.  Sorry for not stating it clearly.  I also propose to remove the  
ability to store downwards routing state at intermediate nodes from  
the base RPL document.  A P2P proposal that satisfies the application  
requirements should be dealt with in a separate draft.

--
Jonathan Hui

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Tue, 17 Nov 2009 18:20:20 +0100

Hi Jonathan and Richard:

My thought process lead me to following (buy or not :) design, that is
what you find in the MANEMO implementations.

* Nodes that can store should if that's what the deployment requires
(that's policy). 

* Source route trace a path. It can be done on traffic, one every so
many messages with exponential backoff, using small messages that can be
extended for the purpose of LSRR.

* In particular when there are movements (churn) only a snapshot is
consistent. Assembling asynchronous pieces some of which might be out of
date into a routing header is doomed.

A node that cannot store states 

* needs *no* DAO support at all and the whole thing still works. Nodes
that do DAO cohabit with nodes that do without a problem.

* Announce in DIO but still silently absorb for the DAO if they come
nevertheless.

* But they forward and add to the source route. Adding to the source
route means add up the SR stack the information about the next hop. That
information is derived from the source of the packet. Then the node sets
its own address as the source of the packet so it is topologically
correct all the way.

A Node that supports DAO states 

* If the state matches the source route path then the node does not need
to add to the source route header. A state matches if the route to the
highest (newest) entry in the source route header is via the source of
the packet. This confirms that the associated routing state learnt from
DAO is still correct.

* The node does not need to store the source route either. Only the
endpoint does that. In our case the root could intercept and store.

* The node still updates the source of the packet with their own address
to keep it topologically correct and allow the next hop to record the
right thing if it needs.

* But if the states does not match the source route, then the states are
obsolete, and the node should add to the source route header and set the
source to self. 

When you run the MANEMO trilogy (tree discovery, nina (DAO) and RRH
(source route)), you see the source route RH2/4 grow upon movement and
quickly shrink again as the NINA (DAO) states are reestablished. 
When things are stable you only see as many entries as non DAO capable
nodes along the path. In my case, the source route is done on a MIP/NEMO
tunnel, so the RH states are stored in eth binding cache on the home
agent. But we could store that at the root with exactly the same
process.
I can demo that next time we meet if you wish.

http://tools.ietf.org/html/draft-thubert-nemo-reverse-routing-header
details the RRH, since there is not LSRR in IPv6.

Note that in our case, the information in the header should be locally
significant, like a label.

cheers

Pascal

Jonathan Hui
>Sent: mardi 17 novembre 2009 17:38
>To: Richard Kelsey
>Cc: [email-masked]
>Subject: Re: [Roll] updating DAO caches (was Re: Something to ADD)
>
>

---

From: Jonathan Hui <[email-masked]>
Date: Tue, 17 Nov 2009 09:56:15 -0800

> significant, like a label.

Here lies the disconnect.  The real benefit of storing state among  
nodes within the network is to reduce the size of the source route  
header not some attempt to support point-to-point traffic.  If you buy  
that, then the mechanism to establish such state could be much better  
than what's currently defined in the draft.  In particular, there are  
some interesting things we could achieve if we start treating next-hop  
information using locally significant labels rather than globally  
significant IP addresses, as you suggested.  But if done properly, I  
think we can specify such a mechanism as an optimization to basic  
source-route/record-route.

--
Jonathan Hui

---

From: Roger Alexander <[email-masked]>
Date: Tue, 17 Nov 2009 12:25:26 -0800

The conclusions drawn are not entirely valid in part due to the  
particular example given. Quite often the examples used to demonstrate  
the protocol are of necessity simpler ones but may not capture the  
larger variety of connectivity seen particularly in larger multihop  
networks. I will try to make the case using a slightly more complex  
network graph which illustrate the benefit of intermediate state  
storage and how it might work without explicit indications of which  
note are maintaining state.

Roger

---

From: Jonathan Hui <[email-masked]>
Date: Tue, 17 Nov 2009 12:49:43 -0800

Hi Roger,

On Nov 17, 2009, at 12:25 PM, Roger Alexander wrote:

> particular example given. Quite often the examples used to  
> demonstrate the protocol are of necessity simpler ones but may not  
> capture the larger variety of connectivity seen particularly in  
> larger multihop networks. I will try to make the case using a  
> slightly more complex network graph which illustrate the benefit of  
> intermediate state storage and how it might work without explicit  
> indications of which note are maintaining state.

A fair characterization is that the change in down route state must be  
reflected up until there is a common ancestor that provides  
connectivity both before and after the change in connectivity *and*  
can store down routes.  In the example that Richard provided, A was  
the common ancestor and it also happened to be the root.  But it is  
also true that nodes within the sub-DAG of A must update their DAO  
routing state to reflect the change in topology.  As Richard's example  
points out, when you allow nodes to chose whether they can store down  
route state, nodes within the sub-DAG must assume the worst case and  
originate their own DAO messages in case nodes between it and the  
common ancestors cannot maintain down routes.

That said, the cost savings of having storage at intermediate nodes  
depends mostly on the depth of the common ancestor - a common ancestor  
with greater depth will result in less transmissions that propagate  
information towards the root.  Of course, in the worst case, the  
common ancestor will be the root.  An unfortunate edge case with  
hierarchical structures is that the common ancestor of you and your  
neighbor could be the root.

I think it is fair to say that the current DAO caching capabilities  
specified in the RPL doc need quite a bit more thought before I would  
be comfortable with putting it into the base specification.  If there  
is a way to treat it as an optimization, I would prefer to do so and  
work on that in a separate draft.

--
Jonathan Hui

---

From: Roger Alexander <[email-masked]>
Date: Tue, 17 Nov 2009 13:02:25 -0800

Flight about to take off but let me just add that source routing must  
remain an option so schemes to optimize its operation need to be kept  
in that context...

Thx.

Roger
On Nov 17, 2009, at 12:49 PM, Jonathan Hui <[email-masked]> wrote:

> A fair characterization is that the change in down route state must  
> be reflected up until there is a common ancestor that provides  
> routing state to reflect the change in topology.  As Richard's  
> example points out, when you allow nodes to chose whether they can  
> store down route state, nodes within the sub-DAG must assume the  
> worst case and originate their own DAO messages in case nodes  
> between it and the common ancestors cannot maintain down routes.
>
> depends mostly on the depth of the common ancestor - a common  
> ancestor with greater depth will result in less transmissions that  
> propagate information towards the root.  Of course, in the worst  
> case, the common ancestor will be the root.  An unfortunate edge  
> case with hierarchical structures is that the common ancestor of you  
> and your neighbor could be the root.
>
> specified in the RPL doc need quite a bit more thought before I  
> would be comfortable with putting it into the base specification.   
> If there is a way to treat it as an optimization, I would prefer to  
> do so and work on that in a separate draft.
>
> --
> Jonathan Hui
>

---

From: [email-masked]
Date: Tue, 17 Nov 2009 15:25:31 -0600

Hi Jonathan,

I am conflicted with the idea of discounting P2P messaging in this 
document in lieu of some future document.  I am completely with you that 
if there will be no attempt to fix the current P2P in RPL then we should 
deprecate it.  What RPL currently documents for P2P communication simply 
won't meet the requirements specified (at least within the commercial 
building market).  On the other hand, if we pull P2P out of RPL, I'm 
afraid it will never get defined. 

In Geneva we discussed that as we complete the MP2P protocol and move it 
toward true implementations, it will be apparent that even for this 
presumably unidirectional protocol, these collection networks will still 
need to application ACK the packets to assure that the packet has been 
successfully delivered to its destination.  Therefore. even MP2P networks 
will need a robust means to move packets outward down the DAG; and hence, 
it would be short-sighted to postpone this to a future draft.

Unless those folks requiring MP2P communication are willing to use a 
protocol that does not support guaranteed delivery, I think we best work 
this out within the confines of this current document.

Jerry

Jonathan Hui <[email-masked]> 
Sent by: [email-masked]
11/17/2009 02:50 PM

To
Roger Alexander <[email-masked]>
cc
"[email-masked]" <[email-masked]>
Subject
Re: [Roll] updating DAO caches (was Re:  Something to ADD)

Hi Roger,

--
Jonathan Hui

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Wed, 18 Nov 2009 08:03:05 +0100

Hi Jonathan

>Here lies the disconnect. 

With the draft, not between us :)

>                          The real benefit of storing state among
>header not some attempt to support point-to-point traffic.  

I'm sure we agree here. 

I'd add that we get a unoptimized P2P if we are willing to have *all* 
nodes support states. Otherwise you get something quite silly.

That unoptimized P2P has interesting characteristics, in particular 
it is very resilient to movement. 

We should not bar that feature, just understand what it is good at 
and what it not so suited for. Like Jerry's problem.

>                                                          If you buy

Looks good. The main consequence that I see at first glance is that 
The DAO should be sent to only one parent, because maintaining multiple
Source route path down the DAG makes little sense for reasons discussed
Earlier in this list (combinatory explosion, no end to end retries...)

Would you agree on that?

Pascal

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Wed, 18 Nov 2009 13:21:46 +0100

Hi Jonathan and Michael.

Both the source route and the DAO depend on the DAG specification.
The other way around, the DAG specification does not depend on them.

And arguably, one deployment could use source route only whereas
Another that needs all end to end connectivity would use DAO states
Yet another could take an unspecified-yet limited P2P solution to
compute only required on-demand constrained routes.

Even more fun, it is very possible to mix DAO states into a source route
network.

Since we have not designed a more specific on demand P2P solution, or
even proven that 
the existing MANET solutions are not enough for the job, I can only
infer that the best 
contender is probably DYMO, in which case it has no dependency at all.
      
Since we already took the path of not having a minimum Interop set in
one spec by removing OCP0, 
* I have no philosophical opposition in splitting the draft to make the
DAO separate.
* Also make a source route document that can work with no states
  yet explains how the DAO states can compress the source route when
they are present 
* Then study the applicability of existing on demand protocol and see
what we need to do there.

>From there, the applicability statement will have to guide us in which
sets we need to pick in an implementation.

But those documents should still make a consistent set, for instance for
the purpose of loop detection.

Pascal

Jonathan Hui
>Sent: mardi 17 novembre 2009 18:07
>To: Michael Richardson
>Cc: [email-masked]

---

From: JP Vasseur <[email-masked]>
Date: Thu, 19 Nov 2009 09:57:18 +0100

Hi Roger,

The spec is exactly along the lines of what you wrote: intermediate  
nodes can store routes of course,
and RPL does not mandate to store route at the DAG only. Some networks  
will exclusively use hop by
hop routing with route storage at each hop, others won't, others will  
have a mixed of nodes and RPL
does support them all.

Cheers.

JP.

On Nov 17, 2009, at 12:42 AM, Roger Alexander wrote:

>> the given node. Granted it may be in some cases that point is at  
>> the root itself. However, in the absence of DAO storage at  
>> intermediate nodes a node's change of parent must always be  
>> conveyed all the way to the root so that outward connectivity (via  
>> source routing) can be supported. For nodes not maintaining state,  
>> the change of parent information must always flow back to the root  
>> or otherwise to the first DAO storing node (which may then need to  
>> update it's parent(s) if the stateless node was not previuosly  
>> reachable via the stateful node).
>>>
>> It also creates additional routing traffic towards the root which  
>> is needed so that the reverse path information from the root to the  
> overhead by avoiding the need for all changes in node connectivity  
> to the DAG from having to always go all the way to the root to  
> provide for maintaining an outward path. Furthermore if only the  
> root stores DAOs the RPL reduces to a source routing protocol which  
> may be an issue.
>>> - --

---

From: JP Vasseur <[email-masked]>
Date: Thu, 19 Nov 2009 11:36:47 +0100

> DAO after the move.  A receives it and changes its next hop

Well I think that you still need the no-DAO since A may continue to send
packets to D via both B and C.

> downward paths to both of them.

Note that with DAO packing only D will send one DAO for local prefixes
and E's prefixes but that's not the topic.

> are in the second case after every move.

Yes but I think that we need no-DAO to avoid nodes upper in the DAG to  
continue
to use an old path anyway and the issues of the number of DAO is IMO  
larger and
packing will sort it out.

---

From: JP Vasseur <[email-masked]>
Date: Thu, 19 Nov 2009 11:36:49 +0100

On Nov 17, 2009, at 5:38 PM, Jonathan Hui wrote:

> that, intuitively, the more places state gets "replicated" within  
> the network, the more costly it is to maintain that state and the  
> more you have to deal with inconsistencies between replicated  
> instances.  Of course, the hope in replicating this routing state is  
> that it creates shorter paths and ultimately offsets the cost of  
> maintaining that state.
>
> storing DAO state as it currently exists in the draft.  It seems  
> like a mediocre attempt to optimize point-to-point routing and  
> something that folks wanting P2P support aren't satisfied with.  If  
> that is the end-goal, then we should be developing better  
> mechanisms.  For now, we are focusing on one-to-many and many-to- 
> one.  And, I see more benefits to simply maintaining state at the  
> root.
>

I do agree with the first statement but not with the second paragraph.  
I do see several deployment cases where no storing DAO would lead to  
extremely sub-optimal paths and even more importantly traffic  
congestion when getting closer to the root of course. This is true  
with several networks where the amount of P2P traffic may ned up being  
not so negligible. The beauty with the current spec is that it allows  
both deployment models.

---

From: JP Vasseur <[email-masked]>
Date: Thu, 19 Nov 2009 11:36:55 +0100

On Nov 17, 2009, at 6:56 PM, Jonathan Hui wrote:

> header not some attempt to support point-to-point traffic.  If you  
> buy that, then the mechanism to establish such state could be much  
> better than what's currently defined in the draft.  In particular,  
> there are some interesting things we could achieve if we start  
> treating next-hop information using locally significant labels  
> rather than globally significant IP addresses, as you suggested.   
> But if done properly, I think we can specify such a mechanism as an  
> optimization to basic source-route/record-route.

I'm with you, well as someone used to work on MPLS, no surprise.
But still that does not solve the traffic matrix issue: not storing  
DAO leads to all traffic transiting via the root, which is not  
acceptable in many networks.

---

From: JP Vasseur <[email-masked]>
Date: Thu, 19 Nov 2009 11:42:45 +0100

[snip]

> Earlier in this list (combinatory explosion, no end to end retries...)

I do. Fairly simple, already supported. If the node cannot store the  
route then you go back to the root
but the support of DAO must stay in the base spec for all networks  
that need it to (1) avoid too much
traffic as you get closer to the root and (2) where the current P2P  
mechanisms provide a good enough
path.

JP.

---

From: Richard Kelsey <[email-masked]>
Date: Thu, 19 Nov 2009 06:01:14 -0500

> Date: Thu, 19 Nov 2009 11:36:49 +0100
>
> > storing DAO state as it currently exists in the draft.  [...]
> > 
> congestion when getting closer to the root of course. 

Can you share these cases with us?  I agree with Jonathan
that storing DAO states will typically not provide much
improvement in P2P routing.

> not so negligible. The beauty with the current spec is that it allows  

It claims to allow both, but fails to actually do so.  That
is the point of the example that I gave and the reason I
keep going on about this.  While the draft says that
intermediate nodes can cache DAOs, it doesn't say how those
caches are updated after a node changes parents.  And
however this is done, we need to avoid the cost of sending
cache updates in the absense of any actual caches.

                                 -Richard Kelsey

---

From: Richard Kelsey <[email-masked]>
Date: Thu, 19 Nov 2009 06:09:00 -0500

> Date: Thu, 19 Nov 2009 11:36:47 +0100
> 

Yes, if DAOs can be sent to multiple parents.  No if DAOs
are only sent to one parent (because then A will only
store the most recently received path to D).

> and E's prefixes but that's not the topic.

No, because D doesn't have a cache.  E has to send its
prefixes, whether packing is present or not.

> Yes but I think that we need no-DAO to avoid nodes upper
> in the DAG to continue to use an old path anyway and the
> issues of the number of DAO is IMO larger and packing will
> sort it out.

The issue is only partly the number of DAO.  It is also who
has to send them.  If switching parents requires that every
node in the sub-DAG send a DAO, we need to take that cost
into account and avoid it when it is possible to do so.  DAO
packing is not a magic bullet that makes DAOs free.

                                 -Richard Kelsey

---

From: JP Vasseur <[email-masked]>
Date: Thu, 19 Nov 2009 13:18:56 +0100

> improvement in P2P routing.

Sure. I'll take the example of an inter primary+secondary substation  
network
(could be the smart metering network) that supports traffic for  
various purposes:
meter read-out, DA alarms, ... etc. Thus traffic of various nature:  
P2MP, MP2P
and P2P. There are many such networks where not storing DAO just does  
not
work since all P2P traffic will have to transit via the root  
(unacceptable delays for
alarms) and the traffic around the root will be way too high.

This is why I am saying that having an RFC that forms a DAG that  
cannot be used
for outward traffic is a non-starter.

> cache updates in the absense of any actual caches.

Yes I agree with you on this and this is why DAO packing is also  
important.
Thus I would propose to all work on this and make it work while still  
allowing
some nodes to not store any DAO is they want to of course.

Does that make sense ?

Cheers.

JP.

---

From: Richard Kelsey <[email-masked]>
Date: Thu, 19 Nov 2009 09:41:41 -0500

> Date: Thu, 19 Nov 2009 13:18:56 +0100
> 
> JP> From: JP Vasseur <[email-masked]>
> JP> Date: Thu, 19 Nov 2009 11:36:49 +0100
> JP>
> JP> I do see several deployment cases where no storing DAO would lead to
> JP> extremely sub-optimal paths and even more importantly traffic
> JP> congestion when getting closer to the root of course.
> 
> Richard> Can you share these cases with us?  I agree with Jonathan
> Richard> that storing DAO states will typically not provide much
> Richard> improvement in P2P routing.
> 
> Sure. I'll take the example of an inter primary+secondary
> substation network (could be the smart metering network)
> that supports traffic for various purposes: meter
> read-out, DA alarms, ... etc. Thus traffic of various
> nature: P2MP, MP2P and P2P.

Yes, I think we all agree that reasonably efficient
P2P is a requirement for many use cases.

The issue isn't whether or not we need good P2P routing.
The issue is whether or not the DAO mechanism does a good
enough job to be worth the effort.

RPL ignores P2P when choosing parents.  Getting a good P2P
route out of RPL is a matter of luck, not design.

> There are many such networks
> where not storing DAO just does not work since all P2P
> traffic will have to transit via the root (unacceptable
> delays for alarms) and the traffic around the root will be
> way too high.

Yes, and in many cases most P2P traffic will have to transit
via the root even if all nodes store DAOs.  This is a side
effect of how RPL chooses parents.  Minimizing the lengths
of the paths to the root maximizes the number of pairwise
paths that include the root.  If this is unacceptable, then
we should stop tweaking the DAOs and work on a better
solution.
                                  -Richard Kelsey

---

From: JP Vasseur <[email-masked]>
Date: Thu, 19 Nov 2009 15:49:15 +0100

> route out of RPL is a matter of luck, not design.

First, you can certainly tune the OF to increase the P2P quality.
Second, in the VERY worst non probable case you would transit via
the route.
Last but not least, without DAO how do you send traffic outward ?
Need to wait until you receive a packet, then record route and do
source routing ?

---

From: "Julien Abeille (jabeille)" <[email-masked]>
Date: Thu, 19 Nov 2009 15:55:16 +0100

Hi JP, all,

I agree that we should keep DAOs in RPL. A routing protocol that
installs routes in one direction only makes no sense to me. By the way
if in a deployment some do not want to store DAOs, they can.

Best,
Julien

> Behalf Of JP Vasseur (jvasseur)
> Sent: jeudi 19 novembre 2009 13:19
> To: Richard Kelsey
> Cc: [email-masked]
> that storing 
> > DAO states will typically not provide much improvement in 
> P2P routing.
> 
> substation network (could be the smart metering network) that 
> supports traffic for various purposes:
> and P2P. There are many such networks where not storing DAO 
> just does not work since all P2P traffic will have to transit 
> via the root (unacceptable delays for
> This is why I am saying that having an RFC that forms a DAG 
> that cannot be used for outward traffic is a non-starter.
> 
> >

---

From: [email-masked]
Date: Thu, 19 Nov 2009 09:40:21 -0600

Hi JP,

Sorry to be beating you up today on the mailing list.  It's not 
intentional; maybe it's just your turn :)

In Geneva, I thought we had reached an epiphany when Thomas noted so 
adroitly that destination nodes cannot a priori know what source nodes 
might be sending them packets in the future.  I believe he referenced the 
pain Google would have if it somehow needed to define a connection to 
potentially everyone wanting to someday access its website!!!  I hoped 
that discussion would be the impetus to find an on-demand means to pass a 
packet outward.  The idea of every node having to form a connection to 
every other node in the DAG to be maintained ad infinitum on the 
off-chance that someday a packet may need to be passed to that node is 
very inefficient. 

As probably the strongest proponent of the P2P requirement on this mailing 
list, I will readily admit that even in building control only about 25% of 
the router nodes need to pass intra-LLN P2P messages.  As I understand the 
DAO algorithm in RPL 4.0 using the preferred parent requirement there will 
be one and only one outward path defined to each node.  If that lonely 
path should happen to be dropped, the outbound packet would be in a limbo 
state for an undetermined amount of time until the DAG recognizes the 
problem, issues a sequence number change and the DAG is fully repaired 
with a new set of DAO exchanges.  The source node will have long ago 
exhausted its retry count and flagged the destination node off-line.

So yes, I think we either need to design outward traffic into the DAG at 
the same level as we do inward traffic; or devise an on-demand scheme 
where a node can easily 'discover' another node in the DAG as needed. 
Richard's comment below is profound saying that right now establishing a 
good outward link is a matter of luck, not design.

Regards,

Jerry

JP Vasseur <[email-masked]> 
Sent by: [email-masked]
11/19/2009 08:49 AM

To
Richard Kelsey <[email-masked]>
cc
[email-masked]
Subject
Re: [Roll] updating DAO caches (was Re:  Something to ADD)

---

From: Richard Kelsey <[email-masked]>
Date: Thu, 19 Nov 2009 10:49:53 -0500

> Date: Thu, 19 Nov 2009 15:49:15 +0100
> 
> 

I haven't thought about it a lot, but it isn't at all clear
to me how you would do this.

I believe that we can get good P2P routes using RPL as a
base.  Doing so will require more than just coming up with
an appropriate OF.

> Second, in the VERY worst non probable case you would
> transit via the root.

We clearly have very different images of the DAGs that RPL
will produce.  The DAG formation mechanism works to maximize
downward fanout, which in turn maximizes the number of P2P
routes that go through the root even if all nodes store
DAOs.  For example, if the root has N children with roughly
equal subgraphs, then each node can reach only 1/N of the
network without through the root.

> Last but not least, without DAO how do you send traffic
> outward?  Need to wait until you receive a packet, then
> record route and do source routing?

My point is that your argument in favor of requiring
multiple DAO caches is also an argument that DAO is not
adequate for P2P routing.

You are claiming that we have to cache DAOs in non-root
nodes because otherwise there is too much traffic through
the root.  If there is too much traffic through the root
without the caching, then there is almost certainly too much
even with the caching.  Having nodes cache DAOs cannot be
counted on to greatly reduce the traffic throught the root.

If the DAO mechanism meets the requirements for P2P, then it
meets those requirements with DAOs only cached at the root.

                            -Richard Kelsey

---

From: "Roger K. Alexander" <[email-masked]>
Date: Thu, 19 Nov 2009 11:16:24 -0500

> From: JP Vasseur [mailto:[email-masked]]
> Sent: Thursday, November 19, 2009 5:37 AM
> To: Richard Kelsey
> Cc: Roger Alexander; [email-masked]

The protocol must work without the need to send no-DAOs. In some cases the
change of a parent is due to loss of link connectivity to the prior parent.
In such cases, there is no opportunity for a no-DAO to be received. Instead,
the new DAO information will be passed inward to the highest state-storing
'common ancestor' (as Jonathon correctly cites) node located at a rank above
the old and new parent (which in some cases may indeed be the root). The
common ancestor will then be able to correct subsequent outward routing. Any
broken routing will be temporary. 

As indicated earlier, with larger multi-hop networks there will be more
potential common ancestor nodes between the node changing its parent and the
root. As such, a DAO issued as a result of a change of parent will need to
travel only to the point at which such a state-storing common ancestor node
is encountered. It some cases this may be the root but in all other cases
the extent of the DAO update transmission is reduced relative to the case in
which only the root maintains state.

---

From: "Roger K. Alexander" <[email-masked]>
Date: Thu, 19 Nov 2009 11:17:07 -0500

> JP Vasseur
> To: Jonathan Hui

I think even if the current focus is one-to-many and many-to-one, a default
capability that allows less than optimal one-to-one routing is still
worthwhile. Particularly in the context of larger networks in which nodes
are not state-constrained, there will be latency and traffic benefits by
avoiding always having to loop all traffic through the root. Furthermore,
that default routing comes without the need to, as yet, introduce any
special mechanisms.

---

From: "Roger K. Alexander" <[email-masked]>
Date: Thu, 19 Nov 2009 11:21:35 -0500

> acceptable in many networks.

Agreed. The emphasis needs to be on ensuring that we can reduce the DAO
update information overhead which benefits networks in which nodes can
maintain state as well as those in which only the root stores state. I still
believe that there can be a DAO specification in which nodes that do not
store state can include Reverse Route info that can then be alternately
removed by state-maintaining nodes and added by stateless nodes as the DAO
information is passed inward towards the root (to the highest rank
state-maintaining common ancestor node that sits above an old and new
parent).

---

From: "Roger K. Alexander" <[email-masked]>
Date: Thu, 19 Nov 2009 11:22:04 -0500

From: [email-masked] [mailto:[email-masked]] On Behalf Of JP
Vasseur
Sent: Thursday, November 19, 2009 5:43 AM
To: Pascal Thubert (pthubert)
Cc: [email-masked]
Subject: Re: [Roll] updating DAO caches (was Re: Something to ADD)

[snip]

                                                        If you buy

Would you agree on that?

I do. Fairly simple, already supported. If the node cannot store the route
then you go back to the root 

but the support of DAO must stay in the base spec for all networks that need
it to (1) avoid too much

path.

I would be fully supportive of such an initial approach.

JP.

Pascal

---

From: "Roger K. Alexander" <[email-masked]>
Date: Thu, 19 Nov 2009 11:27:14 -0500

> Sent: Thursday, November 19, 2009 6:09 AM
> To: JP Vasseur
> Cc: [email-masked]; [email-masked]

No-DAOs cannot be a requirement even in the case of multiple parents since
the link connectivity may not be there. Even with multiple parents the
broken connectivity must be solved by the state-storing common ancestor to
the old and new parents. With multiple parents information consistency will
require that all current parents receive the DAO.

---

From: "Roger K. Alexander" <[email-masked]>
Date: Thu, 19 Nov 2009 11:28:20 -0500

> Richard Kelsey
> Sent: Thursday, November 19, 2009 9:42 AM
> To: JP Vasseur
> Cc: [email-masked]

Until a focused P2P mechanism is introduced I would agree that the potential
for P2P traffic flowing through the root will be a consequence that has to
be accepted.

---

From: JP Vasseur <[email-masked]>
Date: Thu, 19 Nov 2009 18:21:21 +0100

> base.  Doing so will require more than just coming up with

I need to provide more data to back this up. Will do shortly.

> network without through the root.

In the very worst case (your ancestor is the root) you have to go  
through
the root. If you have DAO and cache routes, you have a shortcut.

> counted on to greatly reduce the traffic throught the root.

Why makes you think this ?

---

From: "Julien Abeille (jabeille)" <[email-masked]>
Date: Thu, 19 Nov 2009 18:42:32 +0100

Hi Richard,

Pure source routing is supported in the draft. I think it's much less
random to maintain this with specific messages (non stored DAOs) than
with application traffic. This way the root always has a route to every
node. What are you missing for your scenario?

Best,
Julien

> Sent: jeudi 19 novembre 2009 16:50
> > > RPL ignores P2P when choosing parents.  Getting a good 
> P2P route out 
> > > of RPL is a matter of luck, not design.
> > 
> base.  Doing so will require more than just coming up with an 
> appropriate OF.
> 
> transit via the 
> routes that go through the root even if all nodes store DAOs. 
>  For example, if the root has N children with roughly equal 
> subgraphs, then each node can reach only 1/N of the network 
> without through the root.
> 
> outward?  Need 
> > to wait until you receive a packet, then record route and do source 
> > routing?
> 
> My point is that your argument in favor of requiring multiple 
> DAO caches is also an argument that DAO is not adequate for 
> P2P routing.
> 
> You are claiming that we have to cache DAOs in non-root nodes 
> because otherwise there is too much traffic through the root. 
>  If there is too much traffic through the root without the 
> caching, then there is almost certainly too much even with 
> the caching.  Having nodes cache DAOs cannot be counted on to 
> greatly reduce the traffic throught the root.
>

---

From: Geoff Mulligan <[email-masked]>
Date: Thu, 19 Nov 2009 12:23:22 -0700

While I agree that in most networks you would want to store DAOs so that
you can send packets in both directions, I can also see networks that
likely just collect data from sensor end-nodes and DAOs would be
unnecessary.

But I agree with Richard, that for many P2P applications even storing
DAOs will not provide even a "good enough" P2P route and that some other
alternative routing mechanism/protocol is necessary.

	geoff

---

From: JP Vasseur <[email-masked]>
Date: Thu, 19 Nov 2009 22:31:43 +0100

> likely just collect data from sensor end-nodes and DAOs would be

They surely exist but ... back to our requirement documents we need  
more than unidirectional flows ...

> alternative routing mechanism/protocol is necessary.

would you have any evidence of this ?

---

From: Geoff Mulligan <[email-masked]>
Date: Thu, 19 Nov 2009 14:55:11 -0700

As I understand the requirements for building automation or home control
or industrial control there are requirements for two way flows.
Collection is flow and control is a flow - do you consider these as two
unidirectional flows?

As for "evidence" about the need for an alternative protocol, the fact
that it appears we will have sub-optimal P2P routing (need to traverse
potentially to the DAG root or at best case a common parent in the DAG)
would strongly indicate that for building and home control applications
and smart grid control applications DAGs will very likely not provide
the needed performance - both Richard and Jerry have said this.

Since no one has yet been able to implement RPL we don't have proof and
I am fully supportive of getting RPL done so that we can see what it can
and can't do. we need to understand and be ready to start work on a
solution if RPL cannot adequately support bidirectional and P2P flows.

	geoff

---

From: Michael Richardson <[email-masked]>
Date: Fri, 20 Nov 2009 14:38:41 -0500

>>>>> "Jerald" == Jerald P Martocci <[email-masked]> writes:
    Jerald> As probably the strongest proponent of the P2P requirement
    Jerald> on this mailing list, I will readily admit that even in
    Jerald> building control only about 25% of the router nodes need to
    Jerald> pass intra-LLN P2P messages.  As I understand the DAO

1/4 of the nodes need P2P messages, but how much traffic does that
represent?  Is it a big percentage of overall traffic?  Does it have
particular characteristics that make a trip through the root bad
(i.e. latency) 

    Jerald> So yes, I think we either need to design outward traffic
    Jerald> into the DAG at the same level as we do inward traffic; or
    Jerald> devise an on-demand scheme where a node can easily
    Jerald> 'discover' another node in the DAG as needed. Richard's
    Jerald> comment below is profound saying that right now establishing
    Jerald> a good outward link is a matter of luck, not design.

When you say "discover", I think you mean:
     discover a path through cousin nodes that avoids the root

I too, would like to have this.

I think that this could be a different protocol --- that it could
leverage the communication used by the DAG to implement some kind of
flood-fill algorithm to learn specific P2P routes that are important.

I think the constraints of least-capable nodes excludes this from the
base protocol -- but it's really want I think I care about.

- --

---

From: JP Vasseur <[email-masked]>
Date: Mon, 23 Nov 2009 11:45:20 +0100

> flood-fill algorithm to learn specific P2P routes that are important.

Let's first figure out if we need any other mechanisms beyond what we  
have.
You might gae notice the presence of route-tag to tag important  
routes, this
could be used to improve P2P path but let's first determine if we need  
anything
more first.

> iQEVAwUBSwbwP4CLcPvd0N1lAQIOjAf/VrBNnnxuVjhoV7CVZL2vuT1lJhJiMOH3
> iDWPlL5OCjwjpkjnC2HLYIxxIYh+kMKrqUvea2BnEoMYIAgfG7MsjuU6eFIY5hMe
> gywIbHhf5Zs69HkWxO6uUj4h4F2eiJAJjrTp8b207DWEY+oR/Ky0m1ffH1TCGuOz
> jlwqsSMI94M/RLPSwCw/iGD/zLNDyjvI9Sird16YQ7TP2FM2JTRTqJPOpt74dNCR
> KPeWOUIfK5kKd3S9tYOYC1BRyWUNUFlDO1iApA5YCIcFhQbi3rCqtfJWQqqKcumC
> Ojw1sPchsmdfLb7ScYgYKOgdimkzG4Ga+jOdtCv0HqvrviwNJy+A3Q==
> =Ujy3

---

From: [email-masked]
Date: Mon, 23 Nov 2009 09:15:15 -0600

Hi Michael,

Comments interlaced below.

Jerry

Michael Richardson <[email-masked]> 
Sent by: [email-masked]
11/20/2009 01:39 PM

To
[email-masked]
cc

Subject

The traffic generated by these 25% of these intra-LLN is also about 25% of 
the overall traffic.  As an example, a room controller may need to access 
the 'outdoor air temperature' and 'relative humidity' sensors so it can 
properly calculate its control algorithm.  These two points are common to 
many rooms and will only be instrumented once.  All other room control 
will need to reference these points.  As for latency, this is important 
since the room control algorithm cannot be calculated until all input 
variables have been accessed.  We need to complete the read request in 
under 500 ms.

Yes.  Maybe 'discover' may mean something different in IETF parlance. 
Maybe 'find' a path would be better.  The point I am trying to make is 
that right now using DAOs, we need to create and maintain a link for every 
node in the DAG on the chance that there may need to one day be a message 
that must traverse the link.  So, on a 200 node network where every node 
might need to talk to any other node, there would need to be 39,800 (i.e. 
200*199) links created and maintained.   In reality only 50 links (i.e. 
200*25%) are required.  I'm suggesting that if we had a means to find a 
P2P path as needed, we could save significant processing power and DAG 
overhead.

good!

- -- 
]       He who is tired of Weird Al is tired of life!           | 
firewalls  [
]   Michael Richardson, Sandelman Software Works, Ottawa, ON    |net 
architect[
] [email-masked] http://www.sandelman.ottawa.on.ca/ |device 
driver[
   Kyoto Plus: watch the video <http://www.youtube.com/watch?v=kzx1ycLXQSE
                                then sign the petition.