Subject: Re: [Roll] WG Last Call draft-ietf-roll-minrank-hysteresis-of-02

From: Phoebus Chen <[email-masked]>
Date: Fri, 01 Apr 2011 16:47:08 +0200

JP,

	I suppose draft-ietf-roll-minrank-hysteresis-of-02 will be made 
available online soon?  Or is this a last call regarding 
draft-ietf-roll-minrank-hysteresis-of-01?

Omprakash and Phil,

	I made a pass through draft-ietf-roll-minrank-hysteresis-of-01.

General Comments:
*****************
1) As I understand from Table 1 and the mention of node metrics in the 
second paragraph of the introduction, MRHOF also supports node metrics. 
  However, in various places throughout the document, you refer to the 
"selected metric for the link..." .  I point out where I spot this 
below.  When using node metrics, I presume the node adds it's own node 
metric value to the advertised metric from its candidate neighbor to get 
the path cost?

2) In Section 3, you write "MRHOF cannot be used if the routing 
objective is to maximize the metric."  Those from the optimization 
community may be a little puzzled, because you can just negate the 
objective function to convert it from a maximization problem to a 
minimization problem.

Let's assume you wish to maximizing the product of link probabilities 
along a path.  Then, you can use log(p) which results in only negative 
link metrics (so still monotonic).  And instead of MIN_PATH_COST, you 
start with a MAX_PATH_REWARD of 0 and add the negative link metrics.  I 
don't see any of the MRHOF mechanisms breaking here (with some minor 
tweaks of switching "minimize" to "maximize").  Am I missing something?

As I understand, limiting MRHOF to minimization makes the explanations 
easier and the terminology / constant names more consistent.  But are 
you restricting the scope of the OF too much here?

3) Are the parent selection rules in any way affected by 
minHopRankIncrease, mentioned in (draft-ietf-roll-rpl-19, Section 3.5.2. 
Rank Relationships)?  Should minHopRankIncrease always be set to 1 for 
MRHOF?  In Table 1, you discuss how to convert various metrics into 
rank, but make no mention of minHopRankIncrease. 
(draft-ietf-roll-rpl-19, Section 3.5.1 Rank Comparison (DAGRank()) ) says:

"MinHopRankIncrease is the minimum increase in rank between a node and 
any of its DODAG parents."

As I understand, PARENT_SWITCH_THRESHOLD plays the role of "coarsening" 
the metric, which was originally done by the DAGRank() function for rank 
comparisons.  The way I understand the properties of rank described in 
(draft-ietf-roll-rpl-19, Section 3.5. Rank Properties) and from earlier 
discussions on the mailing list, coarsening the rank is for stability. 
DAGRank() may not do such a good job when two path-cost-to-root's 
advertised by candidate neighbors are less than PARENT_SWITCH_THRESHOLD 
apart but they result in different rank (e.g., DAGRank(A) > DAGRank(B)). 
  This is why we have MRHOF, right?
************

Nits / editorial comments follow below, preceded by "PC>".

Of course, don't forget to update the version numbers of the informative 
references for last call (or is this done after last call?  I never 
remember.).

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

Networking Working Group                                      O. Gnawali
Internet-Draft                                                  P. Levis
Intended status: Standards Track                     Stanford University
Expires: September 1, 2011                             February 28, 2011

The Minimum Rank Objective Function with Hysteresis

draft-ietf-roll-minrank-hysteresis-of-01

Abstract

    Hysteresis delays the effect of changes in link metric on parent
    selection.  Such delay makes the topology stable despite jitters in
    link metrics.  The Routing Protocol for Low Power and Lossy Networks
    (RPL) allows the use of objective functions to construct routes that
    optimize or constrain a routing metric on the paths.  This
    specification describes the Minimum Rank Objective Function with
    Hysteresis (MRHOF), an objective function that minimizes the node
    rank in terms of a given metric, while using hysteresis to prevent
    excessive rank churn.  The use of MRHOF with RPL results in nodes
    selecting stable paths that minimize the given routing metric to the
    roots of a Directed Acyclic Graph (DAG).

Status of this Memo

    This Internet-Draft is submitted to IETF in full conformance with the
    provisions of BCP 78 and BCP 79.

    Internet-Drafts are working documents of the Internet Engineering
    Task Force (IETF), its areas, and its working groups.  Note that
    other groups may also distribute working documents as Internet-
    Drafts.

    Internet-Drafts are draft documents valid for a maximum of six months
    and may be updated, replaced, or obsoleted by other documents at any
    time.  It is inappropriate to use Internet-Drafts as reference
    material or to cite them other than as "work in progress."

    The list of current Internet-Drafts can be accessed at
    http://www.ietf.org/ietf/1id-abstracts.txt.

    The list of Internet-Draft Shadow Directories can be accessed at
    http://www.ietf.org/shadow.html.

    This Internet-Draft will expire on September 1, 2011.

Copyright Notice

Gnawali & Levis         Expires September 1, 2011               [Page 1]

