Subject: [Roll] RPL: why not base a DAG on the min hop distance from the root?

From: Mukul Goyal <[email-masked]>
Date: Wed, 1 Jul 2009 17:55:54 -0500 (CDT)

RPL allows a node to have parents with different depths from the root. By choosing deeper neighbors as parents, a node increases its own depth (required to be more than that of any of its parents to avoid loops) and thus makes itself less attractive for selection as a parent.

RPL also allows a node to discard its deeper parents to improve its own depth and thus make itself more attactive for selection as a parent. But this is not mandatory.

The question is what is the inherent benefit of this flexibility? Why is it that such a DAG may lead to better routes than one based strictly on min hop-distance (i.e. where a node would be required to discard parents when it finds less deeper ones)?

Under the RPL approach, the depth of a node is an upper bound on its hop distance from the root. It just tells that a packet forwarded to the node may take anywhere between 1 and the "depth" hops to reach the root (unless the node maintains the "min_hop_distance" from the root as well, in which case a packet forwarded to the node may take any where between "min_hop_distance" and "depth" hops to reach the root). The end result is that a node has very little control over the number of hops a packet, it forwards, takes to reach the root.

It seems to me that forcing the depth to be same as the min hop distance would still allow all the benefits of DAGs (loop avoidance, flexible routes in face of topology changes) while assigning a better meaning to the term "depth".

Thanks
Mukul

---

From: Philip Levis <[email-masked]>
Date: Wed, 1 Jul 2009 16:00:34 -0700

On Jul 1, 2009, at 3:55 PM, Mukul Goyal wrote:

>  Why is it that such a DAG may lead to better routes than one based  
> strictly on min hop-distance (i.e. where a node would be required to  
> discard parents when it finds less deeper ones)?

There is a tremendous amount of research in wireless which has shown  
that min hop-distance is not a good metric for wireless networks.  
DeCouto's paper is probably the best experimental study:

http://pdos.csail.mit.edu/~rtm/papers/etx.pdf

Any proposal which suggests that routing should be in terms of hop- 
count is dead in the water.

Phil

---

From: Mukul Goyal <[email-masked]>
Date: Wed, 1 Jul 2009 18:07:46 -0500 (CDT)

Let me rephrase:

The question is why is it that a DAG where a node can have parents with different depths is inherently better than one where a node can have parents of same depth only (where the depth may or may not be same as the min hop distance from the root)?

Thanks
Mukul

----- Original Message -----
From: "Mukul Goyal" <[email-masked]>
To: "roll" <[email-masked]>
Sent: Wednesday, July 1, 2009 5:55:54 PM GMT -06:00 US/Canada Central
Subject: [Roll] RPL: why not base a DAG on the min hop distance from the root?

Thanks
Mukul

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

---

From: [email-masked]
Date: Wed, 1 Jul 2009 23:16:31 +0000

Hi Mukul,

I think a feature where a device can elect on its own (absent any topological knowledge of the network) to downgrade itself in depth is questionable.

Phil:  Under what circumstances could you see a device making such an election?

Don
Sent via BlackBerry from T-Mobile

-----Original Message-----
From: Mukul Goyal <[email-masked]>

Date: Wed, 1 Jul 2009 18:07:46 
To: roll<[email-masked]>
Subject: Re: [Roll] RPL: why not base a DAG on the min hop distance from the
 root?

Let me rephrase:

Thanks
Mukul

----- Original Message -----
From: "Mukul Goyal" <[email-masked]>
To: "roll" <[email-masked]>
Sent: Wednesday, July 1, 2009 5:55:54 PM GMT -06:00 US/Canada Central
Subject: [Roll] RPL: why not base a DAG on the min hop distance from the root?

Thanks
Mukul

---

From: Omprakash Gnawali <[email-masked]>
Date: Wed, 1 Jul 2009 19:39:27 -0700

> Phil:  Under what circumstances could you see a device making such an election?

When the selected parent is unreachable, the ability to select a new
parent quickly?

- om_p

---

From: Philip Levis <[email-masked]>
Date: Wed, 1 Jul 2009 20:14:21 -0700

On Jul 1, 2009, at 4:07 PM, Mukul Goyal wrote:

> Let me rephrase:
>
> The question is why is it that a DAG where a node can have parents  
> with different depths is inherently better than one where a node  
> can have parents of same depth only (where the depth may or may not  
> be same as the min hop distance from the root)?
>
> Thanks
> Mukul

The reason Om mentioned is a good one. While a node might prefer a  
parent at the same hopcount in order to prevent loops (IIRC the ARC  
stack does this), it should not require one. Given that you are  
routing in terms of a different metric, this constraint leads to  
inefficient routes.

I'd actually flip this around: almost all working LLN mesh protocols  
I know of do not enforce this limitation. Why do you think going  
against this common wisdom is a good idea? It wasn't an arbitrary  
decision.

Phil

---

From: Jonathan Hui <[email-masked]>
Date: Wed, 1 Jul 2009 20:32:10 -0700

> routing in terms of a different metric, this constraint leads to  

Phil put his finger on an important point. We want to select routes  
using metrics that are not necessarily based on hop-count for a  
variety of reasons (e.g. ETX), but hop-count is a way to avoid and  
detect loops while being agnostic to the metric used. This distinction  
highlights a subtle difference between the Arch Rock stack and CTP,  
where the former uses hop-count for data-path loop detection and the  
latter uses the routing cost itself.

With ETX and other metrics, it's not uncommon to have an equal path  
cost through parents that have different hop counts from the root.

--
Jonathan Hui

---

From: Richard Kelsey <[email-masked]>
Date: Thu, 02 Jul 2009 11:50:05 -0400

From: Jonathan Hui <[email-masked]>
   Date: Wed, 1 Jul 2009 20:32:10 -0700

That subtle difference can have a large effect.  The current
DAG discovery strongly prefers a single hop over any
alternative path that is three or more hops in length,
regardless of any routing contraints.  This stems directly
from the use of hop count for loop avoidance.

To see this, consider a network with four nodes LBR, A, B,
and C, where A and B do not share a link and the LBR<->B
link is inferior enough that the LBR<->A<->C<->B route is
significantly better than the one-hop LBR<->B route.

   LBR
   / \
  A   B
   \ /
    C

LBR, as the root, sends out an RA at depth 0, heard by both
A and B.  They in turn send out their RAs at depth 1 and C
picks A as a parent, the cost of the LBR<->B link making B
an bad choice.  C then sends out an RA at depth 2, which is
ignored by A and B because C's depth is greater than theirs.

The upshot is that B's route to LBR almost always uses the
poor-quality LBR<->B link, rather than the preferred route
via C and A.  The 'almost always' is because you might get
lucky and B might not hear the initial RA from the LBR and
hear C's RA first.
                                -Richard Kelsey

---

From: Jonathan Hui <[email-masked]>
Date: Thu, 2 Jul 2009 09:19:25 -0700

Hi Richard,

> lucky and B might not hear the initial RA from the LBR and

I was referring to data-path loop detection. You are referring to  
control-path loop avoidance. With the former, the forwarding node  
attaches what it believes to be the depth of the next hop in each  
datagram sent. The next hop receives the datagram and checks whether  
the depth agrees.

But to address your specific point - with the example you give, it is  
unclear what the overall best situation is. From B's point of view, it  
is better to go through C. But from C's point of view, it may be  
better to have two feasible successors A and B. If it is acceptable  
for B to communicate directly with the LBR, then that might be the  
overall better solution. In the end, I don't think we can feasibly  
optimize each individual node locally while optimizing the entire  
routing graph. What is globally optimal is not even well defined...

--
Jonathan Hui

---

From: Richard Kelsey <[email-masked]>
Date: Thu, 02 Jul 2009 13:27:47 -0400

Jonathan,

   From: Jonathan Hui <[email-masked]>
   Date: Thu, 2 Jul 2009 09:19:25 -0700

   > lucky and B might not hear the initial RA from the LBR and

   I was referring to data-path loop detection.

Yes, sorry, I missed that.

The problem isn't that hop count doesn't pick the best
route, but that it often doesn't even pick a good one.  To
quote from a posting by Philip Levis:

 There is a tremendous amount of research in wireless which
 has shown that min hop-distance is not a good metric for
 wireless networks.

In this and similar situations, RPL lets hop count trump all
other routing constraints.  This seems like a bad idea.

                               -Richard Kelsey

---

From: Jonathan Hui <[email-masked]>
Date: Thu, 2 Jul 2009 10:56:06 -0700

Hi Richard,

> other routing constraints.  This seems like a bad idea.

Yes. I understand the problem and agree with you here - that the loop  
avoidance mechanism is not based on the actual routing metrics used  
(whatever they may be). We actually had a lengthy discussion about  
this within the DT. I'd actually like to see the loop avoidance  
mechanism be based on the routing metrics themselves rather than the  
hop count. This works fine as long as the metric we use have a  
monotonic property such that there is a consistent notion of "deeper"  
in the gradient.

Things get a bit more tricky when dealing with multiple metrics  
simultaneously. With multiple metrics, nothing changes as long as the  
comparator function between two metric vectors is a strictly monotonic  
function. If that strictly monotonic function does not exist (i.e. the  
metrics are completely orthogonal), then things get a bit more  
difficult. One possible solution is that we require one or more of the  
path metrics to be strictly monotonic and the rule becomes: a node  
cannot go "deeper" in any of the monotonic metrics. This seems a bit  
over-constrained, so we were discussing whether we can relax this  
constraint and this is still work in progress.

