Subject: [Roll] proposal for DAOs in non-caching DODAGs

From: Richard Kelsey <[email-masked]>
Date: Sun, 28 Mar 2010 17:20:59 -0400

Pascal and I had a discussion on how to simplify DAOs if the
group confirms the decision to not explicitly support DAGs
with mixed caching and non-caching routers.  The obvious
simplification is that the DIO 'S' flag is either on or off
throughout a DODAG, eliminating the need to do anything when
it changes.

More interestingly, the reverse route stack is no longer
needed.  It is not used if all nodes cache DAOs.  If only
the root does so, including intermediate hops when
forwarding DAOs only duplicates information that the root
will receive from others.

Our proposal is to replace the reverse route stack with a
set of parents that is forwarded up the DAG to the root.
The DAO format stays the same, except that the reverse route
stack is now a set of parents and is not changed when
forwarded.

The root can then reconstruct the DAG and compute downwards
routes as needed.  This is not as big a change as it may
seem: in the current draft the root may have to compute the
paths to nodes whose S bit is not set.  Path computation is
simpler than for a full link-state protocol, as the DIOs
have preselected the better up/down links in forming the
DAG and other links are not reported.

The advantages of using a parent set rather than a reverse
route stack are:
  - downward path diversity while only sending DAOs
    to the preferred parent
  - DAOs do not grow with DAG depth
  - DAO forwarding is simpler

What do people think?
                                  -Richard Kelsey

---

From: "JeongGil Ko (John)" <[email-masked]>
Date: Sun, 28 Mar 2010 14:42:22 -0700

Richard,

I agree that if we start adding downwards routes then the root will have many sub-route (or sub-path) information that it already has. If we decide the add the neighbor (parent) information in the DAOs do we also add link quality estimation values for each link associated with a parent node? Otherwise the root will have a connectivity graph of the network (DAG) but will have no way to figure out which path is cost-efficient to select (the root can come up with many combinations of paths to select from)?

Thanks.

-John

On Mar 28, 2010, at 2:20 PM, Richard Kelsey wrote:

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

------
JeongGil Ko (John)
Ph.D. Student
Department of Computer Science
Johns Hopkins University
http://www.cs.jhu.edu/~jgko

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Mon, 29 Mar 2010 07:44:34 +0200

Hi John:

Obviously, having multiple parents enables the root to compute multiple
paths down to the node. So your proposal is tempting. But beware, this
is a slippery slope towards centralized Link State computation and away
from the RPL core design, and we can't be designing 2 protocols, by
charter.

The RPL design is that the choice of the best parents belongs to the OF
in the node, not the root. Richard's proposal centralizes in the root
the forwarding decision along the DAG that happens hop by hop with
stateful DAOs, but the routing  states are built in the exact same
fashion whether it is stateful or stateless, by having each node select
a set of preferred DAO parents. Note that we do not specify how a node
selects the next hop between multiple DAO children in the stateful mode.
In the same fashion, we do not specify how the root makes the multi hop
decision.

My suggestion to address your problem would be that the OF in the node
provides more info on how it orders the parents, maybe by setting a
preference level (like 0-3) for each parent in the source route DAO. The
root retains the possibility to build multiple non-overlapping path, do
load balancing, signal to L2 when L2 paths/circuits need to be enabled,
etc... We have not made the step towards a centralized routing model. 

Cheers,

Pascal

> -----Original Message-----
> From: [email-masked] [mailto:[email-masked]] On Behalf
Of
> JeongGil Ko (John)
> Sent: Sunday, March 28, 2010 11:42 PM
> To: Richard Kelsey
> Cc: [email-masked]
> Subject: Re: [Roll] proposal for DAOs in non-caching DODAGs
> 
> Richard,
> 
> I agree that if we start adding downwards routes then the root will
have
> many sub-route (or sub-path) information that it already has. If we
decide
> the add the neighbor (parent) information in the DAOs do we also add
link
> quality estimation values for each link associated with a parent node?
> Otherwise the root will have a connectivity graph of the network (DAG)
but
> will have no way to figure out which path is cost-efficient to select
(the root
> can come up with many combinations of paths to select from)?
> 
> Thanks.
> 
> -John
> 
> > Pascal and I had a discussion on how to simplify DAOs if the group
> > confirms the decision to not explicitly support DAGs with mixed
> > caching and non-caching routers.  The obvious simplification is that
> > the DIO 'S' flag is either on or off throughout a DODAG, eliminating
> > the need to do anything when it changes.
> >
> > More interestingly, the reverse route stack is no longer needed.  It
> > is not used if all nodes cache DAOs.  If only the root does so,
> > including intermediate hops when forwarding DAOs only duplicates
> > information that the root will receive from others.
> >
> > Our proposal is to replace the reverse route stack with a set of
> > parents that is forwarded up the DAG to the root.
> > The DAO format stays the same, except that the reverse route stack
is
> > now a set of parents and is not changed when forwarded.
> >
> > The root can then reconstruct the DAG and compute downwards routes
as
> > needed.  This is not as big a change as it may
> > seem: in the current draft the root may have to compute the paths to
> > nodes whose S bit is not set.  Path computation is simpler than for
a
> > full link-state protocol, as the DIOs have preselected the better
> > up/down links in forming the DAG and other links are not reported.
> >
> > The advantages of using a parent set rather than a reverse route
stack
> > are:

---

From: "JeongGil Ko (John)" <[email-masked]>
Date: Sun, 28 Mar 2010 23:03:32 -0700

Hi Pascal,

I see your point. One question, that confuses me is how the set of 'preferred DAO parents' are determined. Is this set different from the preferred parent set in DIOs? I guess another way of asking is to ask is how the DAORank is defined and computed (this question was asked previously but I didn't really get a clear answer). Will each node that initiates a DAO for a specific prefix be DAORank = 1 and the rank computation continue just like the DIO process? In this case is it true that each node may need to maintain different DAORank values for many different prefixes?

Thanks!

-John

------
JeongGil Ko (John)
Ph.D. Student

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Mon, 29 Mar 2010 08:33:27 +0200

Hi John:

I think I see what you're saying.

If the metrics are asymmetrical, then it might occur that the DAO
parents set is not the exact same as DIO parent set. A node would prefer
a DAO parent for which the metrics from the root to the node are
optimal. So theoretically following the preferred parent path provides
the best metrics without using the DAO rank. 

The current spec enables the OF in a node to compute a DAO Rank based on
the metrics option pretty much like a DIO Rank would be computed using a
DAO DAG Metric Container. This was introduced at some point along the
path and provides an additional capability to rate non preferred paths.
I figure that you're willing to emulate that in the source route DAO

My take is that we have already added too much complexity even though we
made it optional. I'd rather remove the DAO DAG Metric Container. But in
any fashion I have to agree with your desire to make things consistent.
Then again, slippery slope towards link state...

Pascal

> From: JeongGil (John) Ko [mailto:[email-masked]] On Behalf Of
> JeongGil Ko (John)
> Sent: Monday, March 29, 2010 8:04 AM
> To: Pascal Thubert (pthubert)
> Cc: Richard Kelsey; [email-masked]
> I see your point. One question, that confuses me is how the set of
'preferred
> DAO parents' are determined. Is this set different from the preferred
parent
> set in DIOs? I guess another way of asking is to ask is how the
DAORank is
> defined and computed (this question was asked previously but I didn't
really
> get a clear answer). Will each node that initiates a DAO for a
specific prefix be
> DAORank = 1 and the rank computation continue just like the DIO
process? In
> this case is it true that each node may need to maintain different
DAORank
> values for many different prefixes?
> 
> Thanks!
> 
> -John
> 
> > Obviously, having multiple parents enables the root to compute
> > multiple paths down to the node. So your proposal is tempting. But
> > beware, this is a slippery slope towards centralized Link State
> > computation and away from the RPL core design, and we can't be
> > designing 2 protocols, by charter.
> >
> > The RPL design is that the choice of the best parents belongs to the
> > OF in the node, not the root. Richard's proposal centralizes in the
> > root the forwarding decision along the DAG that happens hop by hop
> > with stateful DAOs, but the routing  states are built in the exact
> > same fashion whether it is stateful or stateless, by having each
node
> > select a set of preferred DAO parents. Note that we do not specify
how
> > a node selects the next hop between multiple DAO children in the
stateful
> mode.
> > In the same fashion, we do not specify how the root makes the multi
> > hop decision.
> >
> > preference level (like 0-3) for each parent in the source route DAO.
> > The root retains the possibility to build multiple non-overlapping
> > path, do load balancing, signal to L2 when L2 paths/circuits need to
> > be enabled, etc... We have not made the step towards a centralized
> routing model.
> >
> > Cheers,
> >
> > Pascal
> >
> >

---

From: "JeongGil Ko (John)" <[email-masked]>
Date: Sun, 28 Mar 2010 23:53:38 -0700

Pascal,

> the best metrics without using the DAO rank. 

Exactly. We will need a way to find what the preferred DAO parent set is though. Since we have agreed that the set can be different from the DODAG preferred parent set, how can we do this without using DAO rank values? (Read below and you will find out that I am not a big fan of this DAO rank either :) Just that I don't have a smart answer yet.)

> Then again, slippery slope towards link state...

I was asking about the DAO rank process just to make things clear before I go and implement the stuff (after all this is what the specs want me to use at least until now). I agree that computing separate rank values for DAOs are a pain and can easily take up a lot of resources as the number of supported prefixes increase. So I must say that I have little desire to make things consistent but rather have the desire to make things simpler and working :)

