Subject: [Roll] RPL spec v6 and OF0 draft v1: Identifying what needs to be specified in an Objective Function

From: Phoebus Chen <[email-masked]>
Date: Mon, 08 Mar 2010 17:52:45 +0100

Hello RPL and OF0 authors,

	I've been looking over draft-ietf-roll-of0-01 and 
draft-gnawali-roll-etxof-00 to help get a sense of which items left to 
be "specified by the implementation / implementation-dependent" in 
draft-ietf-roll-rpl-06 are to be specified by the objective function. 
My understanding is that of0 will eventually serve as a template for how 
future objective function specifications should be written (together 
with Section 10 of draft-ietf-roll-rpl-06, which will indicate what MUST 
be specified by an OF).

OF0 currently is tasked to specify:
1) selection of parents and siblings
2) how to compute the rank

I suggest that some sections be added, maybe as placeholders for now, to 
specify:
1) The format/fields of the Objective Code Point, following the OCP 
object format from the ROLL routing metrics document 
(draft-ietf-roll-routing-metrics-04, pg. 24, Sec. 6, Fig. 19).  This is 
especially important because it indicates what parameters of the 
Objective Function are left for tuning.  For instance, it is hard to 
spot the optional preference in (draft-ietf-roll-of0-01, pg. 5, Sec. 
3.2, point #8).

2) The rules for how a node decides to "defer" joining or migrating to a 
new DODAG iteration.  I believe this has a large impact on how well a 
DODAG iteration optimizes a metric.  If this is arbitrary and left up to 
each vendor to implement separately, there is no reason to expect that 
the nodes in the network will cooperate to reach an optimum DODAG.
I'm referring to (draft-ietf-roll-rpl-06, pg. 34, Sec. 5.3.3.4):
"An implementation could defer to migrate for some reasonable amount of 
time, to see if some other neighbors with potentially better metrics but 
higher rank announce themselves."

3) What constitutes a redundant DIO message.  This determines which 
nodes that have joined the DODAG iteration can talk, and thus the set of 
candidate neighbors that a node can choose as a parent.  I'll send a 
follow up email elaborating my thoughts on this.
I'm referring to (draft-ietf-roll-rpl-06, pg. 38, Section 5.3.5.1.1):
"The exact determination of what constitutes a redundant DIO message is
left to an implementation; it could for example include DIOs that
advertise the same rank."

4) How the metric used by this OF may be considered inconsistent, for 
the sake of the Trickle timer.
I'm referring to (draft-ietf-roll-rpl-06, pg. 38, Sec. 5.3.5.1.2):
"A metric communicated in the DIO message is determined to be
inconsistent, as according to a implementation specific path
metric selection engine."

5) The rules for a node to choose which DODAG to join, when it has 
multiple choices within an RPLInstance.  I'm guessing that in most cases 
it is only specified by the DODAGPreference field in the DIO Base 
Option, but the rules should be made explicit for each OF.
I'm referring to (draft-ietf-roll-rpl-06, pg. 33, Sec. 5.3.3.3.)
"If a node has the option to join a more preferred DODAG while still 
meeting other optimization objectives, then the node will generally seek 
to join the more preferred DODAG as determined by the OF."
and also (draft-ietf-roll-rpl-06, pg. 39, Sec. 5.3.6):
"The DODAG selection is implementation and algorithm dependent.  Nodes
SHOULD prefer to join DODAGs for RPLInstanceIDs advertising OCPs and
destinations compatible with their implementation specific
objectives."

6) The rules for how a node decides to jump to another DODAG.  This 
should be related to the value of the node's metric and rank.
I'm referring to (draft-ietf-roll-rpl-06, pg. 34, Sec. 5.3.3.4):
"A node MAY, at any time, choose to join a different DODAG within
a RPL Instance."

7) What triggers the parent selection process.  As I understand, a node 
is allowed to change parents within a DODAG iteration, so long as it 
does not violate any rank constraints.  If the trigger for the parent 
selection process is the same across all OFs, then it should be made 
clear in the RPL core specification (the current wording is ambiguous).
I'm referring to (draft-ietf-roll-rpl-06, pg. 58, Sec. 10):
"The parent selection is triggered each time an event indicates
that a potential next hop information is updated.  This might
happen upon the reception of a DIO message, a timer elapse, or a
trigger indicating that the state of a candidate neighbor has
changed."

