Internet DRAFT - draft-zahariadis-ietf-roll-metrics-composition
draft-zahariadis-ietf-roll-metrics-composition
ROLL Th. Zahariadis, Ed.
Internet Draft TEIHAL
Intended Status: Informational P. Trakadas, Ed.
Expires: March 3, 2012 ADAE
August 31, 2011
Design Guidelines for Routing Metrics Composition in LLN
draft-zahariadis-ietf-roll-metrics-composition-01
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 March 3, 2012 [Page 1]
Internet Draftdraft-zahariadis-roll-metrics-composition-01 August 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. . . . . . . . . . . . . . . . 8
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
4.10 Metrics MUST be normalized. . . . . . . . . . . . . . . . 17
5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . 17
6 Security Considerations . . . . . . . . . . . . . . . . . . . . 17
7 IANA Considerations . . . . . . . . . . . . . . . . . . . . . . 17
8 Acknowledgement . . . . . . . . . . . . . . . . . . . . . . . . 17
9 References . . . . . . . . . . . . . . . . . . . . . . . . . . 18
9.1 Normative References . . . . . . . . . . . . . . . . . . . 18
9.2 Informative References . . . . . . . . . . . . . . . . . . 18
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 19
Zahariadis, et al. Expires March 3, 2012 [Page 2]
Internet Draftdraft-zahariadis-roll-metrics-composition-01 August 2011
1 Introduction
Low Power and Lossy Networks (LLNs) have specific routing
requirements, as described in [RFC5548], [RFC5673], [RFC5826], and
[RFC5867]. In these RFCs, several (and sometimes contradicting)
requirements are set by each application domain. In order to cope
with them, a number of routing metrics and constraints has been
spelled out in [I-D.ietf-roll-routing-metrics], consisting of
link/node, qualitative/quantitative, static/dynamic metrics and
constraints. According to [I-D.ietf-roll-rpl], these metrics and
constraints are carried in objects that are OPTIONAL within RPL
messages.
Path computation algorithms for single metrics have already been
proposed and used in current Internet Drafts [I-D.ietf-roll-of0], 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 [I-D.ietf-roll-routing-metrics].
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 [I-D.ietf-roll-rpl] and [I-D.ietf-roll-routing-metrics].
Zahariadis, et al. Expires March 3, 2012 [Page 3]
Internet Draftdraft-zahariadis-roll-metrics-composition-01 August 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
Zahariadis, et al. Expires March 3, 2012 [Page 4]
Internet Draftdraft-zahariadis-roll-metrics-composition-01 August 2011
defined as a metric operator.
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], and [RFC5867] motivate the design of different composite
routing metrics to cope with different routing application
requirements.
However, the selection of basic and derived metrics to design an
efficient composite metric is neither an arbitrary nor a trivial
task. Combining routing metrics of different types may lead to
routing loops or selection of non-optimal paths.
This document presents the guidelines for designing QoS routing
strategies set by different applications, by identifying the
properties that a composite metric must hold in order to work
seamlessly with RPL routing protocol.
2 Basic and Derived Metrics Properties and Rules
Routing metrics are the representation of an LLN in routing process.
Thus, they might result in major implications on the complexity of
optimal path computation, the existence of optimal path and the range
of application requirements that can be supported.
Path computation algorithms using one basic metric have been widely
used in the literature and practice [I-D.ietf-roll-of0], [I-D.ietf-
roll-minrank-hysteresis-of]. However, in order to support a wide
range of QoS requirements dictated by different application domains,
several routing metric forming a composite metric must be taken into
account.
RPL is a distance vector based, hop-by-hop routing protocol that
builds Directed Acyclic Graphs (DAG) based on routing metrics and
constraints. Following the routing algebra formalism presented in
[Sobrinho] and [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 March 3, 2012 [Page 5]
Internet Draftdraft-zahariadis-roll-metrics-composition-01 August 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 [I-D.ietf-roll-routing-metrics], a metric can either be
recorded or aggregated along the path. In the former case, the metric
can be of maximum type (A=0x01) or minimum type (A=0x02), while in
the latter case, a metric can be of additive type (A=0x00) or
multiplicative type (A=0x03).
Let 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 RSSI is a
multiplicative metric. Moreover, representative examples of concave
metrics are Throughput and Bandwidth.
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.
Zahariadis, et al. Expires March 3, 2012 [Page 6]
Internet Draftdraft-zahariadis-roll-metrics-composition-01 August 2011
In Figure 1, the properties and rules for some well-known basic
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 | addition | < |
| Throughput | 32-bit integer | concave (min.) | > |
| RSSI | [0,255] | multiplicative | > |
| 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 [I-D.ietf-roll-
routing-metrics]. 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 multiplicative
(metric operator) with '>' as a metric order relation. The same
remark applies to Link Color metric.
3 Applicability to RPL
According to [I-D.ietf-roll-rpl], Objective Function (OF) defines how
routing metrics, optimization objectives and related functions are
used to compute Rank. Furthermore, OF dictates how parents in the
DODAG are selected and thus the DODAG formation is defined by OF.
On the other hand, Rank defines the node's individual position
relative to other nodes with respect to a DODAG root. Rank strictly
increases in the Down direction (towards leaf nodes) and strictly
decreases in the Up direction (towards root node). The exact way Rank
is computed, depends on the DAG's OF, as mentioned earlier.
Furthermore, according to [I-D.ietf-roll-rpl], minHopRankIncrease
value is defined as the minimum increase in Rank between a node and
any of its DODAG parents, while maxRankIncrease is defined as the
maximum value increase that a given node can advertise within the
same DODAG version.
There are two distinct approaches to follow, regarding the usability
of multiple basic or derived routing metrics into one composite
metric in RPL routing protocol, namely the lexical metric composition
and the additive metric composition.
Zahariadis, et al. Expires March 3, 2012 [Page 7]
Internet Draftdraft-zahariadis-roll-metrics-composition-01 August 2011
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 [I-D.ietf-roll-rpl] and [I-
D.ietf.roll-routing-metrics] that indicates the precedence of each
routing metric (or constraint) present in the Objective Function.
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 [I-D.ietf-roll-routing-metrics], in this case the
relevant flags of the DAG Metric Container Object must be: C = 0, O =
0, A = 0x00, and R = 0.
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.
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.
Zahariadis, et al. Expires March 3, 2012 [Page 8]
Internet Draftdraft-zahariadis-roll-metrics-composition-01 August 2011
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) <0 , 1.0> |
| / \ |
| / \ |
| / \ |
| 1.3 / \ 1.2 |
| / \ |
| / \ |
| / \ |
| <1 , 1.3> (B) (C) <1 , 1.2> |
| |\_ _/ | |
| | \_ _/ | |
| | 1.5\_ _/1.6 | |
| 1.3 | \/ | 1.3 |
| | _/\_ | |
| | _/ \_ | |
| | _/ \_ | |
| (D) (E) |
| w(A,B,D) = <2 , 3.6> w(A,C,E) = <2 , 3.5> |
| w(A,C,D) = <2 , 3.8> w(A,B,E) = <2 , 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.
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.
Zahariadis, et al. Expires March 3, 2012 [Page 9]
Internet Draftdraft-zahariadis-roll-metrics-composition-01 August 2011
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) <0 , 1.0> |
| / \ |
| / \ |
| / \ |
| 1.2 / \ 1.2 |
| / \ |
| / \ |
| / \ |
| <1 , 1.2> (B) (C) <1 , 1.2> |
| \ | |
| \ | 1.1 |
| \ | |
| 2.8 \ (E) <2 , 2.3> |
| \ / |
| \ _/ 1.1 |
| \ / |
| (D) |
| w(A,B,D) = <2 , 5.0> |
| w(A,C,E,D) = <3 , 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
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.
Zahariadis, et al. Expires March 3, 2012 [Page 10]
Internet Draftdraft-zahariadis-roll-metrics-composition-01 August 2011
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 LQL 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 [I-D.ietf-roll-routing-metrics],
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 March 3, 2012 [Page 11]
Internet Draftdraft-zahariadis-roll-metrics-composition-01 August 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 March 3, 2012 [Page 12]
Internet Draftdraft-zahariadis-roll-metrics-composition-01 August 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.
+-------------------------------------------------------------------+
| (1.0)(A) <0 , 1.0> |
| / \ |
| / \ |
| / \ |
| / \ |
| / \ |
| / \ |
| / \ |
| <1 , 0.8> (B)(0.8) (0.79)(C) <1 , 0.79> |
| \ / |
| \ / |
| \ / |
| \ / |
| \ / |
| \ / |
| \ / |
| (D)(0.7) |
+-------------------------------------------------------------------+
Figure 5: Implication of dynamic metric inclusion in a composite
Zahariadis, et al. Expires March 3, 2012 [Page 13]
Internet Draftdraft-zahariadis-roll-metrics-composition-01 August 2011
lexical approach.
Example 4: Consider the simple LLN topology depicted in Figure 5,
where the OF consists of HP and 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 <1, 0.78>, while the next DIO
transmission of node C will be <1,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].
Example 5: As a second example, consider the LLN depicted in Figure
6. The applied composite metric uses ETX and RE.
+-------------------------------------------------------------------+
| (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.
Zahariadis, et al. Expires March 3, 2012 [Page 14]
Internet Draftdraft-zahariadis-roll-metrics-composition-01 August 2011
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.
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 monotonicity 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
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.
Zahariadis, et al. Expires March 3, 2012 [Page 15]
Internet Draftdraft-zahariadis-roll-metrics-composition-01 August 2011
The source node selects as its parent the node advertising path with
minimum 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. The source 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 + 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.
+-------------------------------------------------------------------+
| (A) <1 , 10> |
| / \ |
| / \ |
| / \ |
| / \ |
| / \ |
| / \ |
| / \ |
| <3 , 2> (B) (C) <2 , 9> |
| \ / |
| \ / |
| \ / |
| \ / |
| \ / |
| \ / |
| \ / |
| <2 , 8> (D) w(A,B,D) = <6 , 2> = 8 |
| | w(A,C,D) = <5 , 8> = 13 |
| | |
| | |
| <6 , 2> (E) w(A,B,D,E) = <12 , 2> = 14 |
| w(A,C,D,E) = <11 , 2> = 13 |
+-------------------------------------------------------------------+
Figure 7: Non-isotonic routing metric leads to non-optimal paths
selection.
Calculating path values, it is straightforward that node D will
Zahariadis, et al. Expires March 3, 2012 [Page 16]
Internet Draftdraft-zahariadis-roll-metrics-composition-01 August 2011
select node B as its parent node, since w(A,B,D)<w(A,C,D). Adding
link D-E, then w(A,B,D,E)>w(A,C,D,E). Thus isotonicity does not hold
for the composite metric (L + T) as defined in this example. The
implication of this can be seen from the following example: The
optimal path for the pair of source-destination A-D is A-B-D, while
the optimal path for the pair of A-E is A-C-D-E, according to
composite metric under examination. Thus, optimality of traversed
paths is not guaranteed.
4.10 Metrics MUST be normalized.
In case that an additive composite metric is used in conjunction with
weighting factors for providing better QoS characteristics according
to different applications, normalization of basic or derived metrics
MUST take place. Considering a composite metric consisting of ETX and
RE, the normalization process yields that a composition function can
be defined as: a1*(1-(1/ETX))+a2*(1-RE). In this case, both metrics
are defined in [0,1], are additive and 'minimizable'.Furthermore, if
RSSI participates in the composite metric, then RSSI must become an
additive metric by applying the logarithmic properties and then used
in the form of the following derived metric: a3*(1/log(RSSI)).
5 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.
6 Security Considerations
No new considerations are raised this document.
7 IANA Considerations
This document includes no request to IANA.
8 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
Zahariadis, et al. Expires March 3, 2012 [Page 17]
Internet Draftdraft-zahariadis-roll-metrics-composition-01 August 2011
Commission has no responsibility for the content of this document.
9 References
9.1 Normative References
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119, March 1997.
[I-D.ietf-roll-routing-metrics] Vasseur, J., Kim, M., Pister, K.,
Dejean, N., and D. Barthel, "Routing Metrics used for Path
Calculation in Low Power and Lossy Networks", draft-ietf-
roll-routing-metrics-19, March 2011.
[I-D.ietf-roll-rpl] Winter, T., Thubert, P., Brandt, A., Clausen,
T., Hui, J., Kelsey, R., Levis, P., Pister, K., Struik,
R., and JP. Vasseur, "RPL: IPv6 Routing Protocol for Low
Power and Lossy Networks", draft-ietf-roll-rpl-19, March
2011.
[I-D.ietf-roll-of0] Thubert, P., "RPL Objective Function 0", draft-
ietf-roll-of0-07, March 2011.
[I-D.ietf-roll-minrank-hysteresis-of] Gnawali, O., and P. Levis,
"The Minimum Rank Objective Function with Hysteresis",
draft-ietf-roll-minrank-hysteresis-of-02, September 2010.
9.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
Zahariadis, et al. Expires March 3, 2012 [Page 18]
Internet Draftdraft-zahariadis-roll-metrics-composition-01 August 2011
5826, April 2010.
[RFC5835] Morton, A., and S. Van der Berghe, "Framework for Metric
Composition", RFC5835, April 2010.
[RFC5867] Martocci, J., De Mil, P., Riou, N., and W. Vermeylen,
"Building Automation Routing Requirements in Low-Power and
Lossy Networks", RFC 5867, June 2010.
[RFC6049] Morton, A., and E. Stephan, "Spatial Composition of
Metrics", RFC 6049, January 2011.
[Sobrinho] J. Sobrinho, "Network Routing with Path Vector Protocols:
Theory and Applications", ACM SIGCOMM, 2003, pp. 49-60.
[Yang] Yang, Y., and J. Wang, "Design Guidelines for Routing
Metrics in Multihop Wireless Networks", IEEE INFOCOM 2008,
pp. 1615-1623.
Authors' Addresses
Theodore Zahariadis (editor)
Technological Educational Institute of Halkida (TEIHAL)
Psachna, Evia, 34400, Greece.
EMail: zahariad@teihal.gr
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 March 3, 2012 [Page 19]
