6LoWPAN Working Group D. Kaspar
Internet-Draft E. Kim
Expires: January 10, 2008 M. Shin
H. Kim
ETRI
July 9, 2007
Problem Statement, Design Goals and Requirements
for 6LoWPAN Mesh Routing
draft-dokaspar-6lowpan-routreq-02
Status of this Memo
By submitting this Internet-Draft, each author represents that any
applicable patent or other IPR claims of which he or she is aware
have been or will be disclosed, and any of which he or she becomes
aware will be disclosed, in accordance with Section 6 of BCP 79.
Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF), its areas, and its working groups. Note that
other groups may also distribute working documents as Internet-
Drafts.
Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress."
The list of current Internet-Drafts can be accessed at
http://www.ietf.org/ietf/1id-abstracts.txt.
The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html.
This Internet-Draft will expire on January 10, 2008.
Copyright Notice
Copyright (C) The IETF Trust (2007).
Kaspar, et al. Expires January 10, 2008 [Page 1]
Internet-Draft 6LoWPAN Mesh Routing Requirements July 2007
Abstract
This document provides the problem statement for mesh routing below
the IP layer (in 6LoWPAN's adaptation layer). It also defines major
design goals and requirements for 6LoWPAN mesh routing considering
the low-power characteristics of the network and its devices.
Table of Contents
1. Problem Statement . . . . . . . . . . . . . . . . . . . . . . 3
2. Scenario Considerations . . . . . . . . . . . . . . . . . . . 6
3. LoWPAN Mesh Routing Design Goals . . . . . . . . . . . . . . . 8
3.1. Power Conservation . . . . . . . . . . . . . . . . . . . . 8
3.2. Low Protocol Complexity . . . . . . . . . . . . . . . . . 9
3.3. Reliability . . . . . . . . . . . . . . . . . . . . . . . 10
3.4. Mobility . . . . . . . . . . . . . . . . . . . . . . . . . 10
3.5. Security . . . . . . . . . . . . . . . . . . . . . . . . . 10
4. Requirements . . . . . . . . . . . . . . . . . . . . . . . . . 11
5. Security Considerations . . . . . . . . . . . . . . . . . . . 13
6. References . . . . . . . . . . . . . . . . . . . . . . . . . . 14
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 15
Intellectual Property and Copyright Statements . . . . . . . . . . 16
Kaspar, et al. Expires January 10, 2008 [Page 2]
Internet-Draft 6LoWPAN Mesh Routing Requirements July 2007
1. Problem Statement
Low-power wireless personal area networks (LoWPANs) are formed by
devices complying to the IEEE 802.15.4 standard [1]. LoWPAN devices
are distinguished by their low bandwidth, short range, scarce memory
capacity, limited processing capability and other attributes of
inexpensive hardware. In this document, the characteristics of nodes
participating in LoWPANs are assumed to be those described in [2].
IEEE 802.15.4 networks support star and mesh topologies and consist
of two different device types: reduced-function devices (RFDs) and
full-function devices (FFDs). RFDs have the most limited
capabilities and are intended to perform only simple and basic tasks.
RFDs may only associate with a single FFD at a time, but FFDs may
form arbitrary topologies and accomplish more advanced functions,
such as multi-hop routing.
However, neither the IEEE 802.15.4 standard nor the 6LoWPAN format
specification ("IPv6 over IEEE 802.15.4" [3]) provide any information
as to how mesh topologies could be obtained and maintained. Routing
in mesh networks has been the subject of much research, also in the
IETF. A number of experimental protocols have been developed in the
Mobile Ad-hoc Networks (MANET) working group, such as AODV [7], OLSR
[8], or DYMO [9]. However, the modification/simplification of
existing routing protocols may be required for mesh routing to be
feasible in a LoWPAN domain, because more stringent requirements
apply to LoWPANs than to higher performance networks. LoWPAN nodes
are characterized by much lower power supplies, smaller memory sizes,
and lower processing power, which creates new challenges on obtaining
robust and reliable mesh routing within LoWPANs.
The 6LoWPAN problem statement document ("6LoWPAN Problems and Goals"
[2]) briefly mentions four requirements on routing protocols; (a) low
overhead on data packets, (b) low routing overhead, (c) minimal
memory computation, and (d) support for sleeping nodes considering
battery saving. These four high-level requirements only describe the
need for low overhead and power saving. But, based on the
fundamental features of LoWPAN, more detailed routing requirements
are presented in this document, which can lead to further analysis
and protocol design.
The target of this document is mesh routing in the adaptation layer
defined by the 6lowpan format document ("IPv6 over IEEE 802.15.4"
[3]), while other efforts in the IETF concentrate on IP-layer routing
for LoWPANs, such as the MANET working group and the current "RSN"
mailing list. The most significant difference is that "mesh under"
routing is directly based on the IEEE 802.15.4 standard, therefore
using (64-bit or 16-bit shortened) MAC addresses, instead of IP
Kaspar, et al. Expires January 10, 2008 [Page 3]
Internet-Draft 6LoWPAN Mesh Routing Requirements July 2007
addresses. On the Network Layer (L3), a LoWPAN is seen as a single
IP link. In case an existing L3 routing mechanism is to be applied
to a LoWPAN, it must support this addressing scheme. Additionally,
because of the low-performance characteristics of LoWPANs, a light-
weight routing protocol must be produced that meets the design goals
and requirements presented in this document.
Figure 1 shows the place of 6LoWPAN mesh routing in the entire
network stack;
+-------------------------------+
| Application Layer |
+-------------------------------+
| Transport Layer (TCP/UDP) |
+-------------------------------+
| Network Layer (IPv6) |
+-------------------------------+
| 6LoWPAN +---------+ |
| Adaptation | Routing | |
| Layer +---------+ |
+-------------------------------+
| IEEE 802.15.4 (MAC) |
+-------------------------------+
| IEEE 802.15.4 (PHY) |
+-------------------------------+
Figure 1
In order to avoid packet fragmentation and the overhead for
reassembly, all data to be transmitted should fit into a single IEEE
802.15.4 physical frame, as shown in Figure 2.
Routing control packets are placed after the 6LoWPAN Dispatch.
Multiple routing protocols can be supported by the usage of different
Dispatch bit sequences.
Kaspar, et al. Expires January 10, 2008 [Page 4]
Internet-Draft 6LoWPAN Mesh Routing Requirements July 2007
Figure 2 shows the place of 6LoWPAN mechanisms, such as mesh routing
control packets, in the big picture of a IEEE 802.15.4 physical
frame;
|<---------------------- PHY Protocol Data Unit -------------------->|
|<----------- MAC Protocol Data Unit -------------------->|
|<-- Adaptation Layer --->|
+----------+--------+----------+--------------+----+-----+-----+-----+
| PHY | MAC | 6LoWPAN | 6LoWPAN | | | | MAC |
| Preamble | Header | Dispatch | Mechanism | IP | UDP | App | FCS |
| & Header | | | (w/HC, etc.) | | | | |
+----------+--------+----------+--------------+----+-----+-----+-----+
|<---6---->|<-------------------- 125 octets ----------------->|<-2->|
Figure 2
In summary, the main problems of mesh routing in LoWPANs are:
1. Existing routing solutions do not operate in 6LoWPAN's adaptation
layer (and do not support the addressing scheme defined by IEEE
802.15.4)
2. The precise 6LoWPAN routing requirements must be defined.
3. It needs to be clarified how existing routing solutions can be
adapted to meet the low-power requirements presented in
Section 4.
Kaspar, et al. Expires January 10, 2008 [Page 5]
Internet-Draft 6LoWPAN Mesh Routing Requirements July 2007
2. Scenario Considerations
IP-based low-power WPAN technology is still in its early stage of
development, but the range of conceivable usage scenarios is
tremendous. The numerous possible applications of sensor networks
make it obvious that mesh topologies will be prevalent in LoWPAN
environments and routing will be a necessity for expedient
communication. Research efforts in the area of sensor networking
have put forth a large variety of multi-hop routing algorithms [4].
Most related work focuses on optimizing routing for specific
application scenarios, which can largely be categorized into the
following models of communication:
o Flooding (may be optimal in very small networks)
o Data-aware routing (dissemination vs. gathering)
o Event-driven vs. query-based routing
o Geographic routing
Depending on the topology of a LoWPAN and the application(s) running
over it, these different types of routing may be used. However, this
draft abstracts from application-specific communication and fetches
general routing requirements valid for any type of routing in
LoWPANs.
In general, the requirements on a routing protocol are depending on
the network architecture, the hardware parameters of the
participating nodes and the properties of the network as a whole;
a. Network Properties:
* Device Number, Density and Network Diameter:
These parameters directly affect the routing state (e.g. the
number of entries in a routing table or neighbor list).
Especially in large and dense networks, policies must be
applied for discarding "low-quality" routing entries in order
to prevent memory overflow.
* Connectivity:
Due to external factors or programmed disconnections, a LoWPAN
can be in several states of connectivity; anything in the
range from "always connected" to "rarely connected". This
poses great challenges to the dynamic discovery of routes
across a LoWPAN.
Kaspar, et al. Expires January 10, 2008 [Page 6]
Internet-Draft 6LoWPAN Mesh Routing Requirements July 2007
* Mobility:
Location changes can be induced by unpredictable external
factors or by controlled motion, which may in turn cause route
changes. The routing state and the volume of control messages
is heavily dependent on the number of moving nodes in a LoWPAN
and their speed.
* Deployment:
In a LoWPAN, it is possible for nodes to be scattered randomly
or to be deployed in an organized manner. The deployment can
occur at once, or as an iterative process, which may also
affect the routing state.
* Network Architecture, Topology and Applications:
The design of a LoWPAN and the requirements on its application
have a big impact on the most efficient routing type to be
used (data-aware routing, geographic routing, ...).
b. Node Parameters:
* Processing Speed and Memory Size:
These basic parameters define the maximum size of the routing
state.
* Power Consumption and Power Source:
The number and topology of battery- and mains-powered nodes in
a LoWPAN affect routing protocols in their selection of
optimal paths for network lifetime maximization.
* Transmission Range, Rate and Bandwidth:
These parameters indirectly affect routing. For example, a
high transmission range may cause a dense network, which in
turn results in more direct neighbors of a node and a larger
routing state.
Kaspar, et al. Expires January 10, 2008 [Page 7]
Internet-Draft 6LoWPAN Mesh Routing Requirements July 2007
3. LoWPAN Mesh Routing Design Goals
This section outlines the fundamental design goals, which serve to
define the issues and to impose a list of requirements for
forthcoming LoWPAN routing solutions. The general design goals for
routing are to provide a loop-free, layer-transparent, robust, and
scalable solution. Based on these fundamental routing goals, this
section describes special features and goals concerning LoWPAN
routing design. LoWPANs have two unique properties to consider;
o Power conservation: some devices are mains-powered, but most are
battery-operated and need to last several months to a few years
with a single AA battery (see Section 3.1).
o Low performance: tiny devices, memory sizes, processors, etc. (see
Section 3.2).
These fundamental features of LoWPANs can affect the design of
routing solutions, so that existing routing specifications should be
simplified and modified to the smallest extent possible, in order to
fit the low-power requirements of LoWPANs.
3.1. Power Conservation
Saving energy is crucially important to LoWPAN devices that are not
mains-powered but have to rely on a depleting source, such as a
battery. The lifetime of a LoWPAN node depends on the energy it can
store and harvest. Power-aware routing is a non-trivial task,
because it is affected by many mutually conflicting goals;
o Minimization of total energy consumed in the network
o Maximization of the time until a network partition occurs
o Minimizing the energy variance at each node
o Minimizing the cost per packet
Compared to functions such as computational operations or taking
sensor samples, radio communications is by far the dominant factor of
power consumption [10]. Therefore, optimization of mesh routing
protocols in terms of achieving a minimal number of control messages
is essential for the longevity of battery-powered nodes. Routing
overhead must be minimized in order to prevent fragmentation of
frames on the physical layer (PHY), reducing the energy required for
transmission and preventing the need for packet reassembly.
In order to find energy-optimal routing paths, LoWPAN mesh routing
Kaspar, et al. Expires January 10, 2008 [Page 8]
Internet-Draft 6LoWPAN Mesh Routing Requirements July 2007
protocols should minimize power consumption by utilizing a
combination of the link quality indication (LQI) provided by the MAC
layer and other measures, such as hop count. Route repair and route
error messages should be avoided for minimizing the overall number of
control messages and the required energy for sending them.
Neighbor discovery is a major precondition to allow routing in a
network. Especially in a low-power environment, where nodes might be
in periodic sleeping states, it is difficult to define whether a node
is a neighbor of another or not. In addition to that, LoWPAN devices
must be very economical in terms of power consumption and should
avoid sending "Hello" messages. Instead, link layer mechanisms (such
as acknowledgments or beacon responses) should be utilized to keep
track of active neighbors. Neighbor discovery for LoWPANs is
described more detailed in [6].
Transparent IP routing between LoWPAN domains and higher layer
networks must be provided bidirectionally. A LoWPAN mesh routing
protocol must allow for gateways to forward packets out of the local
domain and it must be possible to query a LoWPAN device from outside
of the local domain. Strategies must be considered to avoid battery
depletion of nodes by too many queries from higher level networks.
End-to-end communication is not a design goal of LoWPAN.
3.2. Low Protocol Complexity
A routing protocol of low complexity certainly assists to achieve the
previously described goal of reducing power consumption. However,
this section's focus is on designing a LoWPAN protocol that is
robust, easy to analyze and implicitly less prone to security
attacks. A LoWPAN routing protocol solution should consider the
limited memory size and computation capabilities of participating
devices. And even though implementation details are out of IETF
scope, due to the hardware restrictions of LoWPAN devices, code
length should be considered to fit within their small memory size.
Because network layer routing imposes too much overhead for LoWPANs
and link layer techniques are out of scope of IETF, LoWPAN mesh
routing should be performed within the adaptation layer defined in
[3]. Both addressing modes provided by the IEEE 802.15.4 standard,
16-bit short addresses and 64-bit extended addresses, must be
considered by LoWPAN mesh routing protocols. It is also assumed that
nodes participating in LoWPAN mesh routing are assigned only a single
address/identifier and do not support multiple interfaces.
A LoWPAN routing protocol should be designed to minimize the required
memory size, computational and algorithmical complexity. Possible
techniques might include the reduction of routing tables or omission
Kaspar, et al. Expires January 10, 2008 [Page 9]
Internet-Draft 6LoWPAN Mesh Routing Requirements July 2007
local repair procedures.
3.3. Reliability
Another important trait of LoWPAN devices is their unreliability due
to limited system capabilities, and also because they might be
closely coupled to the physical world with all its unpredictable
variation, noise, and asynchrony. It is predicted that LoWPANs will
be comprised of significantly higher numbers of devices than counted
in current networks, causing user interaction and maintenance to
become impractical and therefore requiring robustness and self-
healing capabilities in their fundamental network structure. The
design of mesh routing protocols must consider the fact that packets
are to be reliably delivered over a much higher number of hops, too.
Mesh routing must be robust to unreliable nodes. One method for
estimating the reliability of a node is to use the link quality
indication (LQI) provided by the MAC layer in combination with other
metrics.
The required reliability is heavily dependent on the individual
application scenario and the LoWPAN architecture.
3.4. Mobility
Routing must be functional both in fixed and dynamically adaptive
topologies. Mesh networks are likely to consist of nodes with a
certain degree of mobility. Due to the low performance
characteristics of LoWPAN devices, mobility support should be
provided for unmodified nodes. Fast mobility detection will be a
huge challenge and LoWPAN nodes might even change their location
while being in state of hibernation. Routing must be robust and
remain energy-efficient in all such cases. The detailed mobility
requirements and goals are described in [5]. Also, as recently seen
in discussions related to MANEMO (Network mobility for MANET), a
similar point was stated regarding network mobility in LoWPAN
environments.
The required mobility is heavily dependent on the individual
application scenario and the LoWPAN architecture.
3.5. Security
Security threats within LoWPANs may be different from existing threat
models in ad-hoc network environments. Neighbor Discovery in IEEE
802.15.4 links may be susceptible to threats as listed in RFC3756
[11]. Bootstrapping may also impose additional threats.
Nevertheless, security should not cause significant transmission
overhead.
Kaspar, et al. Expires January 10, 2008 [Page 10]
Internet-Draft 6LoWPAN Mesh Routing Requirements July 2007
4. Requirements
This section lists the requirements on mesh routing protocols for
LoWPANs.
R01: 6LoWPAN routing MUST be performed in the adaptation layer, as
defined in [3].
R02: Both addressing modes, 16-bit short addresses and 64-bit
extended addresses MUST be supported.
R03: Protocol control messages SHOULD not create fragmentation of
physical layer (PHY) layer frames.
R04: 6LoWPAN routing protocols SHOULD keep power consumption at a
minimum. PHY/MAC-layer indicators (such as LQI) SHOULD be matched
with other metrics (such as hop count) for route decisions.
R05: Routing solutions SHOULD be simple and of low computational
complexity.
R05.1: Operation with low routing state (such as routing tables
and neighbor lists) SHOULD be maintained. For example, devices
may have only 32 forwarding entries available.
R05.2: Routing tables and neighbor lists SHOULD support 16-bit
short and 64-bit extended addresses.
R05.3: Code length SHOULD be considered to fit within LoWPAN
devices' small memory size.
R06: 6LoWPAN routing protocols MUST be loop-free.
R07: For neighbor discovery, 6LoWPAN devices SHOULD avoid sending
"Hello" messages. Instead, link-layer mechanisms (such as
acknowledgments or beacon responses) SHOULD be utilized to keep
track of active neighbors.
R08: 6LoWPAN routing protocols SHOULD be robust and SHOULD work
independent of unresponsive nodes.
R09: The solution SHOULD allow for dynamically adaptive topologies
and nodes changing their location.
R10: The routing solution(s) SHOULD be scalable.
R11: The procedure of local repair and related control messages
for intermediate nodes MAY be omitted.
Kaspar, et al. Expires January 10, 2008 [Page 11]
Internet-Draft 6LoWPAN Mesh Routing Requirements July 2007
R12: Protocol control messages MAY be secured.
R13: A 6loWPAN routing protocol MAY allow for gateways to forward
packets out of the local domain and it MAY be possible to query a
6LoWPAN device from outside of the local domain.
Kaspar, et al. Expires January 10, 2008 [Page 12]
Internet-Draft 6LoWPAN Mesh Routing Requirements July 2007
5. Security Considerations
Security issues are handled as described in Section 3.5
Kaspar, et al. Expires January 10, 2008 [Page 13]
Internet-Draft 6LoWPAN Mesh Routing Requirements July 2007
6. References
[1] IEEE Computer Society, "IEEE Std. 802.15.4-2003", October 2003.
[2] Kushalnagar, N., Montenegro, G., and C. Schumacher, "6LoWPAN:
Overview, Assumptions, Problem Statement and Goals,
draft-ietf-6lowpan-problem-08 (work in progress)",
February 2007.
[3] Montenegro, G., Kushalnagar, N., Hui, J., and D. Culler,
"Transmission of IPv6 Packets over IEEE 802.15.4 Networks,
draft-ietf-6lowpan-format-13 (work in progress)", October 2005.
[4] Bulusu, N. and S. Jha, "Wireless Sensor Networks", July 2005.
[5] Chakrabarti, S. and S. Daniel Park, "LoWPAN Mobility
Requirements and Goals, draft-chakrabarti-mobopts-lowpan-req-01
(work in progress)", March 2007.
[6] Chakrabarti, S. and E. Nordmark, "LoWPAN Neighbor Discovery
Extensions, draft-chakrabarti-6lowpan-ipv6-nd-03 (work in
progress)", March 2007.
[7] Perkins, C., Belding-Royer, E., and S. Das, "Ad hoc On-Demand
Distance Vector (AODV) Routing", RFC 3561, July 2003.
[8] Clausen, T. and P. Jacquet, "Optimized Link State Routing
Protocol (OLSR)", RFC 3626, October 2003.
[9] Chakeres, I., "Dynamic MANET On-demand (DYMO) Routing,
draft-ietf-manet-dymo-06 (work in progress)", June 2005.
[10] Pfister, K. and B. Boser, "Smart Dust: Wireless Networks of
Millimeter-Scale Sensor Nodes".
[11] Nikander, P., Kempf, J., and E. Nordmark, "IPv6 Neighbor
Discovery (ND) Trust Models and Threats", RFC 3756, May 2004.
Kaspar, et al. Expires January 10, 2008 [Page 14]
Internet-Draft 6LoWPAN Mesh Routing Requirements July 2007
Authors' Addresses
Dominik Kaspar
ETRI
161 Gajeong-dong
Yuseong-gu
Daejeon 305-700
Korea
Phone: +82-42-860-1072
Email: dominik@etri.re.kr
Eunsook Kim
ETRI
161 Gajeong-dong
Yuseong-gu
Daejeon 305-700
Korea
Phone: +82-42-860-6124
Email: eunah@etri.re.kr
Myungki Shin
ETRI
161 Gajeong-dong
Yuseong-gu
Daejeon 305-700
Korea
Phone: +82-42-860-4847
Email: mkshin@etri.re.kr
Hyoungjun Kim
ETRI
161 Gajeong-dong
Yuseong-gu
Daejeon 305-700
Korea
Phone: +82-42-860-6576
Email: hjk@etri.re.kr
Kaspar, et al. Expires January 10, 2008 [Page 15]
Internet-Draft 6LoWPAN Mesh Routing Requirements 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
"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).
Kaspar, et al. Expires January 10, 2008 [Page 16]