Skip to main content

Design Guidelines for Routing Metrics Composition in LLN
draft-zahariadis-roll-metrics-composition-03

The information below is for an old version of the document.
Document Type
This is an older version of an Internet-Draft whose latest revision state is "Expired".
Authors Theodore Zahariadis , Panagiotis Trakadas
Last updated 2012-05-24
RFC stream (None)
Formats
Stream Stream state (No stream defined)
Consensus boilerplate Unknown
RFC Editor Note (None)
IESG IESG state I-D Exists
Telechat date (None)
Responsible AD (None)
Send notices to (None)
draft-zahariadis-roll-metrics-composition-03
ROLL                                                 Th. Zahariadis, Ed.
Internet Draft                                                    TEIHAL
Intended Status: Informational                          P. Trakadas, Ed.
Expires: November 24, 2012                                          ADAE
                                                            May 23, 2012

        Design Guidelines for Routing Metrics Composition in LLN
              draft-zahariadis-roll-metrics-composition-03

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) 2011 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 November 24, 2012                [Page 1]
Internet Draftdraft-zahariadis-roll-metrics-composition-02 November 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 . . . . . . . . . . . . . . . . . . . . . . . .  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  Applicability to RPL  . . . . . . . . . . . . . . . . . . . . .  7
     3.1  Lexical Metric Composition  . . . . . . . . . . . . . . . .  8
     3.2  Additive Metric Composition . . . . . . . . . . . . . . . .  8
   4  Composition Metrics Requirements  . . . . . . . . . . . . . . .  8
     4.1  Metrics MUST be well-defined. . . . . . . . . . . . . . . .  9
     4.2  Metrics MUST reflect the basic characteristics of LLNs. . .  9
     4.3  Metrics MUST be orthogonal and not antagonistic.  . . . . . 11
     4.4  Metrics MUST exhibit continuity.  . . . . . . . . . . . . . 11
     4.5  Metrics MUST be scalable. . . . . . . . . . . . . . . . . . 11
     4.6  Metrics must have known and identified sources of
          inaccuracies and measurement uncertainties. . . . . . . . . 11
     4.7  Metrics MUST follow the same properties and rules.  . . . . 12
     4.8  Frequent metric values alterations SHALL NOT lead to 
          routing inconsistencies.  . . . . . . . . . . . . . . . . . 13
     4.9  Composite metric MUST hold properties of isotonicity and 
          monotonicity. . . . . . . . . . . . . . . . . . . . . . . . 15
   5. Generic Rules for Metrics Composition . . . . . . . . . . . . . 17
   6  Conclusion  . . . . . . . . . . . . . . . . . . . . . . . . . . 18
   7  Security Considerations . . . . . . . . . . . . . . . . . . . . 19
   8  IANA Considerations . . . . . . . . . . . . . . . . . . . . . . 19
   9  Acknowledgement . . . . . . . . . . . . . . . . . . . . . . . . 19
   10  References . . . . . . . . . . . . . . . . . . . . . . . . . . 19
     10.1  Normative References . . . . . . . . . . . . . . . . . . . 19
     10.2  Informative References . . . . . . . . . . . . . . . . . . 20
   Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 21

 

Zahariadis, et al.     Expires November 24, 2012                [Page 2]
Internet Draftdraft-zahariadis-roll-metrics-composition-02 November 2011

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 November 24, 2012                [Page 3]
Internet Draftdraft-zahariadis-roll-metrics-composition-02 November 2011

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 November 24, 2012                [Page 4]
Internet Draftdraft-zahariadis-roll-metrics-composition-02 November 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 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 November 24, 2012                [Page 5]
Internet Draftdraft-zahariadis-roll-metrics-composition-02 November 2011

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 November 24, 2012                [Page 6]
Internet Draftdraft-zahariadis-roll-metrics-composition-02 November 2011

   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  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
 

Zahariadis, et al.     Expires November 24, 2012                [Page 7]
Internet Draftdraft-zahariadis-roll-metrics-composition-02 November 2011

   version.

   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.

3.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.

3.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.

4  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 November 24, 2012                [Page 8]
Internet Draftdraft-zahariadis-roll-metrics-composition-02 November 2011

4.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.

4.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 November 24, 2012                [Page 9]
Internet Draftdraft-zahariadis-roll-metrics-composition-02 November 2011

   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 November 24, 2012               [Page 10]
Internet Draftdraft-zahariadis-roll-metrics-composition-02 November 2011

   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.

4.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.

4.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.

4.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.

4.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 November 24, 2012               [Page 11]
Internet Draftdraft-zahariadis-roll-metrics-composition-02 November 2011

4.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 <ETX, RE>. 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 November 24, 2012               [Page 12]
Internet Draftdraft-zahariadis-roll-metrics-composition-02 November 2011

   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).