Internet-Draft    draft-ietf-roll-minrank-hysteresis-of    February 2011

    Copyright (c) 2011 IETF Trust and the persons identified as the
    document authors.  All rights reserved.

    This document is subject to BCP 78 and the IETF Trust's Legal
    Provisions Relating to IETF Documents
    (http://trustee.ietf.org/license-info) in effect on the date of
    publication of this document.  Please review these documents
    carefully, as they describe your rights and restrictions with respect
    to this document.  Code Components extracted from this document must
    include Simplified BSD License text as described in Section 4.e of
    the Trust Legal Provisions and are provided without warranty as
    described in the BSD License.

Table of Contents

    1.  Introduction  . . . . . . . . . . . . . . . . . . . . . . . . . 3
    2.  Terminology . . . . . . . . . . . . . . . . . . . . . . . . . . 3
    3.  The Minimum Rank Objective Function with Hysteresis . . . . . . 4
      3.1.  Computing the Path cost . . . . . . . . . . . . . . . . . . 4
      3.2.  Parent Selection  . . . . . . . . . . . . . . . . . . . . . 5
      3.3.  Computing Rank  . . . . . . . . . . . . . . . . . . . . . . 6
      3.4.  Advertising the path cost . . . . . . . . . . . . . . . . . 6
    4.  MRHOF Variables and Parameters  . . . . . . . . . . . . . . . . 7
    5.  Acknowledgements  . . . . . . . . . . . . . . . . . . . . . . . 8
    6.  IANA Considerations . . . . . . . . . . . . . . . . . . . . . . 8
    7.  Security Considerations . . . . . . . . . . . . . . . . . . . . 8
    8.  References  . . . . . . . . . . . . . . . . . . . . . . . . . . 8
      8.1.  Normative References  . . . . . . . . . . . . . . . . . . . 8
      8.2.  Informative References  . . . . . . . . . . . . . . . . . . 8
    Authors' Addresses  . . . . . . . . . . . . . . . . . . . . . . . . 8

Gnawali & Levis         Expires September 1, 2011               [Page 2]

Internet-Draft    draft-ietf-roll-minrank-hysteresis-of    February 2011

1. Introduction

    An objective function allows RPL [I-D.ietf-roll-rpl] to select paths
    that are best in terms of a given routing metric or select paths that
    meet certain constraints in terms of the routing metric.  RPL
    achieves this goal by selecting the parent among the alternate
    parents as dictated by that objective function.  For example, if an
    RPL instance uses an objective function that minimizes hop-count, RPL
    will select paths with minimum hop count.

    The nodes running RPL might use a number of metrics to describe a
    link or a node [I-D.ietf-roll-routing-metrics] and make it available
    for route selection.  A metric can be used by different objective
    functions to optimize or constrain the metric in different ways.

    This specification describes MRHOF, an objective function for RPL.
    MRHOF uses hysteresis while selecting the path with the smallest
    metric value.  The path with the minimum cost has different property

PC> s/has different/has a different/

    depending on the metric used for path selection.  For example, the
    use of MRHOF with the latency metric allows RPL to find stable
    minimum-latency paths from the nodes to a root in the DAG instance.
    The use of MRHOF with the ETX metric allows RPL to find the stable
    minimum-ETX paths from the nodes to a root in the DAG instance.

    MRHOF can be used only with additive metric that must be minimized on

PC> s/can be used only with additive/can only be used with an additive/

    the paths selected for routing.  Although MRHOF can be used with a
    number of metrics, this draft is based on experiences with the ETX

PC> s/a number of metrics/different metrics/

    metric.

2. Terminology

    The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
    "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and
    "OPTIONAL" in this document are to be interpreted as described in RFC
    2119 [RFC2119].

    This terminology used in this document is consistent with the
    terminologies described in [I-D.ietf-roll-terminology],
    [I-D.ietf-roll-rpl], and [I-D.ietf-roll-routing-metrics].

    This document introduces two terms:

    Selected metric:  The metric chosen by the network operator to use
          for path selection.  This metric can be any additive metric
          listed in [I-D.ietf-roll-routing-metrics]

PC> Insert period at end of sentence above.

Gnawali & Levis         Expires September 1, 2011               [Page 3]

Internet-Draft    draft-ietf-roll-minrank-hysteresis-of    February 2011

    Path cost:  Path cost quantifies a property of an end-to-end path.
          Path cost is composed using the selected metric of the links
          along the path.  Path cost can be used by RPL to compare
          different paths.

PC> s/composed using the/obtained by summing up the/

3. The Minimum Rank Objective Function with Hysteresis

    The Minimum Rank Objective Function with Hysteresis, MRHOF, is
    designed to find the paths with the smallest path cost while
    preventing excessive churn in the network.  It does so by switching
    to the minimum cost path only if the path cost of the current path is
    larger than the path cost of the minimum cost path by a given
    threshold.  MRHOF may be used with any additive metric listed in
    [I-D.ietf-roll-routing-metrics] as long the routing objective is to
    minimize the given routing metric.  MRHOF cannot be used if the
    routing objective is to maximize the metric.

3.1. Computing the Path cost

    Nodes compute the path cost for each candidate neighbor reachable on
    all the interfaces.  The Path cost represents the cost of the path,

PC> When I read this sentence literally, it means that a candidate
PC> neighbor must be reachable on ALL the interfaces.  I don't think
PC> that's what you mean.  This is done at various places throughout
PC> the document.  May I suggest:
PC> s/reachable on all the interfaces/that can be reached through an 
interface/

    in terms of the selected metric, from a node to the root of the DODAG
    through the neighbor.

    Root nodes (Grounded or Floating) set the variable cur_min_path_cost
    to MIN_PATH_COST.

    A non-root node computes the path cost for a path to the root through
    each candidate neighbor by adding these two components:

    1.  The selected metric for the link to a candidate neighbor.

    2.  The value of the selected metric in the metric container in the
        DIO sent by that neighbor.

    A node SHOULD compute the path cost for the path through each
    candidate neighbor reachable through all the interfaces.  If a node

PC> Again, "reachable through all the interfaces".  See comment above.

    cannot compute the path cost for the path through a candidate
    neighbor, the node MUST NOT select the candidate neighbor as its
    preferred parent with one exception.  If the node does not have

PC> s/parent with one/parent, with one/

    metrics to compute the path cost through any of the candidate
    neighbors, it SHOULD join one of the candidate neighbors as a leaf
    node.

    If the selected metric of the link to a neighbor is not available,
    the path cost for the path through that neighbor SHOULD be set to
    MAX_PATH_COST.  This cost value will prevent this path from being

Gnawali & Levis         Expires September 1, 2011               [Page 4]

Internet-Draft    draft-ietf-roll-minrank-hysteresis-of    February 2011

    considered for path selection.

    The path cost corresponding to a neighbor SHOULD be re-computed each
    time:

    1.  The selected metric of the link to the candidate neighbor is
        updated.

    2.  A node receives a new metric advertisement from the candidate
        neighbor.

    This computation MAY also be performed periodically.  Deferring the
    path cost computation for too long after new metric advertisements or
    updates to the selected link metric results in nodes making parent
    selection decision based on stale link and path information.

3.2. Parent Selection

    After computing the path cost for all the candidate neighbors
    reachable through all the interfaces for the current DODAG iteration,
    a node selects the preferred parent.  This process is called parent
    selection.  Parent Selection SHOULD be performed each time:

    1.  The path cost for an existing candidate neighbor, including the
        preferred parent, changes.  This condition can be checked
        immediately after the path cost is computed.

    2.  A new candidate neighbor is inserted into the neighbor table.

    The parent selection MAY be deferred until a later time.  Deferring
    the parent selection can delay the use of better paths or stopping

PC> s/stopping/stop/

    the use of worse paths than what is available in the network.

    A node MUST select a candidate neighbor as its preferred parent if
    the path cost corresponding to that neighbor is smaller than the path
    cost corresponding to the rest of the neighbors, except as indicated
    below:

    1.  If the smallest path cost for paths through the candidate
        neighbors is smaller than cur_min_path_cost by less than
        PARENT_SWITCH_THRESHOLD, the node MAY continue to use the current
        preferred parent.

    2.  If there are multiple paths with the smallest path cost and that

PC> remove "that"

        the smallest path cost is smaller than cur_min_path_cost by at
        least PARENT_SWITCH_THRESHOLD, a node MAY use a different
        objective function to select the preferred parent among the
        candidates which are first hop on the path with the minimum cost.

PC> The last phrase is hard to parse, although it is correct.  I'm not
PC> sure how to reword it.

Gnawali & Levis         Expires September 1, 2011               [Page 5]

Internet-Draft    draft-ietf-roll-minrank-hysteresis-of    February 2011

    3.  A node MAY declare itself as a Floating root, and hence no
        preferred parent, depending on the configuration.

    4.  If the selected metric for a link is greater than
        MAX_LINK_METRIC, the node SHOULD exclude that link from
        consideration for parent selection.

    5.  If cur_min_path_cost is greater than MAX_PATH_COST, the node MAY
        declare itself as a Floating root.

    6.  If the configuration disallows a node to be a Floating root and
        no neighbors are discovered, the node does not have a preferred
        parent, and MUST set cur_min_path_cost to MAX_PATH_COST.

    The preferred parent is the only node in the parent set at a given
    time.  Any candidate neighbor may become the preferred parent as
    indicated above.

3.3. Computing Rank

    The DAG roots set their rank to MIN_PATH_COST for the selected
    metric.

    Once a non-root node selects its preferred parent, it can use the
    following table to covert its path cost to the DAG root through its
    preferred parent (written as Cost in the table) to its rank:

                     +--------------------+------------+
                     |  Node/link Metric  |    Rank    |
                     +--------------------+------------+
                     |     Node Energy    | 255 - Cost |
                     |      Hop-Count     |    Cost    |
                     |       Latency      | Cost/65536 |
                     | Link Quality Level |    Cost    |
                     |         ETX        |    Cost    |
                     +--------------------+------------+

                   Table 1: Conversion of metric to rank.

    Node rank is undefined for these node/link metrics: Node state and
    attributes, throughput, and link color.

3.4. Advertising the path cost

    Once the preferred parent is selected, the node sets its
    cur_min_path_cost variable to the path cost corresponding to the
    preferred parent.  Thus, cur_min_path_cost is the cost of the minimum
    cost path from the node to the root.  The value of the

Gnawali & Levis         Expires September 1, 2011               [Page 6]

Internet-Draft    draft-ietf-roll-minrank-hysteresis-of    February 2011

    cur_min_path_cost is carried in the metric container whenever DIO
    messages are sent.

4. MRHOF Variables and Parameters

    MRHOF uses the following variable:

       cur_min_path_cost: The cost of the path from a node through its
       preferred parent to the root computed at the last parent
       selection.

    MRHOF uses the following parameters:

       MAX_LINK_METRIC: Maximum allowed value for the selected link
       metric for each link on the path.

       MAX_PATH_COST: Maximum allowed value for the path metric of a
       selected path.

       MIN_PATH_COST: The minimum allowed value for the path metric of
       the selected path.

       PARENT_SWITCH_THRESHOLD: The difference between metric of the path
       through the preferred parent and the minimum-metric path to
       trigger new preferred parent selection.

PC> s/to trigger new preferred parent selection/in order to trigger the 
selection of a new preferred parent./

    The parameter values are assigned depending on the selected metric.
    The best values for these parameters should be experimentally
    determined.  The working group has long experience routing with the
    ETX metric.  Based on those experiences, these ETX parameters are
    known to work in many settings:

       MAX_LINK_METRIC: 10.  Disallow links with greater than 10 expected
       transmission count on the selected path.

       MAX_PATH_COST: 100.  Disallow paths with greater than 100 expected
       transmission count.

       MIN_PATH_COST: 0.  At root, the expected transmission count is 0.

       PARENT_SWITCH_THRESHOLD: 1.5.  Switch to a new path only if it is
       expected to require at least 1.5 fewer transmission than the
       current path.

Gnawali & Levis         Expires September 1, 2011               [Page 7]

Internet-Draft    draft-ietf-roll-minrank-hysteresis-of    February 2011

5. Acknowledgements

    Thanks to Antonio Grilo, Nicolas Tsiftes, Matteo Paris, JP Vasseur
    for their comments.

6. IANA Considerations

    This specification requires an allocated OCP.  A value of 1 is
    requested.

7. Security Considerations

    Security considerations to be developed in accordance to the output
    of the WG.

8. References

8.1. Normative References

    [RFC2119]  Bradner, S., "Key words for use in RFCs to Indicate
               Requirement Levels", BCP 14, RFC 2119, March 1997.

8.2. Informative References

    [I-D.ietf-roll-routing-metrics]
               Vasseur, J. and D. Networks, "Routing Metrics used for
               Path Calculation in Low Power and Lossy Networks",
               draft-ietf-roll-routing-metrics-01 (work in progress),
               October 2009.

    [I-D.ietf-roll-rpl]
               Winter, T., Thubert, P., and R. Team, "RPL: IPv6 Routing
               Protocol for Low power and Lossy Networks",
               draft-ietf-roll-rpl-05 (work in progress), December 2009.

    [I-D.ietf-roll-terminology]
               Vasseur, J., "Terminology in Low power And Lossy
               Networks", draft-ietf-roll-terminology-01 (work in
               progress), May 2009.

