draft-ietf-roll-routing-metrics-10.txt   draft-ietf-roll-routing-metrics-11.txt 
Networking Working Group JP. Vasseur, Ed. Networking Working Group JP. Vasseur, Ed.
Internet-Draft Cisco Systems, Inc Internet-Draft Cisco Systems, Inc
Intended status: Standards Track M. Kim, Ed. Intended status: Standards Track M. Kim, Ed.
Expires: April 22, 2011 Corporate Technology Group, KT Expires: April 26, 2011 Corporate Technology Group, KT
K. Pister K. Pister
Dust Networks Dust Networks
N. Dejean N. Dejean
Coronis SAS Coronis SAS
D. Barthel D. Barthel
France Telecom Orange France Telecom Orange
October 19, 2010 October 23, 2010
Routing Metrics used for Path Calculation in Low Power and Lossy Routing Metrics used for Path Calculation in Low Power and Lossy
Networks Networks
draft-ietf-roll-routing-metrics-10 draft-ietf-roll-routing-metrics-11
Abstract Abstract
Low power and Lossy Networks (LLNs) have unique characteristics Low power and Lossy Networks (LLNs) have unique characteristics
compared with traditional wired and ad-hoc networks that require the compared with traditional wired and ad-hoc networks that require the
specification of new routing metrics and constraints. By contrast specification of new routing metrics and constraints. By contrast
with typical Interior Gateway Protocol (IGP) routing metrics using with typical Interior Gateway Protocol (IGP) routing metrics using
hop counts or link metrics, this document specifies a set of link and hop counts or link metrics, this document specifies a set of link and
node routing metrics and constraints suitable to LLNs to be used by node routing metrics and constraints suitable to LLNs to be used by
the Routing for Low Power and lossy networks (RPL) routing protocol. the Routing for Low Power and lossy networks (RPL) routing protocol.
skipping to change at page 2, line 4 skipping to change at page 2, line 4
Internet-Drafts are working documents of the Internet Engineering Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF). Note that other groups may also distribute Task Force (IETF). Note that other groups may also distribute
working documents as Internet-Drafts. The list of current Internet- working documents as Internet-Drafts. The list of current Internet-
Drafts is at http://datatracker.ietf.org/drafts/current/. Drafts is at http://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six months Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress." material or to cite them other than as "work in progress."
This Internet-Draft will expire on April 22, 2011. This Internet-Draft will expire on April 26, 2011.
Copyright Notice Copyright Notice
Copyright (c) 2010 IETF Trust and the persons identified as the Copyright (c) 2010 IETF Trust and the persons identified as the
document authors. All rights reserved. document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents Provisions Relating to IETF Documents
(http://trustee.ietf.org/license-info) in effect on the date of (http://trustee.ietf.org/license-info) in effect on the date of
publication of this document. Please review these documents publication of this document. Please review these documents
skipping to change at page 3, line 14 skipping to change at page 3, line 14
Table of Contents Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 4 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 4
2. Object formats . . . . . . . . . . . . . . . . . . . . . . . . 7 2. Object formats . . . . . . . . . . . . . . . . . . . . . . . . 7
2.1. DAG Metric Container format . . . . . . . . . . . . . . . 7 2.1. DAG Metric Container format . . . . . . . . . . . . . . . 7
2.2. Use of multiple DAG Metric Containers . . . . . . . . . . 10 2.2. Use of multiple DAG Metric Containers . . . . . . . . . . 10
2.3. Metric usage . . . . . . . . . . . . . . . . . . . . . . . 10 2.3. Metric usage . . . . . . . . . . . . . . . . . . . . . . . 10
3. Node Metric/Constraint objects . . . . . . . . . . . . . . . . 11 3. Node Metric/Constraint objects . . . . . . . . . . . . . . . . 11
3.1. Node State and Attributes object . . . . . . . . . . . . . 11 3.1. Node State and Attributes object . . . . . . . . . . . . . 11
3.2. Node Energy object . . . . . . . . . . . . . . . . . . . . 13 3.2. Node Energy object . . . . . . . . . . . . . . . . . . . . 12
3.3. Hop-Count object . . . . . . . . . . . . . . . . . . . . . 16 3.3. Hop-Count object . . . . . . . . . . . . . . . . . . . . . 16
4. Link Metric/Constraint objects . . . . . . . . . . . . . . . . 17 4. Link Metric/Constraint objects . . . . . . . . . . . . . . . . 16
4.1. Throughput . . . . . . . . . . . . . . . . . . . . . . . . 17 4.1. Throughput . . . . . . . . . . . . . . . . . . . . . . . . 17
4.2. Latency . . . . . . . . . . . . . . . . . . . . . . . . . 18 4.2. Latency . . . . . . . . . . . . . . . . . . . . . . . . . 18
4.3. Link reliability . . . . . . . . . . . . . . . . . . . . . 19 4.3. Link reliability . . . . . . . . . . . . . . . . . . . . . 19
4.3.1. The Link Quality Level reliability metric . . . . . . 20 4.3.1. The Link Quality Level reliability metric . . . . . . 20
4.3.2. The Expected Transmission Count (ETX) reliability 4.3.2. The Expected Transmission Count (ETX) reliability
object . . . . . . . . . . . . . . . . . . . . . . . . 22 object . . . . . . . . . . . . . . . . . . . . . . . . 21
4.4. Link Color object . . . . . . . . . . . . . . . . . . . . 23 4.4. Link Color object . . . . . . . . . . . . . . . . . . . . 23
4.4.1. Link Color object description . . . . . . . . . . . . 23 4.4.1. Link Color object description . . . . . . . . . . . . 23
4.4.2. Mode of operation . . . . . . . . . . . . . . . . . . 25 4.4.2. Mode of operation . . . . . . . . . . . . . . . . . . 24
5. Computation of dynamic metrics and attributes . . . . . . . . 25 5. Computation of dynamic metrics and attributes . . . . . . . . 25
6. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 26 6. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 25
6.1. Routing Metric/Constraint type . . . . . . . . . . . . . . 26 6.1. Routing Metric/Constraint type . . . . . . . . . . . . . . 25
6.2. Routing Metric/Constraint common header . . . . . . . . . 26 6.2. Routing Metric/Constraint common header . . . . . . . . . 26
6.3. NSA object . . . . . . . . . . . . . . . . . . . . . . . . 27 6.3. NSA object . . . . . . . . . . . . . . . . . . . . . . . . 27
6.4. Hop-Count object . . . . . . . . . . . . . . . . . . . . . 28 6.4. Hop-Count object . . . . . . . . . . . . . . . . . . . . . 27
7. Security considerations . . . . . . . . . . . . . . . . . . . 28 7. Security considerations . . . . . . . . . . . . . . . . . . . 28
8. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 28 8. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 28
9. References . . . . . . . . . . . . . . . . . . . . . . . . . . 29 9. References . . . . . . . . . . . . . . . . . . . . . . . . . . 28
9.1. Normative references . . . . . . . . . . . . . . . . . . . 29 9.1. Normative references . . . . . . . . . . . . . . . . . . . 28
9.2. Informative references . . . . . . . . . . . . . . . . . . 29 9.2. Informative references . . . . . . . . . . . . . . . . . . 28
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 30 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 29
1. Introduction 1. Introduction
This document makes use of the terminology defined in This document makes use of the terminology defined in
[I-D.ietf-roll-terminology]. [I-D.ietf-roll-terminology].
Low power and Lossy Networks (LLNs) have specific routing Low power and Lossy Networks (LLNs) have specific routing
characteristics compared with traditional wired or ad-hoc networks characteristics compared with traditional wired or ad-hoc networks
that have been spelled out in [RFC5548], [RFC5673], [RFC5826] and that have been spelled out in [RFC5548], [RFC5673], [RFC5826] and
[RFC5867]. [RFC5867].
skipping to change at page 4, line 37 skipping to change at page 4, line 37
One of the prime objectives of this document is to propose a flexible One of the prime objectives of this document is to propose a flexible
mechanism for the advertisement of routing metrics and constraints mechanism for the advertisement of routing metrics and constraints
used by RPL. Some RPL implementations may elect to adopt an used by RPL. Some RPL implementations may elect to adopt an
extremely simple approach based on the use of a single metric with no extremely simple approach based on the use of a single metric with no
constraint whereas other implementations may use a larger set of link constraint whereas other implementations may use a larger set of link
and node routing metrics and constraints. This specification and node routing metrics and constraints. This specification
provides a high degree of flexibility and a set of routing metrics provides a high degree of flexibility and a set of routing metrics
and constraints. New routing metrics and constraints could be and constraints. New routing metrics and constraints could be
defined in the future, as needed. defined in the future, as needed.
RPL is a distance vector routing protocol that builds Directed RPL is a distance vector routing protocol variant that builds
Acyclic Graphs (DAGs) based on routing metrics and constraints. DAG Directed Acyclic Graphs (DAGs) based on routing metrics and
formation rules are defined in [I-D.ietf-roll-rpl]: constraints. DAG formation rules are defined in [I-D.ietf-roll-rpl]:
o The DAG root may advertise a routing constraint used as a "filter" o The DODAG root as defined in [I-D.ietf-roll-rpl] may advertise a
to prune links and nodes that do not satisfy specific properties. routing constraint used as a "filter" to prune links and nodes
For example, it may be required for the path to only traverse that do not satisfy specific properties. For example, it may be
nodes that are mains powered or links that have at least a minimum required for the path to only traverse nodes that are mains
reliability or a specific "color" reflecting a user defined link powered or links that have at least a minimum reliability or a
characteristic (e.g the link layer supports encryption). specific "color" reflecting a user defined link characteristic
(e.g the link layer supports encryption).
o A routing metric is a quantitative value that is used to evaluate o A routing metric is a quantitative value that is used to evaluate
the path cost. Link and node metrics are usually (but not always) the path cost. Link and node metrics are usually (but not always)
additive. additive.
The best path is the path with the lowest cost with respect to some The best path is the path with the lowest cost with respect to some
metrics that satisfies all constraints (if any). It is also called metrics that satisfies all constraints (if any). It is also called
the shortest constrained path (in the presence of constraints). the shortest constrained path (in the presence of constraints).
Routing metrics can be classified according to the following set of Routing metrics falls into the following sets of characteristics:
characteristics:
o Link versus Node metrics o Link versus Node metrics
o Qualitative versus quantitative o Qualitative versus quantitative
o Dynamic versus static o Dynamic versus static
As pointed out in various routing requirements documents (see Routing requirements documents (see [RFC5673], [RFC5826] [RFC5548]
[RFC5673], [RFC5826] [RFC5548] and [RFC5867]), it must be possible to and [RFC5867]) observe that it must be possible to take into account
take into account a variety of node constraints/metrics during path a variety of node constraints/metrics during path computation.
computation.
Some link or node characteristics (e.g. link reliability flag, Some link or node characteristics (e.g. link reliability flag,
remaining energy on the node) may either be used by RPL as routing remaining energy on the node) may either be used by RPL either as
constraints or metrics. For example, the path may be computed to routing constraints or metrics. For example, the path may be
avoid links that do not provide a sufficient level of reliability computed to avoid links that do not provide a sufficient level of
(use as a constraint) or as the path offering most links with a reliability (use as a constraint) or as the path offering most links
specified reliability level (use as a metric). The document provides with a specified reliability level (use as a metric). This document
the flexibility to use link and node characterisics either as provides the flexibility to use link and node characterisics either
constraints and/or metrics. as constraints and/or metrics.
The use of link and node routing metrics and constraints is not The use of link and node routing metrics and constraints is not
exclusive. exclusive (e.g. it is for example possible to advertise a "hop count"
both as a metric to optimize the computed path and as a constraint
(e.g. "Path should not exceed n hops")).
It is also worth mentioning that it is fairly common for links in Links in LLN commonly have rapidly changing node and link
LLNs to have fast changing node and link characteristics, which must characteristics: thus routing metrics must be dynamic and techniques
be taken into account when specifying routing metrics. For instance, must be used to smooth out the dynimicity of these metrics so as to
in addition to the dynamic nature of some links (e.g. wireless but avoid routing oscillations. For instance, in addition to the dynamic
also Powerline Communication (PLC) links), nodes' resources such as nature of some links (e.g. wireless but also Powerline Communication
residual energy and other link's characteristics such as the (PLC) links), nodes' resources such as residual energy are changing
throughput are changing continuously and may have to be taken into continuously and may have to be taken into account during the path
account during the path computation. Similarly, link attributes computation.
including throughput and reliability may drastically change over time
due to multi-path interference.
It must be noted that the use of dynamic metrics is not new and has It must be noted that the use of dynamic metrics is not new and has
been experimented in ARPANET 2 [Khanna1989], with moderate success. been experimented in ARPANET 2. The use of dynamic metrics is not
The use of dynamic metrics is not trivial and great care must be trivial and great care must be given to the use of dynamic metrics
given to the use of dynamic metrics since it may lead to potential since it may lead to potential routing instabilities. That being
routing instabilities. it must be noted that the use of dynamic said, lots of experience has been gained over the years on the use of
metrics has been largely experimented and deployed in a number of dynamic routing metrics, which have been deployed in a number of (non
(non IP) networks in the past decade. IP) networks.
Very careful attention must be given when using dynamic metrics and
attributes that affect routing decisions in order to preserve routing
stability. Routing metrics and constraints may either be static or
dynamic. When dynamic, a RPL implementation SHOULD make use of a
multi-threshold scheme rather than fine granular metric updates so as
to avoid constant routing changes.
Furthermore, it is a time and energy consuming process to update Very careful attention must be given to the pace at which routing
dynamic metrics and recompute the routing tables on a frequent basis. metrics and attributes values change in order to preserve routing
Therefore, it may be desirable to use a set of discrete values to stability. When using a dynamic routing metric, a RPL implementation
reduce computational overhead and bandwidth utilization. Of course, SHOULD make use of a multi-threshold scheme rather than fine granular
this comes with a cost, namely, reduced metric accuracy. In other metric updates reflecting each individual change to avoid spurious
cases, a set of flags may be defined to reflect a node state without and unneccessary routing changes.
having to define discrete values.
The requirements on reporting frequency may differ among metrics, The requirements on reporting frequency may differ among metrics,
thus different reporting rates may be used for each category and are thus different reporting rates may be used for each metric.
consequently implementation-specific.
The set of routing metrics and constraints used by an RPL The set of routing metrics and constraints used by an RPL deployment
implementation is signaled along the Directed Acyclic Graph (DAG) is signaled along the Directed Acyclic Graph (DAG) that is built
that is built according to the Objective Function (rules governing according to the Objective Function (rules governing how to build a
how to build a DAG) and the routing metrics and constraints are DAG) and the routing metrics and constraints are advertised in the
advertised in the DAG Information Option (DIO) message specified in DAG Information Option (DIO) message specified in
[I-D.ietf-roll-rpl]. RPL may be used to build DAGs with different [I-D.ietf-roll-rpl]. RPL may be used to build DAGs with different
characteristics. For example, it may be desirable to build a DAG characteristics. For example, it may be desirable to build a DAG
with the goal to maximize reliability by using the link reliability with the goal to maximize reliability by using the link reliability
metric to compute the "best" path. Another example might be to use metric to compute the "best" path. Another example might be to use
the energy node characteristic (e.g. mains powered versus battery the energy node characteristic (e.g. mains powered versus battery
operated) as a node constraint when building the DAG so as to avoid operated) as a node constraint when building the DAG so as to avoid
battery powered nodes in the DAG while optimizing the link battery powered nodes in the DAG while optimizing the link
throughput. throughput.
The specification of objective functions used to compute the DAG The specification of objective functions used to compute the DAG
built by RPL is out of the scope of this document. Routing metrics built by RPL is out of the scope of this document. This document
and constraints are decoupled from the objective function. So a defines routing metrics and constraints that are decoupled from the
generic objective function could for example specify the rules to objective function. So a generic objective function could for
select the best parents in the DAG, the number of backup parents, example specify the rules to select the best parents in the DAG, the
etc. Such objective function can be used with any routing metrics number of backup parents, etc and could be used with any routing
and/or constraints such as the ones specified in this document. metrics and/or constraints such as the ones specified in this
document.
Some metrics are either aggregated or recorded. In the former case, Some metrics are either aggregated or recorded. An aggregated metric
the metric is adjusted as the DIO message travels along the DAG. For is adjusted as the DIO message travels along the DAG. For example,
example, if the metric is the link latency, each node updates the if the metric is the number of hops, each node updates the path cost
latency metric along the DAG. By contrast, a metric may be recorded that reflects the number of traversed hops along the DAG. By
in which case each node adds a sub-object reflecting the local contrast, for a recorded metric, each node adds a sub-object
metric. For example, it might be desirable to record the link reflecting the local valuation of the metric. For example, it might
quality level along the path. In this case, each visited node adds a be desirable to record the link quality level along a path. In this
sub-object reporting the local link quality level. In order to limit case, each visited node adds a sub-object recording the local link
the number of sub-objects, the use of a counter may be desirable quality level. In order to limit the number of sub-objects, the use
(e.g. record the number of links with a certain link quality level), of a counter may be desirable (e.g. record the number of links with a
thus compressing the information to reduce the message length. Upon certain link quality level), thus compressing the information to
receiving the DIO message from a set of parents, a node can decide reduce the message length. Upon receiving the DIO message from a set
according to the OF and local policy which node to choose as a parent of parents, a node might decide according to the OF and local policy
based on the maximum number of links with a specific link reliability which node to choose as a parent based on the maximum number of links
level, for example. with a specific link reliability level, for example.
Note that the routing metrics and constraints specified in this Note that the routing metrics and constraints specified in this
document are not specific to any link layer. An internal API between document are not specific to any particular link layer. An internal
the MAC layer and RPL may be used to accurately reflect the metrics API between the MAC layer and RPL may be used to accurately reflect
values of the link (wireless, wired, PLC). the metrics values of the link (wireless, wired, PLC).
Since a set of metrics and constraints will be used for links and Since a set of metrics and constraints will be used for links and
nodes in LLN, it is particularly critical to ensure the use of nodes in LLN, it is particularly critical to ensure the use of
consistent metric calculation mechanisms for all links and nodes in consistent metric calculation mechanisms for all links and nodes in
the network, similarly to the case of inter-domain IP routing. the network, similarly to the case of inter-domain IP routing.
2. Object formats 2. Object formats
2.1. DAG Metric Container format 2.1. DAG Metric Container format
Routing metrics and constraints are carried within the DAG Metric Routing metrics and constraints are carried within the DAG Metric
Container object defined in [I-D.ietf-roll-rpl]. Should multiple Container object defined in [I-D.ietf-roll-rpl]. Should multiple
metrics and/or constraints be present in the DAG Metric Container, metrics and/or constraints be present in the DAG Metric Container,
their use to determine the "best" path can be defined by an Objective their use to determine the "best" path can be defined by an Objective
Function or a new TLV to be defined in future documents. Function.
0 1 2 3 4 0 1 2 3 4
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-...
| Type=2 | Option Len | Routing Metric/Constraint objects | Type=2 | Option Len |Routing Metric/Constraint objects
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-...
Figure 1: DAG Metric Container format Figure 1: DAG Metric Container format
The Routing Metric/Constraint objects have a common format consisting The Routing Metric/Constraint objects represent a metric or a
of one or more 8-bit words with a common header: constraint of a particular type. They may appear in any order in the
DAG Metric Container. They have a common format consisting of one or
more bytes with a common header:
0 1 2 3 0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|Routing-MC-Type| Flags |P|C|O|R| A | Prec | Length (bytes)| |Routing-MC-Type| Flags |P|C|O|R| A | Prec | Length (bytes)|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | | |
// (object body) // // (object body) //
| | | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Figure 2: Routing Metric/Constraint object generic format Figure 2: Routing Metric/Constraint object generic format
The object body carries one or more sub-objects. The object body carries one or more sub-objects defined later in this
document.
Note that the Routing Metric/Constraint objects defined in this
document can appear in any order in the DAG Metric Container.
Routing-MC-Type (Routing Metric/Constraint Type - 8 bits): the Routing-MC-Type (Routing Metric/Constraint Type - 8 bits): the
Routing Metric/Constraint Type field uniquely identifies each Routing Routing Metric/Constraint Type field uniquely identifies each Routing
Metric/Constraint object and is managed by IANA. Metric/Constraint object and is managed by IANA.
Length: this field defines the length of the object body, in bytes. Length: this field defines the length of the object body, in bytes.
The Flag field of the Routing Metric/Constraint object is managed by The Flag field of the Routing Metric/Constraint object is managed by
IANA. Unassigned bits are considered as reserved. They MUST be set IANA. Unassigned bits are considered as reserved. They MUST be set
to zero on transmission and MUST be ignored on receipt. to zero on transmission and MUST be ignored on receipt.
o C Flag. When set, this indicates that the Routing Metric/ o C Flag. When set, this indicates that the Routing Metric/
Constraint object refers to a routing constraint. When cleared, Constraint object refers to a routing constraint. When cleared,
the routing object refers to a routing metric. the routing object refers to a routing metric.
o O Flag: The O flag is used exclusively for routing constraints (C o O Flag: The O flag is used exclusively for routing constraints (C
flag is set). When set, this indicates that the constraint is flag is set). When set, this indicates that the constraint
optional. When cleared, the constraint is mandatory. If the C specified in the body of the object is optional. When cleared,
flag is zero, the O flag MUST be set to zero on transmission and the constraint is mandatory. If the C flag is zero, the O flag
ignored on reception. MUST be set to zero on transmission and ignored on reception.
o R Flag: The R Flag is only relevant for routing metric (C=0) and o R Flag: The R Flag is only relevant for routing metric (C=0) and
MUST be cleared for C=1. When set, this indicates that the MUST be cleared for C=1. When set, this indicates that the
routing metric is recorded along the path. Conversely, when routing metric is recorded along the path. Conversely, when
cleared, the routing metric is aggregated. cleared, the routing metric is aggregated.
o A Field: The A field is used to indicate whether an aggregated o A Field: The A field is only relevant for metrics and is used to
routing metric is additive, multiplicative, reports a maximum or a indicate whether the aggregated routing metric is additive,
minimum. multiplicative, reports a maximum or a minimum.
* A=0x00: The routing metric is additive * A=0x00: The routing metric is additive
* A=0x01: The routing metric reports a maximum
* A=0x01: The routing metric reports a maximum
* A=0x02: The routing metric reports a minimum * A=0x02: The routing metric reports a minimum
* A=0x03: The routing metric is multiplicative * A=0x03: The routing metric is multiplicative
The A field has no meaning when the C Flag is set (i.e. when the The A field has no meaning when the C Flag is set (i.e. when the
Routing Metric/Constraint object refers to a routing constraint) Routing Metric/Constraint object refers to a routing constraint)
and MUST be written to 0x00. and MUST be written to 0x00.
o Prec field: The Prec field indicates the precedence of this o Prec field: The Prec field indicates the precedence of this
Routing Metric/Constraint object. This is useful when a DAG Routing Metric/Constraint object relative to other objects in the
Metric Container contains several Routing Metric objects. The container. This is useful when a DAG Metric Container contains
value 0 means the highest precedence. several Routing Metric objects. The value 0 means the highest
precedence.
o P field: the P field is only used for recorded metrics. When o P field: the P field is only used for recorded metrics. When
cleared, all nodes along the path successfully recorded the cleared, all nodes along the path successfully recorded the
corresponding metric. When set, this indicates than one or corresponding metric. When set, this indicates than one or
several nodes along the path could not record the metric of several nodes along the path could not record the metric of
interest (either because of lack of knowledge or because this was interest (either because of lack of knowledge or because this was
prevented by policy). prevented by policy).
Example 1: A DAG formed by RPL where all nodes must be mains-powered Example 1: A DAG formed by RPL where all nodes must be mains-powered
and the best path is the one with lower aggregated ETX. In this case and the best path is the one with lower aggregated ETX. In this case
the DAG Metric container carries two Routing Metric/Constraint the DAG Metric container carries two Routing Metric/Constraint
objects: one is an ETX metric object with header (C=0, O=0, A=00, objects: one is an ETX metric object with header (C=0, O=0, A=00,
R=0) and the second one is a Node Energy constraint object with R=0) and the second one is a Node Energy constraint object with
header (C=1, O=0, A=00, R=0). Note that a RPL instance may use the header (C=1, O=0, A=00, R=0). Note that a RPL instance may use the
metric object to report a maximum (A=0x01) or a minimum (A=0x02). metric object to report a maximum (A=0x01) or a minimum (A=0x02).
If, for example, the best path is characterized by the path avoiding If, for example, the best path is characterized by the path avoiding
low quality links, then the path metric reports a maximum (A=0x01) low quality links, then the path metric reports a maximum (A=0x01)
(note that higher values mean lower link quality): when the link (the higher is the ETX the lower link quality is): when the DIO
quality metric (ETX) is processed along a path, each node updates the message reporting link quality metric (ETX) is processed by a node,
each node selected the advertising nodes as a parent updates the
value carried in the metric object by replacing it with its local value carried in the metric object by replacing it with its local
link ETX value if and only if the latter is higher. link ETX value if and only if the latter is higher. As far as the
constraint is concerned, if the constraint signalled in the DIO
message is not satisfied, the advertising node is just not selected
as a parent by the node that processes the DIO message.
Example 2: A DAG formed by RPL where the link metric is the link Example 2: A DAG formed by RPL where the link metric is the link
quality level and link quality levels must be recorded along the quality level (defined in Section 4) and link quality levels must be
path. In this case, the DAG Metric Container carries a Routing recorded along the path. In this case, the DAG Metric Container
Metric/Constraint object: link quality level metric (C=0, O=0, A=00, carries a Routing Metric/Constraint object: link quality level metric
R=1) containing multiple sub-objects. (C=0, O=0, A=00, R=1) containing multiple sub-objects.
A Routing Metric/Constraint object may also include one or more A Routing Metric/Constraint object may also include one or more
type-length-value (TLV) encoded data sets. Each Routing Metric/ additional type-length-value (TLV) encoded data sets. Each Routing
Constraint TLV has the same structure: Metric/Constraint TLV has the same structure:
Type: 1 byte Type: 1 byte
Length: 1 byte Length: 1 byte
Value: variable Value: variable
A Routing Metric/Constraint TLV is comprised of 1 byte for the type, A Routing Metric/Constraint TLV is comprised of 1 byte for the type,
1 byte specifying the TLV length, and a value field. The TLV length 1 byte specifying the TLV length, and a value field. The TLV length
field defines the length of the value field in bytes. field defines the length of the value field in bytes.
Unrecognized TLVs MUST be ignored. Unrecognized TLVs MUST be ignored.
IANA management of the Routing Metric/Constraint objects identifier IANA management of the Routing Metric/Constraint objects identifier
codespace is described in Section 6. codespace is described in Section 6.
2.2. Use of multiple DAG Metric Containers 2.2. Use of multiple DAG Metric Containers
Since the length of RPL options is encoded using 1 octet, they cannot Since the length of RPL options is encoded using 1 octet, they cannot
exceed 256 bytes, which also applies to the DAG Metric Container. In exceed 255 bytes, which also applies to the DAG Metric Container. In
the vast majority of cases, the advertised routing metrics and the vast majority of cases, the advertised routing metrics and
constraints will not require that much space. However, there might constraints will not require that much space. However, there might
be circumstances where larger space is required, should for example a be circumstances where larger space is required, should for example a
set of routing metrics be recorded along a long path. In this case, set of routing metrics be recorded along a long path. In this case,
as specified in [I-D.ietf-roll-rpl], routing metrics will be carried as specified in [I-D.ietf-roll-rpl], routing metrics will be carried
using multiple DAG Metric Containers. using multiple DAG Metric Containers objects.
In the rest of this document, this use of multiple DAG Metric In the rest of this document, this use of multiple DAG Metric
Containers will be considered as if they were actually just one long Containers objects will be considered as if they were actually just
DAG Metric Container. one long DAG Metric Container object.
2.3. Metric usage 2.3. Metric usage
This section describes how metrics carried in the DAG Metric
Container shall be used.
When the DAG Metric Container contains a single aggregated metric When the DAG Metric Container contains a single aggregated metric
(scalar value), the order relation to select the best path is (scalar value), the order relation to select the best path is
implicitly derived from the metric type. For example, lower is implicitly derived from the metric type. For example, lower is
better for Hop Count, Link Latency and ETX. Conversely, for Node better for Hop Count, Link Latency and ETX. Conversely, for Node
Energy or Throughput, higher is better. Energy or Throughput, higher is better.
An example of using such a single aggregated metric is optimizing An example of using such a single aggregated metric is optimizing
routing for node energy. The Node Energy metric (E-E field) is routing for node energy. The Node Energy metric (E-E field) defined
aggregated along paths with an explicit min function (A field), and in Section 3.2 is aggregated along paths with an explicit min
the best path is selected through an implied Max function because the function (A field), and the best path is selected through an implied
metric is Energy. Max function because the metric is Energy.
When the DAG Metric Container contains several aggregated metrics, When the DAG Metric Container contains several aggregated metrics,
they are to be used as tie-breakers according to their precedence they are to be used as tie-breakers according to their precedence
defined by their Prec field values. defined by their Prec field values.
An example of such use of multiple aggregated metrics is the An example of such use of multiple aggregated metrics is the
following: Hop-Count as the primary criterion, LQL as the secondary following: Hop-Count as the primary criterion, LQL as the secondary
criterion and Node Energy as the ultimate tie-breaker. In such a criterion and Node Energy as the ultimate tie-breaker. In such a
case, the Hop-Count, LQL and Node Energy metric objects' Prec fields case, the Hop-Count, LQL and Node Energy metric objects' Prec fields
should bear strictly increasing values such as 0, 1 and 2, should bear strictly increasing values such as 0, 1 and 2,
respectively. respectively.
If several aggregated metrics happen to bear the same Prec value, the If several aggregated metrics happen to bear the same Prec value, the
behavior is implementation-dependant. behavior is implementation-dependant.
3. Node Metric/Constraint objects 3. Node Metric/Constraint objects
It is fairly common for LLNs to be made of nodes with heterogeneous
attributes and capabilities (e.g. nodes being battery operated or
not, amount of memory, etc). More capable and stable nodes may
assist the most constrained ones for routing packets, which results
in extension of network lifetime and efficient network operations.
This is a typical (but non-exclusive) use of constraint-based
routing, where the computed path may not be the shortest path
according to some specified metrics. Another use is to find the
shortest path according to a pre-defined metric while avoiding links
with a specific color (for example "non-secured link").
3.1. Node State and Attributes object 3.1. Node State and Attributes object
The Node State and Attribute (NSA) object is used to provide The Node State and Attribute (NSA) object is used to provide
information on the nodes characteristics. information on node's characteristics.
The NSA object MAY be present in the DAG Metric Container. There The NSA object MAY be present in the DAG Metric Container. There
MUST be no more than one NSA object as a constraint per DAG Metric MUST be no more than one NSA object as a constraint per DAG Metric
Container, and no more than one NSA object as a metric per DAG Metric Container, and no more than one NSA object as a metric per DAG Metric
Container. Container.
The NSA object may also contain a set of TLVs used to convey various The NSA object may also contain a set of TLVs used to convey various
node characteristics. No TLV is currently defined. node characteristics. No TLV is currently defined.
The NSA Routing Metric/Constraint Type is to be assigned by IANA The NSA Routing Metric/Constraint Type is to be assigned by IANA
skipping to change at page 12, line 15 skipping to change at page 11, line 40
The format of the NSA object body is as follows: The format of the NSA object body is as follows:
0 1 2 3 0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ...
| Res | Flags |A|O| Optional TLVs | Res | Flags |A|O| Optional TLVs
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ...
Figure 3: NSA object format Figure 3: NSA object format
Node workload may be hard to determine and express in some scalar 'O' flag: node workload may be hard to determine and express in some
form. However, node workload could be a useful metric to consider scalar form. However, node workload could be a useful metric to
during path calculation, in particular when queuing delays must be consider during path calculation, in particular when queuing delays
minimized for highly sensitive traffic considering Medium Access must be minimized for highly sensitive traffic considering Medium
Control (MAC) layer delay. Node workload MAY be set upon CPU Access Control (MAC) layer delay. Node workload MAY be set upon CPU
overload, lack of memory or any other node related conditions. Using overload, lack of memory or any other node related conditions. Using
a simple 1-bit flag to characterize the node workload provides a a simple 1-bit flag to characterize the node workload provides a
sufficient level of granularity, similarly to the "overload" bit used sufficient level of granularity, similarly to the "overload" bit used
in routing protocols such as IS-IS. Algorithms used to set the in routing protocols such as IS-IS. Algorithms used to set the
overload bit and to compute paths to potentially avoid nodes with overload bit and to compute paths to potentially avoid nodes with
their overload bit set are outside the scope of this document, but it their overload bit set are outside the scope of this document, but it
is RECOMMENDED to avoid frequent changes of this bit to avoid routing is RECOMMENDED to avoid frequent changes of this bit to avoid routing
oscillations. oscillations.
Data Aggregation Attribute: data fusion involves more complicated 'A' flag: data Aggregation Attribute: data fusion involves more
processing to improve the accuracy of the output data, while data complicated processing to improve the accuracy of the output data,
aggregation mostly aims at reducing the amount of data. This is while data aggregation mostly aims at reducing the amount of data.
listed as a requirement in Section 6.2 of [RFC5548]. Some This is listed as a requirement in Section 6.2 of [RFC5548]. Some
applications may make use of the aggregation node attribute in their applications may make use of the aggregation node attribute in their
routing decision so as to minimize the amount of traffic on the routing decision so as to minimize the amount of traffic on the
network, thus potentially increasing its lifetime in battery operated network, thus potentially increasing its lifetime in battery operated
environments. Applications where highly directional data flow is environments. Applications where highly directional data flow is
expected on a regular basis may take advantage of data aggregation expected on a regular basis may take advantage of data aggregation
supported routing. supported routing.
The following two bits of the NSA object are currently defined: The following two bits of the NSA object are currently defined:
o A Flag: When set, this indicates that the node can act as a o A Flag: When set, this indicates that the node can act as a
skipping to change at page 28, line 44 skipping to change at page 28, line 21
metrics/constraints are carried within RPL message, the security metrics/constraints are carried within RPL message, the security
routing mechanisms defined in [I-D.ietf-roll-rpl] applies here. routing mechanisms defined in [I-D.ietf-roll-rpl] applies here.
8. Acknowledgements 8. Acknowledgements
The authors would like to acknowledge the contributions of Young Jae The authors would like to acknowledge the contributions of Young Jae
Kim, Hakjin Chong, David Meyer, Mischa Dohler, Anders Brandt, Philip Kim, Hakjin Chong, David Meyer, Mischa Dohler, Anders Brandt, Philip
Levis, Pascal Thubert, Richard Kelsey, Jonathan Hui, Alexandru Levis, Pascal Thubert, Richard Kelsey, Jonathan Hui, Alexandru
Petrescu, Richard Kelsey, Mathilde Durvy, Phoebus Chen, Tim Winter, Petrescu, Richard Kelsey, Mathilde Durvy, Phoebus Chen, Tim Winter,
Mukul Goyal, Yoav Ben-Yehezkel, Matteo Paris, Omprakash Gnawali, Mads Mukul Goyal, Yoav Ben-Yehezkel, Matteo Paris, Omprakash Gnawali, Mads
Westergreen and Mukul Goyal for their review and valuable comments. Westergreen, Mukul Goyal and David Culler for their review and
valuable comments.
9. References 9. References
9.1. Normative references 9.1. Normative references
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119, March 1997. Requirement Levels", BCP 14, RFC 2119, March 1997.
[RFC5226] Narten, T. and H. Alvestrand, "Guidelines for Writing an [RFC5226] Narten, T. and H. Alvestrand, "Guidelines for Writing an
IANA Considerations Section in RFCs", BCP 26, RFC 5226, IANA Considerations Section in RFCs", BCP 26, RFC 5226,
May 2008. May 2008.
9.2. Informative references 9.2. Informative references
skipping to change at page 29, line 19 skipping to change at page 28, line 41
[RFC5226] Narten, T. and H. Alvestrand, "Guidelines for Writing an [RFC5226] Narten, T. and H. Alvestrand, "Guidelines for Writing an
IANA Considerations Section in RFCs", BCP 26, RFC 5226, IANA Considerations Section in RFCs", BCP 26, RFC 5226,
May 2008. May 2008.
9.2. Informative references 9.2. Informative references
[I-D.ietf-roll-rpl] [I-D.ietf-roll-rpl]
Winter, T., Thubert, P., Brandt, A., Clausen, T., Hui, J., Winter, T., Thubert, P., Brandt, A., Clausen, T., Hui, J.,
Kelsey, R., Levis, P., Networks, D., Struik, R., and J. Kelsey, R., Levis, P., Networks, D., Struik, R., and J.
Vasseur, "RPL: IPv6 Routing Protocol for Low power and Vasseur, "RPL: IPv6 Routing Protocol for Low power and
Lossy Networks", draft-ietf-roll-rpl-12 (work in Lossy Networks", draft-ietf-roll-rpl-13 (work in
progress), October 2010. progress), October 2010.
[I-D.ietf-roll-terminology] [I-D.ietf-roll-terminology]
Vasseur, J., "Terminology in Low power And Lossy Vasseur, J., "Terminology in Low power And Lossy
Networks", draft-ietf-roll-terminology-04 (work in Networks", draft-ietf-roll-terminology-04 (work in
progress), September 2010. progress), September 2010.
[RFC1195] Callon, R., "Use of OSI IS-IS for routing in TCP/IP and [RFC1195] Callon, R., "Use of OSI IS-IS for routing in TCP/IP and
dual environments", RFC 1195, December 1990. dual environments", RFC 1195, December 1990.
[RFC2328] Moy, J., "OSPF Version 2", STD 54, RFC 2328, April 1998. [RFC2328] Moy, J., "OSPF Version 2", STD 54, RFC 2328, April 1998.
[RFC2702] Awduche, D., Malcolm, J., Agogbua, J., O'Dell, M., and J. [RFC2702] Awduche, D., Malcolm, J., Agogbua, J., O'Dell, M., and J.
McManus, "Requirements for Traffic Engineering Over MPLS", McManus, "Requirements for Traffic Engineering Over MPLS",
RFC 2702, September 1999. RFC 2702, September 1999.
[RFC3209] Awduche, D., Berger, L., Gan, D., Li, T., Srinivasan, V., [RFC3209] Awduche, D., Berger, L., Gan, D., Li, T., Srinivasan, V.,
and G. Swallow, "RSVP-TE: Extensions to RSVP for LSP and G. Swallow, "RSVP-TE: Extensions to RSVP for LSP
Tunnels", RFC 3209, December 2001. Tunnels", RFC 3209, December 2001.
[RFC3471] Berger, L., "Generalized Multi-Protocol Label Switching
(GMPLS) Signaling Functional Description", RFC 3471,
January 2003.
[RFC5548] Dohler, M., Watteyne, T., Winter, T., and D. Barthel, [RFC5548] Dohler, M., Watteyne, T., Winter, T., and D. Barthel,
"Routing Requirements for Urban Low-Power and Lossy "Routing Requirements for Urban Low-Power and Lossy
Networks", RFC 5548, May 2009. Networks", RFC 5548, May 2009.
[RFC5673] Pister, K., Thubert, P., Dwars, S., and T. Phinney, [RFC5673] Pister, K., Thubert, P., Dwars, S., and T. Phinney,
"Industrial Routing Requirements in Low-Power and Lossy "Industrial Routing Requirements in Low-Power and Lossy
Networks", RFC 5673, October 2009. Networks", RFC 5673, October 2009.
[RFC5826] Brandt, A., Buron, J., and G. Porcu, "Home Automation [RFC5826] Brandt, A., Buron, J., and G. Porcu, "Home Automation
Routing Requirements in Low-Power and Lossy Networks", Routing Requirements in Low-Power and Lossy Networks",
 End of changes. 52 change blocks. 
170 lines changed or deleted 150 lines changed or added

This html diff was produced by rfcdiff 1.40. The latest version is available from http://tools.ietf.org/tools/rfcdiff/