Thanks.

-John

------
JeongGil Ko (John)
Ph.D. Student

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Mon, 29 Mar 2010 12:24:59 +0200

Hi John:

The DAO metrics enable an ancestor  to assess a path that was mostly
already assessed by the child that selected its parents, so it has
limited value, and could be already very simplified.
When adapt the DAO metric to the source route, yes, it appears that all
one hop link metrics would be sent to the root so that it explores all
the possible paths along the dag and computes the best(s). 
But this might become very complex/costly in terms of CPU in the root,
for something that, again, was mostly already evaluated by the
destination node that picked and ordered its DAO parents.

So my take for making things simple is not to add DAO metrics container
per parent in the source route DAO, but rather to challenge the use of
the DAO metrics even in non-source route case. 

Apart from this, would you support Richard's proposal?

Pascal

> Sent: Monday, March 29, 2010 8:54 AM
> > parents set is not the exact same as DIO parent set. A node would
> > prefer a DAO parent for which the metrics from the root to the node
> > are optimal. So theoretically following the preferred parent path
> > provides the best metrics without using the DAO rank.
> >
> 
> Exactly. We will need a way to find what the preferred DAO parent set
is
> though. Since we have agreed that the set can be different from the
DODAG
> preferred parent set, how can we do this without using DAO rank
values?
> (Read below and you will find out that I am not a big fan of this DAO
rank
> either :) Just that I don't have a smart answer yet.)
> 
> > The current spec enables the OF in a node to compute a DAO Rank
based
> > on the metrics option pretty much like a DIO Rank would be computed
> > using a DAO DAG Metric Container. This was introduced at some point
> > along the path and provides an additional capability to rate non
preferred
> paths.
> > My take is that we have already added too much complexity even
though
> > we made it optional. I'd rather remove the DAO DAG Metric Container.
> > But in any fashion I have to agree with your desire to make things
> consistent.
> I was asking about the DAO rank process just to make things clear
before I go
> and implement the stuff (after all this is what the specs want me to
use at
> least until now). I agree that computing separate rank values for DAOs
are a
> pain and can easily take up a lot of resources as the number of
supported
> prefixes increase. So I must say that I have little desire to make
things
> consistent but rather have the desire to make things simpler and
working :)
> >>>>> Pascal and I had a discussion on how to simplify DAOs if the
group
stack
> routes
paths
> > to
> >>>>> - downward path diversity while only sending DAOs  to the
> >>>>> preferred parent

---

From: "Anders Brandt" <[email-masked]>
Date: Mon, 29 Mar 2010 13:33:13 +0200

> needed.  It is not used if all nodes cache DAOs.

I think some very important details are missing here:

Home and building requirements call for
* P2P support - in particular
  * Expedited discovery of destination nodes for turning on lights
  * Near optimal (but not perfect) routing latency for saving battery

Home requirements in particular call for
* Support for low-cost nodes in the consumer space

It is completely unrealistic for low-cost nodes to hold routing
entries for all potential destinations downstream. Sorry.

It is completely unrealistic for low-cost nodes to be in several DAGs.
Sorry.

To get a decent P2P route across branches, a DAG mechanism would have
to do a lot of coordination. Let's face it: DAGs are good for P2MP and
MP2P as long as there are only a few Ps.
To get across branches would require a lot of neighbor monitoring,
metric analysis, etc.
Neighbor monitoring requires a lot of memory which low-cost nodes do not
have.
Communicating neighbor maps to other neighbors - or to the root - costs
bandwidth and takes time that we may not have.

I would prefer if we started to see the nodes as a mesh and used them as
such.
Expedited discovery messages with limited scope and Trickle scheduling
is the
way forward.
Also start considering the notion of trading node cost against route
quality.
A low-cost node should be able to find a P2P route which works
_good_enough_ within
only a short period of time and do this with almost no RAM involved.

We started some very interesting discussions in Anaheim.
I really look forward to a proposal that claims to do all of the above.

Please do not start finetuning DIOs, DAOs without considering P2P
support as described above.
My guess is that you may indeed end up needing route stacks in some more
messages.

While we cannot see the need, neither know how to make it work, mixed
mode may prove needed and
powerful in the future.
I therefore think that it is not so bad that we planned for one frame
format in RPL until now.
For the same reason I think that we should stick with the same frame
format even when running
RPL in single-mode, be that storing or non-storing.

- Anders

> From: [email-masked] [mailto:[email-masked]] On 
> Behalf Of Richard Kelsey
> Sent: Sunday, March 28, 2010 23:21
> To: [email-masked]
> Subject: [Roll] proposal for DAOs in non-caching DODAGs
> 
> needed.  It is not used if all nodes cache DAOs.  If only the 
> root does so, including intermediate hops when forwarding 
> DAOs only duplicates information that the root will receive 
> from others.
> 
> Our proposal is to replace the reverse route stack with a set 
> of parents that is forwarded up the DAG to the root.
> stack is now a set of parents and is not changed when forwarded.
> 
> simpler than for a full link-state protocol, as the DIOs have 
> preselected the better up/down links in forming the DAG and 
> other links are not reported.
>

---

From: Richard Kelsey <[email-masked]>
Date: Mon, 29 Mar 2010 08:32:37 -0400

> Date: Mon, 29 Mar 2010 13:33:13 +0200
> From: "Anders Brandt" <[email-masked]>
> 

I completely agree.  What I was proposing was a relatively
minor change to the DAO mechanism in order to make DAOs
simpler, and also more efficient in networks of low-cost,
non-DAO-storing nodes.

The proposal is not intended to address P2P routing or
expedited discovery or indeed any other requirement not met
by the current DAO mechanism.  I did not mention P2P routing
in my posting.  While P2P routing is a very important issue
for ROLL, it is not the only issue.

                              -Richard Kelsey

---

From: "Anders Brandt" <[email-masked]>
Date: Mon, 29 Mar 2010 14:48:14 +0200

Hi Richard

I'm am sorry. I did not mean to hijack your threat.

Just tried to suggest that this simplification may
prevent us from adding P2P support.

- Anders

> From: Richard Kelsey [mailto:[email-masked]] 
> Sent: Monday, March 29, 2010 14:33
> To: Anders Brandt
> Cc: [email-masked]

---

From: [email-masked]
Date: Mon, 29 Mar 2010 09:46:08 -0500

I completely agree with Anders.  We
need P2P and we need it without undo routing overhead.  Please keep
in mind that these devices are not routers; rather they are building (or
home) controllers that happen to also route as a sidelight.  Most
of their memory and processor resource is used up controlling the building,
with a bit left over to route packets.

Jerry

From:

"Anders Brandt" <[email-masked]>

To:

"Richard Kelsey" <[email-masked]>,
<[email-masked]>

Date:

03/29/2010 06:33 AM

Subject:

Re: [Roll] proposal for DAOs in non-caching
DODAGs

Sorry.

metric analysis, etc.

have.

such.

is the

way forward.

quality.

_good_enough_ within

messages.

powerful in the future.

format in RPL until now.

format even when running

- Anders

> needed.  It is not used if all nodes cache DAOs.  If only
the

-Richard Kelsey

Roll mailing list

[email-masked]

---

From: Michael Richardson <[email-masked]>
Date: Mon, 29 Mar 2010 13:41:45 -0400

>>>>> "Anders" == Anders Brandt <[email-masked]> writes:

    Anders> I think some very important details are missing here:

    Anders> Home and building requirements call for

I agree that the protocol as it is misses this.
But, I do not understand how the proposal changes the situation?

    Anders> I would prefer if we started to see the nodes as a mesh and
    Anders> used them as such.
    Anders> Expedited discovery messages with limited scope and Trickle
    Anders> scheduling is the way forward.

I think you are saying that RPL (whether all-storing, non-storing, or
mixed-storing) does not solve your requirements.