Do you think we are headed in a fruitful direction? What are your  
thoughts?

--
Jonathan Hui

---

From: Richard Kelsey <[email-masked]>
Date: Thu, 02 Jul 2009 14:47:12 -0400

Jonathan,

   From: Jonathan Hui <[email-masked]>
   Date: Thu, 2 Jul 2009 10:56:06 -0700

Here is a suggestion:

Leave the hop count as is, and add a DAGCost field.  The
DAGCost field is a fixed-point value, say 16 bits of which 8
bits are the fractional part.  The units for the cost field
are hops, so a hop with a cost 0x0001 is equivalent to an
additional 1/256th of a 'best case' hop and 0x0100 is
equivalent to a complete additional 'best case' hop.  The
actual path cost is

    (DAGDepth << 8) + DAGCost

Loop avoidance and parent selection is done using the path
cost.  In an outgoing DIO the DAGDepth MUST be larger than
the maximum parent DAGDepth and the DAGCost MUST be large
enough such that the path cost of the DIO is greater than
the maximum parent path cost.

Increasing the DAGCost is optional.  If no node does so the
result is the same as the current algorithm.  Nodes are free
to include metric containers with additional information.

If a node makes use of multiple metrics the additional costs
for one hop need not be additive.  For example, if a link is
both slow and energy intensive, the link cost could be 
the average of the two, instead of their sum.

What do you think?
                                -Richard Kelsey

---

From: "Don Sturek" <[email-masked]>
Date: Thu, 2 Jul 2009 12:21:43 -0700

Hi Richard,

The proposal below seems reasonable.  Hopefully, these inputs can be
accommodated in the ROLL DT work.  

Overall, I do think the proposal was good absent the issue around
consideration of hops from the DAG root (which I do think some
implementations care about).

Don

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of
Richard Kelsey
Sent: Thursday, July 02, 2009 11:47 AM
To: Jonathan Hui
Cc: [email-masked]
Subject: Re: [Roll] RPL: why not base a DAG on the min hop distance from the
root?

Jonathan,

Here is a suggestion:

What do you think?
                                -Richard Kelsey

---

From: Jonathan Hui <[email-masked]>
Date: Thu, 2 Jul 2009 14:14:46 -0700

Hi Richard,

> the maximum parent path cost.

This is an interesting approach. It forces each node to aggregate  
whatever metrics they use into a single DAGCost metric and relate that  
to the DAGDepth in some way. Does it make sense to add another  
constraint that DAGCost has to be >= the parent's DAGCost? What I'm  
thinking about is the possible loss in information across multiple  
hops. In a completely contrived case, a node could advertise a path  
cost only 1 greater (by incrementing DAGDepth by 1 and decreasing  
DAGCost by 255) - then the meaning of a "hop" and relationship between  
DAGCost and DAGDepth gets lost. Or did you intend it to allow  
reductions in DAGCost so that they can optionally be summarized into  
DAGDepth along the way?

But for now, the way you defined it, it is equivalent to having a  
single 16-bit integer that can be increased arbitrarily at every hop.  
If 0 <= DAGCost < 256, then you must increase by at least 256 - DAGCost.

--
Jonathan Hui

---

From: Mukul Goyal <[email-masked]>
Date: Thu, 2 Jul 2009 17:11:22 -0500 (CDT)

Richard

Could you please explain your suggestion. It seems like you would want the actual routing metrics to be used in loop avoidance and are proposing mapping the routing metrics to a DAGCost variable (in units of hops). The sum of DAGCost and DAGDepth will be used to select parents as well as to avoid loops. 

Is this understanding correct?

Why not do away with DAGDepth totally? It is sort of meaningless any way. Just have DAGCost that is a function of routing metrics and is used for parent selection as well as loop avoidance. All the nodes would have to enforce the same mapping function between the routing metrics and the DAGCost.

Thanks
Mukul
    
----- Original Message -----
From: "Richard Kelsey" <[email-masked]>
To: "Jonathan Hui" <[email-masked]>
Cc: [email-masked]
Sent: Thursday, July 2, 2009 1:47:12 PM GMT -06:00 US/Canada Central
Subject: Re: [Roll] RPL: why not base a DAG on the min hop distance from the root?

Jonathan,

Here is a suggestion:

What do you think?
                                -Richard Kelsey

---

From: Richard Kelsey <[email-masked]>
Date: Thu, 02 Jul 2009 18:43:27 -0400

From: Jonathan Hui <[email-masked]>
   Date: Thu, 2 Jul 2009 14:14:46 -0700

Jonathan,

   This is an interesting approach. It forces each node to aggregate  
   whatever metrics they use into a single DAGCost metric and relate that  
   to the DAGDepth in some way. Does it make sense to add another  
   constraint that DAGCost has to be >= the parent's DAGCost?

With a single parent this would be the way to go.  I am
unsure how to handle multiple parents if there is a large
variance in the split between DAGDepth and DAGCost.  What if
there are two parents, one with a DAGDepth of 1 and a
DAGCost of 3 and the other with a DAGDepth of 3 and a
DAGCost of 1?  The child's DAGDepth has to be 4 and the
DAGCost must be at least 1, but should it be higher?

A related problem raised by the current draft is what should
be done if there are multiple parents with different metric
containers.  How should the metric values from different
parents be combined?

   What I'm thinking about is the possible loss in
   information across multiple hops. In a completely
   contrived case, a node could advertise a path cost only 1
   greater (by incrementing DAGDepth by 1 and decreasing
   DAGCost by 255) - then the meaning of a "hop" and
   relationship between DAGCost and DAGDepth gets lost. Or
   did you intend it to allow reductions in DAGCost so that
   they can optionally be summarized into DAGDepth along the
   way?

My intent was the outgoing DAGCost should be no smaller
than the incoming one.  But can you take the DAGDepth from
one parent and the DAGCost from another?

                                       -Richard Kelsey

---

From: Richard Kelsey <[email-masked]>
Date: Thu, 02 Jul 2009 19:09:41 -0400

Mukul,

   Date: Thu, 2 Jul 2009 17:11:22 -0500 (CDT)
   From: Mukul Goyal <[email-masked]>

   Could you please explain your suggestion. It seems like you would want
   the actual routing metrics to be used in loop avoidance and are
   proposing mapping the routing metrics to a DAGCost variable (in units
   of hops). The sum of DAGCost and DAGDepth will be used to select
   parents as well as to avoid loops.

Yes.

   Why not do away with DAGDepth totally?

I kept it to be conservative.  From this thread it is clear
that DAGDepth is seen to be valuable by some members of the
group.  DAGDepth may have other uses besides DAG formation.

                                  -Richard Kelsey

---

From: Jonathan Hui <[email-masked]>
Date: Thu, 2 Jul 2009 16:27:51 -0700

Hi Richard,

It seems that your proposal is a special case of my original proposal  
to deal with the full vector of metrics in use. In your case, the  
vector has 2 elements (hop count, DAG cost) and both are monotonic.
Some of the issues you identified with advertising DAGdepth and  
DAGcost are also present in mine. Specifically, can a node mix and  
match metric values from different parents? One difference, however,  
is that you no longer have an ill-defined notion of DAGcost since the  
metrics are carried through individually.

This leads me back to thinking about the vector-based approach. The  
nice thing with the vector-based approach is that it's completely  
valid to include or exclude hop count. You also don't have to decide  
how some combination of metric A, B, C relates to hop count.

As for dealing nodes understanding only certain metrics: In one view,  
the set of metrics should be originated by the destination (i.e.  
root). Nodes advertising the cost can either (i) decide to drop the  
metric from the vector or (ii) pass the metric along, possibly  
incrementing by some value. Both are useful in different situations, I  
think. If we went with this approach, it would also be useful to  
define a base set of metrics (hop count should be one).

I still haven't come up with a better solution to the loop-avoidance  
mechanism in the vector-based approach other than the fairly  
constrained one I provided earlier...

--
Jonathan Hui

---

From: Philip Levis <[email-masked]>
Date: Thu, 2 Jul 2009 16:31:48 -0700

> the average of the two, instead of their sum.

Richard,

This seems like a totally reasonable metric to use, but I'd be wary of  
saying it's *the* metric to use. Some implementations are going to  
want to consider hopcount, others won't. It's just another metric.  
Rather than hardwire hopcount based assumptions into the protocol  
design, we should put it on equal footing as other metrics.  
Correspondingly, the protocol should have general, metric-independent  
mechanisms for detecting and avoiding loops.

Jonathan's concerns about integrating metrics into a single cost is  
well-founded: it's fraught with all kinds of problematic edge cases  
which you have to hack around. Advertising the vector is a much safer,  
more flexible, and less likely to run into broken assumptions which  
have to be later worked around.

As a concrete example, one reason why CTP uses a 16-bit encoding of  
ETX was a need for precision to at least tenths of an ETX as well as  
the ability to support > 25 hops (the maximum with 8 bits). Our  
concrete use case for the second requirement was the network deployed  
along the length of the Golden Gate Bridge, which was ~40 hops long.

Phil

---

From: Richard Kelsey <[email-masked]>
Date: Thu, 02 Jul 2009 21:45:27 -0400

Phil,

   From: Philip Levis <[email-masked]>
   Date: Thu, 2 Jul 2009 16:31:48 -0700

   > the maximum parent path cost.

   This seems like a totally reasonable metric to use, but I'd be wary
   of saying it's *the* metric  to use. Some implementations are going
   to  want to  consider  hopcount, others  won't.  It's just  another
   metric.