I also suggest that (draft-ietf-roll-of0-01, pg. 4, Sec. 3.1) be broken 
up into separate sections:
* the general description of the goal
* a placeholder for how to compute the metric (even if it is irrelevant 
here since there is no metric)
* the rules for computing the rank
* how to use administrative preference

The rules for computing the rank should also include a sentence or a 
subsection on how and when administrative rank is to be used to adjust 
the rank computed from the objective function.  Or it should say that it 
is not used.  The guidelines for writing OFs in (draft-ietf-roll-rpl-06, 
pg. 58, Sec. 10) should say that administrative rank must be addressed 
in an OF specification.
I'm referring to (draft-ietf-roll-rpl-06, pg. 39, Sec. 5.5)
"In some cases it might be beneficial to adjust the rank advertised by
a node beyond that computed by the OF based on some implementation
specific policy and properties of the node."

I'm not sure if it's necessary to have a separate "Advertise the metric" 
section, like in (draft-gnawali-roll-etxof-00, pg. 6, Sec. 3.3), or if 
it can be merged into a section on how to compute the metric.  The way I 
think of OFs, a node decides on a single metric and rank, and that is 
what it is always advertised.  Also, is the propagation of metrics 
different from OF to OF?  Otherwise, change the text in the RPL core 
spec: (draft-ietf-roll-rpl-06, pg. 27, Sec. 5.1.3.4)
"The processing and propagation of the Metric Container is governed by 
implementation specific policy functions."

Another point for consideration is whether the rules for how a node 
decides to lower its rank should be made explicit in a separate section 
from the "Preferred Parent Selection" section.  I'm not sure myself.
I'm referring to (draft-ietf-roll-rpl-06, pg. 34, Sec. 5.3.3.4):
"When a node moves to improve its position,...  Such a movement may 
occur at any time to decrease the rank, as per the calculation indicated 
by the OF."

I didn't understand if there are separate OFs for upwards or downwards 
routing... whether there should be placeholder sections for DAO rank, 
DAO metrics, etc.  I suppose this has yet to be decided.

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

P.S.

There are some mechanisms in the RPL specification marked as 
"implementation-dependent" that may not belong in an objective function. 
  Some of these are mentioned in (draft-ietf-roll-rpl-06, Sec. 11 and 
12).  I see these sections as also serving the purpose of helping an 
implementer keep track of what he needs to tune (and what he may have 
implemented differently from other implementers, if their 
implementations turn out to be incompatible or interact in unpredictable 
ways).  I've tried to list some of the "implementation-dependent" 
mechanisms mentioned in the document that were missed in Sections 11 and 
12.  It might also help the reader to separate out what can be tuned 
over the network via messages (besides the ones defined thus far) and 
what is only tuned on the devices before deployment.

Poisoning Interval
(draft-ietf-roll-rpl-06, pg. 14, Sec. 3.4.2)
"Such a move may be undertaken after waiting an appropriate poisoning 
interval, and should allow the node to restore connectivity to the DODAG 
Iteration, if at all possible."

Selection of the candidate neighbors (indirectly mentioned in Sec. 12.3.1)
(draft-ietf-roll-rpl-06, pg. 30, Sec. 5.3.2)
"The exact policies for selecting neighbors and parents is 
implementation-dependent."

Whether to forward packets to future parents
(draft-ietf-roll-rpl-06, pg. 32, Sec. 5.3.3.1)
"During transition to a new DODAG Iteration, a node may decide to
forward packets via 'future parents' that belong to the same DODAG
(same RPLInstanceID and DODAGID), but are observed to advertise a
more recent (incremented) DODAGSequenceNumber."

Whether to poison a sub-DAG before increasing rank and moving, or form a 
floating DODAG
(draft-ietf-roll-rpl-06, pg. 34, Sec. 5.3.3.4)
"If a node needs to move down a DODAG that it is attached to, causing 
the rank to increase, then it MAY poison its routes and delay before
moving as described in Section 5.3.3.5."
(draft-ietf-roll-rpl-06, pg. 35, Sec. 5.3.3.5)
"An implementation may choose to employ this poisoning mechanism when
a node loses all of its current parents, i.e. the set of DODAG
parents becomes depleted, and it can not jump to an alternate DODAG.
An alternate mechanism is to form a floating DODAG."