Gnawali & Levis         Expires September 1, 2011               [Page 8]

Internet-Draft    draft-ietf-roll-minrank-hysteresis-of    February 2011

Authors' Addresses

    Omprakash Gnawali
    Stanford University
    S255 Clark Center, 318 Campus Drive
    Stanford, CA  94305
    USA

    Phone: +1 650 725 6086
    Email: [email-masked]

    Philip Levis
    Stanford University
    358 Gates Hall, Stanford University
    Stanford, CA  94305
    USA

    Email: [email-masked]

Gnawali & Levis         Expires September 1, 2011               [Page 9]

Html markup produced by rfcmarkup 1.92, available from 
http://tools.ietf.org/tools/rfcmarkup/

On 4/1/11 6:13 AM, JP Vasseur wrote:
> Dear all,
>
> draft-ietf-roll-minrank-hysteresis-of has been discussed for quite some time,
> the document is stable and is now ready for Working Group Last Call. As discussed
> during the WG meeting yesterday, there a very questions to address.
>
> This starts a 2-week WG Last call on draft-ietf-roll-minrank-hysteresis-of-02
> that will end on April 11 at noon ET (this is a bit more than 2 weeks, considering
> most of us flying back end of this week).
>
> Please send your comments to the authors and copy the mailing list.
>
> Thanks.
>
> JP.
> _______________________________________________
> Roll mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/roll

---

From: JP Vasseur <[email-masked]>
Date: Fri, 1 Apr 2011 16:52:17 +0200

Sorry for the typo, this is a WG on the -01 version. Thanks !

JP.

On Apr 1, 2011, at 4:47 PM, Phoebus Chen wrote:

> JP,
> 
> 	I suppose draft-ietf-roll-minrank-hysteresis-of-02 will be made available online soon?  Or is this a last call regarding draft-ietf-roll-minrank-hysteresis-of-01?
> 
> 
> 
> 
> Omprakash and Phil,
> 
> 1) As I understand from Table 1 and the mention of node metrics in the second paragraph of the introduction, MRHOF also supports node metrics.  However, in various places throughout the document, you refer to the "selected metric for the link..." .  I point out where I spot this below.  When using node metrics, I presume the node adds it's own node metric value to the advertised metric from its candidate neighbor to get the path cost?
> 
> 
> 2) In Section 3, you write "MRHOF cannot be used if the routing objective is to maximize the metric."  Those from the optimization community may be a little puzzled, because you can just negate the objective function to convert it from a maximization problem to a minimization problem.
> 
> Let's assume you wish to maximizing the product of link probabilities along a path.  Then, you can use log(p) which results in only negative link metrics (so still monotonic).  And instead of MIN_PATH_COST, you start with a MAX_PATH_REWARD of 0 and add the negative link metrics.  I don't see any of the MRHOF mechanisms breaking here (with some minor tweaks of switching "minimize" to "maximize").  Am I missing something?
> 
> As I understand, limiting MRHOF to minimization makes the explanations easier and the terminology / constant names more consistent.  But are you restricting the scope of the OF too much here?
> 
> 
> 3) Are the parent selection rules in any way affected by minHopRankIncrease, mentioned in (draft-ietf-roll-rpl-19, Section 3.5.2. Rank Relationships)?  Should minHopRankIncrease always be set to 1 for MRHOF?  In Table 1, you discuss how to convert various metrics into rank, but make no mention of minHopRankIncrease. (draft-ietf-roll-rpl-19, Section 3.5.1 Rank Comparison (DAGRank()) ) says:
> 
> "MinHopRankIncrease is the minimum increase in rank between a node and any of its DODAG parents."
> 
> As I understand, PARENT_SWITCH_THRESHOLD plays the role of "coarsening" the metric, which was originally done by the DAGRank() function for rank comparisons.  The way I understand the properties of rank described in (draft-ietf-roll-rpl-19, Section 3.5. Rank Properties) and from earlier discussions on the mailing list, coarsening the rank is for stability. DAGRank() may not do such a good job when two path-cost-to-root's advertised by candidate neighbors are less than PARENT_SWITCH_THRESHOLD apart but they result in different rank (e.g., DAGRank(A) > DAGRank(B)).  This is why we have MRHOF, right?
> ************
> 
> 
> Of course, don't forget to update the version numbers of the informative references for last call (or is this done after last call?  I never remember.).
> 
> 
> -- 
> Phoebus Chen
> Postdoctoral Researcher
> PC> s/reachable on all the interfaces/that can be reached through an interface/
> 
> 
> PC> s/to trigger new preferred parent selection/in order to trigger the selection of a new preferred parent./
> 
> Html markup produced by rfcmarkup 1.92, available from http://tools.ietf.org/tools/rfcmarkup/
> 
> 
> 
>

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Fri, 1 Apr 2011 18:13:45 +0200

