Subject: [Roll] clarification about source routing

From: "Julien Abeille (jabeille)" <[email-masked]>
Date: Wed, 28 Oct 2009 13:52:07 +0100

Hi all,
 
just a clarification:
it seems that when using source routing, the routes are recorded when
DAOs are sent, up to the DAG root. It means that routes are recorded
proactively. 
Until now, I thought that we would record routes on data (layer 5)
packets. Hence I thought source routing + record route would only work
in MP2P (meaning when a smart object inititates the traffic) and that it
would not work if the DAG root (or another smart object, P2P mode) wants
to initiate traffic. I think this was the understanding of others in
ROLLE meeting.
 
if my (new) understanding is correct, record route is proactive, done
with control packets (DAOs), hence this enables P2MP, MP2P, P2P. 
Is my understanding correct?
 
Best,
Julien

---

From: JP Vasseur <[email-masked]>
Date: Wed, 28 Oct 2009 14:01:00 +0100

Hi Julien,

On Oct 28, 2009, at 1:52 PM, Julien Abeille (jabeille) wrote:

> Hi all,
>
> just a clarification:
> it seems that when using source routing, the routes are recorded  
> when DAOs are sent, up to the DAG root

Up to a point where routes can be stored, which may or may not be the  
DAG Root.

> . It means that routes are recorded proactively.
> packets. Hence I thought source routing + record route would only  
> work in MP2P (meaning when a smart object inititates the traffic)  
> and that it would not work if the DAG root (or another smart object,  
> P2P mode) wants to initiate traffic. I think this was the  
> understanding of others in ROLLE meeting.
>
> if my (new) understanding is correct, record route is proactive,  
> done with control packets (DAOs), hence this enables P2MP, MP2P, P2P.

Yes.

JP.

>
> Best,
> Julien
> _______________________________________________
> Roll mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/roll

---

From: Richard Kelsey <[email-masked]>
Date: Wed, 28 Oct 2009 10:40:52 -0400

Date: Wed, 28 Oct 2009 13:52:07 +0100
   From: "Julien Abeille (jabeille)" <[email-masked]>

   it seems that when using source routing, the routes are recorded
   when DAOs are sent, up to the DAG root. It means that routes are
   recorded proactively.

Correct, although as JP pointed out, intermediate nodes may
store the routes rather than passing them on to the root.

It would be good to have an on-demand record route mechanism
as well, as the DAG root may not have sufficient RAM to
store routes sent proactively.

I am curious as to why DAOs record the entire route.  Record
route makes sense when sent on demand.  For proactive
messages I would think that it would be simpler and much
more efficient if DAOs contained only the originator's
identity and its preferred parent, or possibly some set of
parents.  The root or whichever node caches the information
could then assemble routes as needed.  This would reduce the
traffic generated by changes to the DAG.  It would also
simplify the decision of when to send a new DAO, as it would
only depend on local information.

Yes.  Note that the P2P you get this way is may be limited
by the bandwidth of the root.  Even if intermediate nodes
store routes, it is quite likely that the least common
ancestor of any particular pair of nodes will be the root or
one of its near descendants, again limiting the available
P2P bandwidth.
                              -Richard Kelsey

---

From: JP Vasseur <[email-masked]>
Date: Wed, 28 Oct 2009 15:49:21 +0100

> only depend on local information.

You still have an issue though - suppose that you have: A----B----C---- 
D----E---Root
B and C cannot store routes.
A advertises the prefix P1.
How cannot you not record the IPv6 address of B and C when sending DAO  
to advertise P1 since you need to source route the packet from D to A ?

> done

Yes, we're currently running some simulation to validate this  
assumption.

---

From: Richard Kelsey <[email-masked]>
Date: Wed, 28 Oct 2009 11:58:48 -0400

From: JP Vasseur <[email-masked]>
   Date: Wed, 28 Oct 2009 15:49:21 +0100

   > only depend on local information.

   You still have an issue though - suppose that you have:
   A----B----C----D----E---Root
   B and C cannot store routes.
   A advertises the prefix P1.
   How cannot you not record the IPv6 address of B and C when sending DAO  
   to advertise P1 since you need to source route the packet from D to A ?

