idnits 2.17.1 draft-zahariadis-roll-metrics-composition-04.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- No issues found here. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year == Line 893 has weird spacing: '... raised this ...' -- The document date (November 23, 2012) is 4171 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- -- Looks like a reference, but probably isn't: '0' on line 574 -- Looks like a reference, but probably isn't: '7' on line 560 -- Looks like a reference, but probably isn't: '255' on line 289 -- Looks like a reference, but probably isn't: '1' on line 624 -- Looks like a reference, but probably isn't: '512' on line 624 == Unused Reference: 'I-D.ietf-roll-terminology' is defined on line 937, but no explicit reference was found in the text == Outdated reference: A later version (-11) exists of draft-ietf-roll-minrank-hysteresis-of-10 == Outdated reference: A later version (-15) exists of draft-ietf-roll-applicability-ami-06 == Outdated reference: A later version (-13) exists of draft-ietf-roll-terminology-04 Summary: 0 errors (**), 0 flaws (~~), 6 warnings (==), 6 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 ROLL Th. Zahariadis, Ed. 3 Internet Draft TEIHAL 4 Intended Status: Informational P. Trakadas, Ed. 5 Expires: May 27, 2013 ADAE 6 November 23, 2012 8 Design Guidelines for Routing Metrics Composition in LLN 9 draft-zahariadis-roll-metrics-composition-04 11 Abstract 13 This document specifies the guidelines for designing efficient 14 composite routing metrics to be applied to the Routing for Low Power 15 and Lossy Networks (RPL) routing protocol. 17 Status of this Memo 19 This Internet-Draft is submitted to IETF in full conformance with the 20 provisions of BCP 78 and BCP 79. 22 Internet-Drafts are working documents of the Internet Engineering 23 Task Force (IETF), its areas, and its working groups. Note that 24 other groups may also distribute working documents as 25 Internet-Drafts. 27 Internet-Drafts are draft documents valid for a maximum of six months 28 and may be updated, replaced, or obsoleted by other documents at any 29 time. It is inappropriate to use Internet-Drafts as reference 30 material or to cite them other than as "work in progress." 32 The list of current Internet-Drafts can be accessed at 33 http://www.ietf.org/1id-abstracts.html 35 The list of Internet-Draft Shadow Directories can be accessed at 36 http://www.ietf.org/shadow.html 38 Copyright and License Notice 40 Copyright (c) 2012 IETF Trust and the persons identified as the 41 document authors. All rights reserved. 43 This document is subject to BCP 78 and the IETF Trust's Legal 44 Provisions Relating to IETF Documents 45 (http://trustee.ietf.org/license-info) in effect on the date of 46 publication of this document. Please review these documents 47 carefully, as they describe your rights and restrictions with respect 48 to this document. Code Components extracted from this document must 49 include Simplified BSD License text as described in Section 4.e of 50 the Trust Legal Provisions and are provided without warranty as 51 described in the Simplified BSD License. 53 Table of Contents 55 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 56 1.1 Terminology . . . . . . . . . . . . . . . . . . . . . . . . 4 57 1.2 Motivation . . . . . . . . . . . . . . . . . . . . . . . . 5 58 2 Basic and Derived Metrics Properties and Rules . . . . . . . . 5 59 2.1 Metric Domain . . . . . . . . . . . . . . . . . . . . . . . 6 60 2.2 Metric Operator . . . . . . . . . . . . . . . . . . . . . . 6 61 2.3 Metric Order Relation . . . . . . . . . . . . . . . . . . . 6 62 3 Trust-Aware Routing Metric . . . . . . . . . . . . . . . . . . 7 63 3.1 Packets Forwarding Indication . . . . . . . . . . . . . . . 8 64 4 Applicability to RPL . . . . . . . . . . . . . . . . . . . . . 8 65 4.1 Lexical Metric Composition . . . . . . . . . . . . . . . . 9 66 4.2 Additive Metric Composition . . . . . . . . . . . . . . . . 9 67 5 Composition Metrics Requirements . . . . . . . . . . . . . . . 9 68 5.1 Metrics MUST be well-defined. . . . . . . . . . . . . . . . 10 69 5.2 Metrics MUST reflect the basic characteristics of LLNs. . . 10 70 5.3 Metrics MUST be orthogonal and not antagonistic. . . . . . 12 71 5.4 Metrics MUST exhibit continuity. . . . . . . . . . . . . . 12 72 5.5 Metrics MUST be scalable. . . . . . . . . . . . . . . . . . 12 73 5.6 Metrics must have known and identified sources of 74 inaccuracies and measurement uncertainties. . . . . . . . . 12 75 5.7 Metrics MUST follow the same properties and rules. . . . . 13 76 5.8 Frequent metric values alterations SHALL NOT lead to 77 routing inconsistencies. . . . . . . . . . . . . . . . . . 14 78 5.9 Composite metric MUST hold properties of isotonicity and 79 monotonicity. . . . . . . . . . . . . . . . . . . . . . . . 16 80 6. Generic Rules for Metrics Composition . . . . . . . . . . . . . 18 81 7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . 19 82 8 Security Considerations . . . . . . . . . . . . . . . . . . . . 20 83 9 IANA Considerations . . . . . . . . . . . . . . . . . . . . . . 20 84 10 Acknowledgement . . . . . . . . . . . . . . . . . . . . . . . 20 85 11 References . . . . . . . . . . . . . . . . . . . . . . . . . . 20 86 11.1 Normative References . . . . . . . . . . . . . . . . . . . 20 87 11.2 Informative References . . . . . . . . . . . . . . . . . . 21 88 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 22 90 1 Introduction 92 Low Power and Lossy Networks (LLNs) have specific routing 93 requirements, as described in [RFC5548], [RFC5673], [RFC5826], 94 [RFC5867], and [I-D.ietf-roll-applicability-ami]. In these RFCs, 95 several (and sometimes contradicting) requirements are set by each 96 application domain. In order to cope with them, a number of routing 97 metrics and constraints has been spelled out in [RFC6551], consisting 98 of link/node, qualitative/quantitative, static/dynamic metrics and 99 constraints. According to [RFC6550], these metrics and constraints 100 are carried in objects that are OPTIONAL within RPL messages. 102 Path computation algorithms for single metrics have already been 103 proposed and used in [RFC6552], and [I-D.ietf-roll-minrank- 104 hysteresis-of]. 106 For providing Quality-of-Service (QoS) routing in future 107 applications, the Objective Function (OF) and Rank value might be 108 built upon a composite metric, consisting of several basic and 109 derived metrics, as defined in [RFC6551]. 111 The intention of this document is to set the guidelines for the 112 proper selection of basic and derived metrics as well as the design 113 of composite routing metrics for LLNs, taking into consideration the 114 theoretical framework of [Sobrinho], as refined by [Yang]. Thus, the 115 main target of this document is to examine the properties that 116 routing metrics must hold to provide convergence, optimality and 117 loop-freeness for the RPL routing protocol. In this way, each node 118 will select the shortest path (or shortest constraint path, in the 119 presence of constraints). 121 The document does not intend to provide one composite metric that 122 fits all cases, but rather to sketch out the guidelines for designing 123 appropriate composite metrics, in line with specific application 124 requirements. The purpose of this document is to provide a common 125 framework for various classes of metrics that are composed of basic 126 metrics. 128 The effectiveness and performance of composite metrics used for IP 129 performance evaluation is beyond the scope of this document and can 130 be found in [RFC2330], [RFC5835] and [RFC6049]. 132 Finally, it is assumed that the reader is familiar with the concepts 133 of [RFC6550] and [RFC6551]. 135 1.1 Terminology 137 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 138 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 139 document are to be interpreted as described in RFC2119 [RFC2119]. 141 This document makes use of the terminology defined in [I-D.ietf-roll- 142 terminology]. Moreover, this document defines the following terms, in 143 accordance with [RFC5835] terminology: 145 basic metric: a metric governed by specific rules and properties, 146 capturing specific link or node characteristics. Examples 147 of basic metrics are hop-count, ETX, LQL, etc. 149 derived metric: a metric that is defined in terms of a basic metric, 150 retaining the properties and rules of the basic metric. 151 For example, (1-(1/ETX)) is an ETX derived metric, since 152 it retains the rules and properties of the basic metric 153 (ETX). 155 composite metric: is defined as a routing metric consisting of 156 several basic or/and derived metrics by applying a 157 deterministic process or function (composition function). 159 composition function: a deterministic process applied to primary 160 and/or derived metrics to derive a composite metric. 162 optimal path: is defined as a path in the DAG that minimizes (or 163 maximizes, respectively) the Rank value between any given 164 pair of source-destination nodes, as well as its sub- 165 paths. 167 sub-path: is defined as any portion of the path traversed between any 168 given pair of source-destination nodes. 170 path weight: a value representing link or/and node characteristics of 171 a path. This definition coincides with 'path cost' defined 172 in [I-D.ietf-roll-minrank-hysteresis-of]. Path weight is 173 used by RPL to compare different paths. 175 metric order relation: is used for path weight comparison with the 176 same source and destination nodes, leading to the next hop 177 neighbor selection. For example: '>' (greater than) is an 178 order relation. 180 metric operator: is used for the transformation of link and node 181 weights into path weights. As an example, addition '+' is 182 defined as a metric operator. 184 1.2 Motivation 186 Different metrics are defined to capture different link and node 187 characteristics of a path. For example, some metrics capture network 188 latency, some others take into account energy consumption of a node, 189 while others focus on link reliability. The diversity of RPL routing 190 protocol application domains, as described in [RFC5548], [RFC5673], 191 [RFC5826], [RFC5867], and [I-D.ietf-roll-applicability-ami] motivate 192 the design of different composite routing metrics to cope with 193 different routing application requirements. 195 However, the selection of basic and derived metrics to design an 196 efficient composite metric is neither an arbitrary nor a trivial 197 task. Combining routing metrics of different types may lead to 198 routing loops or selection of non-optimal paths. 200 This document presents the guidelines for designing QoS routing 201 strategies set by different applications, by identifying the 202 properties that a composite metric must hold in order to work 203 seamlessly with RPL routing protocol. 205 2 Basic and Derived Metrics Properties and Rules 207 Routing metrics are the representation of an LLN in routing process. 208 Thus, they might result in major implications on the complexity of 209 optimal path computation, the existence of optimal path and the range 210 of application requirements that can be supported. 212 Path computation algorithms using one basic metric have been widely 213 used in the literature and practice [RFC6552], [I-D.ietf-roll- 214 minrank-hysteresis-of]. However, in order to support a wide range of 215 QoS requirements dictated by different application domains, several 216 routing metrics forming a composite metric must be taken into 217 account. 219 RPL is a distance vector based, hop-by-hop routing protocol that 220 builds Directed Acyclic Graphs (DAG) based on routing metrics and 221 constraints. Following the routing algebra formalism presented in 222 [Sobrinho] and [Yang], routing metrics must hold specific properties 223 (isotonicity and monotonicity) in order to fulfil routing protocol 224 requirements (convergence, optimality and loop-freeness). 226 In the following sections, basic metrics are examined and categorized 227 according to their properties and rules. This exercise will provide 228 useful information for the composition of efficient composite 229 metrics. 231 2.1 Metric Domain 233 Basic metrics are defined in different domains. For example, Hop- 234 Count (HP) has the value of 1 (per-hop), while ETX is defined in [1, 235 512] and LQL in [0, 7], where 0 means undetermined, 1 indicates the 236 highest and 7 the lowest link quality. Intuitively, the selection of 237 the basic metrics to derive a composite metric MUST take into account 238 the domain of each one of the selected basic metrics. This can be 239 achieved by defining derived metrics, as will be explained later in 240 this document. 242 2.2 Metric Operator 244 According to [RFC6551], a metric can either be recorded or aggregated 245 along the path. In the latter case, the metric can be of maximum type 246 (A=0x01), minimum type (A=0x02), additive type (A=0x00), or 247 multiplicative type (A=0x03). 249 Let w(i,j) be the metric value for link and node characteristics 250 between nodes i and j. Then, for any path p(i,j,k,...,q,r), we define 251 that: 253 - a metric is additive if: w(p)=w(i,j)+w(j,k)+...+w(q,r), 255 - a metric is multiplicative if: w(p)=w(i,j)*w(j,k)*...*w(q,r), 257 - a metric is concave if: w(p)=max[w(i,j),w(j,k),...,w(q,r)] or 258 w(p)=min[w(i,j),w(j,k),...,w(q,r)]. 260 Metrics differ in the aggregation rule they follow. As an example, HP 261 and ETX are defined as additive metrics, while Throughput and 262 Bandwidth are representative examples of concave metrics. 264 Thus, the composite metric must also take into account the metric 265 operators of the selected basic/derived metrics. 267 2.3 Metric Order Relation 269 Another categorization of basic metrics is derived from the fact that 270 some are 'maximizable' (the higher value, the better) while others 271 are 'minimizable' (the lower value, the better). For example, a node 272 selects as its DODAG parent the neighboring node that advertises (via 273 DIO messages) the minimum hop-count (or aggregated ETX) value to 274 reach DAG root node. On the other hand, if the Objective Function is 275 based on RSSI (or Throughput) values, then the maximum value will 276 lead the process of the DODAG parent selection. 278 In Figure 1, the properties and rules for some well-known basic 279 metrics used in LLNs are presented. 281 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 282 | Metric | Domain | Aggregation Rule |Order Relation | 283 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 284 | Hop-count | 1 | additive | < | 285 | ETX | [1,512]*128 | additive | < | 286 | LQL | [0,7] | concave (max.) | < (excl. 0) | 287 | Latency | 32-bit integer | additive | < | 288 | Throughput | 32-bit integer | concave (min.) | > | 289 | RSSI | [0,255] | additive | > | 290 | Packet Loss%| [0,1] | multiplicative | < | 291 | Rem. Energy%| [0,1] | concave (min.) | > | 292 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 293 Figure 1. Properties and rules of basic routing metrics used in LLNs. 295 The properties and rules for the majority of routing metrics shown in 296 this Figure follow the description presented in [RFC6551]. However, 297 it is important to mention that a routing metric MAY follow different 298 properties and rules. As an example, remaining energy percentage MAY 299 also be defined as additive (metric operator) with '>' as a metric 300 order relation. The same remark applies to Link Color metric. 302 Moreover, some of the abovementioned link or node metrics may also be 303 used by RPL as constraints. In such cases, if a link or a node does 304 not satisfy a required constraint, it is excluded from the candidate 305 neighbor set, leading to a constrained shortest path (NP-complete 306 problem). However, this draft mainly focuses on setting the 307 requirements for optimal path selection, among several paths 308 satisfying all supplied constraints (if any). 310 3 Trust-Aware Routing Metric 312 Cooperation among nodes in LLNs raises high concerns regarding 313 security issues. Most solutions available in the literature try to 314 secure networking operations using traditional security techniques, 315 such as encryption and key management. However, the implementation of 316 such security measures comes at a high cost, since it requires 317 significant memory and processing resources, increasing at the same 318 time the energy consumption. To defend against a number of routing 319 attacks, an alternative but rather efficient approach is trust 320 management. Following this approach, LLN nodes establish trust 321 relations based on their expectation that their neighbors will 322 sincerely cooperate on particular tasks (data forwarding). This 323 concept allows one to define and utilize a trust-aware routing metric 324 for the selection of the routing path. 326 Although this issue has been extensively discussed in the literature, 327 no attention has been paid on the definition of a trust-aware metric 328 for LLNs, that can be directly and efficiently combined with other 329 metrics, fulfilling routing metrics properties and thus ensuring 330 routing protocol requirements, as discussed above. 332 3.1 Packets Forwarding Indication 334 Packets Forwarding Indication (PFI) is defined as an effective trust- 335 aware routing metric, capable of capturing the forwarding willingness 336 of the neighboring nodes. Following the concept of ETX, PFI is 337 defined as the inverse probability that node B will forward a packet 338 received coming from node A and is expressed as PFI(A,B)=Ns/Nt, where 339 Ns is the number of successfully forwarded packets (originating from 340 node A) by node B, and Nt is the total number of packets that node A 341 sent to node B for further forwarding. Thus, PFI expresses the 342 expected number of transmissions required for a packet to reach its 343 destination (edge router) when denial of forwarding occurs (e.g. 344 black-hole, grey-hole attack). As a result, PFI calculated for a path 345 is subject to the reaction of a node's perception in terms of a 346 neighbor's forwarding willingness. Specifically, PFI path weights 347 depend on the capability of re-transmitting every packet that has not 348 been further forwarded. 350 According to the analysis presented in [Velivasaki], PFI can be 351 considered either as an additive routing metric, defined in [1,+inf], 352 or as a multiplicative metric that fulfills the routing algebra 353 requirements for strict isotonicity and strict monotonicity and thus 354 can be combined with other routing metrics as will be discussed 355 below. 357 4 Applicability to RPL 359 According to [RFC6550], Objective Function (OF) defines how routing 360 metrics, optimization objectives and related functions are used to 361 compute Rank. Furthermore, OF dictates how parents in the DODAG are 362 selected and thus the DODAG formation is defined by OF. 364 On the other hand, Rank defines the node's individual position 365 relative to other nodes with respect to a DODAG root. Rank strictly 366 increases in the Down direction (towards leaf nodes) and strictly 367 decreases in the Up direction (towards root node). The exact way Rank 368 is computed, depends on the DAG's OF, as mentioned earlier. 370 Furthermore, according to [RFC6550], minHopRankIncrease value is 371 defined as the minimum increase in Rank between a node and any of its 372 DODAG parents, while maxRankIncrease is defined as the maximum value 373 increase that a given node can advertise within the same DODAG 374 version. 376 There are two distinct approaches to follow, regarding the usability 377 of multiple basic or derived routing metrics into one composite 378 metric in RPL routing protocol, namely the lexical metric composition 379 and the additive metric composition. 381 4.1 Lexical Metric Composition 383 According to the lexical metric composition approach, when comparing 384 two composite metric values, the node will select as a DODAG parent 385 the node with the lower (or greater, respectively) value of the first 386 composition metric, and if the first component values are equal (or 387 differ less than a predefined threshold) then it will select the one 388 with the lower (or greater, respectively) value of the second 389 composition metric. Some examples of well-known composite lexical 390 metrics used in IP networks are 'widest-shortest' path, that selects 391 the widest path among the set of shortest paths between the source 392 and the destination node, and 'most reliable-shortest' path, that 393 selects the most reliable path among the set of shortest paths. 395 This is totally in line with the "Prec" field carried within the DAG 396 Metric Container Object defined in [RFC6550] and [RFC6551] that 397 indicates the precedence of each routing metric (or constraint) 398 present in the Objective Function. 400 4.2 Additive Metric Composition 402 According to the additive metric composition, the Rank is evaluated 403 based on a defined OF (composition function) and advertised through 404 the DIO message. Moreover, the values of the basic metrics are 405 aggregated along the path and are included in the DAG Metric 406 Container Object. 408 This approach is also compatible with RPL specifications, since 409 according to [RFC6551], in this case the relevant flags of the DAG 410 Metric Container Object must be: C = 0, O = 0, A = 0x00, and R = 0. 412 5 Composition Metrics Requirements 414 As discussed in the previous section, the selection of the basic 415 routing metrics for designing a composite metric is not 416 straightforward for the routing solution to fulfil routing protocol 417 requirements (convergence, optimality, loop-freeness). In this 418 section the composition metrics requirements will be examined, 419 followed by explanatory text or representative examples, to guide 420 prospective routing protocol designs and implementations. 422 5.1 Metrics MUST be well-defined. 424 For applying an efficient composite metric, all basic or derived 425 metrics must be well-defined. The use of new or not thoroughly tested 426 basic metrics SHALL be avoided. 428 5.2 Metrics MUST reflect the basic characteristics of LLNs. 430 Each network has its own unique characteristics. As an example, a 431 fundamental concern in ad-hoc networks consists on link reliability 432 and node mobility, while in IP networks, bandwidth and latency are of 433 great importance. In LLNs, the resource constraints of nodes demand 434 primarily for energy conservation, link stability and traffic load 435 balance. Thus, the basic metrics selected for defining a composite 436 metric must be analyzed towards capturing the fundamental 437 characteristics of LLNs. In the following, two simple examples are 438 analyzed, where the composite metric consists of Hop-Count (HP) and 439 ETX metric. 441 +-------------------------------------------------------------------+ 442 | (A) <1 , 1.0> | 443 | / \ | 444 | / \ | 445 | / \ | 446 | 1.3 / \ 1.2 | 447 | / \ | 448 | / \ | 449 | / \ | 450 | <2 , 1.3> (B) (C) <2 , 1.2> | 451 | |\_ _/ | | 452 | | \_ _/ | | 453 | | 1.5\_ _/1.6 | | 454 | 1.3 | \/ | 1.3 | 455 | | _/\_ | | 456 | | _/ \_ | | 457 | | _/ \_ | | 458 | (D) (E) | 459 | w(A,B,D) = <3 , 3.6> w(A,C,E) = <3 , 3.5> | 460 | w(A,C,D) = <3 , 3.8> w(A,B,E) = <3 , 3.8> | 461 +-------------------------------------------------------------------+ 462 Figure 2: Example of a simple composite metric consisting of HP and 463 ETX metrics. 465 Example 1: Consider the LLN depicted in Figure 2, where the metrics 466 taken into account are HP and ETX, as described above. Both metrics 467 are added along the path and these values are advertised through DIO 468 messages. The parentheses present the HP and ETX values, 469 respectively. 471 It is evident that if one applies an OF based on the lexical 472 composition of these two metrics (either 'shortest-most reliable' or 473 'most reliable-shortest'), node D will select node B as its parent, 474 while node E will select node C as its parent in both lexical cases. 476 Similarly, by using the additive metric composition approach in the 477 form of w=(a1*HP)+(a2*ETX), node D will select B as its parent and 478 node E will select C for any combination of a1 and a2 values (given 479 that 0<=a1,a2<=1 and a1+a2=1). 481 Example 2: As a second example, consider the (slightly) more complex 482 LLN depicted in Figure 3. Again, consider applying HP and ETX 483 metrics, added along the traversed paths. This example demonstrates 484 the dependency of the parent selection process dictated by the OF 485 composition function. 487 +-------------------------------------------------------------------+ 488 | (A) <1 , 1.0> | 489 | / \ | 490 | / \ | 491 | / \ | 492 | 1.2 / \ 1.2 | 493 | / \ | 494 | / \ | 495 | / \ | 496 | <2 , 1.2> (B) (C) <2 , 1.2> | 497 | \ | | 498 | \ | 1.1 | 499 | \ | | 500 | 2.8 \ (E) <3 , 2.3> | 501 | \ / | 502 | \ _/ 1.1 | 503 | \ / | 504 | (D) | 505 | w(A,B,D) = <3 , 5.0> | 506 | w(A,C,E,D) = <4 , 4.4> | 507 +-------------------------------------------------------------------+ 508 Figure 3: Dependency of routing process dictated by different OF's. 510 If the 'shortest-most reliable' lexical metric composition is chosen, 511 then node D will select node E as its parent, although the traversed 512 path is not the shortest one. On the contrary, if the 'most reliable- 513 shortest' lexical metric composition approach is chosen, then node D 514 will select node B as its parent, although the traversed path is not 515 the most reliable. 517 Accordingly, following the additive metric composition of the form 518 (a1*HP)+(a2*ETX) implies that if (a1,a2)=(0.8,0.2), then node D will 519 select node B as its parent, while in case that (a1,a2)=(0.2,0.8), 520 node D will select node E as its parent. 522 5.3 Metrics MUST be orthogonal and not antagonistic. 524 Orthogonality means that no redundant information is carried within 525 different basic metrics. As an example, the use of RSSI and LQL for 526 metric composition is not a wise option, since they capture the same 527 LLN characteristic; link reliability. In this way, less computational 528 burden (and possibly fewer message exchange) will be achieved. 530 Moreover, the utilization of antagonistic metrics must be avoided. As 531 antagonistic metrics can be defined those metrics that eliminate the 532 effects of one another. As an example, by definition Hop-Count 533 includes a sense of 'greediness', while RSSI partially eliminates 534 this characteristic, since it promotes the most stable links. 535 Assuming that all nodes use the same transmission power level, then a 536 node, based on RSSI metric, will (most probably) select as parent 537 node the neighbor closer to it. 539 5.4 Metrics MUST exhibit continuity. 541 That is, small variations in metric values, MUST result in small 542 variations in the composite metric value. This requirement is more 543 related to derived metrics. Special attention must be paid so that 544 the derived metrics do not produce either instabilities or 545 inconsistencies. 547 5.5 Metrics MUST be scalable. 549 A composite metric must be able to scale to large LLNs (or even 550 Internet). This requirement is relevant to path computation 551 complexity, since the complexity of the path computation is 552 determined by the composition rules of the metric. Especially in 553 LLNs, this requirement is of great importance, taking into account 554 that the computational power of LLN nodes is constrained. 556 5.6 Metrics must have known and identified sources of inaccuracies and 557 measurement uncertainties. 559 Most of the basic metrics are prone to inaccuracies. A representative 560 example is LQL, as defined in [RFC6551], defined in [0,7] domain. 561 Only seven discrete values are used for LQL quantification (0 is 562 excluded). Thus, a range of link quality values will be represented 563 by the same LQL value. In other words, when such metrics are used, 564 the sources of inaccuracies must be, at least, identified. 566 5.7 Metrics MUST follow the same properties and rules. 568 As described above, the combination of metrics retaining different 569 properties and rules may lead to routing instabilities and selection 570 of non-optimal paths. So, the basic routing metrics with different 571 properties must be transformed to derived metrics holding the same 572 properties in order to be used for metric composition. For example, 573 in case that ETX ([1,512], '+', '<') is used in conjunction to the 574 node remaining energy percentage (RE) ([0,1], '*', '>'), then a 575 derived metric must be used for the remaining energy (e.g. 1/RE). 576 With this transformation, both metrics are defined at the same 577 domain, they are additive, and are using '<' as the order relation. 579 Example 3: Consider the LLN depicted in Figure 4, where the metrics 580 taken into consideration are ETX and Remaining Energy percentage, 581 shown as . Also, each node has a remaining energy 582 percentage, as shown in the parenthesis next to each node, e.g. node 583 B has a remaining energy percentage value of 0.8, while node C has a 584 remaining energy percentage value equal to 1.0. 586 +-------------------------------------------------------------------+ 587 | (1.0)(A) <1.0 , 1.0> | 588 | / \ | 589 | / \ | 590 | / \ | 591 | 1.2 / \ 1.1 | 592 | / \ | 593 | / \ | 594 | / \ | 595 | <2.2 , 0.8> (B)(0.8) (1.0)(C) <2.1 , 1.0> | 596 | \ | | 597 | \ | 1.2 | 598 | \ | | 599 | 2.2 \ (0.6)(E) <3.3 , 0.6> | 600 | \ / | 601 | \ ___/ 1.2 | 602 | \ / | 603 | (D)(0.7) | 604 | w(A,B,D) = <4.4 , 0.56> (4.4+0.56=4.96) | 605 | w(A,C,E,D) = <4.5 , 0.42> (4.5+0.42=4.92) | 606 +-------------------------------------------------------------------+ 607 Figure 4: Composition of metrics with different properties and rules. 609 Applying the two lexical metric composition approaches (ETX or RE 610 precedence), node D will select node B as its parent in both cases. 612 Furthermore, consider that one applies the additive metric 613 composition rule ETX+RE and selects the parent based on the '<' order 614 relation. In this case, node D will select node E as its parent, 615 since w(A,B,D)=4.4+0.56=4.96 > w(A,C,E,D)=4.5+0.42=4.92. This results 616 in from the different properties and rules governing these two basic 617 metrics. 619 A possible solution might be the transformation of RE metric in such 620 a way that metric range, operator and order relation of the derived 621 RE metric coincides with ETX's. This can be achieved by defining the 622 derived RE metric, denoted as dRE, as the inverse of RE (1/RE), 623 defined in the range [1.935*10^-3,1]. In this way, dRE shares the 624 same metric range with ETX, namely [1, 512]. Furthermore, the dRE 625 order relation is '<' and the metric operator is '+'. 627 By applying dRE at the composition function and calculating Rank at 628 node D, it is evident that node B will be selected as node D's parent 629 since (w(A,B,D)=4.4+(1/0.56)=6.1857 < 630 w(A,C,E,D)=4.5+(1/0.42)=6.881). 632 5.8 Frequent metric values alterations SHALL NOT lead to routing 633 inconsistencies. 635 This requirement applies mostly to dynamic metrics. In case that 636 dynamic metrics are participating in the OF, then frequent routing 637 alterations may result in, which is undesirable since it may lead to 638 routing instabilities or loops. As a solution, a hysteresis factor 639 can be used in this case in order to reduce frequent routing path 640 alterations due to dynamic metric values. 642 Example 4: Consider the simple LLN topology depicted in Figure 5, 643 where the OF consists of HP and (concave) RE metrics, following the 644 lexical metric composition approach (HP, RE). 646 In this case, node D will select node B as its parent to forward 647 traffic data packets, since w(A,B,D)>w(A,C,D). Furthermore, 648 considering that the cost of forwarding a data packet reduces the RE 649 percentage by 0.02, then the metric values at the next DIO 650 transmission of node B will be <2 , 0.78>, while the next DIO 651 transmission of node C will be <2 , 0.79>. These advertised values 652 will lead node D to select node C as its parent node and thus forward 653 next traffic data packet through node C. 655 Apparently, node D alters its parent selection on a per-packet basis, 656 which may lead to routing inconsistencies (viewed in a larger scale). 657 One solution to this issue MIGHT be the introduction of the 658 hysteresis factor, where the node will switch to another parent only 659 if its path value exceeds the minimum path value by a predefined 660 threshold, as described in [I-D.ietf-roll-minrank-hysteresis-of]. 662 +-------------------------------------------------------------------+ 663 | (1.0)(A) <1 , 1.0> | 664 | / \ | 665 | / \ | 666 | / \ | 667 | / \ | 668 | / \ | 669 | / \ | 670 | / \ | 671 | <2 , 0.8> (B)(0.8) (0.79)(C) <2 , 0.79> | 672 | \ / | 673 | \ / | 674 | \ / | 675 | \ / | 676 | \ / | 677 | \ / | 678 | \ / | 679 | (D)(0.7) | 680 +-------------------------------------------------------------------+ 681 Figure 5: Implication of dynamic metric inclusion in a composite 682 lexical approach. 684 Example 5: As a second example, consider the LLN depicted in Figure 685 6. The applied composite metric uses ETX and RE. 687 This example will demonstrate an advantage of additive metric 688 composition compared to lexical metric composition. 690 Consider applying lexical metric composition of the precedence vector 691 (ETX, RE). Assuming that ETX values do not change, then node D is 692 always selecting node B as its DODAG parent, leading node B to energy 693 depletion. 695 On the contrary, setting proper values in the additive metric 696 composition function of the form (a1*ETX)+(a2*RE), remaining energy 697 percentage value is taken into consideration and after a number of 698 interactions (data traffic forwarding) with node B, node D will 699 switch to node C as its parent. Obviously, the frequency of this 700 switching process is directly proportional to the values of a1 and 701 a2. 703 +-------------------------------------------------------------------+ 704 | (1.0)(A) <1.0 , 1.0> | 705 | / \ | 706 | / \ | 707 | / \ | 708 | 1.3 / \ 1.3 | 709 | / \ | 710 | / \ | 711 | / \ | 712 | <2.3 , 0.8> (B)(0.8) (0.79)(C) <2.3 , 0.79> | 713 | \ / | 714 | \ / | 715 | \ / | 716 | 1.4 \ / 1.3 | 717 | \ / | 718 | \ / | 719 | \ / | 720 | (D)(0.7) | 721 | w(A,B,D) = <3.7 , 0.56> | 722 | w(A,C,D) = <3.6 , 0.55> | 723 +-------------------------------------------------------------------+ 724 Figure 6: An advantage of additive metric composition compared to 725 lexical metric composition approach. 727 5.9 Composite metric MUST hold properties of isotonicity and 728 monotonicity. 730 Monotonicity means that the path weight increases when prefixed or 731 suffixed by another path (or link). A routing metric is monotonic if 732 and only if w(a)<=w(a&b) and w(a)<=w(c&a) (where '&' denotes the 733 metric operator) for any paths a,b,c. Moreover, the routing metric is 734 right-monotonic if only the former inequality holds, and left- 735 monotonic if only the latter inequality holds. Finally, a routing 736 metric is defined as strictly monotonic if both w(a)