- -- 
]       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: "Roger Alexander" <[email-masked]>
Date: Mon, 29 Mar 2010 17:31:11 -0400

Hi Pascal, John,

> From: [email-masked] [mailto:[email-masked]] On Behalf Of
> Pascal Thubert (pthubert)
> Sent: Monday, March 29, 2010 2:33 AM
> To: JeongGil Ko (John)
> Cc: [email-masked]
> prefer

I agree and I think this is an important point that does not seem
consistently emphasized in the current draft. A central principle in the DAG
connectivity is that a node chooses its DAO Parents and by so doing dictates
the downward routing. Whether a DAG Metric is added to address link
asymmetry, the key is that since nodes choose their DAO Parents and not
vice-versa, downward routing is dictated by the nodes' choice of Parents.

With storing nodes performing hop-by-hop routing there is no need to
maintain node DAO Rank to derive downward routes. In the DAO message
(Section 6.1, see Figure 11), DAO Rank is included as a communicated
information element. Similarly in the DAO Routing Table Entry (Section
6.2.4.1), DAO Rank is maintained. For storing nodes, this information is not
needed other than for local confirmation and validation of the DAO
Parent-Child relationship during a DAO exchange (where rank may have changed
since last broadcast DIO). Thus for storing and non-storing modes alike it
appears the DAO rank information is not necessary for downward routing. 

> Behalf

---

From: "Roger Alexander" <[email-masked]>
Date: Mon, 29 Mar 2010 17:34:40 -0400

Hi Richard, 

As indicated previously, I would support this focus on the storing-only and
non-storing DODAGs models within the RPL effort. The benefits of your
proposal for non-caching nodes further makes the case for the gains from a
focus on the specific modes. 

Also, in the context of a network with storing-only nodes there are also a
number of optimizations that can be introduced in the DAO mechanism,
particularly where acknowledged exchanges occur between nodes and their DAO
Parents. A separate proposal for storing nodes only will be put forward but
at this point I would like to endorse your current proposal.

Roger

> Richard Kelsey
> Sent: Sunday, March 28, 2010 5:21 PM
> To: [email-masked]

---

From: "Roger Alexander" <[email-masked]>
Date: Mon, 29 Mar 2010 17:41:22 -0400

Hi Anders,

> Anders Brandt
> Sent: Monday, March 29, 2010 7:33 AM
> To: Richard Kelsey; [email-masked]

I would agree here. The option for mixed mode should fit within the proposed
structure and formats for storing or non-storing only modes.

---

From: "JeongGil Ko (John)" <[email-masked]>
Date: Mon, 29 Mar 2010 14:48:15 -0700

Hey Roger,

> appears the DAO rank information is not necessary for downward routing. 

Maybe a stupid question but I keep making this point without getting an answer. I agree that if we have a DAO parent set and if this is reported to the root then the need for DAO ranks go away. However, how would a node know its DAO parents without using DAO ranks? I am (once again) not in favor of DAOs but I just want to know how we can achieve this. 

Thanks.

-John

------
JeongGil Ko (John)
Ph.D. Student

---

From: "Roger Alexander" <[email-masked]>
Date: Mon, 29 Mar 2010 17:58:44 -0400

Hi John,

> Sent: Monday, March 29, 2010 5:48 PM
> To: Roger Alexander
> Cc: 'Pascal Thubert (pthubert)'; [email-masked]
> Maybe a stupid question but I keep making this point without getting an
> answer. I agree that if we have a DAO parent set and if this is
> reported to the root then the need for DAO ranks go away. However, how
> would a node know its DAO parents without using DAO ranks? I am (once
> again) not in favor of DAOs but I just want to know how we can achieve
> this.
> 

The selection of DAO Parents is based on the Rank that the candidate nodes
advertise in their DIO. As for sending the DAO Parent set to the root, that
is only applicable for non-storing nodes. For storing nodes the DAO(s) is
sent to each of the set of DAO Parents. 

> >> on
> >> the metrics option pretty much like a DIO Rank would be computed
> using
> >> a
> >> we
> >> made it optional. I'd rather remove the DAO DAG Metric Container.
> But
> >> in

---

From: "JeongGil Ko (John)" <[email-masked]>
Date: Mon, 29 Mar 2010 15:04:08 -0700

Roger,

> sent to each of the set of DAO Parents. 

Better understood. Then the selection of the DODAG preferred parent set and DAO parent set MAY be identical. Correct? Since both decisions are made using the DODAG rank values. Now it makes more sense :) I understand that all this is unneeded when storing mode is used in the network. 

Thanks for the clarification!

-John

------
JeongGil Ko (John)
Ph.D. Student

---

From: "Roger Alexander" <[email-masked]>
Date: Mon, 29 Mar 2010 18:31:32 -0400

Hi John,

> Sent: Monday, March 29, 2010 6:04 PM
> To: Roger Alexander
> Cc: [email-masked]
> Better understood. Then the selection of the DODAG preferred parent set
> and DAO parent set MAY be identical. Correct? Since both decisions are
> made using the DODAG rank values. Now it makes more sense :) I
> understand that all this is unneeded when storing mode is used in the
> network.

The node will use the received Rank plus the local link cost to determine
Parents. The sets MAY indeed be identical but there is no requirement that
they be identical as a node can always have more Preferred Parents than DAO
Parents. The node is required to advertise destination addresses to DAO
Parents but can always forward traffic to any Preferred Parent at no control
cost. Furthermore, with link asymmetry as discussed earlier the Preferred
and DAO Parent sets may even be non-overlapping. By choosing the DAO Parents
the node is dictating its desired downward routing alternatives (no current
mechanism for priority but that can be addressed) while remaining free to
choose different parents for upward routing.

For storing and non-storing alike (based on Richard's proposal), the system
can operate without a rank in the DAO, or the need to maintain rank as part
of the routing table entry.
 
> >>>>>> My suggestion to address your problem would be that the OF in
> the
> >>>> node
> >>>>>> provides more info on how it orders the parents, maybe by
> setting
> >> a
> >>>>>> path, do load balancing, signal to L2 when L2 paths/circuits
> need
> >>>> to
> >>>>>>> many sub-route (or sub-path) information that it already has.
> If
> >>>> we
> >>>>>> decide
> >>>>>>> the add the neighbor (parent) information in the DAOs do we
> also
> >>>> add
> >>>>>> link
> >>>>>>> quality estimation values for each link associated with a
> parent
> >>>> node?
> >>>>>>> Otherwise the root will have a connectivity graph of the
> network
> >>>>>>> (DAG)
> >>>>>> but
> >>>>>>>> caching and non-caching routers.  The obvious simplification
> is
> >>>> that
> needed.
> >>>> It
> of
> >>>>>>>> nodes whose S bit is not set.  Path computation is simpler
> than
> >>>> for
> >>>>>> a
> route

---

From: "JeongGil Ko (John)" <[email-masked]>
Date: Mon, 29 Mar 2010 15:37:04 -0700

Roger, 

> choose different parents for upward routing.

Yup. Point taken.

> of the routing table entry.

Indeed having DAO ranks separately can turn in to a nightmare :)

Thanks!

-John

------
JeongGil Ko (John)
Ph.D. Student

---

From: Philip Levis <[email-masked]>
Date: Tue, 30 Mar 2010 10:04:08 -0700

> Indeed having DAO ranks separately can turn in to a nightmare :)

What if the metric in the two directions is drastically different? One example would be latency with low-power MAC layers.

Phil

---

From: "JeongGil Ko (John)" <[email-masked]>
Date: Tue, 30 Mar 2010 10:28:14 -0700

> What if the metric in the two directions is drastically different? One example would be latency with low-power MAC layers.

This is the reason I was initially asking about metrics added for each DAO parent that a node reports. I am guessing that this proposal does not deal with such cases yet. It can assure 'a' routing path to a specific prefix but not always a 'good' one. Of course good is defined as whatever the system designer intends ( e.g., latency).

John

---

From: "Roger Alexander" <[email-masked]>
Date: Tue, 30 Mar 2010 18:38:28 -0400

Hi Phil, John,

> From: Philip Levis [mailto:[email-masked]]
> Sent: Tuesday, March 30, 2010 1:04 PM
> To: JeongGil Ko (John)
> Cc: Roger Alexander; [email-masked]
> >>>>> Maybe a stupid question but I keep making this point without
> getting
> >>> an
> >>>>> reported to the root then the need for DAO ranks go away.
> However,
> >>> how
> >>>> The selection of DAO Parents is based on the Rank that the
> candidate
> >>> nodes
> What if the metric in the two directions is drastically different? One
> example would be latency with low-power MAC layers.
>
 
