[Search] [txt|pdf|bibtex] [Tracker] [Email] [Diff1] [Diff2] [Nits]

Versions: 00 01                                                         
Networking Working Group                                       D. Culler
Internet-Draft                                                 Arch Rock
Intended status: Informational                               JP. Vasseur
Expires: January 8, 2008                              Cisco Systems, Inc
                                                            July 7, 2007

         Routing Requirements for Low Power And Lossy Networks

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-

   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 January 8, 2008.

Copyright Notice

   Copyright (C) The IETF Trust (2007).


   The need for high quality routing for Low power and Lossy Network
   (L2N) such as sensor networks comprised of highly constrained devices
   (CPU, memory, ...) in sometimes unstable wireless environments is
   critical now and will continue to increase.  Interest in this class
   of applications has grown dramatically in recent years and a routing
   solution addressing the specific environments of such networks is
   highly required considering the numerous, incompatible open-source

Culler & Vasseur         Expires January 8, 2008                [Page 1]

Internet-Draft      draft-culler-rl2n-routing-reqs-01          July 2007

   and proprietary routing protocols as well as several industrial
   forums.  The aim of this document is to define the routing
   requirements for Sensor Networks at the IP layer.  Such routing
   protocol(s) would need to address several unique aspects of this
   class of embedded devices and would operate in networks comprising
   links of various nature.

Requirements Language

   The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
   document are to be interpreted as described in RFC 2119 [RFC2119].

Table of Contents

   1.  Terminology  . . . . . . . . . . . . . . . . . . . . . . . . .  3
   2.  Introduction . . . . . . . . . . . . . . . . . . . . . . . . .  3
   3.  "Route over" versus "Mesh under" . . . . . . . . . . . . . . .  3
   4.  Unique Routing Requirements of Low Power Wireless
       Networkson . . . . . . . . . . . . . . . . . . . . . . . . . .  4
     4.1.  Spatially-Driven Multihop  . . . . . . . . . . . . . . . .  4
     4.2.  Light footprint  . . . . . . . . . . . . . . . . . . . . .  5
     4.3.  Small MTU  . . . . . . . . . . . . . . . . . . . . . . . .  6
     4.4.  Deep Power Management  . . . . . . . . . . . . . . . . . .  6
     4.5.  Heterogeneous Capabilities . . . . . . . . . . . . . . . .  7
     4.6.  Highly Variable Connectivity . . . . . . . . . . . . . . .  7
     4.7.  Structured Workload and Traffic Pattern  . . . . . . . . .  8
     4.8.  Partial Information  . . . . . . . . . . . . . . . . . . .  8
     4.9.  Multi-topology Routing . . . . . . . . . . . . . . . . . .  9
     4.10. Data Aware routing . . . . . . . . . . . . . . . . . . . .  9
   5.  Relationship with other Routing Protocols  . . . . . . . . . .  9
   6.  Security Issues  . . . . . . . . . . . . . . . . . . . . . . . 10
   7.  Manageability Issues . . . . . . . . . . . . . . . . . . . . . 10
   8.  IANA Considerations  . . . . . . . . . . . . . . . . . . . . . 10
   9.  Security Considerations  . . . . . . . . . . . . . . . . . . . 10
   10. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 10
   11. References . . . . . . . . . . . . . . . . . . . . . . . . . . 10
     11.1. Normative References . . . . . . . . . . . . . . . . . . . 10
     11.2. Informative References . . . . . . . . . . . . . . . . . . 11
   Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 11
   Intellectual Property and Copyright Statements . . . . . . . . . . 12

Culler & Vasseur         Expires January 8, 2008                [Page 2]

Internet-Draft      draft-culler-rl2n-routing-reqs-01          July 2007

1.  Terminology

   CMOS: Complementary metal-oxide-semiconductor.  DRAM: Dynamic Random
   Access Memory.  L2N: Low power and Lossy Network.

   MAC: Medium Access control.  PAN: Personal Area Network.  RAM: Random
   Access Memory.  RF Links: Radio Frequency Links.  RL2N: Routing in
   Low power and Lossy Networks.

   SNR: Signal Noise Ratio.  SRAM: Static Random Access Memory.

