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

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-

   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

   The list of Internet-Draft Shadow Directories can be accessed at

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


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

   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

   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

   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

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

   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

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

              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.

              Porcu, G., "Home Automation Routing Requirements in Low
              Power and Lossy Networks",
              draft-ietf-roll-home-routing-reqs-06 (work in progress),
              November 2008.

              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.

              Vasseur, J., "Terminology in Low power And Lossy
              Networks", draft-ietf-roll-terminology-00 (work in
              progress), October 2008.

              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


   JP Vasseur (editor)
   Cisco Systems, Inc
   11, Rue Camille Desmoulins
   Issy Les Moulineaux,   92782


   Dust Networks
   30695 Huntwood Ave.
   Hayward, CA  95544


   Future Tech Lab., Korea Telecom
   17 Woomyeon-dong, Seocho-gu
   Seoul,   137-792


Kim, et al.             Expires October 31, 2009               [Page 12]