Subject: [Roll] outward routes and Destination Advertisements

From: Richard Kelsey <[email-masked]>
Date: Tue, 08 Sep 2009 22:55:23 -0400

RPL discovers outward routes by way of Destination
Advertisements passed up the DAG.  Nodes that lack
sufficient route storage add themselves to a route stack (a
kind of route record).  Nodes that do have sufficient
storage store the route stack and do not forward it upwards.

One issue is the potential for an explosion of Destination
Advertisements if each router forwards each advertisement it
receives to all of its parents.  Even if each node only
forwards advertisements to a single parent the root may
receive a great deal of redundant information, as the same
links may appear in many route stacks.

There are fundamentally three scenarios:
  (1) root cannot store outward routes to all nodes
  (2) sufficent route storage only on root
  (3) route storage on root and possibly intermediate nodes
The networks that I am familiar fall into either (1) or (2).

For (1), I think the only solution is to unicast record
route/destination advertisements as needed.  It would be
good if a DAG root could indicate that it was only capable
of storing routes temporarily and that they should be
reported on demand and as needed.

For (2), it would be more efficient for each node to send
its set of parents to the root, rather than enumerating some
or all of the possible paths using route stacks.  Changes in
the parent set could be sent directly, without including any
redundant, unchanged links.  This would eliminate the need
for the Path Digest in RA-DIOs.

There is a problem with this approach in scenario (3), in
that the parent information may be routed past intermediate
nodes that would otherwise be able to store it.  This is
very similar to the problem of deciding which parent to use
when forwarding advertisements or P2P messages inward along
a DAG.  You would like to make use of any intermediate route
storage, but there is currently no way of determining which
parent may have it.  It should be possible to indicate in
the RA-DIO which parents should be sent Destination
Advertisements, perhaps by including the depth of the
deepest ancestor capable of storing routes.

In summary, I think we should:
  - Replace the Destination Advertisement route stack with
    a list of parents.  Destination Advertisements would be
    sent to only a single parent.
  - Remove the Path Digest from RA-DIOS.
  - Add an RA-DIO flag to indicate that the root does not
    want Route Advertisements sent proactively.
  - Add an RA-DIO field giving the depth of the deepest
    ancestor capable of storing routes and preferentially
    forward Route Advertisements via the parent with the
    deepest such ancestor.

Yes?  No?  Thoughts?
                              -Richard Kelsey

---

From: Mukul Goyal <[email-masked]>
Date: Wed, 9 Sep 2009 09:49:36 -0500 (CDT)

Richard,

Please correct me if my understanding is wrong. It seems that as per your proposal a node should unicast its parent set (or delta of the parent set) to its closest ancestor that can store this information.

Thanks
Mukul
----- Original Message -----
From: "Richard Kelsey" <[email-masked]>
To: [email-masked]
Sent: Tuesday, September 8, 2009 9:55:23 PM GMT -06:00 US/Canada Central
Subject: [Roll] outward routes and Destination Advertisements

Yes?  No?  Thoughts?
                              -Richard Kelsey   
_______________________________________________
Roll mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/roll

---

From: Mukul Goyal <[email-masked]>
Date: Wed, 9 Sep 2009 10:02:36 -0500 (CDT)

Richard

Here is another thought:

If the root does not store the route to a destination proactively, it depends on the next periodic update (DAO) from the destination when it does need a route to the destination. If there is a way for the root to request an immediate DAO from a destination, we could make periodic updates (of DAOs) sparse.

Thanks
Mukul
----- Original Message -----
From: "Mukul Goyal" <[email-masked]>
To: "Richard Kelsey" <[email-masked]>
Cc: [email-masked]
Sent: Wednesday, September 9, 2009 9:49:36 AM GMT -06:00 US/Canada Central
Subject: Re: [Roll] outward routes and Destination Advertisements

Richard,

Thanks
Mukul
----- Original Message -----
From: "Richard Kelsey" <[email-masked]>
To: [email-masked]
Sent: Tuesday, September 8, 2009 9:55:23 PM GMT -06:00 US/Canada Central
Subject: [Roll] outward routes and Destination Advertisements