Risk Window
(draft-ietf-roll-rpl-06, pg. 40, Sec. 5.6)
"It left to the implementation to define the duration of the risk window."

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Tue, 9 Mar 2010 19:15:40 +0100

Hi Phoebus,

These are all good points. Too many fore a single thread, and probably
some to be taken as tickets to attract a better WG attention.
In short, what is the separation between OF and RPL, should we specify
an abstract interface, and what's left to implementation.

Please see below

> draft-gnawali-roll-etxof-00 to help get a sense of which items left to
be
> "specified by the implementation / implementation-dependent" in
with
> Section 10 of draft-ietf-roll-rpl-06, which will indicate what MUST be
specified
> by an OF).

Correct, at least as far as I understand it.

> 1) The format/fields of the Objective Code Point, following the OCP
object
> format from the ROLL routing metrics document
(draft-ietf-roll-routing-
> metrics-04, pg. 24, Sec. 6, Fig. 19).  This is especially important
because it
> indicates what parameters of the Objective Function are left for
tuning.  For
> instance, it is hard to spot the optional preference in
(draft-ietf-roll-of0-01,
> pg. 5, Sec.

The preference is in the DIO base format. My expectation is that the OF
gets the DIOs to play with.
I see that I need to align the OF text with the RPL text. Will do in
next revision.

"     DODAGPreference (Prf):  A 3-bit unsigned integer that defines
               how preferable the root of this DODAG is compared to
               other DODAG roots within the instance.  DAGPreference
               ranges from 0x00 (least preferred) to 0x07 (most
               preferred).  The default is 0 (least preferred).
               Section 5.3 describes how DAGPreference affects DIO
               processing.
"

> 2) The rules for how a node decides to "defer" joining or migrating to
a new
> DODAG iteration.  I believe this has a large impact on how well a
DODAG
> iteration optimizes a metric.  If this is arbitrary and left up to
each vendor to
> implement separately, there is no reason to expect that the nodes in
the
> network will cooperate to reach an optimum DODAG.

Yes, I think we need a ticket for this one, to discuss when to actually
jump. Thomas Clausen and I just discussed that same question a few days
ago.

> 3) What constitutes a redundant DIO message.  This determines which
nodes
> that have joined the DODAG iteration can talk, and thus the set of
candidate
> neighbors that a node can choose as a parent.  I'll send a follow up
email
> elaborating my thoughts on this.
advertise
> the same rank."

If you ask me, you'll get one answer.  You've seen from Richard's answer
that there is no easy one.
For reference, my answer is what's really redundant is the role of
router, so we could use trickle to elect routers upon new sequences.
See from http://www.ietf.org/mail-archive/web/roll/current/msg02573.html

Then again, I am not sure that the RPL spec has the full and correct
answer and that deserves a ticket to see what the group thinks.

> 4) How the metric used by this OF may be considered inconsistent, for
the
> sake of the Trickle timer.
> inconsistent, as according to a implementation specific path metric
selection
> engine."

Probably the same ticket as above...

> 5) The rules for a node to choose which DODAG to join, when it has
multiple
> choices within an RPLInstance.  I'm guessing that in most cases it is
only
> specified by the DODAGPreference field in the DIO Base Option, but the
> rules should be made explicit for each OF.
> I'm referring to (draft-ietf-roll-rpl-06, pg. 33, Sec. 5.3.3.3.) "If a
node has the
> option to join a more preferred DODAG while still meeting other
optimization
> objectives, then the node will generally seek to join the more
preferred
> DODAG as determined by the OF."

I'm not sure what more you need here? Once a node joins an instance that
runs a give OF, the OF is responsible to decide the movements within the
DAG for that instance. I hope that OF0 does that clearly, if not, we
need to work out improvements. I do not see what's missing in the base
spec here?

objectives."