I should be a bit more precise... the Rank is used in the selection of the
parents but the aggregated metric advertised by the Parents plus that of the
local link is what determines the total aggregated path cost. With the
ability of the DIO to carry a Metric Container for either direction (this
may need further specification in the current draft) then even if the
metrics are drastically different a node can still determine aggregate
upward and downward path costs and make a choice of Preferred and DAO
Parents.

Note: With multiple parents the aggregated metric advertised by a node in
its DIO, for either direction, may reflect some average across parents. I do
not believe this is currently defined. 
 
> Phil=

---

From: Jonathan Hui <[email-masked]>
Date: Tue, 30 Mar 2010 19:08:42 -0700

Hi Richard,

I like the proposal in general, though it does need to be fleshed out  
a bit more.  Specifically, this works well in the non-storing case if  
all nodes source DAOs to the root so that the root can properly  
construct paths back to any individual node that is sending DAOs.  But  
is there any desire to allow some nodes not to source DAOs if they  
don't need to?  If so, we should specify that a node MUST source DAOs  
as long as they are forwarding DAOs for descendants.

Separately, it might be nice to include a record-route mechanism (not  
the same as reverse route stack DAOs) so that nodes that only want to  
quickly establish routes can do so without having to possibly wait for  
all ancestors to source their own DAOs as well.  I've found that  
record-route works really well in short request-response transactions,  
especially in cases where you don't want to continuously maintain  
downward routing state.

--
Jonathan Hui

---

From: Jonathan Hui <[email-masked]>
Date: Tue, 30 Mar 2010 19:18:24 -0700

> not believe this is currently defined.

I agree with Roger.  Accounting for asymmetric link properties is best  
done by representing the path cost of each direction separately within  
the DIO and not by including some path cost in the DAO.  Like building  
optimal paths to the root, building optimal paths from the root needs  
to originate from the root itself so that nodes can make more informed  
decisions when picking DAO parents.  Without any cost information for  
paths away from the root, a node is blind in choosing its DAO  
parents.  Utilizing the cost towards the root isn't useful since the  
reverse cost may have no relation to it.

What I like about keeping all path cost information in the DIO is that  
it allows a choice in whether you utilize separate path cost values  
for the forward and reverse path or the same path cost value for both  
directions.  The former case allows paths to optimize for asymmetric  
link properties but comes at the price of maintaining and communicate  
more state.  The latter is useful if you want to reduce the cost of  
maintaining separate cost metrics at the price of selecting the same  
route for both directions.

--
Jonathan Hui

---

From: "JeongGil Ko (John)" <[email-masked]>
Date: Tue, 30 Mar 2010 20:26:40 -0700

On Mar 30, 2010, at 7:18 PM, Jonathan Hui wrote:

> I agree with Roger.  Accounting for asymmetric link properties is best done by representing the path cost of each direction separately within the DIO and not by including some path cost in the DAO.  Like building optimal paths to the root, building optimal paths from the root needs to originate from the root itself so that nodes can make more informed decisions when picking DAO parents.  Without any cost information for paths away from the root, a node is blind in choosing its DAO parents.  Utilizing the cost towards the root isn't useful since the reverse cost may have no relation to it.
> 

So let me see if I got it correctly. A DIO will contain the rank information for both downwards and upwards paths. Right? A node can define it's preferred parent list (for both directions) wrt this DIO's rank information? If this is the case then I can see how this can work out. I see packet formats changing for both DIOs and DAOs here :)

-John

> What I like about keeping all path cost information in the DIO is that it allows a choice in whether you utilize separate path cost values for the forward and reverse path or the same path cost value for both directions.  The former case allows paths to optimize for asymmetric link properties but comes at the price of maintaining and communicate more state.  The latter is useful if you want to reduce the cost of maintaining separate cost metrics at the price of selecting the same route for both directions.
> 
> --
> Jonathan Hui
>

---

From: Jonathan Hui <[email-masked]>
Date: Tue, 30 Mar 2010 22:54:01 -0700

On Mar 30, 2010, at 8:26 PM, JeongGil Ko (John) wrote:

>> I agree with Roger.  Accounting for asymmetric link properties is  
>> best done by representing the path cost of each direction  
>> separately within the DIO and not by including some path cost in  
>> the DAO.  Like building optimal paths to the root, building optimal  
>> paths from the root needs to originate from the root itself so that  
>> nodes can make more informed decisions when picking DAO parents.   
>> Without any cost information for paths away from the root, a node  
>> is blind in choosing its DAO parents.  Utilizing the cost towards  
>> the root isn't useful since the reverse cost may have no relation  
>> to it.
>
> So let me see if I got it correctly. A DIO will contain the rank  
> information for both downwards and upwards paths. Right? A node can  
> define it's preferred parent list (for both directions) wrt this  
> DIO's rank information? If this is the case then I can see how this  
> can work out. I see packet formats changing for both DIOs and DAOs  
> here :)

To be more precise, a DIO may contain separate metric information for  
upwards and downwards paths (i.e. directional cost metrics) if having  
the DAG and DAO parents being different sets is desirable.   
Alternatively, a DIO may contain the same metric information for both  
directions paths (i.e. bidirectional cost metrics) if having the DAG  
and DAO parents being the same set is acceptable.

>> What I like about keeping all path cost information in the DIO is  
>> that it allows a choice in whether you utilize separate path cost  
>> values for the forward and reverse path or the same path cost value  
>> for both directions.  The former case allows paths to optimize for  
>> asymmetric link properties but comes at the price of maintaining  
>> and communicate more state.  The latter is useful if you want to  
>> reduce the cost of maintaining separate cost metrics at the price  
>> of selecting the same route for both directions.

--
Jonathan Hui

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Wed, 31 Mar 2010 09:06:26 +0200

Hi John:

The Rank is derived from the decision of the parent set, that includes
both DIO parents that optimize the path towards the root and DAO parents
that optimize the path from the root to this node.

So the Rank mechanism does not depend whether the metrics are all
bidirectional or if some metrics are unidirectional. The Rank mechanism
belongs to the generic RPL and is designed for loop avoidance, whatever
the specific things the OF does with the metrics of the day.

If you really need to have the rank represent finely the metrics cost,
and the metrics are really assymetrical, then probably you want 2 DAGs,
one for which the RANK increment is mostly derived from the up metrics
and one for which it is mostly derived from the down metrics.

Mukul's point stands. Sometimes, the Rank increment for the parent-child
link depends on metrics that are available at the parent after
communication from the child, so we might have a chicken and an egg
problem in the parent selection. I think we need to refine our text on
the link evaluation with candidate neighbors that enables a neighbor to
become a candidate parent in the first place.  

Pascal

From: [email-masked] [mailto:[email-masked]] On Behalf Of
JeongGil Ko (John)
Sent: Wednesday, March 31, 2010 5:27 AM
To: Jonathan Hui
Cc: [email-masked]
Subject: Re: [Roll] proposal for DAOs in non-caching DODAGs

I should be a bit more precise... the Rank is used in the selection of
the

	parents but the aggregated metric advertised by the Parents plus
that of the

	local link is what determines the total aggregated path cost.
With the

	ability of the DIO to carry a Metric Container for either
direction (this

	may need further specification in the current draft) then even
if the

	metrics are drastically different a node can still determine
aggregate

	upward and downward path costs and make a choice of Preferred
and DAO

	Parents.

	Note: With multiple parents the aggregated metric advertised by
a node in

	its DIO, for either direction, may reflect some average across
parents. I do

I agree with Roger.  Accounting for asymmetric link properties is best
done by representing the path cost of each direction separately within
the DIO and not by including some path cost in the DAO.  Like building
optimal paths to the root, building optimal paths from the root needs to
originate from the root itself so that nodes can make more informed
decisions when picking DAO parents.  Without any cost information for
paths away from the root, a node is blind in choosing its DAO parents.
Utilizing the cost towards the root isn't useful since the reverse cost
may have no relation to it.

So let me see if I got it correctly. A DIO will contain the rank
information for both downwards and upwards paths. Right? A node can
define it's preferred parent list (for both directions) wrt this DIO's
rank information? If this is the case then I can see how this can work
out. I see packet formats changing for both DIOs and DAOs here :)

-John

What I like about keeping all path cost information in the DIO is that
it allows a choice in whether you utilize separate path cost values for
the forward and reverse path or the same path cost value for both
directions.  The former case allows paths to optimize for asymmetric
link properties but comes at the price of maintaining and communicate
more state.  The latter is useful if you want to reduce the cost of
maintaining separate cost metrics at the price of selecting the same
route for both directions.

--
Jonathan Hui

---

From: Philip Levis <[email-masked]>
Date: Wed, 31 Mar 2010 00:13:06 -0700

