Networking Working Group M. Kim, Ed. Internet-Draft Future Tech Lab., Korea Telecom Intended status: Standards Track JP. Vasseur, Ed. Expires: October 31, 2009 Cisco Systems, Inc K. Pister Dust Networks H. Chong Future Tech Lab., Korea Telecom April 29, 2009 Routing Metrics used for Path Calculation in Low Power and Lossy Networks draft-ietf-roll-routing-metrics-00 Status of this Memo This Internet-Draft is submitted to IETF in full conformance with the provisions of BCP 78 and BCP 79. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet- Drafts. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress." The list of current Internet-Drafts can be accessed at http://www.ietf.org/ietf/1id-abstracts.txt. The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html. This Internet-Draft will expire on October 31, 2009. Copyright Notice Copyright (c) 2009 IETF Trust and the persons identified as the document authors. All rights reserved. This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents in effect on the date of publication of this document (http://trustee.ietf.org/license-info). Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Kim, et al. Expires October 31, 2009 [Page 1] Internet-Draft draft-ietf-roll-routing-metrics-00 April 2009 Abstract This document specifies routing metrics to be used in path calculation for Routing Over Low power and Lossy networks (ROLL). Low power and Lossy Networks (LLNs) have unique characteristics compared with traditional wired networks or even with similar ones such as mobile ad-hoc networks. By contrast with typical Interior Gateway Protocol (IGP) routing metrics using hop counts or link attributes, this document specifies a set of routing metrics suitable to LLNs. Requirements Language The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in RFC 2119 [RFC2119]. Kim, et al. Expires October 31, 2009 [Page 2] Internet-Draft draft-ietf-roll-routing-metrics-00 April 2009 Table of Contents 1. Note . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 4 3. Node Metrics and Attributes . . . . . . . . . . . . . . . . . 6 3.1. Node Memory Resources . . . . . . . . . . . . . . . . . . 6 3.2. Node CPU Resources . . . . . . . . . . . . . . . . . . . . 6 3.3. Node Residual Energy . . . . . . . . . . . . . . . . . . . 6 3.4. Node Overload State . . . . . . . . . . . . . . . . . . . 7 3.5. Data Aggregation Attribute . . . . . . . . . . . . . . . . 8 4. Link Metrics and Attributes . . . . . . . . . . . . . . . . . 8 4.1. Throughput . . . . . . . . . . . . . . . . . . . . . . . . 8 4.2. Latency . . . . . . . . . . . . . . . . . . . . . . . . . 8 4.3. Link reliability . . . . . . . . . . . . . . . . . . . . . 9 4.4. Link Coloring . . . . . . . . . . . . . . . . . . . . . . 9 5. Computation of Dynamic Metrics and Attributes . . . . . . . . 9 6. Open Issues . . . . . . . . . . . . . . . . . . . . . . . . . 10 7. Metric Consistency . . . . . . . . . . . . . . . . . . . . . . 10 8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 10 9. Security Considerations . . . . . . . . . . . . . . . . . . . 10 10. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 10 11. References . . . . . . . . . . . . . . . . . . . . . . . . . . 11 11.1. Normative References . . . . . . . . . . . . . . . . . . . 11 11.2. Informative References . . . . . . . . . . . . . . . . . . 11 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 12 Kim, et al. Expires October 31, 2009 [Page 3] Internet-Draft draft-ietf-roll-routing-metrics-00 April 2009 1. Note The first revision of this document has been published with a number of link and node metrics. After several discussions on the mailing list and during Working Group meetings, it was decided to reduce the number of these metrics to the strict required minimum. In the revision 02, highly dynamic and application/implementation dependent attributes have been removed (such as node degree and node latency) since they may be too CPU intensive for constrained devices and lead to routing oscillations. Link and node metrics packet format or methods to encode the data will be defined in a further revision of this document. 2. Introduction This document makes use of the terminology defined in [I-D.ietf-roll-terminology]. This document specifies routing metrics to be used in path calculation for Routing Over Low power and Lossy networks (ROLL). Low power and Lossy Networks (LLNs) have specific routing characteristics compared with traditional wired networks or even with similar ones such as mobile ad-hoc networks that lead to a set of specific requirements listed [I-D.ietf-roll-indus-routing-reqs], [I-D.ietf-roll-home-routing-reqs] [I-D.ietf-roll-urban-routing-reqs] and [I-D.ietf-roll-building-routing-reqs]. Routing metrics can be classified according to the following set of characteristics: o Link versus Node metrics o Qualitative versus quantitative o Dynamic or static Historically, IGP such as OSPF ([RFC2328]) and IS-IS ([RFC1195]) have used quantitative static link metrics. Other mechanisms such as Multiprotocol Label Switching (MPLS) Traffic Engineering (TE) (see [RFC2702] and [RFC3209]) make use of other link attributes such as the available reserved bandwidth, affinities and so on to compute constrained shortest paths for Traffic Engineering Label Switched Paths (TE LSPs). Kim, et al. Expires October 31, 2009 [Page 4] Internet-Draft draft-ietf-roll-routing-metrics-00 April 2009 It must be noted that the use of dynamic metrics is not new and has been experimented in ARPANET 2 [Khanna1989], with moderate success. Indeed, the use of dynamic metrics is not trivial and very careful care must be given to the use of dynamic metrics that may lead to potential routing instabilities. As pointed out in various routing requirements documents (see [I-D.ietf-roll-indus-routing-reqs], [I-D.ietf-roll-home-routing-reqs] [I-D.ietf-roll-urban-routing-reqs] and [I-D.ietf-roll-building-routing-reqs]), a variety of nodes constraints must be taken into account during path computation (e.g. node's resources such as memory, energy and CPU computational power). Moreover, node attributes such as the ability to act as an aggregator (node capable of performing data aggregation) may be of interest. It is also worth mentioning that it fairly common for link in LLNs to have fast changing node and link charateristics, which must be taken into account carefully when specifying link metrics. For instance, in addition to the normal dynamic nature of wireless connectivity, nodes' resources such as residual energy and available memory are changing continuously and may have to be taken into account during the path computation. Similarly, link attributes including throughput and reliability may drastically change over time due to multi-path interference. That being said, very careful attention must be given when using dynamic metrics and attributes that affect routing decisions in order to preserve routing stability. Furthermore, it is a time and energy consuming process to update these dynamic metrics and recompute the routing tables on a frequent basis. Therefore, it may be desirable to use a reduced set of discrete values to reduce computational overhead and bandwidth utilization. Of course, this comes with a cost, namely, reduced metric accuracy. Reliability is an example of qualitative parameters which is necessary as a routing metric for path calculation. Such qualitative parameters may be transformed to quantitative values. In other cases, a set of flags may be defined to reflect a node state without having to define discrete values to reflect that state. Some link or node attributes (e.g. level of link reliability, energy remaining on the node) can be used to perform constraint-based routing. It is not required to use all the metrics and attributes specified in this document. A particular implementation MAY use a subset or all of the metrics defined in this document. The requirements on reporting frequency may differ among metrics, thus different reporting rates may be used for each category. The specification of the objective function used to compute the path Kim, et al. Expires October 31, 2009 [Page 5] Internet-Draft draft-ietf-roll-routing-metrics-00 April 2009 is out of the scope of this document. 3. Node Metrics and Attributes In some cases, node metrics and attributes are static. However, critical metrics such as residual power will need to be considered as dynamic metrics and monitored continuously in some scenarios. An implementation may make use of a multi-threshold scheme rather than fine granular metric update so as to avoid constant routing changes. A "multi-threshold scheme" sets a few levels to categorize metric values and uses the levels instead of actual numerical values. In LLNs, it is not uncommon to have highly heterogeneous nodes in term of capabilities (e.g. nodes being battery operated or not, amount of memory, etc) and functionalities. More capable and stable nodes may assist the most constrained ones for routing packets, which results in extension of network lifetime and efficient network operations. This implies that constraint-based routing will be used in some cases. Thus, the computed path may not be the shortest path according to some specified metrics. Resource-awareness should be employed to routing protocols strictly or loosely considering trade- off between cost and benefit. 3.1. Node Memory Resources Memory is a critical node resources in presence of constrained nodes. Units is to be determined. 3.2. Node CPU Resources CPU duty cycle for virtually all LLN applications to date is well below 10%, and the trend in low power embedded systems is to more capable processors rather than less. Computational speed is not expected to be a limiting factor in routing in LLNs. 3.3. Node Residual Energy Whenever possible, a node with low residual energy should not be selected as a router, thus the support for constrained-based routing is needed. In such cases, the routing protocol engine may compute a longer path (constraint based) for some traffic in order to increase the network life duration. The routing engine may prefer a "longer" path that traverses mains-powered nodes or nodes equipped with energy scavening, rather than a "shorter" path through battery operated nodes. Power and energy are clearly critical resources, given the name of Kim, et al. Expires October 31, 2009 [Page 6] Internet-Draft draft-ietf-roll-routing-metrics-00 April 2009 our working group. As yet there are no simple abstractions which adequately cover the broad range of power sources and energy storage devices used in existing LLN nodes. These include line-power, primary batteries, energy-scavengers, and a variety of secondary storage mechanisms. Scavengers may provide a reliable low level of power, such as might be available from a 4-20mA loop; a reliable but periodic stream of power, such as provided by a well-positioned solar cell; or unpredictable power, such as might be provided by a vibrational energy scavenger on an intermittently powered pump. Routes which are viable when the sun is shining may disappear at night. A pump turning on may connect two previously disconnected sections of a network. Storage systems like rechargeable batteries often suffer substantial degradation if regularly used to full discharge, leading to different residual energy numbers for regular vs. emergency operation. A route for emergency traffic may have a different optimum than one for regular reporting. Batteries used in LLNs often degrade substantially if their average current consumption exceeds a small fraction of the peak current that they can deliver. It is not uncommon for LLN nodes to have a combination of primary storage, energy scavenging, and secondary storage, leading to three different values for acceptable average current depending on the time frame being considered, e.g. milliseconds, seconds, and hours/years. Raw power and energy values are meaningless without knowledge of the energy cost of sending and receiving packets, and lifetime estimates have no value without some higher-level constraint on the lifetime required of a device. In some cases the route that exhausts the battery of a node on the bed table in a month may be preferable to a route that reduces the lifetime of a node in the wall to a decade. Given the complexity of trying to address such a broad collection of constraints, a much simpler path is preferable in the short term. A few energy levels, for example, unlimited, scavenger supported, enough energy and low energy, may be sufficient to compute an adequite path in highly constrained scenarios. The method to set the level will be node and application dependent, and is out of the scope of this document. 3.4. Node Overload State Node workload may be hard to determine and express in some scalar form. However, node workload could be a useful metric to consider during path calculation, in particular when queuing delays must be minimized for highly sensitive traffic considering MAC layer delay. Kim, et al. Expires October 31, 2009 [Page 7] Internet-Draft draft-ietf-roll-routing-metrics-00 April 2009 Using a simple 1-bit flag to characterize the node workload may provide a sufficient level of granularity, similarly to the "overload" bit used in protocols such as ISIS. Algorithms used to set the overload bit and to compute path to potentially avoid node with their overload bit set are outside the scope of this document. 3.5. Data Aggregation Attribute Data fusion involves more complicated processing to improve accuracy of the output data while data aggregation mostly aims at reducing the amount of data. Some applications may make use of the aggregation node attribute in their routing decision so as to minimize the amount of traffic on the network, thus potentially increasing its life time in battery operated environments. Applications where high directional data flow is expected in a regular basis may take advantage of data aggregation supported routing. 4. Link Metrics and Attributes There are several dynamic link attributes of interest especially in wireless LLNs. Even in case of fixed LLNs where nodes are stationary, link qualities may greatly vary in the presence of obstacles and signal interference. 4.1. Throughput Many LLNs support a wide range of throughput, measured either in bits per second or packets per second. For some links, this may be due to variable coding. For the deeply duty-cycled links found in many LLNs, the variability comes as a result of trading power consumption for bit rate. There are several MAC sub-layer protocols which allow the effective bit rate and power consumption of a link to vary over more than three orders of magnitude, with a corresponding change in power consumption. For efficient operation, nodes must be able to report the range of throughput that their links can handle, and currently available throughput. 4.2. Latency As with throughput, the latency of many LLN MAC sub-layers can be varied over many orders of magnitude, again with a corresponding Kim, et al. Expires October 31, 2009 [Page 8] Internet-Draft draft-ietf-roll-routing-metrics-00 April 2009 change in current consumption. Some LLN MACs will allow the latency to be adjusted globally on the subnet, or on a link-by-link basis, or not at all. Some will insist that it be fixed for a given link, but allow it to be variable from link to link. For efficient operation, nodes must be able to report the range of latency that their links can handle, and the currently available latency. 4.3. Link reliability In LLNs, link reliability is degraded by external interference and multi-path interference. Multipath typically affects both directions on the link equally, whereas external interference is sometimes uni- directional. Time scales vary from milliseconds to days, and are often periodic and linked to human activity. Packet error rate can generally be measured directly, and other metrics (e.g. bit error rate, mean time between failures) are typically derived from that. A change in link quality can affect network connectivity, thus, link quality may be taken into account as a critical routing metric. Link quality metric should be applied to each directional link unless bi- directionality is one of routing metrics. 4.4. Link Coloring Link color is an administrative static attribute used to avoid or attract specific links for specific traffic types. 5. Computation of Dynamic Metrics and Attributes As already pointed out, dynamically calculated metrics are of the utmost importance in many circumstances in LLNs. This is mainly because a variety of metrics change on a frequent basis, thus implying the need to adapt the routing decisions. That being said, care must be given to the pace at which changes are reported in the network. The attributes will change according to their own time scales. The protocol can control the reporting rate. To minimize metric updates, multi-threshhold algorithms may be used to determine when updates shoudl be sent. When practical, a low-pass filter should be used to avoid rapid fluctuations of these values. Finally, although the specification of path computation algorithms using dynamic metrics are out the scope of this document, the objective function should be designed carefully to avoid too frequent computation of new routes upon metric values changes. Controlled adaptation of the routing metrics and rate at which paths are computed are critical to avoid undesirable routing instabilities Kim, et al. Expires October 31, 2009 [Page 9] Internet-Draft draft-ietf-roll-routing-metrics-00 April 2009 resulting in increased latencies and packet loss because of temporary micro-loops. Furthermore, excessive route changes will impact the traffic and power consumption in the network adversely. 6. Open Issues Other items to be addressed in further revisions of this document include: o Metrics related to security (e.g. capability to avoid a node that has not been authorized or authenticated). o Specification of metric units. o Practical usage related to the use of multiple metrics for path computation in highly constrained envrionments. 7. Metric Consistency Since a set of metrics and attributes will be used for links and nodes in LLN, it is particularly critical to ensure the use of consistent metric calculation mechanisms for all links and nodes in the network. Although this is applicable to all routing schemes, a number of such metrics and attributes in LLN make it particularly challenging. 8. IANA Considerations This document includes no request for IANA action. 9. Security Considerations Routing metrics should be handled in a secure and trustful manner. For instance, a malicious node can not advertise falsely that it has good metrics for routing and belong to the established path to have a chance to intercept packets. 10. Acknowledgements The authors would like to acknowledge the contributions of YoungJae Kim, David Meyer, Mischa Dohler, Anders Brandt, Philip Levis and Pascal Thubert for their review and comments. Kim, et al. Expires October 31, 2009 [Page 10] Internet-Draft draft-ietf-roll-routing-metrics-00 April 2009 11. References 11.1. Normative References [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997. 11.2. Informative References [I-D.ietf-roll-building-routing-reqs] Martocci, J., Riou, N., Mil, P., and W. Vermeylen, "Building Automation Routing Requirements in Low Power and Lossy Networks", draft-ietf-roll-building-routing-reqs-05 (work in progress), February 2009. [I-D.ietf-roll-home-routing-reqs] Porcu, G., "Home Automation Routing Requirements in Low Power and Lossy Networks", draft-ietf-roll-home-routing-reqs-06 (work in progress), November 2008. [I-D.ietf-roll-indus-routing-reqs] Networks, D., Thubert, P., Dwars, S., and T. Phinney, "Industrial Routing Requirements in Low Power and Lossy Networks", draft-ietf-roll-indus-routing-reqs-05 (work in progress), April 2009. [I-D.ietf-roll-terminology] Vasseur, J., "Terminology in Low power And Lossy Networks", draft-ietf-roll-terminology-00 (work in progress), October 2008. [I-D.ietf-roll-urban-routing-reqs] Dohler, M., Watteyne, T., Winter, T., Barthel, D., Jacquenet, C., Madhusudan, G., and G. Chegaray, "Urban WSNs Routing Requirements in Low Power and Lossy Networks", draft-ietf-roll-urban-routing-reqs-05 (work in progress), March 2009. [RFC1195] Callon, R., "Use of OSI IS-IS for routing in TCP/IP and dual environments", RFC 1195, December 1990. [RFC2328] Moy, J., "OSPF Version 2", STD 54, RFC 2328, April 1998. [RFC2702] Awduche, D., Malcolm, J., Agogbua, J., O'Dell, M., and J. McManus, "Requirements for Traffic Engineering Over MPLS", RFC 2702, September 1999. Kim, et al. Expires October 31, 2009 [Page 11] Internet-Draft draft-ietf-roll-routing-metrics-00 April 2009 [RFC3209] Awduche, D., Berger, L., Gan, D., Li, T., Srinivasan, V., and G. Swallow, "RSVP-TE: Extensions to RSVP for LSP Tunnels", RFC 3209, December 2001. Authors' Addresses Mijeon (editor) Future Tech Lab., Korea Telecom 17 Woomyeon-dong, Seocho-gu Seoul, 137-792 Korea Email: mjkim@kt.com JP Vasseur (editor) Cisco Systems, Inc 11, Rue Camille Desmoulins Issy Les Moulineaux, 92782 France Email: jpv@cisco.com Kris Dust Networks 30695 Huntwood Ave. Hayward, CA 95544 USA Email: kpister@dustnetworks.com Hakjin Future Tech Lab., Korea Telecom 17 Woomyeon-dong, Seocho-gu Seoul, 137-792 Korea Email: hjchong@kt.com Kim, et al. Expires October 31, 2009 [Page 12]