Yes?  No?  Thoughts?
                              -Richard Kelsey

---

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

Date: Wed, 9 Sep 2009 09:49:36 -0500 (CDT)
   From: Mukul Goyal <[email-masked]>

   Please correct me if my understanding is wrong. It seems that as per
   your proposal a node should unicast its parent set (or delta of the
   parent set) to its closest ancestor that can store this information.

Mukul,

Not quite.  The node unicasts its parent set to whichever of
its parents has the closest ancestor that can store the
information.  That parent then forwards it to one of its own
parents, and so on until the Destination Advertisement
reaches a node that can store it.  The originating node does
not know the identity of the ancestor; it only knows the
distance to it.
                                -Richard Kelsey

---

From: Mukul Goyal <[email-masked]>
Date: Wed, 9 Sep 2009 10:21:13 -0500 (CDT)

So, each router, that has such capacity, stores a part of the DAG topology. In other words, the collection of such routers store (close to) complete DAG topology.

Thanks
Mukul
----- Original Message -----
From: "Richard Kelsey" <[email-masked]>
To: "Mukul Goyal" <[email-masked]>
Cc: [email-masked]
Sent: Wednesday, September 9, 2009 10:14:32 AM GMT -06:00 US/Canada Central
Subject: Re: [Roll] outward routes and Destination Advertisements

Mukul,

---

From: Richard Kelsey <[email-masked]>
Date: Wed, 09 Sep 2009 14:31:45 -0400

Date: Wed, 9 Sep 2009 10:02:36 -0500 (CDT)
   From: Mukul Goyal <[email-masked]>

Mukul,

   Here is another thought:

   If the root does not store the route to a destination proactively, it
   depends on the next periodic update (DAO) from the destination when it
   does need a route to the destination. If there is a way for the root
   to request an immediate DAO from a destination, we could make periodic
   updates (of DAOs) sparse.

Yes.

Requesting a DAO might be costly, especially if you are in a
hurry.  If the root is short on RAM there may be no other
good option.  My thinking was that in such a case there
would be no periodic updates of DAOs at all.

                                   -Richard Kelsey

---

From: Richard Kelsey <[email-masked]>
Date: Wed, 09 Sep 2009 14:35:26 -0400

Mukul,

   Date: Wed, 9 Sep 2009 10:21:13 -0500 (CDT)
   From: Mukul Goyal <[email-masked]>

   So, each router, that has such capacity, stores a part of the DAG
   topology. In other words, the collection of such routers store (close
   to) complete DAG topology.

Yes.  I think that is how the draft's DAOs work as well.
The difference is whether outward paths must initially be
traversed by DAOs traveling inwards (as in the draft) or
are calculated from parent lists (as I am proposing).

                                  -Richard Kelsey

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Mon, 21 Sep 2009 07:45:01 +0200

Hi Mukul and Richard;

I'm still fighting with the value and consequences of fanning out DAOs
and including source route information.
As you notice in this thread, soon as we pass packets to more than one
parent, there is an explosion of information and states. But that's not
the only issue:

- The OF selects a preferred parent and often at least one alternate to
provide diversity inwards. From a node standpoint, the reverse DAG does
not necessarily have the same properties. So even fanning out the DAO to
all parents does not guarantee that each parent will have alternate
paths towards that Destination. I suspect that fanning out is not the
way to go. If a node is a really important destination multiple DAG is
probably the answer. Else, I trust that making a parent more attractive
for a certain destination will attract DAOs and thus provide it
alternates. Attractiveness could be computed by some hash technique.

- in source route is being used, then a packet that fails the hop-by-hop
L2 retries in the middle of that source route path cannot be passed over
an alternate route, because the intermediate node is stateless and does
not know better. In that example it appears that there is no DAG
protection. And if there's no end-to-end protection along the source
route path, the source does not know that the path is broken and thus
cannot switch to an alternate path. And because the source cannot switch
to an alternate path, there's no point for the source of a source route
path to remember more than one path.