On Mar 31, 2010, at 12:06 AM, Pascal Thubert (pthubert) wrote:

> Hi John:
>  
> The Rank is derived from the decision of the parent set, that includes both DIO parents that optimize the path towards the root and DAO parents that optimize the path from the root to this node.
>  
> So the Rank mechanism does not depend whether the metrics are all bidirectional or if some metrics are unidirectional. The Rank mechanism belongs to the generic RPL and is designed for loop avoidance, whatever the specific things the OF does with the metrics of the day.

I thought we'd gone over this: this can't be true. The rules in RPL in Rank adjustment means that Rank generally comes first in parent set selection. This is part of why we agreed to increase Rank to 16 bits, in order to allow it to better represent metrics as necessary.

>  
> If you really need to have the rank represent finely the metrics cost, and the metrics are really assymetrical, then probably you want 2 DAGs, one for which the RANK increment is mostly derived from the up metrics and one for which it is mostly derived from the down metrics.

I totally disagree -- this seems completely backwards. You're suggesting that my TCP packets from A->B traverse one DAG while B->A traverse another?

>  
> Mukul’s point stands. Sometimes, the Rank increment for the parent-child link depends on metrics that are available at the parent after communication from the child, so we might have a chicken and an egg problem in the parent selection. I think we need to refine our text on the link evaluation with candidate neighbors that enables a neighbor to become a candidate parent in the first place.  

The child gets to pick the parent. Note that link metrics can persist across DODAG iterations. I'm not sure I understand the problem?

Phil

---

From: "JeongGil Ko (John)" <[email-masked]>
Date: Wed, 31 Mar 2010 00:24:15 -0700

Jonathan, I can see how we can play with the DIOs having both upwards and downwards rank values (or just the upwards in some cases). Thanks for the clarification!

Pascal, this email confuses me. I can understand up to Jonathan and Robert's emails and see how that proposal would work but with this email I am suddenly confused. Shouldn't rank be a representation of the metrics that I am using (e.g., ETX in my implementation). Why does the argument on rank not representing metric costs suddenly come up? Are you talking about the case where the OFs for computing downwards and upwards routes are different and the DIO metric container can only carry one at a time?

Thanks.

-John

On Mar 31, 2010, at 12:06 AM, Pascal Thubert (pthubert) wrote:

> From: [email-masked] [mailto:[email-masked]] On Behalf Of JeongGil Ko (John)

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Wed, 31 Mar 2010 09:51:53 +0200

Hi John:

This discussion comes from the fact that your Rank has to be higher than
the Rank of all your parents.

Say you pick a number of parents for going up, and that results in a
Rank that represents more or less a given ETX.

But then, none of those parents is good enough for the way back. What do
you do?

You have to pick a DAO parent that's not one of those parents. And it
might happen that this DAO parent has a Rank that's a lot higher than
the one you would have calculated otherwise.

Guess what, you end up with a Rank that has to grow and stretch away
from the real  ETX upwards.

Or you make 2 DAGs.

Pascal

From: JeongGil (John) Ko [mailto:[email-masked]] On Behalf Of
JeongGil Ko (John)
Sent: Wednesday, March 31, 2010 9:24 AM
To: Pascal Thubert (pthubert)
Cc: Jonathan Hui; [email-masked]
Subject: Re: [Roll] proposal for DAOs in non-caching DODAGs

Jonathan, I can see how we can play with the DIOs having both upwards
and downwards rank values (or just the upwards in some cases). Thanks
for the clarification!

Pascal, this email confuses me. I can understand up to Jonathan and
Robert's emails and see how that proposal would work but with this email
I am suddenly confused. Shouldn't rank be a representation of the
metrics that I am using (e.g., ETX in my implementation). Why does the
argument on rank not representing metric costs suddenly come up? Are you
talking about the case where the OFs for computing downwards and upwards
routes are different and the DIO metric container can only carry one at
a time?

Thanks.

-John

Hi John:

Pascal

 

	Parents.

-John

--
Jonathan Hui

---

From: "JeongGil Ko (John)" <[email-masked]>
Date: Wed, 31 Mar 2010 01:12:01 -0700

Pascal,

On Mar 31, 2010, at 12:51 AM, Pascal Thubert (pthubert) wrote:

> Hi John:
>  
> This discussion comes from the fact that your Rank has to be higher than the Rank of all your parents.
> Say you pick a number of parents for going up, and that results in a Rank that represents more or less a given ETX.
> But then, none of those parents is good enough for the way back. What do you do?

Honestly, I don't think I understand what scenario you are talking about here. a node will select DAG parents that have lower DIO ranks than the node itself. These DIO ranks are computed with the link quality (e.g., etx) of the 'uplink' connection. What do you mean by "none of those parents is good enough for the way back"? Are you trying to imply that in some cases the downwards link quality can be different from the upwards connection? This should be addressable with what I explain below. 

To my understanding in Jonathan and Robert's discussions, there MAY be a separate rank value computed for the downwards links that helps the selection of "downwards path parents". So one rank value is computed using the uplink quality (this would be used to compute the DAG rank and DAG parent set) and the other is computed using the downlink quality (used to compute the downwards rank and downwards path parent set). This downwards path parent set is reported to the root where the DAG topology can be reconstructed and used to form a source route to a specific destination from the root (we have the rank information for the downwards path so the root can construct a loop-free and 'effective' path to the target node). Because this downwards path parent set is computed with downwards link quality, the downwards path parent set can be an effective way to reconstruct the path. Does this not make sense for any reason? Please correct me if I have something wrong.

Thanks.

-John

>  
> You have to pick a DAO parent that’s not one of those parents. And it might happen that this DAO parent has a Rank that’s a lot higher than the one you would have calculated otherwise.
> Guess what, you end up with a Rank that has to grow and stretch away from the real  ETX upwards.
>  
> Or you make 2 DAGs.
>  
> Pascal
>  
> From: JeongGil (John) Ko [mailto:[email-masked]] On Behalf Of JeongGil Ko (John)

------
JeongGil Ko (John)
Ph.D. Student

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Wed, 31 Mar 2010 10:47:22 +0200

Hi John:

The Rank is what makes the DAG a DAG. If you have 2 Ranks, one up one
down, then essentially you have 2 DAGs.

You do not select parents that have a lower Rank than yourself. You
select parents and then you derive a Rank that is higher than theirs. If
your selection includes finding a parent that has a good path down to
you, your Rank must be higher than that of that node as well.

Usually we mostly care about the way out, so you can have the collection
tree state of mind, then probably one of your DIO parents will enable a
good enough path back to you, and your rank will probably ressemble ETX.
All I'm saying is that it does not have to be the case.

Pascal

Sent: Wednesday, March 31, 2010 10:12 AM

Pascal,

Hi John:

Honestly, I don't think I understand what scenario you are talking about
here. a node will select DAG parents that have lower DIO ranks than the
node itself. These DIO ranks are computed with the link quality (e.g.,
etx) of the 'uplink' connection. What do you mean by "none of those
parents is good enough for the way back"? Are you trying to imply that
in some cases the downwards link quality can be different from the
upwards connection? This should be addressable with what I explain
below. 

To my understanding in Jonathan and Robert's discussions, there MAY be a
separate rank value computed for the downwards links that helps the
selection of "downwards path parents". So one rank value is computed
using the uplink quality (this would be used to compute the DAG rank and
DAG parent set) and the other is computed using the downlink quality
(used to compute the downwards rank and downwards path parent set). This
downwards path parent set is reported to the root where the DAG topology
can be reconstructed and used to form a source route to a specific
destination from the root (we have the rank information for the
downwards path so the root can construct a loop-free and 'effective'
path to the target node). Because this downwards path parent set is
computed with downwards link quality, the downwards path parent set can
be an effective way to reconstruct the path. Does this not make sense
for any reason? Please correct me if I have something wrong.

Thanks.

-John

Or you make 2 DAGs.

Pascal

Thanks.

-John

Hi John:

Pascal

 

	Parents.

-John

--
Jonathan Hui

 

------

JeongGil Ko (John)

Ph.D. Student

Johns Hopkins University

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Wed, 31 Mar 2010 10:56:58 +0200

Hi Phil

Pascal

From: Philip Levis [mailto:[email-masked]] 
Sent: Wednesday, March 31, 2010 9:13 AM
To: Pascal Thubert (pthubert)
Cc: JeongGil Ko (John); Jonathan Hui; [email-masked]
Subject: Re: [Roll] proposal for DAOs in non-caching DODAGs

Hi John:

I thought we'd gone over this: this can't be true. The rules in RPL in
Rank adjustment means that Rank generally comes first in parent set
selection. This is part of why we agreed to increase Rank to 16 bits, in
order to allow it to better represent metrics as necessary.

