ROLL Th. Zahariadis, Ed. Internet Draft TEIHAL Intended Status: Informational P. Trakadas, Ed. Expires: January 30, 2012 ADAE July 29, 2011 Design Guidelines for Routing Metrics Composition in LLN draft-zahariadis-ietf-roll-metrics-composition-00 Abstract This document specifies the guidelines for designing efficient composite routing metrics to be applied to the Routing for Low Power and Lossy Networks (RPL) routing protocol. 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/1id-abstracts.html The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html Copyright and License Notice Copyright (c) 2010 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 (http://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents Zahariadis, et al. Expires January 30, 2012 [Page 1] Internet Draftdraft-zahariadis-ietf-roll-metrics-composition-00July 2011 carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License. Table of Contents 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.1 Terminology . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2 Motivation . . . . . . . . . . . . . . . . . . . . . . . . 5 2 Basic and Derived Metrics Properties and Rules . . . . . . . . 5 2.1 Metric Domain . . . . . . . . . . . . . . . . . . . . . . . 6 2.2 Aggregation Rules . . . . . . . . . . . . . . . . . . . . . 6 2.3 Metric Order Relation . . . . . . . . . . . . . . . . . . . 7 3 Composition Metrics Requirements . . . . . . . . . . . . . . . 7 4 Applicability to RPL . . . . . . . . . . . . . . . . . . . . . 9 4.1 Lexical Metric Composition . . . . . . . . . . . . . . . . 10 4.2 Additive Metric Composition . . . . . . . . . . . . . . . . 10 5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . 10 6 Security Considerations . . . . . . . . . . . . . . . . . . . . 11 7 IANA Considerations . . . . . . . . . . . . . . . . . . . . . . 11 8 References . . . . . . . . . . . . . . . . . . . . . . . . . . 11 8.1 Normative References . . . . . . . . . . . . . . . . . . . 11 8.2 Informative References . . . . . . . . . . . . . . . . . . 12 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 12 Zahariadis, et al. Expires January 30, 2012 [Page 2] Internet Draftdraft-zahariadis-ietf-roll-metrics-composition-00July 2011 1 Introduction Low Power and Lossy Networks (LLNs) have specific routing requirements, as described in [RFC5548], [RFC5673], [RFC5826], and [RFC5867]. In these RFCs, several (and sometimes contradicting) requirements are set by each application domain. In order to cope with them, a number of routing metrics and constraints has been spelled out in [I-D.ietf-roll-routing-metrics], consisting of link/node, qualitative/quantitative, static/dynamic metrics and constraints. According to [I-D.ietf-roll-rpl], these metrics and constraints are carried in objects that are OPTIONAL within RPL messages. Path computation algorithms for single metrics have already been proposed and used in current Internet Drafts [I-D.ietf-roll-OF0], [I- D.gnawali-roll-etxof], and [I-D.gnawali-roll-minrank-hysteresis-of]. For providing Quality-of-Service (QoS) routing in future applications, the Objective Function (OF) and Rank value might be built upon a composite metric, consisting of several basic metrics, as defined in [I-D.ietf-roll-routing-metrics]. The intention of this document is to set the guidelines for the proper selection of basic metrics as well as the design of composite routing metrics for LLNs, taking into consideration the theoretical framework of [Sobrinho], as refined by [Yang]. Thus, the main target of this document is to examine the properties that routing metrics must hold to provide consistency, optimality and loop-freeness for the RPL routing protocol. In this way, each node will select the shortest path (or shortest constraint path, in the presence of constraints). The document does not intend to provide one composite metric that fits all cases, but rather to sketch out the guidelines for designing appropriate composite metrics, in line with specific application requirements. The effectiveness and performance of composite metrics used for IP performance evaluation is beyond the scope of this document and can be found in [RFC2330], [RFC5835] and [RFC6049]. The purpose of this document is to provide a common framework for various classes of metrics that are composed of basic metrics. It is assumed that the reader is familiar with the concepts of [I- D.ietf-roll-rpl] and [I-D.ietf-roll-routing-metrics]. 1.1 Terminology Zahariadis, et al. Expires January 30, 2012 [Page 3] Internet Draftdraft-zahariadis-ietf-roll-metrics-composition-00July 2011 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 [RFC2119]. This document makes use of the terminology defined in [I-D.ietf-roll- terminology]. Apart from [I-D.ietf-roll-terminology], this document defines the following terms, in accordance with [RFC5835] terminology: basic metric: a metric governed by specific rules and properties, capturing specific link or node characteristics. Examples of basic metrics are hop-count, ETX, LQL, etc. derived metric: a metric that is defined in terms of a basic metric, retaining the properties and rules of the basic metric. For example, (1-(1/ETX)) is an ETX derived metric, since it retains the rules and properties of the basic metric (ETX). composite metric: is defined as a routing metric consisting of several basic or/and derived metrics by applying a deterministic process or function (composition function). composition function: a deterministic process applied to primary and/or derived metrics to derive a composite metric. optimal path: is defined as a path in the DAG that minimizes (or maximizes, respectively) the Rank value between any given pair of source-destination nodes. sub-path: is defined as any portion of the path traversed between any given pair of source-destination nodes. path weight: a value representing link or/and node characteristics of a path. This definition coincides with 'path cost' defined in [I-D.ietf-roll-minrank-hysteresis-of]. Path weight is used by RPL to compare different paths. metric order relation: is used for weight comparison of paths with the same source and destination nodes, leading to the next hop neighbor selection. For example: '>' (greater than) is an order relation. metric operator: is used for the transformation of link weights and node characteristics into path weights. As an example, addition ( + ) is defined as a metric operator. Zahariadis, et al. Expires January 30, 2012 [Page 4] Internet Draftdraft-zahariadis-ietf-roll-metrics-composition-00July 2011 1.2 Motivation Different metrics are defined to capture different link and node characteristics of a path. For example, some metrics capture network latency, some others take into account the energy consumption of a node, while others focus on link reliability. The diversity of RPL routing protocol application domains, as described in [RFC5548], [RFC5673], [RFC5826], and [RFC5867] motivate the design of different composite routing metrics to cope with different routing application requirements. However, the selection of basic and derived metrics to design an efficient composite metric is neither an arbitrary nor a trivial task. Combining routing metrics of different types may lead to routing loops or selection of non-optimal paths. This document presents the guidelines for designing QoS routing strategies set by different applications, by identifying the properties that a composite metric must hold in order to work seamlessly with RPL routing protocol. 2 Basic and Derived Metrics Properties and Rules Routing metrics are the representation of an LLN in routing process. Thus, they might result in major implications on the complexity of optimal path computation, the existence of optimal path and the range of application requirements that can be supported. Path computation algorithms using a basic metric have been widely used in the literature and practice [I-D.ietf-roll-of0], [I-D.ietf- roll-etxof], [I-D.ietf-roll-minrank-hysteresis-of]. However, in order to support a wide range of QoS requirements dictated by different application domains, several routing metric forming a composite metric must be taken into account. RPL is a distance vector based, hop-by-hop routing protocol that builds Directed Acyclic Graphs (DAG) based on routing metrics and constraints. Following the routing algebra formalism presented in [Sobrinho] and refined in [Yang], routing metrics must hold specific properties, namely isotonicity and monotonicity, in order to fulfil routing protocol requirements (consistency, optimality, loop- freeness). In the following sections, basic metrics are examined and categorized according to their properties and rules. This exercise will provide useful information for the composition of efficient composite Zahariadis, et al. Expires January 30, 2012 [Page 5] Internet Draftdraft-zahariadis-ietf-roll-metrics-composition-00July 2011 metrics. 2.1 Metric Domain Basic metrics are defined in different domains. For example, hop- count has the value of 1 per-hop, while ETX is defined in [1, +infinity) and LQL from 0 to 7, where 0 means undetermined and 1 indicates the highest link quality. Intuitively, the selection of the basic metrics to derive a composite metric MUST take into account the domain of each one of the basic metrics selected. This can be achieved by defining derived metrics, as will be explained later in this document. 2.2 Aggregation Rules According to [I-D.ietf-roll-routing-metrics], a metric can either be recorded or aggregated along the path. In the former case, the metric can be of maximum type (A=0x01) or minimum type (A=0x02), while in the latter case, a metric can be of additive type (A=0x00) or multiplicative type (A=0x03). Let m(i,r) be the metric value for link and node characteristics between nodes i and r. Then, for any path p from node i to node r, we define that: a metric is additive if: m(p)=m(i,j)+m(j,k)+...+m(q,r), a metric is multiplicative if: m(p)=m(i,j)*m(j,k)*...*m(q,r), a metric is concave if: m(p)=max[m(i,j),m(j,k),...,m(q,r)] or m(p)=min[m(i,j),m(j,k),...,m(q,r)]. In most of the cases, basic metrics are aggregated along the path, indicating end-to-end characteristics of the network. This categorization is related to metric operator. Metrics differ in the aggregation rule they follow. As an example, hop-count and ETX are additive metrics, while RSSI is a multiplicative metric. Moreover, the concave metrics are recorded (and not aggregated) along the path. Examples taken from routing schemes in IP networks that make use of concave metrics are 'widest-shortest' and 'shortest-widest' path calculation metrics. Thus, the composite metric must also take into account the Zahariadis, et al. Expires January 30, 2012 [Page 6] Internet Draftdraft-zahariadis-ietf-roll-metrics-composition-00July 2011 aggregation rules of the selected primary metrics. 2.3 Metric Order Relation Another categorization of basic metrics is derived from the fact that some are 'maximizable' (the higher value, the better) while others are 'minimizable' (the lower value, the better). For example, a node selects for routing a neighboring node (DODAG parent) that advertises (DIO) the minimum hop-count (or aggregated ETX) value to reach DAG root node. On the other hand, if the Objective Function is based on RSSI (or throughput) values, then the maximum value will lead the process of the DODAG parent selection. In Figure 1, the properties and rules for some of the well-known primary metrics used in LLNs are presented. +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Metric | Domain | Aggregation Rule | Order Relation | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Hop-count | 1 | additive | minimum | | ETX | [1,+infinity)| additive | minimum | | LQL | [0,7] | additive | maximum | | Latency | real | additive | minimum | | Bandwidth | integer | concave | minimum | | Link-color | integer | concave | minimum | | RSSI | real | multiplicative | maximum | | Packet Loss | [0,1] | multiplicative | minimum | | Rem. Energy | [0,1] | concave | minimum | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Figure 1. Properties and rules of primary routing metrics used in LLNs. 3 Composition Metrics Requirements As discussed in the previous section and supported by [Sobrinho] and [Yang], the selection of the basic routing metrics for designing a composite metric is not straightforward for the routing solution to lead to fulfil routing protocol requirements (consistency, optimality, loop-freeness). In this section the composition metrics requirements will be examined, followed by explanatory text or representative examples, to guide prospective routing protocol designs and implementations. - Metrics MUST be well-defined. For applying an efficient composite metric, all basic or derived metrics must be well-defined. The use of new or not thoroughly tested Zahariadis, et al. Expires January 30, 2012 [Page 7] Internet Draftdraft-zahariadis-ietf-roll-metrics-composition-00July 2011 basic metrics MUST be avoided. - Metrics MUST reflect the basic characteristics of LLNs. Each network has its own unique characteristics. As an example, a fundamental concern in ad-hoc networks consists on link reliability and node mobility, while in IP networks, bandwidth and latency are of great importance. LLNs are no exception. The resource constraints of such networks demand primarily for energy conservation, link instabilities and (in some applications) heavy traffic load. Thus, the basic metrics selected for defining a composite metric must be analyzed towards capturing the fundamental characteristics of LLNs. - Metrics MUST be orthogonal and not antagonistic. Orthogonality means that no correlated information is carried within different basic metrics. As an example, the use of RSSI and LQL for metric composition MUST be avoided, since they capture the same LLN characteristic; link reliability. Moreover, the use of antagonistic metrics must be avoided. As antagonistic metrics can be defined metrics that eliminate the effects of one another. - Metrics MUST exhibit continuity. That is, small variations in metric values, MUST result in small variations in the composite metric value. This requirement is more related to derived metrics. Special attention must be paid so that the derived metrics do not produce instabilities and inconsistencies. - Metrics MUST be scalable. A composite metric must be able to scale to large LLNs. This requirement is relevant to path computation complexity, since the complexity of the path computation is determined by the composition rules of the metric. Especially in LLNs, this requirement is of importance, taking into account that the computational power of LLN nodes is constrained. - Metrics must have known and identified sources of inaccuracies and measurement uncertainties. Most of the basic metrics are prone to inaccuracies. A representative example is LQL, as defined in [I-D.ietf-roll-routing-metrics]. In other words, when such metrics are used, the sources of inaccuracies must be, at least, identified. Zahariadis, et al. Expires January 30, 2012 [Page 8] Internet Draftdraft-zahariadis-ietf-roll-metrics-composition-00July 2011 - Metrics MUST follow the same properties and rules. As described above, the combination of metrics retaining different properties may lead to routing instabilities and selection of non- optimal paths. It is RECOMMENDED that basic routing metrics with different properties are transformed to derived metrics holding the same properties in order to be used for metric composition. For example, in case that ETX is used in conjunction to the node remaining energy (defined as RE =Enow/Emax), then a derived metric must be used for remaining energy (such as 1/RE). With this transformation, both metrics are additive, they share the same domain and are both 'minimizable'. - Metrics MUST be normalized. In case that an additive composite metric is used in conjunction with weighting factors for providing better QoS characteristics according to different applications, normalization of basic or derived metrics MUST take place. In the previous example, a composite metric (consisting of ETX and RE) could be defined as: a1*(1-(1/ETX))+a2*(1- RE). In this case, both derived metrics are defined in [0,1), are additive and 'minimizable'.Furthermore, if RSSI participates in the composite metric, then RSSI must become an additive metric by applying the logarithmic properties and then used in the form of the following derived metric: a3*(1/log(RSSI)). - Composite metric MUST hold isotonic and monotonic properties. Monotonicity means that the path weight strictly increases when prefixed or suffixed by another path. If the algebra is monotonic, then convergence of the routing protocol is ensured. Moreover, the isotonicity property essentially means that a routing metric should ensure that the order of the weights of two paths is preserved if they are appended or prefixed by a common third path. If the algebra is isotonic, then the paths onto which routing protocols converge are optimal. 4 Applicability to RPL According to [I-D.ietf-roll-rpl], Objective Function (OF) defines how routing metrics, optimization objectives and related functions are used to compute Rank. Furthermore, OF dictates how parents in the DODAG are selected and thus the DODAG formation is defined by OF. On the other hand, Rank defines the node's individual position relative to other nodes with respect to a DODAG root. Rank strictly increases in the Down direction (towards leaf nodes) and strictly Zahariadis, et al. Expires January 30, 2012 [Page 9] Internet Draftdraft-zahariadis-ietf-roll-metrics-composition-00July 2011 decreases in the Up direction (towards root node). The exact way Rank is computed, depends on the DAG's OF, as mentioned earlier. Furthermore, according to [I-D.ietf-roll-rpl], minHopRankIncrease value is defined as the minimum increase in Rank between a node and any of its DODAG parents, while maxRankIncrease is defined as the maximum value increase that a given node can advertise within the same DODAG version. There are two distinct approaches to follow, regarding the usability of multiple basic or derived routing metrics into one composite metric in a routing protocol, namely the lexical metric composition and the additive metric composition. 4.1 Lexical Metric Composition According to the lexical metric composition approach, when comparing two composite metric values, the node will select as a DODAG parent the node with the lower value of the first component, and if the first component values are equal (or differ less than a predefined threshold) then it will select the one with the lower value of the second composite metric component. Some examples of well-known composite lexical metrics used in IP networks are 'widest-shortest' path, that selects the widest path among the set of shortest paths between the source and the destination node, and 'most reliable- shortest' path, that selects the most reliable path among the set of shortest paths. This is totally in line with the "Prec" field carried within the DAG Metric Container Object defined in [I-D.ietf-roll-rpl] and [I- D.ietf.roll-routing-metrics] that indicates the precedence of each routing metric (or constraint) present in the Objective Function. 4.2 Additive Metric Composition According to the additive metric composition, the Rank is evaluated based on a defined OF (composition function) and advertised through the DIO message. Moreover, the values of the basic metrics are aggregated along the path and are included in the DAG Metric Container Object. This approach is also compatible with RPL specifications, since according to [I-D.ietf-roll-routing-metrics], in this case the relevant flags of the DAG Metric Container Object must be: C = 0, O = 0, A = 0x00, and R = 0. 5 Conclusion Zahariadis, et al. Expires January 30, 2012 [Page 10] Internet Draftdraft-zahariadis-ietf-roll-metrics-composition-00July 2011 As explained in this document, the composition of several basic or derived routing metrics into a composite routing metric is a challenging problem. Thus, the goal of this document is to describe the framework for routing metrics composition properties and mechanisms, providing guidelines for the proper selection and composition of basic metrics into composite metrics for applicability to RPL routing protocol. This has been achieved by examining issues related to composing a routing metric, subject to multiple basic metrics and constraints. 6 Security Considerations No new considerations are raised by this document. 7 IANA Considerations This document includes no request to IANA. 8 References 8.1 Normative References [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997. [I-D.ietf-roll-routing-metrics] Vasseur, J., Kim, M., Pister, K., Dejean, N., and D. Barthel, "Routing Metrics used for Path Calculation in Low Power and Lossy Networks", draft-ietf- roll-routing-metrics-19, March 2011. [I-D.ietf-roll-rpl] Winter, T., Thubert, P., Brandt, A., Clausen, T., Hui, J., Kelsey, R., Levis, P., Pister, K., Struik, R., and JP. Vasseur, "RPL: IPv6 Routing Protocol for Low Power and Lossy Networks", draft-ietf-roll-rpl-19, March 2011. [I-D.ietf-roll-of0] Thubert, P., "RPL Objective Function 0", draft- ietf-roll-of0-07, March 2011. [I-D.ietf-roll-etxof] Gnawali, O., and P. Levis, "The ETX Objective Function for RPL", draft-gnawali-roll-etxof-01, May 2010. [I-D.ietf-roll-minrank-hysteresis-of] Gnawali, O., and P. Levis, "The Minimum Rank Objective Function with Hysteresis", draft-gnawali-roll-minrank-hysteresis-of-02, September Zahariadis, et al. Expires January 30, 2012 [Page 11] Internet Draftdraft-zahariadis-ietf-roll-metrics-composition-00July 2011 2010. 8.2 Informative References [I-D.ietf-roll-terminology] Vasseur, J., "Terminology in Low Power and Lossy Networks", draft-ietf-roll-terminology-04 (work in progress), September 2010. [RFC2330] Paxson, V., Almes, G., Mahdavi, J., and M. Mathis, "Framework for IP Performance Metrics", RFC2330, May 1998. [RFC5548] Dohler, M., Watteyne, T., Winter, T., and D. Barthel, "Routing Requirements for Urban Low-Power and Lossy Networks", RFC 5548, May 2009. [RFC5673] Pister, K., Thubert, P., Dwars, S., and T. Phinney, "Industrial Routing Requirements in Low-Power and Lossy Networks", RFC 5673, October 2009. [RFC5826] Brandt, A., Buron, J., and G. Porcu, "Home Automation Routing Requirements in Low-Power and Lossy Networks", RFC 5826, April 2010. [RFC5835] Morton, A., and S. Van der Berghe, "Framework for Metric Composition", RFC5835, April 2010. [RFC5867] Martocci, J., De Mil, P., Riou, N., and W. Vermeylen, "Building Automation Routing Requirements in Low-Power and Lossy Networks", RFC 5867, June 2010. [RFC6049] Morton, A., and E. Stephan, "Spatial Composition of Metrics", RFC 6049, January 2011. [Sobrinho] J. Sobrinho, "Network Routing with Path Vector Protocols: Theory and Applications", ACM SIGCOMM, 2003, pp. 49-60. [Yang] Yang, Y., and J. Wang, "Design Guidelines for Routing Metrics in Multihop Wireless Networks", IEEE INFOCOM 2008, pp. 1615-1623. Authors' Addresses Theodore Zahariadis (editor) Technological Educational Institute of Halkida (TEIHAL) Psachna, Evia, 34400, Greece. EMail: zahariad@teihal.gr Zahariadis, et al. Expires January 30, 2012 [Page 12] Internet Draftdraft-zahariadis-ietf-roll-metrics-composition-00July 2011 Panos Trakadas (editor) Hellenic Authority for Communications Security and Privacy (ADAE) 3, Ierou Lochou, str, 15125, Greece. EMail: trakadasp@adae.gr Zahariadis, et al. Expires January 30, 2012 [Page 13]