TOC 
6LoWPAN Working GroupE. Kim
Internet-DraftETRI
Expires: January 15, 2009D. Kaspar
 Simula Research Laboratory
 C. Gomez
 Technical University of
 Catalonia/i2CAT
 C. Bormann
 Universität Bremen TZI
 July 14, 2008


Problem Statement and Requirements for 6LoWPAN Mesh Routing
draft-dokaspar-6lowpan-routreq-06

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 15, 2009.

Abstract

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


Table of Contents

1.  Problem Statement
2.  Design Space
3.  Scenario Considerations and Parameters for 6LoWPAN Routing
4.  6LoWPAN Routing Requirements
    4.1.  Routing Requirements depending on the 6LoWPAN Device Properties
    4.2.  Routing Requirements depending on Types of 6LoWPAN Applications
    4.3.  MAC-coupled Requirements
    4.4.  Mesh-under specific Requirements
    4.5.  Route-over specific Requirements
5.  Security Considerations
6.  Acknowledgements
7.  References
    7.1.  Normative References
    7.2.  Informative References
§  Authors' Addresses
§  Intellectual Property and Copyright Statements



 TOC 

1.  Problem Statement

Low-power wireless personal area networks (LoWPANs) are formed by devices complying to the IEEE 802.15.4 standard [5] (IEEE Computer Society, “IEEE Std. 802.15.4-2003,” October 2003.)[6] (IEEE Computer Society, “IEEE Std. 802.15.4-2006,” September 2006.). 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 [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 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" [4] (Montenegro, G., Kushalnagar, N., Hui, J., and D. Culler, “Transmission of IPv6 Packets over IEEE 802.15.4 Networks,” September 2007.)) specify how mesh topologies could be obtained and maintained. Thus, the 6LoWPAN formation and multi-hop routing should be supported by higher layer, either 6LoWPAN adaptation layer or IP layer. In the IETF, a number of experimental protocols in IP layer have been developed in many working groups. However, these existing routing protocols may not be satisfying for mesh routing in a LoWPAN domain, for the following reasons:

This creates new challenges on obtaining robust and reliable mesh 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 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.

Using the 6LoWPAN header format[6], 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, 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 to both the mesh-under and route-over cases.

In summary, the main issues of mesh routing in 6LoWPANs are:

  1. The precise 6LoWPAN routing requirements must be defined.
  2. If a routing protocol for 6LoWPAN is designed to run in the IP layer, it should meet the 6LoWPAN-specific requirements. It needs to be clarified how existing routing solutions can be adapted to meet the low-power requirements presented in Section 4 (6LoWPAN Routing Requirements).
    [Note] ROLL WG is now working on the protocol survey for Low power and Lossy Networks (LLNs), not specifically for 6LoWPAN. It will decide whether new solution will be developed or not, after that survey. This document is focused on 6LoWPAN specific requirements, in alignment with ROLL WG.
  3. If a routing procotol for 6LoWPAN within a subnet is designed to run in adaptation layer, existing routing solutions do not operate in 6LoWPAN's adaptation layer (and do not support the addressing scheme defined by IEEE 802.15.4).

Considering the problems above, this draft addresses routing requirements for 6LoWPANs for both mesh-under and route-over routing protocol design.

Application-specific features affect the design of 6lowpan routing requirements and the corresponding solutions. However, various applications can be profiled by similar technical characteristics. This document states the requirements to consider the features of 6LoWPAN applications in general. However, it does not mean that one single routing solution may be the best one for all 6LoWPAN applications.


 TOC 

2.  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 in the IP-layer using a route-over approach. The most significant consequence of mesh-under routing is that routing would be directly based on the IEEE 802.15.4 standard, therefore using (64-bit or 16-bit short) MAC addresses instead of IP addresses, and a LoWPAN would be seen as a single IP link. In case a route-over mechanism is to be applied to a LoWPAN it must also support 6LoWPAN's unique properties using global IPv6 addressing.

Additionally, because of the low-performance characteristics of LoWPANs, a light-weight routing protocol must be provided that meets the design goals and requirements presented in this document.


Figure 1 (Mesh-under (left) and route-over routing (right)) shows the place of 6LoWPAN mesh 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.

If a mesh-under routing protocol is built for operation in 6LoWPAN's adaptation layer, routing control packets are placed after the 6LoWPAN Dispatch, unless a new code type is assigned for mesh-under routing. Multiple routing protocols can be supported by the usage of different Dispatch bit sequences. When a route-over protocol is built in the IPv6 layer, the Dispatch value can be chosen as one of the Dispatch patterns for 6LoWPAN compressed or uncompressed IPv6, followed by the IPv6 header.

If a 6LoWPAN is formed like the Figure 2 (An example of a 6LoWPAN) , the PnC is the only IPv6 router in the LoWPAN in the assumption of [8] (Chakrabarti, S. and E. Nordmark, “LoWPAN Neighbor Discovery Extensions, draft-chakrabarti-6lowpan-ipv6-nd-04 (work in progress),” November 2007.). The mesh-under routing mechanism MUST be provided to forward packets which require multi-hop forwarding. If route-over routing is used in the stub-network, not only the PnC but also other FFDs need to set up IP paths for multi-hop transmission. 


    O     X
    |     |                    PnC: PAN Coordinator
PnC --- O --- O --- X         C: Coordinator
	   / \                O: FFD
      X   C--X                X: RFD
          |
         / \
        O---O--X
 Figure 2: An example of a 6LoWPAN 

If multiple 6LoPWANs 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 PnC (= IPv6 router) will be always the default router for the outgoing packet of the 6LoWPAN.


 TOC 

3.  Scenario Considerations and Parameters for 6LoWPAN Routing

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 [7] (Bulusu, N. and S. Jha, “Wireless Sensor Networks,” July 2005.). 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 any type of 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:

 TOC 

4.  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 support multiple device types and roles, for example:

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

These fundamental features of LoWPANs 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, meeting the following requirements:


 TOC 

4.1.  Routing Requirements depending on the 6LoWPAN Device Properties

The general objectives listed in this subsection should be followed by 6LoWPAN routing protocols. The importance of each requirement is dependent on what device type the protocol is running on and what the role of the device is.

[R01] A 6LoWPAN routing protocol SHOULD be designed to minimize the required computational and algorithmical complexity.

The lifetime of a wireless sensor node depends on the energy it can store and harvest. Saving energy is crucially important to 6LoWPAN devices that are not mains-powered. However, one major factor of power consumption in 6LoWPAN nodes is caused by the microcontroller. Typical low power sensor nodes have 8 or 16 bit microcontrollers. They normally consume between 0.250 mA and 2.5 mA per MHz [10] (Hill, J., “System Architecture for Wireless Sensor Networks,” .). Low power microcontrollers can have a significant impact on system performance. A routing protocol of low complexity helps to achieve the goal of reducing power consumption, improves robustness, requires lower routing state, is more easy to analyze, and is implicitly less prone to security attacks.

See also Section 4.2 in [14] (Brandit, A. and G. Porcu, “Home Automation Routing Requirement in Low Power and Lossy Networks, draft-ietf-roll-home-routing-reqs-01 (work in progress),” July 2008.) and Section 6.2 in [16] (Dohler, M., Watteyne, T., and T. Winter, “Urban WSNs Routing Requirements in Low Power and Lossy Networks, draft-ietf-roll-urban-routing-reqs-01 (work in progress),” July 2008.).

[R02] 6LoWPAN routing protocols SHOULD have a low routing state to fit the typical 6LoWPAN node capacity.

Typical RAM size of 6LoWPAN nodes 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). 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 example, devices may have only 32 forwarding entries available. A LoWPAN routing protocol solution should consider the limited memory size typically starting at 4KB, in which it is hard to store neighbor state of hundreds of nodes) and computation capabilities of participating devices; due to these hardware restrictions, code length should be considered to fit within a small memory size. In addition, it should consider that flash writing/reading is energy expensive, while power consumption for RAM is may be comparably negligible. For instance, in MICA motes, writing and reading consumes 1.1 nAh/byte and 83.3 nAh/byte, respectively.