[Pascal] When you can do that, well that's fine. Typically for the
collection tree I'd think. I already elaborated with John on why the
parent selection on the way back might blur this optimistic vision.

I totally disagree -- this seems completely backwards. You're suggesting
that my TCP packets from A->B traverse one DAG while B->A traverse
another?

[Pascal] Welcome to the Internet. Whatever you do, there is a large
probability that the way back is not the way in. Note that whether you
make 1 or 2 DAGs, as soon as you have different metrics for upwards and
downwards you get  a different path.

The child gets to pick the parent. Note that link metrics can persist
across DODAG iterations. I'm not sure I understand the problem?

[Pascal] If the child needs link metrics that the parent gathers upon
messages from the child, then the parent cannot place them in the first
mcast DIO. Some unicast communication must come first to assert the link
quality and exchange the perceptions from both ends. At that point, the
candidate neighbor becomes a candidate parent. In 07 and I think we lost
a lot of that discussion and se do not even define what candidate
parents and neighbors are. I think we need a few words to explain what
we expect from the out-of-scope neighboring mechanism that does a metric
aware NUD of some form.

Pascal

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Wed, 31 Mar 2010 11:56:27 +0200

Hi Jonathan:

100% with you. Richard's broad lines show the way. And we need to refine
a bit to make sure that the root has all the hops in all cases. I see
actually 2 cases:

- In one, all routers are supposed to send their parent set in a DAO. If
the root computes a path and finds one hop missing, then that is an
inconsistency. The new target option in the DIO can be a powerful toot
to fix that inconsistency.

- in the other, routers would advertise their parent on demand, that is
as soon as they know that they are on the path of at least one source
route. I see at least one case where we want to do that, that's when we
apply the P2P proposal that we discussed in another DAO thread to source
route. In that case, it appears that there is a need to trigger that the
parents also send their source route DAO on the way back. It is probably
enough to mandate that a parent that forwards a source route DAO makes
sure that it also has sent its source route DAO, and if not yet, then it
should now.

What do you think?

Pascal

Of
> Jonathan Hui
> Sent: Wednesday, March 31, 2010 4:09 AM
> To: Richard Kelsey
> Cc: [email-masked]
a bit
> more.  Specifically, this works well in the non-storing case if all
nodes source
> DAOs to the root so that the root can properly construct paths back to
any
> individual node that is sending DAOs.  But is there any desire to
allow some
> nodes not to source DAOs if they don't need to?  If so, we should
specify that
> a node MUST source DAOs as long as they are forwarding DAOs for
> descendants.
> 
the
> same as reverse route stack DAOs) so that nodes that only want to
quickly
> establish routes can do so without having to possibly wait for all
ancestors to
> source their own DAOs as well.  I've found that record-route works
really well
> in short request-response transactions, especially in cases where you
don't
> want to continuously maintain downward routing state.
> 
> --
> Jonathan Hui
> 
is
as
a
stack

---

From: Mukul Goyal <[email-masked]>
Date: Wed, 31 Mar 2010 06:19:10 -0500 (CDT)

>>>Mukul’s point stands. Sometimes, the Rank increment for the parent-child link depends on metrics that are available at the parent after communication from the child, so we might have a chicken and…

[Phil]The child gets to pick the parent. Note that link metrics can persist across DODAG iterations. I'm not sure I understand the problem? 

[Pascal] If the child needs link metrics that the parent gathers upon messages from the child, then the parent cannot place them in the first mcast DIO. Some unicast communication must come first to assert the link quality and exchange the perceptions from both ends. At that point, the candidate neighbor becomes a candidate parent. In 07 and I think we lost a lot of that discussion and se do not even define what candidate parents and neighbors are. I think we need a few words to explain what we expect from the out-of-scope neighboring mechanism that does a metric aware NUD of some form. 

I totally agree.

Mukul  

Pascal

---

From: Richard Kelsey <[email-masked]>
Date: Wed, 31 Mar 2010 10:20:28 -0400

> From: Jonathan Hui <[email-masked]>
> Date: Tue, 30 Mar 2010 22:54:01 -0700
> 

This makes no sense to me.  If you want to optimize two
different metrics, in this case the upward and downward
costs, you need two separate DODAGs.  While you can use two
different criteria for DIO parents and DAO parents, both
sets need to be parents as defined by the rank in the DIO.
The DODAG is going to optimize the metric that determines
the rank.  Another metric can be used to tweak the DAO
parent choice, but it only gets to pick between parents
chosen by the rank metric.

If the upward and downward link or node qualities diverge
enough that one metric won't work for both, then you need
two RPL instances.  This is no different from optmizing
latency and bandwidth, for example.

                                      -Richard

---

From: Richard Kelsey <[email-masked]>
Date: Wed, 31 Mar 2010 10:36:04 -0400

> From: Philip Levis <[email-masked]>
> Date: Wed, 31 Mar 2010 00:13:06 -0700
> 

The whole issue here is dealing with links that work better
in one direction than the other.  Given the presence of such
links, it makes perfect sense that packets in one direction
would take a different path than packets in the other.  As
an example, I can easily imagine low-duty-cycle networks
where the nodes' different wake cycles makes links have very
different upward and downwards latency.  Low latency in such
a network would require separate upward and downward routes,
chosen by separate RPL instances.

In the extreme, if there were a smattering of always-on
nodes with links between them having very low latency, you
could get links that were traversed in the same direction
for both the upwards and downwards paths to a particular
node.  This clearly requires separate DAGs.

Given the way RPL works, it can only use links that have at
least some capacity in both directions.  Upwards routes
require that the downward DIO be received and downwards
routes require that the upward DAO be received.

                                  -Richard Kelsey

---

From: Richard Kelsey <[email-masked]>
Date: Wed, 31 Mar 2010 11:13:39 -0400

> Date: Tue, 30 Mar 2010 19:08:42 -0700
> 
> a bit more.

I have not gone over the draft to see exactly what changes
would be required.  If there is enough support for going
forward, I will do so.  This is all assuming that we stop
supporting mixed mode, which will require its own set of
changes to the text.

> Specifically, this works well in the non-storing case if  

The current draft requires that all nodes send DAOs:

   13.  A node that receives a newly incremented DTSN from a DAO Parent
        MUST schedule a DAO transmission.

If we wanted to relax this, then yes, forwarding a DAO would
require that the forwarder also send their own DIO.

> especially in cases where you don't want to continuously maintain  

Yes.  Would record route go in the RPL draft?  I associate
it what source route, which apparently cannot be in the RPL
draft.

                                -Richard Kelsey

---

From: Jonathan Hui <[email-masked]>
Date: Wed, 31 Mar 2010 08:28:28 -0700

> latency and bandwidth, for example.

Are you talking about initiating a DODAG from the root and each  
individual node?  Or initiating two DODAGs from the root?  I hope you  
meant the latter.

I tried to avoid the subject of how many instances or DODAGs in my  
prior mail.  We all agree that sometimes you want to have different  
criteria for selecting DAG parents and DAO parents.  It gets confusing  
because a single DODAG is attempting to select both DAG and DAO  
parents.  A single DODAG (as currently written) is responsible for  
coordinating DIO sequence numbers, triggering DAOs, etc.  Today, a  
DODAG selects both DAG and DAO parents using a set of metrics, an OF,  
and a single Rank value.

I could see a single DODAG approach work by accepting that a DODAG can  
optimizing for DAG and DAO parents separately if requested to do so.   
We could make a two DODAG approach work, but you would need some way  
to tell which DODAG to use for selecting DAG vs. DAO parents.  The  
single DODAG approach seems to make better sense architecturally since  
a single DODAG is tasked with selecting both DAG and DAO parents.   
There would be no duplicated effort in selecting the two sets of  
parents between the two DODAGs.  I could also see a two DODAG solution  
work if we can completely decouple the DAG and DAO parent selection  
process and eliminate any of the effort, which BTW I've been  
advocating for a while.

--
Jonathan Hui

---

From: Richard Kelsey <[email-masked]>
Date: Wed, 31 Mar 2010 12:38:48 -0400

> Date: Wed, 31 Mar 2010 08:28:28 -0700

> > If you want to optimize two

Yes.  It would require that the metric indicate whether the
upward or downward cost should be considered.  This is
required whenever you use an asymmetric link metric,
regardless of how many DODAGs you have.  Just saying
latency, say, is not enough if a link has a different
latency in different directions.  Perhaps this could go in
the DODAG Configuration option.

> criteria for selecting DAG parents and DAO parents.

I guess so.  Doing so is a minor tweak to get local
improvement in upward routes.  Those two criteria have to be
broadly similar for upwards and downwards routes to both
work well in the same DODAG.

