ROLL Th. Zahariadis, Ed. Internet Draft TEIHAL Intended Status: Informational P. Trakadas, Ed. Expires: May 27, 2013 ADAE November 23, 2012 Design Guidelines for Routing Metrics Composition in LLN draft-zahariadis-roll-metrics-composition-04 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) 2012 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 May 27, 2013 [Page 1] Internet Draftdraft-zahariadis-roll-metrics-composition-04 November 2012 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 . . . . . . . . . . . . . . . . . . . . . . . . 4 1.2 Motivation . . . . . . . . . . . . . . . . . . . . . . . . 5 2 Basic and Derived Metrics Properties and Rules . . . . . . . . 5 2.1 Metric Domain . . . . . . . . . . . . . . . . . . . . . . . 6 2.2 Metric Operator . . . . . . . . . . . . . . . . . . . . . . 6 2.3 Metric Order Relation . . . . . . . . . . . . . . . . . . . 6 3 Trust-Aware Routing Metric . . . . . . . . . . . . . . . . . . 7 3.1 Packets Forwarding Indication . . . . . . . . . . . . . . . 8 4 Applicability to RPL . . . . . . . . . . . . . . . . . . . . . 8 4.1 Lexical Metric Composition . . . . . . . . . . . . . . . . 9 4.2 Additive Metric Composition . . . . . . . . . . . . . . . . 9 5 Composition Metrics Requirements . . . . . . . . . . . . . . . 9 5.1 Metrics MUST be well-defined. . . . . . . . . . . . . . . . 10 5.2 Metrics MUST reflect the basic characteristics of LLNs. . . 10 5.3 Metrics MUST be orthogonal and not antagonistic. . . . . . 12 5.4 Metrics MUST exhibit continuity. . . . . . . . . . . . . . 12 5.5 Metrics MUST be scalable. . . . . . . . . . . . . . . . . . 12 5.6 Metrics must have known and identified sources of inaccuracies and measurement uncertainties. . . . . . . . . 12 5.7 Metrics MUST follow the same properties and rules. . . . . 13 5.8 Frequent metric values alterations SHALL NOT lead to routing inconsistencies. . . . . . . . . . . . . . . . . . 14 5.9 Composite metric MUST hold properties of isotonicity and monotonicity. . . . . . . . . . . . . . . . . . . . . . . . 16 6. Generic Rules for Metrics Composition . . . . . . . . . . . . . 18 7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . 19 8 Security Considerations . . . . . . . . . . . . . . . . . . . . 20 9 IANA Considerations . . . . . . . . . . . . . . . . . . . . . . 20 10 Acknowledgement . . . . . . . . . . . . . . . . . . . . . . . 20 11 References . . . . . . . . . . . . . . . . . . . . . . . . . . 20 11.1 Normative References . . . . . . . . . . . . . . . . . . . 20 11.2 Informative References . . . . . . . . . . . . . . . . . . 21 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 22 Zahariadis, et al. Expires May 27, 2013 [Page 2] Internet Draftdraft-zahariadis-roll-metrics-composition-04 November 2012 1 Introduction Low Power and Lossy Networks (LLNs) have specific routing requirements, as described in [RFC5548], [RFC5673], [RFC5826], [RFC5867], and [I-D.ietf-roll-applicability-ami]. 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 [RFC6551], consisting of link/node, qualitative/quantitative, static/dynamic metrics and constraints. According to [RFC6550], 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 [RFC6552], and [I-D.ietf-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 and derived metrics, as defined in [RFC6551]. The intention of this document is to set the guidelines for the proper selection of basic and derived 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 convergence, 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 purpose of this document is to provide a common framework for various classes of metrics that are composed of basic metrics. 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]. Finally, it is assumed that the reader is familiar with the concepts of [RFC6550] and [RFC6551]. Zahariadis, et al. Expires May 27, 2013 [Page 3] Internet Draftdraft-zahariadis-roll-metrics-composition-04 November 2012 1.1 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 [RFC2119]. This document makes use of the terminology defined in [I-D.ietf-roll- terminology]. Moreover, 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, as well as its sub- paths. 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 path weight comparison 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 and node weights into path weights. As an example, addition '+' is defined as a metric operator. Zahariadis, et al. Expires May 27, 2013 [Page 4] Internet Draftdraft-zahariadis-roll-metrics-composition-04 November 2012 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 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], [RFC5867], and [I-D.ietf-roll-applicability-ami] 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 one basic metric have been widely used in the literature and practice [RFC6552], [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 metrics 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 [Yang], routing metrics must hold specific properties (isotonicity and monotonicity) in order to fulfil routing protocol requirements (convergence, optimality and 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 metrics. Zahariadis, et al. Expires May 27, 2013 [Page 5] Internet Draftdraft-zahariadis-roll-metrics-composition-04 November 2012 2.1 Metric Domain Basic metrics are defined in different domains. For example, Hop- Count (HP) has the value of 1 (per-hop), while ETX is defined in [1, 512] and LQL in [0, 7], where 0 means undetermined, 1 indicates the highest and 7 the lowest 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 selected basic metrics. This can be achieved by defining derived metrics, as will be explained later in this document. 2.2 Metric Operator According to [RFC6551], a metric can either be recorded or aggregated along the path. In the latter case, the metric can be of maximum type (A=0x01), minimum type (A=0x02), additive type (A=0x00), or multiplicative type (A=0x03). Let w(i,j) be the metric value for link and node characteristics between nodes i and j. Then, for any path p(i,j,k,...,q,r), we define that: - a metric is additive if: w(p)=w(i,j)+w(j,k)+...+w(q,r), - a metric is multiplicative if: w(p)=w(i,j)*w(j,k)*...*w(q,r), - a metric is concave if: w(p)=max[w(i,j),w(j,k),...,w(q,r)] or w(p)=min[w(i,j),w(j,k),...,w(q,r)]. Metrics differ in the aggregation rule they follow. As an example, HP and ETX are defined as additive metrics, while Throughput and Bandwidth are representative examples of concave metrics. Thus, the composite metric must also take into account the metric operators of the selected basic/derived 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 as its DODAG parent the neighboring node that advertises (via DIO messages) 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 well-known basic Zahariadis, et al. Expires May 27, 2013 [Page 6] Internet Draftdraft-zahariadis-roll-metrics-composition-04 November 2012 metrics used in LLNs are presented. +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Metric | Domain | Aggregation Rule |Order Relation | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Hop-count | 1 | additive | < | | ETX | [1,512]*128 | additive | < | | LQL | [0,7] | concave (max.) | < (excl. 0) | | Latency | 32-bit integer | additive | < | | Throughput | 32-bit integer | concave (min.) | > | | RSSI | [0,255] | additive | > | | Packet Loss%| [0,1] | multiplicative | < | | Rem. Energy%| [0,1] | concave (min.) | > | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Figure 1. Properties and rules of basic routing metrics used in LLNs. The properties and rules for the majority of routing metrics shown in this Figure follow the description presented in [RFC6551]. However, it is important to mention that a routing metric MAY follow different properties and rules. As an example, remaining energy percentage MAY also be defined as additive (metric operator) with '>' as a metric order relation. The same remark applies to Link Color metric. Moreover, some of the abovementioned link or node metrics may also be used by RPL as constraints. In such cases, if a link or a node does not satisfy a required constraint, it is excluded from the candidate neighbor set, leading to a constrained shortest path (NP-complete problem). However, this draft mainly focuses on setting the requirements for optimal path selection, among several paths satisfying all supplied constraints (if any). 3 Trust-Aware Routing Metric Cooperation among nodes in LLNs raises high concerns regarding security issues. Most solutions available in the literature try to secure networking operations using traditional security techniques, such as encryption and key management. However, the implementation of such security measures comes at a high cost, since it requires significant memory and processing resources, increasing at the same time the energy consumption. To defend against a number of routing attacks, an alternative but rather efficient approach is trust management. Following this approach, LLN nodes establish trust relations based on their expectation that their neighbors will sincerely cooperate on particular tasks (data forwarding). This concept allows one to define and utilize a trust-aware routing metric for the selection of the routing path. Although this issue has been extensively discussed in the literature, Zahariadis, et al. Expires May 27, 2013 [Page 7] Internet Draftdraft-zahariadis-roll-metrics-composition-04 November 2012 no attention has been paid on the definition of a trust-aware metric for LLNs, that can be directly and efficiently combined with other metrics, fulfilling routing metrics properties and thus ensuring routing protocol requirements, as discussed above. 3.1 Packets Forwarding Indication Packets Forwarding Indication (PFI) is defined as an effective trust- aware routing metric, capable of capturing the forwarding willingness of the neighboring nodes. Following the concept of ETX, PFI is defined as the inverse probability that node B will forward a packet received coming from node A and is expressed as PFI(A,B)=Ns/Nt, where Ns is the number of successfully forwarded packets (originating from node A) by node B, and Nt is the total number of packets that node A sent to node B for further forwarding. Thus, PFI expresses the expected number of transmissions required for a packet to reach its destination (edge router) when denial of forwarding occurs (e.g. black-hole, grey-hole attack). As a result, PFI calculated for a path is subject to the reaction of a node's perception in terms of a neighbor's forwarding willingness. Specifically, PFI path weights depend on the capability of re-transmitting every packet that has not been further forwarded. According to the analysis presented in [Velivasaki], PFI can be considered either as an additive routing metric, defined in [1,+inf], or as a multiplicative metric that fulfills the routing algebra requirements for strict isotonicity and strict monotonicity and thus can be combined with other routing metrics as will be discussed below. 4 Applicability to RPL According to [RFC6550], 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 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 [RFC6550], 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. Zahariadis, et al. Expires May 27, 2013 [Page 8] Internet Draftdraft-zahariadis-roll-metrics-composition-04 November 2012 There are two distinct approaches to follow, regarding the usability of multiple basic or derived routing metrics into one composite metric in RPL 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 (or greater, respectively) value of the first composition metric, and if the first component values are equal (or differ less than a predefined threshold) then it will select the one with the lower (or greater, respectively) value of the second composition metric. 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 [RFC6550] and [RFC6551] 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 [RFC6551], in this case the relevant flags of the DAG Metric Container Object must be: C = 0, O = 0, A = 0x00, and R = 0. 5 Composition Metrics Requirements As discussed in the previous section, the selection of the basic routing metrics for designing a composite metric is not straightforward for the routing solution to fulfil routing protocol requirements (convergence, 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. Zahariadis, et al. Expires May 27, 2013 [Page 9] Internet Draftdraft-zahariadis-roll-metrics-composition-04 November 2012 5.1 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 basic metrics SHALL be avoided. 5.2 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. In LLNs, the resource constraints of nodes demand primarily for energy conservation, link stability and traffic load balance. Thus, the basic metrics selected for defining a composite metric must be analyzed towards capturing the fundamental characteristics of LLNs. In the following, two simple examples are analyzed, where the composite metric consists of Hop-Count (HP) and ETX metric. +-------------------------------------------------------------------+ | (A) <1 , 1.0> | | / \ | | / \ | | / \ | | 1.3 / \ 1.2 | | / \ | | / \ | | / \ | | <2 , 1.3> (B) (C) <2 , 1.2> | | |\_ _/ | | | | \_ _/ | | | | 1.5\_ _/1.6 | | | 1.3 | \/ | 1.3 | | | _/\_ | | | | _/ \_ | | | | _/ \_ | | | (D) (E) | | w(A,B,D) = <3 , 3.6> w(A,C,E) = <3 , 3.5> | | w(A,C,D) = <3 , 3.8> w(A,B,E) = <3 , 3.8> | +-------------------------------------------------------------------+ Figure 2: Example of a simple composite metric consisting of HP and ETX metrics. Example 1: Consider the LLN depicted in Figure 2, where the metrics taken into account are HP and ETX, as described above. Both metrics are added along the path and these values are advertised through DIO messages. The parentheses present the HP and ETX values, respectively. Zahariadis, et al. Expires May 27, 2013 [Page 10] Internet Draftdraft-zahariadis-roll-metrics-composition-04 November 2012 It is evident that if one applies an OF based on the lexical composition of these two metrics (either 'shortest-most reliable' or 'most reliable-shortest'), node D will select node B as its parent, while node E will select node C as its parent in both lexical cases. Similarly, by using the additive metric composition approach in the form of w=(a1*HP)+(a2*ETX), node D will select B as its parent and node E will select C for any combination of a1 and a2 values (given that 0<=a1,a2<=1 and a1+a2=1). Example 2: As a second example, consider the (slightly) more complex LLN depicted in Figure 3. Again, consider applying HP and ETX metrics, added along the traversed paths. This example demonstrates the dependency of the parent selection process dictated by the OF composition function. +-------------------------------------------------------------------+ | (A) <1 , 1.0> | | / \ | | / \ | | / \ | | 1.2 / \ 1.2 | | / \ | | / \ | | / \ | | <2 , 1.2> (B) (C) <2 , 1.2> | | \ | | | \ | 1.1 | | \ | | | 2.8 \ (E) <3 , 2.3> | | \ / | | \ _/ 1.1 | | \ / | | (D) | | w(A,B,D) = <3 , 5.0> | | w(A,C,E,D) = <4 , 4.4> | +-------------------------------------------------------------------+ Figure 3: Dependency of routing process dictated by different OF's. If the 'shortest-most reliable' lexical metric composition is chosen, then node D will select node E as its parent, although the traversed path is not the shortest one. On the contrary, if the 'most reliable- shortest' lexical metric composition approach is chosen, then node D will select node B as its parent, although the traversed path is not the most reliable. Accordingly, following the additive metric composition of the form (a1*HP)+(a2*ETX) implies that if (a1,a2)=(0.8,0.2), then node D will Zahariadis, et al. Expires May 27, 2013 [Page 11] Internet Draftdraft-zahariadis-roll-metrics-composition-04 November 2012 select node B as its parent, while in case that (a1,a2)=(0.2,0.8), node D will select node E as its parent. 5.3 Metrics MUST be orthogonal and not antagonistic. Orthogonality means that no redundant information is carried within different basic metrics. As an example, the use of RSSI and LQL for metric composition is not a wise option, since they capture the same LLN characteristic; link reliability. In this way, less computational burden (and possibly fewer message exchange) will be achieved. Moreover, the utilization of antagonistic metrics must be avoided. As antagonistic metrics can be defined those metrics that eliminate the effects of one another. As an example, by definition Hop-Count includes a sense of 'greediness', while RSSI partially eliminates this characteristic, since it promotes the most stable links. Assuming that all nodes use the same transmission power level, then a node, based on RSSI metric, will (most probably) select as parent node the neighbor closer to it. 5.4 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 either instabilities or inconsistencies. 5.5 Metrics MUST be scalable. A composite metric must be able to scale to large LLNs (or even Internet). 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 great importance, taking into account that the computational power of LLN nodes is constrained. 5.6 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 [RFC6551], defined in [0,7] domain. Only seven discrete values are used for LQL quantification (0 is excluded). Thus, a range of link quality values will be represented by the same LQL value. In other words, when such metrics are used, the sources of inaccuracies must be, at least, identified. Zahariadis, et al. Expires May 27, 2013 [Page 12] Internet Draftdraft-zahariadis-roll-metrics-composition-04 November 2012 5.7 Metrics MUST follow the same properties and rules. As described above, the combination of metrics retaining different properties and rules may lead to routing instabilities and selection of non-optimal paths. So, the basic routing metrics with different properties must be transformed to derived metrics holding the same properties in order to be used for metric composition. For example, in case that ETX ([1,512], '+', '<') is used in conjunction to the node remaining energy percentage (RE) ([0,1], '*', '>'), then a derived metric must be used for the remaining energy (e.g. 1/RE). With this transformation, both metrics are defined at the same domain, they are additive, and are using '<' as the order relation. Example 3: Consider the LLN depicted in Figure 4, where the metrics taken into consideration are ETX and Remaining Energy percentage, shown as . Also, each node has a remaining energy percentage, as shown in the parenthesis next to each node, e.g. node B has a remaining energy percentage value of 0.8, while node C has a remaining energy percentage value equal to 1.0. +-------------------------------------------------------------------+ | (1.0)(A) <1.0 , 1.0> | | / \ | | / \ | | / \ | | 1.2 / \ 1.1 | | / \ | | / \ | | / \ | | <2.2 , 0.8> (B)(0.8) (1.0)(C) <2.1 , 1.0> | | \ | | | \ | 1.2 | | \ | | | 2.2 \ (0.6)(E) <3.3 , 0.6> | | \ / | | \ ___/ 1.2 | | \ / | | (D)(0.7) | | w(A,B,D) = <4.4 , 0.56> (4.4+0.56=4.96) | | w(A,C,E,D) = <4.5 , 0.42> (4.5+0.42=4.92) | +-------------------------------------------------------------------+ Figure 4: Composition of metrics with different properties and rules. Applying the two lexical metric composition approaches (ETX or RE precedence), node D will select node B as its parent in both cases. Furthermore, consider that one applies the additive metric composition rule ETX+RE and selects the parent based on the '<' order Zahariadis, et al. Expires May 27, 2013 [Page 13] Internet Draftdraft-zahariadis-roll-metrics-composition-04 November 2012 relation. In this case, node D will select node E as its parent, since w(A,B,D)=4.4+0.56=4.96 > w(A,C,E,D)=4.5+0.42=4.92. This results in from the different properties and rules governing these two basic metrics. A possible solution might be the transformation of RE metric in such a way that metric range, operator and order relation of the derived RE metric coincides with ETX's. This can be achieved by defining the derived RE metric, denoted as dRE, as the inverse of RE (1/RE), defined in the range [1.935*10^-3,1]. In this way, dRE shares the same metric range with ETX, namely [1, 512]. Furthermore, the dRE order relation is '<' and the metric operator is '+'. By applying dRE at the composition function and calculating Rank at node D, it is evident that node B will be selected as node D's parent since (w(A,B,D)=4.4+(1/0.56)=6.1857 < w(A,C,E,D)=4.5+(1/0.42)=6.881). 5.8 Frequent metric values alterations SHALL NOT lead to routing inconsistencies. This requirement applies mostly to dynamic metrics. In case that dynamic metrics are participating in the OF, then frequent routing alterations may result in, which is undesirable since it may lead to routing instabilities or loops. As a solution, a hysteresis factor can be used in this case in order to reduce frequent routing path alterations due to dynamic metric values. Example 4: Consider the simple LLN topology depicted in Figure 5, where the OF consists of HP and (concave) RE metrics, following the lexical metric composition approach (HP, RE). In this case, node D will select node B as its parent to forward traffic data packets, since w(A,B,D)>w(A,C,D). Furthermore, considering that the cost of forwarding a data packet reduces the RE percentage by 0.02, then the metric values at the next DIO transmission of node B will be <2 , 0.78>, while the next DIO transmission of node C will be <2 , 0.79>. These advertised values will lead node D to select node C as its parent node and thus forward next traffic data packet through node C. Apparently, node D alters its parent selection on a per-packet basis, which may lead to routing inconsistencies (viewed in a larger scale). One solution to this issue MIGHT be the introduction of the hysteresis factor, where the node will switch to another parent only if its path value exceeds the minimum path value by a predefined threshold, as described in [I-D.ietf-roll-minrank-hysteresis-of]. Zahariadis, et al. Expires May 27, 2013 [Page 14] Internet Draftdraft-zahariadis-roll-metrics-composition-04 November 2012 +-------------------------------------------------------------------+ | (1.0)(A) <1 , 1.0> | | / \ | | / \ | | / \ | | / \ | | / \ | | / \ | | / \ | | <2 , 0.8> (B)(0.8) (0.79)(C) <2 , 0.79> | | \ / | | \ / | | \ / | | \ / | | \ / | | \ / | | \ / | | (D)(0.7) | +-------------------------------------------------------------------+ Figure 5: Implication of dynamic metric inclusion in a composite lexical approach. Example 5: As a second example, consider the LLN depicted in Figure 6. The applied composite metric uses ETX and RE. This example will demonstrate an advantage of additive metric composition compared to lexical metric composition. Consider applying lexical metric composition of the precedence vector (ETX, RE). Assuming that ETX values do not change, then node D is always selecting node B as its DODAG parent, leading node B to energy depletion. On the contrary, setting proper values in the additive metric composition function of the form (a1*ETX)+(a2*RE), remaining energy percentage value is taken into consideration and after a number of interactions (data traffic forwarding) with node B, node D will switch to node C as its parent. Obviously, the frequency of this switching process is directly proportional to the values of a1 and a2. Zahariadis, et al. Expires May 27, 2013 [Page 15] Internet Draftdraft-zahariadis-roll-metrics-composition-04 November 2012 +-------------------------------------------------------------------+ | (1.0)(A) <1.0 , 1.0> | | / \ | | / \ | | / \ | | 1.3 / \ 1.3 | | / \ | | / \ | | / \ | | <2.3 , 0.8> (B)(0.8) (0.79)(C) <2.3 , 0.79> | | \ / | | \ / | | \ / | | 1.4 \ / 1.3 | | \ / | | \ / | | \ / | | (D)(0.7) | | w(A,B,D) = <3.7 , 0.56> | | w(A,C,D) = <3.6 , 0.55> | +-------------------------------------------------------------------+ Figure 6: An advantage of additive metric composition compared to lexical metric composition approach. 5.9 Composite metric MUST hold properties of isotonicity and monotonicity. Monotonicity means that the path weight increases when prefixed or suffixed by another path (or link). A routing metric is monotonic if and only if w(a)<=w(a&b) and w(a)<=w(c&a) (where '&' denotes the metric operator) for any paths a,b,c. Moreover, the routing metric is right-monotonic if only the former inequality holds, and left- monotonic if only the latter inequality holds. Finally, a routing metric is defined as strictly monotonic if both w(a)