Networking Working Group M. Kim, Ed. Internet-Draft KT Intended status: Standards Track JP. Vasseur, Ed. Expires: May 21, 2009 Cisco Systems H. Chong KT November 17, 2008 Routing Metrics used for Path Calculation in Low Power and Lossy Networks draft-mjkim-roll-routing-metrics-02 Status of this Memo By submitting this Internet-Draft, each author represents that any applicable patent or other IPR claims of which he or she is aware have been or will be disclosed, and any of which he or she becomes aware will be disclosed, in accordance with Section 6 of 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 May 21, 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. Kim, Vasseur et al. Expires May 21, 2009 [Page 1] Internet-Draft Routing Metrics for LLNs November 2008 Table of Contents 1. Note (to be removed upon publication) . . . . . . . . . . . . 3 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 3 3. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 4. Node metrics and attributes . . . . . . . . . . . . . . . . . 5 4.1. Node resources . . . . . . . . . . . . . . . . . . . . . . 5 4.2. Residual Energy . . . . . . . . . . . . . . . . . . . . . 5 4.3. Node overload . . . . . . . . . . . . . . . . . . . . . . 6 4.4. Data Aggregation attribute . . . . . . . . . . . . . . . . 6 4.5. Node reliability . . . . . . . . . . . . . . . . . . . . . 8 5. Link metrics and attributes . . . . . . . . . . . . . . . . . 8 5.1. Throughput . . . . . . . . . . . . . . . . . . . . . . . . 8 5.2. Link reliability . . . . . . . . . . . . . . . . . . . . . 8 5.3. Link coloring . . . . . . . . . . . . . . . . . . . . . . 9 6. Computation of dynamic metrics and attributes . . . . . . . . 9 7. Open issues . . . . . . . . . . . . . . . . . . . . . . . . . 9 8. Metric consistency . . . . . . . . . . . . . . . . . . . . . . 10 9. Security Considerations . . . . . . . . . . . . . . . . . . . 10 10. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 10 11. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 10 12. References . . . . . . . . . . . . . . . . . . . . . . . . . . 10 12.1. Normative References . . . . . . . . . . . . . . . . . . . 10 12.2. Informative References . . . . . . . . . . . . . . . . . . 11 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 12 Intellectual Property and Copyright Statements . . . . . . . . . . 13 Kim, Vasseur et al. Expires May 21, 2009 [Page 2] Internet-Draft Routing Metrics for LLNs November 2008 1. Note (to be removed upon publication) Rev -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. Terminology 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 [RFC2119]. This document makes use of the terminology defined in [I-D.ietf-roll-terminology]. o Mobile LLN: Low power and Lossy Network where some nodes are mobile. o Fixed LLN: Low power and Lossy Network where all nodes are static, not mobile. 3. Introduction 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. Routing metrics can be classified according to the following set of characteristics: - Link versus Node metrics - Qualitative versus quantitative - Dynamic or static Historically, IGP such as OSPF [RFC2328] and IS-IS [ISO.10589.1992] Kim, Vasseur et al. Expires May 21, 2009 [Page 3] Internet-Draft Routing Metrics for LLNs November 2008 have been using quantitative static link metrics. Other mechanisms such as Multiprotocol Label Switching (MPLS) Traffic Engineering (TE) [RFC2702] [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). It must be noted that the use of dynamic metrics is not new and has been experimented in ARPANET 2 [Khanna1989], with a 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 draft-ietf-roll-urban-routing-reqs, draft-ietf-roll-indus-routing-reqs, draft-ietf-roll-home-routing-reqs, draft-ietf-roll-building-routing-reqs) in LLNs, several nodes constraints must be taken into account during path computation. Node metrics include 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. Additionally, mobility may also be considered. Link attributes include throughput and reliability. Bi- directionality are also of interest. In LLNs, it is fairly common for links and nodes to have changing characteristics in terms of reliability and available resources. Thus, it is required to specify a set of dynamic metrics. For instance, even though a wireless sensor network topology is static in absence of failure, 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 because moving obstacles can appear at any time. That being said, very careful attention must be given when using highly dynamic metrics and attributes that affect routing decisions in order to preserve the routing stability. Furthermore, it is 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 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 Kim, Vasseur et al. Expires May 21, 2009 [Page 4] Internet-Draft Routing Metrics for LLNs November 2008 having to define discrete values to reflect that state. This document specifies a set of link and nodes metrics that can be used to compute paths within a LLN. 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. Requirement of reporting frequency may differ among metrics, so classifying a few categories can be exploited and different reporting rates should be used for each category. The specification of the objective function used to compute the path is out of the scope of this document. 4. Node metrics and attributes In most cases, node metrics and attributes are static. However, critical metrics such as residual power might 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. "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. node being battery operated or not, amount of memory, etc) and functionalities. More capable and stable nodes can 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. 4.1. Node resources Memory and CPU resources are critical node resources in presence of constrained nodes. Resource-awareness should be employed to routing protocols strictly or loosely considering trade-off between cost and benefit. 4.2. Residual Energy Low power is one of the most distinguished features of LLNs, so node residual energy is a pivotal metric in environments where nodes are battery powered. Residual energy should be taken as a relative value Kim, Vasseur et al. Expires May 21, 2009 [Page 5] Internet-Draft Routing Metrics for LLNs November 2008 considering statistical node lifetime and other conditions such as the role of the node in the network. For example, if the node's expected lifetime is 5 years and the remaining energy is only one fifth, then the energy is a critical resource for the node. Hence, whenever possible, the node should not be selected as a router (an intermediate node to deliver data), thus the support for constrained- based routing is needed. In such cases, the routing protocol engine may compute a longer path (constrained based) for some traffic in order to increase the network life duration. Another typical use of constrained-based routing consists of using a node attribute as a routing criterion. For example, the routing engine may prefer a "longer" path that traverses main powered nodes or nodes equipped with rechargeable batteries. Algorithm can be designed to consider a combination of node metrics and node attributes. Algorithms defining how such metrics and attributes should be combined are outside of the scope of this document. Generally, the residual energy should be taken as a dynamic metric. Most battery operated devices have the ability to estimate the remaining energy [I-D.ietf-roll-indus-routing-reqs]. However, initial energy status can be considered as a static metric in some situations where monitoring the energy level is too CPU intensive. A few energy levels, for example, unlimited, scavenger supported, enough energy and low energy, may be sufficient to compute the path in highly constrained scenarios. The method to set the level should be defined using same criteria at every node. Note: a detailed list of energy related metrics will be specified in the next revision of this document. 4.3. Node overload 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. 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 IS-IS [ISO.10589.1992]. An implementation may then decide to exclude from its routes any node with a "heavy" value for workload unless there is no alternative. 4.4. Data Aggregation attribute Some nodes may sense or receive the same (or similar) data if the nodes are located in a close area due to data correlation. Thus, data aggregation/fusion may be possible. Data fusion involves more complicated processing to improve accuracy of the output data while Kim, Vasseur et al. Expires May 21, 2009 [Page 6] Internet-Draft Routing Metrics for LLNs November 2008 data aggregation mostly aims to reduce the amount of data. Especially in urban applications where sensor nodes collect environmental information and send it to a data sink, a potentially large amount of nodes sense similar data. For the sake of illustration, consider the simple example shown in the Figure 1. Let us assume that three nodes A, B and C need to send sensed data to the data sink. Node A sensed "xyz" and sent this data to node C. Since C also sensed same data, it has no additional information from node A. However, because the data node B sent is "xqz", node C aggregates this data with its own data "xyz" resulting in "xyqz". Therefore, node C sends "xyqz" to the data sink. In this example, each node's data requires 3 bytes. If no aggregation is performed, node C needs to send 9 byte data to the sink, but C only sends 4 bytes thanks to data aggregation. A B |------| |------| | xyz | | xqz | |______| |______| \ / \ / \ C / sink |------| xyqz |------| | xyz |-----------| | |______| |______| Figure 1: Data aggregation 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. To make data aggregation possible, the routing protocol needs to capture the time and location dependent correlation among sensed data from nodes on the possible routes, which may be challenging. Obtaining correlation structure also demands high resource (energy) consumption and in-network processing itself may have high complexity. Consequently, in most applications, data aggregation may not be adopted for routing. Applications where high directional data flow is expected in a regular basis may take advantage of data aggregation supported routing. Kim, Vasseur et al. Expires May 21, 2009 [Page 7] Internet-Draft Routing Metrics for LLNs November 2008 4.5. Node reliability Node reliability can be measured by many different factors such as the node failure rate and mobility (dynamicity). Node reliability directly affects the network topology and connectivity, which in turn may trigger path re-computation. It is usually very challenging to estimate or monitor node reliability and historical data can be used to that end. A specific function needs to be defined to get values of the reliability metric from a variety of features affecting node reliability. In the most constrained LLN environments, the simple heuristic of classifying nodes into static and dynamic can be very helpful in routing decision since static node are more reliable, thus should be preferred. 5. Link metrics and attributes There are several dynamic link attributes 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. That being said, as for node metrics and attributes, link metrics and attributes may be considered as static in fixed LLNs not only because it is very challenging to update them in real-time but also because updating mechanisms may be too time and energy consuming. However, in mobile LLNs, we may need to consider these metrics and attributes as dynamic. 5.1. Throughput Throughput is the average rate of successful message delivery over a communication channel. Throughput is usually measured in bit rate (bits per second). There are nodes that support for multiple bit rates, possibly using different encodings, to allows multiple throughput values between two nodes. This should be taken into account during throughput evaluation. 5.2. Link reliability Link reliability can be measured by the Bit Error Rate (BER), Packet Error Rate (PER), Mean Time Between Failures (MTBF) or link churn, the rate at which links see their status changed (up or down). Link reliability is closely related to node reliability especially in wireless LLNs. Two nodes which form a link affect directly to the link reliability as follows: if one (or both) end node of the link dies or moves away beyond of the transmission range from the other node, the link vanishes and should be removed from routing. However, link reliability is also influenced by other factors like unexpected obstacles or temporary interference. Kim, Vasseur et al. Expires May 21, 2009 [Page 8] Internet-Draft Routing Metrics for LLNs November 2008 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. Since path reliability is a function of each link and node reliability, such metrics may become critical as path length increases. 5.3. Link coloring Link color is an administrative static attribute used to avoid or attract specific links for specific traffic types. 6. 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, careful care must be given to the pace at which such metrics and attributes change. Algorithms used to compute such metrics can use multi-threshold mechanisms with low and high water marks for binary values and a limited set of discrete metric values for non binary metric. Furthermore, it is recommended to use a low-pass filter 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, it is recommended to design the objective function carefully to avoid too frequent computation of new routes upon metric values changes. Controlled adaptation of the routing metrics and rate at which path are computed are critical to avoid undesirable routing instabilities resulting in increased latencies and packet loss because of temporary micro-loops. Furthermore, since LLNs are made of constrained devices, computational resources must be used with care to preserve battery in case of battery operated devices and not to impact quality of service of the data traffic. 7. Open issues Other items to be addressed in further revisions of this document include: o Metrics related to security: Metrics that security is associated with need to be further considered. If a route is comprised of Kim, Vasseur et al. Expires May 21, 2009 [Page 9] Internet-Draft Routing Metrics for LLNs November 2008 authenticated and authorized nodes for the data, then the route may be preferable. o Consideration of routing efficiency: Since LLNs are highly constrained networks, maintaining many different routing metrics is challenging. Routing should be lightweight. 8. 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. 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. IANA Considerations This document requests no action by IANA. 11. Acknowledgements The authors would like to acknowledge the contributions of YoungJae Kim, David Meyer, Mischa Dohler, Kris Pister, Anders Brandt, Philip Levis and Pascal Thubert for their review and comments. 12. References 12.1. Normative References [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997. Kim, Vasseur et al. Expires May 21, 2009 [Page 10] Internet-Draft Routing Metrics for LLNs November 2008 12.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-01 (work in progress), October 2008. [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-04 (work in progress), October 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-02 (work in progress), October 2008. [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-02 (work in progress), October 2008. [ISO.10589.1992] International Organization for Standardization, "Intermediate system to intermediate system intra-domain- routing routine information exchange protocol for use in conjunction with the protocol for providing the connectionless-mode Network Service (ISO 8473)", ISO Standard 10589, 1992. [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. [RFC3209] Awduche, D., Berger, L., Gan, D., Li, T., Srinivasan, V., and G. Swallow, "RSVP-TE: Extensions to RSVP for LSP Kim, Vasseur et al. Expires May 21, 2009 [Page 11] Internet-Draft Routing Metrics for LLNs November 2008 Tunnels", RFC 3209, December 2001. [Khanna89] Khanna, A., and Zinky, J.,"The revised ARPANET routing metric", ACM SIGCOMM, Austin, USA, Sept. 1989, pp. 45-56. Authors' Addresses Mijeom Kim (editor) Future Tech Lab., KT 17 Woomyeon-dong, Seocho-gu Seoul 137-792 Korea Phone: +82-2-526-6063 Fax: +82-2-526-5071 Email: mjkim@kt.com JP Vasseur (editor) Cisco Systems 11, Rue Camille Desmoulins L'Atlantis 92782 Issy Les Moulineaux France Email: jpv@cisco.com Hakjin Chong Future Tech Lab., KT 17 Woomyeon-dong, Seocho-gu Seoul 137-792 Korea Phone: +82-2-526-5070 Fax: +82-2-526-5071 Email: hjchong@kt.com Kim, Vasseur et al. Expires May 21, 2009 [Page 12] Internet-Draft Routing Metrics for LLNs November 2008 Full Copyright Statement Copyright (C) The IETF Trust (2008). This document is subject to the rights, licenses and restrictions contained in BCP 78, and except as set forth therein, the authors retain all their rights. This document and the information contained herein are provided on an "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY, THE IETF TRUST AND THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. Intellectual Property The IETF takes no position regarding the validity or scope of any Intellectual Property Rights or other rights that might be claimed to pertain to the implementation or use of the technology described in this document or the extent to which any license under such rights might or might not be available; nor does it represent that it has made any independent effort to identify any such rights. Information on the procedures with respect to rights in RFC documents can be found in BCP 78 and BCP 79. Copies of IPR disclosures made to the IETF Secretariat and any assurances of licenses to be made available, or the result of an attempt made to obtain a general license or permission for the use of such proprietary rights by implementers or users of this specification can be obtained from the IETF on-line IPR repository at http://www.ietf.org/ipr. The IETF invites any interested party to bring to its attention any copyrights, patents or patent applications, or other proprietary rights that may cover technology that may be required to implement this standard. Please address the information to the IETF at ietf-ipr@ietf.org. Kim, Vasseur et al. Expires May 21, 2009 [Page 13]