> I could see a single DODAG approach work by accepting that
> a DODAG can optimizing for DAG and DAO parents separately
> if requested to do so.

Wouldn't this require two rank values?  How is that
different from having two DODAGs?

> to tell which DODAG to use for selecting DAG vs. DAO parents.

The two DODAG approach works today, modulo the question of
how you specify whether the upwards or downwards link cost
is to be used.  Both optimize their metric and pick parents
with the lowest cost.  The 'upwards' DODAG is not used for
sending downwards, so it would not set the 'A' flag in the
DIOs and no DAOs would be sent.  The only upwards messages
in the 'downwards' DODAG would be the DAOs used to establish
the downwards routes.

I am at a loss as to why upwards vs. downwards costs should
be treated differently than any other two different metrics.

> The single DODAG approach seems to make better sense
> architecturally since a single DODAG is tasked with
> selecting both DAG and DAO parents.

Can you explain the single DODAG approach in more detail?

                                   -Richard Kelsey

---

From: Jonathan Hui <[email-masked]>
Date: Wed, 31 Mar 2010 10:47:22 -0700

Richard,

I think there isn't any real difference in what you and I are trying  
to achieve with one or two instances.  What I had in mind for the  
single instance approach is nearly identical to the two instance  
approach as you indicated.  What was confusing me was the discussion  
starting around selecting non-overlapping sets of DAG and DAO parents.

I think the two instance solution would make sense if we stick with  
the current constraint in rpl-07 that DAO parents must be a subset of  
the DAG parents (i.e. all DAO parents are also DAG parents).  Then all  
we need is a way to specify whether or not an instance is building  
upward routes, downward routes, or both.  The only other minor issue  
is whether we need to think through any cases where coordination  
between the upwards and downwards instances is useful.  For example,  
what needs to happen when packet delivery fails on the downward  
route?  Does the error/backtracking happen on the same instance or a  
different instance?  Do we need to specify such behavior in the core  
spec?  I recognize that we tried to avoid specifying how multiple  
instances work together.  This is one case where I though having a  
single instance was conceptually easier to understand than having two,  
but I can get over that :)

As for indicating which direction of routes to build, it might make  
sense to generalize the A-bit to indicate whether the DODAG is  
building upward, downward, or both.

--
Jonathan Hui

---

From: Jonathan Hui <[email-masked]>
Date: Wed, 31 Mar 2010 10:50:16 -0700

> supporting mixed mode, which will require its own set of

I'm in support.

> require that the forwarder also send their own DIO.

Is there anything in the draft that says a node cannot source its own  
DAOs asynchronously?

> it what source route, which apparently cannot be in the RPL

The difference in my mind is that record-route information can/will  
update RPL routing information.

--
Jonathan Hui

---

From: Philip Levis <[email-masked]>
Date: Wed, 31 Mar 2010 10:58:43 -0700

On Mar 31, 2010, at 1:47 AM, Pascal Thubert (pthubert) wrote:

> Hi John:
>  
> The Rank is what makes the DAG a DAG. If you have 2 Ranks, one up one down, then essentially you have 2 DAGs.
> 

Ah, OK, sorry. I think we have a confusion of terminology? Using *graph theoretic* terminology, yes, there are two DAGs. Using *I-D* terminology, there's only one DAG[1]. I was assuming the latter, you were assuming the former?

I think the confusion is due to the wording of the draft: we should probably clean it up to adjust the "root node" text ("destination node"?) so there isn't an ambiguity between RPL roots and graph roots. This would make bring the text closer to the graph theoretic definition (which we want to be consistent with).

Phil

[1]    DAG:  Directed Acyclic Graph.  A directed graph having the property
         that all edges are oriented in such a way that no cycles exist.
         All edges are contained in paths oriented toward and
         terminating at one or more root nodes.

---

From: Philip Levis <[email-masked]>
Date: Wed, 31 Mar 2010 11:02:20 -0700

> [Pascal] If the child needs link metrics that the parent gathers upon messages from the child, then the parent cannot place them in the first mcast DIO. Some unicast communication must come first t…

I still don't understand. Is the assumption that the only messages used for link metric calculation are RPL messages? How could a node N send unicast RPL messages to a DIO parent P before having an estimate of the link N->P? Such an estimate would have required that N send packets...

This is the basic link metric bootstrapping problem: to measure the link A->B node A must send messages to B (either as unicast or broadcast/multicast). The first transmission has zero knowledge of A->B. Link estimators use a variety of approaches, such as:

 1) A sends broadcasts/multicasts; B sends information on these messages back to A (DeCouto's and Woo's ETX)

 2) A measures B->A and assumes A-B is symmetric; it validates this by using A->B and observing the result (4B link estimator)

 3) A measures B->A and applies a very harsh filter to avoid intermediate links, assuming that an almost-perfect B->A implies A->B is at least very good (many RSSI/chip error approaches)

Your concern seems to be based on assuming 1) is in use? I'd argue we don't want to assume how the link metric estimator works and incorporate that assumption into RPL. It should be the link metric estimator's job to do its job given RPL's traffic, rather than RPL's job to generate traffic to support a link metric estimator. A link metric estimator can always generate its own packets if needed, after all.

Phil

---

From: Richard Kelsey <[email-masked]>
Date: Wed, 31 Mar 2010 17:23:34 -0400

> Date: Wed, 31 Mar 2010 10:47:22 -0700
> 
> approach as you indicated.

Jonathan,

For me there is one big difference, which is that using two
instances does not require any changes to the RPL draft.  We
need to support multiple instances in any case, so using two
instances for separate up/down routes does not add any new
complications.

> I think the two instance solution would make sense if we
> stick with the current constraint in rpl-07 that DAO
> parents must be a subset of the DAG parents (i.e. all DAO
> parents are also DAG parents).

Yes.  I am having trouble seeing how DAOs would work if DAO
parents were not also DAG parents.

> Then all we need is a way to specify whether or not an
> instance is building upward routes, downward routes, or
> both.

I think a better way to put it would be to specify how
asymmetric link metrics are to be combined (downward value
only, upward value only, max of the two, min of the two,
average, ...).  I will ask JP to open a ticket.

> The only other minor issue  
> spec?

Again, I do not see how this is different from other
collections of instances.  What happens when a packet
delivery fails on a low-latency instance?  Does the error
get forwarded on that instance or some other instance?

                              -Richard Kelsey

---

From: Jonathan Hui <[email-masked]>
Date: Wed, 31 Mar 2010 14:47:59 -0700

Richard,

> instances for separate up/down routes does not add any new

Yes, I agree this is desirable.

> average, ...).  I will ask JP to open a ticket.

Metrics are important, yes.  But a node also needs to know whether or  
not to install forwarding table entries for its DAG parents.  If the  
instance is only for downward routes, then one approach is to say a  
node need not install default/destination forwarding entries.  But  
maybe this isn't the best approach (see below).

> get forwarded on that instance or some other instance?

The difference in my mind is whether or not we require all instances  
to maintain upward routes.  Then backtracking within an instance works  
as we have envisioned it so far.  If we allow backtracking to occur  
across instances, then the benefits of backtracking become less  
obvious because you are no longer 'backtracking' in the literal sense  
of the word.  Of course, this assumes we even want backtracking at all  
and I'm not convinced yet...

In any case, it seems that we need a mechanism to identify how  
instances are tied together (minimally what instance to use what  
routes fail).  This is the kind of coordination that I was alluding to.

--
Jonathan Hui

---

From: "Roger Alexander" <[email-masked]>
Date: Wed, 31 Mar 2010 18:52:34 -0400

Hi Phil, Pascal,

From: [email-masked] [mailto:[email-masked]] On Behalf Of
Pascal Thubert (pthubert)
Sent: Wednesday, March 31, 2010 4:57 AM
To: Philip Levis
Cc: [email-masked]
Subject: Re: [Roll] proposal for DAOs in non-caching DODAGs

Hi Phil

Pascal

 

Hi John:

The Rank is derived from the decision of the parent set, that includes both
DIO parents that optimize the path towards the root and DAO parents that
optimize the path from the root to this node.

So the Rank mechanism does not depend whether the metrics are all
bidirectional or if some metrics are unidirectional. The Rank mechanism
belongs to the generic RPL and is designed for loop avoidance, whatever the
specific things the OF does with the metrics of the day.

I thought we'd gone over this: this can't be true. The rules in RPL in Rank
adjustment means that Rank generally comes first in parent set selection.
This is part of why we agreed to increase Rank to 16 bits, in order to allow
it to better represent metrics as necessary.

[Pascal] When you can do that, well that's fine. Typically for the
collection tree I'd think. I already elaborated with John on why the parent
selection on the way back might blur this optimistic vision.