Because B and C send in their own DAOs with their own
IPv6 address as the prefix and with their own parents.
Are you suggesting that there will be nodes that will
not send in DAOs containing their IPv6 addresses?  If
the 'D' bit is set in a DIO all nodes are supposed to
send in a DAO, but I suppose they might use a different
prefix.

I am pretty sure it is true in the case where only the root
stores routes :-).
                                  -Richard Kelsey

---

From: JP Vasseur <[email-masked]>
Date: Wed, 28 Oct 2009 17:07:37 +0100

> send in a DAO, but I suppose they might use a different

The point I was trying to make is that in the case above, we do need  
to record
in the DAO the IP address of both B and C up to D. I had the  
impression that
you were suggesting a different mechanism ?

> I am pretty sure it is true in the case where only the root

Ah yes, in this case (only the DAG can store routes) the answer is  
pretty straightforward ;-))

---

From: Richard Kelsey <[email-masked]>
Date: Wed, 28 Oct 2009 12:54:37 -0400

From: JP Vasseur <[email-masked]>
   Date: Wed, 28 Oct 2009 17:07:37 +0100

   The point I was trying to make is that in the case above, we do
   need to record in the DAO the IP address of both B and C up to D. I
   had the impression that you were suggesting a different mechanism ?

The mechanism is nearly the same.  Let me try to explain it
more clearly using your example.

In your example, D stores routes.  What D needs is a set of
links:
  A---B, B---C, C---D

>From this D can assemble routes to A, B, and C.  As things
stand now, D will receive three DAOs, two of which include
non-empty reverse route stacks:
  A[BC], B[C], C[]

I am suggesting that the reverse route stack be limited to a
single hop, rather than contain the entire path.  In this
case, D would receive
  A[B], B[C], C[]

In the new scheme, DAOs would be forwarded unmodified.  In
particular they would not get larger as they go up the DAG.
Only those nodes that changed parents would need to send new
DAOs.  Nodes whose ancestors change parents would not need
to send new DAOs.  This would greatly reduce the traffic
generated when a node high in the DAG changes parents.

                               -Richard Kelsey

---

From: JP Vasseur <[email-masked]>
Date: Wed, 28 Oct 2009 18:35:41 +0100

Hi Richard,

> non-empty reverse route stacks:

You would send a single DAO, not 3 since that would not scale, the Root
would end up receiving quite a few DIOs.

In this case, there would be a single DIO with A[BC].

Makes sense ?

---

From: Richard Kelsey <[email-masked]>
Date: Wed, 28 Oct 2009 14:17:07 -0400

From: JP Vasseur <[email-masked]>
   Date: Wed, 28 Oct 2009 18:35:41 +0100

   > non-empty reverse route stacks:

JP,

I am going to assume you mean DAO everywhere, not DIO.
If you did mean DIO, then I do not understand what you
are saying.

Exactly my concern.

How does this come about?  I do not think there is anything
in the current draft describing how DAOs can be suppressed
in this fashion.

While it would help if we could suppress the DAOs from
interior nodes, they are usually outnumbered by the leaf
nodes.  For this example, in the more likely situation of A
having siblings, even with some kind of suppression D would
receive multiple DAOs each with a copy of the route from B
on up.
                             -Richard Kelsey

---

From: "Julien Abeille (jabeille)" <[email-masked]>
Date: Wed, 28 Oct 2009 20:46:06 +0100

Hi Richard,

Not sure this is explained well in the draft, but with A - B - C - D (D
as root), A sends a DAO with prefix pA, upon reception B sends DAO with
prefix pA and pB, C sends DAO with prefix pA, pB, pC (B and C also add
their address to the reverse route stack). C ends up sending one DAO
with all three perfixes

Best,
Julien

> -----Original Message-----
> From: [email-masked] [mailto:[email-masked]] On 
> Behalf Of Richard Kelsey
> Sent: mercredi 28 octobre 2009 19:17
> To: JP Vasseur (jvasseur)
> Cc: [email-masked]
> Subject: Re: [Roll] clarification about source routing
> 
> 
> If you did mean DIO, then I do not understand what you are saying.
> 
> in the current draft describing how DAOs can be suppressed in 
> this fashion.
> 
> receive multiple DAOs each with a copy of the route from B on up.
>                              -Richard Kelsey
>

