Subject: [Roll] RPL spec v6: Preferred Parent for Rank Calculation and Packet Forwarding

From: Phoebus Chen <[email-masked]>
Date: Wed, 03 Mar 2010 15:23:31 +0100

Hello,

In version 6 of the RPL specification, the preferred parent is used for 
two purposes:
1) Rank calculations (pg. 36, Sec. 5.3.4.1) (bottom of pg. 59, Sec. 10)
2) Preferred next hop for forwarding packets upwards (pg. 30, Sec. 
5.3.2) (pg. 56,57, Sec. 8)

I recall that this had caused some confusion on the mailing list earlier 
on.  Is it really a good idea to have the preferred parent serve both 
purposes?

We had a discussion within our research group, and there does seem to be 
situations where it might be better to NOT force every node in the DODAG 
to specify a preferred parent for forwarding packets.  For instance, if 
a node has several parents with reliable paths to the root (and their 
reliability doesn't differ too much), there might be better load 
balancing in the network if you allow a node to cycle through its 
parents when forwarding packets.  This could affect packet queuing 
delay, energy consumption, etc.

Another example arises when using a fixed, repeating TDMA schedule for 
the network, like with WirelessHART.  The first link scheduled for 
transmission after a packet arrives at a node (or is generated at a 
node) might not be to the node's preferred parent.  If RPL requires that 
a node tries to forward to the preferred parent first, then the packet 
will have to wait at the node.  This could severely prolong the 
end-to-end latency of the packet if this situation happens at each hop 
along the path and the nodes in the network are duty-cycled (sleep) to 
save energy.

Section 10, "Guidelines for Objective Functions," goes so far as to 
suggest creating an ordered list of parents, presumably for preference 
forwarding packets.  If this is just a suggestion, I feel that this 
section needs to be clearer what is required (MUST) and what is optional 
(SHOULD).

On the other hand, I feel that the current RPL specification makes sense 
designating a node in the parent set with the highest rank (whether you 
want to call it the "preferred parent" or something else) to calculate 
the rank of the node.

What do others think of this suggestion to not force all RPL 
implementations to designate a preferred parent for forwarding packets?

-- 
Phoebus Chen
Postdoctoral Researcher
Automatic Control Lab, KTH (Royal Institute of Technology)
http://www.ee.kth.se/~phoebus

---

From: Anders Jagd <[email-masked]>
Date: Wed, 3 Mar 2010 10:16:33 -0500

Phoebus,

I believe Section 7.1 is quite clear about the forwarding options for each
node:

Quote:
5. If there is a DODAG iteration offering a route to a prefix matching the
destination, then select *one of those DODAG parents* as a successor.
End Quote

Nothing written about giving preference to the "preferred parent". Not only
is load balancing allowed, I believe it is encouraged (on a case by case
basis as usual).

I do agree that, in order to avoid confusion, we may want to get rid of the
"preferred parent" terminology, unless there is some other "special
attention" given to the preferred parent.

/Anders

On Wed, Mar 3, 2010 at 9:23 AM, Phoebus Chen <[email-masked]> wrote:

> Hello,
>
> In version 6 of the RPL specification, the preferred parent is used for two
> purposes:
> 2) Preferred next hop for forwarding packets upwards (pg. 30, Sec. 5.3.2)
> (pg. 56,57, Sec. 8)
>
> situations where it might be better to NOT force every node in the DODAG to
> specify a preferred parent for forwarding packets.  For instance, if a node
> has several parents with reliable paths to the root (and their reliability
> doesn't differ too much), there might be better load balancing in the
> network if you allow a node to cycle through its parents when forwarding
> packets.  This could affect packet queuing delay, energy consumption, etc.
>
> Another example arises when using a fixed, repeating TDMA schedule for the
> network, like with WirelessHART.  The first link scheduled for transmission
> after a packet arrives at a node (or is generated at a node) might not be to
> the node's preferred parent.  If RPL requires that a node tries to forward
> to the preferred parent first, then the packet will have to wait at the
> node.  This could severely prolong the end-to-end latency of the packet if
> this situation happens at each hop along the path and the nodes in the
> network are duty-cycled (sleep) to save energy.
>
> Section 10, "Guidelines for Objective Functions," goes so far as to suggest
> creating an ordered list of parents, presumably for preference forwarding
> packets.  If this is just a suggestion, I feel that this section needs to be
> clearer what is required (MUST) and what is optional (SHOULD).
>
> designating a node in the parent set with the highest rank (whether you want
> to call it the "preferred parent" or something else) to calculate the rank
> of the node.
>
> _______________________________________________
> Roll mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/roll
>

---

From: Anders Jagd <[email-masked]>
Date: Wed, 3 Mar 2010 10:40:48 -0500

Allow me to clarify myself (see below)
/Anders

> attention" given to the preferred parent.
I meant to say "unless there is some other special attention - besides rank
calculation - given to the preferred parent".

>> forwarding packets.  If this is just a suggestion, I feel that this section
>> needs to be clearer what is required (MUST) and what is optional (SHOULD).
>>

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Wed, 3 Mar 2010 16:44:24 +0100

Hi Anders and Phoebus

Quote:

5. If there is a DODAG iteration offering a route to a prefix matching
the destination, then select *one of those DODAG parents* as a
successor.

End Quote

Nothing written about giving preference to the "preferred parent". Not
only is load balancing allowed, I believe it is encouraged (on a case by
case basis as usual).

[Pascal] Most certainly. This also enables a quick reactivity to
transient events that will not be reflected in the routing plane. 

I do agree that, in order to avoid confusion, we may want to get rid of
the "preferred parent" terminology, unless there is some other "special
attention" given to the preferred parent.

[Pascal] The preferred parent is still needed as the reference for the
metrics computation. If a node derives its own metrics from that of a
preferred parent, then it can be expected that this preferred parent
also gets the bulk of the traffic, otherwise the node is not honest
about the service that it is providing.

Pascal

---

From: Phoebus Chen <[email-masked]>
Date: Wed, 03 Mar 2010 17:30:01 +0100

Anders and Pascal,

Thanks for your responses.  Comments Inline below.

On 3/3/10 4:44 PM, Pascal Thubert (pthubert) wrote:
> the destination, then select *one of those DODAG parents* as a successor.
>
> End Quote
>
> */[Pascal] Most certainly. This also enables a quick reactivity to
> transient events that will not be reflected in the routing plane. /*

Hmm, then I suppose that the text I quoted:

(pg. 30, Sec. 5.3.2)
"Finally, the preferred parent, a set of size one, is an element of the 
parent set that is the preferred next hop in upward routes."

(pg. 56,57, Sec. 8)
"For a source inside the DODAG, the packet is passed to the preferred
  parents, and if that fails then to the alternates in the DODAG."

is outdated and will be removed in the next revision of the specification?

> */[Pascal] The preferred parent is still needed as the reference for the
> about the service that it is providing./*
>
> */Pascal/*
>

I see your point of why you might want to make a node get the bulk of 
the traffic if it is the basis for the (single-path) metric computation.
But if a node really is doing load balancing, he is "not being honest" 
by sending the bulk of the traffic to one parent anyways, regardless of 
whether you call it a "preferred parent." ;)

As an aside, I'd like to point out that although this mailing list and 
the drafts have been discussing mostly single-path metrics, there may be 
multi-path / mesh metrics developed for RPL in the future.  What I mean 
by a multi-path/mesh metric is a metric assigned to a node that takes 
into account all the paths through its parents.  These aren't so common 
in the literature, so I'll take an example of what I've worked with. 
Suppose you want to define a metric that measures reliability, i.e. 
end-to-end packet delivery probability, when you have a mesh of paths 
from a source to a sink.  Such a metric should reflect the fact that 
routing to a parent with many equally good paths to the sink is better 
than routing to a parent that has one good path to the sink.

If you're skeptical that such multi-path metrics can be defined, you can 
look at one example:
http://www.eecs.berkeley.edu/Pubs/TechRpts/2009/EECS-2009-75.html
pg. 73, Definition 2.3.2.  In a nutshell, it measures the end-to-end 
delivery probability assuming that a node will try to forward packets on 
its outgoing links with equal probability, and calculates the 
probability that a packet reaches the sink assuming all links are 
independent and stay up or down (does not switch between the two) during 
the entire duration of the packet transmission.

I'll probably comment more on this later... after I've read the latest 
version of the routing metrics document and can provide some feedback.

---

From: Anders Jagd <[email-masked]>
Date: Thu, 4 Mar 2010 10:59:43 -0500

Phoebus,

One thing to keep in mind is that RPL-06 - at least the way I look at it -
is a "base" draft (others, feel free to correct me). It is extremely
ambitious to generate a single RFC suitable for networks ranging from small
home area "light switch control" networks to large scale urban smart grid
networks with tens of thousands or even hundred of thousands of nodes. This
is what I meant when I, in a previous mail, congratulated the WG on having
achieved a good balance of content for such a base document.

In a base document, general rules are defined, while specific algorithms are
only hinted at. More work is clearly needed moving forwards in the form of
"applicability" documents for various environments.

That said, let me comment a bit further on the "preferred parent":

Rank and aggregated metrics are not the same, but they will typically be
somewhat (even strongly) correlated. As we all know, a nodes rank is given
by preferred parent rank + some "delta". All other parents must have ranks
less than the nodes rank, which, since "delta" is bounded, typically limits
the number of parents with a rank higher than the preferred parent. In other
words, often, if a node wants to maintain a lot of parents (for redundancy,
load balancing, etc.), many (most) of them will have a lower rank (thus to
some extent better aggregated metric) than the preferred parent. So, if a
node chooses to forward a message through an alternative (not preferred)
parent, chances are that quality/metrics are actually "better" than what the
node "promised" downstream.

This is all (intentionally) kept somewhat vague; applicability documents
will need to make all of this more precise, in particular if we are to
enable multi-vendor "heterogeneous" systems. As far as I understand, this
could be left up to the objective function, which would specify how much (if
at all) a node may deviate from it's "promised" aggregated metric, even to
the (extreme) extent of limiting nodes to never route through non-preferred
parents with worse metrics.

A clear (and well known) dilemma can probably be seen here. If a node wants
to maintain a lot of parents (redundancy, robustness, load balancing, ...),
it will typically be difficult to, at the same time, achieve best possible
aggregated metric. This since, in order to collect a lot of parents, the
node will likely have to base it's rank (metric) on a "preferred" parent
that is not the lowest ranked one. So, being "greedy" regarding parent set
won't be "free" (no free lunch).

I hope this helps. The above are obviously my interpretations, not
necessarily the WGs, so I look forward to become educated in case I have
(unintentionally) misinterpreted something.

/Anders

On Wed, Mar 3, 2010 at 11:30 AM, Phoebus Chen <[email-masked]> wrote:

> I see your point of why you might want to make a node get the bulk of the
> traffic if it is the basis for the (single-path) metric computation.
> But if a node really is doing load balancing, he is "not being honest" by
> sending the bulk of the traffic to one parent anyways, regardless of whether
> you call it a "preferred parent." ;)
>
>
> As an aside, I'd like to point out that although this mailing list and the
> drafts have been discussing mostly single-path metrics, there may be
> multi-path / mesh metrics developed for RPL in the future.  What I mean by a
> multi-path/mesh metric is a metric assigned to a node that takes into
> account all the paths through its parents.  These aren't so common in the
> literature, so I'll take an example of what I've worked with. Suppose you
> want to define a metric that measures reliability, i.e. end-to-end packet
> delivery probability, when you have a mesh of paths from a source to a sink.
>  Such a metric should reflect the fact that routing to a parent with many
> equally good paths to the sink is better than routing to a parent that has
> one good path to the sink.
>
> delivery probability assuming that a node will try to forward packets on its
> outgoing links with equal probability, and calculates the probability that a
> packet reaches the sink assuming all links are independent and stay up or
> down (does not switch between the two) during the entire duration of the
> packet transmission.
>