6LoWPAN Working Group D. Kaspar Internet-Draft E. Kim Expires: May 22, 2008 ETRI C. Bormann Universitaet Bremen TZI November 19, 2007 Problem Statement and Requirements for 6LoWPAN Mesh Routing draft-dokaspar-6lowpan-routreq-03 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 May 22, 2008. Copyright Notice Copyright (C) The IETF Trust (2007). Kaspar, et al. Expires May 22, 2008 [Page 1] Internet-Draft 6LoWPAN Mesh Routing Requirements November 2007 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 . . . . . . . . . . . . . . . . . . . . . . 3 2. Design Space . . . . . . . . . . . . . . . . . . . . . . . . . 5 3. Scenario Considerations . . . . . . . . . . . . . . . . . . . 7 4. 6LoWPAN Routing Requirements . . . . . . . . . . . . . . . . . 10 4.1. General Routing Requirements . . . . . . . . . . . . . . . 10 4.2. 6LoWPAN-specific Requirements . . . . . . . . . . . . . . 12 4.3. Technical Approaches . . . . . . . . . . . . . . . . . . . 13 5. Security Considerations . . . . . . . . . . . . . . . . . . . 15 6. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 16 7. References . . . . . . . . . . . . . . . . . . . . . . . . . . 17 7.1. Normative References . . . . . . . . . . . . . . . . . . . 17 7.2. Informative References . . . . . . . . . . . . . . . . . . 17 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 18 Intellectual Property and Copyright Statements . . . . . . . . . . 19 Kaspar, et al. Expires May 22, 2008 [Page 2] Internet-Draft 6LoWPAN Mesh Routing Requirements November 2007 1. Problem Statement Low-power wireless personal area networks (LoWPANs) are formed by devices complying to the IEEE 802.15.4 standard [7]. 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 [5]. 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" [6]) specify 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 [2], OLSR [3], or DYMO [11]. However, the modification/simplification of these existing routing protocols may be required for mesh routing to be feasible in a LoWPAN domain, for the following reasons: o A possibly simpler routing problem, because LoWPANs are not transit networks. o The more stringent requirements that apply to LoWPANs as opposed to high performance and non-battery-operated networks. LoWPAN nodes are characterized by small memory sizes, low processing power, and are running on very limited power supplied by primary non-rechargeable batteries. A node's lifetime is usually defined by the lifetime of its battery. This creates new challenges on obtaining robust and reliable mesh routing within LoWPANs. Using the 6LoWPAN header format, 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). Kaspar, et al. Expires May 22, 2008 [Page 3] Internet-Draft 6LoWPAN Mesh Routing Requirements November 2007 Most statements in this draft apply to both the mesh-under and route- over cases. The 6LoWPAN problem statement document ("6LoWPAN Problems and Goals" [5]) 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. 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). If a routing protocol for 6LoWPAN is designed to run in the IP layer, it should be adapted to meet the 6LoWPAN- specific requirements. It must be evaluated which layer is most suitable for 6LoWPAN routing. 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. Considering the problems above, this draft addresses mesh routing requirements for 6LoWPANs for both mesh-under and route-over routing protocol design. Kaspar, et al. Expires May 22, 2008 [Page 4] Internet-Draft 6LoWPAN Mesh Routing Requirements November 2007 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 [6]), 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 shortened) 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 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 | | 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. 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 Kaspar, et al. Expires May 22, 2008 [Page 5] Internet-Draft 6LoWPAN Mesh Routing Requirements November 2007 as one of the Dispatch patterns for 6LoWPAN compressed or uncompressed IPv6, followed by the IPv6 header. Kaspar, et al. Expires May 22, 2008 [Page 6] Internet-Draft 6LoWPAN Mesh Routing Requirements November 2007 3. 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 [8]. Most related work focuses on optimizing routing for specific application scenarios, which can largely be categorized into the following models of communication: o Flooding (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 describes general routing requirements valid for any type of routing in LoWPANs. The following parameters can be used to describe specific scenarios in which the candidate routing protocols could be evaluated. a. Network Properties: * Device Number, Density and Network Diameter: These parameters usually affect the routing state directly (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. * Dynamicity (incl. mobility): Location changes can be induced by unpredictable external Kaspar, et al. Expires May 22, 2008 [Page 7] Internet-Draft 6LoWPAN Mesh Routing Requirements November 2007 factors or by controlled motion, which may in turn cause route changes. Also, nodes may dynamically be introduced into a LoWPAN and removed from it later. 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. * Traffic Patterns, 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. For different traffic patterns (point-to-point, multipoint-to-point, point-to-multipoint) and network architectures, various routing mechanisms have been introduced, such as data-aware, event-driven, address-centric, and geographic routing. * Quality of Service (QoS): For mission-critical applications, support of QoS is mandatory in resource-constrained LoWPANs and cannot be achieved without a certain degree of control message overhead. * Security: LoWPANs may carry sensitive information and require a high level of security support where the availability, integrity, and confidentiality of data are primordial. Secured messages cause overhead and affect the power consumption of LoWPAN routing protocols. b. Node Parameters: * Processing Speed and Memory Size: These basic parameters define the maximum size of the routing state. LoWPAN nodes may have different performance characteristics beyond the common RFD/FFD distinction. * 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 Kaspar, et al. Expires May 22, 2008 [Page 8] Internet-Draft 6LoWPAN Mesh Routing Requirements November 2007 turn results in more direct neighbors of a node and a larger routing state. Kaspar, et al. Expires May 22, 2008 [Page 9] Internet-Draft 6LoWPAN Mesh Routing Requirements November 2007 4. 6LoWPAN Routing Requirements This section defines a list of requirements for 6LoWPAN routing. The two most important design properties, unique to low-power networks are 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. Many devices are mains-powered most of the time, but still need to function for possible extended periods from batteries (e.g. before building power is switched on for the first time). o Low performance: tiny devices, memory sizes, processors, low bandwidth, high loss rates, etc. 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: 4.1. General Routing Requirements The general objectives listed in this subsection should be followed by 6LoWPAN routing protocols: [R01] 6LoWPAN routing protocols SHOULD be simple and of low computational complexity. A LoWPAN routing protocol should be designed to minimize the required memory size, computational and algorithmical complexity. A routing protocol of low complexity helps to achieve the goal of reducing power consumption, improves robustness, is more easy to analyze, and is implicitly less prone to security attacks. [R02] 6LoWPAN routing protocols SHOULD have a low routing state. 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. A LoWPAN routing protocol solution should consider the limited memory size (typically starting at 4K bytes) and computation capabilities of participating devices; due to these hardware restrictions, code length should be considered to fit within a small memory size. [R03] 6LoWPAN routing protocols SHOULD be loop-free. Kaspar, et al. Expires May 22, 2008 [Page 10] Internet-Draft 6LoWPAN Mesh Routing Requirements November 2007 No matter whether a solution is mesh-under or route-over, 6LoWPAN routing protocols SHOULD consider a cost-effective loop-free mechanism. [R04] 6LoWPAN routing protocols SHOULD be robust to dynamic loss rates. An 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 delivered with reasonable probability despite unreliable and unresponsive nodes. [R05] 6LoWPAN routing protocols SHOULD allow for dynamically adaptive topologies and mobile nodes. There are several challenges that should be addressed by a 6LoWPAN routing protocol in order to create robust routing in dynamic environments: * Mobile nodes changing their location inside a LoWPAN. * Movement of a LoWPAN with respect to other (inter)connected LoWPANs. * Nodes permanently joining or leaving the LoWPAN. * Nodes appearing and disappearing in the network due to changes in the physical environment. When supporting dynamic topologies and mobile nodes, route maintenance should be managed by keeping in mind the goal of a minimal routing state. [R06] 6LoWPAN routing protocols SHOULD be scalable. 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 large buildings). 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 Kaspar, et al. Expires May 22, 2008 [Page 11] Internet-Draft 6LoWPAN Mesh Routing Requirements November 2007 forwarding entries to a small number, such as 32 routing table entries. Routing protocols should be designed to achieve both scalability and minimality in terms of used system resources. [R07] 6LoWPAN protocol control messages SHOULD be secured. 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 [4]. Bootstrapping may also impose additional threats. Security is also very important for designing robust routing protocols, but it should not cause significant transmission overhead. 4.2. 6LoWPAN-specific Requirements [R08] 6LoWPAN routing protocols SHOULD cause minimal power consumption, both in the efficient use of control packet and also in the process of packet forwarding after route establishment. 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. 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; * Minimization of total energy consumed in the network * Maximization of the time until a network partition occurs * Minimizing the energy variance at each node * 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 [12]. One way of battery lifetime optimization is by achieving a minimal control message overhead. [R09] 6LoWPAN routing protocol control messages SHOULD not create fragmentation of physical layer (PHY) frames. In order to save energy, routing overhead should be minimized in order to prevent fragmentation of frames on the physical layer (PHY). Therefore, 6LoWPAN routing should not cause packets to exceed the IEEE 802.25.4 frame size. This both reduces the energy Kaspar, et al. Expires May 22, 2008 [Page 12] Internet-Draft 6LoWPAN Mesh Routing Requirements November 2007 required for transmission and prevents the need for packet reassembly. [R10] 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 [10]. In case of a route-over protocol, IPv6 neighbor discovery should be operated energy- efficiently. [R11] 6LoWPAN routing protocols SHOULD be reliable despite unresponsive nodes. Many nodes in LoWPAN 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 from the lower IEEE 802.15.4 layer may be considered to enhance the power-awareness of 6LoWPAN routing protocols. 4.3. Technical Approaches Routing protocols that address the above mentioned requirements in a generic way without making use of the points below may still be suboptimal. The following reminders describe several technical ways the above stated requirements can be achieved. [T01] 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. [T02] The procedure of local repair and related control messages for intermediate nodes MAY be omitted. In order to find energy-optimal routing paths, LoWPAN mesh routing 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. [T03] One method for estimating the reliability of a node is to use Kaspar, et al. Expires May 22, 2008 [Page 13] Internet-Draft 6LoWPAN Mesh Routing Requirements November 2007 the link quality indication (LQI) provided by the MAC layer in combination with other metrics. [T04] In case a routing protocol operates in 6LoWPAN's adaptation layer, then routing tables and neighbor lists SHOULD support 16-bit short and 64-bit extended addresses. Kaspar, et al. Expires May 22, 2008 [Page 14] Internet-Draft 6LoWPAN Mesh Routing Requirements November 2007 5. Security Considerations Security issues are described in Section 4 Kaspar, et al. Expires May 22, 2008 [Page 15] Internet-Draft 6LoWPAN Mesh Routing Requirements November 2007 6. Acknowledgements The authors would like to thank Myung-Ki Shin for giving the idea of writing this draft. Kaspar, et al. Expires May 22, 2008 [Page 16] Internet-Draft 6LoWPAN Mesh Routing Requirements November 2007 7. References 7.1. Normative References [1] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997. [2] Perkins, C., Belding-Royer, E., and S. Das, "Ad hoc On-Demand Distance Vector (AODV) Routing", RFC 3561, July 2003. [3] Clausen, T. and P. Jacquet, "Optimized Link State Routing Protocol (OLSR)", RFC 3626, October 2003. [4] Nikander, P., Kempf, J., and E. Nordmark, "IPv6 Neighbor Discovery (ND) Trust Models and Threats", RFC 3756, May 2004. [5] 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. [6] Montenegro, G., Kushalnagar, N., Hui, J., and D. Culler, "Transmission of IPv6 Packets over IEEE 802.15.4 Networks", RFC 4944, September 2007. [7] IEEE Computer Society, "IEEE Std. 802.15.4-2003", October 2003. 7.2. Informative References [8] Bulusu, N. and S. Jha, "Wireless Sensor Networks", July 2005. [9] Chakrabarti, S. and S. Daniel Park, "LoWPAN Mobility Requirements and Goals, draft-chakrabarti-mobopts-lowpan-req-01 (work in progress)", March 2007. [10] Chakrabarti, S. and E. Nordmark, "LoWPAN Neighbor Discovery Extensions, draft-chakrabarti-6lowpan-ipv6-nd-03 (work in progress)", March 2007. [11] Chakeres, I., "Dynamic MANET On-demand (DYMO) Routing, draft-ietf-manet-dymo-10 (work in progress)", June 2005. [12] Pister, K. and B. Boser, "Smart Dust: Wireless Networks of Millimeter-Scale Sensor Nodes". Kaspar, et al. Expires May 22, 2008 [Page 17] Internet-Draft 6LoWPAN Mesh Routing Requirements November 2007 Authors' Addresses Dominik Kaspar ETRI 161 Gajeong-dong Yuseong-gu Daejeon 305-700 Korea Phone: +82-42-860-1072 Email: dokaspar.ietf@gmail.com Eunsook Kim ETRI 161 Gajeong-dong Yuseong-gu Daejeon 305-700 Korea Phone: +82-42-860-6124 Email: eunah.ietf@gmail.com Carsten Bormann Universitaet Bremen TZI Postfach 330440 Bremen D-28359 Germany Phone: +49-421-218-7024 Fax: +49-421-218-7000 Email: cabo@tzi.org Kaspar, et al. Expires May 22, 2008 [Page 18] Internet-Draft 6LoWPAN Mesh Routing Requirements November 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 May 22, 2008 [Page 19]