---

From: JP Vasseur <[email-masked]>
Date: Wed, 28 Oct 2009 20:49:03 +0100

> I am going to assume you mean DAO everywhere, not DIO.

Arrr ... yes of course ;-)

> in the current draft describing how DAOs can be suppressed

Then we should clarify it, this is how I would implement it for sure.  
DAOs are sent to
parents, not targeted to any specific node. Thus in that case, A would  
send
a DAO to B, B would send its own DAO to C, etc ...  you would indeed
come up with a single DAO from D to E, etc ...

This need to be clarified in the document.

> receive multiple DAOs each with a copy of the route from B

But do you see an issue with this ?

Cheers.

JP.

---

From: Richard Kelsey <[email-masked]>
Date: Wed, 28 Oct 2009 16:54:09 -0400

Julien,

   Date: Wed, 28 Oct 2009 20:46:06 +0100
   From: "Julien Abeille (jabeille)" <[email-masked]>

The Destination Advertisement Object has space for only one
prefix and one reverse route stack.  Are you saying that
multiple DAOs can be included in a single ICMPv6 message?

To make this aggregation work, nodes higher in the DAG have to
wait to receive the DAOs from their descendants.  How long
should they wait?
                              -Richard Kelsey

---

From: Mukul Goyal <[email-masked]>
Date: Wed, 28 Oct 2009 16:04:26 -0500 (CDT)

Another question is what happens if the prefixes can't be aggregated together. i.e. what happens if I can not aggregate prefixes advertized by my children into one prefix? In this case, it seems that I will be forced to send a large number of prefixes to my parent and the parent would need to send a still larger number of prefixes to its parent and so on.

This is a concern some of us have had for a long time.

Thanks
Mukul

----- Original Message -----
From: "Richard Kelsey" <[email-masked]>
To: "Julien Abeille (jabeille)" <[email-masked]>
Cc: [email-masked]
Sent: Wednesday, October 28, 2009 3:54:09 PM GMT -06:00 US/Canada Central
Subject: Re: [Roll] clarification about source routing

Julien,

---

From: Jonathan Hui <[email-masked]>
Date: Wed, 28 Oct 2009 18:47:27 -0700

> wait to receive the DAOs from their descendants.  How long

To make this more clear, lets replace A with X, Y, and Z hanging off  
of B:

   X
    \
Y - B - C - D
    /
   Z

Assume again that B and C cannot store any routes.  In the best case,  
the DAOs that D will receive are X[BC], Y[BC], and Z[BC].  As  
currently specified, there is no way to aggregate those three DAOs  
into a single DAO.  It is possible to carry multiple DAOs in a single  
datagram, but a "stateless" node can only buffer so much before  
offloading DAOs to its parent(s).

In a network where all nodes (except the root) do not maintain any DAO  
state, the sole purpose of DAOs is to communicate DAG edges to the  
root.  The record-route format is, in some cases, more efficient  
because it provides a list of addresses, rather than a list of address  
pairs.  The best case for using record-route is a long linear network  
- half of what it would cost to communicate address pairs.  The worst  
case is a network that has high fan-out - a record-route message must  
be communicated for each leaf node.  More simply, the number of DAOs  
that MUST be communicated scales with the number of DAG leaves.

We could do a bit better in the high fain-out case by allowing a node  
to "terminate" a record-route when it thinks its redundant, preventing  
nodes further down the line from appending, but I think the complexity  
of doing this right outweighs the benefits.  Though, as Richard  
mentioned, record-route is useful for on-demand purposes.  It can also  
be extremely useful as a debugging/diagnosis tool.  Given that, it  
seems useful to support both parent-only and record-route reporting.

--
Jonathan Hui

---

From: Michael Richardson <[email-masked]>
Date: Wed, 28 Oct 2009 22:44:38 -0400

(XYZ/BCD analysis, which I understood, and agree with... A first!)