Hi JP and authors:

Phil and I have worked hard to clarify that OF0 can use link layer
information though it is not propagating it in containers. 

For good reasons, Mr Hof is more specific that OF0 in its behavior and
its use of metrics than OF0 that had to be as generic as possible. 

Yet I think that getting as much commonality as we can is a valuable
goal. This starts with the ranges that are similar but not identical.

Yes, MrHof uses metrics containers, whereas OF0 does not. But can a Mr
Hof implementation refrain from using containers and connect to an OF0
network? IOW, what  does it take for an MrHof implementation be able to
attach to an OF0 network? What needs to be done - is it a simple tuning,
complete rewrite?

Also I wonder, should a Mr Hof implementation support all the metrics
that are listed? If not, then how does a node know if it can actually
work with the metrics in use in a Mr Hof network?

Cheers,

Pascal
http://www.xtranormal.com/watch/7011357/

> -----Original Message-----
> From: [email-masked] [mailto:[email-masked]] On Behalf
Of JP
> Vasseur
> Sent: Friday, April 01, 2011 6:14 AM
> To: ROLL WG
> Subject: [Roll] WG Last Call draft-ietf-roll-minrank-hysteresis-of-02
> 
> Dear all,
> 
> the document is stable and is now ready for Working Group Last Call.
As
> discussed during the WG meeting yesterday, there a very questions to
> address.
> 
> that will end on April 11 at noon ET (this is a bit more than 2 weeks,
> considering most of us flying back end of this week).
>

---

From: Omprakash Gnawali <[email-masked]>
Date: Sat, 9 Apr 2011 21:40:11 -0700

> draft-ietf-roll-minrank-hysteresis-of-01?

The last call is on -01.

> "selected metric for the link..." .  I point out where I spot this below.
>  When using node metrics, I presume the node adds it's own node metric value
> to the advertised metric from its candidate neighbor to get the path cost?

Yes. Would it be better to say near the top that the discussion uses
the phrase link metric but all the discussions also apply to node
metric or use the phrase link or node metric throughout the text?

> 2) In Section 3, you write "MRHOF cannot be used if the routing objective is
> to maximize the metric."  Those from the optimization community may be a
> little puzzled, because you can just negate the objective function to
> convert it from a maximization problem to a minimization problem.
>
> Let's assume you wish to maximizing the product of link probabilities along
> a path.  Then, you can use log(p) which results in only negative link
> metrics (so still monotonic).  And instead of MIN_PATH_COST, you start with
> a MAX_PATH_REWARD of 0 and add the negative link metrics.  I don't see any
> of the MRHOF mechanisms breaking here (with some minor tweaks of switching
> "minimize" to "maximize").  Am I missing something?
>
> easier and the terminology / constant names more consistent.  But are you
> restricting the scope of the OF too much here?

Yes. Another way way converting maximization to minimization is by
computing a reciprocal of the metric. Would it be adequate to include
a subsection that describes how to convert maximization metric to a
minimization metric so that we can use mrhof? I think the most common
use of mrhof will be with something like etx so I hesitate to make the
draft too general which will make force the implementers of the most
common case to have to read a lot of generalizations.

If we want to use mrhof with maximization metrics by converting them
to minimization, we need to standardize how to do this conversion so
that two mrhof implementations can interoperate. One option is to use
negative metric another is computing a reciprocal. We need to pick
one.

> 3) Are the parent selection rules in any way affected by minHopRankIncrease,
> mentioned in (draft-ietf-roll-rpl-19, Section 3.5.2. Rank Relationships)?
>  Should minHopRankIncrease always be set to 1 for MRHOF?  In Table 1, you
> discuss how to convert various metrics into rank, but make no mention of
> minHopRankIncrease. (draft-ietf-roll-rpl-19, Section 3.5.1 Rank Comparison
> (DAGRank()) ) says:
>

Good point. We should put a requirement saying RPL minHopRankIncrease
should be 1 because depending on the metric, mrhof computes the rank
at the granularity of 1. What is the best section to put such
requirements?

> As I understand, PARENT_SWITCH_THRESHOLD plays the role of "coarsening" the
> metric, which was originally done by the DAGRank() function for rank
> DAGRank() may not do such a good job when two path-cost-to-root's advertised
> by candidate neighbors are less than PARENT_SWITCH_THRESHOLD apart but they
> result in different rank (e.g., DAGRank(A) > DAGRank(B)).  This is why we
> have MRHOF, right?

MRHOF will compute the rank based on the metrics. I believe the rank
you are talking about is more like hop-count Rank?

I processed all your editorial comments.

Thanks for all the comments.

- om_p

---

From: Omprakash Gnawali <[email-masked]>
Date: Sat, 9 Apr 2011 21:53:45 -0700

> attach to an OF0 network? What needs to be done - is it a simple tuning,

We can change mrhof to use the rank advertised by of0 as the
advertised path cost if there is no metric container. Then the network
with mrhof can compute additive metric based on that base cost. of0
would have no difficulty using the rank computed by mrhof. So, with
that little tweak above, we can make mrhof and of0 networks
interoperate. The interoperation, however, will not be ideal. If there
are multiple connection points between a mrhof and an of0 networks,
the metric minimization algorithm will compute the lowest ranks
assuming homogeneous metric because downstream nodes in a mrhof
network don't know what fraction of the path cost is due to rank from
of0.

> work with the metrics in use in a Mr Hof network?

I have this text for now:

"   Node rank is undefined for these node/link metrics: Node state and
   attributes, throughput, and link color."

We can set the rank to max rank in case of  unsupported metrics?

- om_p

---

From: Omprakash Gnawali <[email-masked]>
Date: Sun, 10 Apr 2011 05:05:36 -0700

Regarding parent set - I am planning to suggest a parent set of size
3. It will be a SHOULD because this might not be too big in a very
sparse network. Please send your comments.

- om_p

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Mon, 11 Apr 2011 12:04:59 +0200

Hi Om:

> > network? IOW, what  does it take for an MrHof implementation be able
> > to attach to an OF0 network? What needs to be done - is it a simple
> > tuning, complete rewrite?
> 
> We can change mrhof to use the rank advertised by of0 as the advertised
> path cost if there is no metric container. Then the network with mrhof can

[Pascal] Yes.
 I think that when there is no metric container, Mr Hof should operate within the OF0 frame, and then:
- explain that by default F(ETX) of the link is used for step-of-rank. 
- describe F()
- add the hysteresis logic
- ...

Which means that we need to agree of the constants in OF0 section 7. Right now:

- OF0 has a  MAXIMUM_STEP_OF_RANK of 9 while  Mr Hof has  MAX_LINK_METRIC of  10

- OF0 allows up to 28 hops even when default settings are  used and each hop has the worst Rank-increase of 9, while MrHof has only 10 hops (MAX_PATH_METRIC: 100). Note that this comes from Phil's comment that 16 was not enough.

- Mr Hof does not have a  MINIMUM_STEP_OF_RANK

- Mr Hof does not have a  Rank Factor 

I think you should align all these constants to OF0 and point onto OF0 for their definitions. I can still change MAXIMUM_STEP_OF_RANK to 10 in OF0 if that's important for your use cases.

> compute additive metric based on that base cost. of0 would have no
> difficulty using the rank computed by mrhof. So, with that little tweak above,
> we can make mrhof and of0 networks interoperate. The interoperation,

[Pascal] It is not about interoperation between a Mr Hof DAG and an OF0 DAG. Right now we do not really try to do that.
It is about the fact that an implementation of Mr Hof can claim compliance to OF0, which is a MUST in RPL.  As opposed to having to implement 2different OFs.

