Networking Working Group D. Culler, Ed.
Internet-Draft Arch Rock (& UC Berkeley)
Intended status: Informational JP. Vasseur, Ed.
Expires: December 31, 2007 Cisco Systems, Inc
June 29, 2007
Routing Requirements for Low-Power Wireless Networks
draft-culler-rl2n-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 December 31, 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 December 31, 2007 [Page 1]
Internet-Draft draft-culler-rl2n-routing-reqs-00.txt June 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 Low Power Wireless Networks . . 3
2.1. Spatially-Driven Multihop . . . . . . . . . . . . . . . . 3
2.2. Light Footprint . . . . . . . . . . . . . . . . . . . . . 4
2.3. Small MTU . . . . . . . . . . . . . . . . . . . . . . . . 5
2.4. Deep power management . . . . . . . . . . . . . . . . . . 5
2.5. Heterogeneous Capabilities . . . . . . . . . . . . . . . . 6
2.6. Highly Variable Connectivity . . . . . . . . . . . . . . . 6
2.7. Structured Workload and Traffic Pattern . . . . . . . . . 7
2.8. Partial Information . . . . . . . . . . . . . . . . . . . 8
2.9. Quality of Service Capable Routing . . . . . . . . . . . . 8
2.10. Date Aware routing . . . . . . . . . . . . . . . . . . . . 8
3. Relationship with other Routing Protocols . . . . . . . . . . 8
4. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 9
5. Security Considerations . . . . . . . . . . . . . . . . . . . 9
6. Manageability Considerations . . . . . . . . . . . . . . . . . 9
7. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 9
8. References . . . . . . . . . . . . . . . . . . . . . . . . . . 10
8.1. Normative References . . . . . . . . . . . . . . . . . . . 10
8.2. Informative References . . . . . . . . . . . . . . . . . . 10
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 10
Intellectual Property and Copyright Statements . . . . . . . . . . 11
Culler & Vasseur Expires December 31, 2007 [Page 2]
Internet-Draft draft-culler-rl2n-routing-reqs-00.txt June 2007
1. 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 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.
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
low power wireless networks 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.
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 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.
2. Unique Routing Requirements of Low Power Wireless Networks
Sensor networks and related networks of low-power, emebedded devices
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.
2.1. Spatially-Driven Multihop
The low transmission power of PAN (Personal Area Network) radios, as
typically defined by the collection of IEEE 802.15 links, implies
Culler & Vasseur Expires December 31, 2007 [Page 3]
Internet-Draft draft-culler-rl2n-routing-reqs-00.txt June 2007
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 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 links.
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
equivalent of a single IP link and only within the context of stacks
vertically integrated from phy to application with no provisions for
routing to other kinds of links.
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
Culler & Vasseur Expires December 31, 2007 [Page 4]
Internet-Draft draft-culler-rl2n-routing-reqs-00.txt June 2007
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. 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.
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 characterstics. 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
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. For
example, protocols involving the exchange of lists of all 1-hop or
all 2-hop nighbors 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.
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,
Culler & Vasseur Expires December 31, 2007 [Page 5]
Internet-Draft draft-culler-rl2n-routing-reqs-00.txt June 2007
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
forwarding (and for route maintainence) 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.
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, 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.
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
Culler & Vasseur Expires December 31, 2007 [Page 6]
Internet-Draft draft-culler-rl2n-routing-reqs-00.txt June 2007
through a stationary network of similar devices, or collections of
devices moving together as a network.
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.
2.7. Structured Workload and Traffic Pattern
The above characteristics suggest that effective general-purpose
routing for low-power wireless networks 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 should 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.
Culler & Vasseur Expires December 31, 2007 [Page 7]
Internet-Draft draft-culler-rl2n-routing-reqs-00.txt June 2007
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 both with the goal of improving service where it is is
desirable, but in reducing effort where service requirements are lax.
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 path
quality leads to the potential requirements for QoS-aware routing.
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
Culler & Vasseur Expires December 31, 2007 [Page 8]
Internet-Draft draft-culler-rl2n-routing-reqs-00.txt June 2007
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.
4. IANA Considerations
This memo includes no request to IANA.
5. Security Considerations
TBD.
6. Manageability Considerations
TBD.
7. Acknowledgements
8. References
Culler & Vasseur Expires December 31, 2007 [Page 9]
Internet-Draft draft-culler-rl2n-routing-reqs-00.txt June 2007
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 December 31, 2007 [Page 10]
Internet-Draft draft-culler-rl2n-routing-reqs-00.txt June 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 December 31, 2007 [Page 11]