If you really need to have the rank represent finely the metrics cost, and
the metrics are really assymetrical, then probably you want 2 DAGs, one for
which the RANK increment is mostly derived from the up metrics and one for
which it is mostly derived from the down metrics.

I totally disagree -- this seems completely backwards. You're suggesting
that my TCP packets from A->B traverse one DAG while B->A traverse another?

[Pascal] Welcome to the Internet. Whatever you do, there is a large
probability that the way back is not the way in. Note that whether you make
1 or 2 DAGs, as soon as you have different metrics for upwards and downwards
you get  a different path.

Mukul's point stands. Sometimes, the Rank increment for the parent-child
link depends on metrics that are available at the parent after communication
from the child, so we might have a chicken and an egg problem in the parent
selection. I think we need to refine our text on the link evaluation with
candidate neighbors that enables a neighbor to become a candidate parent in
the first place.  

The child gets to pick the parent. Note that link metrics can persist across
DODAG iterations. I'm not sure I understand the problem?

[Pascal] If the child needs link metrics that the parent gathers upon
messages from the child, then the parent cannot place them in the first
mcast DIO. Some unicast communication must come first to assert the link
quality and exchange the perceptions from both ends. At that point, the
candidate neighbor becomes a candidate parent. In 07 and I think we lost a
lot of that discussion and se do not even define what candidate parents and
neighbors are. I think we need a few words to explain what we expect from
the out-of-scope neighboring mechanism that does a metric aware NUD of some
form.

>>[RA] The Parent only needs to convey aggregated metrics, upward (downward)
from itself to the root (from the root to itself). Even if the Child node
needs link statistics that the Parent node gathers, that would be derived
and conveyed through a separate process. 

Pascal

---

From: "Roger Alexander" <[email-masked]>
Date: Wed, 31 Mar 2010 18:57:35 -0400

Hi Jonathan, 

I do think the case of two (or multiple) instances is already supported and
could be used to implement separate upward and downward routing with
different metrics and objective functions...

> Sent: Wednesday, March 31, 2010 5:48 PM
> To: Richard Kelsey
> Cc: [email-masked]

All instances will be required to maintain, though not necessarily use,
upward routes as these are the bases of the DODAG. The 'backtracking' does
not have to be across the instances. Another way to think of the two
instances would be to consider them as two DODAGs formed on the same root
but using different objective functions (OFs); each OF leading to a separate
(logical) bidirectional DODAG. On one DODAG the node chooses to send DAOs to
get downward routing and in the other the node sends no DAOs but uses
preferred Parents for forwarding (the node may need to function as a leaf).
The two instances would be distinguished by the RPLInstanceID which would
require the node to maintain state and support operation in each instance.

---

From: Jonathan Hui <[email-masked]>
Date: Wed, 31 Mar 2010 16:10:28 -0700

Hi Roger,

> different metrics and objective functions...

Yes, I fully understand that.

> require the node to maintain state and support operation in each  

Again, I understand that's how you see it to work.  My question was  
whether a node also installs default routes in the forwarding (*not*  
routing) table for each instance and it seems to be that your answer  
is 'yes'.  Note that if we don't care about 'backtracking', then an  
instance that is primarily used to maintain downward routes does not  
need to maintain default routes since RPL messages occur hop-by-hop.

--
Jonathan Hui

---

From: Roger Alexander <[email-masked]>
Date: Wed, 31 Mar 2010 20:43:04 -0400

Hi Jonathan,

> need to maintain default routes since RPL messages occur hop-by-hop.

We are fully in synch. However, even if forwarding routes are  
maintained in both instaces the state requirement may not be very  
significant being potentially as few as one for the downward instance.

---

From: Jonathan Hui <[email-masked]>
Date: Wed, 31 Mar 2010 19:04:21 -0700

Hi Roger,

On Mar 31, 2010, at 5:43 PM, Roger Alexander wrote:

>> whether a node also installs default routes in the forwarding  
>> (*not* routing) table for each instance and it seems to be that  
>> your answer is 'yes'.  Note that if we don't care about  
>> 'backtracking', then an instance that is primarily used to maintain  
>> downward routes does not need to maintain default routes since RPL  
>> messages occur hop-by-hop.
>

It was more a question of whether you want to allow arbitrary traffic  
to utilize any default route table entries generated for a 'downward  
instance'.  Indicating what kind of forwarding table entries you would  
like to populate (if any) is what I had in mind in indicating what  
routes you would like an instance to maintain (upward, downward, or  
both).

--
Jonathan Hui

---

From: Richard Kelsey <[email-masked]>
Date: Wed, 31 Mar 2010 22:02:23 -0400

> Date: Wed, 31 Mar 2010 14:47:59 -0700
> 
> to maintain upward routes.

We don't currently.  The DIO 'A' flag which enables/disables
upward routes.  Do you think that we should require upward
routes for all instances?  It doesn't seem necessary to me.

> Then backtracking within an instance works  
> of the word.

Crossing between DODAGs when forwarding raises the possibility
of looping.  Care would have to be exercised.

> Of course, this assumes we even want backtracking at all  

Neither am I.

> routes fail).

I fully agree.
                                    -Richard Kelsey

---

From: Richard Kelsey <[email-masked]>
Date: Wed, 31 Mar 2010 22:31:37 -0400

> Date: Wed, 31 Mar 2010 22:02:23 -0400
> From: Richard Kelsey <[email-masked]>
> 

Sorry, I got my upward and downward confused.

All instances have to maintain parent sets, so at least they
have implicit upward routes.  If your question is whether
all instances have to contribute upward routes for use in
forwarding, I would say no.

Backtracking would seem to be a separate issue.  Can a node
return a packet to a parent without having a routing entry
pointing that way?  In any case, perhaps we can decide whether
to use backtracking before worrying about the details of how
it is accomplished.
                                     -Richard Kelsey

---

From: Jonathan Hui <[email-masked]>
Date: Wed, 31 Mar 2010 19:40:50 -0700

Hi Richard,

> Sorry, I got my upward and downward confused.

Thanks for the clarification.

> forwarding, I would say no.

That's exactly the question I was asking.  So I think it would be a  
good idea to also indicate what kind of forwarding table entries an  
instance should contribute.  That would be in addition to what kind of  
metrics the instance should use.

> to use backtracking before worrying about the details of how

Agree.  I think it's fair to say that backtracking creates additional  
complications like the ones I was raising.  An additional one is how  
backtracking works when nodes maintain more than one DAO parent.

--
Jonathan Hui

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Thu, 1 Apr 2010 08:57:04 +0200

Hi Jonathan:

The default route is needed as soon as you do some P2P along the DAG,
because you cannot switch instance on the way. This is somewhat
unrelated to the discussion here.

The question is rather which instance is applied to a packet before the
packet is sent out. 

The application in a RPL node needs to be (abstractly) aware of
instances, and it should tag the packets with the proper instance ID so
that the DAG that is computed to optimize the upstream is used. Even if
multiple DAGs have a default route, we still use the right one.

Pascal

Of
> Jonathan Hui
> Sent: Wednesday, March 31, 2010 11:48 PM
> To: Richard Kelsey
> Cc: [email-masked]
instances
> > does not require any changes to the RPL draft.  We need to support
> > multiple instances in any case, so using two instances for separate
> > up/down routes does not add any new complications.
> 
> >> the DAG parents (i.e. all DAO parents are also DAG parents).
> >
> > Yes.  I am having trouble seeing how DAOs would work if DAO parents
> > were not also DAG parents.
> >
> >> Then all we need is a way to specify whether or not an instance is
> >> building upward routes, downward routes, or both.
> >
> > I think a better way to put it would be to specify how asymmetric
link
> > metrics are to be combined (downward value only, upward value only,
> > max of the two, min of the two, average, ...).  I will ask JP to
open
> > a ticket.
not to
> install forwarding table entries for its DAG parents.  If the instance
is only for
> downward routes, then one approach is to say a node need not install
> default/destination forwarding entries.  But maybe this isn't the best
> approach (see below).
> 
> > Again, I do not see how this is different from other collections of
> > instances.  What happens when a packet delivery fails on a
low-latency
> > instance?  Does the error get forwarded on that instance or some
other
> > instance?
to
> maintain upward routes.  Then backtracking within an instance works as
we
> have envisioned it so far.  If we allow backtracking to occur across
instances,
> then the benefits of backtracking become less obvious because you are
no
> longer 'backtracking' in the literal sense of the word.  Of course,
this assumes
> we even want backtracking at all and I'm not convinced yet...
> 
instances
> are tied together (minimally what instance to use what routes fail).
This is
> the kind of coordination that I was alluding to.
> 
> --
> Jonathan Hui
>