>>>>> "Jonathan" == Jonathan Hui <[email-masked]> writes:
    Jonathan> We could do a bit better in the high fain-out case by
    Jonathan> allowing a node to "terminate" a record-route when it
    Jonathan> thinks its redundant, preventing nodes further down the
    Jonathan> line from appending, but I think the complexity of doing
    Jonathan> this right outweighs the benefits.  Though, as Richard
    Jonathan> mentioned, record-route is useful for on-demand purposes.
    Jonathan> It can also be extremely useful as a debugging/diagnosis
    Jonathan> tool.  Given that, it seems useful to support both
    Jonathan> parent-only and record-route reporting.

Which one is MUST, and which one is MAY?

-- 
]       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: JP Vasseur <[email-masked]>
Date: Thu, 29 Oct 2009 10:35:59 +0100

Hi Jonathan,

What I was referring to was to pack prefix in DAO, a very light change  
in the spec (just make use of TLV) and factor the common fields. This  
allows to reduce the number of packets very significantly as we get  
closer to the root.

There two benefits here:
1) You send one DAO between C and D instead of 3
2) You can also pack the Reverse Route Stack whenever possible for all  
prefix sharing the same routes.

Let's suppose that:
1) X advertises two prefixes X1 and X2
2) Y advertises two prefixes Y1, Y2 and Y3
3) Z advertised one prefix: Z1

Instead of sending 6 DAO, C would send one DAO to D would look like  
this:
X1,X2[XBC], Y1,Y2,Y3[YBC], Z1[ZBC]

Note that you could when possible also aggregates prefixes at the same  
time if they share a common path.

BAck to you timing question Richard, it depends of the sequence of  
events but there is no need to wait.
C could start with one DAO and then start to pack at it receives more,  
the same reasoning applies to other
nodes.

Others, thoughts ?

Thanks.

JP.

On Oct 29, 2009, at 2:47 AM, Jonathan Hui wrote:

> Assume again that B and C cannot store any routes.  In the best  
> case, the DAOs that D will receive are X[BC], Y[BC], and Z[BC].  As  
> into a single DAO.  It is possible to carry multiple DAOs in a  
> single datagram, but a "stateless" node can only buffer so much  
> before offloading DAOs to its parent(s).
>
> In a network where all nodes (except the root) do not maintain any  
> DAO state, the sole purpose of DAOs is to communicate DAG edges to  
> the root.  The record-route format is, in some cases, more efficient  
> because it provides a list of addresses, rather than a list of  
> address pairs.  The best case for using record-route is a long  
> linear network - half of what it would cost to communicate address  
> pairs.  The worst case is a network that has high fan-out - a record- 
> route message must be communicated for each leaf node.  More simply,  
> the number of DAOs that MUST be communicated scales with the number  
> of DAG leaves.
>
> We could do a bit better in the high fain-out case by allowing a  
> node to "terminate" a record-route when it thinks its redundant,  
> preventing nodes further down the line from appending, but I think  
> the complexity of doing this right outweighs the benefits.  Though,  
> as Richard mentioned, record-route is useful for on-demand  
> purposes.  It can also be extremely useful as a debugging/diagnosis  
> tool.  Given that, it seems useful to support both parent-only and  
> record-route reporting.
>
> --
> Jonathan Hui
>

---

From: Richard Kelsey <[email-masked]>
Date: Thu, 29 Oct 2009 10:54:22 -0400

I think we are focusing on minor improvements to an already
not-too-bad case, where the entire DAG is sending DAOs and
only the root stores the routes.

The issues I was trying to address with an alternate
mechanism concern:
 - DAOs sent in reaction to DAG changes
 - nodes besides the root storing routes
 - DAOs sent to multiple parents
And most especially, how do these interact with each
other?

To take one example, as far as the DAG itself goes,
switching to a new parent at the same depth has a very low
cost, and to one at a different depth only a moderate cost.
On the other hand, depending on the details of the
situation, the DAO overhead of a node switching to a new
parent may be very large.

Suppose a few nodes besides the root are capable of storing
downwards routes.  If a node changes parents such that the
ancestor storing the route to it does not change, then only
that ancestor has to be informed of the change, and only
needs to be told the identity of the new parent.  All other
path information can be inferred.

On the other hand, if the new parent results in a new
route-storing ancestor, then the entire subtree below the
parent-changing node has to be reported upwards.

There are a lot of complexities lurking here.  We need
to be clearer about what they are and how much of this
we want to support.
                            -Richard Kelsey