> however, will not be ideal. If there are multiple connection points between a
> mrhof and an of0 networks, the metric minimization algorithm will compute
> the lowest ranks assuming homogeneous metric because downstream
> nodes in a mrhof network don't know what fraction of the path cost is due to
> rank from of0.

[Pascal] Agreed. Things work better when the metrics are passed in containers.

> We can set the rank to max rank in case of  unsupported metrics?

[Pascal] No I think that you need to
- MUST support certain metric  containers (give the list)
- MAY/SHOULD others to hint an implementation that they are considered useful to support
- MUST not switch containers in flight. Root decides, routers propagate the same containers with updated metrics, leaves are free to ignore
- MUST act as a leaf when not supporting the container that's decided by the root

: )

[Pascal]

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Mon, 11 Apr 2011 12:24:24 +0200

Parent set size and STRETCH of Rank are antagonistic goals.

OF0 started with the conservative approach to allow a stretch only to
get a sibling, but did not allow a node A to stop being a potential next
hop for a node B by stretching below that node B. Which is in essence
the greediness problem. This goes along the general recommendation in
RPL section 14.

Phil convinced me that we need OF0 to be more generic and allow a
stretch. But then the implementation has to be very careful to make sure
that when A stretches its rank, it does not cause B to be deprived of a
(its 3rd in your case) parent. It's the same problem as the
MaxRankIncrease in RPL. It is fine for A to go down to attach to B if B
is not in A's subdag, but harmful and source of Count to Infinity if B
is in A's subdag. 

Trouble is that A does not know. The STRETCH of Rank and the
MaxRankIncrease are both mechanism to control how deep the CTI goes; but
it is still a bad idea when it happens and we allow deployments to turn
it off.

In any case you probably have to choose between making a number of
parent a desirable goal for the OF, and allow stretch. Otherwise you're
prone to see domino effects. 

To judge that I'll need to see how you word the equivalent of OF 0
section 4/5. Right now it is a bit unclear to me: do you inherit them
from OF0, if not what's the delta?

Cheers,

Pascal

> From: Omprakash Gnawali [mailto:[email-masked]]
> Sent: Sunday, April 10, 2011 2:06 PM
> To: Pascal Thubert (pthubert)
> Cc: JP Vasseur; ROLL WG
> Subject: Re: [Roll] WG Last Call
draft-ietf-roll-minrank-hysteresis-of-02
> Regarding parent set - I am planning to suggest a parent set of size
3. It will
> be a SHOULD because this might not be too big in a very sparse
network.
> Please send your comments.
> 
> - om_p

---

From: Phoebus Chen <[email-masked]>
Date: Mon, 11 Apr 2011 12:27:37 +0200

Omprakash,

	Responses are inline below.

On 4/10/11 6:40 AM, Omprakash Gnawali wrote:
> On Fri, Apr 1, 2011 at 7:47 AM, Phoebus Chen<[email-masked]>  wrote:
>> JP,
>>

I think either approach is fine (if you choose the latter, you may also 
use "link (node)" if you think "link or node" is too much text).

On related note, I'm wondering if it's necessary to emphasize in the 
introduction that a node adds its own node metric to the aggregate 
before checking for parent selection (basically, emphasize that the 
steps in the subsections of section 3 MUST be followed in that order). 
Just for consistency amongst the nodes if they come from different 
vendors.  An implementor might think it doesn't matter since the 
addition of the node's own metric doesn't change the parent selection. 
What do you think?

> negative metric another is computing a reciprocal. We need to pick

Yes, I think your suggestion about writing a subsection describing how 
to convert the maximization metric to a minimization metric is the best 
approach, rather what I had written above.  Maybe you can mention that 
the key point for determining whether you can convert the maximization 
problem to a minimization problem that MRHOF can handle is that there is 
a known, fixed bound on the optimum that is the value taken on by the 
root (corresponding to MIN_PATH_COST), and the additive link (node) 
costs are all the same sign (negative in the maximization problem, 
positive in the minimization problem).

I would certainly prefer negating the metric.  Taking the reciprocal of 
the entire path metric is more complicated to describe (you are 
advertising the denominator in the DIO messages so you don't have round 
off / quantization errors, and then you take the reciprocal for 
comparisons for parent selection).

If by taking the reciprocal you mean the reciprocal of each individual 
link (node) metric, this would rescale the metrics and yield a different 
topology when you try to maximize the path metric.  I'm sure you know 
this already, but for the others following this thread on the mailing 
list: just look at building a tree that minimizes ETX vs. a tree that 
maximizes path probability (ex. root = A, probability of links BA = 0.9, 
CB = 0.9, CA = 0.5; ETX will have path CA, path probability will have 
path CBA).

> at the granularity of 1. What is the best section to put such

Hmm, I can't see a nice way to add it to the intro paragraph of Section 
3 as it is written now.  I would mention it both in Section 3.2 and 3.3. 
  It really belongs in Section 3.3, but the reader first needs to 
consider this in 3.2.  In Section 3.2, maybe just a sentence that we 
assume that minHopRankIncrease = 1, so the considerations in 
draft-ietf-roll-rpl-19, Section 3.5.1 do not impose additional 
constraints on the parent selection rules.

>> result in different rank (e.g., DAGRank(A)>  DAGRank(B)).  This is why we
>> have MRHOF, right?
>

No, I was just pointing out that maybe the rules in 
(draft-ietf-roll-rpl-19, Section 3.5. Rank Properties) are redundant 
given the PARENT_SWITCH_THRESHOLD in MRHOF.  In any case, if we set 
minHopRankIncrease = 1, we won't be applying two sets of rules to 
achieve the same effect of coarsening the metric.

> Thanks for all the comments.

Sure!  Thanks for incorporating them.

---

From: JP Vasseur <[email-masked]>
Date: Mon, 11 Apr 2011 18:00:06 +0200

Hi,

WG Last Call on draft-ietf-roll-minrank-hysteresis-of-01 is now over. 
Several comments were made during the WG Last Call. Authors, could you
please update the document, post the new revision and send a email to the
lists summarizing the changes and making sure that all comments have been
addressed ?

Thanks.

JP.

---

From: Phoebus Chen <[email-masked]>
Date: Mon, 11 Apr 2011 20:38:17 +0200

Omprakash,

	I just realized when writing my last email to Pascal that maybe it 
would necessary to specify the messages for configuring the parameters 
Section 4, MRHOF Variables and Parameters?  I presume it can be 
configured from the root.

	Also, depending on Pascal's response to my last email, maybe it would 
be nice to also have an "Interface with RPL core" section in MRHOF. 
Unless you both decide there is no need for that section.  Following the 
format in (Section 6, draft-ietf-roll-of0-10), maybe you also need a 
"Provide Metrics" interface?

(my last email was for version 9 of OF0, before I noticed version 10 was 
posted, but I think these comments still apply).

---

From: Omprakash Gnawali <[email-masked]>
Date: Thu, 14 Apr 2011 16:30:17 -0700

> - add the hysteresis logic

I need one clarification - did we decide that OF0 is the default OF?
At some point, you had mentioned that "0" in OF0 does not imply
default OF. In that case, I am not sure how MRHOF can assume it can
operate within the OF0 frame when there is no metric container. I am
trying to understand if "no metric container" case is different from
"no of0" case.

> I think you should align all these constants to OF0 and point onto OF0 for their definitions. I can still change MAXIMUM_STEP_OF_RANK to 10 in OF0 if that's important for your use cases.

I think it is the metrics used (called selected metric in the draft)
that dictate these constants so it is hard to say what should be the
minimum step or the maximum step for MRHOF in general. The values you
cite are given as examples (not as default or standard values) for one
specific metric (ETX). I am hesitant to prescribe these constants
because I have no idea if these constants work with the other metrics
listed on the draft.

