Networking Working Group M. Kim, Ed.
Internet-Draft Future Tech Lab., Korea Telecom
Intended status: Standards Track JP. Vasseur, Ed.
Expires: October 31, 2009 Cisco Systems, Inc
K. Pister
Dust Networks
H. Chong
Future Tech Lab., Korea Telecom
April 29, 2009
Routing Metrics used for Path Calculation in Low Power and Lossy
Networks
draft-ietf-roll-routing-metrics-00
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/ietf/1id-abstracts.txt.
The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html.
This Internet-Draft will expire on October 31, 2009.
Copyright Notice
Copyright (c) 2009 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 in effect on the date of
publication of this document (http://trustee.ietf.org/license-info).
Please review these documents carefully, as they describe your rights
and restrictions with respect to this document.
Kim, et al. Expires October 31, 2009 [Page 1]
Internet-Draft draft-ietf-roll-routing-metrics-00 April 2009
Abstract
This document specifies routing metrics to be used in path
calculation for Routing Over Low power and Lossy networks (ROLL).
Low power and Lossy Networks (LLNs) have unique characteristics
compared with traditional wired networks or even with similar ones
such as mobile ad-hoc networks. By contrast with typical Interior
Gateway Protocol (IGP) routing metrics using hop counts or link
attributes, this document specifies a set of routing metrics suitable
to LLNs.
Requirements Language
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 RFC 2119 [RFC2119].
Kim, et al. Expires October 31, 2009 [Page 2]
Internet-Draft draft-ietf-roll-routing-metrics-00 April 2009
Table of Contents
1. Note . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 4
3. Node Metrics and Attributes . . . . . . . . . . . . . . . . . 6
3.1. Node Memory Resources . . . . . . . . . . . . . . . . . . 6
3.2. Node CPU Resources . . . . . . . . . . . . . . . . . . . . 6
3.3. Node Residual Energy . . . . . . . . . . . . . . . . . . . 6
3.4. Node Overload State . . . . . . . . . . . . . . . . . . . 7
3.5. Data Aggregation Attribute . . . . . . . . . . . . . . . . 8
4. Link Metrics and Attributes . . . . . . . . . . . . . . . . . 8
4.1. Throughput . . . . . . . . . . . . . . . . . . . . . . . . 8
4.2. Latency . . . . . . . . . . . . . . . . . . . . . . . . . 8
4.3. Link reliability . . . . . . . . . . . . . . . . . . . . . 9
4.4. Link Coloring . . . . . . . . . . . . . . . . . . . . . . 9
5. Computation of Dynamic Metrics and Attributes . . . . . . . . 9
6. Open Issues . . . . . . . . . . . . . . . . . . . . . . . . . 10
7. Metric Consistency . . . . . . . . . . . . . . . . . . . . . . 10
8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 10
9. Security Considerations . . . . . . . . . . . . . . . . . . . 10
10. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 10
11. References . . . . . . . . . . . . . . . . . . . . . . . . . . 11
11.1. Normative References . . . . . . . . . . . . . . . . . . . 11
11.2. Informative References . . . . . . . . . . . . . . . . . . 11
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 12
Kim, et al. Expires October 31, 2009 [Page 3]
Internet-Draft draft-ietf-roll-routing-metrics-00 April 2009
1. Note
The first revision of this document has been published with a number
of link and node metrics.
After several discussions on the mailing list and during Working
Group meetings, it was decided to reduce the number of these metrics
to the strict required minimum.
In the revision 02, highly dynamic and application/implementation
dependent attributes have been removed (such as node degree and node
latency) since they may be too CPU intensive for constrained devices
and lead to routing oscillations. Link and node metrics packet
format or methods to encode the data will be defined in a further
revision of this document.
2. Introduction
This document makes use of the terminology defined in
[I-D.ietf-roll-terminology].
This document specifies routing metrics to be used in path
calculation for Routing Over Low power and Lossy networks (ROLL).
Low power and Lossy Networks (LLNs) have specific routing
characteristics compared with traditional wired networks or even with
similar ones such as mobile ad-hoc networks that lead to a set of
specific requirements listed [I-D.ietf-roll-indus-routing-reqs],
[I-D.ietf-roll-home-routing-reqs] [I-D.ietf-roll-urban-routing-reqs]
and [I-D.ietf-roll-building-routing-reqs].
Routing metrics can be classified according to the following set of
characteristics:
o Link versus Node metrics
o Qualitative versus quantitative
o Dynamic or static
Historically, IGP such as OSPF ([RFC2328]) and IS-IS ([RFC1195]) have
used quantitative static link metrics. Other mechanisms such as
Multiprotocol Label Switching (MPLS) Traffic Engineering (TE) (see
[RFC2702] and [RFC3209]) make use of other link attributes such as
the available reserved bandwidth, affinities and so on to compute
constrained shortest paths for Traffic Engineering Label Switched
Paths (TE LSPs).
Kim, et al. Expires October 31, 2009 [Page 4]
Internet-Draft draft-ietf-roll-routing-metrics-00 April 2009
It must be noted that the use of dynamic metrics is not new and has
been experimented in ARPANET 2 [Khanna1989], with moderate success.
Indeed, the use of dynamic metrics is not trivial and very careful
care must be given to the use of dynamic metrics that may lead to
potential routing instabilities.
As pointed out in various routing requirements documents (see
[I-D.ietf-roll-indus-routing-reqs], [I-D.ietf-roll-home-routing-reqs]
[I-D.ietf-roll-urban-routing-reqs] and
[I-D.ietf-roll-building-routing-reqs]), a variety of nodes
constraints must be taken into account during path computation (e.g.
node's resources such as memory, energy and CPU computational power).
Moreover, node attributes such as the ability to act as an aggregator
(node capable of performing data aggregation) may be of interest.
It is also worth mentioning that it fairly common for link in LLNs to
have fast changing node and link charateristics, which must be taken
into account carefully when specifying link metrics. For instance,
in addition to the normal dynamic nature of wireless connectivity,
nodes' resources such as residual energy and available memory are
changing continuously and may have to be taken into account during
the path computation. Similarly, link attributes including
throughput and reliability may drastically change over time due to
multi-path interference. That being said, very careful attention
must be given when using dynamic metrics and attributes that affect
routing decisions in order to preserve routing stability.
Furthermore, it is a time and energy consuming process to update
these dynamic metrics and recompute the routing tables on a frequent
basis. Therefore, it may be desirable to use a reduced set of
discrete values to reduce computational overhead and bandwidth
utilization. Of course, this comes with a cost, namely, reduced
metric accuracy.
Reliability is an example of qualitative parameters which is
necessary as a routing metric for path calculation. Such qualitative
parameters may be transformed to quantitative values. In other
cases, a set of flags may be defined to reflect a node state without
having to define discrete values to reflect that state.
Some link or node attributes (e.g. level of link reliability, energy
remaining on the node) can be used to perform constraint-based
routing. It is not required to use all the metrics and attributes
specified in this document. A particular implementation MAY use a
subset or all of the metrics defined in this document. The
requirements on reporting frequency may differ among metrics, thus
different reporting rates may be used for each category.
The specification of the objective function used to compute the path
Kim, et al. Expires October 31, 2009 [Page 5]
Internet-Draft draft-ietf-roll-routing-metrics-00 April 2009
is out of the scope of this document.
3. Node Metrics and Attributes
In some cases, node metrics and attributes are static. However,
critical metrics such as residual power will need to be considered as
dynamic metrics and monitored continuously in some scenarios. An
implementation may make use of a multi-threshold scheme rather than
fine granular metric update so as to avoid constant routing changes.
A "multi-threshold scheme" sets a few levels to categorize metric
values and uses the levels instead of actual numerical values.
In LLNs, it is not uncommon to have highly heterogeneous nodes in
term of capabilities (e.g. nodes being battery operated or not,
amount of memory, etc) and functionalities. 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 implies that constraint-based routing will be used
in some cases. Thus, the computed path may not be the shortest path
according to some specified metrics. Resource-awareness should be
employed to routing protocols strictly or loosely considering trade-
off between cost and benefit.
3.1. Node Memory Resources
Memory is a critical node resources in presence of constrained nodes.
Units is to be determined.
3.2. Node CPU Resources
CPU duty cycle for virtually all LLN applications to date is well
below 10%, and the trend in low power embedded systems is to more
capable processors rather than less. Computational speed is not
expected to be a limiting factor in routing in LLNs.
3.3. Node Residual Energy
Whenever possible, a node with low residual energy should not be
selected as a router, thus the support for constrained-based routing
is needed. In such cases, the routing protocol engine may compute a
longer path (constraint based) for some traffic in order to increase
the network life duration. The routing engine may prefer a "longer"
path that traverses mains-powered nodes or nodes equipped with energy
scavening, rather than a "shorter" path through battery operated
nodes.
Power and energy are clearly critical resources, given the name of
Kim, et al. Expires October 31, 2009 [Page 6]
Internet-Draft draft-ietf-roll-routing-metrics-00 April 2009
our working group. As yet there are no simple abstractions which
adequately cover the broad range of power sources and energy storage
devices used in existing LLN nodes. These include line-power,
primary batteries, energy-scavengers, and a variety of secondary
storage mechanisms. Scavengers may provide a reliable low level of
power, such as might be available from a 4-20mA loop; a reliable but
periodic stream of power, such as provided by a well-positioned solar
cell; or unpredictable power, such as might be provided by a
vibrational energy scavenger on an intermittently powered pump.
Routes which are viable when the sun is shining may disappear at
night. A pump turning on may connect two previously disconnected
sections of a network.
Storage systems like rechargeable batteries often suffer substantial
degradation if regularly used to full discharge, leading to different
residual energy numbers for regular vs. emergency operation. A route
for emergency traffic may have a different optimum than one for
regular reporting.
Batteries used in LLNs often degrade substantially if their average
current consumption exceeds a small fraction of the peak current that
they can deliver. It is not uncommon for LLN nodes to have a
combination of primary storage, energy scavenging, and secondary
storage, leading to three different values for acceptable average
current depending on the time frame being considered, e.g.
milliseconds, seconds, and hours/years.
Raw power and energy values are meaningless without knowledge of the
energy cost of sending and receiving packets, and lifetime estimates
have no value without some higher-level constraint on the lifetime
required of a device. In some cases the route that exhausts the
battery of a node on the bed table in a month may be preferable to a
route that reduces the lifetime of a node in the wall to a decade.
Given the complexity of trying to address such a broad collection of
constraints, a much simpler path is preferable in the short term. A
few energy levels, for example, unlimited, scavenger supported,
enough energy and low energy, may be sufficient to compute an
adequite path in highly constrained scenarios. The method to set the
level will be node and application dependent, and is out of the scope
of this document.
3.4. Node Overload State
Node workload may be hard to determine and express in some scalar
form. However, node workload could be a useful metric to consider
during path calculation, in particular when queuing delays must be
minimized for highly sensitive traffic considering MAC layer delay.
Kim, et al. Expires October 31, 2009 [Page 7]
Internet-Draft draft-ietf-roll-routing-metrics-00 April 2009
Using a simple 1-bit flag to characterize the node workload may
provide a sufficient level of granularity, similarly to the
"overload" bit used in protocols such as ISIS.
Algorithms used to set the overload bit and to compute path to
potentially avoid node with their overload bit set are outside the
scope of this document.
3.5. Data Aggregation Attribute
Data fusion involves more complicated processing to improve accuracy
of the output data while data aggregation mostly aims at reducing the
amount of data.
Some applications may make use of the aggregation node attribute in
their routing decision so as to minimize the amount of traffic on the
network, thus potentially increasing its life time in battery
operated environments.
Applications where high directional data flow is expected in a
regular basis may take advantage of data aggregation supported
routing.
4. Link Metrics and Attributes
There are several dynamic link attributes of interest especially in
wireless LLNs. Even in case of fixed LLNs where nodes are
stationary, link qualities may greatly vary in the presence of
obstacles and signal interference.
4.1. Throughput
Many LLNs support a wide range of throughput, measured either in bits
per second or packets per second. For some links, this may be due to
variable coding. For the deeply duty-cycled links found in many
LLNs, the variability comes as a result of trading power consumption
for bit rate. There are several MAC sub-layer protocols which allow
the effective bit rate and power consumption of a link to vary over
more than three orders of magnitude, with a corresponding change in
power consumption. For efficient operation, nodes must be able to
report the range of throughput that their links can handle, and
currently available throughput.
4.2. Latency
As with throughput, the latency of many LLN MAC sub-layers can be
varied over many orders of magnitude, again with a corresponding
Kim, et al. Expires October 31, 2009 [Page 8]
Internet-Draft draft-ietf-roll-routing-metrics-00 April 2009
change in current consumption. Some LLN MACs will allow the latency
to be adjusted globally on the subnet, or on a link-by-link basis, or
not at all. Some will insist that it be fixed for a given link, but
allow it to be variable from link to link. For efficient operation,
nodes must be able to report the range of latency that their links
can handle, and the currently available latency.
4.3. Link reliability
In LLNs, link reliability is degraded by external interference and
multi-path interference. Multipath typically affects both directions
on the link equally, whereas external interference is sometimes uni-
directional. Time scales vary from milliseconds to days, and are
often periodic and linked to human activity. Packet error rate can
generally be measured directly, and other metrics (e.g. bit error
rate, mean time between failures) are typically derived from that.
A change in link quality can affect network connectivity, thus, link
quality may be taken into account as a critical routing metric. Link
quality metric should be applied to each directional link unless bi-
directionality is one of routing metrics.
4.4. Link Coloring
Link color is an administrative static attribute used to avoid or
attract specific links for specific traffic types.
5. Computation of Dynamic Metrics and Attributes
As already pointed out, dynamically calculated metrics are of the
utmost importance in many circumstances in LLNs. This is mainly
because a variety of metrics change on a frequent basis, thus
implying the need to adapt the routing decisions. That being said,
care must be given to the pace at which changes are reported in the
network. The attributes will change according to their own time
scales. The protocol can control the reporting rate.
To minimize metric updates, multi-threshhold algorithms may be used
to determine when updates shoudl be sent. When practical, a low-pass
filter should be used to avoid rapid fluctuations of these values.
Finally, although the specification of path computation algorithms
using dynamic metrics are out the scope of this document, the
objective function should be designed carefully to avoid too frequent
computation of new routes upon metric values changes.
Controlled adaptation of the routing metrics and rate at which paths
are computed are critical to avoid undesirable routing instabilities
Kim, et al. Expires October 31, 2009 [Page 9]
Internet-Draft draft-ietf-roll-routing-metrics-00 April 2009
resulting in increased latencies and packet loss because of temporary
micro-loops. Furthermore, excessive route changes will impact the
traffic and power consumption in the network adversely.
6. Open Issues
Other items to be addressed in further revisions of this document
include:
o Metrics related to security (e.g. capability to avoid a node that
has not been authorized or authenticated).
o Specification of metric units.
o Practical usage related to the use of multiple metrics for path
computation in highly constrained envrionments.
7. Metric Consistency
Since a set of metrics and attributes will be used for links and
nodes in LLN, it is particularly critical to ensure the use of
consistent metric calculation mechanisms for all links and nodes in
the network. Although this is applicable to all routing schemes, a
number of such metrics and attributes in LLN make it particularly
challenging.
8. IANA Considerations
This document includes no request for IANA action.
9. Security Considerations
Routing metrics should be handled in a secure and trustful manner.
For instance, a malicious node can not advertise falsely that it has
good metrics for routing and belong to the established path to have a
chance to intercept packets.
10. Acknowledgements
The authors would like to acknowledge the contributions of YoungJae
Kim, David Meyer, Mischa Dohler, Anders Brandt, Philip Levis and
Pascal Thubert for their review and comments.
Kim, et al. Expires October 31, 2009 [Page 10]
Internet-Draft draft-ietf-roll-routing-metrics-00 April 2009
11. References
11.1. Normative References
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119, March 1997.
11.2. Informative References
[I-D.ietf-roll-building-routing-reqs]
Martocci, J., Riou, N., Mil, P., and W. Vermeylen,
"Building Automation Routing Requirements in Low Power and
Lossy Networks", draft-ietf-roll-building-routing-reqs-05
(work in progress), February 2009.
[I-D.ietf-roll-home-routing-reqs]
Porcu, G., "Home Automation Routing Requirements in Low
Power and Lossy Networks",
draft-ietf-roll-home-routing-reqs-06 (work in progress),
November 2008.
[I-D.ietf-roll-indus-routing-reqs]
Networks, D., Thubert, P., Dwars, S., and T. Phinney,
"Industrial Routing Requirements in Low Power and Lossy
Networks", draft-ietf-roll-indus-routing-reqs-05 (work in
progress), April 2009.
[I-D.ietf-roll-terminology]
Vasseur, J., "Terminology in Low power And Lossy
Networks", draft-ietf-roll-terminology-00 (work in
progress), October 2008.
[I-D.ietf-roll-urban-routing-reqs]
Dohler, M., Watteyne, T., Winter, T., Barthel, D.,
Jacquenet, C., Madhusudan, G., and G. Chegaray, "Urban
WSNs Routing Requirements in Low Power and Lossy
Networks", draft-ietf-roll-urban-routing-reqs-05 (work in
progress), March 2009.
[RFC1195] Callon, R., "Use of OSI IS-IS for routing in TCP/IP and
dual environments", RFC 1195, December 1990.
[RFC2328] Moy, J., "OSPF Version 2", STD 54, RFC 2328, April 1998.
[RFC2702] Awduche, D., Malcolm, J., Agogbua, J., O'Dell, M., and J.
McManus, "Requirements for Traffic Engineering Over MPLS",
RFC 2702, September 1999.
Kim, et al. Expires October 31, 2009 [Page 11]
Internet-Draft draft-ietf-roll-routing-metrics-00 April 2009
[RFC3209] Awduche, D., Berger, L., Gan, D., Li, T., Srinivasan, V.,
and G. Swallow, "RSVP-TE: Extensions to RSVP for LSP
Tunnels", RFC 3209, December 2001.
Authors' Addresses
Mijeon (editor)
Future Tech Lab., Korea Telecom
17 Woomyeon-dong, Seocho-gu
Seoul, 137-792
Korea
Email: mjkim@kt.com
JP Vasseur (editor)
Cisco Systems, Inc
11, Rue Camille Desmoulins
Issy Les Moulineaux, 92782
France
Email: jpv@cisco.com
Kris
Dust Networks
30695 Huntwood Ave.
Hayward, CA 95544
USA
Email: kpister@dustnetworks.com
Hakjin
Future Tech Lab., Korea Telecom
17 Woomyeon-dong, Seocho-gu
Seoul, 137-792
Korea
Email: hjchong@kt.com
Kim, et al. Expires October 31, 2009 [Page 12]