I am proposing it, or something like it, as the default
metric.  The current draft uses hop count both as the
default metric and to override other metrics in some
cases.  This does not seem like a good idea.  Replacing
hop count with a finer-grained cost avoids the need to
override other metrics.

   Rather than hardwire hopcount based assumptions into the
   protocol design, we should put it on equal footing as
   other metrics.  Correspondingly, the protocol should have
   general, metric-independent mechanisms for detecting and
   avoiding loops.

Are there such mechanisms?  In order to avoid creating a
loop you have to remove or ignore some edges in the graph.
Picking which edges to remove would seem to require a metric
of some kind.

   Jonathan's concerns about integrating metrics into a
   single cost is well-founded: it's fraught with all kinds
   of problematic edge cases which you have to hack
   around.

I don't understand.  Using a single metric, regardless
of how it is defined, is straightforward.  What are the
problematic edge cases?  Using a single metric clearly
doesn't optimize other metrics, but in the general case
you have to use something.

For homogeneous networks, where all of the nodes implement
and make use of the same set of metrics, then that is the
set of metrics you want to use.  For such a network the
choice of parents will be based on information in the metric
containers.  The only additional requirement is that the
choice be reflected in the DAGCost values.

For heterogeneous networks, there is little point in passing
around a vector of metrics if different nodes implement and
optimize different sets of them.  Even if they all implement
the same metrics, nothing is optimized if some nodes pick
parents based on latency, others use reliability, and still
others use energy.  For any notion of optimality all nodes
have to be using more-or-less the same optimization
function.

   As a concrete example, one reason why CTP uses a 16-bit
   encoding of ETX was a need for precision to at least
   tenths of an ETX as well as the ability to support > 25
   hops (the maximum with 8 bits). Our concrete use case for
   the second requirement was the network deployed along the
   length of the Golden Gate Bridge, which was ~40 hops
   long.

Yes, more bits are likely to be needed than the 16 I mentioned.

                                  -Richard Kelsey

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Fri, 3 Jul 2009 09:35:36 +0200

Hi Richard:

Please consider my proposal (attached). It appears that B could rate its
link to MBR poor so give is a 'depth' of say, 6 in a scale of 8. So if C
to A and A to LBR are both perfect links (rated 1) C will be depth 2,
and will not attach to B. When B see C coming, it will attach to C (no
wait) and drop LBR. Can you adapt that generic scheme to your own case
in a satisfactory manner?

I need to explain a lot deeper why we do the things we do. A routing
protocol in general aims are a high degree of loop avoidance AND
stability. Instabilities result from feedback loops. For instance at a
point in ARPANET, the routing metrics would derive from usage, so usage
could change the routing which is turn changes the usage, and this would
create a feedback loop. In a similar fashion, a node movement might
generate another node movement and we could be in a loop.

To avoid such an instability problem, the draft creates an event
horizon. Whatever happens behind you, don't look. So you're only
impacted by movements at a lesser depth, which makes sense in a DV
anyway. So there cannot be a feedback loop. There's probably a better
way to prevent instabilities, but this one has the merits to 1) exist
and 2) be dead simple.

I take advantage of this mail to discuss another illusion. There is no

>    C

Maybe it's BAD for B to be attached to LBR but it's beneficial for C
since that gives it an alternate. So optimizing one thing is detrimental
for another thing (le bonheur des uns...). 

So what the draft does is enable to do something which is satisfactory
though imperfect for all. Consider the event horizon thing. This law
does not prevent in your example B from detaching and then reattach to
C. It only prevents this from happening because of C's messages that
MUST be ignored if coming from deeper. So if for other reasons (link to
B no more good enough, battery depletion, whatever) B detaches from LBR,
then B can later listen to all RAs from that tree and reattach where it
prefers.

And another illusion of a predictable behavior. The characteristics of
the network, including the metrics, are unpredictable. What we really
want is that every node gets an acceptable result most of the time.
There are many ways in which that can be arranged and we do not look for
the illusory perfect DAG one so we could reach any of a large number of
acceptable solutions.

And another illusion, of the perfection of existing IGPs. The IGPs we're
used to operate on a perfect world (one metric, stable links). Yet they
would serve us badly. The shortest path perfection yield to highly used
avenues and many unused alternate links. The shortcomings must be
addressed manually by a new form of art called traffic engineering. All
bad for us: avenues would deplete our batteries on the best path to
rapidly, and manual interventions are antagonistic to one of our main
goals, autonomicity.

With the slowly reforming imperfect structures that we are building, we
expect the paths to change overtime between an acceptable state to
another, and we expect to dissolve the avenue effect. The multiple
forwarding solutions that the DAG propose further enables forthcoming
additions to automate some degree of autonomic traffic engineering,
though haw is can be achieve is out of scope for this doc.

Sorry for all the words...

Pascal

Richard Kelsey
>Sent: jeudi 2 juillet 2009 17:50
>To: Jonathan Hui
>Cc: [email-masked]
>Subject: Re: [Roll] RPL: why not base a DAG on the min hop distance
fromthe root?
>lucky and B might not hear the initial RA from the LBR and

Subject: Re: [Roll] RPL: why not base a DAG on the minhopdistance from theroot?
From: "Pascal Thubert (pthubert)" <[email-masked]>
To: <[email-masked]>, <[email-masked]>, <[email-masked]>, "Alexandru Petrescu" <[email-masked]>, <[email-masked]>
Cc: <[email-masked]>, <[email-masked]>
Date: Fri, 3 Jul 2009 08:24:32 +0200

Hi:

Actually the draft recognizes that there are tons of metrics and then algorithms to sort out those metrics.

The draft also recognizes that the perfect one-fit-it-all scalar metric for all is an illusion amongst a number of other illusions, I'm sure I'll have ample chances to come back to those.

The net result is that RPL extracts the metrics and their handling in a specific component that selects a (set of) preferred  parent(s). That component will vary. From use case to use case. From device generation to the next.

The draft focuses on the generic operations that happen after the preferred parent(s?) is selected. The draft then proposes a number of simple laws to organize the society of machines with different and somewhat conflicting objective. 

The 'depth' metric is the lingua franca that the draft requires to enable comparison between nodes and establish a graph with the required properties of loop avoidance and stability (we're doing a routing protocol) while optimizing the desired property multiple feasible successors for all (that's one of the LLN specific things).

That 'depth' must have a number of properties. It MUST be:

-          Scalar for simple comparison

-          Strictly monotonous to orient the parent links and sort out siblings

-          Universal thus very abstract

-          Coarse grained to enable multiple parents and siblings

-          Constrained in range to count rapidly to infinity if that can happen in the protocol

So it DOES NOT have to be a simple increment by one. Expected Transmission Count is certainly a better approximation of what's needed in a radio mesh and is widely used there. The only trouble with pure ETX is that is makes a lot less sense in wired environment.

My sense is that we should abstract something that could be implemented by ETX - or something else - by the node to characterize its hop to parent. That value would be a scalar link rate, like 1, best can do for that type of link, to 8 for the worst acceptable for that type of link. This abstraction fits the MUSTs of the depth and can be derived from an ETX.

Pascal

From: [email-masked] [mailto:[email-masked]] On Behalf Of [email-masked]
Sent: jeudi 2 juillet 2009 22:22
To: [email-masked]
Cc: [email-masked]; [email-masked]; [email-masked]
Subject: Re: [Roll] RPL: why not base a DAG on the min hopdistance from theroot?

Hi JP and Don, 
You are both correct. The number of hops should be one of the metrics not "the metric". 

Regards, 
Yusuf 

From: 

"Don Sturek" <[email-masked]> 

To: 

"'JP Vasseur'" <[email-masked]> 

Cc: 

[email-masked], [email-masked], [email-masked], [email-masked] 

Date: 

07/02/2009 03:12 PM 

Subject: 

Re: [Roll] RPL: why not base a DAG on the min hop distance        from        theroot?

  _____  

Hi JP,

Absolutely correct.  Number of hops is not *the* metric.  It just cannot be
completely ignored and in some cases (like the data link security example)
it does have a direct affect on latency.

Don

-----Original Message-----
From: JP Vasseur [ <mailto:[email-masked]> mailto:[email-masked]] 
Sent: Thursday, July 02, 2009 1:01 PM
To: [email-masked]
Cc: 'Jonathan Hui'; [email-masked]; [email-masked];
[email-masked]; [email-masked]
Subject: Re: [Roll] RPL: why not base a DAG on the min hop distance from
theroot?

Hi Don,

I think that we are on the same page here: the number of hops should  
not be *the* only metric but *could* be a metric.

Agree ?

Thanks.

JP.

On Jul 2, 2009, at 9:51 PM, Don Sturek wrote:

> Hi Jonathan,
>
> I think the example Yusuf may be referring to involves data link level
> security where packets are encrypted/decrypted hop by hop (please  
> correct me
> if I am wrong).  In that scenario, it is good to minimize the number  
> of hops
> (within reason of course).  If that involves a few extra re- 
> transmissions
> then you probably still end up with a more efficient packet delivery  
> from a
> latency point of view.
>
> Don
>
>
> From: [email-masked] [ <mailto:[email-masked]> mailto:[email-masked]] On Behalf  
> Of
> Jonathan Hui
> Sent: Thursday, July 02, 2009 9:28 AM
> To: [email-masked]
> Cc: [email-masked]; [email-masked]; [email-masked]
> Subject: Re: [Roll] RPL: why not base a DAG on the min hop distance  
> from
> theroot?
>
>
> On Jul 2, 2009, at 8:48 AM, [email-masked] wrote:
>>
>> Using low data rate 802.15.4 radios in commercial buildings we
>> design our deployments
>> to minimize hops and that has been an essential part of the success
>> of our networks. The result of
>> excessive hops is higher latency and higher probability of
>> collisions which leads to devices timing out and going
>> offline. This is an essential customer requirement for us.  We also
>> have data showing that when you do over the air downloads,
>> minimizing hops is key to meeting our timing requirements.
>
> But would you agree that minimizing the number of transmissions on a
> path is a better metric than hops in your case?
>
> --
> Jonathan Hui
>
>  <https://www.ietf.org/mailman/listinfo/roll> https://www.ietf.org/mailman/listinfo/roll
>
>  <https://www.ietf.org/mailman/listinfo/roll> https://www.ietf.org/mailman/listinfo/roll

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

