[Roll] Few comments on OF0 before publication request

[JP Vasseur <[e-mail]>]

Hi Pascal,

Here they are:

ROLL                                                     P. Thubert, Ed.
Internet-Draft                                             Cisco Systems
Intended status: Standards Track                             May 5, 2011
Expires: November 6, 2011


                        RPL Objective Function 0
                         draft-ietf-roll-of0-11

Abstract

   The Routing Protocol for Low Power and Lossy Networks (RPL) defines a
   generic 
JP> Remove "generic"
Distance Vector protocol that is adapted to such networks.
JP> s/such networks/Low power and Lossy Networks (LLNs)
   RPL requires a specific Objective Function to establish a desired
   routing topology.  This document specifies a basic Objective Function
   that relies only on RPL's basic Protocol Data Units
JP> What do you mean by "protocol data units" ?
; it does not use
   extensions such as RPL metric containers.
JP> it does not require the use of routing metrics

Requirements Language

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

Status of this Memo

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

   Internet-Drafts are working documents of the Internet Engineering
   Task Force (IETF).  Note that other groups may also distribute
   working documents as Internet-Drafts.  The list of current Internet-
   Drafts is at http://datatracker.ietf.org/drafts/current/.

   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."

   This Internet-Draft will expire on November 6, 2011.

Copyright Notice

   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



Thubert                 Expires November 6, 2011                [Page 1]