See also Section 4.2 in [14] (Brandit, A. and G. Porcu, “Home Automation Routing Requirement in Low Power and Lossy Networks, draft-ietf-roll-home-routing-reqs-01 (work in progress),” July 2008.), Section 5 in [15] (Pister, K., Thubert, P., Dwars, S., and T. Phinney, “Industrial Routing Requirements in Low Power and Lossy Networks, draft-ietf-roll-indus-routing-reqs-01 (work in progress),” July 2008.) and Section 6.2 in [16] (Dohler, M., Watteyne, T., and T. Winter, “Urban WSNs Routing Requirements in Low Power and Lossy Networks, draft-ietf-roll-urban-routing-reqs-01 (work in progress),” July 2008.).

[R03] 6LoWPAN routing protocols SHOULD cause minimal power consumption, both in the efficient use of control packets and also in the process of packet forwarding after route establishment.

Routing protocol design for 6LoWPAN should consider IEEE 802.15.4 link layer feedback on energy consumption. Power-aware routing is a non-trivial task, because it is affected by many mutually conflicting goals:

while keeping packet delivery ratio, latency or other requirements depending on each application.

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 [9] (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 [12] (Shih, E., “Physical Layer Driven Protocols and Algorithm Design for Energy-Efficient Wireless Sensor Networks,” July 2001.)

In [10] (Hill, J., “System Architecture for Wireless Sensor Networks,” .) the energy consumption of two example RF controllers for low-power nodes is shown. The TR1000 radio consumes: 21mW on transmitting at 0.75mW; 15mW on reception (a receiver sensitivity of -85dBm). The CC1000 consumes: 31.6mW on transmitting 0.75mW; 20mW on reception (a receiver sensitivity of -105dBm). [10] (Hill, J., “System Architecture for Wireless Sensor Networks,” .) explains the power continuation under the concept of an idealized power source: the CC1000 can transmit for approximately 4 days straight or receive for 9 days straight. The CC1000 must operate at a duty cycle of approximately 2% to survive for one year.

See also Section 4.2 in [14] (Brandit, A. and G. Porcu, “Home Automation Routing Requirement in Low Power and Lossy Networks, draft-ietf-roll-home-routing-reqs-01 (work in progress),” July 2008.).

[R04] 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 is needed since routes can be repaired without source initiated Route Discovery [11] (Lee, S., Belding-Royer, E., and C. Perkins, “Scalability Study of the Ad Hoc On-Demand Distance-Vector Routing Protocol,” March 2003.).

[R05] Neighbor discovery for 6LoWPAN routing SHOULD be energy-efficient.

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. Mesh-under neighbor discovery for 6LoWPANs is currently still in progress and described more detailed in [8] (Chakrabarti, S. and E. Nordmark, “LoWPAN Neighbor Discovery Extensions, draft-chakrabarti-6lowpan-ipv6-nd-04 (work in progress),” November 2007.).

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

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

See also Section 4.2 in [14] (Brandit, A. and G. Porcu, “Home Automation Routing Requirement in Low Power and Lossy Networks, draft-ietf-roll-home-routing-reqs-01 (work in progress),” July 2008.).


 TOC 

4.2.  Routing Requirements depending on Types of 6LoWPAN Applications

The routing requirements described in this subsection are heavily dependent on application needs.

[R07] 6LoWPAN routing protocol SHOULD support various traffic patterns; point-to-point, point-to-multipoint, and multipoint-to-point, while avoid excessive multicast traffic (broadcast in Link) in 6LoWPAN.

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

See also Section 5 in [14] (Brandit, A. and G. Porcu, “Home Automation Routing Requirement in Low Power and Lossy Networks, draft-ietf-roll-home-routing-reqs-01 (work in progress),” July 2008.), Section 2.1 in [15] (Pister, K., Thubert, P., Dwars, S., and T. Phinney, “Industrial Routing Requirements in Low Power and Lossy Networks, draft-ietf-roll-indus-routing-reqs-01 (work in progress),” July 2008.) and Section 5 in [16] (Dohler, M., Watteyne, T., and T. Winter, “Urban WSNs Routing Requirements in Low Power and Lossy Networks, draft-ietf-roll-urban-routing-reqs-01 (work in progress),” July 2008.).

[R08] 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.

The routing protocol has to exploit network resources (e.g. path redundancy) to offer good network behavior despite node failure. For instance, in case of structural health monitoring, hundreds of nodes could be placed on 20 bridge pillars spanning over a river. Once the nodes are distributed, they are hardly accessible for maintenance and in case of single node failure, the network should not break down.

The design of routing protocols for 6LoWPANs must consider the fact that packets are to be delivered with reasonable probability despite unreliable and unresponsive nodes.

See also Section 4 in [15] (Pister, K., Thubert, P., Dwars, S., and T. Phinney, “Industrial Routing Requirements in Low Power and Lossy Networks, draft-ietf-roll-indus-routing-reqs-01 (work in progress),” July 2008.).

[R09] 6LoWPAN routing protocols SHOULD allow for dynamically adaptive topologies and mobile nodes. When supporting dynamic topologies and mobile nodes, route maintenance should be managed by keeping in mind the goal of a minimal routing state.

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

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

A 6LoWPAN 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). 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 32 routing table entries.

