Networking Working Group M. Kim, Ed.
Internet-Draft KT
Intended status: Standards Track JP. Vasseur, Ed.
Expires: May 21, 2009 Cisco Systems
H. Chong
KT
November 17, 2008
Routing Metrics used for Path Calculation in Low Power and Lossy
Networks
draft-mjkim-roll-routing-metrics-02
Status of this Memo
By submitting this Internet-Draft, each author represents that any
applicable patent or other IPR claims of which he or she is aware
have been or will be disclosed, and any of which he or she becomes
aware will be disclosed, in accordance with Section 6 of 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 May 21, 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.
Kim, Vasseur et al. Expires May 21, 2009 [Page 1]
Internet-Draft Routing Metrics for LLNs November 2008
Table of Contents
1. Note (to be removed upon publication) . . . . . . . . . . . . 3
2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 3
3. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3
4. Node metrics and attributes . . . . . . . . . . . . . . . . . 5
4.1. Node resources . . . . . . . . . . . . . . . . . . . . . . 5
4.2. Residual Energy . . . . . . . . . . . . . . . . . . . . . 5
4.3. Node overload . . . . . . . . . . . . . . . . . . . . . . 6
4.4. Data Aggregation attribute . . . . . . . . . . . . . . . . 6
4.5. Node reliability . . . . . . . . . . . . . . . . . . . . . 8
5. Link metrics and attributes . . . . . . . . . . . . . . . . . 8
5.1. Throughput . . . . . . . . . . . . . . . . . . . . . . . . 8
5.2. Link reliability . . . . . . . . . . . . . . . . . . . . . 8
5.3. Link coloring . . . . . . . . . . . . . . . . . . . . . . 9
6. Computation of dynamic metrics and attributes . . . . . . . . 9
7. Open issues . . . . . . . . . . . . . . . . . . . . . . . . . 9
8. Metric consistency . . . . . . . . . . . . . . . . . . . . . . 10
9. Security Considerations . . . . . . . . . . . . . . . . . . . 10
10. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 10
11. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 10
12. References . . . . . . . . . . . . . . . . . . . . . . . . . . 10
12.1. Normative References . . . . . . . . . . . . . . . . . . . 10
12.2. Informative References . . . . . . . . . . . . . . . . . . 11
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 12
Intellectual Property and Copyright Statements . . . . . . . . . . 13
Kim, Vasseur et al. Expires May 21, 2009 [Page 2]
Internet-Draft Routing Metrics for LLNs November 2008
1. Note (to be removed upon publication)
Rev -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. 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].
This document makes use of the terminology defined in
[I-D.ietf-roll-terminology].
o Mobile LLN: Low power and Lossy Network where some nodes are
mobile.
o Fixed LLN: Low power and Lossy Network where all nodes are static,
not mobile.
3. Introduction
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.
Routing metrics can be classified according to the following set of
characteristics:
- Link versus Node metrics
- Qualitative versus quantitative
- Dynamic or static
Historically, IGP such as OSPF [RFC2328] and IS-IS [ISO.10589.1992]
Kim, Vasseur et al. Expires May 21, 2009 [Page 3]
Internet-Draft Routing Metrics for LLNs November 2008
have been using quantitative static link metrics. Other mechanisms
such as Multiprotocol Label Switching (MPLS) Traffic Engineering (TE)
[RFC2702] [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).
It must be noted that the use of dynamic metrics is not new and has
been experimented in ARPANET 2 [Khanna1989], with a 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
draft-ietf-roll-urban-routing-reqs,
draft-ietf-roll-indus-routing-reqs,
draft-ietf-roll-home-routing-reqs,
draft-ietf-roll-building-routing-reqs) in LLNs, several nodes
constraints must be taken into account during path computation. Node
metrics include 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. Additionally, mobility may also be considered.
Link attributes include throughput and reliability. Bi-
directionality are also of interest.
In LLNs, it is fairly common for links and nodes to have changing
characteristics in terms of reliability and available resources.
Thus, it is required to specify a set of dynamic metrics. For
instance, even though a wireless sensor network topology is static in
absence of failure, 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
because moving obstacles can appear at any time. That being said,
very careful attention must be given when using highly dynamic
metrics and attributes that affect routing decisions in order to
preserve the routing stability. Furthermore, it is 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 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
Kim, Vasseur et al. Expires May 21, 2009 [Page 4]
Internet-Draft Routing Metrics for LLNs November 2008
having to define discrete values to reflect that state.
This document specifies a set of link and nodes metrics that can be
used to compute paths within a LLN. 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.
Requirement of reporting frequency may differ among metrics, so
classifying a few categories can be exploited and different reporting
rates should be used for each category. The specification of the
objective function used to compute the path is out of the scope of
this document.
4. Node metrics and attributes
In most cases, node metrics and attributes are static. However,
critical metrics such as residual power might 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.
"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. node being battery operated or not, amount
of memory, etc) and functionalities. More capable and stable nodes
can 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.
4.1. Node resources
Memory and CPU resources are critical node resources in presence of
constrained nodes. Resource-awareness should be employed to routing
protocols strictly or loosely considering trade-off between cost and
benefit.
4.2. Residual Energy
Low power is one of the most distinguished features of LLNs, so node
residual energy is a pivotal metric in environments where nodes are
battery powered. Residual energy should be taken as a relative value
Kim, Vasseur et al. Expires May 21, 2009 [Page 5]
Internet-Draft Routing Metrics for LLNs November 2008
considering statistical node lifetime and other conditions such as
the role of the node in the network. For example, if the node's
expected lifetime is 5 years and the remaining energy is only one
fifth, then the energy is a critical resource for the node. Hence,
whenever possible, the node should not be selected as a router (an
intermediate node to deliver data), thus the support for constrained-
based routing is needed. In such cases, the routing protocol engine
may compute a longer path (constrained based) for some traffic in
order to increase the network life duration. Another typical use of
constrained-based routing consists of using a node attribute as a
routing criterion. For example, the routing engine may prefer a
"longer" path that traverses main powered nodes or nodes equipped
with rechargeable batteries. Algorithm can be designed to consider a
combination of node metrics and node attributes. Algorithms defining
how such metrics and attributes should be combined are outside of the
scope of this document.
Generally, the residual energy should be taken as a dynamic metric.
Most battery operated devices have the ability to estimate the
remaining energy [I-D.ietf-roll-indus-routing-reqs]. However,
initial energy status can be considered as a static metric in some
situations where monitoring the energy level is too CPU intensive. A
few energy levels, for example, unlimited, scavenger supported,
enough energy and low energy, may be sufficient to compute the path
in highly constrained scenarios. The method to set the level should
be defined using same criteria at every node.
Note: a detailed list of energy related metrics will be specified in
the next revision of this document.
4.3. Node overload
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.
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 IS-IS [ISO.10589.1992]. An
implementation may then decide to exclude from its routes any node
with a "heavy" value for workload unless there is no alternative.
4.4. Data Aggregation attribute
Some nodes may sense or receive the same (or similar) data if the
nodes are located in a close area due to data correlation. Thus,
data aggregation/fusion may be possible. Data fusion involves more
complicated processing to improve accuracy of the output data while
Kim, Vasseur et al. Expires May 21, 2009 [Page 6]
Internet-Draft Routing Metrics for LLNs November 2008
data aggregation mostly aims to reduce the amount of data.
Especially in urban applications where sensor nodes collect
environmental information and send it to a data sink, a potentially
large amount of nodes sense similar data. For the sake of
illustration, consider the simple example shown in the Figure 1. Let
us assume that three nodes A, B and C need to send sensed data to the
data sink. Node A sensed "xyz" and sent this data to node C. Since C
also sensed same data, it has no additional information from node A.
However, because the data node B sent is "xqz", node C aggregates
this data with its own data "xyz" resulting in "xyqz". Therefore,
node C sends "xyqz" to the data sink. In this example, each node's
data requires 3 bytes. If no aggregation is performed, node C needs
to send 9 byte data to the sink, but C only sends 4 bytes thanks to
data aggregation.
A B
|------| |------|
| xyz | | xqz |
|______| |______|
\ /
\ /
\ C / sink
|------| xyqz |------|
| xyz |-----------| |
|______| |______|
Figure 1: Data aggregation
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.
To make data aggregation possible, the routing protocol needs to
capture the time and location dependent correlation among sensed data
from nodes on the possible routes, which may be challenging.
Obtaining correlation structure also demands high resource (energy)
consumption and in-network processing itself may have high
complexity. Consequently, in most applications, data aggregation may
not be adopted for routing. Applications where high directional data
flow is expected in a regular basis may take advantage of data
aggregation supported routing.
Kim, Vasseur et al. Expires May 21, 2009 [Page 7]
Internet-Draft Routing Metrics for LLNs November 2008
4.5. Node reliability
Node reliability can be measured by many different factors such as
the node failure rate and mobility (dynamicity). Node reliability
directly affects the network topology and connectivity, which in turn
may trigger path re-computation. It is usually very challenging to
estimate or monitor node reliability and historical data can be used
to that end. A specific function needs to be defined to get values
of the reliability metric from a variety of features affecting node
reliability. In the most constrained LLN environments, the simple
heuristic of classifying nodes into static and dynamic can be very
helpful in routing decision since static node are more reliable, thus
should be preferred.
5. Link metrics and attributes
There are several dynamic link attributes 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. That being said, as for node metrics and attributes,
link metrics and attributes may be considered as static in fixed LLNs
not only because it is very challenging to update them in real-time
but also because updating mechanisms may be too time and energy
consuming. However, in mobile LLNs, we may need to consider these
metrics and attributes as dynamic.
5.1. Throughput
Throughput is the average rate of successful message delivery over a
communication channel. Throughput is usually measured in bit rate
(bits per second). There are nodes that support for multiple bit
rates, possibly using different encodings, to allows multiple
throughput values between two nodes. This should be taken into
account during throughput evaluation.
5.2. Link reliability
Link reliability can be measured by the Bit Error Rate (BER), Packet
Error Rate (PER), Mean Time Between Failures (MTBF) or link churn,
the rate at which links see their status changed (up or down). Link
reliability is closely related to node reliability especially in
wireless LLNs. Two nodes which form a link affect directly to the
link reliability as follows: if one (or both) end node of the link
dies or moves away beyond of the transmission range from the other
node, the link vanishes and should be removed from routing. However,
link reliability is also influenced by other factors like unexpected
obstacles or temporary interference.
Kim, Vasseur et al. Expires May 21, 2009 [Page 8]
Internet-Draft Routing Metrics for LLNs November 2008
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. Since path reliability is
a function of each link and node reliability, such metrics may become
critical as path length increases.
5.3. Link coloring
Link color is an administrative static attribute used to avoid or
attract specific links for specific traffic types.
6. 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,
careful care must be given to the pace at which such metrics and
attributes change.
Algorithms used to compute such metrics can use multi-threshold
mechanisms with low and high water marks for binary values and a
limited set of discrete metric values for non binary metric.
Furthermore, it is recommended to use a low-pass filter 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, it is recommended to design the
objective function carefully to avoid too frequent computation of new
routes upon metric values changes.
Controlled adaptation of the routing metrics and rate at which path
are computed are critical to avoid undesirable routing instabilities
resulting in increased latencies and packet loss because of temporary
micro-loops. Furthermore, since LLNs are made of constrained
devices, computational resources must be used with care to preserve
battery in case of battery operated devices and not to impact quality
of service of the data traffic.
7. Open issues
Other items to be addressed in further revisions of this document
include:
o Metrics related to security: Metrics that security is associated
with need to be further considered. If a route is comprised of
Kim, Vasseur et al. Expires May 21, 2009 [Page 9]
Internet-Draft Routing Metrics for LLNs November 2008
authenticated and authorized nodes for the data, then the route
may be preferable.
o Consideration of routing efficiency: Since LLNs are highly
constrained networks, maintaining many different routing metrics
is challenging. Routing should be lightweight.
8. 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.
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. IANA Considerations
This document requests no action by IANA.
11. Acknowledgements
The authors would like to acknowledge the contributions of YoungJae
Kim, David Meyer, Mischa Dohler, Kris Pister, Anders Brandt, Philip
Levis and Pascal Thubert for their review and comments.
12. References
12.1. Normative References
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119, March 1997.
Kim, Vasseur et al. Expires May 21, 2009 [Page 10]
Internet-Draft Routing Metrics for LLNs November 2008
12.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-01
(work in progress), October 2008.
[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-04 (work in progress),
October 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-02 (work in
progress), October 2008.
[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-02 (work in
progress), October 2008.
[ISO.10589.1992]
International Organization for Standardization,
"Intermediate system to intermediate system intra-domain-
routing routine information exchange protocol for use in
conjunction with the protocol for providing the
connectionless-mode Network Service (ISO 8473)",
ISO Standard 10589, 1992.
[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.
[RFC3209] Awduche, D., Berger, L., Gan, D., Li, T., Srinivasan, V.,
and G. Swallow, "RSVP-TE: Extensions to RSVP for LSP
Kim, Vasseur et al. Expires May 21, 2009 [Page 11]
Internet-Draft Routing Metrics for LLNs November 2008
Tunnels", RFC 3209, December 2001.
[Khanna89] Khanna, A., and Zinky, J.,"The revised ARPANET routing
metric", ACM SIGCOMM, Austin, USA, Sept. 1989, pp. 45-56.
Authors' Addresses
Mijeom Kim (editor)
Future Tech Lab., KT
17 Woomyeon-dong, Seocho-gu
Seoul 137-792
Korea
Phone: +82-2-526-6063
Fax: +82-2-526-5071
Email: mjkim@kt.com
JP Vasseur (editor)
Cisco Systems
11, Rue Camille Desmoulins
L'Atlantis 92782 Issy Les Moulineaux
France
Email: jpv@cisco.com
Hakjin Chong
Future Tech Lab., KT
17 Woomyeon-dong, Seocho-gu
Seoul 137-792
Korea
Phone: +82-2-526-5070
Fax: +82-2-526-5071
Email: hjchong@kt.com
Kim, Vasseur et al. Expires May 21, 2009 [Page 12]
Internet-Draft Routing Metrics for LLNs November 2008
Full Copyright Statement
Copyright (C) The IETF Trust (2008).
This document is subject to the rights, licenses and restrictions
contained in BCP 78, and except as set forth therein, the authors
retain all their rights.
This document and the information contained herein are provided on an
"AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS
OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY, THE IETF TRUST AND
THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS
OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF
THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED
WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
Intellectual Property
The IETF takes no position regarding the validity or scope of any
Intellectual Property Rights or other rights that might be claimed to
pertain to the implementation or use of the technology described in
this document or the extent to which any license under such rights
might or might not be available; nor does it represent that it has
made any independent effort to identify any such rights. Information
on the procedures with respect to rights in RFC documents can be
found in BCP 78 and BCP 79.
Copies of IPR disclosures made to the IETF Secretariat and any
assurances of licenses to be made available, or the result of an
attempt made to obtain a general license or permission for the use of
such proprietary rights by implementers or users of this
specification can be obtained from the IETF on-line IPR repository at
http://www.ietf.org/ipr.
The IETF invites any interested party to bring to its attention any
copyrights, patents or patent applications, or other proprietary
rights that may cover technology that may be required to implement
this standard. Please address the information to the IETF at
ietf-ipr@ietf.org.
Kim, Vasseur et al. Expires May 21, 2009 [Page 13]