> It is about the fact that an implementation of Mr Hof can claim compliance to OF0, which is a MUST in RPL.  As opposed to having to implement 2different OFs.

Maybe the text describes the scope of this compliance requirement,
which you state as a MUST. Can you please point me to the text?

> - MUST support certain metric  containers (give the list)

I don't see a reason why we should require routing decisions based on
specific metrics. Some platforms will have one metric, some will have
another. The routing decisions are made on some subset of metrics
available on those platforms.

> - MAY/SHOULD others to hint an implementation that they are considered useful to support

It is hard to make that recommendation without knowing more about what
are all the metrics available on that platform.

> - MUST not switch containers in flight. Root decides, routers propagate the same containers with updated metrics, leaves are free to ignore

There is a sentence: "The value of the cur_min_path_cost is carried in
the metric container whenever ..."

I can change that to: "The value of the cur_min_path_cost is carried
in the metric container corresponding to the selected metric
whenever..."

> - MUST act as a leaf when not supporting the container that's decided by the root

We have this text right now:

"If the node does not have
   metrics to compute the path cost through any of the candidate
   neighbors, it SHOULD join one of the candidate neighbors as a leaf
   node."

We can change that to a MUST.

- om_p

---

From: Omprakash Gnawali <[email-masked]>
Date: Thu, 14 Apr 2011 16:45:16 -0700

> from OF0, if not what's the delta?

I plan to say:

- PARENT_SET_SIZE number of next hops
- Advertise the rank corresponding to the worst path in the set
- Suggest a value of 3 for PARENT_SET_SIZE for ETX metric
- If the rank corresponding to the best and the worst path in the set
differ by a large amount (what is large depends on the metric so hard
to have a constant), consider using a smaller PARENT_SET_SIZE

- om_p

---

From: Omprakash Gnawali <[email-masked]>
Date: Thu, 14 Apr 2011 16:58:02 -0700

On Mon, Apr 11, 2011 at 3:27 AM, Phoebus Chen <[email-masked]> wrote:
....
> introduction that a node adds its own node metric to the aggregate before
> checking for parent selection (basically, emphasize that the steps in the
> subsections of section 3 MUST be followed in that order). Just for
> consistency amongst the nodes if they come from different vendors.  An
> implementor might think it doesn't matter since the addition of the node's
> own metric doesn't change the parent selection. What do you think?

Yes, the current description adds the unnecessary dependency between
those steps. I will remove that dependency.

>>> convert it from a maximization problem to a minimization problem.
...
> Yes, I think your suggestion about writing a subsection describing how to
> convert the maximization metric to a minimization metric is the best
> approach, rather what I had written above.  Maybe you can mention that the
> key point for determining whether you can convert the maximization problem
> to a minimization problem that MRHOF can handle is that there is a known,
> fixed bound on the optimum that is the value taken on by the root
> (corresponding to MIN_PATH_COST), and the additive link (node) costs are all
> the same sign (negative in the maximization problem, positive in the
> minimization problem).
>
> I would certainly prefer negating the metric.  Taking the reciprocal of the
> entire path metric is more complicated to describe (you are advertising the
> denominator in the DIO messages so you don't have round off / quantization
> errors, and then you take the reciprocal for comparisons for parent
> selection).

I will suggest this approach in the new subsection on using mrhof with
maximization metrics.

- om_p

---

From: Omprakash Gnawali <[email-masked]>
Date: Thu, 14 Apr 2011 17:00:18 -0700

On Mon, Apr 11, 2011 at 11:38 AM, Phoebus Chen <[email-masked]> wrote:
> Section 4, MRHOF Variables and Parameters?  I presume it can be configured
> from the root.

Lets make sure we use consistent messaging for of0 and mrhof if we
decide to list those configuration messages.

> be nice to also have an "Interface with RPL core" section in MRHOF. Unless
> you both decide there is no need for that section.  Following the format in
> (Section 6, draft-ietf-roll-of0-10), maybe you also need a "Provide Metrics"
> interface?
>

We need a consistent place to list MinHopRankIncrease at least.

- om_p

---

From: JP Vasseur <[email-masked]>
Date: Fri, 15 Apr 2011 08:33:25 +0200

> trying to understand if "no metric container" case is different from

OF0 is not the default OF but just one OF among others. RPL implementation do
not have to support OF0 if they do not need to.

---

From: JP Vasseur <[email-masked]>
Date: Fri, 15 Apr 2011 09:07:52 +0200

>> Section 4, MRHOF Variables and Parameters?  I presume it can be configured

They all can be configured from the root.

> decide to list those configuration messages.

VERY good point ! Thanks.

---

From: Phoebus Chen <[email-masked]>
Date: Fri, 15 Apr 2011 10:45:50 +0200

On 4/15/11 1:58 AM, Omprakash Gnawali wrote:
> On Mon, Apr 11, 2011 at 3:27 AM, Phoebus Chen<[email-masked]>  wrote:
> ....

I should have worded my comment above more very carefully, because I 
think you misunderstood what I meant.  I was in *favor* of specifying 
that the order of the steps in section 3 MUST be followed.  Just in case 
the nodes from one of the vendors decides (for node metrics) to do 
parent selection on the advertised metric, while the nodes from another 
vendor decides to do parent selection on the advertised metric + its own 
node metric.  In that sense, the dependency of the steps, which I 
interpret as following the steps in the same order, is necessary.

Anyhow, my question to you was whether the order of the steps were 
emphasized enough, or whether we should emphasize the steps more explicitly.

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Fri, 15 Apr 2011 11:04:06 +0200

> OF0 is not the default OF but just one OF among others. RPL
implementation
> do not have to support OF0 if they do not need to.

[Pascal] I agree that default is not the right wording.

RPL now says:

"
   If further guidance is not available then a RPL Router implementation
   MUST at least support the metric-less OF0 [I-D.ietf-roll-of0].
"

Which means that OF0 has the special role of least common denominator
for generic implementations. This is why it has to be quite abstract and
container-less. That comes from an IESG DISCUSS by Jari. 

I'm advocating that an Mr Hof implementation should be usable as an OF0
so that same implementation can be used outside of the limited scope
where "further guidance" is given that does not require OF0.

Unless operation with no metric container is not doable with Mr Hof?

Pascal

---

From: JP Vasseur <[email-masked]>
Date: Fri, 15 Apr 2011 11:10:10 +0200

> container-less. That comes from an IESG DISCUSS by Jari. 

Just to make sure that there is no ambiguity this does not mean that implementations 
must at least support OF0. You can have a network with all nodes only supporting MrHof
or other OF

> Unless operation with no metric container is not doable with Mr Hof?

Let's make things simple ... we have OF0 and Mrhof so far. An implementation may choose
to support one or the other.

---

From: Matteo Paris <[email-masked]>
Date: Fri, 15 Apr 2011 10:30:31 -0400

Hi Omprakash,

>to have a constant), consider using a smaller PARENT_SET_SIZE

Computing rank as the worst path cost in the parent set is a natural 
thing to try, but it creates a problem (originally pointed out to me 
by Joseph Reddy).  Suppose A is the root (rank 1) and B joins but has 
a poor link to A, say link cost 9, giving it a rank of 10.  Now 
suppose C joins and has good links (cost 1) to both A and B.  It 
places them both in its parent set and advertises a rank of 11.  This 
prevents B from finding the good route through C, which it would have 
found had C joined first.

Your final bullet point could remedy this problem, but it seems 
reversed.  It would be more straightforward to compute the rank as 
the best path in the parent set, plus a RANK_FUZZ factor which 
depends on the metric.