Internet-Draft             draft-ietf-roll-of0                  May 2011


   (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 Simplified BSD License.


Table of Contents

   1.  Introduction . . . . . . . . . . . . . . . . . . . . . . . . .  3
   2.  Terminology  . . . . . . . . . . . . . . . . . . . . . . . . .  4
   3.  Objective Function 0 Overview  . . . . . . . . . . . . . . . .  4
   4.  OF0 operations . . . . . . . . . . . . . . . . . . . . . . . .  5
     4.1.  Computing Rank . . . . . . . . . . . . . . . . . . . . . .  5
     4.2.  Feasible successors selection  . . . . . . . . . . . . . .  6
       4.2.1.  Selection of the Preferred Parent  . . . . . . . . . .  6
       4.2.2.  Selection of the backup feasible successor . . . . . .  7
   5.  Abstract Interface with RPL core . . . . . . . . . . . . . . .  8
   6.  OF0 Operands . . . . . . . . . . . . . . . . . . . . . . . . .  8
     6.1.  Variables  . . . . . . . . . . . . . . . . . . . . . . . .  8
     6.2.  Configurable parameters  . . . . . . . . . . . . . . . . .  8
     6.3.  Constants  . . . . . . . . . . . . . . . . . . . . . . . .  9
   7.  IANA Considerations  . . . . . . . . . . . . . . . . . . . . .  9
   8.  Security Considerations  . . . . . . . . . . . . . . . . . . .  9
   9.  Acknowledgements . . . . . . . . . . . . . . . . . . . . . . .  9
   10. References . . . . . . . . . . . . . . . . . . . . . . . . . . 10
     10.1. Normative References . . . . . . . . . . . . . . . . . . . 10
     10.2. Informative References . . . . . . . . . . . . . . . . . . 10
   Author's Address . . . . . . . . . . . . . . . . . . . . . . . . . 10




















Thubert                 Expires November 6, 2011                [Page 2]

Internet-Draft             draft-ietf-roll-of0                  May 2011


1.  Introduction

   The Routing Protocol for Low Power and Lossy Networks
   [I-D.ietf-roll-rpl] was designed as a generic core 
JP> s/generic core/modular distance vector routing protocol
that is agnostic
   to metrics 
JP>s/agnostic to metrics/that may not may not require the use of 
routing metrics.
and that is adapted to a given problem using Objective
   Functions (OF).  This separation of Objective Functions from the core
   protocol specification allows RPL to adapt to meet the different
   optimization criteria required by the wide range of use cases.

   RPL forms Destination Oriented Directed Acyclic Graphs (DODAGs)
   within instances of the protocol.  Each instance is associated with a
   specialized Objective Function.  A DODAG is periodically
   reconstructed in a new Version to enable a global reoptimization of
   the graph.

   An Objective Function selects the DODAG Version that a device joins
   within an instance, and a number of neighbor routers within that
   DODAG Version as parents or feasible successors.  The OF generates
   the Rank of the device, that represents an abstract distance to the
   root within the DODAG.  In turn, the Rank is used by the generic RPL
   core 
JP> avoid using the term "core" ... 
to enable a degree of loop avoidance and verify forward
   progression towards a destination, as specified in
   [I-D.ietf-roll-rpl].

   The Objective Function 0 (OF0) corresponds to the Objective Code
   Point 0 (OCP0). 
JP> Code point can be defined later.
 OF0 only requires the information in the RPL DIO
   base container, such as Rank and the DODAGPreference field that
   describes an administrative preference [I-D.ietf-roll-rpl].  The Rank
   of a node is obtained by adding a normalized scalar, rank_increase,
   to the Rank of a selected preferred parent.  OF0 uses a unit
   MinHopRankIncrease of rank_increase of 0x100 so that Rank value can
   be stored in one octet.  This allows up to at least 28 hops even when
   default settings are used and each hop has the worst rank_increase of
   9.
JP> Clear for RPL designer but ... please elaborate on the last two sentences.
   Since there is no default OF or metric container in the RPL main
   specification, it might happen that, unless two given implementations
   follow the same guidance for a specific problem or environment, those
   implementations will not support a common OF with which they could
   interoperate.  OF0 is designed to be common to all implementations
   that are not specifically designed to apply to a given case for which
   further guidance is provided.  
JP> Confusing wording ... IMO you can remove the last sentence
This is why it is very abstract 
JP> Very abstract?
as to
   how the link properties are transformed into a rank_increase and
   leaves that responsibility to implementation; rather, OF0 enforces
   normalized values for the rank_increase of a normal link and its
   acceptable range, as opposed to formulating the details of its
   computation.  This is also why OF0 ignores metric containers.




Thubert                 Expires November 6, 2011                [Page 3]

Internet-Draft             draft-ietf-roll-of0                  May 2011


2.  Terminology

   The terminology used in this document is consistent with and
   incorporates that described in `Terminology in Low power And Lossy
   Networks' [I-D.ietf-roll-terminology] and [I-D.ietf-roll-rpl].

   The term feasible successor is used to refer to a neighbor that can
   possibly be used as a next-hop for upwards traffic following the loop
   avoidance and forwarding rules that the nodes implements and that are
   defined outside of this specification, in particular in the RPL
   specification.

JP> s/defined outside of this specification, in particular in the RPL
   specification./defined in [I-D.ietf-roll-rpl]
3.  Objective Function 0 Overview

   The core RPL specification describes constraints on how nodes select
   potential parents, called a parent set, from their neighbors.  All
   parents are feasible successors for upgoing traffic (towards the
   root).  Additionally, RPL allows the use of parents in a subsequent
   Version of a same DODAG as feasible successors, in which case this
   node acts as a leaf in the subsequent DODAG Version.  Further
   specifications might extend the set of feasible successors, for
   instance to nodes of a same Rank, aka siblings.
JP> Remove previous sentence, out of the scope.

   The Goal 
JP> s/Goal/objective
of the OF0 is for a node to join a DODAG Version that offers
   connectivity to a specific set of nodes or to a larger routing
   infrastructure.  
JP> Add "with no attempt to optimize the path according to a specific
routing metric"
For the purpose of OF0, Grounded thus means that the
   root provides such connectivity.  How that connectivity is asserted
   and maintained is out of scope.

   Objective Function 0 is designed to find the nearest Grounded root.
   This can be achieved if the Rank of a node represents closely 
JP> closely ?
its
   distance to the root.  This need is balanced with the other need of
   maintaining some path diversity.  
JP> what do you mean by "balanced with the other need of maintaining
some path diversity" ?
In the absence of a Grounded root,
   LLN inner connectivity is still desirable and floating DAGs will
   form, rooted at the nodes with the highest administrative preference.

   OF0 selects a preferred parent and a backup feasible successor if one
   is available.  All the upward traffic is normally routed via the
   preferred parent.  When the link conditions do not let an upward
   packet through the preferred parent, the packet is passed to the
   backup feasible successor.
JP> Add "there is no attempt to perform load balancing"


   OF0 assigns a step_of_rank to each link to another node that it
   monitors.  The exact method for computing the step_of_rank 
JP> Indicate where is "step_of_rank" defined
is
   implementation-dependent.





Thubert                 Expires November 6, 2011                [Page 4]

Internet-Draft             draft-ietf-roll-of0                  May 2011


4.  OF0 operations

4.1.  Computing Rank

   One trivial 
JP> remove "trivial"
OF0 implementation might compute the step_of_rank from as
   a classical administrative cost that is assigned to the link.  Using
   a metric similar to hop count implies that the OF0 implementation
   only considers neighbors with good enough connectivity, for instance
   neighbors that are reachable over an Ethernet link, or a WIFI link in
   infrastructure mode.
JP> Not necesarily ... furthermore, why are you referring to Ethernet/Wifi links?

   In most wireless networks
JP> s/in most wireless networks/in most LLNs
, a Rank that is analogous to an unweighted
   hop count favors paths with long distance links 
JP> Long distance links ?
and poor connectivity
   properties.  Other link properties such as the expected transmission
   count metric (ETX) [DeCouto03] should be used 
JP> should be used for what ?
instead to compute the
   step_of_rank.  For instance, the Minimum Rank Objective Function with
   Hysteresis [I-D.ietf-roll-minrank-hysteresis-of] provides guidance on
   how link cost can be computed and on how hysteresis can improve Rank
   stability.

   An implementation MAY allow to stretch the step_of_rank with a
   stretch_of_rank 
JP> refer to the section where this is defined
up to no more than MAXIMUM_RANK_STRETCH in order to
   enable the selection of a feasible successor and maintain path
   diversity.  
JP> you do no explain the implication on path diversity?
The use of a stretch_of_rank augments the apparent
   distance from the node to the root and distorts the DODAG; it should
   be used with care so as to avoid instabilities due to greedy
   behaviours.
JP> paragraph above too cryptic ... 

   The step_of_rank is expressed in units of MINIMUM_STEP_OF_RANK.  As a
   result, the least significant octet in the RPL Rank is not used.  The
   default step_of_rank is DEFAULT_STEP_OF_RANK for each hop.  An
   implementation MUST maintain the stretched step_of_rank between
   MINIMUM_STEP_OF_RANK and MAXIMUM_STEP_OF_RANK, which allows to
   reflect a large variation of link quality.

   The gap between MINIMUM_STEP_OF_RANK and MAXIMUM_RANK_STRETCH may not
   be sufficient in every case to strongly distinguish links of
   different types or categories in order to favor, say, powered over
   battery-operated or wired over wireless, within a same DAG.

   An implementation SHOULD allow a configurable factor called Rank-
   factor and to apply the factor on all links and peers.
JP> Factor used where and how ?
   An implementation MAY recognizes sub-categories of peers and links,
   such as different MAC types, in which case it SHOULD be able to
   configure a more specific Rank-factor to those categories.  The Rank-
   factor SHOULD be set between MINIMUM_RANK_FACTOR and
   MAXIMUM_RANK_FACTOR.



Thubert                 Expires November 6, 2011                [Page 5]

Internet-Draft             draft-ietf-roll-of0                  May 2011


   The step_of_rank Sp that is computed for that link is multiplied by
   the Rank-factor Rf and then possibly stretched by a stretch_of_rank
   Sr. The resulting rank_increase Ri is added to the Rank of preferred
   parent R(P) to obtain that of this node R(N):

   R(N) = R(P) + Ri where Ri = (Rf*Sp + Sr) * MinHopRankIncrease
JP> Add a short example in appendix for clarity

   Optionally, the administrative preference of a root MAY be configured
   to supersede the goal to join a Grounded DODAG.  In that case, nodes
   will associate to the root with the highest preference available,
   regardless of whether that root is Grounded or not.  Compared to a
   deployment with a multitude of Grounded roots that would result in a
   same multitude of DODAGs, such a configuration may result in possibly
   less but larger DODAGs, as many as roots configured with the highest
   priority in the reachable vicinity.

4.2.  Feasible successors selection

4.2.1.  Selection of the Preferred Parent

   As it scans all the candidate neighbors, OF0 performs in order the
   following checks and keeps the parent that is the best for the first
   criterion that makes a difference:

   1.   [I-D.ietf-roll-rpl] spells out the generic rules for a node to
        reparent and in particular the boundaries to augment its Rank
        within a DODAG Version.  
JP> point to the section in RPL core specification
A candidate that would not satisfy
        those rules MUST NOT be considered.

   2.   An implementation should 
JP> should or SHOULD ?
validate a router prior to selecting it
        as preferred.  This validation process is implementation and
        link type dependent, and is out of scope.  A router that has
        been validated is preferable.
JP> You mean "ensure that the link is sufficiently stable" not "Validate
the router"


   3.   When multiple interfaces are available, a policy might be
        locally configured to order them and that policy applies first;
        that is a router on a higher order interface in the policy is
        preferable.

   4.   If the administrative preference of the root is configured to
        supersede the goal to join a Grounded DODAG, a router that
        offers connectivity to a more preferable root SHOULD be
        preferred.

   5.   A router that offers connectivity to a grounded DODAG Version
        SHOULD be preferred over one that does not.





Thubert                 Expires November 6, 2011                [Page 6]

Internet-Draft             draft-ietf-roll-of0                  May 2011


   6.   A router that offers connectivity to a more preferable root
        SHOULD be preferred.

   7.   When comparing 2 routers 
JP> s/2/two
JP>s/routers/parents
that belong to the same DODAG, a router
        that offers connectivity to the freshest DODAG 
JP>freshed => higher Version
Version SHOULD be
        preferred.

   8.   The parent that causes the lesser resulting Rank for this node,
        as specified in Section 4.1, SHOULD be preferred.

   9.   A DODAG Version for which there is an alternate parent SHOULD be
        preferred.  This check is optional.  It is performed by
        computing the backup feasible successor while assuming that the
        router that is currently examined is finally selected as
        preferred parent.

   10.  The preferred parent that was in use already SHOULD be
        preferred.

   11.  A router that has announced a DIO message more recently SHOULD
        be preferred.

4.2.2.  Selection of the backup feasible successor

   When selecting a backup feasible successor, the OF performs in order
   the following checks:

   1.  When multiple interfaces are available, a router on a higher
       order interface is preferable.

   2.  The backup feasible successor MUST NOT be the preferred parent.

   3.  The backup feasible successor MUST be either in the same DODAG
       Version as this node or in an subsequent DODAG Version.

   4.  Along with RPL rules, a Router in the same DODAG Version as this
       node and with a Rank that is higher than the Rank computed for
       this node MUST NOT be selected as a feasible successor.

   5.  A router with a lesser Rank SHOULD be preferred.

   6.  A router that has been validated as usable by an implementation
       dependant validation process SHOULD be preferred.

   7.  The backup feasible successor that was in use already SHOULD be
       preferred.





Thubert                 Expires November 6, 2011                [Page 7]

Internet-Draft             draft-ietf-roll-of0                  May 2011


5.  Abstract Interface with RPL core

   Objective Function 0 interacts with the core RPL in the following
   ways:

   Processing DIO:  This core RPL 
JP> core RPL triggers ??
triggers the OF when a new DIO was
      received.  OF0 analyses the information in the DIO and may select
      the source as a parent or sibling.
JP> Remove sibling

   Providing DAG information:  The OF is called to provide information
      about a given instance.  This includes material from the DIO base
      header, the role (router, leaf), and the Rank of this node.
JP> what are you defining here ?

   Providing a Parent List:  The OF0 support can be required 
JP> required by who ?
to provide
      the ordered list of the parents and feasible successors for a
      given instance to the RPL core.  This includes the material that
      is contained in the transit option for each entry.

   Trigger:  The OF0 support may trigger the RPL core to inform it that
      a change occurred.  This can be used to indicate whether the
      change requires a new DIO to be fired or whether trickle timers
      need to be reset.
JP> Part of this section belong to a manageability section

6.  OF0 Operands

6.1.  Variables

   OF0 uses the following variables:

   step_of_rank (unsigned integer):  an intermediate computation based
      on the link properties with a certain neighbor.

   rank-increase (unsigned integer):  delta between the Rank of the
      preferred parent and self

6.2.  Configurable parameters

   OF0 can use the following optional parameters:

   stretch_of_rank (unsigned integer):  an optional augmentation to the
      step-of-rank of the preferred parent to allow the selection of
      additional parents.

   rank_factor (unsigned integer):  A configurable factor that is used
      to multiply the effect of the link properties in the rank_increase
      computation.




Thubert                 Expires November 6, 2011                [Page 8]

Internet-Draft             draft-ietf-roll-of0                  May 2011


6.3.  Constants

   OF0 fixes the following constants:

   MinHopRankIncrease:  256

   DEFAULT_STEP_OF_RANK:  3

   MINIMUM_STEP_OF_RANK:  1

   MAXIMUM_STEP_OF_RANK:  9

   DEFAULT_RANK_STRETCH:  0

   MAXIMUM_RANK_STRETCH:  5

   DEFAULT_RANK_FACTOR:  1

   MINIMUM_RANK_FACTOR:  1

   MAXIMUM_RANK_FACTOR:  4


7.  IANA Considerations

   This specification requires the assignment of an OCP for OF0.  The
   value of 0 is suggested.


8.  Security Considerations

   Security Considerations for OCP/OF are to be developed in accordance
   with recommendations laid out in, for example,
   [I-D.tsao-roll-security-framework].


9.  Acknowledgements

   Most specific thanks to Philip Levis and Phoebus Chen for their help
   in finalizing this document.

   Many thanks also to Tim Winter, JP Vasseur, Julien Abeille, Mathilde
   Durvy, Teco Boot, Navneet Agarwal and Henning Rogge for in-depth
   review and first hand implementer's feedback.


10.  References




Thubert                 Expires November 6, 2011                [Page 9]

Internet-Draft             draft-ietf-roll-of0                  May 2011


10.1.  Normative References

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

10.2.  Informative References

   [DeCouto03]
              De Couto, Aguayo, Bicket, and Morris, "A High-Throughput
              Path Metric for Multi-Hop Wireless Routing", MobiCom
              '03 The 9th ACM International Conference on Mobile
              Computing and Networking, San Diego, California,, 2003, <h
              ttp://pdos.csail.mit.edu/papers/grid:mobicom03/paper.pdf>.

   [I-D.ietf-roll-minrank-hysteresis-of]
              Gnawali, O. and P. Levis, "The Minimum Rank Objective
              Function with Hysteresis",
              draft-ietf-roll-minrank-hysteresis-of-03 (work in
              progress), May 2011.

   [I-D.ietf-roll-routing-metrics]
              Vasseur, J., Kim, M., Pister, K., Dejean, N., and D.
              Barthel, "Routing Metrics used for Path Calculation in Low
              Power and Lossy Networks",
              draft-ietf-roll-routing-metrics-19 (work in progress),
              March 2011.
JP> Note referenced anywhere in the document.


   [I-D.ietf-roll-rpl]
              Winter, T., Thubert, P., Brandt, A., Clausen, T., Hui, J.,
              Kelsey, R., Levis, P., Pister, K., Struik, R., and J.
              Vasseur, "RPL: IPv6 Routing Protocol for Low power and
              Lossy Networks", draft-ietf-roll-rpl-19 (work in
              progress), March 2011.

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

   [I-D.tsao-roll-security-framework]
              Tsao, T., Alexander, R., Daza, V., and A. Lozano, "A
              Security Framework for Routing over Low Power and Lossy
              Networks", draft-tsao-roll-security-framework-02 (work in
              progress), March 2010.


JP> ID NITS:







Thubert                 Expires November 6, 2011               [Page 10]

Internet-Draft             draft-ietf-roll-of0                  May 2011


Author's Address

   Pascal Thubert (editor)
   Cisco Systems
   Village d'Entreprises Green Side
   400, Avenue de Roumanille
   Batiment T3
   Biot - Sophia Antipolis  06410
   FRANCE

   Phone: [phone]
   Email: [e-mail]







































Thubert                 Expires November 6, 2011               [Page 11]