2.  Introduction

   The need for high quality routing for wireless networks comprised of
   highly constrained (memory, power, bandwidth, CPU ...) and typically
   embedded devices in a potentially variable environment (thus the
   therm "Lossy") is critical now and will continue to increase.
   Interest in this class of applications, including sensor networks,
   device networks, environmental monitoring, home automation, building
   automation, process control, automated meter readings, condition-
   based maintenanace, security, and others, has grown dramatically in
   recent years; a routing solution addressing the specific environments
   of such networks is highly required considering the numerous,
   incompatible open-source and proprietary routing protocols that have
   emerged, as well as several industrial forums that have emerged over
   the IEEE 802.15.4 link and various proprietary links.

   Such routing protocol(s) would need to address several unique
   requirements of this class of embedded devices and would operate in
   networks comprising links of various nature.  Considering the variety
   of Sensor and Controller-based applications, there may not be a
   single routing protocol satisfying the entire list of requirements,
   in which case it may be decided to define a limited set of routing
   protocols that could be combined to satify the overall objective.  It
   is also envisioned that the designed solution will not address very
   specific requirements of some more "exotic" networks.

3.  "Route over" versus "Mesh under"

   Within the IETF, working groups are attending to aspects of this
   issue with, for example, 6LoWPAN considering layer 2 "mesh-under" for
   IEEE 802.15.4 links and MANET considering layer 3 and higher layer
   routing in mobile environments with relatively high powered nodes and
   links.  Meanwhile, industry forums, including Zigbee, Zwave, Wireless
   HART, and ISA SP100.11a, and numerous proprietary offerings address
   the combination of low-power and wireless, but only within the

Culler & Vasseur         Expires January 8, 2008                [Page 3]

Internet-Draft      draft-culler-rl2n-routing-reqs-01          July 2007

   equivalent of a single IP link and only within the context of stacks
   vertically integrated from the physical layer to the application with
   no provisions for routing to other kinds of links.

   It is clearly envisioned that Low Power and Lossy Networks (L2Ns)
   will comprise a variety of nodes interconnected by links of different
   nature including IEEE 802.15.4, IEEE 802.11, IEEE 802.16 and so on.

   The IETF 6LoWPAN working group has defined a format for IPv6 over
   802.15.4 with extensive header compression, fragmentation for very
   small link frames, and support for mesh routing under the IP link
   (see [I-D.ietf-6lowpan-format]).

   Clearly routing techniques can be defined at the link layer (also
   referred as to the "Mesh Under" approach).  By contrast, the "Route
   over" approach exclusively relies on IP routing over a network made
   of a variety of nodes interconnected by links of various nature.  The
   aim of this document is to define the routing requirements L2Ns at
   the IP layer.  As such, it pertains to collections of IEEE 802.15.4
   devices, but is not limited to communication within a single IP link.
   It pertains to IP level routing among multiple such PANs, routing
   among IEEE 802.15.4 PANs and other links, and routing in other low
   power (wireless) networks.

4.  Unique Routing Requirements of Low Power Wireless Networkson

   L2Ns present a variety of unique routing requirements driven partly
   by implementation technology constraints, partly by the domain of
   usage, and partly by application characteristics.  These issues are
   listed roughly in order of criticality.
   [I-D.levis-rl2n-overview-protocols]provides an overview of existing
   protocols in light of L2Ns' specific requirements.  Of course, none
   of these protocols were designed with all these considerations in
   mind, and so it is not surprising that some of the issues remain

   Whereas this document lists the set of generic requirement for RL2N
   other documents lists application specific routing requirements.  The
   routing requirements for home control and automation are discussed in