---

From: Alexandru Petrescu <[email-masked]>
Date: Fri, 03 Jul 2009 10:57:00 +0200

Philip Levis a écrit :
> saying it's *the* metric to use. Some implementations are going to want 
> to consider hopcount, others won't. It's just another metric. Rather 
> than hardwire hopcount based assumptions into the protocol design, we 
> should put it on equal footing as other metrics. Correspondingly, the 
> protocol should have general, metric-independent mechanisms for 
> detecting and avoiding loops.

Phil, what does 'loop' mean when metrics other than hopcount are used? 
What does a loop look like when e.g. ETX is used as metric?

Alex

---

From: JP Vasseur <[email-masked]>
Date: Fri, 3 Jul 2009 13:05:02 +0200

Alex and all,

There is clearly a confusion between the use of hop count (depth) to  
avoid loops, the use of the metric to choose a parent (regardless of  
the depth by the way), rules to re-attach to a potential deeper  
parents offering a best path metric, ...

What I suggested to the DT (stay tune for a few hours) is to show  
these rules using simple examples to make sure that every is on the  
same page.

Hope that this will help.

JP.

On Jul 3, 2009, at 10:57 AM, Alexandru Petrescu wrote:

>> metric. Rather than hardwire hopcount based assumptions into the  
>> protocol design, we should put it on equal footing as other  
>> metrics. Correspondingly, the protocol should have general, metric- 
>> independent mechanisms for detecting and avoiding loops.
>
> Phil, what does 'loop' mean when metrics other than hopcount are  
> used? What does a loop look like when e.g. ETX is used as metric?
>
> Alex
>
>

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Fri, 3 Jul 2009 14:06:47 +0200

Agreed. 

The idea on the table would be to select a preferred parent (that might
not be least depth because depth might not be the foremost argument in
parent selection) and then constrain all other parents to be not_deeper.

Pascal

>From: [email-masked] [mailto:[email-masked]] On Behalf Of
Mukul Goyal
>Sent: jeudi 2 juillet 2009 00:56
>To: roll
>Subject: [Roll] RPL: why not base a DAG on the min hop distance from
theroot?
>
>RPL allows a node to have parents with different depths from the root.
By choosing deeper neighbors as
>parents, a node increases its own depth (required to be more than that
of any of its parents to avoid loops)
>and thus makes itself less attractive for selection as a parent.
>
>RPL also allows a node to discard its deeper parents to improve its own
depth and thus make itself more
>attactive for selection as a parent. But this is not mandatory.
>
>The question is what is the inherent benefit of this flexibility? Why
is it that such a DAG may lead to better
>routes than one based strictly on min hop-distance (i.e. where a node
would be required to discard parents
>when it finds less deeper ones)?
>
>Under the RPL approach, the depth of a node is an upper bound on its
hop distance from the root. It just tells
>that a packet forwarded to the node may take anywhere between 1 and the
"depth" hops to reach the root (unless
>the node maintains the "min_hop_distance" from the root as well, in
which case a packet forwarded to the node
>may take any where between "min_hop_distance" and "depth" hops to reach
the root). The end result is that a
>node has very little control over the number of hops a packet, it
forwards, takes to reach the root.
>
>It seems to me that forcing the depth to be same as the min hop
distance would still allow all the benefits of
>DAGs (loop avoidance, flexible routes in face of topology changes)
while assigning a better meaning to the
>term "depth".

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Fri, 3 Jul 2009 14:06:50 +0200

Hi Phil:

What we call depth here does not have to represent a hop count. It
should be incremented by a number that represents an abstraction of the
cost to the parent and that cannot be null. 

What that langua franca metric is really is and by what it is
incremented not settled yet.

The proposal on the table is to give a range for the per hop increment.
The range could be variable per interface type, and it would be
something like 1 to 8. We could decide that on radio networks we
normalize ETX within the acceptable range and rescale that to 1 .. 8,
that way ETX would be the depth increment. 

On other interface types, that could be something else. Including the
fact that you have a battery that you use to get over that interface and
that's going down.

Pascal

>From: [email-masked] [mailto:[email-masked]] On Behalf Of
Philip Levis
>Sent: jeudi 2 juillet 2009 01:01
>To: Mukul Goyal
>Cc: roll
from theroot?

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Fri, 3 Jul 2009 15:34:15 +0200

Hi Mukul:

The only case I see is when the parent that has the least depth also has
poor properties in terms of the metrics that are used for parent
selection. In that case, the preferred parent will be deeper than the
shallowest parent. In general - and in spirit, I'm like you, I do not
see the point of having parents that are deeper than the preferred
parent.

Pascal

Mukul Goyal
>Sent: jeudi 2 juillet 2009 01:08
>To: roll
from the root?
>
>Let me rephrase:
>
>The question is why is it that a DAG where a node can have parents with
different depths is inherently better
>than one where a node can have parents of same depth only (where the
depth may or may not be same as the min
>hop distance from the root)?
>
>Thanks
>Mukul
>
the root?

---

From: [email-masked]
Date: Fri, 3 Jul 2009 08:53:32 -0500

Phil,

Your Golden Gate Bridge example is very
interesting.Did you have to alternate channels as you hopped to maintain

a certain throughput level with
the 40 hops or did the application not care?

Regards,

Yusuf

From:

Philip Levis <[email-masked]>

To:

Richard Kelsey <[email-masked]>

Cc:

[email-masked]

Date:

07/02/2009 07:57 PM

Subject:

Re: [Roll] RPL: why not base a DAG on
the min hop distance from the        root?

>   simultaneously. With multiple metrics, nothing changes as long
as

> the

>   comparator function between two metric vectors is a strictly

> monotonic

>   function. If that strictly monotonic function does not exist
(i.e.

> the

>   difficult. One possible solution is that we require one or
more of

> the

Richard,

Phil

Roll mailing list

[email-masked]

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Fri, 3 Jul 2009 17:42:40 +0200

>other routing constraints.  This seems like a bad idea.

That would. But RPL only used the depth once the parents are selected,
by means that do not have to include the depth at all. Because the draft
says that this part (the plugin) is out of scope than it appears that
the depth is THE metric. No. The depth is a tool for loop avoidance and
stability. It comes after the parent selection happened. All the metrics
that you currently use are welcome.

I tend to agree that 1-increment per link whatever the link is not
panacea either. Hopefully we'll end up converging on that. From Mukul's
comments on ETX I find that there should be a way to translate the link
poor behavior relative to expected as a good reason to fake a worse
depth - be a bit more greedy.

Pascal

Richard Kelsey
>Sent: jeudi 2 juillet 2009 19:28
>To: Jonathan Hui
>Cc: [email-masked]
from theroot?

---

From: Richard Kelsey <[email-masked]>
Date: Fri, 03 Jul 2009 13:24:20 -0400

Date: Fri, 3 Jul 2009 17:42:40 +0200
   From: "Pascal Thubert (pthubert)" <[email-masked]>

   >other routing constraints.  This seems like a bad idea.

   That would. But RPL only used the depth once the parents
   are selected, by means that do not have to include the
   depth at all. Because the draft says that this part (the
   plugin) is out of scope than it appears that the depth is
   THE metric. No. The depth is a tool for loop avoidance
   and stability. It comes after the parent selection
   happened. All the metrics that you currently use are
   welcome.

As I understand the draft, in the situation I described,
RPL always (except if messages go unheard) picks the
shorter route over the longer one.  It doesn't matter
what other metrics are in use.

Here is the example again.  If I have misunderstood how
RPL works, please show me where this example is incorrect.

Cconsider a network with four nodes LBR, A, B, and C, where
A and B do not share a link and, according to the routing
metric in use, the LBR<->B link is inferior enough that the
LBR<->A<->C<->B route is significantly better than the
one-hop LBR<->B route.

   LBR
   / \
  A   B
   \ /
    C

1) LBR, as the root, sends out an RA at depth 0, heard by both
   A and B.
2) A and B choose LBR as their parent, having heard no other
   other RAs.  The order in which A and B choose a parent
   does not affect the outcome.
3) A and B send out their RAs at depth 1, in either order.
4) C picks A as a parent because the cost of the LBR<->B
   link makes B an bad choice.
5) C then sends out an RA at depth 2, which is ignored by B
   because C's depth is greater than B's.

B's route to LBR is the poor-quality LBR<->B link, rather
than the preferred route via C and A.  The routing metric
only affects C's choice of parent.  It has no effect on B's
choice.
                                -Richard Kelsey

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Sat, 4 Jul 2009 20:34:14 +0200

We are certainly converging. I do like the concept though maybe I'd have
used less bits. That's because I expect a given mesh to be formed of
analogous links. 

