One document matched: draft-culler-rsn-routing-reqs-00.txt

Networking Working Group                                  D. Culler, Ed.
Internet-Draft                                 Arch Rock (& UC Berkeley)
Intended status: Informational                          JP. Vasseur, Ed.
Expires: October 14, 2007                             Cisco Systems, Inc
                                                          April 12, 2007


                Routing Requirements for Sensor Networks
                  draft-culler-rsn-routing-reqs-00.txt

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 October 14, 2007.

Copyright Notice

   Copyright (C) The IETF Trust (2007).

Abstract

   The need for high quality routing for 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 and proprietary routing protocols



Culler & Vasseur        Expires October 14, 2007                [Page 1]

Internet-Draft    draft-culler-rsn-routing-reqs-00.txt        April 2007


   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",
   "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
   document are to be interpreted as described in RFC 2119 [RFC2119].


Table of Contents

   1.  Introduction  . . . . . . . . . . . . . . . . . . . . . . . . . 3
   2.  Unique Routing Requirements of Sensor Networks  . . . . . . . . 3
     2.1.  Spatially-Driven Multihop . . . . . . . . . . . . . . . . . 3
     2.2.  Light Footprint . . . . . . . . . . . . . . . . . . . . . . 4
     2.3.  Small MTU . . . . . . . . . . . . . . . . . . . . . . . . . 4
     2.4.  Deep power management . . . . . . . . . . . . . . . . . . . 4
     2.5.  Heterogeneous Capabilities  . . . . . . . . . . . . . . . . 5
     2.6.  Highly Variable Connectivity  . . . . . . . . . . . . . . . 5
     2.7.  Structured Workload and Traffic Pattern . . . . . . . . . . 6
     2.8.  Partial Information . . . . . . . . . . . . . . . . . . . . 6
     2.9.  Quality of Service Capable Routing  . . . . . . . . . . . . 6
     2.10. Date Aware routing  . . . . . . . . . . . . . . . . . . . . 7
   3.  Relationship with other Routing Protocols . . . . . . . . . . . 7
   4.  IANA Considerations . . . . . . . . . . . . . . . . . . . . . . 8
   5.  Security Considerations . . . . . . . . . . . . . . . . . . . . 8
   6.  Manageability Considerations  . . . . . . . . . . . . . . . . . 8
   7.  Acknowledgements  . . . . . . . . . . . . . . . . . . . . . . . 8
   8.  References  . . . . . . . . . . . . . . . . . . . . . . . . . . 8
     8.1.  Normative References  . . . . . . . . . . . . . . . . . . . 8
     8.2.  Informative References  . . . . . . . . . . . . . . . . . . 8
   Authors' Addresses  . . . . . . . . . . . . . . . . . . . . . . . . 8
   Intellectual Property and Copyright Statements  . . . . . . . . . . 9














Culler & Vasseur        Expires October 14, 2007                [Page 2]

Internet-Draft    draft-culler-rsn-routing-reqs-00.txt        April 2007


1.  Introduction

   The need for high quality routing for Sensor networks comprised of
   highly constrained devices (CPU, memory, ...) in a potentially
   variable wireless environment 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 and proprietary routing
   protocols as well as several industrial forums that have emerged over
   the IEEE 802.15.4 link and various proprietary links.

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

   Considering the variety of Sensor 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.


2.  Unique Routing Requirements of Sensor Networks

   Sensor networks present a variety of unique routing requirements
   driven partly by implementation technology constraints, partly by the
   domain of usage, and partly by application characteristics.

2.1.  Spatially-Driven Multihop

   The low transmission power of PAN (Personal Area Network) radios
   implies that the range is relatively short; multiple hops are
   required to achieve communication over greater distances.  Variously
   referred to as mesh or multihop routing, such multihop routing
   communication is important from a basic energy viewpoint.  The energy
   cost to traverse a given distance with 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.  Moderate 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



Culler & Vasseur        Expires October 14, 2007                [Page 3]

Internet-Draft    draft-culler-rsn-routing-reqs-00.txt        April 2007


   retransmission as well as spatial diversity through multiple
   receivers, i.e., multipath routing.

2.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
   state, including neighbor tables, link estimators, sequence number
   and other caches.

2.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.

2.4.   Deep power management

   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.  Few
   routing protocols anticipate that the devices have their network link
   off most of the time.




Culler & Vasseur        Expires October 14, 2007                [Page 4]

Internet-Draft    draft-culler-rsn-routing-reqs-00.txt        April 2007


2.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 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
   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.

2.6.   Highly Variable Connectivity

   In many use cases for low power wireless devices, mobility is a
   central element.  However, this is often structured mobility, such as
   mobile devices moving through a stationary network of similar
   devices, or collections of devices moving together as a network.
   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 most extreme variations in 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 contrained devices so as to save energy.




Culler & Vasseur        Expires October 14, 2007                [Page 5]

Internet-Draft    draft-culler-rsn-routing-reqs-00.txt        April 2007


2.7.  Structured Workload and Traffic Pattern

   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.

2.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 the sensor network as it facilitates scaling
   down of the node or scaling up of the 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.

2.9.  Quality of Service Capable Routing

   QoS (Quality of Service) capable routing is also important to
   consider.  Although many WSN uses 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



Culler & Vasseur        Expires October 14, 2007                [Page 6]

Internet-Draft    draft-culler-rsn-routing-reqs-00.txt        April 2007


   path quality leads to the potential requirements for QoS-aware
   routing.

   Consequently, the routing protocol MUST support multi-topology
   routing in one form or another with different degrees of route
   optimization on a per topology basis.

2.10.  Date 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 SHOULD take points of aggregation (another node
   capability) into account when calculating routes.


3.  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
   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 Sensor Networks network listed
   above.

   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.



Culler & Vasseur        Expires October 14, 2007                [Page 7]

Internet-Draft    draft-culler-rsn-routing-reqs-00.txt        April 2007


4.  IANA Considerations

   This memo includes no request to IANA.


5.  Security Considerations

   TBD.


6.  Manageability Considerations

   TBD.


7.  Acknowledgements


8.  References

8.1.  Normative References

   [RFC2119]  Bradner, S., "Key words for use in RFCs to Indicate
              Requirement Levels", BCP 14, RFC 2119, March 1997.

8.2.  Informative References


Authors' Addresses

   David Culler (editor)
   Arch Rock (& UC Berkeley)
   657 Mission St. Suite 600
   San Francisco, CA  94105
   USA

   Email: dculler@archrock.com


   JP Vasseur (editor)
   Cisco Systems, Inc
   1414 Massachusetts Avenue
   Boxborough, MA  01719
   USA

   Email: jpv@cisco.com





Culler & Vasseur        Expires October 14, 2007                [Page 8]

Internet-Draft    draft-culler-rsn-routing-reqs-00.txt        April 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
   "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.


Acknowledgment

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





Culler & Vasseur        Expires October 14, 2007                [Page 9]