Networking Working Group M. Kim, Ed. Internet-Draft KT Intended status: Standards Track JP. Vasseur, Ed. Expires: January 5, 2009 Cisco Systems H. Chong KT July 4, 2008 Routing Metrics used for Path Calculation in Low Power and Lossy Networks draft-mjkim-roll-routing-metrics-00 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 January 5, 2009. Abstract This document specifies routing metrics 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 as indicated in several application-specific requirements documents. Since typical IGP routing metrics such as hop counts or link metrics are not sufficient for LLNs, this document specifies a new set of required link and node metrics suitable to Kim, et al. Expires January 5, 2009 [Page 1] Internet-Draft Routing Metrics for LLNs July 2008 LLNs. Table of Contents 1. Note . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 3 3. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 4. Node attributes . . . . . . . . . . . . . . . . . . . . . . . 5 4.1. Computational resources . . . . . . . . . . . . . . . . . 6 4.2. Residual Energy . . . . . . . . . . . . . . . . . . . . . 6 4.3. Current workload . . . . . . . . . . . . . . . . . . . . . 7 4.4. Node latency . . . . . . . . . . . . . . . . . . . . . . . 7 4.5. Data Aggregation attribute . . . . . . . . . . . . . . . . 7 4.6. Node degree . . . . . . . . . . . . . . . . . . . . . . . 8 4.7. Dynamicity . . . . . . . . . . . . . . . . . . . . . . . . 9 4.8. Node reliability . . . . . . . . . . . . . . . . . . . . . 9 5. Link attributes . . . . . . . . . . . . . . . . . . . . . . . 9 5.1. Bandwidth . . . . . . . . . . . . . . . . . . . . . . . . 10 5.2. Reliability (Quality) . . . . . . . . . . . . . . . . . . 10 5.3. Propagation delay . . . . . . . . . . . . . . . . . . . . 10 6. Open issues . . . . . . . . . . . . . . . . . . . . . . . . . 10 7. Security Considerations . . . . . . . . . . . . . . . . . . . 11 8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 12 9. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 12 10. References . . . . . . . . . . . . . . . . . . . . . . . . . . 12 10.1. Normative References . . . . . . . . . . . . . . . . . . . 12 10.2. Informative References . . . . . . . . . . . . . . . . . . 12 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 12 Intellectual Property and Copyright Statements . . . . . . . . . . 14 Kim, et al. Expires January 5, 2009 [Page 2] Internet-Draft Routing Metrics for LLNs July 2008 1. Note Some of the routing metrics defined in this document may be subject to change or may even be removed in light of the routing requirements currently being specified by the Routing Over Low power and Lossy networks (ROLL) Working Group. For the sake of illustration, some metrics are only meaningful in routing protocols that fall into the category of Distance Vector. Since the Working Group has not yet determined which routing protocol will be chosen for Low power and Lossy Networks (LLNs), it is not yet possible to determine whether such metrics will be required. Conversely, other metrics may be further required depending on which routing protocol is selected by the Working Group. 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]. o Access point: An infrastructure device that connects the low power and lossy networks to the backbone network like the Internet, mostly via access networks. o Data sink: A device which collects data from nodes in a LLN. o Dynamic LLN: Low power and Lossy Network where some nodes are mobile. o ROLL: Routing Over Low-power and Lossy networks. o Static LLN: Low power and Lossy Network where all nodes are static, not mobile. 3. Introduction This document specifies routing metrics 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 as indicated in several application-specific requirements documents. Since typical IGP routing metrics such as hop counts or link metrics are not sufficient for LLNs, this document specifies a new set of required link and node metrics suitable to LLNs. Kim, et al. Expires January 5, 2009 [Page 3] Internet-Draft Routing Metrics for LLNs July 2008 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 and IS-IS have been using quantitative static link metrics. Other mechanisms such as Multiprotocol Label Switching (MPLS) Traffic Engineering (TE) make use of other link attributes such as the available reserved bandwidth, affinities and so on to compute constrained shortest path 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, with a moderate success. Indeed, a very careful care must be given to the use of dynamic metrics that may lead to potential routing instabilities. In LLNs, it is required to take into account various node constraints when calculating the desirable path. Node metrics include the node's resources like memory, energy and CPU (computational power). Other node attributes such as the ability to act as an aggregator (node capable of performing data aggregation) may be of interest. Additionally, work load, transmission range and dynamicity (mobility, duty cycle, etc) may need to be taken into account. Link attributes include propagation delay, reliability (quality) and available bandwidth. By contrast with the current Internet, LLNs are characterized by their dynamic nature, which not only applies to the link but also to the nodes in the networks. Thus, it is required to specify various dynamic metrics. For instance, even though a wireless sensor network topology is static in absence of failure, nodes' workload and resource 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 latency and reliability are not static because moving obstacles can appear at any time. Thus, they are real-time parameters. That being said, very careful attention must be given to highly dynamic parameters that affect routing decision in order to preserve the routing stability. Furthermore, it is quite time- and energy-consuming process to update these dynamic metrics in a regular basis. Therefore, we may regard them as static metrics in static LLNs to cut off overhead by compromising accuracy. Kim, et al. Expires January 5, 2009 [Page 4] Internet-Draft Routing Metrics for LLNs July 2008 Reliability is an example of quality parameter. However, to be routing metrics for path calculation, quality parameters MUST be transformed to quantity values. Some criteria SHOULD be set to make the quality parameters appear in quantity forms. Quantity form can be numbers or levels. This document specifies a set of link and nodes metrics that can be used to compute the optimal path within a LLN. Furthermore, 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. Note: finding the shortest path is not always best in LLNs since a reliable path is more preferable. !oThe optimal path!+/- here means the best path having regard to constraints. The term !oconstrained shortest path!+/- may be used instead. The specification of the objective function used to compute the path is out of the scope of this document. Note: in the first revision of this document, link and node metrics are defined with no packet format or suggestions to encode the data. This will be determined in a further revision of this document. 4. Node attributes Most node attributes may be taken as static attributes in LLNs since it might require quite amount of resources to get exact values of the attributes and update them periodically. Furthermore, the use of dynamic metrics is subject to routing instabilities and must be used with extreme care. However, critical parameters like residual power might need to be considered dynamic and monitored continuously in some scenarios. Implementation MUST make use of multi-threshold scheme rather than fine granular metric update so as to avoid constant routing changes. 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, !|) 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. Therefore, node metrics SHOULD be carefully maintained and utilized for routing. This has the following strong implication referred to as constrained-based routing whereby the computed path may not be the shortest path according to some specified metrics. Kim, et al. Expires January 5, 2009 [Page 5] Internet-Draft Routing Metrics for LLNs July 2008 Mechanisms must be designed to ensure lack of routing loops in the presence of constrained based routing with a non connection oriented environment. 4.1. Computational resources Memory and CPU resources can be considered as computational ones and are potentially important routing metrics in LLNs because in some environments nodes are resource constraint. 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 residual energy MUST be considered as a pivotal metric in environments where nodes are battery powered. Residual energy should be taken as a relative value considering statistical node lifetime and other conditions like 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 quite precious resources to the node. In such cases, the routing protocol decision should be such that potentially a suboptimal path would be used for some traffic so as to increase the network life duration. Furthermore, in case absence of the node affects the network connectivity critically, the node SHOULD be avoided to save its power. 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. If the battery can be simply charged or the node can be easily replaced with another same kind of node, then it is not really a matter to use up the battery. Such information should be defined as a node attribute to be used in combination with the energy level. 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 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 current energy status demands quite resources. Simply categorizing devices into two classes, main-powered and battery- powered, can be good enough to select a routing path for highly constrained scenarios, which contributes to prolonging network lifetime. To maximize network lifetime, it is essential to maintain energy balance among nodes in LLNs. Kim, et al. Expires January 5, 2009 [Page 6] Internet-Draft Routing Metrics for LLNs July 2008 4.3. Current workload Workload of a node is somewhat difficult to be measured and compared. It is also difficult to express the workload in a quantitative form. However, it could be an important metric to select a path in LLNs, especially when data processing along the data path is required or queuing delays must be minimized for highly sensitive traffic. Putting the workload as a "heavy" or "light" one bit metric can give a good advice to select a path for routing, thus providing a sufficient level of granularity, similarly to the "overload" bit used in protocols such as IS-IS. 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. Node latency Node latency is the time span from the arrival time to the departure time of a given packet at a node. It is primarily made up of packet processing time and packet transmission time. Node latency is highly correlated with other metrics. For instance, heavy workload increases node latency while enough computational resources can reduce it. Therefore, in some LLNs where available resources and current workload can be measured, they can facilitate to estimate node latency or may substitute it. 4.5. Data Aggregation attribute Some nodes may sense (get) similar or same data if the nodes are located in a close area due to data correlation. Thus, data aggregation/fusion can be performed. Data fusion involves more complicated processing to improve accuracy of the output data while 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, quite a number of sensor nodes sense same kind or same value of data. 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. Kim, et al. Expires January 5, 2009 [Page 7] Internet-Draft Routing Metrics for LLNs July 2008 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 is quite 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. However, simply choosing nodes that have the same kind of sensors with the source node can increase the chance to aggregate data, so it can be helpful for path formation regardless of having data-aware routing capability. Applications where high directional data flow is expected in a regular basis may take advantage of data aggregation supported routing. 4.6. Node degree Node degree is the number of neighbors that can send a message to the node directly. In other words, neighbors are nodes located within the transmission range of the node. Generally, a high node degree can be helpful for quick route recovery when the next hop node on the route cannot be accessible. Therefore, it may be beneficial to choose a node with a high degree to construct a route. On the contrary, a node with a high degree has a high possibility to have heavy workload in a busy network. Therefore, node degree has to be carefully utilized in routing decision. Kim, et al. Expires January 5, 2009 [Page 8] Internet-Draft Routing Metrics for LLNs July 2008 4.7. Dynamicity Node dynamicity can be measured by many different factors such as mobility, transmission range, duty cycle, and the rate at which node joins and leaves the network. Node dynamicity directly affects the network topology and connectivity, which in turn may trigger route reestablishment process. For that reason, node dynamicity needs to be monitored and presented in a quantity form utilizing a well defined objective function. Thus, less dynamic nodes should be preferred for path selection. In the most constrained LLN environments, classifying nodes into only static and dynamic can be very helpful in routing decision. Note that this node metric may either be static or dynamic. In the later case, the network administrator will have to use consistent metric values. 4.8. Node reliability Node reliability is deeply related to node dynamicity such that node reliability deteriorates as node dynamicity increases. However, node reliability is a wider concept than node dynamicity since node reliability is influenced by more factors. For example, node's unexpected failure cuts off node reliability, but it is not really related to node dynamicity. Therefore, node dynamicity metric can be covered by node reliability metric. However, it is very challenging to estimate or monitor node reliability. A specific function needs to be defined to get values of the reliability metric from a variety of features affecting node reliability. Node reliability is a crucial metric in LLNs compared with in other conventional or even wireless networks considering that nodes in LLNs may stay in a sleep mode most of the time. A sleeping node should not be an intermediate node to deliver a packet, thus status of a node must be monitored or can be anticipated. Additionally, residual energy of a node should be predictable not to make the node suddenly die during routing process due to battery out. Nodes on the chosen path for routing should be reliable. 5. Link attributes There are several dynamic link attributes especially in wireless LLNs. Even in case of static LLNs where nodes are stationary, there are always variables like appearance of obstacles and signal interference. Similar to node attributes, link attributes can be considered as static ones in static LLNs not only because it is very challenging to update them in a real-time manner, but also it is quite time- and energy-consuming work. However, in dynamic LLNs, we may need to take these attributes as dynamic metrics and make use of Kim, et al. Expires January 5, 2009 [Page 9] Internet-Draft Routing Metrics for LLNs July 2008 current real-time values whenever necessary. Values of dynamic metrics cannot be obtained easily. One way to get values of dynamic metrics is to use historical data and average them within a specified time window. 5.1. Bandwidth Bandwidth can be taken as a link capacity metric. It can be evaluated as nodes' communicational capability, too. It must be remembered that in case of wireless link, the link capacity is shared among nodes in a single wireless link. 5.2. Reliability (Quality) Link reliability can be measured by the Bit Error Rate (BER), Mean Time Between Failures (MTBF) or link churn defined as the rate at which links change between good and bad [I-D.levis-roll-protocols-survey]. 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 node falls in a sleep mode or moves away beyond of the transmission range from the other node, the link vanishes away. However, link reliability is also influenced by other factors like unexpected obstacles or temporary interference. Just like node reliability is critical, link reliability is also essential for routing given that most nodes have very short duty cycles. Change of link quality directly gives rise to that of network connectivity. Therefore, link quality may be taken into account as a critical routing metric. Increasing link and node reliability together enhances route robustness. Therefore, choosing reliable links and nodes during route establishment process improves robustness of the selected routes. 5.3. Propagation delay Propagation delay is the time taken for the packet to traverse the link from the source node to the target node. Path (route) latency is made up of nodes' latency and links!_ propagation delay on the path. As mentioned earlier, it can be obtained by making average from historical data. 6. Open issues Other items to be addressed in further revisions of this document include: Kim, et al. Expires January 5, 2009 [Page 10] Internet-Draft Routing Metrics for LLNs July 2008 o Traffic flow requirement: selection of applicable routing metrics needs to be performed depending on application and traffic flow requirements. For example, when latency is not a matter at all, it is possible to remove latency related metrics in the objective function to calculate the routing path. As such, different applications or Service Level Agreement (SLA) might demand different routing metric combination for path calculation, which forms a different route. Moreover, some routing algorithm may support Multi-topology routing with the ability to compute routes based on the traffic flow requirements using different set of metrics. o Metric weights exploitation: weights for the listed metrics should be decided according to applications and data flows. For example, latency critical applications in military scenarios SHOULD put a high weight to latency metrics rather than resource metrics. On top of that, applicable metrics or optimized weights may need to be changed on demand. o Metrics related to security: Metrics that security is associated with need to be further considered. If a route is comprised of authenticated and authorized nodes for the data, then the route should be preferable. o Consideration of routing efficiency and stability: LLNs are highly constrained networks, thus it is hard to maintain many metrics for efficient routing due to resource demand and overhead. Routing should be lightweight. In addition, careful condition should be given to the dynamic nature of some metrics and their implication on routing stability. o Influence of network topology and density: Network topology and network density need to affect route construction in such a way that they need to give some input to metric decision. For example, star topology and mesh topology should employ different routing protocols. Obviously they need to adopt different routing metrics. Similarly, network density in terms of average node degree needs to be considered when setting routing metrics and weights. Network size in terms of physical and total number of nodes needs to be taken into account, too. In addition, influence of network deployment on routing metrics should be further studied. 7. 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 Kim, et al. Expires January 5, 2009 [Page 11] Internet-Draft Routing Metrics for LLNs July 2008 good metrics for routing and belong to the established path to have a chance to intercept packets. 8. IANA Considerations This document requests no action by IANA. 9. Acknowledgements The authors would like to acknowledge the contributions of Dr. YoungJae Kim for his review and comments. 10. References 10.1. Normative References [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997. 10.2. Informative References [I-D.ietf-roll-indus-routing-reqs] Networks, D. and P. Thubert, "Industrial Routing Requirements in Low Power and Lossy Networks", draft-ietf-roll-indus-routing-reqs-00 (work in progress), April 2008. [I-D.levis-roll-protocols-survey] Levis, P., Vasseur, J., and D. Culler, "Overview of Existing Routing Protocols for Low Power and Lossy Networks", draft-levis-roll-protocols-survey-00 (work in progress), May 2008. Kim, et al. Expires January 5, 2009 [Page 12] Internet-Draft Routing Metrics for LLNs July 2008 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 Distinguished Engineer 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, et al. Expires January 5, 2009 [Page 13] Internet-Draft Routing Metrics for LLNs July 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, et al. Expires January 5, 2009 [Page 14]