TOC 
6LoWPAN Working GroupE. Kim
Internet-DraftETRI
Expires: September 10, 2009D. Kaspar
 Simula Research Laboratory
 C. Gomez
 Tech. Univ. of Catalonia/i2CAT
 C. Bormann
 Universität Bremen TZI
 March 09, 2009


Problem Statement and Requirements for 6LoWPAN Routing
draft-ietf-6lowpan-routing-requirements-01

Status of this Memo

This Internet-Draft is submitted to IETF in full conformance with the provisions of BCP 78 and BCP 79.

Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet-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 September 10, 2009.

Copyright Notice

Copyright (c) 2009 IETF Trust and the persons identified as the document authors. All rights reserved.

This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents in effect on the date of publication of this document (http://trustee.ietf.org/license-info). Please review these documents carefully, as they describe your rights and restrictions with respect to this document.

Abstract

This document provides the problem statement for 6LoWPAN routing. It also defines the requirements for 6LoWPAN routing considering IEEE 802.15.4 specificities and the low-power characteristics of the network and its devices.



Table of Contents

1.  Problem Statement
2.  Terminology
3.  Design Space
    3.1.  6LoWPAN Headers for Routing
    3.2.  Reference Network Model
4.  Scenario Considerations and Parameters for 6LoWPAN Routing
5.  6LoWPAN Routing Requirements
    5.1.  Support of 6LoWPAN Device Properties
    5.2.  Support of 6LoWPAN Link Properties
    5.3.  Support of 6LoWPAN Network Characteristics
    5.4.  Support of Security
    5.5.  Support of Mesh-under Forwarding
6.  Security Considerations
7.  Acknowledgements
8.  References
    8.1.  Normative References
    8.2.  Informative References
§  Authors' Addresses




 TOC 

1.  Problem Statement

In the context of this document, low-power wireless personal area networks (LoWPANs) are formed by devices that are compatible with the IEEE 802.15.4 standard [6] (IEEE Computer Society, “IEEE Std. 802.15.4-2006 (as amended),” 2007.). Most of the LoWPAN devices are distinguished by their low bandwidth, short range, scarce memory capacity, limited processing capability and other attributes of inexpensive hardware. The characteristics of nodes participating in LoWPANs are assumed to be those described in RFC 4919 [3] (Kushalnagar, N., Montenegro, G., and C. Schumacher, “IPv6 over Low-Power Wireless Personal Area Networks (6LoWPANs): Overview, Assumptions, Problem Statement, and Goals,” August 2007.).

IEEE 802.15.4 networks support star and mesh topologies. However, neither the IEEE 802.15.4 standard nor the 6LoWPAN format specification ("IPv6 over IEEE 802.15.4" [4] (Montenegro, G., Kushalnagar, N., Hui, J., and D. Culler, “Transmission of IPv6 Packets over IEEE 802.15.4 Networks,” September 2007.)) define how mesh topologies could be obtained and maintained. Thus, the 6LoWPAN formation and multi-hop routing should be supported by higher layers, either the 6LoWPAN adaptation layer or the IP layer. A number of IP routing protocols have been developed in various IETF working groups. However, these existing routing protocols may not satisfy the requirements of multi-hop routing in 6LoWPANs, for the following reasons:

This creates new challenges on obtaining robust and reliable routing within LoWPANs.

The 6LoWPAN problem statement document ("6LoWPAN Problems and Goals" [3] (Kushalnagar, N., Montenegro, G., and C. Schumacher, “IPv6 over Low-Power Wireless Personal Area Networks (6LoWPANs): Overview, Assumptions, Problem Statement, and Goals,” August 2007.)) briefly mentions four requirements on routing protocols;

(a) low overhead on data packets

(b) low routing overhead

(c) minimal memory and computation requirements

(d) support for sleeping nodes considering battery saving

These four high-level requirements describe the basic need for 6LoWPAN routing. Based on the fundamental features of 6LoWPAN, more detailed routing requirements are presented in this document, which can lead to further analysis and protocol design.

Using the 6LoWPAN header format [4] (Montenegro, G., Kushalnagar, N., Hui, J., and D. Culler, “Transmission of IPv6 Packets over IEEE 802.15.4 Networks,” September 2007.), there are two layers routing protocols can be defined at, commonly referred to as "Mesh Under" and "Route Over". The Mesh Under approach supports routing under the IP link and is directly based on the link-layer IEEE 802.15.4 standard in 6LoWPAN, therefore using (64-bit or 16-bit short) MAC addresses. On the other hand, the Route Over approach relies on IP routing and therefore supports routing over possibly various types of interconnected links (see also Figure 1 (Mesh-under (left) and route-over routing (right))). Most statements in this document consider both the Mesh Under and Route Over cases.
Note: The ROLL WG is now working on Route Over approaches for Low power and Lossy Networks (LLNs), not specifically for 6LoWPAN. This document is focused on 6LoWPAN-specific requirements, in alignment with the ROLL WG.

Considering the problems above, detailed 6LoWPAN routing requirements must be defined. Application-specific features affect the design of 6LoWPAN routing requirements and the corresponding solutions. However, various applications can be profiled by similar technical characteristics, although the related detailed requirements might differ (e.g., a few dozens of nodes for home lighting system need appropriate scalability for the applications, while billions of nodes for a highway infrastructure system also need appropriate scalability). This document states the routing requirements of 6LoWPAN applications in general, while trying to give examples for different cases of routing. This routing requirements document does not imply that a single routing solution may be the best one for all 6LoWPAN applications.



 TOC 

2.  Terminology

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 [1] (Bradner, S., “Key words for use in RFCs to Indicate Requirement Levels,” March 1997.).

Readers are expected to be familiar with all the terms and concepts that are discussed in "IPv6 over Low-Power Wireless Personal Area Networks (6LoWPANs): Overview, Assumptions, Problem Statement, and Goals" (Kushalnagar, N., Montenegro, G., and C. Schumacher, “IPv6 over Low-Power Wireless Personal Area Networks (6LoWPANs): Overview, Assumptions, Problem Statement, and Goals,” August 2007.) [3], and " Transmission of IPv6 Packets over IEEE 802.15.4 Networks" (Montenegro, G., Kushalnagar, N., Hui, J., and D. Culler, “Transmission of IPv6 Packets over IEEE 802.15.4 Networks,” September 2007.) [4].

This document defines additional terms:

LoWPAN Coordinator Node
A logical functional entity that performs the special role of coordinating its child nodes for local data aggregation, status management of local nodes, etc. Thus, the Coordinator Node does not need to coincide with a link-layer PAN coordinator and there may be multiple instance in a LoWPAN.
LoWPAN Mesh Node
A LoWPAN node that forwards data between arbitary source-destination pairs in 6LoWPAN adaptation layer using link address (and thus only exist in Mesh Under LoWPANs). A Mesh Node may also serve as a LoWPAN Host.

Additionally, in alignment with all other 6LoWPAN drafts, this document uses the same terms and definitions as provided by the 6LoWPAN ND draft [8] (Shelby, Z., Thubert, P., Hui, J., Chakrabarti, S., and E. Nordmark, “LoWPAN Neighbor Discovery Extensions, draft-ietf-6lowpan-nd-01 (work in progress),” February 2009.):

LoWPAN Host
A node that only sources or sinks IPv6 datagrams. Referred to as a host in this document. The term node (see LoWPAN Node) is used when the the differentiation between host and router is not important.
LoWPAN Edge Router
An IPv6 router that interconnects the LoWPAN to another network. Referred to as an edge router in this document.
LoWPAN Router
A node that forwards datagrams between arbitrary source-destination pairs using a single 6LoWPAN interface performing IP routing (and thus only exist in route over LoWPANs). A LoWPAN Router may also serve as a LoWPAN Host - both sourcing and sinking IPv6 datagrams. Refered to as a router in 6LoWPAN documents. All LoWPAN Routers perform ND message relay on behalf of other nodes.
LoWPAN Node
A node that composes a LoWPAN. In mesh under, each intermidiate node performs multi-hop forwarding at L2. In route over, each intermidiate node serves as a LoWPAN router performing IP routing.
Mesh Under
A LoWPAN configuration where the link-local scope is defined by the boundaries of the LoWPAN and includes all nodes within. Forwarding and multihop routing functions are achieved at L2 between mesh nodes.
Route Over
A LoWPAN configuration where the link-local scope is defined by those nodes reachable over a single radio transmission. Due to the time-varying characteristics of wireless communication, the neighbor set may change over time even when nodes maintain the same physical locations. Multihop is achieved using IP routing.
Backbone Link
This is an IPv6 link that interconnects two or more edge routers. It is expected to be deployed as a high speed backbone in order to federate a potentially large set of LoWPANs.
Extended LoWPAN
This is the aggregation of multiple LoWPANs as defined in [3] (Kushalnagar, N., Montenegro, G., and C. Schumacher, “IPv6 over Low-Power Wireless Personal Area Networks (6LoWPANs): Overview, Assumptions, Problem Statement, and Goals,” August 2007.) interconnected by a backbone link via Edge Routers and forming a single subnet.
LoWPAN Link
A low-power wireless link which is shared by a link-local scope in a LoWPAN. In a LoWPAN, a link can be a very instable set of nodes, for instance the set of nodes that can receive a packet that is broadcast over the air in a route over LoWPAN, or the set of nodes currently reachable in an L2 mesh in a mesh under LoWPAN. Such a set may vary from one packet to the next as the nodes move or as the radio propagation conditions change.
LoWPAN Subnet
A subnet including a LoWPAN or an Extended LoWPAN, together with the backbone link with the same subnet prefix and prefix length.



 TOC 

3.  Design Space

Apart from a wide variety of routing algorithms possible for 6LoWPAN, the question remains as to whether routing should be performed Mesh Under (in the adaptation layer defined by the 6lowpan format document [4] (Montenegro, G., Kushalnagar, N., Hui, J., and D. Culler, “Transmission of IPv6 Packets over IEEE 802.15.4 Networks,” September 2007.)), or by the IP-layer using a Route Over approach. The most significant consequence of Mesh Under routing is that the inherited stringent characteristics of IEEE 802.15.4 would directly affect the 6LoWPAN routing mechanisms, therefore using (64-bit or 16-bit short) MAC addresses instead of IP addresses, and a 6LoWPAN would be seen as a single IP link. In case a Route Over mechanism is to be applied to a 6LoWPAN it must also support 6LoWPAN's unique properties using global IPv6 addressing.



Figure 1 (Mesh-under (left) and route-over routing (right)) shows the place of 6LoWPAN routing in the entire network stack.

 +-----------------------------+    +-----------------------------+
 |  Application Layer          |    |  Application Layer          |
 +-----------------------------+    +-----------------------------+
 |  Transport Layer (TCP/UDP)  |    |  Transport Layer (TCP/UDP)  |
 +-----------------------------+    +-----------------------------+
 |  Network Layer (IPv6)       |    |  Network       +---------+  |
 +-----------------------------+    |  Layer         | Routing |  |
 |  6LoWPAN       +---------+  |    |  (IPv6)        +---------+  |
 |  Adaptation    | Routing |  |    +-----------------------------+
 |  Layer         +---------+  |    |  6LoWPAN Adaptation Layer   |
 +-----------------------------+    +-----------------------------+
 |  IEEE 802.15.4 (MAC)        |    |  IEEE 802.15.4 (MAC)        |
 +-----------------------------+    +-----------------------------+
 |  IEEE 802.15.4 (PHY)        |    |  IEEE 802.15.4 (PHY)        |
 +-----------------------------+    +-----------------------------+

 Figure 1: Mesh-under (left) and route-over routing (right) 

In order to avoid packet fragmentation and the overhead for reassembly, routing packets should fit into a single IEEE 802.15.4 physical frame and application data should not be expanded to an extent that they no longer fit.



 TOC 

3.1.  6LoWPAN Headers for Routing

In the simplest case for a Mesh Under where predefined layer two forwarding is appropriate, the mesh-header defined in RFC 4944 [4] (Montenegro, G., Kushalnagar, N., Hui, J., and D. Culler, “Transmission of IPv6 Packets over IEEE 802.15.4 Networks,” September 2007.) is sufficient. Frame Delivery in a Link-Layer Mesh is described in the Section 11 in RFC 4944. The mesh type and header defined in RFC 4944 are as follows:



A 6LoWPAN Mesh Header:

                 1                   2                   3
 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 |1 0|V|F|HopsLft| originator address, final address
 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

 Figure 2: 6LoWPAN Mesh Header 

However, the mesh header is not sufficient when it needs full routing functionalities applying more routing metrics and functions. If a Mesh Under routing protocol is built for operation in 6LoWPAN's adaptation layer, routing control packets with MAC addresses are placed after the 6LoWPAN Dispatch. A new Dispatch value is REQUIRED to be assigned for Mesh Under routing. As shown in Figure 3 (6LoWPAN packet format and Mesh Under routing), multiple routing protocols can be supported by the usage of different Dispatch bit sequences.



A 6LoWPAN encapsulated Mesh Under Routing packet:

 +---------------------+----------------+---------+----
 | Dispatch (new val.) | Routing header |   ...
 +---------------------+----------------+---------+----

 Figure 3: 6LoWPAN packet format and Mesh Under routing 

When a Route Over protocol is built over the IPv6 layer, the Dispatch value can be chosen as one of the Dispatch patterns for 6LoWPAN, followed by a compressed or uncompressed IPv6 header, and Route Over routing header will be included in the payload of IPv6 packet.



Figure 4 (6LoWPAN HC1 packet format and Route Over routing) depicts an example of 6LoWPAN encapsulated Route Over routing packets for HC1 defined in RFC 4944:

 +----------------+-------------+------------------------+---
 | Dispatch + HC1 | IPv6 Header | Payload(Routing packet)| ...
 +----------------+-------------+------------------------+---

 Figure 4: 6LoWPAN HC1 packet format and Route Over routing 



Figure 4 (6LoWPAN HC1 packet format and Route Over routing) depicts an example of 6LoWPAN encapsulated Route Over routing packets for IPHC defined in the ongoing packet format work in 6LoWPAN [9] (Hui, J. and P. Thubert, “Compression Format for IPv6 Datagrams in 6LoWPAN Networks, draft-ietf-6lowpan-hc-04 (work in progress),” December 2008.):

 +----------------------+-------------+------------------------+--
 |Dispatch + LOWPAN_IPHC| IPv6 Header | Payload(Routing packet)|...
 +----------------------+-------------+------------------------+--

 Figure 5: 6LoWPAN IPHC packet format and Route Over routing 



 TOC 

3.2.  Reference Network Model

When a 6LoWPAN follows the Mesh Under configuration, the LoWPAN Edge Router (ER) is the only IPv6 router in the 6LoWPAN (see Figure 6 (An example of a Mesh Under LoWPAN)). This means that the IPv6 link-local scope includes all nodes in the LoWPAN. A Mesh Under routing mechanism MUST be provided to support multi-hop transmission.

If a Route Over routing is used in the stub-network, not only the ER but also other intermediate nodes become LoWPAN Routers and perform standard layer 3 routing (see Figure 7 (An example of a Route Over LoWPAN)). The link-local scope is defined by one radio hop.



    h   h
   /    |                     ER: Edge Router
 ER --- m --- m --- h          m: Mesh Node
       / \                     h: LoWPAN Host
      h   m --- h
          |
         / \
        m - m -- h
 Figure 6: An example of a Mesh Under LoWPAN 



    h   h
   /    |                   ER: Edge Router
 ER --- r --- r --- h        r: LoWPAN Router
       / \                   h: LoWPAN Host
      h   r --- h
          |
         / \
        r - r -- h
 Figure 7: An example of a Route Over LoWPAN 

When multiple 6LoWPANs are formed with globally unique IPv6 addresses in the 6LoWPANs, and node (a) of 6LoWPAN [A] wants to communicate with node (b) of 6LoWPAN [B], the normal IPv6 mechanisms can be employed. For Mesh Under, there is one IP hop from a node (a) to ER of [A], no matter how many radio hops stay apart from each other. This, of course, assumes the existence of a Mesh Under routing protocol in order to reach the ER. For Route Over, the IPv6 address of (b) is set as the destination of the packets, and the nodes perform IP routing to the ER for these outgoing packets. In this case, one radio hop is one IPv6 link. Additionally, a default route to the ER could be inserted into the 6LoWPAN routing system.



 TOC 

4.  Scenario Considerations and Parameters for 6LoWPAN Routing

IP-based LoWPAN 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 robust 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 [7] (Bulusu, N. and S. Jha, “Wireless Sensor Networks,” July 2005.) and [21] (Lu, J., Valois, F., Dohler, M., and D. Barthel, “Quantifying Organization by Means of Entropy,” 2008.). Most related work focuses on optimizing routing for specific application scenarios, which can largely be categorized into several models of communication, including the following ones:

Depending on the topology of a 6LoWPAN and the application(s) running over it, different types of routing may be used. However, this document abstracts from application-specific communication and describes general routing requirements valid for overall routing in 6LoWPANs.

The following parameters can be used to describe specific scenarios in which the candidate routing protocols could be evaluated.

a.
Network Properties:
b.
Node Parameters:
c.
Link Parameters:
This section discusses link parameters that apply to IEEE 802.15.4 legacy mode (i.e. not making use of improved schemes).


 TOC 

5.  6LoWPAN Routing Requirements

This section defines a list of requirements for 6LoWPAN routing. The most important design property unique to low-power networks is that 6LoWPANs have to support multiple device types and roles, for example:

Due to these unique device types and roles LoWPANs need to consider the following two primary attributes:

These fundamental attributes of LoWPANs affect the design of routing solutions, so that existing routing specifications should be simplified and modified to the smallest extent possible when there are appropriate solutions to adapt, otherwise, new solutions should be introduced in order to fit the low-power requirements of LoWPANs, meeting the requirements described in the following.



 TOC 

5.1.  Support of 6LoWPAN Device Properties

The general objectives listed in this section should be followed by 6LoWPAN routing protocols. The importance of each requirement is dependent on what node type the protocol is running on and what the role of the node is. The following requirements are based on battery-powered LoWPAN nodes.

[R01] 6LoWPAN routing protocols SHOULD allow to be implemented with small code size and require low routing state to fit the typical 6LoWPAN node capacity (e.g., code size considering its typical flash memory size, and routing table less than 32 entries).

A 6LoWPAN routing protocol solution should consider the limited memory size typically starting at 4KB. RAM size of LoWPAN nodes often ranges between 2KB and 10KB, and program flash memory normally consists of 48KB to 128KB. (e.g., in the current market, MICAz has 128KB program flash, 4KB EEPROM, 512KB external flash ROM; TIP700CM has 48KB program flash, 10KB RAM, 1MB external flash ROM).

Due to these hardware restrictions, code length should be considered to fit within a small memory size; no more than 48KB to 128KB of flash memory including at least a few tens of KB of application code size. A routing protocol of low complexity helps to achieve the goal of reducing power consumption, improves robustness, requires lower routing state, is easier to analyze, and may be implicitly less prone to security attacks.

In addition, operation with low routing state (such as routing tables and neighbor lists) SHOULD be maintained since some typical memory sizes preclude to store state of a large number of nodes. For instance, industrial monitoring applications need to support at maximum 20 hops [16] (Pister, K., Thubert, P., Dwars, S., and T. Phinney, “Industrial Routing Requirements in Low Power and Lossy Networks, draft-ietf-roll-indus-routing-reqs-04 (work in progress),” January 2009.). Small networks can be designed to support a smaller number of hops. It is highly dependent on the network architecture, but considering the 6LoWPAN device properties, there should be at least one mode of operation that can function with 32 forwarding entries or less.

[R02] 6LoWPAN routing protocols SHOULD cause minimal power consumption by the efficient use of control packets (e.g., minimize expensive IP multicast which causes link broadcast to the entire LoWPAN) and by the efficient routing of data packets.

One way of battery lifetime optimization is by achieving a minimal control message overhead. Compared to functions such as computational operations or taking sensor samples, radio communications is by far the dominant factor of power consumption [10] (Pister, K. and B. Boser, “Smart Dust: Wireless Networks of Millimeter-Scale Sensor Nodes,” .). Power consumption of transmission and/or reception depends linearly on the length of data units and on the frequency of transmission and reception of the data units [13] (Shih, E., “Physical Layer Driven Protocols and Algorithm Design for Energy-Efficient Wireless Sensor Networks,” July 2001.).

The energy consumption of two example RF controllers for low-power nodes is shown in [11] (Hill, J., “System Architecture for Wireless Sensor Networks,” .). The TR1000 radio consumes 21mW when transmitting at 0.75mW, and 15mW on reception (with a receiver sensitivity of -85dBm). The CC1000 consumes 31.6mW when transmitting 0.75mW, and 20mW for receiving (with a receiver sensitivity of -105dBm). The power continuation under the concept of an idealized power source is explained in [11] (Hill, J., “System Architecture for Wireless Sensor Networks,” .). Based on the energy of an idealized AA battery, the CC1000 can transmit for approximately 4 days straight or receive for 9 consecutive days. Note that availability for reception consumes power as well.

Multicast may causes flooding in the LoWPAN. On consideration this, 6LoWPAN routing protocol SHOULD minimize the control cost by the routing packets. Another document discusses control cost of routing protocols in low power and lossy networks [19] (Levis, P., Tavakoli, A., and S. Dawson-Haggerty, “Overview of Existing Routing Protocols for Low Power and Lossy Networks , draft-ietf-roll-protocols-survey-06 (work in progress),” .).



 TOC 

5.2.  Support of 6LoWPAN Link Properties

6LoWPAN links have the characteristics of low data rate and possibly high loss rates. The routing requirements described in this section are derived from the link properties.

[R03] 6LoWPAN routing protocol control messages SHOULD NOT exceed a single IEEE 802.15.4 frame size in order to avoid packet fragmentation and the overhead for reassembly.

In order to save energy, routing overhead should be minimized to prevent fragmentation of frames. Therefore, 6LoWPAN routing should not cause packets to exceed the IEEE 802.15.4 frame size. This reduces the energy required for transmission, avoids unnecessary waste of bandwidth, and prevents the need for packet reassembly. As calculated in RFC4944 [4] (Montenegro, G., Kushalnagar, N., Hui, J., and D. Culler, “Transmission of IPv6 Packets over IEEE 802.15.4 Networks,” September 2007.), the maximum size of a 6LoWPAN frame, in order not to cause fragmentation, is 81 octets. This may imply the use of semantic fragmentation and/or algorithms that can work on small increments of routing information.

[R04] The design of routing protocols for LoWPANs must consider the fact that packets are to be delivered with sufficient probability according to application requirements.

Requirements on successful end-to-end packet delivery ratio (where delivery may be bounded within certain latency) vary depending on applications. In industrial applications, some non-critical monitoring applications may tolerate successful delivery ratio of less than 90% with hours of latency; in some other cases, a delivery ratio of 99.9% is required [16] (Pister, K., Thubert, P., Dwars, S., and T. Phinney, “Industrial Routing Requirements in Low Power and Lossy Networks, draft-ietf-roll-indus-routing-reqs-04 (work in progress),” January 2009.). In building automation applications, application layer errors must be below 0.01% [18] (Martocci, J., De Mil, P., Vermeylen, W., and N. Riou, “Building Automation Routing Requirements in Low Power and Lossy Networks, draft-ietf-roll-building-routing-reqs-05 (work in progress),” .).

Successful end-to-end delivery of packets in a IEEE 802.15.4 mesh depends on the quality of the path selected by the routing protocol and on the ability of the routing protocol to cope with short-term and long-term quality variation. The metric of the routing protocol strongly influences performance of the routing protocol in terms of delivery ratio.

The quality of a given path depends on the individual qualities of the links (including the devices) that compose that path. IEEE 802.15.4 settings affect the quality perceived at upper layers. In particular, in IEEE 802.15.4 reliable mode, if an acknowledgment frame is not received after a given period, the originator retries frame transmission up to a maximum number of times. If an acknowledgment frame is still not received by the sender after performing the maximum number of transmission attempts, the MAC layer assumes the transmission has failed and notifies the next higher layer of the failure. Note that excessive retransmission may be detrimental, see RFC 3819 [5] (Karn, P., Bormann, C., Fairhurst, G., Grossman, D., Ludwig, R., Mahdavi, J., Montenegro, G., Touch, J., and L. Wood, “Advice for Internet Subnetwork Designers,” July 2004.).

[R05] The design of routing protocols for LoWPANs must consider the latency requirements of applications and IEEE 802.15.4 link latency characteristics.

Latency requirements may differ from a few hundreds milliseconds to minutes, depending on the type of application. Real-time building automation applications usually need response times below 500 ms between egress and ingress, while forced entry security alerts must be routed to one or more fixed or mobile user devices within 5 seconds [18] (Martocci, J., De Mil, P., Vermeylen, W., and N. Riou, “Building Automation Routing Requirements in Low Power and Lossy Networks, draft-ietf-roll-building-routing-reqs-05 (work in progress),” .). Non-critical closed loop applications for industrial automation have latency requirements that can be as low as 100 ms but many control loops are tolerant of latencies above 1s [16] (Pister, K., Thubert, P., Dwars, S., and T. Phinney, “Industrial Routing Requirements in Low Power and Lossy Networks, draft-ietf-roll-indus-routing-reqs-04 (work in progress),” January 2009.). In contrast to this, urban monitoring applications allow latencies smaller than the typical intervals used for reporting sensed information; for instance, in the order of seconds to minutes [17] (Dohler, M., Watteyne, T., Winter, T., Barthel, D., and C. Jacquenet, “Urban WSNs Routing Requirements in Low Power and Lossy Networks, draft-ietf-roll-urban-routing-reqs-03 (work in progress),” January 2009.).

The range of latencies of a frame transmission between a single sender and a single receiver through an ideal unslotted IEEE 802.15.4 2.4 GHz channel is between 2.46ms and 6.02ms in 64 bit MAC address unreliable mode and 2.20 ms to 6.56ms in 64 bit address reliable mode. The range of latencies of 868 MHz band is from 11.7 ms to 63.7 ms, depending on the address type and reliable/unreliable mode used. Note that the latencies may be larger than that depending on channel load, MAC layer settings , and reliable/unreliable mode choice. Note that other MAC approaches than the legacy 802.15.4 may be used (e.g. TDMA). Duty cycling may further affect latency (see [R08 ]).

Note that a tradeoff exists between [R05] and [R04].

[R06] 6LoWPAN routing protocols SHOULD be robust to dynamic loss caused by link failure or device unavailability either in short-term (e.g. due to RSSI variation, interference variation, noise and asynchrony) or in long-term (e.g. due to a depleted power source, hardware breakdown, operating system misbehavior, etc).

An important trait of 6LoWPAN 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. In harsh environments, LoWPANs easily suffer from link failure. Collision or link failure easily increases Send Queue/Receive Queue (SQ/RQ) and it can lead to queue overflow and packet losses.

For home applications, where users expect feedback after carrying out actions (such as handling a remote control while moving around), routing protocols must converge within 2 seconds if the destination node of the packet has moved and must converge within 0.5 seconds if only the sender has moved [15] (Brandt, A., Buron, J., and G. Porcu, “Home Automation Routing Requirement in Low Power and Lossy Networks, draft-ietf-roll-home-routing-reqs-06 (work in progress),” November 2008.). The tolerance of the recovery time can vary depending on the application, however, the routing protocol must provide the detection of short-term unavailability and long-term disappearance. The routing protocol has to exploit network resources (e.g. path redundancy) to offer good network behavior despite of node failure.

[R07] 6LoWPAN routing protocols SHOULD be designed to correctly operate in the presence of link asymmetry.

Link asymmetry occurs when the probability of successful transmission between two nodes is significantly higher in one direction than in the other one. This phenomenon has been reported in a large number of experimental studies and it is expected that 6LoWPANs will exhibit link asymmetry.



 TOC 

5.3.  Support of 6LoWPAN Network Characteristics

6LoWPANs can be deployed in different sizes and topologies, adhere to various models of mobility, tolerate various levels of interference, etc. In any case, LoWPANs must maintain low energy consumption. The requirements described in the following subsection are derived from the network attributes of 6LoWPANs.

[R08] 6LoWPAN routing protocols SHOULD be reliable despite unresponsive nodes due to periodic hibernation.

Many nodes in LoWPAN environments might periodically hibernate (i.e. disable their transceiver activity) in order to save energy. Therefore, routing protocols must ensure robust packet delivery despite nodes frequently shutting off their radio transmission interface. Feedback from the lower IEEE 802.15.4 layer may be considered to enhance the power-awareness of 6LoWPAN routing protocols.

CC1000-based nodes must operate at a duty cycle of approximately 2% to survive for one year from idealized AA battery power source [11] (Hill, J., “System Architecture for Wireless Sensor Networks,” .). For home automation purposes, it is suggested that that the devices have to maximize the sleep phase with a duty cycle lower than 1% [15] (Brandt, A., Buron, J., and G. Porcu, “Home Automation Routing Requirement in Low Power and Lossy Networks, draft-ietf-roll-home-routing-reqs-06 (work in progress),” November 2008.), while in building automation applications, batteries must be operational for at least 5 years when the sensing devices are transmitting data (e.g. 64 bytes) once per minute [18] (Martocci, J., De Mil, P., Vermeylen, W., and N. Riou, “Building Automation Routing Requirements in Low Power and Lossy Networks, draft-ietf-roll-building-routing-reqs-05 (work in progress),” .).

Dependent on the application in use, packet rates differ from 1/sec to 1/day. Routing protocols need to know the cycle of the packet transmission and utilize the information to calculate routing paths.

[R09] The metric used by 6LoWPAN routing protocols MAY utilize a combination of the inputs provided by the lower layers and other measures to obtain the optimal path considering energy balance and link qualities.

In homes, buildings, or infrastructure, some nodes will be installed with mains power. Such power-installed nodes MUST be considered as a relay points for more roles in packet delivery. 6LoWPAN routing protocols MUST know the power constraints of the nodes.

Simple hop-count-only mechanisms may be inefficient in 6LoWPANs. There is a Link Quality Indication (LQI), or/and RSSI from IEEE 802.15.4 that may be taken into account for better metrics. The metric to be used (and its goal) may depend on applications and requirements.

The numbers in Figure 8 (An example network) represent the Link Delivery Ratio (LDR) of each pair of nodes. There are studies that show a piecewise linear dependence between LQI and LDR [14] (Chen, B., Muniswamy-Reddy, K., and M. Welsh, “Ad-Hoc Multicast Routing on Resource-Limited Sensor Nodes,” 2006.).



                                  0.6
                               A-------C
                                \     /
                             0.9 \   / 0.9
                                  \ /
                                   B
 Figure 8: An example network 

In this simple example, there are two options in routing from node A to node C, with the following features:

A.
Path AC:
  • (1/0.6) = 1.67 avg. transmissions needed for each packet
  • one-hop path
  • good in energy consumption and end-to-end latency of data packets, bad in delivery ratio (0.6)
  • bad in probability of route reconfigurations
B.
Path ABC
  • 2*(1/0.81) = 2.47 avg. transmissions needed for each packet
  • two-hop path
  • bad in energy consumption and end-to-end latency of data packets, good in delivery ratio (0.81)

If energy consumption of the network must be minimized, path AC is the best (this path would be chosen based on a hop count metric). However, if the delivery ratio in that case is not sufficient, the best path is ABC (it would be chosen by an LQI based metric). Combinations of both metrics can be used.

The metric also affects the probability of route reconfiguration. Route reconfiguration, which may be triggered by packet losses, may require transmission of routing protocol messages. It is possible to use a metric aimed at selecting the path with low route reconfiguration rate by using LQI as an input to the metric. Such a path has good properties, including stability and low control message overhead.

[R10] 6LoWPAN routing protocols SHOULD be designed to achieve both scalability from a few nodes to millions of nodes and minimality in terms of used system resources.

A LoWPAN may consist of just a couple of nodes (for instance in a body-area network), but may expand to much higher numbers of devices (e.g. monitoring of a city infrastructure or a highway). For home automation applications it is envisioned that the routing protocol must support 250 devices in the network [15] (Brandt, A., Buron, J., and G. Porcu, “Home Automation Routing Requirement in Low Power and Lossy Networks, draft-ietf-roll-home-routing-reqs-06 (work in progress),” November 2008.), while routing protocols for metropolitan-scale sensor networks must be capable of clustering a large number of sensing nodes into regions containing on the order of 10^2 to 10^4 sensing nodes each [17] (Dohler, M., Watteyne, T., Winter, T., Barthel, D., and C. Jacquenet, “Urban WSNs Routing Requirements in Low Power and Lossy Networks, draft-ietf-roll-urban-routing-reqs-03 (work in progress),” January 2009.). It is therefore necessary that routing mechanisms are designed to be scalable for operation in various network sizes. However, due to a lack of memory size and computational power, 6LoWPAN routing might limit forwarding entries to a small number, such as at maximum 32 routing table entries.

[R11] The procedure of route repair and related control messages should not harm overall energy consumption from the routing protocols.

Local repair improves throughput and end-to-end latency, especially in large networks. Since routes are repaired quickly, fewer data packets are dropped, and a smaller number of routing protocol packet transmissions are needed since routes can be repaired without source initiated Route Discovery [12] (Lee, S., Belding-Royer, E., and C. Perkins, “Scalability Study of the Ad Hoc On-Demand Distance-Vector Routing Protocol,” March 2003.). One important consideration here may be to avoid premature depletion, even in case that impairs other requirements.

[R12] 6LoWPAN routing protocols SHOULD allow for dynamically adaptive topologies and mobile nodes. When supporting dynamic topologies and mobile nodes, route maintenance should keep in mind the goal of a minimal routing state and routing protocol message overhead.

Building monitoring applications, for instance, require that the mobile devices SHOULD be capable of leaving (handing-off) from an old network joining onto a new network within 15 seconds [18] (Martocci, J., De Mil, P., Vermeylen, W., and N. Riou, “Building Automation Routing Requirements in Low Power and Lossy Networks, draft-ietf-roll-building-routing-reqs-05 (work in progress),” .). More interactive applications such as used in home automation systems, where users are giving input and expect instant feedback, mobility requirements are also stricter and a convergence time below 0.5 seconds is commonly required [15] (Brandt, A., Buron, J., and G. Porcu, “Home Automation Routing Requirement in Low Power and Lossy Networks, draft-ietf-roll-home-routing-reqs-06 (work in progress),” November 2008.). In industrial environments, where mobile equipment such as cranes move around, the support of vehicular speeds of up to 35 km/h are required to be supported by the routing protocol [16] (Pister, K., Thubert, P., Dwars, S., and T. Phinney, “Industrial Routing Requirements in Low Power and Lossy Networks, draft-ietf-roll-indus-routing-reqs-04 (work in progress),” January 2009.). Currently, 6LoWPANs are not being used for such a fast mobility, but dynamic association and disassociation MUST be supported in 6LoWPAN.

There are several challenges that should be addressed by a 6LoWPAN routing protocol in order to create robust routing in dynamic environments:

[R13] 6LoWPAN routing protocol SHOULD support various traffic patterns; point-to-point, point-to-multipoint, and multipoint-to-point, while avoid excessive multicast traffic in a LoWPAN.

6LoWPANs often have point-to-multipoint or multipoint-to-point traffic patterns. Many emerging applications include point-to-point communication as well. 6LoWPAN routing protocols should be designed with the consideration of forwarding packets from/to multiple sources/destinations. Current WG drafts in the ROLL working group explain that the workload or traffic pattern of use cases for LoWPANs tend to be highly structured, unlike the any-to-any data transfers that dominate typical client and server workloads. In many cases, exploiting such structure may simplify difficult problems arising from resource constraints or variation in connectivity.



 TOC 

5.4.  Support of Security

The routing requirement described in this subsection allows secure transmission of routing messages. Solutions may take into account the specific features of IEEE 802.15.4 MAC layers.

[R14] 6LoWPAN protocols SHOULD support secure delivery of control messages. A minimal security level can be achieved by utilizing AES-based mechanism provided by IEEE 802.15.4.

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 [2] (Nikander, P., Kempf, J., and E. Nordmark, “IPv6 Neighbor Discovery (ND) Trust Models and Threats,” May 2004.). Bootstrapping may also impose additional threats. Security is also very important for designing robust routing protocols, but it should not cause significant transmission overhead. While there are applications which require very high security, such as in traffic control, other applications are less easily harmed by wrong node behavior, such as a home entertainment system.

The IEEE 802.15.4 MAC provides an AES-based security mechanism. Routing protocols need to define how this mechanism can be used to obtain the intended security. Byte overhead of the mechanism, which depends on the security services selected, must be considered. In the worst case in terms of overhead, the mechanism consumes 21 bytes of MAC payload.

IEEE 802.15.4 does not specify protection for acknowledgement frames. Since the sequence numbers of data frames are sent in the clear, an adversary can forge an acknowledgement for each data frame. This weakness can be combined with targeted jamming to prevent delivery of selected packets. In consequence, IEEE 802.15.4 acknowledgements cannot be relied upon. In applications that require high security, the routing protocol must not exploit feedback from acknowledgements (e.g. to keep track of neighbor connectivity, see [R16]).



 TOC 

5.5.  Support of Mesh-under Forwarding

One LoWPAN may be built as one IPv6 link. In this case, Mesh Under forwarding/routing mechanisms must be supported. The routing requirements described in this subsection allow optimization and correct operation of routing solutions taking into account the specific features of the mesh-under configuration.

[R15] In case a routing protocol operates in 6LoWPAN's adaptation layer, routing tables and neighbor lists MUST support 16-bit short and 64-bit extended addresses.

[R16] In order to perform discovery and maintenance of neighbors, LoWPAN Nodes SHOULD avoid sending "Hello" messages of NS, NA, RS or RA messages. Instead, link-layer mechanisms (such as acknowledgments) MAY be utilized to keep track of active neighbors.

Reception of an acknowledgement after a frame transmission may render unnecessary the transmission of explicit Hello messages, for example. In a more general view, any frame received by a node may be used as an input to evaluate the connectivity between the sender and receiver of that frame.

[R17] In case there are one or more nodes allocated for the specific role of local management, the nodes MAY take the role of keeping track of node association and de-association within the charging area of the LoWPAN.

[R18] If the routing protocol functionality includes enabling IP multicast, then it may want to employ relay points of group-targeting messages instead of using link-layer multicast (broadcast).



 TOC 

6.  Security Considerations

Security issues are described in Section 4.4. Security considerations of RFC 4919 [3] (Kushalnagar, N., Montenegro, G., and C. Schumacher, “IPv6 over Low-Power Wireless Personal Area Networks (6LoWPANs): Overview, Assumptions, Problem Statement, and Goals,” August 2007.) and RFC 4944 [4] (Montenegro, G., Kushalnagar, N., Hui, J., and D. Culler, “Transmission of IPv6 Packets over IEEE 802.15.4 Networks,” September 2007.) apply as well. More security considerations will result from the 6LoWPAN security analysis work.



 TOC 

7.  Acknowledgements

The authors thank Myung-Ki Shin for giving the idea of writing this draft. The authors also thank to S. Chakrabarti who gave valuable comments for mesh-under requirements.



 TOC 

8.  References



 TOC 

8.1. Normative References

[1] Bradner, S., “Key words for use in RFCs to Indicate Requirement Levels,” BCP 14, RFC 2119, March 1997 (TXT, HTML, XML).
[2] Nikander, P., Kempf, J., and E. Nordmark, “IPv6 Neighbor Discovery (ND) Trust Models and Threats,” RFC 3756, May 2004 (TXT).
[3] Kushalnagar, N., Montenegro, G., and C. Schumacher, “IPv6 over Low-Power Wireless Personal Area Networks (6LoWPANs): Overview, Assumptions, Problem Statement, and Goals,” RFC 4919, August 2007 (TXT).
[4] Montenegro, G., Kushalnagar, N., Hui, J., and D. Culler, “Transmission of IPv6 Packets over IEEE 802.15.4 Networks,” RFC 4944, September 2007 (TXT).
[5] Karn, P., Bormann, C., Fairhurst, G., Grossman, D., Ludwig, R., Mahdavi, J., Montenegro, G., Touch, J., and L. Wood, “Advice for Internet Subnetwork Designers,” BCP 89, RFC 3819, July 2004 (TXT).
[6] IEEE Computer Society, “IEEE Std. 802.15.4-2006 (as amended),” 2007.


 TOC 

8.2. Informative References

[7] Bulusu, N. and S. Jha, “Wireless Sensor Networks,” July 2005.
[8] Shelby, Z., Thubert, P., Hui, J., Chakrabarti, S., and E. Nordmark, “LoWPAN Neighbor Discovery Extensions, draft-ietf-6lowpan-nd-01 (work in progress),” February 2009.
[9] Hui, J. and P. Thubert, “Compression Format for IPv6 Datagrams in 6LoWPAN Networks, draft-ietf-6lowpan-hc-04 (work in progress),” December 2008.
[10] Pister, K. and B. Boser, “Smart Dust: Wireless Networks of Millimeter-Scale Sensor Nodes.”
[11] Hill, J., “System Architecture for Wireless Sensor Networks.”
[12] Lee, S., Belding-Royer, E., and C. Perkins, “Scalability Study of the Ad Hoc On-Demand Distance-Vector Routing Protocol,” March 2003.
[13] Shih, E., “Physical Layer Driven Protocols and Algorithm Design for Energy-Efficient Wireless Sensor Networks,” July 2001.
[14] Chen, B., Muniswamy-Reddy, K., and M. Welsh, “Ad-Hoc Multicast Routing on Resource-Limited Sensor Nodes,” 2006.
[15] Brandt, A., Buron, J., and G. Porcu, “Home Automation Routing Requirement in Low Power and Lossy Networks, draft-ietf-roll-home-routing-reqs-06 (work in progress),” November 2008.
[16] Pister, K., Thubert, P., Dwars, S., and T. Phinney, “Industrial Routing Requirements in Low Power and Lossy Networks, draft-ietf-roll-indus-routing-reqs-04 (work in progress),” January 2009.
[17] Dohler, M., Watteyne, T., Winter, T., Barthel, D., and C. Jacquenet, “Urban WSNs Routing Requirements in Low Power and Lossy Networks, draft-ietf-roll-urban-routing-reqs-03 (work in progress),” January 2009.
[18] Martocci, J., De Mil, P., Vermeylen, W., and N. Riou, “Building Automation Routing Requirements in Low Power and Lossy Networks, draft-ietf-roll-building-routing-reqs-05 (work in progress).”
[19] Levis, P., Tavakoli, A., and S. Dawson-Haggerty, “Overview of Existing Routing Protocols for Low Power and Lossy Networks , draft-ietf-roll-protocols-survey-06 (work in progress).”
[20] Latre, M., De Mil, P., Moerman, I., Dhoedt, B., and P. Demeester, “Throughput and Delay Analysis of Unslotted IEEE 802.15.4,” May 2006.
[21] Lu, J., Valois, F., Dohler, M., and D. Barthel, “Quantifying Organization by Means of Entropy,” 2008.


 TOC 

Authors' Addresses

  Eunsook Eunah Kim
  ETRI
  161 Gajeong-dong
  Yuseong-gu
  Daejeon 305-700
  Korea
Phone:  +82-42-860-6124
Email:  eunah.ietf@gmail.com
  
  Dominik Kaspar
  Simula Research Laboratory
  Martin Linges v 17
  Snaroya 1367
  Norway
Phone:  +47-6782-8223
Email:  dokaspar.ietf@gmail.com
  
  Carles Gomez
  Tech. Univ. of Catalonia/i2CAT
  Escola Politecnica Superior de Castelldefels
  Avda. del Canal Olimpic, 15
  Castelldefels 08860
  Spain
Phone:  +34-93-413-7206
Email:  carlesgo@entel.upc.edu
  
  Carsten Bormann
  Universität Bremen TZI
  Postfach 330440
  Bremen D-28359
  Germany
Phone:  +49-421-218-63921
Fax:  +49-421-218-7000
Email:  cabo@tzi.org