Maybe we should just remove this text? What I think is that there is a
need to join a default instance (0) in order to get more info on the
environment (like discuss to some management entity) and from there,
join more instances as appropriate. All this is out of scope, but the
mandate to support an instance 0 with OF 0 could be added. What do you
think?

> 6) The rules for how a node decides to jump to another DODAG.  This
should
> be related to the value of the node's metric and rank.
> "A node MAY, at any time, choose to join a different DODAG within a
RPL
> Instance."

Some OF might be 'sticky' for instance if the root is a collection
point. Others might just optimize the metrics and the preference.
There must be logic that ties the whole thing in, and that logic is the
core of the OF.

> 7) What triggers the parent selection process.  As I understand, a
node is
> allowed to change parents within a DODAG iteration, so long as it does
not
> violate any rank constraints.  If the trigger for the parent selection
process is
> the same across all OFs, then it should be made clear in the RPL core
> specification (the current wording is ambiguous).
> "The parent selection is triggered each time an event indicates that a
> potential next hop information is updated.  This might happen upon the
> reception of a DIO message, a timer elapse, or a trigger indicating
that the
> state of a candidate neighbor has changed."
> I also suggest that (draft-ietf-roll-of0-01, pg. 4, Sec. 3.1) be
broken up into
> separate sections:
> * a placeholder for how to compute the metric (even if it is
irrelevant here
> since there is no metric)

OF0 is an example for sure, but the spec is not THE schema that all OFs
should follow, though.

> subsection on how and when administrative rank is to be used to adjust
the
> rank computed from the objective function.  Or it should say that it
is not
> used.  The guidelines for writing OFs in (draft-ietf-roll-rpl-06, pg.
58, Sec. 10)
> should say that administrative rank must be addressed in an OF
specification.
> I'm referring to (draft-ietf-roll-rpl-06, pg. 39, Sec. 5.5) "In some
cases it might
> be beneficial to adjust the rank advertised by a node beyond that
computed
> by the OF based on some implementation specific policy and properties
of
> the node."

Good point. I'm not sure whether OF0 has anything special there though.
Maybe a ticket against OF0 wold be appropriate.

> section, like in (draft-gnawali-roll-etxof-00, pg. 6, Sec. 3.3), or if
it can be
> merged into a section on how to compute the metric.  The way I think
of OFs,
> a node decides on a single metric and rank, and that is what it is
always
> advertised.  Also, is the propagation of metrics different from OF to
OF?
> Otherwise, change the text in the RPL core
> spec: (draft-ietf-roll-rpl-06, pg. 27, Sec. 5.1.3.4) "The processing
and
> propagation of the Metric Container is governed by implementation
specific
> policy functions."

Hum, could you reword that? Do you really mean single? The logic in the
OF enables to tie policies with multiple metrics and other
administrative and non-administrative information. The metrics
propagation belongs to the metrics draft, not the OF.

> Another point for consideration is whether the rules for how a node
decides
> to lower its rank should be made explicit in a separate section from
the
> "Preferred Parent Selection" section.  I'm not sure myself.
occur
> at any time to decrease the rank, as per the calculation indicated by
the OF."
> routing... whether there should be placeholder sections for DAO rank,
DAO
> metrics, etc.  I suppose this has yet to be decided.

Routing downwards happen along a DAG that is decided by the OF. The OF
might be selecting a parent as DAO parent for metrics that indicate a
good down path rather than a good up path. So ultimately, you could
think of an OF as being split in 2, one up, one down, as you figured.
You could even have a different set of parents for up and down routes. 

Still at the moment, we form a single DAG, not a DAG for UP routes and a
DAG for down routes, which seemed overly complex.  So there's a single
Rank as opposed to an up Rank and a down Rank. And all the DAOs will
circulate along the reverse DAG. So we do not need DAO metrics to avoid
loops, the loops are already avoided by the DAG construction. DAO
metrics can still be useful to select a shorter path within the loopless
DAG, allow a better load balancing, etc... and they are are described in
Section 5.1.3.4. I see that as an optimization that might or might not
be very useful, depending on the DAG. It is certainly useless if DAOs
only follow a tree of preferred DAO parents.

Thanks for all  your very pertinent comments,

Pascal

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

---

From: Phoebus Chen <[email-masked]>
Date: Wed, 10 Mar 2010 15:29:44 +0100