Matteo

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Fri, 15 Apr 2011 18:07:23 +0200

Hi Matteo:

I agree with you. 

This was the spirit from the start & I'm surprised this keeps on coming
back. Just like the stretch, Computing rank as the worst path cost in
the parent set is a trick that leads the DAG to be less and less true to
the metric to the point that you illustrate. Let's face it, there's no
way in a DAG that all nodes have 2 parents. People might hide that truth
through complex behaviors and large datasets, but it comes back with a
revenge.

An OF could theoretically play games with metrics from multiple parents,
but in the end, if forwarding is to take place mostly over the preferred
parent, the metrics that the node advertises should be true to that.

Cheers,

Pascal

> From: Matteo Paris [mailto:[email-masked]]
> Sent: Friday, April 15, 2011 4:31 PM
> To: Omprakash Gnawali; Pascal Thubert (pthubert)
> Cc: ROLL WG
> Computing rank as the worst path cost in the parent set is a natural
thing to
> try, but it creates a problem (originally pointed out to me by Joseph
Reddy).
> Suppose A is the root (rank 1) and B joins but has a poor link to A,
say link cost
> 9, giving it a rank of 10.  Now suppose C joins and has good links
(cost 1) to
> both A and B.  It places them both in its parent set and advertises a
rank of
> 11.  This prevents B from finding the good route through C, which it
would
> have found had C joined first.
> 
reversed.  It
> would be more straightforward to compute the rank as the best path in
the
> parent set, plus a RANK_FUZZ factor which depends on the metric.
> 
> Matteo

---

From: Philip Levis <[email-masked]>
Date: Fri, 15 Apr 2011 10:06:14 -0700

On Apr 15, 2011, at 7:30 AM, Matteo Paris wrote:

> Computing rank as the worst path cost in the parent set is a natural thing to try, but it creates a problem (originally pointed out to me by Joseph Reddy).  Suppose A is the root (rank 1) and B joins but has a poor link to A, say link cost 9, giving it a rank of 10.  Now suppose C joins and has good links (cost 1) to both A and B.  It places them both in its parent set and advertises a rank of 11.  This prevents B from finding the good route through C, which it would have found had C joined first.

Yes, this is correct.

The way that you prevent this is using MaxRankIncrease. If MaxRankIncrease is 0, then if C places both A and B in its parent set it must advertise 11. But C does not have to place B in its parent set: C can have a parent set of just A and advertise a Rank of 2. With a MaxRankIncrease of 0, however, if link CA fails, then C cannot fail over to B until a new version. This is the tradeoff which I think all of these discussions ignore: in order to prevent loops, low MaxRankIncrease values force nodes to trade off between routing flexibility and routing efficiency. There is no free lunch here (well, except datapath validation, which while cheap is not free).

Of course, the simplest solution to this problem is to have a significant MaxRankIncrease. E.g., if MaxRankIncrease is 20, then C can keep B as a neighbor but not a member of the parent set. If link CA fails, then C can fail over to link CB and advertise a Rank of 11.

Phil

---

From: Matteo Paris <[email-masked]>
Date: Fri, 15 Apr 2011 16:03:13 -0400

On Apr 15, 2011, at 7:30 AM, Matteo Paris wrote:
>by Joseph Reddy).  Suppose A is the root (rank 1) and B joins but 
>has a poor link to A, say link cost 9, giving it a rank of 10.  Now 
>places them both in its parent set and advertises a rank of 11. 
>This prevents B from finding the good route through C, which it 
>would have found had C joined first.

At 10:06 AM -0700 4/15/11, Philip Levis wrote:
>
>Yes, this is correct.
>
>The way that you prevent this is using MaxRankIncrease.
>
>If MaxRankIncrease is 0, then if C places both A and B in its parent 
>set it must advertise 11. But C does not have to place B in its 
>parent set: C can have a parent set of just A and advertise a Rank 
>of 2. With a MaxRankIncrease of 0, however, if link CA fails, then C 
>cannot fail over to B until a new version. This is the tradeoff 
>which I think all of these discussions ignore: in order to prevent 
>loops, low MaxRankIncrease values force nodes to trade off between 
>routing flexibility and routing efficiency. There is no free lunch 
>here (well, except datapath validation, which while cheap is not 
>free).
>
>Of course, the simplest solution to this problem is to have a 
>significant MaxRankIncrease. E.g., if MaxRankIncrease is 20, then C 
>can keep B as a neighbor but not a member of the parent set. If link 
>CA fails, then C can fail over to link CB and advertise a Rank of 11.

Hi Phil, what you say about MaxRankIncrease is true, but I don't see 
on how it relates to preventing the problem caused by the parent 
selection strategy above.  You say "C does not have to place B in its 
parent set", but my reading of the bullets above is that C would 
indeed put B in its parent set (PARENT_SET_SIZE is 3) and set its 
rank to 11, regardless of the value of MaxRankIncrease.  It seems 
that we are interpreting the selection strategy differently. 
Omprakash?

Matteo

---

From: Philip Levis <[email-masked]>
Date: Fri, 15 Apr 2011 13:50:13 -0700

On Apr 15, 2011, at 1:03 PM, Matteo Paris wrote:

>> If MaxRankIncrease is 0, then if C places both A and B in its parent set it must advertise 11. But C does not have to place B in its parent set: C can have a parent set of just A and advertise a Rank of 2. With a MaxRankIncrease of 0, however, if link CA fails, then C cannot fail over to B until a new version. This is the tradeoff which I think all of these discussions ignore: in order to prevent loops, low MaxRankIncrease values force nodes to trade off between routing flexibility and routing efficiency. There is no free lunch here (well, except datapath validation, which while cheap is not free).
>> 
> Hi Phil, what you say about MaxRankIncrease is true, but I don't see on how it relates to preventing the problem caused by the parent selection strategy above.  You say "C does not have to place B in its parent set", but my reading of the bullets above is that C would indeed put B in its parent set (PARENT_SET_SIZE is 3) and set its rank to 11, regardless of the value of MaxRankIncrease.  It seems that we are interpreting the selection strategy differently. Omprakash?

I think what we're learning from this is that RPL should have, rather than requiring a node advertise a Rank greater than all elements of its parent set, should have to advertise a rank greater than both the rank of the lowest rank member of the parent set as well as greater than the rank of the highest rank member of the parent set *minus MaxRankIncrease."

The issue here is that a node might have valid potential parents in its neighbor set that it does not want to include in the parent set because of the Rank advertisement they would require. The draft should explain this: perhaps we should cal them "potential parents."

phil

---

From: Omprakash Gnawali <[email-masked]>
Date: Fri, 15 Apr 2011 14:03:29 -0700

> Unless operation with no metric container is not doable with Mr Hof?

Now that we are clear between no of0 and no metric container case, we
can discuss what MRHOF should do when there is no metric container.
Pascal has put in a lot of thought over the last several months on how
to do routing without metric containers so it makes sense to use that
work. I can state in MRHOF draft:

"If there is no metric container, parent selection and rank
computation is done according to the mechanisms mentioned in OF0."

Does that work?

- om_p

---

From: Philip Levis <[email-masked]>
Date: Fri, 15 Apr 2011 17:43:53 -0700

> computation is done according to the mechanisms mentioned in OF0."

I think Rank computation makes sense -- but parent selection is actually quite a bit different. So I would just say Rank computation.

Phil

---

From: Matteo Paris <[email-masked]>
Date: Fri, 15 Apr 2011 21:46:34 -0400