- if the metrics are asymmetrical, and the traffic is mostly inwards,
then the preferred parent will but optimal for going to the root, not
coming from the root. It could be possible that the OF selects different
parents for passing DAO than for attachment. At this point I do not see
why this would be a problem but maybe we'll need to revisit our wording
about preferred parent if we go along that path. In particular, because
the preferred parent dictates the depth, it might be possible that a
preferred parent is selected to optimize traffic from the root and thus
is not selected as default GW because another parent is better for
traffic towards the root.

Thoughts?

Pascal

>-----Original Message-----
>From: [email-masked] [mailto:[email-masked]] On Behalf Of
Richard Kelsey
>Sent: mercredi 9 septembre 2009 20:35
>To: Mukul Goyal
>Cc: [email-masked]

---

From: Richard Kelsey <[email-masked]>
Date: Mon, 21 Sep 2009 08:06:12 -0400

Hi Pascal,

   Date: Mon, 21 Sep 2009 07:45:01 +0200
   From: "Pascal Thubert (pthubert)" <[email-masked]>

   - [...] If a node is a really important destination multiple DAG is
   probably the answer.

Definitely.  This is the only way to really take advantage
of locality, which is very important.  A node a couple of
hops away can be much further off in a DAG rooted on some
third party.

   Else, I trust that making a parent more attractive
   for a certain destination will attract DAOs and thus provide it
   alternates. Attractiveness could be computed by some hash technique.

Please, no more DAG additions.  RPL is already significantly
more complex than the equivalent mechanisms in the deployed
systems that I am aware of.

   not know better.

This isn't an issue if the intermediate node lacks the
memory to store the alternate routes, which is the case for
us, at least.  Storing an extra parent per DAG isn't so bad,
but storing data about descendents is out of the question.
(Obviously, other networks will be different.)

   In that example it appears that there is no DAG
   protection. And if there's no end-to-end protection along the source
   route path, the source does not know that the path is broken and thus
   cannot switch to an alternate path.

This is why it is necessary to have end-to-end
acknowledgements within this kind of network.  Without them,
there is no way to know when routes are broken, which in
turn means there is no way to know when to fix them.

   coming from the root.

Our experience has been that asymmetric links are also
unreliable links.  Overall, it is much easier and more
reliable to detect and discard asymmetric links at the
link layer than to try to accommodate them at the routing
layer.  They just aren't worth the extra effort.

                               -Richard Kelsey

---

From: [email-masked]
Date: Mon, 21 Sep 2009 10:41:06 -0500

Richard

You wrote - - - - - - - -
Our experience has been that asymmetric links are also
unreliable links.  Overall, it is much easier and more
reliable to detect and discard asymmetric links at the
link layer than to try to accommodate them at the routing
layer.  They just aren't worth the extra effort. -------

Just a small comment -  Our experience has shown, in installed commercial
buildings,  that asymmetric routes
are more the norm, and that the quality of the paths varies considerably
based on the direction.

 When the selection of the route is chosen - a symmetric route certainly
does make things easier -
and may be considered preferred,  but  I would not wish to exclude an
asymmetric route - especially if a symmetric route is not available.

A reliable asymmetric route is better than a low quality symmetric route or
no route at all [ if a symmetric route can not be determined ].

The ability for a symmetric route is very dependent on the chosen radio and
antenna, in addition to the placement of the
equipment relative to the metalwork (ductwork, structural steel, metal
cabinets, etc.) in its vicinity.

Ted

             Richard Kelsey                                                
             <richard.kelsey@e                                             
             mber.com>                                                  To 
             Sent by:                  "Pascal Thubert (pthubert)"         
             roll-bounces@ietf         <[email-masked]>                
             .org                                                       cc 
                                       [email-masked]                       
                                                                   Subject 
             09/21/2009 07:06          Re: [Roll] outward routes and       
             AM                        Destination Advertisements          

                                                                           

Hi Pascal,

                               -Richard Kelsey