If so, it is possible to define a unit that represents a normalized good
hop. In my mind that was 1. It makes sense with ETX  in mind that a
radio hop that in average will take one retry could a cost of 2. So it
certainly makes sense to do depth += 2 for that hop. But to malke that
generic to links where the problem is not retries the result for a link
type must be normalized like 1 to 8, whatever the maximum retries is on
that link.

Now if there is a chance that a hop costs a lot less than 1, then it
makes sense to echo Richard and say that the normalize increment for the
link under expected behavior is say 256, but so we can allow both
multiples and fractions of the normalized hop cost. 

What I  strongly doubt is whether the high order octet can still
meaningfully be the real hop count. 

Say what? I don't really mind. That's not required for the ROLL
algorithm to operate. What's needed is a reliable sense of inwards so we
can pass packets towards there and ignore whatever route changes happens
in your back. If we want a hop count we can still have one in the
metrics and it will be used wherever useful.

If the high order octet is not the hop count, then what Richard is
proposing is pretty much analogous to what I just proposed before I read
that mail (gargl, sorry Richard). We have a unit, and a hop costs a
number of units. The way to compute that is specific to the case like
the plugin is. For a link type, there could be is a range of what an
acceptable hop can cost. 

Now do we need 2 octets? Could be useful, but remember, IF we count to
infinity, then we'll pay for the extra. Also, how do we define parents
vs siblings? If that's only the high order bit then that's fine.
Otherwise, being too fine grained will reduce the chances to have
siblings. 

Today the protocol does not count to infinity. That's like a path
holddown, because we block RADIOs for parents going deeper. I'm not sure
whether we should retain that. Following parents that go deeper
immediately treats a loop if RAs are not lost. To be discussed...

What do you think?

Pascal

Jonathan Hui
>Sent: jeudi 2 juillet 2009 23:15
>To: Richard Kelsey
>Cc: [email-masked]
from theroot?

---

From: Tim Winter <[email-masked]>
Date: Sun, 05 Jul 2009 19:15:16 -0400

Hi Richard,

Thanks for all of your feedback so far.

Your example and understanding of RPL is correct.  In my view, it stems in
part from the fact that the loop avoidance mechanism does not trust that
other nodes are cooperative, e.g. trying to make the same optimizations and
taking into consideration the same metrics.  This is a design consideration
in the current specification of RPL, e.g. to support LLNs with nodes that
may have different optimization goals and may use different metrics, not all
of which may be understood by all nodes.

In your example, it leads to a functional LLN, but a suboptimal LLN (which
is the problem).

For illustration, if LBR<->B becomes so bad as to not use the link, then:

6) B will leave the LLN (and start its own floating DAG)
7) B may then, after a hold-up period, hear the DIO of C and attach at depth 3.

Now, the real problem you are pointing out comes when LBR<->B is bad, but
not bad enough to cause B to leave the LLN.  RPLs loop avoidance mechanism
causes node B to behave in a manner that may be too conservative in this cases.