4.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 November 24, 2012               [Page 13]
Internet Draftdraft-zahariadis-roll-metrics-composition-02 November 2011

   +-------------------------------------------------------------------+
   |                           (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 November 24, 2012               [Page 14]
Internet Draftdraft-zahariadis-roll-metrics-composition-02 November 2011

   +-------------------------------------------------------------------+
   |                           (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.

4.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)<w(a&b) and
   w(a)<w(c&a) hold. If the routing metric is monotonic, then
   convergence and loop-freeness 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. In
   mathematical form, a routing metric is isotonic if and only if
   w(a)<=w(b) implies both w(a&c)<=w(b&c) and w(c&a)<=w(c&b) for all
   paths a,b,c. In accordance to monotonicity, left-, right- and strict
   isotonicity can be defined, respectively. If the algebra is isotonic,
   then the paths onto which routing protocols converge are optimal.

   According to [Yang], RPL, as a distance vector based, hop-by-hop
   routing protocol must be left-monotonic and left-isotonic in order to
 

Zahariadis, et al.     Expires November 24, 2012               [Page 15]
Internet Draftdraft-zahariadis-roll-metrics-composition-02 November 2011

   fulfil the routing algebra requirements of convergence, optimality
   and loop-freeness.

   Example 6: Consider the LLN topology, as shown in Figure 7. The basic
   metrics taken into consideration are Latency and Throughput.

   Latency metric (L) is defined as the sum of the transmission
   latencies along the path to the root node for a fixed-size packet.
   Thus, each node selects as its parent the node advertising path with
   minimum aggregated latency value. In other words, the metric operator
   is '+' and the metric order relation is '<'.

   Throughput metric (T) is defined as the minimum throughput value
   along the path to the root. Under this metric, each node will select
   as its parent the node advertising the maximum value of path
   throughput. Thus, for this metric: the metric operator is 'min' and
   the metric order relation is 'max'.

   In this example, the composite metric is defined as (L + (1/T)) with
   '<=' as the composite metric order relation.

   Since the contribution of any path increases the non-negative
   composite metric value and one is minimizing along the non-decreasing
   paths, the metric satisfies the property of monotonicity.

   On the contrary, isotonicity does not hold for this composite metric.
   

   Calculating path values, it is straightforward that node D selects
   node B as its parent node, since w(A,B,D)<w(A,C,D), sending (via DIO
   Metric Container) the pair of values <6 , 0.8> to node E. Having node
   D as its only potential parent, node E will recalculate Latency and
   Throughput values and transmit the pair of path values <11 , 0.3>,
   although it can be computed that w(A,B,D,E)>w(A,C,D,E). Finally,
   comparing the pair of values received by nodes E and G, node H will
   select node G as its parent and route traffic through the path H-G-F-
   A. However, according to this composite metric the optimal path is
   the one traversing H-E-D-C-A. This stems from the fact that the
   optimal path for the pair of source-destination nodes A-D is A-B-D,
   while the optimal path for the pair of A-E is A-C-D-E. 

   This example proves that utilizing a composite metric that does not
   satisfy the property of isotonicity (L + (1/T) in this case) may lead
   to the selection of a non-optimal path.

 

Zahariadis, et al.     Expires November 24, 2012               [Page 16]
Internet Draftdraft-zahariadis-roll-metrics-composition-02 November 2011

   +-------------------------------------------------------------------+
   |                   -------------(A) <1 , 1.0>                      |
   |                  /             / \                                |
   |                 /             /   \                               |
   |       (6 , 0.9)/    (3 , 0.8)/     \(2 , 0.3)                     |
   |               /             /       \                             |
   |              /             /         \                            |
   |             /             /           \                           |
   |            /             /             \                          |
   | <6 , 0.9>(F)   <4 , 0.8>(B)            (C) <3 , 0.3>              |
   |           |              \             /                          |
   |  (5 , 0.6)|               \           /                           |
   |           |       (2 , 0.8)\         /(2 , 0.8)                   |
   |           |                 \       /                             |
   |<12 , 0.6>(G)                 \     /                              |
   |           |                   \   /                               |
   |           |                    \ /                                |
   |           |                    (D) w(A,B,D) = <6 , 0.8> = 7.25    |
   |           |                     |  w(A,C,D) = <5 , 0.3> = 8.33    |
   |            \           (5 , 0.3)|                                 |
   |             \                   |                                 |
   |              \         <6 , 2> (E) w(A,B,D,E) = <11 , 0.3> = 14.33|
   |               \      ----------/   w(A,C,D,E) = <10 , 0.3> = 13.33|
   |       (2 , 0.8)\    /(2 , 0.8)                                    |
   |                 \  /                                              |
   |                 (H)  w(A,F,G,H)  = <14 , 0.6> = 15.66             |
   |                     w(A,B,D,E,H) = <13 , 0.3> = 16.33             |
   |                     w(A,C,D,E,H) = <12 , 0.3> = 15.33             |
   |                                                                   |
   +-------------------------------------------------------------------+
   Figure 7: Adoption of a non-isotonic routing metric leads to non-
   optimal paths selection. 

5. Generic Rules for Metrics Composition

   Taking into consideration the composition metrics requirements
   discussed above, this section provides generic composition rules that
   must be used during combination of basic or derived metrics to
   achieve convergence, optimality and loop-freeness for the RPL routing
   protocol.

   1. Any two basic or derived metrics can be combined in the lexical
   approach given that the metric to be used first in this composition
   is strictly isotonic. As an example, HP and ETX can be used in any
   precedence to define a composite metric that guarantees routing
   algebra requirements (monotonicity and isotonicity). Moreover,
   latency and packet loss percentage (being additive and multiplicative
   metrics, respectively) can be combined in a lexical composition
 

Zahariadis, et al.     Expires November 24, 2012               [Page 17]
Internet Draftdraft-zahariadis-roll-metrics-composition-02 November 2011

   function.

   2. Two additive routing metrics can be composed in an additive
   manner, given that they follow the same properties and rules (namely
   metric operator and metric order relation). A simple example could be
   the utilization of a composition function of the form a1*HP+a2*ETX.
   The question arising is whether multiplicative metrics can also be
   used in such an approach. Consider, for example, a reliability metric
   such as packet loss percentage. By applying logarithmic function to
   this basic metric, one can define a derived metric that follows the
   additive metric operator and share the same order relation with ETX.
   By properly modifying the metric domain of the newly derived metric,
   a combination with ETX can be achieved under the additive metric
   composition.

   From the abovementioned rules, it is obvious that lexical approach is
   less restrictive, offering combinations among a plethora of additive,
   multiplicative and concave metrics, according to user or application-
   specific requirements. On the other hand, combining routing metrics
   in an additive manner is more demanding in terms of mathematical
   formulation. However, achieving to define a composite routing metric
   under the additive approach is advantageous since it offers the
   flexibility to set proper values to the weighting factors of the
   composed metrics and thus satisfy quality of service requirements
   according to user demand. On the contrary, following the lexical
   approach, such flexibility is not possible since the metric used
   first in lexical approach is dominating over the second metric.
   Concluding, as a general rule of thumb, in cases where maximization
   in terms of a specific metric is required while the second metric is
   used only as a tie-break, lexical approach is to be used. On the
   contrary, in cases where two link or node characteristics must be
   captured in a more balanced manner, the utilization of the additive
   composition approach is advantageous.

6  Conclusion

   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 and derived metrics.

 

Zahariadis, et al.     Expires November 24, 2012               [Page 18]
Internet Draftdraft-zahariadis-roll-metrics-composition-02 November 2011

7  Security Considerations

   No new considerations are raised  this document.

8  IANA Considerations

   This document includes no request to IANA.

9  Acknowledgement

   The work presented in this I-D is partially supported by the EU-
   funded FP7-ICT-257245 VITRO project. Apart form this, the European
   Commission has no responsibility for the content of this document.

10  References

10.1  Normative References

   [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
              Requirement Levels", BCP 14, RFC 2119, March 1997.

   [RFC6550]  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", March 2012.

   [RFC6552]  Thubert, P., "RPL Objective Function 0", draft-ietf-roll-
              of0-20 (work in progress), March 2012.

   [RFC6551] Vasseur, J., Kim, M., Pister, K., Dejean, N., and D.
              Barthel, "Routing Metrics used for Path Calculation in Low
              Power and Lossy Networks", March 2012.

   [I-D.ietf-roll-minrank-hysteresis-of]  Gnawali, O., and P. Levis,
              "The Minimum Rank Objective Function with Hysteresis",
              draft-ietf-roll-minrank-hysteresis-of-10 (work in
              progress), April 2012.

   [I-D.ietf-roll-applicability-ami]  Popa, D., Jetcheva, J., Dejean,
              N., Salazar, R., Hui, J., and K. Monden, "Applicability
              Statement for the Routing Protocol for Low Power and Lossy
              Networks (RPL) in AMI Networks", draft-ietf-roll-
              applicability-ami-06 (work in progress), April 2012.

 

Zahariadis, et al.     Expires November 24, 2012               [Page 19]
Internet Draftdraft-zahariadis-roll-metrics-composition-02 November 2011

10.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.

 

Zahariadis, et al.     Expires November 24, 2012               [Page 20]
Internet Draftdraft-zahariadis-roll-metrics-composition-02 November 2011

Authors' Addresses

   Theodore Zahariadis (editor)
   Technological Educational Institute of Halkida (TEIHAL)
   Psachna, Evia, 34400, Greece.

   EMail: zahariad@teihal.gr

   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 November 24, 2012               [Page 21]