---

From: Richard Kelsey <[email-masked]>
Date: Mon, 21 Sep 2009 13:28:54 -0400

Ted, 

   From: [email-masked]
   Date: Mon, 21 Sep 2009 10:41:06 -0500

   Just a small comment - Our experience has shown, in installed
   commercial buildings, that asymmetric routes are more the norm, and
   that the quality of the paths varies considerably based on the
   direction.

   When the selection of the route is chosen - a symmetric route
   certainly does make things easier - and may be considered
   preferred, but I would not wish to exclude an asymmetric route -
   especially if a symmetric route is not available.

I overstated the case, for which I apologize.  I was
trying to put too many things into one message.

Our experience isn't that asymmetric links are unreliable,
but that they can't be relied on to be consistently
asymmetric, if that makes sense.  At the link layer we
discard the better of the two direction's qualities and
treat the link as if it were a symmetric link of the same
quality as the worse of the two directions.

The routing layer then treats all links as symmetric.

   The ability for a symmetric route is very dependent on the chosen
   radio and antenna, in addition to the placement of the equipment
   relative to the metalwork (ductwork, structural steel, metal
   cabinets, etc.) in its vicinity.

Yes.  What it means for a link to be 'symmetric' or
'reliable' also vary widely.
                                 -Richard Kelsey

---

From: Kris Pister <[email-masked]>
Date: Mon, 21 Sep 2009 12:13:25 -0700

Richard - I'm used to using queues from the link layer to let me know 
that one of the hops along a route is broken. 
You seem to be advocating for end-to-end ACKs to figure that out.  Is 
that right?

ksjp

---

From: Richard Kelsey <[email-masked]>
Date: Mon, 21 Sep 2009 17:33:53 -0400

Kris,

   Date: Mon, 21 Sep 2009 12:13:25 -0700
   From: Kris Pister <[email-masked]>

   Richard - I'm used to using queues from the link layer to
   let me know that one of the hops along a route is broken.
   You seem to be advocating for end-to-end ACKs to figure
   that out.  Is that right?

Yes, but only end-to-end within the mesh.  My hope is that
this can be done by 6LoWPAN and need not involve ROLL at
all.  I only mentioned it because Pascal pointed out that
the lack of end-to-end protection is a problem for source
routes.

The nice thing about end-to-end ACKs is that getting an ACK
means that the packet got to the destination.  Most other
mechanisms, including, I think, observing link layer queues,
treat the absence of a failure report as a positive
acknowledgement.  That just seems too risky in a lossy
environment.  You can't expect nodes to reliably send
messages saying that they are having trouble sending
messages.
                           -Richard Kelsey

---

From: Kris Pister <[email-masked]>
Date: Mon, 21 Sep 2009 17:27:52 -0700

I like the last line of your email - that has a nice ring to it, in a 
Joseph Heller sort of way. :)

I disagree with the statement though.  If node X is a part of a route 
from A to Z, then
the fact that it loses its link to Y doesn't in general mean that it 
can't talk to W anymore.
If X disappears completely, then the next time that W tries to send to 
X, W will detect the problem.

I guess I'm making the underlying assumption that we use link-layer 
ACKs.  I actually meant to write "cues", like 'MAC layer failed after 5 
attempts', not "queues", but they are certainly related.

My concern with end-to-end is that it's tough on efficiency, with 
implications for throughput and lifetime.

ksjp

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Tue, 22 Sep 2009 16:19:22 +0200

I suspect we need to review / update the text for asymmetrical paths but
the spirit as I understand it goes like this:

The structure we build encompasses inwards and outwards paths. They are
not necessarily congruent though it might appear so in the current text.
In other words the DAG defines a set of parents, and some of them might
be used for inwards traffic mostly whereas others are used for outwards
traffic mostly.

What about the preferred parent ? The preferred parent is the reference
for computing the rank. That's what it is, that's all it is. A better
name should be found for that thing. Suggestions appreciated :)