4.1.  Spatially-Driven Multihop

   The low transmission power of PAN (Personal Area Network) radios
   (e.g. collection of IEEE 802.15 links, implies that the range is
   relatively short; multiple hops are required to achieve communication
   over greater distances.  Variously referred to as mesh or multihop

Culler & Vasseur         Expires January 8, 2008                [Page 4]

Internet-Draft      draft-culler-rl2n-routing-reqs-01          July 2007

   routing, such multihop routing communication is important from a
   basic energy viewpoint.  The energy cost to traverse a given distance
   with multiple fixed-power hops grows only linearly with distance,
   whereas the energy of a single RF "hop" grows as a cubic or higher
   power of the distance, depending on elevation and other factors.

   It is also essential from a reliability viewpoint.  Lower
   transmission power generally means lower SNR, relatively high per-hop
   loss rates and greater sensitivity to fading, interference,
   attenuation, and occlusion.  Mutihop communication permits routing
   around obstacles and provides temporal diversity through
   retransmission as well as spatial diversity through multiple
   receivers, i.e., multipath routing.  In addition, with multihop
   routing use to cover distance, route formation and reliability are
   intimately linked.  Taking a longer hop will typically incur a larger
   loss rate, while a more reliable hop incurs more transmissions to
   reach the destination.  These issues occur potentially both at layer
   2, with IP routing over mesh-routed links, and, of course, at layer
   3, with IP routing over similar or dissimilar links.

   Furthermore, with multiple points of egress between low-power
   wireless networks and conventional powered networks, route selection
   over on type of link may be influenced by factors in the low-power

4.2.  Light footprint

   Integrated CMOS radios typically have sophisticated physical layer
   and MAC support integrated with the transceiver.  However, the
   network layer over this MAC (or sub-MAC) is generally implemented on
   a microcontroller device with the capabilities and resources
   historically associated with serial links (e.g., RS-232 and RS-485).
   In particular, as of today, these devices have only a few kilobytes
   of RAM and a few to several tens of kilobytes of program ROM.  The
   memory capacity of these device has been growing, but at much slower
   rate than the SRAM and DRAM storage found in microprocessor-based
   systems.  The marginal cost of memory in embedded devices is much
   greater than in conventional computers and standby power consumption
   increases with RAM capacity due to leakage, so memory capacity
   impacts the lifetime of battery powered, low-duty cycle devices.

   Thus, the small memory capacity of these units is fundamental and
   constrains routing table size, buffer capacity, and all routing
   states, including neighbor tables, link estimators, sequence number
   and other caches.  For example, link state algorithms, distance
   vector algorithms, and various intermediates and hybrids may have
   quite different relative merits when footprint is at premium, as
   compared to convergence rate, information exchange rate, and so on.

Culler & Vasseur         Expires January 8, 2008                [Page 5]

Internet-Draft      draft-culler-rl2n-routing-reqs-01          July 2007

   Existing routing protocols generally attend to constraints imposed by
   the links more than to constraints imposed by the nodes that connect
   those links.  The prime exception to this is scalability concerns of
   very large networks given fixed, albeit powerful, routers.  Here we
   are concerned with how routing protocols scale down to less capable
   nodes, even a fixed network scale.  We are also concerned with how
   routing protocols can allow more capable nodes to relieve less
   capable ones, even with common link characteristics.  Compression
   techniques, such as that in 6LoWPAN, enable the opportunity to
   perform routing on low-power devices (and permit the use of small
   MTUs and modest forwarding buffers), but do not address the resource
   requirements of the routing protocols that guide the exchange of such
   compressed packets.

4.3.  Small MTU

   Potentially high bit error rates, limited buffer capacity, limited
   channel capacity shared among numerous devices, and pervasive hidden-
   terminal occurrences due to the presence of many devices spread over
   physical regions all lead to the use of relatively small frames.
   Thus, per packet routing and header information comes at a premium.
   These issues, as well as limited energy, storage and bandwidth
   resources, imply that routing needs to be more aware of underlying
   physical factors than in traditional, even wireless, networks.  For
   example, protocols involving the exchange of lists of all 1-hop or
   all 2-hop neighbors may be forced to reckon with longs lists (if the
   physical density is high compared to the communication range).

   Alternatively, efforts to limit the degree of the network by
   adjusting transmission range bring additional physical factors into
   the purvue of routing.  Moreover, such measures to optimize route
   formation may be at odds with optimizing forwarding cost.

4.4.  Deep Power Management

   In most L2Ns, average transmission rates are very low, relative to
   channel capacity and powering on the radio to be ready receive costs
   power consumption that is roughly equal to that of actual
   transmission or reception.

   Thus, power budgets tend to be dominated by idle listening costs,
   unless the receivers are heavily duty cycled.  Thus, routing
   protocols MUST permit deep power management in the underlying link
   layers.  Currently, these link level techniques fall into three
   general categories: variants of TDMA either local or global, variants
   of cluster-based beaconing, and variants of preamble sample.  While
   power management is typically viewed as a layer 2 responsibility, few
   routing protocols anticipate that the devices responsible for

Culler & Vasseur         Expires January 8, 2008                [Page 6]

Internet-Draft      draft-culler-rl2n-routing-reqs-01          July 2007

   forwarding (and for route maintenance) have their network link off
   most (often over 99%) of the time.  Alternatively, certain link-level
   power management strategies may introduce extreme constraints on
   routing protocols.

4.5.  Heterogeneous Capabilities

   While the majority of devices are highly constrained, in many
   settings they operate in conjunction with more capable devices,
   including microprocessors hosting the same RF link but with greater
   RAM capacity, devices on mains power with either large or small
   storage, devices with directional to high-gain antennas, and devices
   that bridge or route to higher bandwidth links.  The existence of
   such a wide scope of device types within L2N (e.g Sensor Networks
   must be taken into account by the routing protocol to increase the
   lifetime and robustness of the most constrained devices.  In some
   cases, it may be advantageous to decrease the routing optimality at
   the benefit of energy saving for the most constrained (set of)
   devices.  Thus the routing protocol must not only be capable of
   supporting such a wide variety a devices but should consider the
   device capability as a key element of the routing decision, domain
   scope for the exchange of routing control plane messages.

   The routing protocol MUST support the ability to perform constrained
   based routing taking into account a variety of static or dynamic node

4.6.  Highly Variable Connectivity

   In many use cases for low power wireless devices, mobility is a
   central element.  However, even where all the devices are stationary,
   changes in environmental conditions gives rise to substantial changes
   in the connectivity relationships.  Moving objects, opening and
   closing of doors, background interference due to machinery,
   electronic equipment, radios, or other wireless networks, even
   atmospheric changes which increase or decrease absorption all alter
   the connection topology over which routing takes place.  Thus,
   routing protocols MUST be adaptive to a changing underlying topology
   and able to utilize connectivity and related information, such as
   link quality or signal strength, to maintain viable paths.

   The routing protocol MUST be particularly robust to topology changes
   in the network due to frequent change of link states.  For many
   embedded networks with substantial, often the mobility is structured,
   rather than ad hoc, such as items moving through a manufacturing
   process, shipping exchanges, mobile devices moving through a
   stationary network of similar devices, or collections of devices
   moving together as a network.  The most extreme variations in

Culler & Vasseur         Expires January 8, 2008                [Page 7]

Internet-Draft      draft-culler-rl2n-routing-reqs-01          July 2007

   connectivity, including mobility over large distances and enclosure
   into RF-opaque settings, give rise to intermittent connectivity (DTN:
   Delay Tolerant Networks).  Many use cases involve logging over long
   periods of disconnected operation and dispersion of logged data upon
   arrival and detection of a point of connectivity.  Such topology
   changing environments are usually challenging for routing protocols
   and may lead to frequent rerouting decisions: careful consideration
   must be given to bound the number of rerouting decisions for the most
   constrained devices so as to save energy.

4.7.  Structured Workload and Traffic Pattern

   The above characteristics suggest that effective general-purpose RL2N
   can be very hard - multiple hops are required over spontaneously
   varying connections where bandwidth is precious, packets are small
   and little state can be expended at each router.  However, the same
   observations suggests that routing protocols can take advantage of
   the constrained setting to simplify the general problem.  The
   workload or traffic pattern of use cases for these networks tend to
   be highly structured (Point-to-Multipoint or Multipoint-to-point due
   to the specific role of one or more sinks), unlike the any-to-any
   data transfers and interactive key-strokes that dominate typical
   client and server workloads.  Instrumentation and monitoring
   typically involve regular, periodic, or alarm-based collection from a
   large collection of devices.  Configuration, tasking, and management
   typically involve dissemination of commands to an aggregate of
   devices.  Automation, such as lighting control, involve numerous
   long-lived aggregates of actuation points and control points.  Uses
   in transportation and shipping involve opportunistic communication
   bursts upon arrival at suitable way points.  General-purpose any-to-
   any connectivity arises in situations such as management, diagnosis,
   and field access.  In many cases, exploiting such structure may
   simplify difficult problems arising from resource constraints or
   variation in connectivity.  Thus the routing protocols MUST support
   Point to Point, Point to Multipoint and Multipoint to Point routing.
   However, the highly correlated, repetitive use of particular traffic
   patterns will typically allow routing protocols to optimize for very
   common simple cases.

4.8.  Partial Information

   The density of connectivity varies dramatically from long nearly-
   linear structures (e.g., over a transect of land, a bridge or a road)
   to extremely dense collections in a single RF 'cell' (e.g., parcels
   on a dock or containers in transport).  Thus, routing protocols and
   addressing SHOULD avoid placing arbitrary limits on the underlying
   connection topology.  Conversely, routing with partial information is
   an important property in L2Ns as it facilitates scaling down of the

Culler & Vasseur         Expires January 8, 2008                [Page 8]

Internet-Draft      draft-culler-rl2n-routing-reqs-01          July 2007

   node or scaling up of the network to points where algorithmic
   concepts such "all 1-hop neighbors", "all 2-hop neighbors", all
   nodes, or all pairs may not be representable with the resources
   available per node.

4.9.  Multi-topology Routing

   Multi-topology Routing (MTR) is also important to consider both with
   the goal of improving service where it is desirable, but in reducing
   effort where service requirements are lax.  Although many L2Ns use
   initially provide fairly latency in-sensitive monitoring, many
   applications have emerged that require timely delivery of the vast
   majority of the readings, eventual delivery of the remainder, time-
   sensitive delivery of alarms, and/or increasing predictability for
   soft and moderately real-time.

   These issues impact path selection and path quality optimization, as
   well as the impact of protocol and route maintenance traffic on data
   traffic, especially during times of critical physical change.  Thus,
   the mix of applications with a wide range of requirements in term of
   path quality leads to the requirements for MTR.

4.10.  Data Aware routing

   Ultimately, scalability may benefit from the ability to perform
   computations for data reduction or fusion within the network, not
   just at the data processing sink level.  The most common case being
   aggregation along a dynamically computed path to a sink.

   Thus the routing protocol MUST take points of aggregation (another
   node capability) into account when calculating routes.

5.  Relationship with other Routing Protocols

   This family of unique characteristics pose unique routing challenges.
   At the same time, these challenges have deep similarities (and
   substantial points of difference) with several other IETF routing
   protocols.  Like MANET, the interconnection topology over which
   routing is performed must, in general, be deduced from observed
   communication events, in addition to physical wiring or explicit
   configuration.  This topology may be static or dynamic, depending on
   physical conditions.  However, the routing state, neighbor table
   size, and cache state per node will in many cases be highly
   constrained.  Devices themselves have important structure and
   characteristics, as many are stationary and some are unconstrained.

   In general, the average bandwidth and power demand per node should

Culler & Vasseur         Expires January 8, 2008                [Page 9]

Internet-Draft      draft-culler-rl2n-routing-reqs-01          July 2007

   stay bounded and not grow unreasonably with the size of a network.
   Thus, it may be unacceptable to generate unscoped floods, unless the
   frequency of floods per node diminishes with the size of the network.
   In these respects, light footprint routing has much in common with
   IGP.  Effective routing must be carried out in the presence of
   partial (space limited) and somewhat imperfect information.  Note
   that mixed routing protocol may be considered (Distance Vector and
   Link state).  That said, none of the currently available routing
   protocol fulfills the requirement of L2Ns network listed above.
   [I-D.levis-rl2n-overview-protocols]aims at providing an overview
   survey of existing routing protocols.  The aforementioned
   requirements may be conflicting and defining a new routing protocol
   fully satisfying those requirements might be challenging.  The
   objective of this work would be to define a routing protocol that
   will satisfy those requirements as much as possible and that would
   potentially adapt itself to the particular deployment context.

6.  Security Issues


7.  Manageability Issues


8.  IANA Considerations

   This document includes no request to IANA.

9.  Security Considerations


10.  Acknowledgements

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.

Culler & Vasseur         Expires January 8, 2008               [Page 10]

Internet-Draft      draft-culler-rl2n-routing-reqs-01          July 2007

11.2.  Informative References

              Vasseur, J., "Routing Requirement in Low Power and Lossy
              Networks in Home automation  requirements for RL2N-
              routing", draft-brandt-rl2n-home-routing-reqs-00 (work in
              progress), July 2007.

              Montenegro, G., "Transmission of IPv6 Packets over IEEE
              802.15.4 Networks", draft-ietf-6lowpan-format-13 (work in
              progress), April 2007.

              Vasseur, J., "Overview of Existing Wireless Mesh Routing
              Protocols for Low Power and Lossy  Networks",
              draft-levis-rl2n-overview-protocols-00 (work in progress),
              July 2007.

Authors' Addresses

   D Culler
   Arch Rock
   657 Mission St. Suite 600
   San Francisco, CA  94105

   Email: dculler@archrock.com

   JP Vasseur
   Cisco Systems, Inc
   1414 Massachusetts Avenue
   Boxborough, MA  01719

   Email: jpv@cisco.com

Culler & Vasseur         Expires January 8, 2008               [Page 11]

Internet-Draft      draft-culler-rl2n-routing-reqs-01          July 2007

Full Copyright Statement

   Copyright (C) The IETF Trust (2007).

   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

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

   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


   Funding for the RFC Editor function is provided by the IETF
   Administrative Support Activity (IASA).

Culler & Vasseur         Expires January 8, 2008               [Page 12]