idnits 2.17.1 draft-ietf-roll-routing-metrics-00.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** The document seems to lack a License Notice according IETF Trust Provisions of 28 Dec 2009, Section 6.b.i or Provisions of 12 Sep 2009 Section 6.b -- however, there's a paragraph with a matching beginning. Boilerplate error? (You're using the IETF Trust Provisions' Section 6.b License Notice from 12 Feb 2009 rather than one of the newer Notices. See https://trustee.ietf.org/license-info/.) Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. 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 (April 29, 2009) is 5448 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) == Missing Reference: 'Khanna1989' is mentioned on line 140, but not defined == Outdated reference: A later version (-09) exists of draft-ietf-roll-building-routing-reqs-05 == Outdated reference: A later version (-11) exists of draft-ietf-roll-home-routing-reqs-06 == Outdated reference: A later version (-06) exists of draft-ietf-roll-indus-routing-reqs-05 == Outdated reference: A later version (-13) exists of draft-ietf-roll-terminology-00 Summary: 1 error (**), 0 flaws (~~), 6 warnings (==), 1 comment (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 1 Networking Working Group M. Kim, Ed. 2 Internet-Draft Future Tech Lab., Korea Telecom 3 Intended status: Standards Track JP. Vasseur, Ed. 4 Expires: October 31, 2009 Cisco Systems, Inc 5 K. Pister 6 Dust Networks 7 H. Chong 8 Future Tech Lab., Korea Telecom 9 April 29, 2009 11 Routing Metrics used for Path Calculation in Low Power and Lossy 12 Networks 13 draft-ietf-roll-routing-metrics-00 15 Status of this Memo 17 This Internet-Draft is submitted to IETF in full conformance with the 18 provisions of BCP 78 and BCP 79. 20 Internet-Drafts are working documents of the Internet Engineering 21 Task Force (IETF), its areas, and its working groups. Note that 22 other groups may also distribute working documents as Internet- 23 Drafts. 25 Internet-Drafts are draft documents valid for a maximum of six months 26 and may be updated, replaced, or obsoleted by other documents at any 27 time. It is inappropriate to use Internet-Drafts as reference 28 material or to cite them other than as "work in progress." 30 The list of current Internet-Drafts can be accessed at 31 http://www.ietf.org/ietf/1id-abstracts.txt. 33 The list of Internet-Draft Shadow Directories can be accessed at 34 http://www.ietf.org/shadow.html. 36 This Internet-Draft will expire on October 31, 2009. 38 Copyright Notice 40 Copyright (c) 2009 IETF Trust and the persons identified as the 41 document authors. All rights reserved. 43 This document is subject to BCP 78 and the IETF Trust's Legal 44 Provisions Relating to IETF Documents in effect on the date of 45 publication of this document (http://trustee.ietf.org/license-info). 46 Please review these documents carefully, as they describe your rights 47 and restrictions with respect to this document. 49 Abstract 51 This document specifies routing metrics to be used in path 52 calculation for Routing Over Low power and Lossy networks (ROLL). 53 Low power and Lossy Networks (LLNs) have unique characteristics 54 compared with traditional wired networks or even with similar ones 55 such as mobile ad-hoc networks. By contrast with typical Interior 56 Gateway Protocol (IGP) routing metrics using hop counts or link 57 attributes, this document specifies a set of routing metrics suitable 58 to LLNs. 60 Requirements Language 62 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 63 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 64 document are to be interpreted as described in RFC 2119 [RFC2119]. 66 Table of Contents 68 1. Note . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 69 2. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 4 70 3. Node Metrics and Attributes . . . . . . . . . . . . . . . . . 6 71 3.1. Node Memory Resources . . . . . . . . . . . . . . . . . . 6 72 3.2. Node CPU Resources . . . . . . . . . . . . . . . . . . . . 6 73 3.3. Node Residual Energy . . . . . . . . . . . . . . . . . . . 6 74 3.4. Node Overload State . . . . . . . . . . . . . . . . . . . 7 75 3.5. Data Aggregation Attribute . . . . . . . . . . . . . . . . 8 76 4. Link Metrics and Attributes . . . . . . . . . . . . . . . . . 8 77 4.1. Throughput . . . . . . . . . . . . . . . . . . . . . . . . 8 78 4.2. Latency . . . . . . . . . . . . . . . . . . . . . . . . . 8 79 4.3. Link reliability . . . . . . . . . . . . . . . . . . . . . 9 80 4.4. Link Coloring . . . . . . . . . . . . . . . . . . . . . . 9 81 5. Computation of Dynamic Metrics and Attributes . . . . . . . . 9 82 6. Open Issues . . . . . . . . . . . . . . . . . . . . . . . . . 10 83 7. Metric Consistency . . . . . . . . . . . . . . . . . . . . . . 10 84 8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 10 85 9. Security Considerations . . . . . . . . . . . . . . . . . . . 10 86 10. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 10 87 11. References . . . . . . . . . . . . . . . . . . . . . . . . . . 11 88 11.1. Normative References . . . . . . . . . . . . . . . . . . . 11 89 11.2. Informative References . . . . . . . . . . . . . . . . . . 11 90 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 12 92 1. Note 94 The first revision of this document has been published with a number 95 of link and node metrics. 97 After several discussions on the mailing list and during Working 98 Group meetings, it was decided to reduce the number of these metrics 99 to the strict required minimum. 101 In the revision 02, highly dynamic and application/implementation 102 dependent attributes have been removed (such as node degree and node 103 latency) since they may be too CPU intensive for constrained devices 104 and lead to routing oscillations. Link and node metrics packet 105 format or methods to encode the data will be defined in a further 106 revision of this document. 108 2. Introduction 110 This document makes use of the terminology defined in 111 [I-D.ietf-roll-terminology]. 113 This document specifies routing metrics to be used in path 114 calculation for Routing Over Low power and Lossy networks (ROLL). 115 Low power and Lossy Networks (LLNs) have specific routing 116 characteristics compared with traditional wired networks or even with 117 similar ones such as mobile ad-hoc networks that lead to a set of 118 specific requirements listed [I-D.ietf-roll-indus-routing-reqs], 119 [I-D.ietf-roll-home-routing-reqs] [I-D.ietf-roll-urban-routing-reqs] 120 and [I-D.ietf-roll-building-routing-reqs]. 122 Routing metrics can be classified according to the following set of 123 characteristics: 125 o Link versus Node metrics 127 o Qualitative versus quantitative 129 o Dynamic or static 131 Historically, IGP such as OSPF ([RFC2328]) and IS-IS ([RFC1195]) have 132 used quantitative static link metrics. Other mechanisms such as 133 Multiprotocol Label Switching (MPLS) Traffic Engineering (TE) (see 134 [RFC2702] and [RFC3209]) make use of other link attributes such as 135 the available reserved bandwidth, affinities and so on to compute 136 constrained shortest paths for Traffic Engineering Label Switched 137 Paths (TE LSPs). 139 It must be noted that the use of dynamic metrics is not new and has 140 been experimented in ARPANET 2 [Khanna1989], with moderate success. 141 Indeed, the use of dynamic metrics is not trivial and very careful 142 care must be given to the use of dynamic metrics that may lead to 143 potential routing instabilities. 145 As pointed out in various routing requirements documents (see 146 [I-D.ietf-roll-indus-routing-reqs], [I-D.ietf-roll-home-routing-reqs] 147 [I-D.ietf-roll-urban-routing-reqs] and 148 [I-D.ietf-roll-building-routing-reqs]), a variety of nodes 149 constraints must be taken into account during path computation (e.g. 150 node's resources such as memory, energy and CPU computational power). 151 Moreover, node attributes such as the ability to act as an aggregator 152 (node capable of performing data aggregation) may be of interest. 154 It is also worth mentioning that it fairly common for link in LLNs to 155 have fast changing node and link charateristics, which must be taken 156 into account carefully when specifying link metrics. For instance, 157 in addition to the normal dynamic nature of wireless connectivity, 158 nodes' resources such as residual energy and available memory are 159 changing continuously and may have to be taken into account during 160 the path computation. Similarly, link attributes including 161 throughput and reliability may drastically change over time due to 162 multi-path interference. That being said, very careful attention 163 must be given when using dynamic metrics and attributes that affect 164 routing decisions in order to preserve routing stability. 165 Furthermore, it is a time and energy consuming process to update 166 these dynamic metrics and recompute the routing tables on a frequent 167 basis. Therefore, it may be desirable to use a reduced set of 168 discrete values to reduce computational overhead and bandwidth 169 utilization. Of course, this comes with a cost, namely, reduced 170 metric accuracy. 172 Reliability is an example of qualitative parameters which is 173 necessary as a routing metric for path calculation. Such qualitative 174 parameters may be transformed to quantitative values. In other 175 cases, a set of flags may be defined to reflect a node state without 176 having to define discrete values to reflect that state. 178 Some link or node attributes (e.g. level of link reliability, energy 179 remaining on the node) can be used to perform constraint-based 180 routing. It is not required to use all the metrics and attributes 181 specified in this document. A particular implementation MAY use a 182 subset or all of the metrics defined in this document. The 183 requirements on reporting frequency may differ among metrics, thus 184 different reporting rates may be used for each category. 186 The specification of the objective function used to compute the path 187 is out of the scope of this document. 189 3. Node Metrics and Attributes 191 In some cases, node metrics and attributes are static. However, 192 critical metrics such as residual power will need to be considered as 193 dynamic metrics and monitored continuously in some scenarios. An 194 implementation may make use of a multi-threshold scheme rather than 195 fine granular metric update so as to avoid constant routing changes. 196 A "multi-threshold scheme" sets a few levels to categorize metric 197 values and uses the levels instead of actual numerical values. 199 In LLNs, it is not uncommon to have highly heterogeneous nodes in 200 term of capabilities (e.g. nodes being battery operated or not, 201 amount of memory, etc) and functionalities. More capable and stable 202 nodes may assist the most constrained ones for routing packets, which 203 results in extension of network lifetime and efficient network 204 operations. This implies that constraint-based routing will be used 205 in some cases. Thus, the computed path may not be the shortest path 206 according to some specified metrics. Resource-awareness should be 207 employed to routing protocols strictly or loosely considering trade- 208 off between cost and benefit. 210 3.1. Node Memory Resources 212 Memory is a critical node resources in presence of constrained nodes. 213 Units is to be determined. 215 3.2. Node CPU Resources 217 CPU duty cycle for virtually all LLN applications to date is well 218 below 10%, and the trend in low power embedded systems is to more 219 capable processors rather than less. Computational speed is not 220 expected to be a limiting factor in routing in LLNs. 222 3.3. Node Residual Energy 224 Whenever possible, a node with low residual energy should not be 225 selected as a router, thus the support for constrained-based routing 226 is needed. In such cases, the routing protocol engine may compute a 227 longer path (constraint based) for some traffic in order to increase 228 the network life duration. The routing engine may prefer a "longer" 229 path that traverses mains-powered nodes or nodes equipped with energy 230 scavening, rather than a "shorter" path through battery operated 231 nodes. 233 Power and energy are clearly critical resources, given the name of 234 our working group. As yet there are no simple abstractions which 235 adequately cover the broad range of power sources and energy storage 236 devices used in existing LLN nodes. These include line-power, 237 primary batteries, energy-scavengers, and a variety of secondary 238 storage mechanisms. Scavengers may provide a reliable low level of 239 power, such as might be available from a 4-20mA loop; a reliable but 240 periodic stream of power, such as provided by a well-positioned solar 241 cell; or unpredictable power, such as might be provided by a 242 vibrational energy scavenger on an intermittently powered pump. 243 Routes which are viable when the sun is shining may disappear at 244 night. A pump turning on may connect two previously disconnected 245 sections of a network. 247 Storage systems like rechargeable batteries often suffer substantial 248 degradation if regularly used to full discharge, leading to different 249 residual energy numbers for regular vs. emergency operation. A route 250 for emergency traffic may have a different optimum than one for 251 regular reporting. 253 Batteries used in LLNs often degrade substantially if their average 254 current consumption exceeds a small fraction of the peak current that 255 they can deliver. It is not uncommon for LLN nodes to have a 256 combination of primary storage, energy scavenging, and secondary 257 storage, leading to three different values for acceptable average 258 current depending on the time frame being considered, e.g. 259 milliseconds, seconds, and hours/years. 261 Raw power and energy values are meaningless without knowledge of the 262 energy cost of sending and receiving packets, and lifetime estimates 263 have no value without some higher-level constraint on the lifetime 264 required of a device. In some cases the route that exhausts the 265 battery of a node on the bed table in a month may be preferable to a 266 route that reduces the lifetime of a node in the wall to a decade. 268 Given the complexity of trying to address such a broad collection of 269 constraints, a much simpler path is preferable in the short term. A 270 few energy levels, for example, unlimited, scavenger supported, 271 enough energy and low energy, may be sufficient to compute an 272 adequite path in highly constrained scenarios. The method to set the 273 level will be node and application dependent, and is out of the scope 274 of this document. 276 3.4. Node Overload State 278 Node workload may be hard to determine and express in some scalar 279 form. However, node workload could be a useful metric to consider 280 during path calculation, in particular when queuing delays must be 281 minimized for highly sensitive traffic considering MAC layer delay. 283 Using a simple 1-bit flag to characterize the node workload may 284 provide a sufficient level of granularity, similarly to the 285 "overload" bit used in protocols such as ISIS. 287 Algorithms used to set the overload bit and to compute path to 288 potentially avoid node with their overload bit set are outside the 289 scope of this document. 291 3.5. Data Aggregation Attribute 293 Data fusion involves more complicated processing to improve accuracy 294 of the output data while data aggregation mostly aims at reducing the 295 amount of data. 297 Some applications may make use of the aggregation node attribute in 298 their routing decision so as to minimize the amount of traffic on the 299 network, thus potentially increasing its life time in battery 300 operated environments. 302 Applications where high directional data flow is expected in a 303 regular basis may take advantage of data aggregation supported 304 routing. 306 4. Link Metrics and Attributes 308 There are several dynamic link attributes of interest especially in 309 wireless LLNs. Even in case of fixed LLNs where nodes are 310 stationary, link qualities may greatly vary in the presence of 311 obstacles and signal interference. 313 4.1. Throughput 315 Many LLNs support a wide range of throughput, measured either in bits 316 per second or packets per second. For some links, this may be due to 317 variable coding. For the deeply duty-cycled links found in many 318 LLNs, the variability comes as a result of trading power consumption 319 for bit rate. There are several MAC sub-layer protocols which allow 320 the effective bit rate and power consumption of a link to vary over 321 more than three orders of magnitude, with a corresponding change in 322 power consumption. For efficient operation, nodes must be able to 323 report the range of throughput that their links can handle, and 324 currently available throughput. 326 4.2. Latency 328 As with throughput, the latency of many LLN MAC sub-layers can be 329 varied over many orders of magnitude, again with a corresponding 330 change in current consumption. Some LLN MACs will allow the latency 331 to be adjusted globally on the subnet, or on a link-by-link basis, or 332 not at all. Some will insist that it be fixed for a given link, but 333 allow it to be variable from link to link. For efficient operation, 334 nodes must be able to report the range of latency that their links 335 can handle, and the currently available latency. 337 4.3. Link reliability 339 In LLNs, link reliability is degraded by external interference and 340 multi-path interference. Multipath typically affects both directions 341 on the link equally, whereas external interference is sometimes uni- 342 directional. Time scales vary from milliseconds to days, and are 343 often periodic and linked to human activity. Packet error rate can 344 generally be measured directly, and other metrics (e.g. bit error 345 rate, mean time between failures) are typically derived from that. 347 A change in link quality can affect network connectivity, thus, link 348 quality may be taken into account as a critical routing metric. Link 349 quality metric should be applied to each directional link unless bi- 350 directionality is one of routing metrics. 352 4.4. Link Coloring 354 Link color is an administrative static attribute used to avoid or 355 attract specific links for specific traffic types. 357 5. Computation of Dynamic Metrics and Attributes 359 As already pointed out, dynamically calculated metrics are of the 360 utmost importance in many circumstances in LLNs. This is mainly 361 because a variety of metrics change on a frequent basis, thus 362 implying the need to adapt the routing decisions. That being said, 363 care must be given to the pace at which changes are reported in the 364 network. The attributes will change according to their own time 365 scales. The protocol can control the reporting rate. 367 To minimize metric updates, multi-threshhold algorithms may be used 368 to determine when updates shoudl be sent. When practical, a low-pass 369 filter should be used to avoid rapid fluctuations of these values. 370 Finally, although the specification of path computation algorithms 371 using dynamic metrics are out the scope of this document, the 372 objective function should be designed carefully to avoid too frequent 373 computation of new routes upon metric values changes. 375 Controlled adaptation of the routing metrics and rate at which paths 376 are computed are critical to avoid undesirable routing instabilities 377 resulting in increased latencies and packet loss because of temporary 378 micro-loops. Furthermore, excessive route changes will impact the 379 traffic and power consumption in the network adversely. 381 6. Open Issues 383 Other items to be addressed in further revisions of this document 384 include: 386 o Metrics related to security (e.g. capability to avoid a node that 387 has not been authorized or authenticated). 389 o Specification of metric units. 391 o Practical usage related to the use of multiple metrics for path 392 computation in highly constrained envrionments. 394 7. Metric Consistency 396 Since a set of metrics and attributes will be used for links and 397 nodes in LLN, it is particularly critical to ensure the use of 398 consistent metric calculation mechanisms for all links and nodes in 399 the network. Although this is applicable to all routing schemes, a 400 number of such metrics and attributes in LLN make it particularly 401 challenging. 403 8. IANA Considerations 405 This document includes no request for IANA action. 407 9. Security Considerations 409 Routing metrics should be handled in a secure and trustful manner. 410 For instance, a malicious node can not advertise falsely that it has 411 good metrics for routing and belong to the established path to have a 412 chance to intercept packets. 414 10. Acknowledgements 416 The authors would like to acknowledge the contributions of YoungJae 417 Kim, David Meyer, Mischa Dohler, Anders Brandt, Philip Levis and 418 Pascal Thubert for their review and comments. 420 11. References 422 11.1. Normative References 424 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 425 Requirement Levels", BCP 14, RFC 2119, March 1997. 427 11.2. Informative References 429 [I-D.ietf-roll-building-routing-reqs] 430 Martocci, J., Riou, N., Mil, P., and W. Vermeylen, 431 "Building Automation Routing Requirements in Low Power and 432 Lossy Networks", draft-ietf-roll-building-routing-reqs-05 433 (work in progress), February 2009. 435 [I-D.ietf-roll-home-routing-reqs] 436 Porcu, G., "Home Automation Routing Requirements in Low 437 Power and Lossy Networks", 438 draft-ietf-roll-home-routing-reqs-06 (work in progress), 439 November 2008. 441 [I-D.ietf-roll-indus-routing-reqs] 442 Networks, D., Thubert, P., Dwars, S., and T. Phinney, 443 "Industrial Routing Requirements in Low Power and Lossy 444 Networks", draft-ietf-roll-indus-routing-reqs-05 (work in 445 progress), April 2009. 447 [I-D.ietf-roll-terminology] 448 Vasseur, J., "Terminology in Low power And Lossy 449 Networks", draft-ietf-roll-terminology-00 (work in 450 progress), October 2008. 452 [I-D.ietf-roll-urban-routing-reqs] 453 Dohler, M., Watteyne, T., Winter, T., Barthel, D., 454 Jacquenet, C., Madhusudan, G., and G. Chegaray, "Urban 455 WSNs Routing Requirements in Low Power and Lossy 456 Networks", draft-ietf-roll-urban-routing-reqs-05 (work in 457 progress), March 2009. 459 [RFC1195] Callon, R., "Use of OSI IS-IS for routing in TCP/IP and 460 dual environments", RFC 1195, December 1990. 462 [RFC2328] Moy, J., "OSPF Version 2", STD 54, RFC 2328, April 1998. 464 [RFC2702] Awduche, D., Malcolm, J., Agogbua, J., O'Dell, M., and J. 465 McManus, "Requirements for Traffic Engineering Over MPLS", 466 RFC 2702, September 1999. 468 [RFC3209] Awduche, D., Berger, L., Gan, D., Li, T., Srinivasan, V., 469 and G. Swallow, "RSVP-TE: Extensions to RSVP for LSP 470 Tunnels", RFC 3209, December 2001. 472 Authors' Addresses 474 Mijeon (editor) 475 Future Tech Lab., Korea Telecom 476 17 Woomyeon-dong, Seocho-gu 477 Seoul, 137-792 478 Korea 480 Email: mjkim@kt.com 482 JP Vasseur (editor) 483 Cisco Systems, Inc 484 11, Rue Camille Desmoulins 485 Issy Les Moulineaux, 92782 486 France 488 Email: jpv@cisco.com 490 Kris 491 Dust Networks 492 30695 Huntwood Ave. 493 Hayward, CA 95544 494 USA 496 Email: kpister@dustnetworks.com 498 Hakjin 499 Future Tech Lab., Korea Telecom 500 17 Woomyeon-dong, Seocho-gu 501 Seoul, 137-792 502 Korea 504 Email: hjchong@kt.com