At 1:50 PM -0700 4/15/11, Philip Levis wrote:
>I think what we're learning from this is that RPL should have, 
>rather than requiring a node advertise a Rank greater than all 
>elements of its parent set, should have to advertise a rank greater 
>than both the rank of the lowest rank member of the parent set as 
>well as greater than the rank of the highest rank member of the 
>parent set *minus MaxRankIncrease."

Hi Phil, I'm sorry but I am not following you.  It seems to me that 
with that definition, a node could choose a rank lower than the rank 
of one of its parents.  For example, suppose MaxRankIncrease is 255. 
Then a node could choose to have two parents with ranks 10 and 20, 
but set its own rank to 11.

MaxRankIncrease was introduced to (optionally) shorten the distance 
to infinity, to avoid lengthy counts-to-infinity.  I think your 
concern can be addressed by setting MaxRankIncrease to a sufficiently 
high value.  My concern with Omprakash's most recent parent selection 
proposal is not directly related to MaxRankIncrease.

Matteo

---

From: Richard Kelsey <[email-masked]>
Date: Sat, 16 Apr 2011 06:44:54 -0400

> From: Omprakash Gnawali <[email-masked]>
> Date: Fri, 15 Apr 2011 14:03:29 -0700
>

I would like to be able to use ETX as the rank directly,
without the additional overhead of a metric container.  It
seems silly to send the same value twice, once as the rank
and once wrapped in a metric container.
                                          -Richard

---

From: Omprakash Gnawali <[email-masked]>
Date: Sat, 16 Apr 2011 08:54:39 -0700

> and once wrapped in a metric container.

Sure it is redundant for this particular metric but according to RPL,
OFs are supposed to convert metrics to Rank. MRHOF is written within
that framework.

- om_p

---

From: Philip Levis <[email-masked]>
Date: Sat, 16 Apr 2011 09:54:19 -0700

> and once wrapped in a metric container.

This raises a good question -- would it be preferable for, in the  
absence of a metric container, for MRHOF to calculate Rank as in OF0,  
or to use ETX?

Phil

---

From: Richard Kelsey <[email-masked]>
Date: Sat, 16 Apr 2011 16:55:20 -0400

> Date: Sat, 16 Apr 2011 08:54:39 -0700
> 

I understand that in general the metric and rank are
different values and need to be sent separately.  But when
the conversion to rank is the identity function, it would
be simpler and more efficient to leave off the metric
container.
                                    -Richard

---

From: Richard Kelsey <[email-masked]>
Date: Sat, 16 Apr 2011 18:01:04 -0400

> From: Philip Levis <[email-masked]>
> Date: Sat, 16 Apr 2011 09:54:19 -0700
> 

Would it be possible to allow both?  While many devices may
need to delay the choice of metric or objective function
until RPL is actually running, for many embedded devices
these have to be built in at the factory.

Perhaps the MRHOF document could say that in the absence of
a metric container the default is Rank as in OF0, but that
other options, such as using Rank == ETX, may be configured
out of band.
                                    -Richard

---

From: Philip Levis <[email-masked]>
Date: Sat, 16 Apr 2011 15:06:12 -0700

> other options, such as using Rank == ETX, may be configured

I don't understand -- one could certainly configure a node to use ETX for Rank if there is no metric container provided: OF0 is quite explicit that one could do this. The issue is not what a node uses, but rather what it can assume other nodes use. Or are you suggesting some additional protocol exchange for a node to query another node on how it's computing Rank with OF0? I don't think that's a good idea.

Phil

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Mon, 18 Apr 2011 08:58:00 +0200

I think I agree with Phil here;

Richard, we specifically wanted to allow what you also ask for, that is
that OF0 can use with ETX to compute Rank. But we had to leave some room
for people who'd do it differently, probably for other types of links.
Eg, a wire could use a static cost, wifi infra mode could transform the
current data rate into Rank, etc...

We leave the exact formula for ETX to Rank to the implementation, but we
recommend taking a look at how Mr Hof does it.

In turn, I'd have expected that when Mr Hof does not have a container,
it recommends ETX within the OF0 contraints so that Mr Hof can actually
present itself as an OF0.

I my mind, this means providing a more specific formula for Rank -> ETX,
and obeying the various normalization rules in OF0.

This being said, I still have to answer Phoebus ' long email, and one of
the topics is whether we want a config container. Like Phil below, I
cannot see that container explaining OF0 how to compute Rank, but I can
see a container passing  a default value for the stretch for instance.
We'll see what people think about that.

Pascal

> From: [email-masked] [mailto:[email-masked]] On Behalf
Of
> Philip Levis
> Sent: Sunday, April 17, 2011 12:06 AM
> To: Richard Kelsey
> Cc: [email-masked]
> > Would it be possible to allow both?  While many devices may need to
> > delay the choice of metric or objective function until RPL is
actually
> > running, for many embedded devices these have to be built in at the
> > factory.
> >
> > Perhaps the MRHOF document could say that in the absence of a metric
> > container the default is Rank as in OF0, but that other options,
such
> > as using Rank == ETX, may be configured out of band.
> 
> I don't understand -- one could certainly configure a node to use ETX
for Rank
> if there is no metric container provided: OF0 is quite explicit that
one could
> do this. The issue is not what a node uses, but rather what it can
assume
> other nodes use. Or are you suggesting some additional protocol
exchange
> for a node to query another node on how it's computing Rank with OF0?
I
> don't think that's a good idea.
> 
> Phil
>

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Mon, 18 Apr 2011 10:13:03 +0200

> >
> > I would like to be able to use ETX as the rank directly, without the
> > additional overhead of a metric container.  It seems silly to send
the
> > same value twice, once as the rank and once wrapped in a metric
> > container.
> 
absence of a
> metric container, for MRHOF to calculate Rank as in OF0, or to use
ETX?
[Pascal] OF0 does not calculate Rank.  
Is there something that prevents it an OF0 to use ETX? Rounding error?

Pascal

---

From: Richard Kelsey <[email-masked]>
Date: Mon, 18 Apr 2011 07:03:50 -0400

> Date: Sat, 16 Apr 2011 15:06:12 -0700
> 
> for Rank if there is no metric container provided: OF0 is quite
> explicit that one could do this. The issue is not what a node uses,
> but rather what it can assume other nodes use. Or are you suggesting
> some additional protocol exchange for a node to query another node on
> how it's computing Rank with OF0? I don't think that's a good idea.

What I would like to do is to make sending configuration
information optional, the way RPL security is optional.  For
the kind of systems I work with, small embedded devices that
go into autonomous, multi-vendor networks, the protocols
versions, options and so forth must be determined ahead of
time.  This makes most over-the-air configuration redundant.
In most cases the redundant overhead isn't much, so we do it
anyway.  When using ETX, or in any other case where the
metric value can be derived from the Rank, it would be nice
not to have to send the metric container.

                                      -Richard

---

From: Omprakash Gnawali <[email-masked]>
Date: Tue, 19 Apr 2011 12:33:42 -0700

> not to have to send the metric container.

I am fine with doing routing based on ETX if there are no metric
containers. The way it would work is - you compute the Rank based on
ETX, which is an identity function. Then you just advertise that Rank.
The receiving nodes, in the absence of metric container, can convert
the Rank to ETX, which is an identity function, and compute their path
cost, convert that to Rank and advertise that. This mechanism will
allow simple and efficient implementation for the most likely use
case.

Richard - is this what you had in mind?

- om_p

---

From: Omprakash Gnawali <[email-masked]>
Date: Tue, 19 Apr 2011 19:19:36 -0700

On Tue, Apr 19, 2011 at 6:32 PM, Richard Kelsey
<[email-masked]> wrote:
>> Date: Tue, 19 Apr 2011 12:33:42 -0700
>>
> Yes, that is exactly what I was thinking of.

Perfect. I will update the draft accordingly.

- om_p