idnits 2.17.1 draft-ietf-roll-routing-metrics-15.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- == The page length should not exceed 58 lines per page, but there was 1 longer page, the longest (page 28) being 59 lines Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- No issues found here. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (January 14, 2011) is 4848 days in the past. Is this intentional? Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) == Outdated reference: A later version (-19) exists of draft-ietf-roll-rpl-17 ** Obsolete normative reference: RFC 5226 (Obsoleted by RFC 8126) == Outdated reference: A later version (-13) exists of draft-ietf-roll-terminology-04 Summary: 1 error (**), 0 flaws (~~), 4 warnings (==), 1 comment (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 1 Networking Working Group JP. Vasseur, Ed. 2 Internet-Draft Cisco Systems, Inc 3 Intended status: Standards Track M. Kim, Ed. 4 Expires: July 18, 2011 Corporate Technology Group, KT 5 K. Pister 6 Dust Networks 7 N. Dejean 8 Coronis SAS 9 D. Barthel 10 France Telecom Orange 11 January 14, 2011 13 Routing Metrics used for Path Calculation in Low Power and Lossy 14 Networks 15 draft-ietf-roll-routing-metrics-15 17 Abstract 19 Low power and Lossy Networks (LLNs) have unique characteristics 20 compared with traditional wired and ad-hoc networks that require the 21 specification of new routing metrics and constraints. By contrast 22 with typical Interior Gateway Protocol (IGP) routing metrics using 23 hop counts or link metrics, this document specifies a set of link and 24 node routing metrics and constraints suitable to LLNs to be used by 25 the Routing for Low Power and lossy networks (RPL) routing protocol. 27 Requirements Language 29 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 30 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 31 document are to be interpreted as described in RFC 2119 [RFC2119]. 33 Status of this Memo 35 This Internet-Draft is submitted in full conformance with the 36 provisions of BCP 78 and BCP 79. 38 Internet-Drafts are working documents of the Internet Engineering 39 Task Force (IETF). Note that other groups may also distribute 40 working documents as Internet-Drafts. The list of current Internet- 41 Drafts is at http://datatracker.ietf.org/drafts/current/. 43 Internet-Drafts are draft documents valid for a maximum of six months 44 and may be updated, replaced, or obsoleted by other documents at any 45 time. It is inappropriate to use Internet-Drafts as reference 46 material or to cite them other than as "work in progress." 47 This Internet-Draft will expire on July 18, 2011. 49 Copyright Notice 51 Copyright (c) 2011 IETF Trust and the persons identified as the 52 document authors. All rights reserved. 54 This document is subject to BCP 78 and the IETF Trust's Legal 55 Provisions Relating to IETF Documents 56 (http://trustee.ietf.org/license-info) in effect on the date of 57 publication of this document. Please review these documents 58 carefully, as they describe your rights and restrictions with respect 59 to this document. Code Components extracted from this document must 60 include Simplified BSD License text as described in Section 4.e of 61 the Trust Legal Provisions and are provided without warranty as 62 described in the Simplified BSD License. 64 Table of Contents 66 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 4 67 2. Object Formats . . . . . . . . . . . . . . . . . . . . . . . . 7 68 2.1. DAG Metric Container Format . . . . . . . . . . . . . . . 7 69 2.2. Use of Multiple DAG Metric Containers . . . . . . . . . . 10 70 2.3. Metric Usage . . . . . . . . . . . . . . . . . . . . . . . 10 71 3. Node Metric/Constraint Objects . . . . . . . . . . . . . . . . 11 72 3.1. Node State and Attributes Object . . . . . . . . . . . . . 11 73 3.2. Node Energy Object . . . . . . . . . . . . . . . . . . . . 13 74 3.3. Hop-Count Object . . . . . . . . . . . . . . . . . . . . . 16 75 4. Link Metric/Constraint Objects . . . . . . . . . . . . . . . . 17 76 4.1. Throughput . . . . . . . . . . . . . . . . . . . . . . . . 17 77 4.2. Latency . . . . . . . . . . . . . . . . . . . . . . . . . 18 78 4.3. Link Reliability . . . . . . . . . . . . . . . . . . . . . 19 79 4.3.1. The Link Quality Level Reliability Metric . . . . . . 20 80 4.3.2. The Expected Transmission Count (ETX) reliability 81 object . . . . . . . . . . . . . . . . . . . . . . . . 21 82 4.4. Link Color Object . . . . . . . . . . . . . . . . . . . . 23 83 4.4.1. Link Color Object Description . . . . . . . . . . . . 23 84 4.4.2. Mode of operation . . . . . . . . . . . . . . . . . . 24 85 5. Computation of Dynamic Metrics and Attributes . . . . . . . . 25 86 6. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 25 87 6.1. Routing Metric/Constraint Type . . . . . . . . . . . . . . 26 88 6.2. Routing Metric/Constraint TLV . . . . . . . . . . . . . . 26 89 6.3. Routing Metric/Constraint Common Header . . . . . . . . . 26 90 6.4. NSA Object . . . . . . . . . . . . . . . . . . . . . . . . 27 91 6.5. Hop-Count Object . . . . . . . . . . . . . . . . . . . . . 27 92 7. Security Considerations . . . . . . . . . . . . . . . . . . . 27 93 8. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 28 94 9. References . . . . . . . . . . . . . . . . . . . . . . . . . . 28 95 9.1. Normative references . . . . . . . . . . . . . . . . . . . 28 96 9.2. Informative references . . . . . . . . . . . . . . . . . . 28 97 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 29 99 1. Introduction 101 This document makes use of the terminology defined in 102 [I-D.ietf-roll-terminology]. 104 Low power and Lossy Networks (LLNs) have specific routing 105 characteristics compared with traditional wired or ad-hoc networks 106 that have been spelled out in [RFC5548], [RFC5673], [RFC5826] and 107 [RFC5867]. 109 Historically, IGP such as OSPF ([RFC2328]) and IS-IS ([RFC1195]) have 110 used quantitative static link metrics. Other mechanisms such as 111 Multiprotocol Label Switching (MPLS) Traffic Engineering (TE) (see 112 [RFC2702] and [RFC3209]) make use of other link attributes such as 113 the available reserved bandwidth (dynamic) or link affinities (most 114 of the time static) to compute constrained shortest paths for Traffic 115 Engineering Label Switched Paths (TE LSPs). 117 This document specifies routing metrics and constraints to be used in 118 path calculation by the Routing Protocol for Low Power and Lossy 119 Networks (RPL) specified in [I-D.ietf-roll-rpl]. 121 One of the prime objectives of this document is to define a flexible 122 mechanism for the advertisement of routing metrics and constraints 123 used by RPL. Some RPL implementations may elect to adopt an 124 extremely simple approach based on the use of a single metric with no 125 constraint whereas other implementations may use a larger set of link 126 and node routing metrics and constraints. This specification 127 provides a high degree of flexibility and a set of routing metrics 128 and constraints. New routing metrics and constraints could be 129 defined in the future, as needed. 131 The metrics and constraints defined in this document are carried in 132 objects that are OPTIONAL within RPL. This means that 133 implementations are free to include different subsets of the 134 functions (metric, constraint) defined in this document. Specific 135 sets of metrics/constraints and other optional RPL parameters for use 136 in key environments will be specified as compliance profiles in 137 applicability profile documents produced by the ROLL working group. 139 RPL is a distance vector routing protocol variant that builds 140 Directed Acyclic Graphs (DAGs) based on routing metrics and 141 constraints. DAG formation rules are defined in [I-D.ietf-roll-rpl]: 143 o The Destination Oriented Directed Acyclic Graph (DODAG) root as 144 defined in [I-D.ietf-roll-rpl] may advertise a routing constraint 145 used as a "filter" to prune links and nodes that do not satisfy 146 specific properties. For example, it may be required for the path 147 to only traverse nodes that are mains powered or links that have 148 at least a minimum reliability or a specific "color" reflecting a 149 user defined link characteristic (e.g the link layer supports 150 encryption). 152 o A routing metric is a quantitative value that is used to evaluate 153 the path cost. Link and node metrics are usually (but not always) 154 additive. 156 The best path is the path that satisfies all supplied constraints (if 157 any) and that has the lowest cost with respect to some specified 158 metrics. It is also called the shortest constrained path (in the 159 presence of constraints). 161 Routing metrics may be categorized according to the following 162 characteristics: 164 o Link versus Node metrics 166 o Qualitative versus quantitative 168 o Dynamic versus static 170 Routing requirements documents (see [RFC5673], [RFC5826] [RFC5548] 171 and [RFC5867]) observe that it must be possible to take into account 172 a variety of node constraints/metrics during path computation. 174 Some link or node characteristics (e.g. link reliability, remaining 175 energy on the node) may be used by RPL either as routing constraints 176 or as metrics. For example, the path may be computed to avoid links 177 that do not provide a sufficient level of reliability (use as a 178 constraint) or as the path offering most links with a specified 179 reliability level (use as a metric). This document provides the 180 flexibility to use link and node characterisics either as constraints 181 and/or metrics. 183 The use of link and node routing metrics and constraints is not 184 exclusive (e.g. it is possible to advertise a "hop count" both as a 185 metric to optimize the computed path and as a constraint (e.g. "Path 186 should not exceed n hops")). 188 Links in LLN commonly have rapidly changing node and link 189 characteristics: thus routing metrics must be dynamic and techniques 190 must be used to smooth out the dynamicity of these metrics so as to 191 avoid routing oscillations. For instance, in addition to the dynamic 192 nature of some links (e.g. wireless but also Powerline Communication 193 (PLC) links), nodes' resources such as residual energy are changing 194 continuously and may have to be taken into account during the path 195 computation. 197 It must be noted that the use of dynamic metrics is not new and has 198 been experimented in ARPANET 2 (see [[Khanna1989J]). The use of 199 dynamic metrics is not trivial and great care must be given to the 200 use of dynamic metrics since it may lead to potential routing 201 instabilities. That being said, lots of experience has been gained 202 over the years on the use of dynamic routing metrics, which have been 203 deployed in a number of (non IP) networks. 205 Very careful attention must be given to the pace at which routing 206 metrics and attributes values change in order to preserve routing 207 stability. When using a dynamic routing metric, a RPL implementation 208 should make use of a multi-threshold scheme rather than fine granular 209 metric updates reflecting each individual change to avoid spurious 210 and unneccessary routing changes. 212 The requirements on reporting frequency may differ among metrics, 213 thus different reporting rates may be used for each metric. 215 The set of routing metrics and constraints used by an RPL deployment 216 is signaled along the DAG that is built according to the Objective 217 Function (rules governing how to build a DAG) and the routing metrics 218 and constraints are advertised in the DAG Information Option (DIO) 219 message specified in [I-D.ietf-roll-rpl]. RPL may be used to build 220 DAGs with different characteristics. For example, it may be 221 desirable to build a DAG with the goal to maximize reliability by 222 using the link reliability metric to compute the "best" path. 223 Another example might be to use the energy node characteristic (e.g. 224 mains powered versus battery operated) as a node constraint when 225 building the DAG so as to avoid battery powered nodes in the DAG 226 while optimizing the link throughput. 228 The specification of objective functions used to compute the DAG 229 built by RPL is out of the scope of this document. This document 230 defines routing metrics and constraints that are decoupled from the 231 objective function. So a generic objective function could for 232 example specify the rules to select the best parents in the DAG, the 233 number of backup parents, etc and could be used with any routing 234 metrics and/or constraints such as the ones specified in this 235 document. 237 Some metrics are either aggregated or recorded. An aggregated metric 238 is adjusted as the DIO message travels along the DAG. For example, 239 if the metric is the number of hops, each node updates the path cost 240 that reflects the number of traversed hops along the DAG. By 241 contrast, for a recorded metric, each node adds a sub-object 242 reflecting the local valuation of the metric. For example, it might 243 be desirable to record the link quality level along a path. In this 244 case, each visited node adds a sub-object recording the local link 245 quality level. In order to limit the number of sub-objects, the use 246 of a counter may be desirable (e.g. record the number of links with a 247 certain link quality level), thus compressing the information to 248 reduce the message length. Upon receiving the DIO message from a set 249 of parents, a node might decide according to the OF and local policy 250 which node to choose as a parent based on the maximum number of links 251 with a specific link reliability level, for example. 253 Note that the routing metrics and constraints specified in this 254 document are not specific to any particular link layer. An internal 255 API between the MAC layer and RPL may be used to accurately reflect 256 the metrics values of the link (wireless, wired, PLC). 258 Since a set of metrics and constraints will be used for links and 259 nodes in LLN, it is critical to ensure the use of consistent metric 260 calculation mechanisms for all links and nodes in the network, 261 similarly to the case of inter-domain IP routing. 263 2. Object Formats 265 2.1. DAG Metric Container Format 267 Routing metrics and constraints are carried within the DAG Metric 268 Container object defined in [I-D.ietf-roll-rpl]. Should multiple 269 metrics and/or constraints be present in the DAG Metric Container, 270 their use to determine the "best" path can be defined by an Objective 271 Function. 273 The Routing Metric/Constraint objects represent a metric or a 274 constraint of a particular type. They may appear in any order in the 275 DAG Metric Container (specified in [I-D.ietf-roll-rpl]). They have a 276 common format consisting of one or more bytes with a common header: 278 0 1 2 3 279 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 280 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 281 |Routing-MC-Type| Flags |P|C|O|R| A | Prec | Length (bytes)| 282 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 283 | | 284 // (object body) // 285 | | 286 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 288 Figure 1: Routing Metric/Constraint object generic format 290 The object body carries one or more sub-objects defined later in this 291 document. Note that an object may carry TLV, which may itself 292 comprise other TLVs. A TLV carried within a TLV is called a TLV in 293 this specification. 295 Routing-MC-Type (Routing Metric/Constraint Type - 8 bits): the 296 Routing Metric/Constraint Type field uniquely identifies each Routing 297 Metric/Constraint object and is managed by IANA. 299 Length: this field defines the length of the object body, in bytes. 301 Flag field (16 bits). The Flag field of the Routing Metric/ 302 Constraint object is managed by IANA. Unassigned bits are considered 303 as reserved. They MUST be set to zero on transmission and MUST be 304 ignored on receipt. 306 The following bits of the Routing Metric/Constraint Flag field object 307 are currently defined: 309 o P flag: the P field is only used for recorded metrics. When 310 cleared, all nodes along the path successfully recorded the 311 corresponding metric. When set, this indicates than one or 312 several nodes along the path could not record the metric of 313 interest (either because of lack of knowledge or because this was 314 prevented by policy). 316 o C Flag. When set, this indicates that the Routing Metric/ 317 Constraint object refers to a routing constraint. When cleared, 318 the routing object refers to a routing metric. 320 o O Flag: The O flag is used exclusively for routing constraints (C 321 flag is set). When set, this indicates that the constraint 322 specified in the body of the object is optional. When cleared, 323 the constraint is mandatory. If the C flag is zero, the O flag 324 MUST be set to zero on transmission and ignored on reception. 326 o R Flag: The R Flag is only relevant for routing metric (C=0) and 327 MUST be cleared for C=1. When set, this indicates that the 328 routing metric is recorded along the path. Conversely, when 329 cleared, the routing metric is aggregated. 331 A Field (3 bits): The A field is only relevant for metrics and is 332 used to indicate whether the aggregated routing metric is additive, 333 multiplicative, reports a maximum or a minimum. 335 o A=0x00: The routing metric is additive 337 o A=0x01: The routing metric reports a maximum 339 o A=0x02: The routing metric reports a minimum 341 o A=0x03: The routing metric is multiplicative 343 The A field has no meaning when the C Flag is set (i.e. when the 344 Routing Metric/Constraint object refers to a routing constraint) and 345 he only valid when the R bit is cleared. Otherwise, the A field MUST 346 be set to 0x00 and MUST be ignored on receipt. 348 Prec field (4 bits): The Prec field indicates the precedence of this 349 Routing Metric/Constraint object relative to other objects in the 350 container. This is useful when a DAG Metric Container contains 351 several Routing Metric objects. The value 0 means the highest 352 precedence. 354 Example 1: A DAG formed by RPL where all nodes must be mains-powered 355 and the best path is the one with lower aggregated ETX. In this case 356 the DAG Metric container carries two Routing Metric/Constraint 357 objects: one is an ETX metric object with header (C=0, O=0, A=00, 358 R=0) and the second one is a Node Energy constraint object with 359 header (C=1, O=0, A=00, R=0). Note that a RPL instance may use the 360 metric object to report a maximum (A=0x01) or a minimum (A=0x02). 361 If, for example, the best path is characterized by the path avoiding 362 low quality links, then the path metric reports a maximum (A=0x01) 363 (the higher is the ETX the lower link quality is): when the DIO 364 message reporting link quality metric (ETX) is processed by a node, 365 each node selecting the advertising node as a parent updates the 366 value carried in the metric object by replacing it with its local 367 link ETX value if and only if the latter is higher. As far as the 368 constraint is concerned, the object body will carry a node energy 369 constraint object defined in Section 3.1 indicating that nodes must 370 be mains-powered: if the constraint signalled in the DIO message is 371 not satisfied, the advertising node is just not selected as a parent 372 by the node that processes the DIO message. 374 Example 2: A DAG formed by RPL where the link metric is the link 375 quality level (defined in Section 4) and link quality levels must be 376 recorded along the path. In this case, the DAG Metric Container 377 carries a Routing Metric/Constraint object: link quality level metric 378 (C=0, O=0, A=00, R=1) containing multiple sub-objects. 380 A Routing Metric/Constraint object may also include one or more 381 additional type-length-value (TLV) encoded data sets. Each Routing 382 Metric/Constraint TLV has the same structure: 384 Type: 1 byte 385 Length: 1 byte 386 Value: variable 388 A Routing Metric/Constraint TLV is comprised of 1 byte for the type, 389 1 byte specifying the TLV length, and a value field. The TLV length 390 field defines the length of the value field in bytes. 392 Unrecognized TLVs MUST be silently ignored while still being 393 propagated in DIO generated by receiving node. 395 IANA manages the codepoints for all TLV carried in routing 396 constraint/metric objects. 398 IANA management of the Routing Metric/Constraint objects identifier 399 codespace is described in Section 6. 401 2.2. Use of Multiple DAG Metric Containers 403 Since the length of RPL options is encoded using 1 octet, they cannot 404 exceed 255 bytes, which also applies to the DAG Metric Container. In 405 the vast majority of cases, the advertised routing metrics and 406 constraints will not require that much space. However, there might 407 be circumstances where larger space is required, should for example a 408 set of routing metrics be recorded along a long path. In this case, 409 in order to avoid overflow, as specified in [I-D.ietf-roll-rpl], 410 routing metrics will be carried using multiple DAG Metric Containers 411 objects. 413 In the rest of this document, this use of multiple DAG Metric 414 Containers objects will be considered as if they were actually just 415 one long DAG Metric Container object. 417 2.3. Metric Usage 419 When the DAG Metric Container contains a single aggregated metric 420 (scalar value), the order relation to select the best path is 421 implicitly derived from the metric type. For example, lower is 422 better for Hop Count, Link Latency and ETX. Conversely, for Node 423 Energy or Throughput, higher is better. 425 An example of using such a single aggregated metric is optimizing 426 routing for node energy. The Node Energy metric (E-E field) defined 427 in Section 3.2 is aggregated along paths with an explicit min 428 function (A field), and the best path is selected through an implied 429 Max function because the metric is Energy. 431 When the DAG Metric Container contains several aggregated metrics, 432 they are to be used as tie-breakers according to their precedence 433 defined by their Prec field values. 435 An example of such use of multiple aggregated metrics is the 436 following: Hop-Count as the primary criterion, LQL as the secondary 437 criterion and Node Energy as the ultimate tie-breaker. In such a 438 case, the Hop-Count, LQL and Node Energy metric objects' Prec fields 439 should bear strictly increasing values such as 0, 1 and 2, 440 respectively. 442 If several aggregated metrics happen to bear the same Prec value, the 443 behavior is implementation-dependant. 445 3. Node Metric/Constraint Objects 447 The sections 3. and 4. specify several link and node metric/ 448 constraint objects. In some cases it is stated that there must not 449 be more than one object of a specific type. In that case, if an RPL 450 implementation receives more than one object of that type, the second 451 objet MUST silently be ignored. 453 In the presence of a constraint and a metric (which may or may not be 454 of the same type), a node MUST update the constraint before 455 advertising the updated metric and constraints. For example, if the 456 constraint is the number of hops (e.g. the maximum number of hops is 457 n) and the path is optimized against the delay: if a node selects a 458 parent advertising a maximum number of hops of n (constraint), it 459 must advertises DIO messages containing a hop count metrics 460 constraint with a field value equal of (n-1) and the newly computed 461 path metric. This applies to the following constraints defined 462 below: hop-count, latency and path ETX. 464 3.1. Node State and Attributes Object 466 The Node State and Attribute (NSA) object is used to provide 467 information on node characteristics. 469 The NSA object MAY be present in the DAG Metric Container. There 470 MUST NOT be more than one NSA object as a constraint per DAG Metric 471 Container, and there MUST NOT be more than one NSA object as a metric 472 per DAG Metric Container. 474 The NSA object may also contain a set of TLVs used to convey various 475 node characteristics. No TLV is currently defined. 477 The NSA Routing Metric/Constraint Type is to be assigned by IANA 478 (recommended value=1). 480 The format of the NSA object body is as follows: 482 0 1 2 483 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 484 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ... 485 | Res | Flags |A|O| Optional TLVs 486 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ... 488 Figure 2: NSA object body format 490 Res flags (8 bits): Reserved field. This field MUST be set to zero 491 on transmission and MUST be ignored on receipt. 493 Flags field (8 bits). The following two bits of the NSA object are 494 currently defined: 496 o A Flag: data Aggregation Attribute. Data fusion involves more 497 complicated processing to improve the accuracy of the output data, 498 while data aggregation mostly aims at reducing the amount of data. 499 This is listed as a requirement in Section 6.2 of [RFC5548]. Some 500 applications may make use of the aggregation node attribute in 501 their routing decision so as to minimize the amount of traffic on 502 the network, thus potentially increasing its lifetime in battery 503 operated environments. Applications where highly directional data 504 flow is expected on a regular basis may take advantage of data 505 aggregation supported routing. When set, this indicates that the 506 node can act as a traffic aggregator. An implementation MAY 507 decide to add optional TLVs (not currently defined) to further 508 describe the node traffic aggregator functionality. 510 o O Flag: node workload may be hard to determine and express in some 511 scalar form. However, node workload could be a useful metric to 512 consider during path calculation, in particular when queuing 513 delays must be minimized for highly sensitive traffic considering 514 Medium Access Control (MAC) layer delay. Node workload MAY be set 515 upon CPU overload, lack of memory or any other node related 516 conditions. Using a simple 1-bit flag to characterize the node 517 workload provides a sufficient level of granularity, similarly to 518 the "overload" bit used in routing protocols such as IS-IS. 519 Algorithms used to set the overload bit and to compute paths to 520 potentially avoid nodes with their overload bit set are outside 521 the scope of this document, but it is RECOMMENDED to avoid 522 frequent changes of this bit to avoid routing oscillations. When 523 set, this indicates that the node is overloaded and may not be 524 able to process traffic. 526 They MUST be set to zero on transmission and MUST be ignored on 527 receipt. 529 The Flag field of the NSA Routing Metric/Constraint object is managed 530 by IANA. Unassigned bits are considered as reserved. 532 3.2. Node Energy Object 534 It may sometimes be desirable to avoid selecting a node with low 535 residual energy as a router, thus the support for constraint-based 536 routing is needed. In such cases, the routing protocol engine may 537 compute a longer path (constraint based) for some traffic in order to 538 increase the network life duration. 540 Power and energy are clearly critical resources in most LLNs. As yet 541 there is no simple abstraction which adequately covers the broad 542 range of power sources and energy storage devices used in existing 543 LLN nodes. These include mains-powered, primary batteries, energy 544 scavengers, and a variety of secondary storage mechanisms. 545 Scavengers may provide a reliable low level of power, such as might 546 be available from a 4-20mA loop; a reliable but periodic stream of 547 power, such as provided by a well-positioned solar cell; or 548 unpredictable power, such as might be provided by a vibrational 549 energy scavenger on an intermittently powered pump. Routes which are 550 viable when the sun is shining may disappear at night. A pump 551 turning on may connect two previously disconnected sections of a 552 network. 554 Storage systems like rechargeable batteries often suffer substantial 555 degradation if regularly used to full discharge, leading to different 556 residual energy numbers for regular versus emergency operation. A 557 route for emergency traffic may have a different optimum than one for 558 regular reporting. 560 Batteries used in LLNs often degrade substantially if their average 561 current consumption exceeds a small fraction of the peak current that 562 they can deliver. It is not uncommon for self-supporting nodes to 563 have a combination of primary storage, energy scavenging, and 564 secondary storage, leading to three different values for acceptable 565 average current depending on the time frame being considered, e.g. 566 milliseconds, seconds, and hours/years. 568 Raw power and energy values are meaningless without knowledge of the 569 energy cost of sending and receiving packets, and lifetime estimates 570 have no value without some higher-level constraint on the lifetime 571 required of a device. In some cases the path that exhausts the 572 battery of a node on the bed table in a month may be preferable to a 573 route that reduces the lifetime of a node in the wall to a decade. 575 Given the complexity of trying to address such a broad collection of 576 constraints, this document defines two levels of fidelity in the 577 solution. 579 The simplest solution relies on a 2-bit field encoding three types of 580 power sources: "powered", "battery", "scavenger". This simple 581 approach may be sufficient for many applications. 583 The mid-complexity solution is a single parameter that can be used to 584 encode the energetic happiness of both battery powered and scavenging 585 nodes. For scavenging nodes, the 8 bit quantity is the power 586 provided by the scavenger divided by the power consumed by the 587 application, E-E=P_in/P_out, in units of percent. Nodes which are 588 scavenging more power than they are consuming will register above 589 100. A good time period for averaging power in this calculation may 590 be related to the discharge time of the energy storage device on the 591 node, but specifying this is out of the scope of this document. For 592 battery powered devices, E-E is the current expected lifetime divided 593 by the desired minimum lifetime, in units of percent. The estimation 594 of remaining battery energy and actual power consumption can be 595 difficult, and the specifics of this calculation are out of scope of 596 this document, but two examples are presented. If the node can 597 measure its average power consumption, then H can be calculated as 598 the ratio of desired max power (initial energy E_0 divided by desired 599 lifetime T) to actual power, E-E=P_max/P_now. Alternatively, if the 600 energy in the battery E_bat can be estimated, and the total elapsed 601 lifetime, t, is available, then H can be calculated as the total 602 stored energy remaining versus the target energy remaining: E-E= 603 E_bat / [E_0 (T-t)/T]. 605 An example of optimized route is max(min(H)) for all battery operated 606 nodes along the route, subject to the constraint that E-E>=100 for 607 all scavengers along the route. 609 Note that the estimated percentage of remaining energy indicated in 610 the E-E field may not be useful in the presence of nodes powered by 611 battery or energy scavengers when the amount of energy accumulated by 612 the device significantly differ. Indeed, X% of remaining energy on a 613 node that can store a large amount of energy cannot be easily 614 compared to the same percentage of remaining energy on a node powered 615 by a tiny source of energy. That being said, in networks where nodes 616 have relatively close energy storage, such a percentage of remaining 617 energy is useful. 619 The Node Energy (NE) object is used to provide information related to 620 node energy and may be used as a metric or as constraint. 622 The NE object MAY be present in the DAG Metric Container. There MUST 623 NOT be more than one NE object as a constraint per DAG Metric 624 Container, and there MUST NOT be more than one NE object as a metric 625 per DAG Metric Container. 627 The NE object Type is to be assigned by IANA (recommended value=2). 629 The format of the NE object body is as follows: 631 0 1 2 632 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 633 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ... 634 | NE Sub-objects 635 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ... 637 Figure 3: NE sub-object format 639 The format of the NE sub-object body is as follows: 641 0 1 2 642 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 643 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ... 644 | Flags |I| T |E| E-E | Optional TLVs 645 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ... 647 Figure 4: NE sub-object format 649 The NE sub-object may also contain a set of TLVs used to convey 650 various nodes' characteristics. 652 Flags field (8 bits). The following flags are currently defined: 654 o I (Included): the I bit is only relevant when the node type is 655 used as a constraint. For example, the path must only traverse 656 mains-powered nodes. Conversely, battery operated nodes must be 657 excluded. The I bit is used to stipulate inclusion versus 658 exclusion. When set, this indicates that nodes of the type 659 specified in the node type field MUST be included. Conversely, 660 when cleared, this indicates that nodes of type specified in the 661 node type field MUST be excluded. 663 o T (node Type): 2-bit field indicating the node type. T=0x00 664 designates a mains-powered node, T=0x01 a battery-powered node and 665 T=0x02 a node powered by an energy scavenger. 667 o E (Estimation): when the E bit is set for a metric, the estimated 668 percentage of remaining energy on the node is indicated in the E-E 669 8-bit field. When cleared, the estimated percentage of remaining 670 energy is not provided. When the E bit is set for a constraint, 671 the E-E field defines a threshold for the inclusion/exclusion: if 672 an inclusion, nodes with values higher than the threshold are to 673 be included; if an exclusion, nodes with values lower than the 674 threshold are to be excluded. 676 E-E (Estimated-Energy): 8-bit unsigned integer field indicating an 677 estimated percentage of remaining energy. The E-E field is only 678 relevant when the E flag is set, and MUST be set to 0 when the E flag 679 is cleared. 681 If the NE object comprises several sub-objects when used as a 682 constraint, each sub-object adds or subtracts node subsets as the 683 sub-objects are parsed in order. The initial set (full or empty) is 684 defined by the I bit of the first sub-object: full if that I bit is 685 an exclusion, empty if that I bit is an inclusion. 687 No TLV is currently defined. 689 Future documents may define more complex solutions involving TLV 690 parameters representing energy storage, consumption, and generation 691 capabilities of the node, as well as desired lifetime. 693 3.3. Hop-Count Object 695 The HoP-Count (HP) object is used to report the number of traversed 696 nodes along the path. 698 The HP object MAY be present in the DAG Metric Container. There MUST 699 NOT be more than one HP object as a constraint per DAG Metric 700 Container, and there MUST NOT be more than one HP object as a metric 701 per DAG Metric Container. 703 The HP object may also contain a set of TLVs used to convey various 704 node characteristics. No TLV is currently defined. 706 The HP routing metric object Type is to be assigned by IANA 707 (recommended value=3) 708 The format of the Hop Count object body is as follows: 710 0 1 2 711 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 712 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ... 713 | Res | Flags | Hop Count | Optional TLVs 714 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ... 716 Figure 5: Hop Count object body format 718 Res flags (4 bits): Reserved field. This field MUST be set to zero 719 on transmission and MUST be ignored on receipt. 721 No Flag is currently defined. Unassigned bits are considered as 722 reserved. They MUST be set to zero on transmission and MUST be 723 ignored on receipt. 725 The HP object may be used as a constraint or a metric. When used as 726 a constraint, the DAG root indicates the maximum number of hops that 727 a path may traverse. When that number is reached, no other node can 728 join that path. When used as a metric, each visited node simply 729 increments the Hop Count field. 731 Note that the first node along a path inserting a Hop-count object 732 MUST set the Hop Count field value to 1. 734 4. Link Metric/Constraint Objects 736 4.1. Throughput 738 Many LLNs support a wide range of throughputs. For some links, this 739 may be due to variable coding. For the deeply duty-cycled links 740 found in many LLNs, the variability comes as a result of trading 741 power consumption for bit rate. There are several MAC layer 742 protocols which allow for the effective bit rate of a link to vary 743 over more than three orders of magnitude with a corresponding change 744 in power consumption. For efficient operation, it may be desirable 745 for nodes to report the range of throughput that their links can 746 handle in addition to the currently available throughput. 748 The Throughput object MAY be present in the DAG Metric Container. 749 There MUST NOT be more than one Throughput object as a constraint per 750 DAG Metric Container, and there MUST NOT be more than one Throughput 751 object as a metric per DAG Metric Container. 753 The Throughput object is made of throughput sub-objects and MUST at 754 least comprise one Throughput sub-object. The first Throughput sub- 755 object MUST be the most recently estimated actual throughput. The 756 actual estimation of the throughput is outside the scope of this 757 document. 759 Each Throughput sub-object has a fixed length of 4 bytes. 761 The Throughput object does not contain any additional TLV. 763 The Throughput object Type is to be assigned by IANA (recommended 764 value=4) 766 The format of the Throughput object body is as follows: 768 0 1 769 0 1 2 3 4 5 6 7 8 9 0 1 2 3 770 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 771 | (sub-object) ..... 772 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 774 Figure 6: Throughput object body format 776 0 1 2 3 777 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 778 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 779 | Throughput | 780 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 782 Figure 7: Throughput sub-object format 784 Throughput: 32 bits. The Throughput is encoded in 32 bits in 785 unsigned integer format, expressed in bytes per second. 787 4.2. Latency 789 Similarly to throughput, the latency of many LLN MAC sub-layers can 790 vary over many orders of magnitude, again with a corresponding change 791 in power consumption. Some LLN MAC link layers will allow the 792 latency to be adjusted globally on the subnet, on a link-by-link 793 basis, or not at all. Some will insist that it be fixed for a given 794 link, but allow it to be variable from link to link. 796 The Latency object MAY be present in the DAG Metric Container. There 797 MUST NOT be more than one Latency object as a constraint per DAG 798 Metric Container, and there MUST NOT be more than one Latency object 799 as a metric per DAG Metric Container. 801 The Latency object is made of Latency sub-objects and MUST at least 802 comprise one Latency sub-object. Each Latency sub-object has a fixed 803 length of 4 bytes. 805 The Latency object does not contain any additional TLV. 807 The Latency object Type is to be assigned by IANA (recommended 808 value=5) 810 The Latency object is a metric or constraint. 812 The format of the Latency object body is as follows: 814 0 1 815 0 1 2 3 4 5 6 7 8 9 0 1 2 3 816 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 817 | (sub-object) ..... 818 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 820 Figure 8: Latency object body format 822 0 1 2 3 823 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 824 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 825 | Latency | 826 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 828 Figure 9: Latency sub-object format 830 Latency: 32 bits. The Latency is encoded in 32 bits in unsigned 831 integer format, expressed in microseconds. 833 The Latency object may be used as a constraint or a path metric. For 834 example, one may want the latency not to exceed some value. In this 835 case, the Latency object common header indicates that the provided 836 value relates to a constraint. In another example, the Latency 837 object may be used as an aggregated additive metric where the value 838 is updated along the path to reflect the path latency. 840 4.3. Link Reliability 842 In LLNs, link reliability is degraded by external interference and 843 multi-path interference (wireless links). Multipath typically 844 affects both directions on the link equally, whereas external 845 interference is sometimes unidirectional. Time scales vary from 846 milliseconds to days, and are often periodic and linked to human 847 activity. Packet error rates can generally be measured directly, and 848 other metrics (e.g. bit error rate, mean time between failures) are 849 typically derived from that. Note that such variability is not 850 specific to wireless link but also applies to PLC links. 852 A change in link quality can affect network connectivity, thus, link 853 quality may be taken into account as a critical routing metric. 855 A number of link reliability metrics could be defined reflecting 856 several reliability aspects. Two link reliability metrics are 857 defined in this document: the Link Quality Level (LQL) and the 858 Expected Transmission count Metric (ETX). 860 Note that an RPL deployment MAY either use the LQL, the ETX or both. 862 4.3.1. The Link Quality Level Reliability Metric 864 The Link Quality Level (LQL) object is used to quantify the link 865 reliability using a discrete value, from 0 to 7 where 0 indicates 866 that the link quality level is unknown and 1 reports the highest link 867 quality level. The mechanisms and algorithms used to compute the LQL 868 are implementation specific and outside of the scope of this 869 document. 871 The LQL can either be used as a metric or a constraint. When used as 872 a metric, the LQL metric can only be recorded. For example, the DAG 873 Metric object may request all traversed nodes to record the LQL of 874 their incoming link into the LQL object. Each node can then use the 875 LQL record to select its parent based on some user defined rules 876 (e.g. something like "select the path with most links reporting a LQL 877 value of 3 or less"). 879 Counters are used to compress the information: for each encountered 880 LQL value, only the number of matching links is reported. 882 The LQL object MAY be present in the DAG Metric Container. There 883 MUST NOT be more than one LQL object as a constraint per DAG Metric 884 Container, and there MUST NOT be more than one LQL object as a metric 885 per DAG Metric Container. 887 The LQL object MUST contain one or more sub-object used to report the 888 number of links along with their LQL. 890 The LQL object Type is to be assigned by IANA (recommended value=6) 891 The format of the LQL object body is as follows: 893 0 1 2 894 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 895 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ... 896 | Res | LQL sub-object 897 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ... 899 Figure 10: LQL object body format 901 Res flags (8 bits): Reserved field. This field MUST be set to zero 902 on transmission and MUST be ignored on receipt. 904 When the LQL metric is recorded, the LQL object body comprises one or 905 more LQL Type 1 sub-object. 907 The format of the LQL Type 1 sub-object is as follows 909 0 910 0 1 2 3 4 5 6 7 911 +-+-+-+-+-+-+-+-+ 912 | Val | Counter | 913 +-+-+-+-+-+-+-+-+ 915 Figure 11: LQL Type 1 sub-object format 917 Val: LQL value from 0 to 7 where 0 means undetermined and 1 indicates 918 the highest link quality. 920 Counter: number of links with that value. 922 4.3.2. The Expected Transmission Count (ETX) reliability object 924 The Expected Transmission Count (ETX) metric is the number of 925 transmissions a node expects to make to a destination in order to 926 successfully deliver a packet. In contrast with the LQL routing 927 metric, the ETX provides a discrete value (which may not be an 928 integer) computed according to a specific formula: for example, an 929 implementation may use the following formula: ETX= 1 / (Df * Dr) 930 where Df is the measured probability that a packet is received by the 931 neighbor and Dr is the measured probability that the acknowledgment 932 packet is successfully received. This document does not mandate the 933 use of a specific formula to compute the ETX value. 935 The ETX object MAY be present in the DAG Metric Container. There 936 MUST NOT be more than one ETX object as a constraint per DAG Metric 937 Container, and there MUST NOT be more than one ETX object as a metric 938 per DAG Metric Container. 940 The ETX object is made of ETX sub-objects and MUST at least comprise 941 one ETX sub-object. Each ETX sub-object has a fixed length of 8 942 bits. 944 The ETX object does not contain any additional TLV. 946 The ETX object Type is to be assigned by IANA (recommended value=7) 948 The format of the ETX object body is as follows: 950 0 1 951 0 1 2 3 4 5 6 7 8 9 0 1 2 3 952 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 953 | (sub-object) ..... 954 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 956 Figure 12: ETX object body format 958 0 1 959 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 960 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 961 | ETX | 962 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 964 Figure 13: ETX sub-object format 966 ETX: 16 bits. The ETX * 128 is encoded using 16 bits in unsigned 967 integer format, rounded off to the nearest whole number. For 968 example, if ETX = 3.569, the object value will be 457. If ETX > 969 511.9921875, the object value will be the maximum which is 65535. 971 The ETX object may be used as a constraint or a path metric. For 972 example, it may be required that the ETX must not exceed some 973 specified value. In this case, the ETX object common header 974 indicates that the value relates to a constraint. In another 975 example, the ETX object may be used as an aggregated additive metric 976 where the value is updated along the path to reflect the path 977 quality: when a node receives the aggregated additive ETX value of 978 the path (cummulative path ETX calculated as the sum of the link ETX 979 of all of the traversed links from the advertising node to the DAG 980 root), if it selects that node as its preferred parent, the node 981 updates the path ETX by adding the ETX of the local link between 982 itself and the preferred parent to the received path cost (path ETX) 983 before potentially advertising itself the new path ETX. 985 4.4. Link Color Object 987 4.4.1. Link Color Object Description 989 The Link Color (LC) object is an administrative 10-bit link 990 constraint (which may either be static or dynamically adjusted) used 991 to avoid or attract specific links for specific traffic types. 993 The LC object can either be used as a metric or as a constraint. 994 When used as a metric, the LC metric can only be recorded. For 995 example, the DAG may require recording the link colors for all 996 traversed links. A color is defined as a specific set of bit values: 997 in other words, that 10-bit field is a flag field, and not a scalar 998 value. Each node can then use the LC to select the parent based on 999 user defined rules (e.g. "select the path with the maximum number of 1000 links having their first bit set 1 (e.g. encrypted links)"). The LC 1001 object may also be used as a constraint. 1003 When used as a recorded metric, a counter is used to compress the 1004 information where the number of links for each Link Color is 1005 reported. 1007 The Link Color (LC) object MAY be present in the DAG Metric 1008 Container. There MUST NOT be more than one LC object as a constraint 1009 per DAG Metric Container, and there MUST NOT be more than one LC 1010 object as a metric per DAG Metric Container. 1012 There MUST be a at least one LC sub-object per LC object. 1014 The LC object does not contain any additional TLV. 1016 The LC object Type is to be assigned by IANA (recommended value=8) 1018 The format of the LC object body is as follows: 1020 0 1 2 1021 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 1022 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ... 1023 | Res | LC sub-objects 1024 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ... 1026 Figure 14: LC object format 1028 Res flags (8 bits): Reserved field. This field MUST be set to zero 1029 on transmission and MUST be ignored on receipt. 1031 When the LC object is used as a recorded metric, the LC object body 1032 comprises one or more LC Type 1 sub-objects. 1034 The format of the LC Type 1 sub-object body is as follows: 1036 0 1 1037 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 1038 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1039 | Link Color | Counter | 1040 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1042 Figure 15: LC Type 1 sub-object format 1044 When the LC object is used as a constraint, the LC object body 1045 comprises one or more LC Type 2 sub-objects. 1047 The format of the LC Type 2 sub-object body is as follows: 1049 0 1 1050 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 1051 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1052 | Link Color |Reserved |I| 1053 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1055 Figure 16: LC Type 2 sub-object format 1057 Res flags (7 bits): Reserved field. This field MUST be set to zero 1058 on transmission and MUST be ignored on receipt. 1060 I Bit: The I bit is only relevant when the Link Color is used as a 1061 constraint. When cleared, this indicates that links with the 1062 specified color must be included. When set, this indicates that 1063 links with the specified color must be excluded. 1065 It is left to the implementer to define the meaning of each bit of 1066 the 10-bit Link Color Flag field. 1068 4.4.2. Mode of operation 1070 The link color may be used as a constraint or a metric. 1072 o When used as constraint, the LC object may be inserted in the DAG 1073 Metric Container to indicate that links with a specific color 1074 should be included or excluded from the computed path. 1076 o When used as recorded metric, each node along the path may insert 1077 a LC object in the DAG Metric Container to report the color of the 1078 local link. If there is already a LC object reporting a similar 1079 color, the node MUST NOT add another identical LC sub-object and 1080 MUST increment the counter field. 1082 5. Computation of Dynamic Metrics and Attributes 1084 As already pointed out, dynamically calculated metrics are of the 1085 utmost importance in many circumstances in LLNs. This is mainly 1086 because a variety of metrics change on a frequent basis, thus 1087 implying the need to adapt the routing decisions. That being said, 1088 care must be given to the pace at which changes are reported in the 1089 network. The attributes will change according to their own time 1090 scales. RPL controls the reporting rate. 1092 To minimize metric updates, multi-threshold algorithms MAY be used to 1093 determine when updates should be sent. When practical, low-pass 1094 filtering and/or hysteresis should be used to avoid rapid 1095 fluctuations of these values. Finally, although the specification of 1096 path computation algorithms using dynamic metrics are out the scope 1097 of this document, it is RECOMMENDED to carefully design the route 1098 optimization algorithm to avoid too frequent computation of new 1099 routes upon metric values changes. 1101 Controlled adaptation of the routing metrics and rate at which paths 1102 are computed are critical to avoid undesirable routing instabilities 1103 resulting in increased latencies and packet loss because of temporary 1104 micro-loops. Furthermore, excessive route changes will adversely 1105 impact the traffic and power consumption in the network, thus 1106 potentially impacting its scalability. 1108 6. IANA Considerations 1110 IANA is requested to establish a new top-level registry to contain 1111 all Routing Metric/Constraint objects codepoints and sub-registries. 1113 The allocation policy for each new registry is by IETF review: new 1114 values are assigned through the IETF review process (see [RFC5226]). 1115 Specifically, new assignments are made via RFCs approved by the IESG. 1116 Typically, the IESG will seek input on prospective assignments from 1117 appropriate persons (e.g., a relevant Working Group if one exists). 1119 New bit numbers may be allocated only by an IETF Review action. Each 1120 bit should be tracked with the following qualities: 1122 o Bit number 1124 o Capability Description 1126 o Defining RFC 1128 6.1. Routing Metric/Constraint Type 1130 IANA is requested to create a registry for Routing Metric/Constraint 1131 objects. Each Routing Metric/Constraint object has a type value 1132 (from 1 to 255). 1134 Value Meaning Reference 1135 1 Node State and Attribute This document 1136 2 Node Energy This document 1137 3 Hop Count This document 1138 4 Link Throughput This document 1139 5 Link Latency This document 1140 6 Link Quality Level This document 1141 7 Link ETX This document 1142 8 Link Color This document 1144 6.2. Routing Metric/Constraint TLV 1146 IANA is requested to create a registry used for all TLVs carried 1147 within Routing Metric/Constraint objects. The type field is an 8-bit 1148 field whose value can be comprised between 1 and 255. 1150 6.3. Routing Metric/Constraint Common Header 1152 IANA is requested to create a registry to manage the Flag field of 1153 the Routing Metric/Constraint common header. 1155 Several bits are defined for the Routing Metric/Constraint common 1156 header in this document. The following values have been assigned: 1158 Codespace of the Flag field (Routing Metric/Constraint common header) 1159 Bit Description Reference 1161 12-15 Precedence This document 1162 9-11 Additive/Max/Min/Multi This document 1163 8 Recorded/Aggregated This document 1164 7 Optional Constraint This document 1165 6 Constraint/Metric This document 1166 5 P (Partial) This document 1168 IANA is requested to create a registry to manage the codespace of the 1169 A field of the Routing Metric/Constraint common header. 1171 Codespace of the A field (Routing Metric/Constraint common header) 1172 Value Meaning Reference 1174 0 Routing metric is additive This document 1175 1 Routing metric reports a maximum This document 1176 2 Routing metric reports a minimum This document 1177 3 Routing metric is multiplicative This document 1179 6.4. NSA Object 1181 IANA is requested to create a registry to manage the codespace of the 1182 Flag field of the NSA object. 1184 Several bits are defined for the NSA object flag field in this 1185 document. The following values have been assigned: 1187 Codespace of the Flag field (NSA object) 1188 Bit Description Reference 1190 14 Aggregator This document 1191 15 Overloaded This document 1193 6.5. Hop-Count Object 1195 IANA is requested to create a registry to manage the codespace of the 1196 Flag field of the Hop-count object. 1198 No Flag is currently defined. 1200 7. Security Considerations 1202 Routing metrics should be handled in a secure and trustful manner. 1203 For instance, RPL should not allow a malicious node to falsely 1204 advertise that it has good metrics for routing, be added as a router 1205 for other nodes' traffic and intercept packets. Another attack may 1206 consist of making intermitment attacks on a link in an attempt to 1207 constantly modify the link quality and consequently the associated 1208 routing metric, thus leading to potential fluctuation in the DODAG. 1209 It is thus RECOMMENDED for a RPL implementation to put in place 1210 mechanism so as to stop advertising routing metrics for highly 1211 unstable links that may be subject to attacks. 1213 Some routing metrics may also be used to identify some areas of 1214 weaknesses in the network (a highly unreliable link, a node running 1215 low in terms of energy, etc.). Such information may be used by a 1216 potential attacker. Thus, it is RECOMMENDED to carefully consider 1217 which metrics should be used by RPL and the level of visibility that 1218 they provide about the network state or to use appropriate the 1219 security measures as specified in [I-D.ietf-roll-rpl] to protect that 1220 information. 1222 Since the routing metrics/constraints are carried within RPL message, 1223 the security routing mechanisms defined in [I-D.ietf-roll-rpl] 1224 applies here. 1226 8. Acknowledgements 1228 The authors would like to acknowledge the contributions of Young Jae 1229 Kim, Hakjin Chong, David Meyer, Mischa Dohler, Anders Brandt, Philip 1230 Levis, Pascal Thubert, Richard Kelsey, Jonathan Hui, Alexandru 1231 Petrescu, Richard Kelsey, Mathilde Durvy, Phoebus Chen, Tim Winter, 1232 Mukul Goyal, Yoav Ben-Yehezkel, Matteo Paris, Omprakash Gnawali, Mads 1233 Westergreen, Mukul Goyal, Joseph Saloway and David Culler for their 1234 review and valuable comments. Special thank to Adrian Farrel for his 1235 thourough review. 1237 9. References 1239 9.1. Normative references 1241 [I-D.ietf-roll-rpl] 1242 Winter, T., Thubert, P., Brandt, A., Clausen, T., Hui, J., 1243 Kelsey, R., Levis, P., Pister, K., Struik, R., and J. 1244 Vasseur, "RPL: IPv6 Routing Protocol for Low power and 1245 Lossy Networks", draft-ietf-roll-rpl-17 (work in 1246 progress), December 2010. 1248 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 1249 Requirement Levels", BCP 14, RFC 2119, March 1997. 1251 [RFC5226] Narten, T. and H. Alvestrand, "Guidelines for Writing an 1252 IANA Considerations Section in RFCs", BCP 26, RFC 5226, 1253 May 2008. 1255 9.2. Informative references 1257 [I-D.ietf-roll-terminology] 1258 Vasseur, J., "Terminology in Low power And Lossy 1259 Networks", draft-ietf-roll-terminology-04 (work in 1260 progress), September 2010. 1262 [Khanna1989J A. Zinky, A. Khanna, and G. Vichniac. "Performance of 1263 the Revised Routing Metric for ARPANET and MILNET. 1264 Submitted to MILCOM 89, March 1989 1266 [RFC1195] Callon, R., "Use of OSI IS-IS for routing in TCP/IP and 1267 dual environments", RFC 1195, December 1990. 1269 [RFC2328] Moy, J., "OSPF Version 2", STD 54, RFC 2328, April 1998. 1271 [RFC2702] Awduche, D., Malcolm, J., Agogbua, J., O'Dell, M., and J. 1272 McManus, "Requirements for Traffic Engineering Over MPLS", 1273 RFC 2702, September 1999. 1275 [RFC3209] Awduche, D., Berger, L., Gan, D., Li, T., Srinivasan, V., 1276 and G. Swallow, "RSVP-TE: Extensions to RSVP for LSP 1277 Tunnels", RFC 3209, December 2001. 1279 [RFC5548] Dohler, M., Watteyne, T., Winter, T., and D. Barthel, 1280 "Routing Requirements for Urban Low-Power and Lossy 1281 Networks", RFC 5548, May 2009. 1283 [RFC5673] Pister, K., Thubert, P., Dwars, S., and T. Phinney, 1284 "Industrial Routing Requirements in Low-Power and Lossy 1285 Networks", RFC 5673, October 2009. 1287 [RFC5826] Brandt, A., Buron, J., and G. Porcu, "Home Automation 1288 Routing Requirements in Low-Power and Lossy Networks", 1289 RFC 5826, April 2010. 1291 [RFC5867] Martocci, J., De Mil, P., Riou, N., and W. Vermeylen, 1292 "Building Automation Routing Requirements in Low-Power and 1293 Lossy Networks", RFC 5867, June 2010. 1295 Authors' Addresses 1297 JP Vasseur (editor) 1298 Cisco Systems, Inc 1299 11, Rue Camille Desmoulins 1300 Issy Les Moulineaux, 92782 1301 France 1303 Email: jpv@cisco.com 1305 Mijeom Kim (editor) 1306 Corporate Technology Group, KT 1307 17 Woomyeon-dong, Seocho-gu 1308 Seoul, 137-792 1309 Korea 1311 Email: mjkim@kt.com 1312 Kris Pister 1313 Dust Networks 1314 30695 Huntwood Ave. 1315 Hayward, CA 95544 1316 USA 1318 Email: kpister@dustnetworks.com 1320 Nicolas Dejean 1321 Coronis SAS 1322 Espace Concorde, 120 impasse JB Say 1323 Perols, 34470 1324 France 1326 Email: nicolas.dejean@coronis.com 1328 Dominique Barthel 1329 France Telecom Orange 1330 28 chemin du Vieux Chene, BP 98 1331 Meylan, 38243 1332 France 1334 Email: dominique.barthel@orange-ftgroup.com 1336 Networking Working Group JP. Vasseur, Ed. 1337 Internet-Draft Cisco Systems, Inc 1338 Intended status: Standards Track M. Kim, Ed. 1339 Expires: July 18, 2011 Corporate Technology Group, KT 1340 K. Pister 1341 Dust Networks 1342 N. Dejean 1343 Coronis SAS 1344 D. Barthel 1345 France Telecom Orange 1346 January 14, 2011 1348 Routing Metrics used for Path Calculation in Low Power and Lossy 1349 Networks 1350 draft-ietf-roll-routing-metrics-15 1352 Abstract 1354 Low power and Lossy Networks (LLNs) have unique characteristics 1355 compared with traditional wired and ad-hoc networks that require the 1356 specification of new routing metrics and constraints. By contrast 1357 with typical Interior Gateway Protocol (IGP) routing metrics using 1358 hop counts or link metrics, this document specifies a set of link and 1359 node routing metrics and constraints suitable to LLNs to be used by 1360 the Routing for Low Power and lossy networks (RPL) routing protocol. 1362 Requirements Language 1364 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 1365 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 1366 document are to be interpreted as described in RFC 2119 [RFC2119]. 1368 Status of this Memo 1370 This Internet-Draft is submitted in full conformance with the 1371 provisions of BCP 78 and BCP 79. 1373 Internet-Drafts are working documents of the Internet Engineering 1374 Task Force (IETF). Note that other groups may also distribute 1375 working documents as Internet-Drafts. The list of current Internet- 1376 Drafts is at http://datatracker.ietf.org/drafts/current/. 1378 Internet-Drafts are draft documents valid for a maximum of six months 1379 and may be updated, replaced, or obsoleted by other documents at any 1380 time. It is inappropriate to use Internet-Drafts as reference 1381 material or to cite them other than as "work in progress." 1382 This Internet-Draft will expire on July 18, 2011. 1384 Copyright Notice 1386 Copyright (c) 2011 IETF Trust and the persons identified as the 1387 document authors. All rights reserved. 1389 This document is subject to BCP 78 and the IETF Trust's Legal 1390 Provisions Relating to IETF Documents 1391 (http://trustee.ietf.org/license-info) in effect on the date of 1392 publication of this document. Please review these documents 1393 carefully, as they describe your rights and restrictions with respect 1394 to this document. Code Components extracted from this document must 1395 include Simplified BSD License text as described in Section 4.e of 1396 the Trust Legal Provisions and are provided without warranty as 1397 described in the Simplified BSD License. 1399 Table of Contents 1401 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 4 1402 2. Object Formats . . . . . . . . . . . . . . . . . . . . . . . . 7 1403 2.1. DAG Metric Container Format . . . . . . . . . . . . . . . 7 1404 2.2. Use of Multiple DAG Metric Containers . . . . . . . . . . 10 1405 2.3. Metric Usage . . . . . . . . . . . . . . . . . . . . . . . 10 1406 3. Node Metric/Constraint Objects . . . . . . . . . . . . . . . . 11 1407 3.1. Node State and Attributes Object . . . . . . . . . . . . . 11 1408 3.2. Node Energy Object . . . . . . . . . . . . . . . . . . . . 13 1409 3.3. Hop-Count Object . . . . . . . . . . . . . . . . . . . . . 16 1410 4. Link Metric/Constraint Objects . . . . . . . . . . . . . . . . 17 1411 4.1. Throughput . . . . . . . . . . . . . . . . . . . . . . . . 17 1412 4.2. Latency . . . . . . . . . . . . . . . . . . . . . . . . . 18 1413 4.3. Link Reliability . . . . . . . . . . . . . . . . . . . . . 19 1414 4.3.1. The Link Quality Level Reliability Metric . . . . . . 20 1415 4.3.2. The Expected Transmission Count (ETX) reliability 1416 object . . . . . . . . . . . . . . . . . . . . . . . . 21 1417 4.4. Link Color Object . . . . . . . . . . . . . . . . . . . . 23 1418 4.4.1. Link Color Object Description . . . . . . . . . . . . 23 1419 4.4.2. Mode of operation . . . . . . . . . . . . . . . . . . 24 1420 5. Computation of Dynamic Metrics and Attributes . . . . . . . . 25 1421 6. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 25 1422 6.1. Routing Metric/Constraint Type . . . . . . . . . . . . . . 26 1423 6.2. Routing Metric/Constraint TLV . . . . . . . . . . . . . . 26 1424 6.3. Routing Metric/Constraint Common Header . . . . . . . . . 26 1425 6.4. NSA Object . . . . . . . . . . . . . . . . . . . . . . . . 27 1426 6.5. Hop-Count Object . . . . . . . . . . . . . . . . . . . . . 27 1427 7. Security Considerations . . . . . . . . . . . . . . . . . . . 27 1428 8. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 28 1429 9. References . . . . . . . . . . . . . . . . . . . . . . . . . . 28 1430 9.1. Normative references . . . . . . . . . . . . . . . . . . . 28 1431 9.2. Informative references . . . . . . . . . . . . . . . . . . 28 1432 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 29 1434 1. Introduction 1436 This document makes use of the terminology defined in 1437 [I-D.ietf-roll-terminology]. 1439 Low power and Lossy Networks (LLNs) have specific routing 1440 characteristics compared with traditional wired or ad-hoc networks 1441 that have been spelled out in [RFC5548], [RFC5673], [RFC5826] and 1442 [RFC5867]. 1444 Historically, IGP such as OSPF ([RFC2328]) and IS-IS ([RFC1195]) have 1445 used quantitative static link metrics. Other mechanisms such as 1446 Multiprotocol Label Switching (MPLS) Traffic Engineering (TE) (see 1447 [RFC2702] and [RFC3209]) make use of other link attributes such as 1448 the available reserved bandwidth (dynamic) or link affinities (most 1449 of the time static) to compute constrained shortest paths for Traffic 1450 Engineering Label Switched Paths (TE LSPs). 1452 This document specifies routing metrics and constraints to be used in 1453 path calculation by the Routing Protocol for Low Power and Lossy 1454 Networks (RPL) specified in [I-D.ietf-roll-rpl]. 1456 One of the prime objectives of this document is to define a flexible 1457 mechanism for the advertisement of routing metrics and constraints 1458 used by RPL. Some RPL implementations may elect to adopt an 1459 extremely simple approach based on the use of a single metric with no 1460 constraint whereas other implementations may use a larger set of link 1461 and node routing metrics and constraints. This specification 1462 provides a high degree of flexibility and a set of routing metrics 1463 and constraints. New routing metrics and constraints could be 1464 defined in the future, as needed. 1466 The metrics and constraints defined in this document are carried in 1467 objects that are OPTIONAL within RPL. This means that 1468 implementations are free to include different subsets of the 1469 functions (metric, constraint) defined in this document. Specific 1470 sets of metrics/constraints and other optional RPL parameters for use 1471 in key environments will be specified as compliance profiles in 1472 applicability profile documents produced by the ROLL working group. 1474 RPL is a distance vector routing protocol variant that builds 1475 Directed Acyclic Graphs (DAGs) based on routing metrics and 1476 constraints. DAG formation rules are defined in [I-D.ietf-roll-rpl]: 1478 o The Destination Oriented Directed Acyclic Graph (DODAG) root as 1479 defined in [I-D.ietf-roll-rpl] may advertise a routing constraint 1480 used as a "filter" to prune links and nodes that do not satisfy 1481 specific properties. For example, it may be required for the path 1482 to only traverse nodes that are mains powered or links that have 1483 at least a minimum reliability or a specific "color" reflecting a 1484 user defined link characteristic (e.g the link layer supports 1485 encryption). 1487 o A routing metric is a quantitative value that is used to evaluate 1488 the path cost. Link and node metrics are usually (but not always) 1489 additive. 1491 The best path is the path that satisfies all supplied constraints (if 1492 any) and that has the lowest cost with respect to some specified 1493 metrics. It is also called the shortest constrained path (in the 1494 presence of constraints). 1496 Routing metrics may be categorized according to the following 1497 characteristics: 1499 o Link versus Node metrics 1501 o Qualitative versus quantitative 1503 o Dynamic versus static 1505 Routing requirements documents (see [RFC5673], [RFC5826] [RFC5548] 1506 and [RFC5867]) observe that it must be possible to take into account 1507 a variety of node constraints/metrics during path computation. 1509 Some link or node characteristics (e.g. link reliability, remaining 1510 energy on the node) may be used by RPL either as routing constraints 1511 or as metrics. For example, the path may be computed to avoid links 1512 that do not provide a sufficient level of reliability (use as a 1513 constraint) or as the path offering most links with a specified 1514 reliability level (use as a metric). This document provides the 1515 flexibility to use link and node characterisics either as constraints 1516 and/or metrics. 1518 The use of link and node routing metrics and constraints is not 1519 exclusive (e.g. it is possible to advertise a "hop count" both as a 1520 metric to optimize the computed path and as a constraint (e.g. "Path 1521 should not exceed n hops")). 1523 Links in LLN commonly have rapidly changing node and link 1524 characteristics: thus routing metrics must be dynamic and techniques 1525 must be used to smooth out the dynamicity of these metrics so as to 1526 avoid routing oscillations. For instance, in addition to the dynamic 1527 nature of some links (e.g. wireless but also Powerline Communication 1528 (PLC) links), nodes' resources such as residual energy are changing 1529 continuously and may have to be taken into account during the path 1530 computation. 1532 It must be noted that the use of dynamic metrics is not new and has 1533 been experimented in ARPANET 2 (see [[Khanna1989J]). The use of 1534 dynamic metrics is not trivial and great care must be given to the 1535 use of dynamic metrics since it may lead to potential routing 1536 instabilities. That being said, lots of experience has been gained 1537 over the years on the use of dynamic routing metrics, which have been 1538 deployed in a number of (non IP) networks. 1540 Very careful attention must be given to the pace at which routing 1541 metrics and attributes values change in order to preserve routing 1542 stability. When using a dynamic routing metric, a RPL implementation 1543 should make use of a multi-threshold scheme rather than fine granular 1544 metric updates reflecting each individual change to avoid spurious 1545 and unneccessary routing changes. 1547 The requirements on reporting frequency may differ among metrics, 1548 thus different reporting rates may be used for each metric. 1550 The set of routing metrics and constraints used by an RPL deployment 1551 is signaled along the DAG that is built according to the Objective 1552 Function (rules governing how to build a DAG) and the routing metrics 1553 and constraints are advertised in the DAG Information Option (DIO) 1554 message specified in [I-D.ietf-roll-rpl]. RPL may be used to build 1555 DAGs with different characteristics. For example, it may be 1556 desirable to build a DAG with the goal to maximize reliability by 1557 using the link reliability metric to compute the "best" path. 1558 Another example might be to use the energy node characteristic (e.g. 1559 mains powered versus battery operated) as a node constraint when 1560 building the DAG so as to avoid battery powered nodes in the DAG 1561 while optimizing the link throughput. 1563 The specification of objective functions used to compute the DAG 1564 built by RPL is out of the scope of this document. This document 1565 defines routing metrics and constraints that are decoupled from the 1566 objective function. So a generic objective function could for 1567 example specify the rules to select the best parents in the DAG, the 1568 number of backup parents, etc and could be used with any routing 1569 metrics and/or constraints such as the ones specified in this 1570 document. 1572 Some metrics are either aggregated or recorded. An aggregated metric 1573 is adjusted as the DIO message travels along the DAG. For example, 1574 if the metric is the number of hops, each node updates the path cost 1575 that reflects the number of traversed hops along the DAG. By 1576 contrast, for a recorded metric, each node adds a sub-object 1577 reflecting the local valuation of the metric. For example, it might 1578 be desirable to record the link quality level along a path. In this 1579 case, each visited node adds a sub-object recording the local link 1580 quality level. In order to limit the number of sub-objects, the use 1581 of a counter may be desirable (e.g. record the number of links with a 1582 certain link quality level), thus compressing the information to 1583 reduce the message length. Upon receiving the DIO message from a set 1584 of parents, a node might decide according to the OF and local policy 1585 which node to choose as a parent based on the maximum number of links 1586 with a specific link reliability level, for example. 1588 Note that the routing metrics and constraints specified in this 1589 document are not specific to any particular link layer. An internal 1590 API between the MAC layer and RPL may be used to accurately reflect 1591 the metrics values of the link (wireless, wired, PLC). 1593 Since a set of metrics and constraints will be used for links and 1594 nodes in LLN, it is critical to ensure the use of consistent metric 1595 calculation mechanisms for all links and nodes in the network, 1596 similarly to the case of inter-domain IP routing. 1598 2. Object Formats 1600 2.1. DAG Metric Container Format 1602 Routing metrics and constraints are carried within the DAG Metric 1603 Container object defined in [I-D.ietf-roll-rpl]. Should multiple 1604 metrics and/or constraints be present in the DAG Metric Container, 1605 their use to determine the "best" path can be defined by an Objective 1606 Function. 1608 The Routing Metric/Constraint objects represent a metric or a 1609 constraint of a particular type. They may appear in any order in the 1610 DAG Metric Container (specified in [I-D.ietf-roll-rpl]). They have a 1611 common format consisting of one or more bytes with a common header: 1613 0 1 2 3 1614 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 1615 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1616 |Routing-MC-Type| Flags |P|C|O|R| A | Prec | Length (bytes)| 1617 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1618 | | 1619 // (object body) // 1620 | | 1621 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1623 Figure 1: Routing Metric/Constraint object generic format 1625 The object body carries one or more sub-objects defined later in this 1626 document. Note that an object may carry TLV, which may itself 1627 comprise other TLVs. A TLV carried within a TLV is called a TLV in 1628 this specification. 1630 Routing-MC-Type (Routing Metric/Constraint Type - 8 bits): the 1631 Routing Metric/Constraint Type field uniquely identifies each Routing 1632 Metric/Constraint object and is managed by IANA. 1634 Length: this field defines the length of the object body, in bytes. 1636 Flag field (16 bits). The Flag field of the Routing Metric/ 1637 Constraint object is managed by IANA. Unassigned bits are considered 1638 as reserved. They MUST be set to zero on transmission and MUST be 1639 ignored on receipt. 1641 The following bits of the Routing Metric/Constraint Flag field object 1642 are currently defined: 1644 o P flag: the P field is only used for recorded metrics. When 1645 cleared, all nodes along the path successfully recorded the 1646 corresponding metric. When set, this indicates than one or 1647 several nodes along the path could not record the metric of 1648 interest (either because of lack of knowledge or because this was 1649 prevented by policy). 1651 o C Flag. When set, this indicates that the Routing Metric/ 1652 Constraint object refers to a routing constraint. When cleared, 1653 the routing object refers to a routing metric. 1655 o O Flag: The O flag is used exclusively for routing constraints (C 1656 flag is set). When set, this indicates that the constraint 1657 specified in the body of the object is optional. When cleared, 1658 the constraint is mandatory. If the C flag is zero, the O flag 1659 MUST be set to zero on transmission and ignored on reception. 1661 o R Flag: The R Flag is only relevant for routing metric (C=0) and 1662 MUST be cleared for C=1. When set, this indicates that the 1663 routing metric is recorded along the path. Conversely, when 1664 cleared, the routing metric is aggregated. 1666 A Field (3 bits): The A field is only relevant for metrics and is 1667 used to indicate whether the aggregated routing metric is additive, 1668 multiplicative, reports a maximum or a minimum. 1670 o A=0x00: The routing metric is additive 1672 o A=0x01: The routing metric reports a maximum 1674 o A=0x02: The routing metric reports a minimum 1676 o A=0x03: The routing metric is multiplicative 1678 The A field has no meaning when the C Flag is set (i.e. when the 1679 Routing Metric/Constraint object refers to a routing constraint) and 1680 he only valid when the R bit is cleared. Otherwise, the A field MUST 1681 be set to 0x00 and MUST be ignored on receipt. 1683 Prec field (4 bits): The Prec field indicates the precedence of this 1684 Routing Metric/Constraint object relative to other objects in the 1685 container. This is useful when a DAG Metric Container contains 1686 several Routing Metric objects. The value 0 means the highest 1687 precedence. 1689 Example 1: A DAG formed by RPL where all nodes must be mains-powered 1690 and the best path is the one with lower aggregated ETX. In this case 1691 the DAG Metric container carries two Routing Metric/Constraint 1692 objects: one is an ETX metric object with header (C=0, O=0, A=00, 1693 R=0) and the second one is a Node Energy constraint object with 1694 header (C=1, O=0, A=00, R=0). Note that a RPL instance may use the 1695 metric object to report a maximum (A=0x01) or a minimum (A=0x02). 1696 If, for example, the best path is characterized by the path avoiding 1697 low quality links, then the path metric reports a maximum (A=0x01) 1698 (the higher is the ETX the lower link quality is): when the DIO 1699 message reporting link quality metric (ETX) is processed by a node, 1700 each node selecting the advertising node as a parent updates the 1701 value carried in the metric object by replacing it with its local 1702 link ETX value if and only if the latter is higher. As far as the 1703 constraint is concerned, the object body will carry a node energy 1704 constraint object defined in Section 3.1 indicating that nodes must 1705 be mains-powered: if the constraint signalled in the DIO message is 1706 not satisfied, the advertising node is just not selected as a parent 1707 by the node that processes the DIO message. 1709 Example 2: A DAG formed by RPL where the link metric is the link 1710 quality level (defined in Section 4) and link quality levels must be 1711 recorded along the path. In this case, the DAG Metric Container 1712 carries a Routing Metric/Constraint object: link quality level metric 1713 (C=0, O=0, A=00, R=1) containing multiple sub-objects. 1715 A Routing Metric/Constraint object may also include one or more 1716 additional type-length-value (TLV) encoded data sets. Each Routing 1717 Metric/Constraint TLV has the same structure: 1719 Type: 1 byte 1720 Length: 1 byte 1721 Value: variable 1723 A Routing Metric/Constraint TLV is comprised of 1 byte for the type, 1724 1 byte specifying the TLV length, and a value field. The TLV length 1725 field defines the length of the value field in bytes. 1727 Unrecognized TLVs MUST be silently ignored while still being 1728 propagated in DIO generated by receiving node. 1730 IANA manages the codepoints for all TLV carried in routing 1731 constraint/metric objects. 1733 IANA management of the Routing Metric/Constraint objects identifier 1734 codespace is described in Section 6. 1736 2.2. Use of Multiple DAG Metric Containers 1738 Since the length of RPL options is encoded using 1 octet, they cannot 1739 exceed 255 bytes, which also applies to the DAG Metric Container. In 1740 the vast majority of cases, the advertised routing metrics and 1741 constraints will not require that much space. However, there might 1742 be circumstances where larger space is required, should for example a 1743 set of routing metrics be recorded along a long path. In this case, 1744 in order to avoid overflow, as specified in [I-D.ietf-roll-rpl], 1745 routing metrics will be carried using multiple DAG Metric Containers 1746 objects. 1748 In the rest of this document, this use of multiple DAG Metric 1749 Containers objects will be considered as if they were actually just 1750 one long DAG Metric Container object. 1752 2.3. Metric Usage 1754 When the DAG Metric Container contains a single aggregated metric 1755 (scalar value), the order relation to select the best path is 1756 implicitly derived from the metric type. For example, lower is 1757 better for Hop Count, Link Latency and ETX. Conversely, for Node 1758 Energy or Throughput, higher is better. 1760 An example of using such a single aggregated metric is optimizing 1761 routing for node energy. The Node Energy metric (E-E field) defined 1762 in Section 3.2 is aggregated along paths with an explicit min 1763 function (A field), and the best path is selected through an implied 1764 Max function because the metric is Energy. 1766 When the DAG Metric Container contains several aggregated metrics, 1767 they are to be used as tie-breakers according to their precedence 1768 defined by their Prec field values. 1770 An example of such use of multiple aggregated metrics is the 1771 following: Hop-Count as the primary criterion, LQL as the secondary 1772 criterion and Node Energy as the ultimate tie-breaker. In such a 1773 case, the Hop-Count, LQL and Node Energy metric objects' Prec fields 1774 should bear strictly increasing values such as 0, 1 and 2, 1775 respectively. 1777 If several aggregated metrics happen to bear the same Prec value, the 1778 behavior is implementation-dependant. 1780 3. Node Metric/Constraint Objects 1782 The sections 3. and 4. specify several link and node metric/ 1783 constraint objects. In some cases it is stated that there must not 1784 be more than one object of a specific type. In that case, if an RPL 1785 implementation receives more than one object of that type, the second 1786 objet MUST silently be ignored. 1788 In the presence of a constraint and a metric (which may or may not be 1789 of the same type), a node MUST update the constraint before 1790 advertising the updated metric and constraints. For example, if the 1791 constraint is the number of hops (e.g. the maximum number of hops is 1792 n) and the path is optimized against the delay: if a node selects a 1793 parent advertising a maximum number of hops of n (constraint), it 1794 must advertises DIO messages containing a hop count metrics 1795 constraint with a field value equal of (n-1) and the newly computed 1796 path metric. This applies to the following constraints defined 1797 below: hop-count, latency and path ETX. 1799 3.1. Node State and Attributes Object 1801 The Node State and Attribute (NSA) object is used to provide 1802 information on node characteristics. 1804 The NSA object MAY be present in the DAG Metric Container. There 1805 MUST NOT be more than one NSA object as a constraint per DAG Metric 1806 Container, and there MUST NOT be more than one NSA object as a metric 1807 per DAG Metric Container. 1809 The NSA object may also contain a set of TLVs used to convey various 1810 node characteristics. No TLV is currently defined. 1812 The NSA Routing Metric/Constraint Type is to be assigned by IANA 1813 (recommended value=1). 1815 The format of the NSA object body is as follows: 1817 0 1 2 1818 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 1819 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ... 1820 | Res | Flags |A|O| Optional TLVs 1821 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ... 1823 Figure 2: NSA object body format 1825 Res flags (8 bits): Reserved field. This field MUST be set to zero 1826 on transmission and MUST be ignored on receipt. 1828 Flags field (8 bits). The following two bits of the NSA object are 1829 currently defined: 1831 o A Flag: data Aggregation Attribute. Data fusion involves more 1832 complicated processing to improve the accuracy of the output data, 1833 while data aggregation mostly aims at reducing the amount of data. 1834 This is listed as a requirement in Section 6.2 of [RFC5548]. Some 1835 applications may make use of the aggregation node attribute in 1836 their routing decision so as to minimize the amount of traffic on 1837 the network, thus potentially increasing its lifetime in battery 1838 operated environments. Applications where highly directional data 1839 flow is expected on a regular basis may take advantage of data 1840 aggregation supported routing. When set, this indicates that the 1841 node can act as a traffic aggregator. An implementation MAY 1842 decide to add optional TLVs (not currently defined) to further 1843 describe the node traffic aggregator functionality. 1845 o O Flag: node workload may be hard to determine and express in some 1846 scalar form. However, node workload could be a useful metric to 1847 consider during path calculation, in particular when queuing 1848 delays must be minimized for highly sensitive traffic considering 1849 Medium Access Control (MAC) layer delay. Node workload MAY be set 1850 upon CPU overload, lack of memory or any other node related 1851 conditions. Using a simple 1-bit flag to characterize the node 1852 workload provides a sufficient level of granularity, similarly to 1853 the "overload" bit used in routing protocols such as IS-IS. 1854 Algorithms used to set the overload bit and to compute paths to 1855 potentially avoid nodes with their overload bit set are outside 1856 the scope of this document, but it is RECOMMENDED to avoid 1857 frequent changes of this bit to avoid routing oscillations. When 1858 set, this indicates that the node is overloaded and may not be 1859 able to process traffic. 1861 They MUST be set to zero on transmission and MUST be ignored on 1862 receipt. 1864 The Flag field of the NSA Routing Metric/Constraint object is managed 1865 by IANA. Unassigned bits are considered as reserved. 1867 3.2. Node Energy Object 1869 It may sometimes be desirable to avoid selecting a node with low 1870 residual energy as a router, thus the support for constraint-based 1871 routing is needed. In such cases, the routing protocol engine may 1872 compute a longer path (constraint based) for some traffic in order to 1873 increase the network life duration. 1875 Power and energy are clearly critical resources in most LLNs. As yet 1876 there is no simple abstraction which adequately covers the broad 1877 range of power sources and energy storage devices used in existing 1878 LLN nodes. These include mains-powered, primary batteries, energy 1879 scavengers, and a variety of secondary storage mechanisms. 1880 Scavengers may provide a reliable low level of power, such as might 1881 be available from a 4-20mA loop; a reliable but periodic stream of 1882 power, such as provided by a well-positioned solar cell; or 1883 unpredictable power, such as might be provided by a vibrational 1884 energy scavenger on an intermittently powered pump. Routes which are 1885 viable when the sun is shining may disappear at night. A pump 1886 turning on may connect two previously disconnected sections of a 1887 network. 1889 Storage systems like rechargeable batteries often suffer substantial 1890 degradation if regularly used to full discharge, leading to different 1891 residual energy numbers for regular versus emergency operation. A 1892 route for emergency traffic may have a different optimum than one for 1893 regular reporting. 1895 Batteries used in LLNs often degrade substantially if their average 1896 current consumption exceeds a small fraction of the peak current that 1897 they can deliver. It is not uncommon for self-supporting nodes to 1898 have a combination of primary storage, energy scavenging, and 1899 secondary storage, leading to three different values for acceptable 1900 average current depending on the time frame being considered, e.g. 1901 milliseconds, seconds, and hours/years. 1903 Raw power and energy values are meaningless without knowledge of the 1904 energy cost of sending and receiving packets, and lifetime estimates 1905 have no value without some higher-level constraint on the lifetime 1906 required of a device. In some cases the path that exhausts the 1907 battery of a node on the bed table in a month may be preferable to a 1908 route that reduces the lifetime of a node in the wall to a decade. 1910 Given the complexity of trying to address such a broad collection of 1911 constraints, this document defines two levels of fidelity in the 1912 solution. 1914 The simplest solution relies on a 2-bit field encoding three types of 1915 power sources: "powered", "battery", "scavenger". This simple 1916 approach may be sufficient for many applications. 1918 The mid-complexity solution is a single parameter that can be used to 1919 encode the energetic happiness of both battery powered and scavenging 1920 nodes. For scavenging nodes, the 8 bit quantity is the power 1921 provided by the scavenger divided by the power consumed by the 1922 application, E-E=P_in/P_out, in units of percent. Nodes which are 1923 scavenging more power than they are consuming will register above 1924 100. A good time period for averaging power in this calculation may 1925 be related to the discharge time of the energy storage device on the 1926 node, but specifying this is out of the scope of this document. For 1927 battery powered devices, E-E is the current expected lifetime divided 1928 by the desired minimum lifetime, in units of percent. The estimation 1929 of remaining battery energy and actual power consumption can be 1930 difficult, and the specifics of this calculation are out of scope of 1931 this document, but two examples are presented. If the node can 1932 measure its average power consumption, then H can be calculated as 1933 the ratio of desired max power (initial energy E_0 divided by desired 1934 lifetime T) to actual power, E-E=P_max/P_now. Alternatively, if the 1935 energy in the battery E_bat can be estimated, and the total elapsed 1936 lifetime, t, is available, then H can be calculated as the total 1937 stored energy remaining versus the target energy remaining: E-E= 1938 E_bat / [E_0 (T-t)/T]. 1940 An example of optimized route is max(min(H)) for all battery operated 1941 nodes along the route, subject to the constraint that E-E>=100 for 1942 all scavengers along the route. 1944 Note that the estimated percentage of remaining energy indicated in 1945 the E-E field may not be useful in the presence of nodes powered by 1946 battery or energy scavengers when the amount of energy accumulated by 1947 the device significantly differ. Indeed, X% of remaining energy on a 1948 node that can store a large amount of energy cannot be easily 1949 compared to the same percentage of remaining energy on a node powered 1950 by a tiny source of energy. That being said, in networks where nodes 1951 have relatively close energy storage, such a percentage of remaining 1952 energy is useful. 1954 The Node Energy (NE) object is used to provide information related to 1955 node energy and may be used as a metric or as constraint. 1957 The NE object MAY be present in the DAG Metric Container. There MUST 1958 NOT be more than one NE object as a constraint per DAG Metric 1959 Container, and there MUST NOT be more than one NE object as a metric 1960 per DAG Metric Container. 1962 The NE object Type is to be assigned by IANA (recommended value=2). 1964 The format of the NE object body is as follows: 1966 0 1 2 1967 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 1968 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ... 1969 | NE Sub-objects 1970 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ... 1972 Figure 3: NE sub-object format 1974 The format of the NE sub-object body is as follows: 1976 0 1 2 1977 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 1978 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ... 1979 | Flags |I| T |E| E-E | Optional TLVs 1980 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ... 1982 Figure 4: NE sub-object format 1984 The NE sub-object may also contain a set of TLVs used to convey 1985 various nodes' characteristics. 1987 Flags field (8 bits). The following flags are currently defined: 1989 o I (Included): the I bit is only relevant when the node type is 1990 used as a constraint. For example, the path must only traverse 1991 mains-powered nodes. Conversely, battery operated nodes must be 1992 excluded. The I bit is used to stipulate inclusion versus 1993 exclusion. When set, this indicates that nodes of the type 1994 specified in the node type field MUST be included. Conversely, 1995 when cleared, this indicates that nodes of type specified in the 1996 node type field MUST be excluded. 1998 o T (node Type): 2-bit field indicating the node type. T=0x00 1999 designates a mains-powered node, T=0x01 a battery-powered node and 2000 T=0x02 a node powered by an energy scavenger. 2002 o E (Estimation): when the E bit is set for a metric, the estimated 2003 percentage of remaining energy on the node is indicated in the E-E 2004 8-bit field. When cleared, the estimated percentage of remaining 2005 energy is not provided. When the E bit is set for a constraint, 2006 the E-E field defines a threshold for the inclusion/exclusion: if 2007 an inclusion, nodes with values higher than the threshold are to 2008 be included; if an exclusion, nodes with values lower than the 2009 threshold are to be excluded. 2011 E-E (Estimated-Energy): 8-bit unsigned integer field indicating an 2012 estimated percentage of remaining energy. The E-E field is only 2013 relevant when the E flag is set, and MUST be set to 0 when the E flag 2014 is cleared. 2016 If the NE object comprises several sub-objects when used as a 2017 constraint, each sub-object adds or subtracts node subsets as the 2018 sub-objects are parsed in order. The initial set (full or empty) is 2019 defined by the I bit of the first sub-object: full if that I bit is 2020 an exclusion, empty if that I bit is an inclusion. 2022 No TLV is currently defined. 2024 Future documents may define more complex solutions involving TLV 2025 parameters representing energy storage, consumption, and generation 2026 capabilities of the node, as well as desired lifetime. 2028 3.3. Hop-Count Object 2030 The HoP-Count (HP) object is used to report the number of traversed 2031 nodes along the path. 2033 The HP object MAY be present in the DAG Metric Container. There MUST 2034 NOT be more than one HP object as a constraint per DAG Metric 2035 Container, and there MUST NOT be more than one HP object as a metric 2036 per DAG Metric Container. 2038 The HP object may also contain a set of TLVs used to convey various 2039 node characteristics. No TLV is currently defined. 2041 The HP routing metric object Type is to be assigned by IANA 2042 (recommended value=3) 2043 The format of the Hop Count object body is as follows: 2045 0 1 2 2046 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 2047 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ... 2048 | Res | Flags | Hop Count | Optional TLVs 2049 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ... 2051 Figure 5: Hop Count object body format 2053 Res flags (4 bits): Reserved field. This field MUST be set to zero 2054 on transmission and MUST be ignored on receipt. 2056 No Flag is currently defined. Unassigned bits are considered as 2057 reserved. They MUST be set to zero on transmission and MUST be 2058 ignored on receipt. 2060 The HP object may be used as a constraint or a metric. When used as 2061 a constraint, the DAG root indicates the maximum number of hops that 2062 a path may traverse. When that number is reached, no other node can 2063 join that path. When used as a metric, each visited node simply 2064 increments the Hop Count field. 2066 Note that the first node along a path inserting a Hop-count object 2067 MUST set the Hop Count field value to 1. 2069 4. Link Metric/Constraint Objects 2071 4.1. Throughput 2073 Many LLNs support a wide range of throughputs. For some links, this 2074 may be due to variable coding. For the deeply duty-cycled links 2075 found in many LLNs, the variability comes as a result of trading 2076 power consumption for bit rate. There are several MAC layer 2077 protocols which allow for the effective bit rate of a link to vary 2078 over more than three orders of magnitude with a corresponding change 2079 in power consumption. For efficient operation, it may be desirable 2080 for nodes to report the range of throughput that their links can 2081 handle in addition to the currently available throughput. 2083 The Throughput object MAY be present in the DAG Metric Container. 2084 There MUST NOT be more than one Throughput object as a constraint per 2085 DAG Metric Container, and there MUST NOT be more than one Throughput 2086 object as a metric per DAG Metric Container. 2088 The Throughput object is made of throughput sub-objects and MUST at 2089 least comprise one Throughput sub-object. The first Throughput sub- 2090 object MUST be the most recently estimated actual throughput. The 2091 actual estimation of the throughput is outside the scope of this 2092 document. 2094 Each Throughput sub-object has a fixed length of 4 bytes. 2096 The Throughput object does not contain any additional TLV. 2098 The Throughput object Type is to be assigned by IANA (recommended 2099 value=4) 2101 The format of the Throughput object body is as follows: 2103 0 1 2104 0 1 2 3 4 5 6 7 8 9 0 1 2 3 2105 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2106 | (sub-object) ..... 2107 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2109 Figure 6: Throughput object body format 2111 0 1 2 3 2112 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2113 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2114 | Throughput | 2115 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2117 Figure 7: Throughput sub-object format 2119 Throughput: 32 bits. The Throughput is encoded in 32 bits in 2120 unsigned integer format, expressed in bytes per second. 2122 4.2. Latency 2124 Similarly to throughput, the latency of many LLN MAC sub-layers can 2125 vary over many orders of magnitude, again with a corresponding change 2126 in power consumption. Some LLN MAC link layers will allow the 2127 latency to be adjusted globally on the subnet, on a link-by-link 2128 basis, or not at all. Some will insist that it be fixed for a given 2129 link, but allow it to be variable from link to link. 2131 The Latency object MAY be present in the DAG Metric Container. There 2132 MUST NOT be more than one Latency object as a constraint per DAG 2133 Metric Container, and there MUST NOT be more than one Latency object 2134 as a metric per DAG Metric Container. 2136 The Latency object is made of Latency sub-objects and MUST at least 2137 comprise one Latency sub-object. Each Latency sub-object has a fixed 2138 length of 4 bytes. 2140 The Latency object does not contain any additional TLV. 2142 The Latency object Type is to be assigned by IANA (recommended 2143 value=5) 2145 The Latency object is a metric or constraint. 2147 The format of the Latency object body is as follows: 2149 0 1 2150 0 1 2 3 4 5 6 7 8 9 0 1 2 3 2151 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2152 | (sub-object) ..... 2153 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2155 Figure 8: Latency object body format 2157 0 1 2 3 2158 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2159 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2160 | Latency | 2161 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2163 Figure 9: Latency sub-object format 2165 Latency: 32 bits. The Latency is encoded in 32 bits in unsigned 2166 integer format, expressed in microseconds. 2168 The Latency object may be used as a constraint or a path metric. For 2169 example, one may want the latency not to exceed some value. In this 2170 case, the Latency object common header indicates that the provided 2171 value relates to a constraint. In another example, the Latency 2172 object may be used as an aggregated additive metric where the value 2173 is updated along the path to reflect the path latency. 2175 4.3. Link Reliability 2177 In LLNs, link reliability is degraded by external interference and 2178 multi-path interference (wireless links). Multipath typically 2179 affects both directions on the link equally, whereas external 2180 interference is sometimes unidirectional. Time scales vary from 2181 milliseconds to days, and are often periodic and linked to human 2182 activity. Packet error rates can generally be measured directly, and 2183 other metrics (e.g. bit error rate, mean time between failures) are 2184 typically derived from that. Note that such variability is not 2185 specific to wireless link but also applies to PLC links. 2187 A change in link quality can affect network connectivity, thus, link 2188 quality may be taken into account as a critical routing metric. 2190 A number of link reliability metrics could be defined reflecting 2191 several reliability aspects. Two link reliability metrics are 2192 defined in this document: the Link Quality Level (LQL) and the 2193 Expected Transmission count Metric (ETX). 2195 Note that an RPL deployment MAY either use the LQL, the ETX or both. 2197 4.3.1. The Link Quality Level Reliability Metric 2199 The Link Quality Level (LQL) object is used to quantify the link 2200 reliability using a discrete value, from 0 to 7 where 0 indicates 2201 that the link quality level is unknown and 1 reports the highest link 2202 quality level. The mechanisms and algorithms used to compute the LQL 2203 are implementation specific and outside of the scope of this 2204 document. 2206 The LQL can either be used as a metric or a constraint. When used as 2207 a metric, the LQL metric can only be recorded. For example, the DAG 2208 Metric object may request all traversed nodes to record the LQL of 2209 their incoming link into the LQL object. Each node can then use the 2210 LQL record to select its parent based on some user defined rules 2211 (e.g. something like "select the path with most links reporting a LQL 2212 value of 3 or less"). 2214 Counters are used to compress the information: for each encountered 2215 LQL value, only the number of matching links is reported. 2217 The LQL object MAY be present in the DAG Metric Container. There 2218 MUST NOT be more than one LQL object as a constraint per DAG Metric 2219 Container, and there MUST NOT be more than one LQL object as a metric 2220 per DAG Metric Container. 2222 The LQL object MUST contain one or more sub-object used to report the 2223 number of links along with their LQL. 2225 The LQL object Type is to be assigned by IANA (recommended value=6) 2226 The format of the LQL object body is as follows: 2228 0 1 2 2229 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 2230 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ... 2231 | Res | LQL sub-object 2232 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ... 2234 Figure 10: LQL object body format 2236 Res flags (8 bits): Reserved field. This field MUST be set to zero 2237 on transmission and MUST be ignored on receipt. 2239 When the LQL metric is recorded, the LQL object body comprises one or 2240 more LQL Type 1 sub-object. 2242 The format of the LQL Type 1 sub-object is as follows 2244 0 2245 0 1 2 3 4 5 6 7 2246 +-+-+-+-+-+-+-+-+ 2247 | Val | Counter | 2248 +-+-+-+-+-+-+-+-+ 2250 Figure 11: LQL Type 1 sub-object format 2252 Val: LQL value from 0 to 7 where 0 means undetermined and 1 indicates 2253 the highest link quality. 2255 Counter: number of links with that value. 2257 4.3.2. The Expected Transmission Count (ETX) reliability object 2259 The Expected Transmission Count (ETX) metric is the number of 2260 transmissions a node expects to make to a destination in order to 2261 successfully deliver a packet. In contrast with the LQL routing 2262 metric, the ETX provides a discrete value (which may not be an 2263 integer) computed according to a specific formula: for example, an 2264 implementation may use the following formula: ETX= 1 / (Df * Dr) 2265 where Df is the measured probability that a packet is received by the 2266 neighbor and Dr is the measured probability that the acknowledgment 2267 packet is successfully received. This document does not mandate the 2268 use of a specific formula to compute the ETX value. 2270 The ETX object MAY be present in the DAG Metric Container. There 2271 MUST NOT be more than one ETX object as a constraint per DAG Metric 2272 Container, and there MUST NOT be more than one ETX object as a metric 2273 per DAG Metric Container. 2275 The ETX object is made of ETX sub-objects and MUST at least comprise 2276 one ETX sub-object. Each ETX sub-object has a fixed length of 8 2277 bits. 2279 The ETX object does not contain any additional TLV. 2281 The ETX object Type is to be assigned by IANA (recommended value=7) 2283 The format of the ETX object body is as follows: 2285 0 1 2286 0 1 2 3 4 5 6 7 8 9 0 1 2 3 2287 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2288 | (sub-object) ..... 2289 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2291 Figure 12: ETX object body format 2293 0 1 2294 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 2295 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2296 | ETX | 2297 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2299 Figure 13: ETX sub-object format 2301 ETX: 16 bits. The ETX * 128 is encoded using 16 bits in unsigned 2302 integer format, rounded off to the nearest whole number. For 2303 example, if ETX = 3.569, the object value will be 457. If ETX > 2304 511.9921875, the object value will be the maximum which is 65535. 2306 The ETX object may be used as a constraint or a path metric. For 2307 example, it may be required that the ETX must not exceed some 2308 specified value. In this case, the ETX object common header 2309 indicates that the value relates to a constraint. In another 2310 example, the ETX object may be used as an aggregated additive metric 2311 where the value is updated along the path to reflect the path 2312 quality: when a node receives the aggregated additive ETX value of 2313 the path (cummulative path ETX calculated as the sum of the link ETX 2314 of all of the traversed links from the advertising node to the DAG 2315 root), if it selects that node as its preferred parent, the node 2316 updates the path ETX by adding the ETX of the local link between 2317 itself and the preferred parent to the received path cost (path ETX) 2318 before potentially advertising itself the new path ETX. 2320 4.4. Link Color Object 2322 4.4.1. Link Color Object Description 2324 The Link Color (LC) object is an administrative 10-bit link 2325 constraint (which may either be static or dynamically adjusted) used 2326 to avoid or attract specific links for specific traffic types. 2328 The LC object can either be used as a metric or as a constraint. 2329 When used as a metric, the LC metric can only be recorded. For 2330 example, the DAG may require recording the link colors for all 2331 traversed links. A color is defined as a specific set of bit values: 2332 in other words, that 10-bit field is a flag field, and not a scalar 2333 value. Each node can then use the LC to select the parent based on 2334 user defined rules (e.g. "select the path with the maximum number of 2335 links having their first bit set 1 (e.g. encrypted links)"). The LC 2336 object may also be used as a constraint. 2338 When used as a recorded metric, a counter is used to compress the 2339 information where the number of links for each Link Color is 2340 reported. 2342 The Link Color (LC) object MAY be present in the DAG Metric 2343 Container. There MUST NOT be more than one LC object as a constraint 2344 per DAG Metric Container, and there MUST NOT be more than one LC 2345 object as a metric per DAG Metric Container. 2347 There MUST be a at least one LC sub-object per LC object. 2349 The LC object does not contain any additional TLV. 2351 The LC object Type is to be assigned by IANA (recommended value=8) 2353 The format of the LC object body is as follows: 2355 0 1 2 2356 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 2357 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ... 2358 | Res | LC sub-objects 2359 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ... 2361 Figure 14: LC object format 2363 Res flags (8 bits): Reserved field. This field MUST be set to zero 2364 on transmission and MUST be ignored on receipt. 2366 When the LC object is used as a recorded metric, the LC object body 2367 comprises one or more LC Type 1 sub-objects. 2369 The format of the LC Type 1 sub-object body is as follows: 2371 0 1 2372 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 2373 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2374 | Link Color | Counter | 2375 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2377 Figure 15: LC Type 1 sub-object format 2379 When the LC object is used as a constraint, the LC object body 2380 comprises one or more LC Type 2 sub-objects. 2382 The format of the LC Type 2 sub-object body is as follows: 2384 0 1 2385 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 2386 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2387 | Link Color |Reserved |I| 2388 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2390 Figure 16: LC Type 2 sub-object format 2392 Res flags (7 bits): Reserved field. This field MUST be set to zero 2393 on transmission and MUST be ignored on receipt. 2395 I Bit: The I bit is only relevant when the Link Color is used as a 2396 constraint. When cleared, this indicates that links with the 2397 specified color must be included. When set, this indicates that 2398 links with the specified color must be excluded. 2400 It is left to the implementer to define the meaning of each bit of 2401 the 10-bit Link Color Flag field. 2403 4.4.2. Mode of operation 2405 The link color may be used as a constraint or a metric. 2407 o When used as constraint, the LC object may be inserted in the DAG 2408 Metric Container to indicate that links with a specific color 2409 should be included or excluded from the computed path. 2411 o When used as recorded metric, each node along the path may insert 2412 a LC object in the DAG Metric Container to report the color of the 2413 local link. If there is already a LC object reporting a similar 2414 color, the node MUST NOT add another identical LC sub-object and 2415 MUST increment the counter field. 2417 5. Computation of Dynamic Metrics and Attributes 2419 As already pointed out, dynamically calculated metrics are of the 2420 utmost importance in many circumstances in LLNs. This is mainly 2421 because a variety of metrics change on a frequent basis, thus 2422 implying the need to adapt the routing decisions. That being said, 2423 care must be given to the pace at which changes are reported in the 2424 network. The attributes will change according to their own time 2425 scales. RPL controls the reporting rate. 2427 To minimize metric updates, multi-threshold algorithms MAY be used to 2428 determine when updates should be sent. When practical, low-pass 2429 filtering and/or hysteresis should be used to avoid rapid 2430 fluctuations of these values. Finally, although the specification of 2431 path computation algorithms using dynamic metrics are out the scope 2432 of this document, it is RECOMMENDED to carefully design the route 2433 optimization algorithm to avoid too frequent computation of new 2434 routes upon metric values changes. 2436 Controlled adaptation of the routing metrics and rate at which paths 2437 are computed are critical to avoid undesirable routing instabilities 2438 resulting in increased latencies and packet loss because of temporary 2439 micro-loops. Furthermore, excessive route changes will adversely 2440 impact the traffic and power consumption in the network, thus 2441 potentially impacting its scalability. 2443 6. IANA Considerations 2445 IANA is requested to establish a new top-level registry to contain 2446 all Routing Metric/Constraint objects codepoints and sub-registries. 2448 The allocation policy for each new registry is by IETF review: new 2449 values are assigned through the IETF review process (see [RFC5226]). 2450 Specifically, new assignments are made via RFCs approved by the IESG. 2451 Typically, the IESG will seek input on prospective assignments from 2452 appropriate persons (e.g., a relevant Working Group if one exists). 2454 New bit numbers may be allocated only by an IETF Review action. Each 2455 bit should be tracked with the following qualities: 2457 o Bit number 2459 o Capability Description 2461 o Defining RFC 2463 6.1. Routing Metric/Constraint Type 2465 IANA is requested to create a registry for Routing Metric/Constraint 2466 objects. Each Routing Metric/Constraint object has a type value 2467 (from 1 to 255). 2469 Value Meaning Reference 2470 1 Node State and Attribute This document 2471 2 Node Energy This document 2472 3 Hop Count This document 2473 4 Link Throughput This document 2474 5 Link Latency This document 2475 6 Link Quality Level This document 2476 7 Link ETX This document 2477 8 Link Color This document 2479 6.2. Routing Metric/Constraint TLV 2481 IANA is requested to create a registry used for all TLVs carried 2482 within Routing Metric/Constraint objects. The type field is an 8-bit 2483 field whose value can be comprised between 1 and 255. 2485 6.3. Routing Metric/Constraint Common Header 2487 IANA is requested to create a registry to manage the Flag field of 2488 the Routing Metric/Constraint common header. 2490 Several bits are defined for the Routing Metric/Constraint common 2491 header in this document. The following values have been assigned: 2493 Codespace of the Flag field (Routing Metric/Constraint common header) 2494 Bit Description Reference 2496 12-15 Precedence This document 2497 9-11 Additive/Max/Min/Multi This document 2498 8 Recorded/Aggregated This document 2499 7 Optional Constraint This document 2500 6 Constraint/Metric This document 2501 5 P (Partial) This document 2503 IANA is requested to create a registry to manage the codespace of the 2504 A field of the Routing Metric/Constraint common header. 2506 Codespace of the A field (Routing Metric/Constraint common header) 2507 Value Meaning Reference 2509 0 Routing metric is additive This document 2510 1 Routing metric reports a maximum This document 2511 2 Routing metric reports a minimum This document 2512 3 Routing metric is multiplicative This document 2514 6.4. NSA Object 2516 IANA is requested to create a registry to manage the codespace of the 2517 Flag field of the NSA object. 2519 Several bits are defined for the NSA object flag field in this 2520 document. The following values have been assigned: 2522 Codespace of the Flag field (NSA object) 2523 Bit Description Reference 2525 14 Aggregator This document 2526 15 Overloaded This document 2528 6.5. Hop-Count Object 2530 IANA is requested to create a registry to manage the codespace of the 2531 Flag field of the Hop-count object. 2533 No Flag is currently defined. 2535 7. Security Considerations 2537 Routing metrics should be handled in a secure and trustful manner. 2538 For instance, RPL should not allow a malicious node to falsely 2539 advertise that it has good metrics for routing, be added as a router 2540 for other nodes' traffic and intercept packets. Another attack may 2541 consist of making intermitment attacks on a link in an attempt to 2542 constantly modify the link quality and consequently the associated 2543 routing metric, thus leading to potential fluctuation in the DODAG. 2544 It is thus RECOMMENDED for a RPL implementation to put in place 2545 mechanism so as to stop advertising routing metrics for highly 2546 unstable links that may be subject to attacks. 2548 Some routing metrics may also be used to identify some areas of 2549 weaknesses in the network (a highly unreliable link, a node running 2550 low in terms of energy, etc.). Such information may be used by a 2551 potential attacker. Thus, it is RECOMMENDED to carefully consider 2552 which metrics should be used by RPL and the level of visibility that 2553 they provide about the network state or to use appropriate the 2554 security measures as specified in [I-D.ietf-roll-rpl] to protect that 2555 information. 2557 Since the routing metrics/constraints are carried within RPL message, 2558 the security routing mechanisms defined in [I-D.ietf-roll-rpl] 2559 applies here. 2561 8. Acknowledgements 2563 The authors would like to acknowledge the contributions of Young Jae 2564 Kim, Hakjin Chong, David Meyer, Mischa Dohler, Anders Brandt, Philip 2565 Levis, Pascal Thubert, Richard Kelsey, Jonathan Hui, Alexandru 2566 Petrescu, Richard Kelsey, Mathilde Durvy, Phoebus Chen, Tim Winter, 2567 Mukul Goyal, Yoav Ben-Yehezkel, Matteo Paris, Omprakash Gnawali, Mads 2568 Westergreen, Mukul Goyal, Joseph Saloway and David Culler for their 2569 review and valuable comments. Special thank to Adrian Farrel for his 2570 thourough review. 2572 9. References 2574 9.1. Normative references 2576 [I-D.ietf-roll-rpl] 2577 Winter, T., Thubert, P., Brandt, A., Clausen, T., Hui, J., 2578 Kelsey, R., Levis, P., Pister, K., Struik, R., and J. 2579 Vasseur, "RPL: IPv6 Routing Protocol for Low power and 2580 Lossy Networks", draft-ietf-roll-rpl-17 (work in 2581 progress), December 2010. 2583 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 2584 Requirement Levels", BCP 14, RFC 2119, March 1997. 2586 [RFC5226] Narten, T. and H. Alvestrand, "Guidelines for Writing an 2587 IANA Considerations Section in RFCs", BCP 26, RFC 5226, 2588 May 2008. 2590 9.2. Informative references 2592 [I-D.ietf-roll-terminology] 2593 Vasseur, J., "Terminology in Low power And Lossy 2594 Networks", draft-ietf-roll-terminology-04 (work in 2595 progress), September 2010. 2597 [RFC1195] Callon, R., "Use of OSI IS-IS for routing in TCP/IP and 2598 dual environments", RFC 1195, December 1990. 2600 [RFC2328] Moy, J., "OSPF Version 2", STD 54, RFC 2328, April 1998. 2602 [RFC2702] Awduche, D., Malcolm, J., Agogbua, J., O'Dell, M., and J. 2603 McManus, "Requirements for Traffic Engineering Over MPLS", 2604 RFC 2702, September 1999. 2606 [RFC3209] Awduche, D., Berger, L., Gan, D., Li, T., Srinivasan, V., 2607 and G. Swallow, "RSVP-TE: Extensions to RSVP for LSP 2608 Tunnels", RFC 3209, December 2001. 2610 [RFC5548] Dohler, M., Watteyne, T., Winter, T., and D. Barthel, 2611 "Routing Requirements for Urban Low-Power and Lossy 2612 Networks", RFC 5548, May 2009. 2614 [RFC5673] Pister, K., Thubert, P., Dwars, S., and T. Phinney, 2615 "Industrial Routing Requirements in Low-Power and Lossy 2616 Networks", RFC 5673, October 2009. 2618 [RFC5826] Brandt, A., Buron, J., and G. Porcu, "Home Automation 2619 Routing Requirements in Low-Power and Lossy Networks", 2620 RFC 5826, April 2010. 2622 [RFC5867] Martocci, J., De Mil, P., Riou, N., and W. Vermeylen, 2623 "Building Automation Routing Requirements in Low-Power and 2624 Lossy Networks", RFC 5867, June 2010. 2626 Authors' Addresses 2628 JP Vasseur (editor) 2629 Cisco Systems, Inc 2630 11, Rue Camille Desmoulins 2631 Issy Les Moulineaux, 92782 2632 France 2634 Email: jpv@cisco.com 2636 Mijeom Kim (editor) 2637 Corporate Technology Group, KT 2638 17 Woomyeon-dong, Seocho-gu 2639 Seoul, 137-792 2640 Korea 2642 Email: mjkim@kt.com 2643 Kris Pister 2644 Dust Networks 2645 30695 Huntwood Ave. 2646 Hayward, CA 95544 2647 USA 2649 Email: kpister@dustnetworks.com 2651 Nicolas Dejean 2652 Coronis SAS 2653 Espace Concorde, 120 impasse JB Say 2654 Perols, 34470 2655 France 2657 Email: nicolas.dejean@coronis.com 2659 Dominique Barthel 2660 France Telecom Orange 2661 28 chemin du Vieux Chene, BP 98 2662 Meylan, 38243 2663 France 2665 Email: dominique.barthel@orange-ftgroup.com