One possible approach is to negotiate/limit the use of the metrics in the
LLN and how they are optimized- maybe by defining `sets' of metrics and
goals for LLNs?  Alternately, to tag certain metrics and their exclusive use
as `safe', e.g. because they are known to monotonically increase globally,
therefore if a node has a smaller value it is known to not be in your
sub-DAG (similar to Jonathan's discussion).

For example, if in an LLN all nodes act to minimize ETX, then node B may
safely make a move to attach to node C based on investigation of ETX- if
node C has a lesser ETX than node B in this case, then by induction node C
cannot be in the sub-DAG of node B and there is no chance of a loop.
Such constraints on the use of metrics would have to be done in an
interoperable manner- and only in the cases were by design it can be sure
that they are globally cooperative, such as `all nodes min ETX', is it safe.

Regards,

-Tim

---

From: Richard Kelsey <[email-masked]>
Date: Sun, 05 Jul 2009 21:58:18 -0400

Tim,

   Date: Sun, 05 Jul 2009 19:15:16 -0400
   From: Tim Winter <[email-masked]>

No problem.  I get paid to do this. :-)

   In your example, it leads to a functional LLN, but a
   suboptimal LLN (which is the problem).

Suboptimal in itself is OK, but hop count has been shown to
be unusably bad in many cases.

   For illustration, if LBR<->B becomes so bad as to not use
   the link, then:

   6) B will leave the LLN (and start its own floating DAG)
   7) B may then, after a hold-up period, hear the DIO of C
   and attach at depth 3.

What is the purpose of the hold-up period?  Is it enough to
hear a DIO from C with a later sequence number?  Or is the
hold-up period typically less than the period between RAs?

                              -Richard Kelsey

---

From: Richard Kelsey <[email-masked]>
Date: Mon, 06 Jul 2009 09:33:55 -0400

Date: Sat, 4 Jul 2009 20:34:14 +0200
   From: "Pascal Thubert (pthubert)" <[email-masked]>

   We are certainly converging.

Yes.  Progress!

   I do like the concept though maybe I'd have used less
   bits. That's because I expect a given mesh to be formed
   of analogous links.

I suggest that we get the algorithms figured out and then
deal with the exact sizes of the fields.

   If so, it is possible to define a unit that represents a
   normalized good hop. In my mind that was 1. It makes
   sense with ETX in mind that a radio hop that in average
   will take one retry could a cost of 2.

A link that requires one retry on average is a pretty bad
link.  I would expect that most reliable links would require
less than that, hence the need for rational costs.

Yes, I agree.

   Now do we need 2 octets? Could be useful, but remember,
   IF we count to infinity, then we'll pay for the extra.

We definitely do not want to count to infinity.  I believe
that using the DIO sequence number avoids the need to count
to infinity.

   Also, how do we define parents vs siblings? If that's
   only the high order bit then that's fine.  Otherwise,
   being too fine grained will reduce the chances to have
   siblings.

If the minimum hop cost is k, then any two nodes whose costs
differ by less than k are siblings, in the sense that
neither is a parent or ancestor of the other.  This has the
effect of making the sibling relationship nontransitive.  A
parent and child can both be siblings of the same node.

Some terminology (which I just made up):
  If a node has DAGcost c and the minimum hop cost is k,
  then:

  - neighbors with costs in the interval (c, c-k) are
    "inward siblings".

  - neighbors with costs in the interval (c+k, c] are
    "outward siblings"

Note that if k = 1 there are no inward siblings and the
outward siblings all have the same cost as the node itself,
as we have now.

Routing via inward siblings will not create a loop.
Converting an inward sibling into a parent will also
not create a loop, assuming that the new parent has
not moved simultaneously.

Routing via outward siblings may create a loop.
Converting an outward sibling into a parent will not
create a loop once the ex-sibling/new-parent has
been informed of the change, again assuming no
simultaneous moves.
                            -Richard Kelsey

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Mon, 6 Jul 2009 18:14:10 +0200

Hi Richard.

(Some sort of) simultaneous moves are already prevented in the spec by
the boot time random. 

That's a tie breaker for nodes that would simultaneously attach to one
another. So when a router sends an RA and receives another one within a
short window of time, it will be able to use that only if the random
based tie breaker allows so - so one will and not the other.

Note that the highest order octet of that tie breaker can be
administered if you want to control how the network forms in a floating
environment.

Yet re-parenting to siblings is discouraged because of additional
complexities associated - like you said, collision, but mostly cases
where your sibling goes deeper by attaching to another sibling, but you
don't know because you missed its RA, and then what you think is inwards
but is outwards, and then you end up in a loop. So basically RPL does
not let a router augment its depth and I understand that your idea of
attaching to an inwards sibling would do that. 

>From that standpoint, I fail to see that k>1 yields a huge benefit for
the cost of the extra complexity.

I still can see value of your decimal approach as long as being more
precise does not cause us to be less stable. As I understand that the
idea was to use the integer part for loop avoidance and still enable to
advertise subincrements that could add up along the way and represent
the path cost more honestly.

There's a danger of ending up with numbers like 1.99 and still advertise
1 or the undesired case where a hop that you would rate .10 causes you
to go from 1 to 2 because the integer part is the depth and must be
incremented. There's also the danger of going from 1.99 to 2.01 which
would cause the node to detach and reattach, require some hysteresis
etc... brrrrr.

Now we could pick a unit that's still quite coarse but yet a half or a
4th a normalized hop cost, and let a hop cost up to 8 or 16 of that
unit. That seems to enable abstracting what we want to achieve here with
things like ETX. So we would let one hop increment the depth by up to
eight and still enable 32 hops across. Or up to 16 and enable at least
16 hops across, generally more.

I thought that this is really where you wanted to get. Did I miss
something?

Pascal

>From: Richard Kelsey [mailto:[email-masked]]
>Sent: lundi 6 juillet 2009 15:34
>To: Pascal Thubert (pthubert)
>Cc: [email-masked]; [email-masked]
from theroot?

---

From: Philip Levis <[email-masked]>
Date: Mon, 6 Jul 2009 09:17:21 -0700

> cost to the parent and that cannot be null.

I didn't say it did -- I was responding to Mukul's suggestion that  
routes should be constrained by hopcount.

Phil

---

From: Philip Levis <[email-masked]>
Date: Mon, 6 Jul 2009 09:16:31 -0700

> used? What does a loop look like when e.g. ETX is used as metric?

If there's a loop in an ETX graph, then ETX does not monotonically  
decrease along the route. This goes back to Jonathan's comment on  
metric vectors.

Phil

---

From: Richard Kelsey <[email-masked]>
Date: Mon, 06 Jul 2009 13:31:00 -0400

Hi Pascal,

   Date: Mon, 6 Jul 2009 18:14:10 +0200
   From: "Pascal Thubert (pthubert)" <[email-masked]>

   [discussion of reparenting to siblings]

It's a side issue and not particularly important, so
we needn't go into it.  We can leave that siblings
are nodes with the same cost to the root.

Not quite.  The idea is to use a route cost for loop
avoidance.  The route cost has a fractional part, but the
entire value is used for loop avoidance, including the
fraction.

Whether or not the low bits of the cost are considered a
fraction is a matter of terminology.  The outcome is exactly
the same if you have an integer cost and require that each
hop have a cost of at least k, for some constant k.  To get
a useful amount of precision, k should be at least 8 or 16.
I don't think that going higher than that is particularly
useful.
                             -Richard Kelsey

---

From: Jonathan Hui <[email-masked]>
Date: Mon, 6 Jul 2009 12:51:49 -0700

Hi Richard,

> are nodes with the same cost to the root.

If I understand properly, the fundamental difference in philosophy  
between Pascal's approach and yours is the orthogonal reasons behind  
coarse vs. fine in the route cost precision. Pascal wants to encourage  
a undirected sibling edges using lower precision. You want to allow  
greater information in the route cost by making it have greater  
precision. Both are fruitful, but are unfortunately at odds. Making  
k>1 means that a packet can actually make backwards progress, so I'm  
not sure that's exactly what we want. I personally favor your original  
approach with k = 1. It does move us closer to a true DAG, but I think  
robustness will still be good in networks that aren't dangerously  
sparse.

> I don't think that going higher than that is particularly

Agree. Things make much more sense now if we say that it is a single  
route cost and each hop must increment by at least X (8 or 16). I also  
think 8 or 16 is sufficient.

Now that we've gone down a path where ETX can be embedded in the loop  
detection information, one open question I'm still grappling with is  
why define a route cost for loop detection separate from the actual  
routing metrics used? In most cases, I would expect a single route  
cost metric will be used. In cases when multiple metrics are used,  
they will often be combined into a single number using some  
polynomial. Are there cases where multiple metrics are used without  
any combination? If so, why not simply designate one of those metrics  
to be used for loop detection?

Isn't the real issue here that the loop detection metrics were  
disjoint from the desired routing metrics?

--
Jonathan Hui

---

From: Tim Winter <[email-masked]>
Date: Mon, 06 Jul 2009 18:13:10 -0400

Hi Richard,

Richard Kelsey wrote:
<SNIP>
> hold-up period typically less than the period between RAs?

Yes, it would be sufficient to hear a DIO from C with a later sequence
number - then node B would be certain that node C was not in its sub-DAG.

Meanwhile, the hold-up timer in this case allows some time for the fact that
node B has detached and formed its own floating DAG to diffuse, in the form
of RA-DIOs into node Bs sub-DAG.  If node B had a sub-DAG, and if node C
happened to be part of it, then by the time the hold-up has finished then
node C should realize, and advertise in its RA-DIOs, that it is now part of
the floating sub-DAG.  Node B would subsequently see that Node C is deeper
in its own sub-DAG and not attach to node C, avoiding a loop.  In an
alternate example, node C is able to remain part of the grounded DAG and
node B may proceed to attach.

In a more complicated example, node B's sub-DAG may have several options to
attach back to the grounded DAG.  In these cases the hold-up timer may have
a variable duration such that nodes who can get a better position into the
grounded DAG will move first, and the rest of the nodes can subsequently follow.

-Tim

---

From: Richard Kelsey <[email-masked]>
Date: Mon, 06 Jul 2009 18:45:53 -0400

Hi Jonathan,

   From: Jonathan Hui <[email-masked]>
   Date: Mon, 6 Jul 2009 12:51:49 -0700

   On Jul 6, 2009, at 10:31 AM, Richard Kelsey wrote:

   >   From that standpoint, I fail to see that k>1 yields a huge benefit  
   >   for the cost of the extra complexity.
   >

   precision. Both are fruitful, but are unfortunately at odds.

With hop count neighbors are either:
  parents  (lower hop count)
  siblings (same hop count)
  ignored  (higher hp count)

With a more precise metric, where the optimal link has cost k,
neighbors can be divided into four categories:
  parents         (cost less by k or more)
  inward siblings (cost less by k-1 or less)
  siblings        (same cost)
  ignored         (higher cost)

In either case, forwarding via siblings or 'ignored' can
send a message around a loop.  Forwarding via parents or
inward siblings cannot.

Using a more precise metric produces fewer siblings, with
the remainder being either 'ignored' or inward siblings.
category.  The net effect is to increase the number of
neighbors that can be used to forward messages without
creating into a loop, while decreasing the number that might
create a loop.

I don't have any idea which is likely to work better in
practice.

   Making k>1 means that a packet can actually make
   backwards progress, so I'm not sure that's exactly what
   we want. I personally favor your original approach with k
   = 1. It does move us closer to a true DAG, but I think
   robustness will still be good in networks that aren't
   dangerously sparse.

I am not sure what 'k' means here.

   Now that we've gone down a path where ETX can be embedded
   in the loop detection information, one open question I'm
   still grappling with is why define a route cost for loop
   detection separate from the actual routing metrics used?

One advantage of having multiple metrics is that it
indicates the actual properties of the route.  It
might make a difference whether it was a low-latency
or low-energy route.  This works well only if there
are not multiple parents (a tree, not a DAG), so
that picking a parent also picks a path.

I suppose that a root could create two separate DAGs
with different metrics.  For time-critical messages
you use the low latency DAG, for ordinary messages you
use the low energy one, even though they go to the
same root.  Keeping track of two DAGs would be costly.

   In most cases, I would expect a single route cost metric
   will be used. In cases when multiple metrics are used,
   they will often be combined into a single number using
   some polynomial. Are there cases where multiple metrics
   are used without any combination? If so, why not simply
   designate one of those metrics to be used for loop
   detection?

If you do that, the loop detection metric will trump
the other ones in some cases.  

Yes.  A related issue is that for lossy links I think any
metric works better if the second best link cost is not
twice the best.  With hop count you have no choice.

                                  -Richard Kelsey

---

From: Jonathan Hui <[email-masked]>
Date: Mon, 6 Jul 2009 16:06:04 -0700

Hi Richard,

> I don't have any idea which is likely to work better in

In the end we are saying the same things just in different words. A  
less precise route cost produces more siblings and leaves more edges  
undirected. A more precise route cost makes more edges directed. The  
one that works better in practice depends on the density and number of  
feasible successors. In other words, if there are many edges to choose  
from - why not orient them and avoid loops altogether? In a sparse  
network, you might want to leave them undirected to give greater  
opportunity of routing around failures.

> I am not sure what 'k' means here.

Sorry - too many uses of 'k' in this thread. It's the same 'k' that  
you used when defining "inward/outward" siblings. I was just observing  
that outward siblings is worse that strict siblings in that a packet  
may make reverse progress when following outward siblings.

> that picking a parent also picks a path.

The advertised metric in the DAG case can just be the upper bound. In  
the hop-count case that's in the current RPL draft, the advertised  
depth indicates that all of it's parents will have a smaller hop count.

> same root.  Keeping track of two DAGs would be costly.

The Cisco guys would say that this is a classic use case of Multiple  
Topology Routing (MTR). Maintaining two DAGs is basically what they  
would propose to do :-). I do agree that maintaining multiple  
topologies is not cheap.

> the other ones in some cases.

Yes, but at least you're using a metric that you care about. What is a  
good example of having two disjoint metrics that you would prefer not  
to combine for a routing cost, but would combine for loop avoidance?

> twice the best.  With hop count you have no choice.

Agree.

--
Jonathan Hui

---

From: Alexandru Petrescu <[email-masked]>
Date: Tue, 07 Jul 2009 11:19:16 +0200

Philip Levis a écrit :
>>> Richard, This seems like a totally reasonable metric to use, but
>>> I'd be wary of saying it's *the* metric to use. Some
>>> implementations are going to want to consider hopcount, others
>>> won't. It's just another metric. Rather than hardwire hopcount
>>> based assumptions into the protocol design, we should put it on
>>> equal footing as other metrics. Correspondingly, the protocol
>>> should have general, metric-independent mechanisms for detecting
>>> and avoiding loops.
>> 

I personally haven't yet grasped the notion of a loop in terms of ETX
(Expected Transmission count metric [De Couto 2003]).  I do understand a
loop in terms of the hop count metric.

By your definition above it may seem that an ETX-loop appears when the 
ETX increases arbitrarily along a path.  From this I think there may be 
loop-free paths (in terms of hopcount) which are ETX-loops.

Alex

Alex

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Tue, 7 Jul 2009 14:21:23 +0200

Hi Richard:

I do not follow your inward sibling idea. Being sibling is a symmetrical
relationship. 
I am your siblings <=> you are my sibling. Inward is not like that so
it's not siblings.
What you could do instead is mask off the least significant M bits.

Pascal

>Sent: mardi 7 juillet 2009 00:46
>To: Jonathan Hui
>Cc: Pascal Thubert (pthubert); [email-masked]
from theroot?

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Tue, 7 Jul 2009 14:21:27 +0200

>opportunity of routing around failures.

I'd say that in dense networks the routers should have enough parents to
choose from so they would never need the siblings or even keep track of
them by lack of resources. So the coarse metric seems to obtain the
desired result in both cases, use parents when there are enough of them,
enable siblings in sparse conditions. 

We can carry many metrics and their aggregation over a path will be the
factor to select a parent. Then again depth is there for loop avoidance
and stability, not for parent selection. 

Form this thread I gather that:
- Improving the definition of the metric (that is providing decimals)
improves only the likelihood that alternate parents provide similar
services, and that will be true only if with homogeneous devices. 
- allowing a hop to cost several times more than another hop can also
help abstract a bad but still usable link.

I understand from this discussion that there's value in allowing
something like that and I tend to agree if we keep it tightly
constrained. How much could be link type or deployment dependent so we
need sensible defaults (per link type?) for instance enable a reasonable
range to cover ETX in radios. We also need to be consistent along a DAG
to make any sense so we need a representation to be able to advertize
that in DIO.

So why not enable to split the depth increment in 3 zones. The size of a
zone is expressed in bits.

- The least significant bits would be "decimals" of a normalized hop
(d-field of D bits)
- The middle bits would de usable to represent that the number of
normalized hop (n-field of N bits)
- The most significant bits represents how many hops across we can do
before the depth can reach infinity. (h-field of H bits
0<H<=depth_size-D-N). Must be set to zero in the increment, meaning 0 or
1 of all the other fields have a length of zero.

So we'd just need to carry the values for D, N, H and INFINITY in the
DIO. Because an increment of zero is unlawful, we could encode as
follows:

- D=0; N=0. The depth is a hop count along the (preferred?) path. Could
have up to 254 hops.
- D=1; N=0 allows a hop to cost 0.5 or 1 normalized hop cost. Could have
up to 254 hops.
- D=2; N=0 allows a hop to cost 0.25, 0.5, 0.75 or 1 normalized hop cost
- D=0; N=1 allows a hop to cost 1 or 2 normalized hop count
- D=2; N=1 allows a hop to cost 0.25 to 2 normalized hop count by .25
increments. 
- D=1; N=2 allows a hop to cost 0.5 to 4 normalized hop count by .5
increments.
Etc...

With that encoding, the current draft is using D=N=0. There's no way to
extract the real hop count from the depth if another setting for D and N
is used. If so, hop count could still be transported as a one input
metric, but would not be the one used for loop avoidance.

Another number M that could be useful is how many low significant bits
are masked off for parent vs. sibling determination. I think I agree
with Richard that we can start with M=0, which then again is the way the
draft is written. It could be useful to artificially set it up higher to
augment the number of siblings in a very sparse environment.

As density augments, M is 0 and it becomes possible to use larger values
of D+N but my sense is that we should rather make it so that less nodes
act as router and thus control the maximum density of routers. If so,
there would not be a need for D+N to grow too large, maybe 3 or 4 bits
for the 2 of them at most.

In which case depth field of 8 bits is still enough. History has shown
that we might want to grow the size of the depth metric so it's cool to
allow for 16 bits in the DIO as long as we control D+N+H stays
reasonable (like within one octet) for the cases at hand.

Is that what you wished to be able to express?

Note: I'll be away from this mailing list from today till the IETF. I
wish you all a good summer time since then.

---

From: Richard Kelsey <[email-masked]>
Date: Tue, 07 Jul 2009 09:12:35 -0400

Hi Jonathan,

   From: Jonathan Hui <[email-masked]>
   Date: Mon, 6 Jul 2009 16:06:04 -0700

With more precision in route cost you can increase the
number of undirected links by partioning costs into
horizontal bands.  Pick a constant h and define siblings to
be nodes that have the same value for

   floor(cost / h)

If h is the same as the optimal link cost you get siblings
that are analogous to those produced by hop count.  In
theory you could make h greater than the optimal link cost,
but that could get complicated, depending on the mechanism
used to avoid loops when routing through siblings.

If we have a reliable way to prevent looping when routing
through siblings, then I would propose that we use h equal
to the optimal link cost.  This would gives us close to what
we have now in terms of siblings.  This is what you meant
by having k=1, correct?

If we cannot prevent looping when routing through siblings,
it would be better to only allow forwarding via nodes with
lower cost (parents and 'inward siblings').

                                -Richard Kelsey

---

From: Richard Kelsey <[email-masked]>
Date: Tue, 07 Jul 2009 11:45:17 -0400

Hi Pascal,

> Date: Tue, 7 Jul 2009 14:21:23 +0200

You are correct that inward siblings and outward siblings
are not siblings.  'Siblings', 'inward siblings, and
'outward siblings' are three disjoint sets of neighbors.

For node N, its 'inward siblings' are nodes that whose cost
is less than N's but not enough less that N can use them as
parents.  N's 'outward siblings' are neighbors whose costs
are greater than N's, but not enough greater that they can
be children of N.

And yes, you could do instead is mask off the least
significant M bits, or, more generally, divide by some
constant.  Which method is better depends on the
circumstants, including whether or not routing to siblings
may create a loop.

                                -Richard Kelsey

P.S. Strictly speaking, only nodes with the same parent are
siblings.  Nodes at the same depth in a DAG are usually
called a 'level', I think, but that doesn't work as well
grammatically.  'Cousins' might be a better term for us than
'siblings'.

---

From: Jonathan Hui <[email-masked]>
Date: Tue, 7 Jul 2009 09:44:21 -0700

Hi Richard,

> used to avoid loops when routing through siblings.

Sure. You can arbitrarily truncate the route cost and make it less  
precise for use with loop detection. Having hard bounds defining each  
band is useful to make sure packets never make reverse progress.

> we have now in terms of siblings.  This is what you meant

Yes, that's what I meant. I don't think there's a particular mechanism  
to *prevent* loops. Pascal's assumptions are that a packet will only  
continue to loop with some small-ish probability. If a packet does get  
stuck in a loop, then the hop limit will expire it. Only annoying  
thing with relying on the hop limit is ICMPv6 time exceeded errors.

> lower cost (parents and 'inward siblings').

I also like that this encourages fewer loops. The special case,  
however, is when you're near the root. Assuming perfect information,  
there will be one node that has no alternate parents.

--
Jonathan Hui

---

From: Jonathan Hui <[email-masked]>
Date: Tue, 7 Jul 2009 10:05:47 -0700

Hi Pascal,

> 1 of all the other fields have a length of zero.

While this is certainly more general and interesting, I think it's  
going a bit too far :-). We should be able to settle on some fixed- 
point format - identify the number of fractional and integral bits.

I do like the ability to specify the maximum number of hops (i.e.  
infinity).

I'm also good with carrying the hop count as a separate "metric" that  
won't be used for loop avoidance. I've found that hop information can  
be useful as management information - more so than an actual route  
metric.

--
Jonathan Hui

---

From: Philip Levis <[email-masked]>
Date: Tue, 7 Jul 2009 09:28:48 -0700

On Jul 7, 2009, at 2:19 AM, Alexandru Petrescu wrote:

> By your definition above it may seem that an ETX-loop appears when  
> the ETX increases arbitrarily along a path.  From this I think there  
> may be loop-free paths (in terms of hopcount) which are ETX-loops.

Have you read the CTP paper? It talks about this in depth. A loop  
*can* occur when a metric that should monotonically decrease along a  
route (hop count, ETX, etc.) doesn't do so due to inconsistencies in  
tables.

Phil

---

From: Philip Levis <[email-masked]>
Date: Tue, 7 Jul 2009 09:59:00 -0700

> enable siblings in sparse conditions.

Routing loops are only a problem if they persist, such that they waste  
transmissions and lose packets. If the protocol can detect loops and  
repair them on the order of a few packet times -- loops are always  
transient -- they aren't a problem. It can be that all of the  
mechanisms you put in place to avoid/prevent loops are more expensive  
than simply detecting and repairing them.

Phil

---

From: Philip Levis <[email-masked]>
Date: Tue, 7 Jul 2009 10:08:02 -0700

On Jul 7, 2009, at 9:44 AM, Jonathan Hui wrote:
> Yes, that's what I meant. I don't think there's a particular  
> mechanism to *prevent* loops. Pascal's assumptions are that a packet  
> will only continue to loop with some small-ish probability. If a  
> packet does get stuck in a loop, then the hop limit will expire it.  
> Only annoying thing with relying on the hop limit is ICMPv6 time  
> exceeded errors.
>

This seems like towards the right approach -- avoid loops and quickly  
detect them when they occur, rather than go through gymnastics to  
prevent them.

Phil

---

From: JP Vasseur <[email-masked]>
Date: Tue, 7 Jul 2009 22:48:09 +0200

On Jul 7, 2009, at 6:59 PM, Philip Levis wrote:

> Routing loops are only a problem if they persist, such that they  
> waste transmissions and lose packets. If the protocol can detect  
> loops and repair them on the order of a few packet times -- loops  
> are always transient -- they aren't a problem. It can be that all of  
> the mechanisms you put in place to avoid/prevent loops are more  
> expensive than simply detecting and repairing them.

Excellent point and I fully agree ... this is true in most LLNs'  
application (not all but most).

---

From: Alexandru Petrescu <[email-masked]>
Date: Wed, 08 Jul 2009 12:02:16 +0200

Philip Levis a écrit :
>> ETX increases arbitrarily along a path.  From this I think there may 
>> be loop-free paths (in terms of hopcount) which are ETX-loops.
> 
> Have you read the CTP paper? It talks about this in depth. A loop *can* 
> occur when a metric that should monotonically decrease along a route 
> (hop count, ETX, etc.) doesn't do so due to inconsistencies in tables.

Yes, I read the Collection Tree Protocol CTP paper at 
http://tinyos.net/tinyos-2.x/doc/txt/tep123.txt
It indeed describes loops in terms of ETX.

I have some doubts though.

CTP addressing and 'routing' model seems different than IP addressing 
and routing.  For example CTP doesn't use IP addresses, and considers 
that src and dst fields in packets are those of immediate neighbors, not 
further.  CTP also considers a 'beacon' can be sent to the entire network.

(I think many a source of confusion of the discussions here is from
  using terms such as routing/forwarding/loops mixing the expected
  meanings between networking and link-layer.)

Routing and addressing at networking and link-layer are very different.

Back to my remark, after reading the CTP paper I still have problems 
grasping the concept of an _IP_ loop in terms of ETX and of hopcount at 
the same time.

Alex

---

From: Alexandru Petrescu <[email-masked]>
Date: Wed, 08 Jul 2009 13:03:32 +0200

> grammatically.  'Cousins' might be a better term for us than

I agree to call 'siblings' only nodes having a same direct parent, in a 
tree (not DAG).  I am used to it.

Alex

---

From: Philip Levis <[email-masked]>
Date: Wed, 8 Jul 2009 10:05:43 -0700

On Jul 8, 2009, at 3:02 AM, Alexandru Petrescu wrote:

>
> Yes, I read the Collection Tree Protocol CTP paper at http://tinyos.net/tinyos-2.x/doc/txt/tep123.txt

That's the specification. This is the paper:

http://sing.stanford.edu/pubs/sing-09-01.pdf

> grasping the concept of an _IP_ loop in terms of ETX and of hopcount  
> at the same time.

Both hopcount and ETX define a gradient to a destination. In both  
cases, the value of the destination is 0. In the case of hopcount, the  
gradient decreases by 1 on each hop. So a route (source, X, Y, Z,  
destination) looks like this:

Source (4) -> X (3) -> Y (2) -> Z (1) -> Destination (0)

In the case of ETX, the gradient decreases by >=1 on each hop. So a  
route (source, X, Y, Z, destination) could look like this:

Source (6.4) -> X (5.1) -> Y (3.3) -> Z (1.8) -> Destination (0)

In both cases, a loop can exist if and only if the gradient value does  
not decrease across a hop. If the gradient value decreases  
monotonically, it will reach zero and there is no loop. But here's a  
possible loop:

Case A: Source (3) -> X (2) -> Y (3) -> X (2) -> Y (3)

or

Case B: Source (3) -> X (2) -> Y (2) -> X (2)

These can occur when a node changes its route and updates its gradient  
value but its children have not yet learned the new value. E.g., the  
link between Y and Z breaks, leading to case A, where Y's best choice  
for a next hop is X.

Phil

---

From: JP Vasseur <[email-masked]>
Date: Thu, 9 Jul 2009 08:38:36 +0200

On Jul 8, 2009, at 7:05 PM, Philip Levis wrote:

>> Back to my remark, after reading the CTP paper I still have  
>> problems grasping the concept of an _IP_ loop in terms of ETX and  
>> of hopcount at the same time.
>
> cases, the value of the destination is 0. In the case of hopcount,  
> the gradient decreases by 1 on each hop. So a route (source, X, Y,  
> Z, destination) looks like this:
>
> In both cases, a loop can exist if and only if the gradient value  
> does not decrease across a hop. If the gradient value decreases  
> These can occur when a node changes its route and updates its  
> gradient value but its children have not yet learned the new value.  
> E.g., the link between Y and Z breaks, leading to case A, where Y's  
> best choice for a next hop is X.

But the loop is transient. Note that the exact same situation exist  
with link state protocol, we call it a micro-loop since it is quickly  
resolve but time scale are different and although loop duration may be  
much shorter, the number of impacted packets may be much larger.

Cheers.

JP.

---

From: JP Vasseur <[email-masked]>
Date: Thu, 9 Jul 2009 08:41:34 +0200

On Jul 7, 2009, at 7:08 PM, Philip Levis wrote:

>> mechanism to *prevent* loops. Pascal's assumptions are that a  
>> packet will only continue to loop with some small-ish probability.  
>> If a packet does get stuck in a loop, then the hop limit will  
>> expire it. Only annoying thing with relying on the hop limit is  
>> ICMPv6 time exceeded errors.

And this is acceptable as long as we detect them and then break those  
loops, as opposed to imposing strict rules to avoid them especially  
when they impose severe constraints.

>> however, is when you're near the root. Assuming perfect  
>> information, there will be one node that has no alternate parents.
>
> This seems like towards the right approach -- avoid loops and  
> quickly detect them when they occur, rather than go through  
> gymnastics to prevent them.
>

Yes indeed.

JP.

---

From: Michael Richardson <[email-masked]>
Date: Mon, 13 Jul 2009 07:03:51 -0400

>>>>> "Richard" == Richard Kelsey <[email-masked]> writes:
    Richard> precision. Both are fruitful, but are unfortunately at odds.

    Richard> With hop count neighbors are either:
    Richard> parents  (lower hop count)
    Richard> siblings (same hop count)
    Richard> ignored  (higher hp count)

    Richard> With a more precise metric, where the optimal link has cost k,
    Richard> neighbors can be divided into four categories:
    Richard> parents         (cost less by k or more)
    Richard> inward siblings (cost less by k-1 or less)
    Richard> siblings        (same cost)
    Richard> ignored         (higher cost)

    Richard> In either case, forwarding via siblings or 'ignored' can
    Richard> send a message around a loop.  Forwarding via parents or
    Richard> inward siblings cannot.

  Let's say that I have a network that looks like this:

           R
          / \
         X   Y
         |   |
 	 A   B
        / \ / \
       C   D   E

  I thought that one of the goals of this protocol was such that one
could have a route E->B->D->A->X-R as well as a route E->B->Y->R for the
situation where X had a good power supply, while Y had a power budget.
  or is this handled by another part of the protocol?

  If Y shows a high enough hop-cost to prefer the longer route, then it
never gets used, which perhaps is an issue if the links are at capacity.

  This is why I do not understand the focus on a DAG, when I thought
that the problem was more complex.  (Back to reading the documents and
this long thread)

- -- 
]     Y'avait une poule de jammé dans l'muffler!!!!!!!!!        |  firewalls  [
]   Michael Richardson, Sandelman Software Works, Ottawa, ON    |net architect[
] [email-masked] http://www.sandelman.ottawa.on.ca/ |device driver[
]    h("Just another Debian GNU/Linux using, kernel hacking,    ruby  guy");  [

---

From: Russ White <[email-masked]>
Date: Tue, 14 Jul 2009 11:33:59 -0400

> But the loop is transient. Note that the exact same situation exist with
> link state protocol, we call it a micro-loop since it is quickly resolve
> but time scale are different and although loop duration may be much
> shorter, the number of impacted packets may be much larger.

Yes--this isn't what we would call a loop, but a transient loop, because
it resolves itself. RIP and BGP do the same thing. In fact, there is
only one routing protocol in widespread use that doesn't have
microloops, as far as I know.

:-)

Russ

- --
[email-masked] :: CCIE :: CCDE :: <>< Grace Alone

What makes us happy in life is not what we've acquired. What makes us
happy in life is what we appreciate.

---

From: Tim Winter <[email-masked]>
Date: Tue, 14 Jul 2009 13:28:44 -0400

Hi Michael,

> that the problem was more complex.  (Back to reading the documents and

First, I would like to clarify (just in case there is any doubt) that RPL is
not generally trying to minimize hop count.  ;)  (Although it could if that
was the defined metric and optimization goal).

Finding the `least cost' path across multiple intermediate nodes according
to some metric using distance vector protocols should tend to yield a tree-
allowing for multiple choices of parents is how we get to a DAG.

RPL is capable to employ whatever metrics and objective functions that have
been defined in a particular implementation in order to construct the
least-cost DAG to the DAG Root.  (As a *consequence*, a node takes up a
position in a DAG, has a related rank (depth), and this is taken advantage
of for some loop avoidance as the DAG undergoes maintenance -- which is
another topic).

In your example, if I understand right, you want to use one path
(E->B->D->A->X->R) when you want to avoid node Y, e.g. to avoid using Y's
limited energy, and to use path E->B->Y->R in another case, e.g. to reduce
latency.  In the case you have stated as I understand it, it is really as if
you are trying to maintain 2 routing topologies, one to minimize energy
(where using Y is expensive) and one to minimize latency/hop-count (where
avoiding Y is expensive).  In this case, RPL would in fact construct 2 DAGs,
both rooted at `R'.  One DAG would be constructed using the `min latency'
objective and the second with the `min energy' objective.  If we follow the
conventions of the recently posted -01 draft, each DAG would be defined by a
different Objective Code Point (OCP)- one to indicate the `min latency' goal
and one for the `min energy' goal.  Subsequently, the traffic would have to
be marked in the IPv6 header in such a way that it can follow the correct
DAG.  For example, a particular Traffic Class might follow the `min latency'
DAG by administrative convention, and all other traffic might default to the
`min energy' DAG.

To extend your example, the use of multiple metrics does not necessarily
mean that RPL must maintain multiple DAGs.  In some cases it may be
possible/appropriate to define a `synthesis' function that digests/weights
multiple metrics into a single scalar value and subsequently uses that
scalar for the purpose of finding the least cost path.  In the case of RPL
this is not part of the core specification, but would be
application/implementation specific and defined in the specification of a
particular OCP.

Does this help?

-Tim

---

From: Russ White <[email-masked]>
Date: Tue, 14 Jul 2009 09:42:49 -0400

:-)

Russ

- --

The whole aim of practical politics is to keep the populace alarmed (and
hence clamarous to be led to safety) by menacing it with an endless
series of hobgoblins, all of them imaginary. -H.L. Menkin