When the traffic is mostly inwards, it makes sense for a OPC to use
metrics that qualify the direction towards the root to select the
preferred parent. In this case, the preferred parent is also selected as
default GW since the default route is towards the root. This is how the
draft presents things today and that corresponds to the most common
requirements.

But if outwards traffic is more important, the OF might in fact select a
preferred parent for outwards metrics. In that case, the most preferred
parent might not be selected as default GW since it might have lesser
properties inwards than other parents.

The OF might be required to make sure that there is at least one inwards
and one outwards parent with good enough link properties, whether they
are the same node or not, and the preferred parent would be the one that
results to the highest rank for this node so that both can be used as
parents, one inwards and one outwards.

Conceptually, such an OF would be really be building 2 DAGs, one for
inwards and one for outwards traffic. A node would need to detach if it
loses all good enough parents either inwards or outwards.

Pascal

>From: Richard Kelsey [mailto:[email-masked]]
>Sent: lundi 21 septembre 2009 19:29
>To: [email-masked]
>Cc: Pascal Thubert (pthubert); [email-masked]; [email-masked]

---

From: Richard Kelsey <[email-masked]>
Date: Tue, 22 Sep 2009 11:04:02 -0400

Date: Mon, 21 Sep 2009 17:27:52 -0700
   From: Kris Pister <[email-masked]>

   I disagree with the statement though.  If node X is a
   part of a route from A to Z, then the fact that it loses
   its link to Y doesn't in general mean that it can't talk
   to W anymore.

Routing problems are often not as simple as 'X loses
its link to Y'.  For example, it might be 'X temporarily
loses all its links', 'X runs out of buffer space', 
'X reboots', or just 'that packet got unlucky and
was interferred with on all N transmissions'.

   If X disappears completely, then the next
   time that W tries to send to X, W will detect the
   problem.

How does that help A, the source of the message?

   I guess I'm making the underlying assumption that we use
   link-layer ACKs.

I was assuming that as well.  Even if an intermediate node
realizes that it can't, at the moment, forward a packet to
the next hop, what does it do about it?  You can't assume
that it has a route to the source or anywhere else in
particular.  It can optimistically forward the packet to
someone else, which may or may not work for that packet
and may or may not repair the route.

   My concern with end-to-end is that it's tough on
   efficiency, with implications for throughput and
   lifetime.

Looking at the big picture, it could easily be more
efficient to be able to assume reliable message delivery and
send fewer messages.  Having a reliable delivery
confirmation makes the application writer's job much
simpler.  How many messages do you have to send before you
can be sure that the routing layer has been alerted to any
problems that exist?  With end-to-end acks, one message is
enough.

I am not proposing that we require end-to-end acks on all
messages.  I do think that end-to-end acks within the mesh
must be available as an option.  As I wrote earlier, I think
the ack mechanism belongs in 6LoWPAN, not ROLL.

                          -Richard Kelsey

---

From: Kris Pister <[email-masked]>
Date: Tue, 22 Sep 2009 08:34:56 -0700

OK, we agree that end-to-end ACKs are an important option.
I misunderstood and thought that your intent was that it be the 
default.  My mistake.

Some comments inline below - not as important now.

ksjp

> was interferred with on all N transmissions'.
I agree that all of those are not uncommon in LLNs.  I'm asserting that 
transient ones
don't affect normal operation, and long-term or permanent ones are 
detected, e.g. by our friend W.
> How does that help A, the source of the message?
Well, hopefully we've done things right so that W has another option on 
the DAG and can still get the message through to Z via an alternate 
path.  If losing X as a parent means that W only has one remaining 
parent, then it should go about the process of finding another one in 
order to maintain path diversity.  If losing X means that W doesn't have 
any parents on this DAG, then it's got bigger problems, but should 
presumably issue a "destination unreachable".
> particular.  
Hmm.  I guess I'd never build a network like that.  Now I understand 
your concern.
> It can optimistically forward the packet to
Using another option on the DAG is not optimistic, it's just part of 
normal DAG operation.
That forwarding effort is independent of route repair, yes?