Hi Pascal,

Yes, I'd love to see the WG address some of these issues in detail. 
Please see my comments below.

>                 Section 5.3 describes how DAGPreference affects DIO

Oh, I see.  Yes, a reference to the DODAGPreference field in the RPL 
document would help here.

> need to work out improvements. I do not see what's missing in the base

I did not mean that the base spec (draft-ietf-roll-rpl-06) needed to be 
revised.  I was suggesting that you create a new section within OF0 to 
address how it uses the DODAGPreference field to choose between 
different DODAGs.  Now that I understand (draft-ietf-roll-of0-01, pg. 5, 
Sec. 3.2, point #8) was for DODAGPreference, I see that you can just 
break out point #8 into its own section.  I think this makes it easy for 
the reader, to separate choosing a preferred parent within a DODAG from 
choosing which DODAG to join, although the two are interrelated.

> mandate to support an instance 0 with OF 0 could be added. What do you

I thought that the leaf node functionality described in 
(draft-ietf-roll-rpl-07, pg. 39-40, Sec. 5.4) was for management 
purposes.  Maybe it's not sufficient.  Let me outline what I see as 
possible concerns.

1) The RPLInstances that have been installed might not be good for 
management.  For instance, if the installed RPLInstances had OFs that 
did not account for reliability, many of the management packets might be 
lost.  Or maybe the latencies for the installed RPLInstances are too 
large for a management user interface (humans managing the nodes would 
get impatient waiting for a response).

2) If there are multiple RPLInstances, nodes may join different 
RPLInstances as leaf nodes, expecting to be managed.  This can create a 
slight headache for the network operator (or network management 
software), who now has to use more than one RPLInstance to manage all 
the nodes in his network.
A counterargument to this is that there might be deployments where you 
need to use different RPLInstances to manage different sets of nodes 
anyways.  The (weak) example I have is with path diversity in a DODAG 
without siblings... with a single DODAG, there might be some nodes that 
help other nodes forward packets but do not have many nodes that would 
help them forward packets (there is at least one node besides the sink 
in every DODAG that has no one else forwarding packets for him).  A 
second RPLInstance can be built to provide path diversity for these nodes.

Here is what I see as possible solutions besides a mandate to support 
instance 0 with OF 0:

1) Maybe designating instance 0 as the "management instance" that all 
nodes must join, even if it is not associated with OF0, is good enough. 
  Since nodes can always join as leaves, they don't have to understand 
the OF.  A network operator might have a better OF than OF0 for managing 
his deployment and for his network traffic.  If this is the case, he can 
save memory on the nodes by not having them maintain another RPLInstance.

2) Overload the use of the DODAGPreference (or create another 
RPLPreference field), to let the network operator specify which 
RPLInstance the nodes should try to join if the nodes cannot join all 
the available RPLInstances in the network because of memory constraints. 
  The management RPLInstance would advertise the highest preference.

Hopefully there is only one network operator managing the network... I'm 
not sure how you would resolve conflicts if multiple network operators 
tried to manage the network.

> OF0 is an example for sure, but the spec is not THE schema that all OFs

OK.  I thought it would be nice to use OF0 as THE schema, putting "Not 
Applicable" in sections as appropriate.  It allows the readers to 
compare OF's really quickly, to see what is there and what is missing.

> propagation belongs to the metrics draft, not the OF.

I was wrong.  I was thinking single metric because oftentimes, to choose 
between parents, one compares a scalar value (maybe a weighted 
combination of several metrics) computed for one node with the scalar 
value computed for another node.  But you're right, there is no 
limitation that a node only sends a single metric and a single rank in 
its DIO advertisements.

I see, "propagation of the metric container" refers to whether it is 
global or local (only one hop).  I got mixed up by the words 
"implementation specific policy functions," thinking this was something 
addressed in the OF documents.  In this case, I guess an "advertise the 
metric" section is necessary to explain what metrics to mark as local 
and what metrics to mark as global (and if it is recorded, aggregated, 
etc.).

> only follow a tree of preferred DAO parents.

Thanks for the clarification.  I'll have to read over RPL v7 and digest 
what is going on with Downwards routing.