See also Section 4.5 in [14] (Brandit, A. and G. Porcu, “Home Automation Routing Requirement in Low Power and Lossy Networks, draft-ietf-roll-home-routing-reqs-01 (work in progress),” July 2008.) and Section 6.1 in [16] (Dohler, M., Watteyne, T., and T. Winter, “Urban WSNs Routing Requirements in Low Power and Lossy Networks, draft-ietf-roll-urban-routing-reqs-01 (work in progress),” July 2008.).


 TOC 

4.3.  MAC-coupled Requirements

The routing requirements described in this subsection allow optimization and correct operation of routing solutions taking into account the specific features of IEEE 802.15.4 physical and MAC layers.

[R11] 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.

[R12] 6LoWPAN routing protocol control messages SHOULD not create fragmentation of physical layer (PHY) frames.

In order to save energy, routing overhead should be minimized to prevent fragmentation of frames on the physical layer (PHY). 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 on the PHY layer, is 81 octets.

[R13] The metric used by 6LoWPAN routing protocols MAY utilize a combination of the inputs provided by the MAC layer and other measures

Simple hop-count-only mechanisms may be inefficient in 6LoWPANs. There is a Link Quality Indicator (LQI), Link Delivery Ratio (LDR), 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 application and requirements.

The numbers in Figure 3 (An example network) represent the Link Delivery Ratio (LDR) between each pair of nodes. There are studies that show a piecewise linear dependence between LQI and LDR [13] (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 3: An example network 

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

A.
Path AC:
  • (1/0.6) = 1.67 avg. transmissions needed for each packet
  • one-hop path
  • good in energy consumption, bad in delivery ratio (0.6)
B.
Path ABC
  • 2*(1/0.81) = 2.47 avg. transmissions needed for each packet
  • two-hop path
  • bad in energy consumption, 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 by hop count metric). However, if delivery ratio in that case is not sufficient, best path is ABC (it would be chosen by an LQI based metric). Combinations of both of metrics can be used.


 TOC 

