--- 1/draft-ietf-roll-of0-16.txt 2011-08-26 11:16:52.000000000 +0200 +++ 2/draft-ietf-roll-of0-17.txt 2011-08-26 11:16:52.000000000 +0200 @@ -1,55 +1,58 @@ ROLL P. Thubert, Ed. Internet-Draft Cisco Systems -Intended status: Standards Track August 22, 2011 -Expires: February 23, 2012 +Intended status: Standards Track August 26, 2011 +Expires: February 27, 2012 RPL Objective Function Zero - draft-ietf-roll-of0-16 + draft-ietf-roll-of0-17 Abstract The Routing Protocol for Low Power and Lossy Networks (RPL) specification defines a generic Distance Vector protocol that is adapted to a variety of networks types by the application of specific - Objective Functions. An Objective Function defines how a RPL node - selects and optimizes routes within a RPL Instance based on the - information objects available. This document specifies a basic - Objective Function that relies only on the objects that are defined - in RPL and does not use any extension. + Objective Functions (OFs). An OF states the outcome of the process + used by a RPL node to select and optimize routes within a RPL + Instance based on the information objects available; an OF is not an + algorithm. + + This document specifies a basic Objective Function that relies only + on the objects that are defined in RPL and does not use any protocol + extension 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]. + "SHOULD", "SHOULD NOT", "RECOMMENDED", "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 February 23, 2012. + This Internet-Draft will expire on February 27, 2012. 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 (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 @@ -56,104 +59,115 @@ 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 Zero Overview . . . . . . . . . . . . . . . 4 4. OF0 Operations . . . . . . . . . . . . . . . . . . . . . . . . 5 4.1. Computing Rank . . . . . . . . . . . . . . . . . . . . . . 5 - 4.2. Feasible Successors Selection . . . . . . . . . . . . . . 7 + 4.2. Parent Selection . . . . . . . . . . . . . . . . . . . . . 7 4.2.1. Selection Of The Preferred Parent . . . . . . . . . . 7 4.2.2. Selection Of The Backup Feasible Successor . . . . . . 8 - 5. Abstract Interface to OF0 . . . . . . . . . . . . . . . . . . 8 + 5. Abstract Interface to OF0 . . . . . . . . . . . . . . . . . . 9 6. OF0 Operands . . . . . . . . . . . . . . . . . . . . . . . . . 9 6.1. Variables . . . . . . . . . . . . . . . . . . . . . . . . 9 - 6.2. Configurable Parameters . . . . . . . . . . . . . . . . . 9 + 6.2. Configurable Parameters . . . . . . . . . . . . . . . . . 10 6.3. Constants . . . . . . . . . . . . . . . . . . . . . . . . 10 7. Manageability Considerations . . . . . . . . . . . . . . . . . 10 - 7.1. Device Configuration . . . . . . . . . . . . . . . . . . . 10 + 7.1. Device Configuration . . . . . . . . . . . . . . . . . . . 11 7.2. Device Monitoring . . . . . . . . . . . . . . . . . . . . 11 - 8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 11 + 8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 12 9. Security Considerations . . . . . . . . . . . . . . . . . . . 12 10. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 12 - 11. References . . . . . . . . . . . . . . . . . . . . . . . . . . 12 - 11.1. Normative References . . . . . . . . . . . . . . . . . . . 12 + 11. References . . . . . . . . . . . . . . . . . . . . . . . . . . 13 + 11.1. Normative References . . . . . . . . . . . . . . . . . . . 13 11.2. Informative References . . . . . . . . . . . . . . . . . . 13 - Author's Address . . . . . . . . . . . . . . . . . . . . . . . . . 13 + Author's Address . . . . . . . . . . . . . . . . . . . . . . . . . 14 1. Introduction - The Routing Protocol for LLN (RPL) [I-D.ietf-roll-rpl] specification - defines a generic Distance Vector protocol that is adapted to a - variety of Low Power and Lossy Networks (LLN) types by the - application of specific Objective Functions. An Objective Function - defines how a RPL node selects and optimizes routes within a RPL - Instance based on the information objects available. This separation - of Objective Functions from the core protocol specification allows - RPL to be adapted to meet the different optimization criteria - required by the wide range of deployments, applications and network - designs. + The Routing Protocol for Low Power and Lossy Networks (RPL) + [I-D.ietf-roll-rpl]specification defines a generic Distance Vector + protocol that is adapted to a variety of Low Power and Lossy Networks + (LLN) types by the application of specific Objective Functions (OFs). + + An OF states the outcome of the process used by a RPL node to select + and optimize routes within a RPL Instance based on the information + objects available; an OF is not an algorithm. For example, "shortest + path first" is an algorithm where the least cost path between two + points is derived as an outcome; there are a number of algorithms + that can be used to satisfy the OF, of which the well-known Dijkstra + algorithm is an example. + + The separation of OFs from the core protocol specification allows RPL + to be adapted to meet the different optimization criteria required by + the wide range of deployments, applications, and network designs. RPL forms Directed Acyclic Graphs (DAGs) as collections of Destination Oriented DAGs (DODAGs) within instances of the protocol. Each instance is associated with a specialized Objective Function. A DODAG is periodically reconstructed as a new DODAG Version to enable a global reoptimization of the graph. An instance of RPL running on a device uses an Objective Function to - help it determine which DODAG Version it should join. The OF is also - used by the RPL instance to select a number of routers within the - DODAG Version to serve as parents or as feasible successors. + help it determine which DODAG and which Version of that DODAG it + should join. The OF is also used by the RPL instance to select a + number of routers within the DODAG current and subsequent Versions to + serve as parents or as feasible successors. The RPL instance uses the OF to compute a Rank for the device. This value represents an abstract distance to the root of the DODAG within the DODAG Version. The Rank is exchanged between nodes using RPL and allows other RPL nodes to avoid loops and verify forward progression toward the destination, as specified in [I-D.ietf-roll-rpl]. - Regardless of the particular OF used by a node, Rank will always - increase and thus, post convergence, loop free paths are always - formed. The Objective Function Zero (OF0) operates on parameters that are obtained from provisioning, the RPL DODAG Configuration option and the RPL DIO base container [I-D.ietf-roll-rpl]. - The Rank of a node is obtained by adding a normalized scalar, - rank_increase (Section 6.1), to the Rank of a selected preferred - parent. The rank_increase can vary with a ratio from 1 (excellent) - to 9 (worst acceptable) to represent the link properties. By + The Rank of a node is obtained by adding a stricly positive, + indirectly normalized scalar, rank_increase (Section 6.1), to the + Rank of a selected preferred parent. The rank_increase is based on a + step_of_rank (Section 6.1) normalized scalar that can vary with a + ratio from 1 (excellent) to 9 (worst acceptable) to represent the + link properties. The step_of_rank can be multiplied by a + configurable factor called rank_factor (Section 6.2) that amplifies + the rank_increase to reflect the relative preferences between + different link types that would be used in a same RPL instance. The + rank_increase can be further adapted as detailed in Section 4.1. By default, OF0 encodes the 2-octet Rank in units of 256, and the default settings allow to encode a minimum of 28 (worst acceptable) hops and a maximum of 255 (excellent) hops. - The RPL specification [I-D.ietf-roll-rpl] requires the use of a - common OF by all nodes in a network. The possible use of multiple - OFs with a single network is for further study. - - The RPL specification [I-D.ietf-roll-rpl] does not include any OF - definitions. This is left for other documents specific to different - deployments and application environments. 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. + It is important that devices deployed in a particular network or + environment use the same OF to build and operate DODAGs. If they do + not, it is likely that sub-optimal paths will be selected. In + practice, without a common definition of an OF, RPL implementations + cannot guarantee to interoperate correctly. The RPL specification + [I-D.ietf-roll-rpl] does not include any OF definitions. This is + left for other documents specific to different deployments and + application environments. 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 as a default OF that will allow interoperation between implementations in a wide spectrum of use cases. This is why OF0 does not specify how the link properties are transformed into a rank_increase and leaves that responsibility to the 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. + rather, OF0 enforces the values for the rank_increase by normalizing + the step_of_rank for a normal link and its acceptable range, as + opposed to formulating the details of the step_of_rank computation. + This is also why OF0 ignores metric containers. 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 @@ -164,24 +178,28 @@ The RPL specification describes constraints on how nodes select potential parents, called a parent set, from their neighbors. All parents are feasible successors for upward 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. The Goal of the OF0 is for a node to join a DODAG Version that offers good enough connectivity to a specific set of nodes or to a larger routing infrastructure though there is no guarantee that the path - will be optimized according to a specific metric. Thus, for the - purpose of OF0, the term Grounded [I-D.ietf-roll-rpl] means that the - DODAG root provides such connectivity. How that connectivity is - asserted and maintained is out of scope. + will be optimized according to a specific metric. This validation + process for the connectivity is implementation and link type + dependent, and is out of scope. The validation involves but is not + limited to application of [I-D.ietf-roll-rpl] sections 3.2.3 and 13 + as appropriate, and may involve deployment specific policies as well. + Thus, for the purpose of OF0, the term Grounded [I-D.ietf-roll-rpl] + means that the DODAG root provides such connectivity. How that + connectivity is asserted and maintained is out of scope. Objective Function Zero is designed to find the nearest Grounded root. This can be achieved if the Rank of a node is very close to an abstract function of its distance to the root. This need is balanced with the other need of maintaining some path diversity, which may be achieved by increasing the Rank. In the absence of a Grounded root, inner connectivity within the LLN is still desirable and floating DAGs will form, rooted at the nodes with the highest administrative preference. @@ -232,23 +250,23 @@ An implementation MUST maintain the stretched step_of_rank between the fixed constants MINIMUM_STEP_OF_RANK and MAXIMUM_STEP_OF_RANK (Section 6.3). This range 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 the operator to configure a factor called - rank_factor (Section 6.2) and to apply the factor on all links and - peers to multiply the effect of the stretched step_of_rank in the + implementation SHOULD allow to configure a factor called rank_factor + (Section 6.2) and to apply the factor on all links and peers to + multiply the effect of the stretched step_of_rank in the rank_increase computation as further detailed below. Additionally, an implementation MAY recognize categories of peers and links, such as different link types, in which case it SHOULD be able to configure a more specific rank_factor to those categories. The rank_factor MUST be set between the fixed constants MINIMUM_RANK_FACTOR and MAXIMUM_RANK_FACTOR (Section 6.3) . The variable rank_increase is represented in units expressed by the variable MinHopRankIncrease which defaults to the fixed constant @@ -268,70 +286,66 @@ 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 the 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. Parent Selection 4.2.1. Selection Of The Preferred Parent As it scans all the candidate neighbors, OF0 keeps the parent that is the best for the following criteria (in order): 1. [I-D.ietf-roll-rpl] section 8 spells out the generic rules for a node to re-parent and in particular the boundaries to augment its Rank within a DODAG Version. A candidate that would not satisfy those rules MUST NOT be considered. 2. An implementation 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 - succeeded that validation process is preferable. - - 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. + as preferred.In most cases, a router that does not succeed the + validation process can not be further considered for selection + as preferred parent. In any case a router that succeeded that + validation process SHOULD be preferred. - 4. If the administrative preference of the root is configured to + 3. 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 + 4. A router that offers connectivity to a grounded DODAG Version SHOULD be preferred over one that does not. - 6. A router that offers connectivity to a more preferable root + 5. A router that offers connectivity to a more preferable root SHOULD be preferred. - 7. When comparing 2 parents that belong to the same DODAG, a router + 6. When comparing 2 parents that belong to the same DODAG, a router that offers connectivity to the most recent DODAG Version SHOULD be preferred. - 8. The parent that causes the lesser resulting Rank for this node, + 7. 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 + 8. 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 + 9. The preferred parent that was in use already SHOULD be preferred. - 11. A router that has announced a DIO message more recently SHOULD + 10. A router that has announced a DIO message more recently SHOULD be preferred. These rules and their order MAY be varied by an implementation according to configured policy. 4.2.2. Selection Of The Backup Feasible Successor When selecting a backup feasible successor, the OF performs in order the following checks: @@ -449,41 +463,46 @@ rank_factor that applies to all links. Additionally, the implementation may allow to group interfaces, links and/or neighbors and configure a more specific rank_factor to such groups. An implementation MAY allow to configure a maximum stretch_of_rank as discussed in Section 4.1. If none is configured, a value of 0 is assumed and the step_of_rank is not stretched. An OF0 implementation SHOULD support the DODAG Configuration option as specified in section 6.7.6 of [I-D.ietf-roll-rpl] and apply the - parameters contained therein. When the option is used, the - parameters are configured to the nodes that may become DODAG roots, - and the nodes are configured to redistribute the information using - the DODAG Configuration option. In particular, the value of + parameters contained therein. As discussed in section 16 of + [I-D.ietf-roll-rpl], this requirement might be overridden by further + guidance for certain application scenarios. When the option is used, + the parameters are configured to the nodes that may become DODAG + roots, and the nodes are configured to redistribute the information + using the DODAG Configuration option. In particular, the value of MinHopRankIncrease can be distributed with that option and override the fixed constant of DEFAULT_MIN_HOP_RANK_INCREASE that is defined section 17 of [I-D.ietf-roll-rpl] with a fixed value of 256. - At build-time, the default constant values should be used, that is: + Out of the box, that is at initial factory time, the default constant + values SHOULD be used, that is: the rank_factor is set to the fixed constant DEFAULT_RANK_FACTOR (Section 6.3). the maximum stretch_of_rank is set to the fixed constant DEFAULT_RANK_STRETCH (Section 6.3). the MinHopRankIncrease is set to the fixed constant DEFAULT_MIN_HOP_RANK_INCREASE ([I-D.ietf-roll-rpl]). The values can be overridden at anytime and apply at the next Version - of the DODAG. + of the DODAG. As discussed in section 16 of [I-D.ietf-roll-rpl], + this requirement might be overridden by further guidance for certain + application scenarios. 7.2. Device Monitoring As discussed in Section 5, the OF support must be able to provide information about its operations, and trigger events when that information changes. At a minimum, the information should include: DAG information as specified in Section 6.3.1 of [I-D.ietf-roll-rpl], and including the DODAGID, the RPLInstanceID, the Mode of Operation, the Rank of this node, the current Version