4.4.  Mesh-under specific Requirements

The routing requirements described in this subsection allow optimization and correct operation of routing solutions taking into account the specific features mesh-under routing.

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

[R15] For neighbor discovery, 6LoWPAN devices SHOULD avoid sending "Hello" messages. Instead, link-layer mechanisms (such as acknowledgments or beacon responses) MAY be utilized to keep track of active neighbors.

After an IEEE 802.15.4 PAN coordinator permits a device to join, the new device adds the PAN coordinator to its neighbor list and starts transmitting periodic beacons. These beacons can be used as an indication of current neighbors.

[R16] In case there are one or more alternative PAN coordinators, the coordinators MAY take the role of keeping track of node association and de-association within the LoWPAN.

[R17] Alternative PAN coordinators, if any, MAY be a relay point of group-targeting message instead of using multicast (broadcast in the link layer).

For example, RS and RA can be only sent to the coordinators, instead of being multicast. The coordinators take the role to pass the packets to their own neighbors.


 TOC 

4.5.  Route-over specific Requirements

The routing requirements described in this subsection allow optimization and correct operation of routing solutions taking into account the specific features of route-over routing.

[R18] In a mesh topology, 6LoWPAN network formation MUST support to build IP routing connection.

[R19] IP multicast SHOULD be optimized.

In case route-over protocols is applied to 6LoWPAN, excessive IP multicast should be avoided, as it causes not-necessary broadcasting in Link of 6LoWPANs. For example, Multicast (broadcast in Link layer) messages will consume a lot of energy if IPv6 ND cannot be optimized well to suit for 6LoWPAN device.


 TOC 

5.  Security Considerations

Security issues are described in Section 4.2 (Routing Requirements depending on Types of 6LoWPAN Applications)


 TOC 

6.  Acknowledgements

The authors would like to thank Myung-Ki Shin for giving the idea of writing this draft.


 TOC 

7.  References


 TOC 

7.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] IEEE Computer Society, “IEEE Std. 802.15.4-2003,” October 2003.
[6] IEEE Computer Society, “IEEE Std. 802.15.4-2006,” September 2006.

 TOC 

7.2. Informative References

[7] Bulusu, N. and S. Jha, “Wireless Sensor Networks,” July 2005.
[8] Chakrabarti, S. and E. Nordmark, “LoWPAN Neighbor Discovery Extensions, draft-chakrabarti-6lowpan-ipv6-nd-04 (work in progress),” November 2007.
[9] Pister, K. and B. Boser, “Smart Dust: Wireless Networks of Millimeter-Scale Sensor Nodes.”
[10] Hill, J., “System Architecture for Wireless Sensor Networks.”
[11] Lee, S., Belding-Royer, E., and C. Perkins, “Scalability Study of the Ad Hoc On-Demand Distance-Vector Routing Protocol,” March 2003.
[12] Shih, E., “Physical Layer Driven Protocols and Algorithm Design for Energy-Efficient Wireless Sensor Networks,” July 2001.
[13] Chen, B., Muniswamy-Reddy, K., and M. Welsh, “Ad-Hoc Multicast Routing on Resource-Limited Sensor Nodes,” 2006.
[14] Brandit, A. and G. Porcu, “Home Automation Routing Requirement in Low Power and Lossy Networks, draft-ietf-roll-home-routing-reqs-01 (work in progress),” July 2008.
[15] Pister, K., Thubert, P., Dwars, S., and T. Phinney, “Industrial Routing Requirements in Low Power and Lossy Networks, draft-ietf-roll-indus-routing-reqs-01 (work in progress),” July 2008.
[16] Dohler, M., Watteyne, T., and T. Winter, “Urban WSNs Routing Requirements in Low Power and Lossy Networks, draft-ietf-roll-urban-routing-reqs-01 (work in progress),” July 2008.
[17] Latre, M., De Mil, P., Moerman, I., Dhoedt, B., and P. Demeester, “Throughput and Delay Analysis of Unslotted IEEE 802.15.4,” May 2006.

 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
  Technical University 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

 TOC 

Full Copyright Statement

Copyright © The IETF Trust (2008).

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.