6LoWPAN Working Group D. Kaspar Internet-Draft E. Kim Expires: September 29, 2007 M. Shin H. Kim ETRI / PEC March 28, 2007 Design Goals and Requirements for 6LoWPAN Mesh Routing draft-dokaspar-6lowpan-routreq-01 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 September 29, 2007. Copyright Notice Copyright (C) The IETF Trust (2007). Kaspar, et al. Expires September 29, 2007 [Page 1] Internet-Draft 6LoWPAN Mesh Routing Requirements March 2007 Abstract This document defines the problem statement, design goals, and requirements for mesh routing in low-power wireless personal area networks (LoWPANs). Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.1. Scenario Considerations . . . . . . . . . . . . . . . . . 3 2. Problem Statement . . . . . . . . . . . . . . . . . . . . . . 5 3. LoWPAN Mesh Routing Design Goals . . . . . . . . . . . . . . . 6 3.1. Power Conservation . . . . . . . . . . . . . . . . . . . . 6 3.2. Low Protocol Complexity . . . . . . . . . . . . . . . . . 7 3.3. Reliability . . . . . . . . . . . . . . . . . . . . . . . 8 3.4. Mobility . . . . . . . . . . . . . . . . . . . . . . . . . 8 3.5. Security . . . . . . . . . . . . . . . . . . . . . . . . . 8 4. Requirements . . . . . . . . . . . . . . . . . . . . . . . . . 9 5. Analysis of Existing Mesh Routing Candidates . . . . . . . . . 11 6. Security Considerations . . . . . . . . . . . . . . . . . . . 12 7. References . . . . . . . . . . . . . . . . . . . . . . . . . . 13 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 14 Intellectual Property and Copyright Statements . . . . . . . . . . 15 Kaspar, et al. Expires September 29, 2007 [Page 2] Internet-Draft 6LoWPAN Mesh Routing Requirements March 2007 1. Introduction Low-power wireless personal area networks (LoWPANs) are formed by devices complying to the IEEE 802.15.4 standard [1]. LoWPAN devices are distinguished by their low bandwidth, short range, scarce memory capacity, limited processing capability and other attributes of inexpensive hardware. In this document, the characteristics of nodes participating in LoWPANs are assumed to be those described in [2]. IEEE 802.15.4 networks support star and mesh topologies and consist of two different device types: reduced-function devices (RFDs) and full-function devices (FFDs). RFDs have the most limited capabilities and are intended to perform only simple and basic tasks. RFDs may only associate with a single FFD at a time, but FFDs may form arbitrary topologies among each other and accomplish more advanced functions, such as multi-hop routing. Neither the IEEE 802.15.4 standard nor the "IPv6 over IEEE 802.15.4" [3] specification provide any information as to how mesh topologies could be obtained and maintained. However, routing in mesh networks has been the subject of much research in the IETF. A number of experimental protocols have been developed in the Mobile Ad-hoc Networks (MANET) working group, such as AODV [6], OLSR [7], or DYMO [8]. This document defines the problem statement of mesh routing in LoWPAN environments and outlines the relevant design goals and requirements. 1.1. Scenario Considerations 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. In general, the requirements on a routing protocol are depending on the network architecture - the hardware parameters of the participating nodes and the properties of the network; 1. Network properties: * Device number and density * Network scale and topology * Mobility issues Kaspar, et al. Expires September 29, 2007 [Page 3] Internet-Draft 6LoWPAN Mesh Routing Requirements March 2007 * ... etc. 2. Node parameters: * Physical dimensions * Hardware Cost * Processing speed and memory size * Power consumption and source * Transmission range, rate and bandwidth * ... etc. Network properties may vary arbitrarily for application scenarios in both LoWPAN or MANET contexts. For instance, even though LoWPANs are often regarded as more dense and consisting of more nodes than MANET networks, it might as well occur that a MANET consists of more devices than a LoWPAN. On the other hand, the node parameters themselves define whether a certain node is a LoWPAN device, a MANET device or neither of both. The classification boundaries are only vaguely defined and heavily depend on the LoWPAN architecture. However, it is perceivable that LoWPAN devices enable services that MANET devices can not provide because of their nature of being more expensive, occupying greater physical space or requiring too much battery power. We might think that the characteristics of LoWPANs are device features only, but they enable a whole new segment of services that MANET devices are not necessarily able to satisfy. Kaspar, et al. Expires September 29, 2007 [Page 4] Internet-Draft 6LoWPAN Mesh Routing Requirements March 2007 2. Problem Statement If possible, the easiest way to achieve LoWPAN mesh routing is by reusing existing MANET protocols without making any modifications. However, the modification or simplification of existing MANET routing protocols may be required for mesh routing to be feasible in a LoWPAN domain, because other requirements apply to LoWPAN devices. Unlike MANET devices, LoWPAN nodes are characterized by much lower power supplies, smaller memory sizes, and lower processing power, which creates new challenges on obtaining robust and reliable mesh routing within LoWPANs. There exists a trade-off relationship between routing effectiveness and the requirements posed upon the devices participating in a mesh network. The challenge is to create a balance between protocol simplicity and routing performance. But stripping down existing protocols to power-aware, low-overhead protocols decreases the efficacy and functionality of their sophisticated routing techniques, or possibly even endangers the goals they were designed for. The document "6LoWPAN Problems and Goals" [2] briefly mentions four requirements on the routing protocol in the section 4.2; low overhead on data packets, low routing overhead, minimal memory computation, and support for sleeping nodes considering battery saving. These high-level requirements only describe low overhead and power saving. Based on these fundamental features of LoWPAN routing, more detailed requirements need to be considered, which can lead to protocol design and analysis. Kaspar, et al. Expires September 29, 2007 [Page 5] Internet-Draft 6LoWPAN Mesh Routing Requirements March 2007 3. LoWPAN Mesh Routing Design Goals This section outlines the fundamental design goals, which serve to define the issues and to impose a list of requirements for forthcoming LoWPAN routing solutions. The general design goals for routing are to provide a loop-free, transparent to lower and upper layers, and robust and scalable solution. Based on these fundamental routing goals, this section describes special features and goals concerning LoWPAN routing design. If the application of MANET routing protocols is feasible in LoWPAN environments, the reuse of existing solutions must be considered. However, LoWPANs have two unique goals to consider; o Power conservation: some devices are mains-powered, but most are battery-operated and needed to last several months to a few years with single AA battery Section 3.1. o Hardware miniaturization: tiny devices, memory sizes, and/or processors Section 3.2. These fundamental features of LoWPANs can affect the design of routing solutions, so that existing specifications from MANET should be simplified and modified to the smallest extent possible, in order to fit the low-power requirements of LoWPANs. 3.1. Power Conservation Saving energy is crucially important to LoWPAN devices that are not mains-powered but have to rely on a depleting source, such as a battery. The lifetime of a LoWPAN node depends on the energy it can store and harvest. Compared to functions such as computational operations or taking sensor samples, radio communications is by far the dominant factor of power consumption [9]. Therefore, optimization of mesh routing protocols in terms of achieving a minimal number of control messages is essential for the longevity of battery-powered nodes. Routing overhead must be minimized in order to prevent fragmentation of frames on the physical layer (PHY), reducing the energy required for transmission and preventing the need for packet reassembly. In order to find energy-optimal routing paths, LoWPAN mesh routing 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. Kaspar, et al. Expires September 29, 2007 [Page 6] Internet-Draft 6LoWPAN Mesh Routing Requirements March 2007 Many nodes in LoWPAN environments might periodically hibernate (i.e. disable their transceiver activity) to save energy. Therefore, mesh routing protocols must ensure robust packet delivery despite of nodes frequently shutting off their radio transmission interface. Neighbor discovery is a major precondition to allow routing in a network. Especially in a low-power environment, where nodes might be in periodic sleeping states, it is difficult to define whether a node is a neighbor of another or not. In addition to that, LoWPAN devices must be very economical in terms of power consumption and should avoid sending "Hello" messages. Instead, link layer mechanisms (such as acknowledgments or beacon responses) could be utilized to keep track of active neighbors. Neighbor discovery for LoWPANs is described more detailed in [5]. Transparent IP routing between LoWPAN domains and higher layer networks must be provided bidirectionally. A LoWPAN mesh routing protocol must allow for gateways to forward packets out of the local domain and it must be possible to query a LoWPAN device from outside of the local domain. Strategies must be considered to avoid battery depletion of nodes by too many queries from higher level networks. End-to-end communication is not a design goal of LoWPAN. 3.2. Low Protocol Complexity A routing protocol of low complexity certainly assists to achieve the previously described goal of reducing power consumption. However, this section's focus is on designing a LoWPAN protocol that is robust, easy to analyze and implicitly less prone to security attacks. A LoWPAN routing protocol solution MUST consider the limited memory size and computation capabilities of participating devices. And even though implementation details are out of IETF scope, due to the hardware restrictions of LoWPAN devices, code length SHOULD be considered to fit within their small memory size. Because network layer routing imposes too much overhead for LoWPANs and link layer techniques are out of scope of IETF, LoWPAN mesh routing should be performed within the adaptation layer defined in [3]. Both addressing modes provided by the IEEE 802.15.4 standard, 16 bit short addresses and 64 bit extended addresses, must be considered by LoWPAN mesh routing protocols. It is also assumed that nodes participating in LoWPAN mesh routing are assigned only a single address/identifier and do not support multiple interfaces. A LoWPAN routing protocol should be designed to minimize the required memory size, computational and algorithmical complexity. Possible techniques might include the omission of routing tables or local repair procedures, but the actual details are left to the protocol Kaspar, et al. Expires September 29, 2007 [Page 7] Internet-Draft 6LoWPAN Mesh Routing Requirements March 2007 designers. 3.3. Reliability Another important characteristic of LoWPAN devices is their unreliability due to limited system capabilities, and also because they might be closely coupled to the physical world with all its unpredictable variation, noise, and asynchrony. It is predicted that LoWPANs will be comprised of significantly higher numbers of devices than counted in current networks, causing user interaction and maintenance to become impractical and therefore requiring robustness and self-healing capabilities in their fundamental network structure. The design of mesh routing protocols must consider the fact that packets are to be reliably delivered over a much higher number of hops, too. Mesh routing must be aware of unreliable nodes. One method to estimate the reliability of a node is to use the link quality indication (LQI) provided by the MAC layer in combination with other indicators. The required reliability is heavily dependent on the individual service scenario and the LoWPAN architecture. 3.4. Mobility Routing must be allowed both for fixed and dynamically adaptive topologies. Mesh networks are likely to consist of nodes with a certain degree of mobility. Due to the low performance characteristics of LoWPAN devices, mobility support should be provided for unmodified nodes. Fast mobility detection will be a huge challenge and LoWPAN nodes might even change their location while being in state of hibernation. Routing must be robust and remain energy- efficient in all such cases. The detailed mobility requirements and goals are described in [4]. Also, as recently seen in discussions related to MANEMO (Network mobility for MANET), a similar point was stated regarding network mobility in LoWPAN environments. The required mobility is heavily dependent on the individual service scenario and the LoWPAN architecture. 3.5. Security Security threats within LoWPANs may be different from existing threat models in MANET environments. Neighbor Discovery in IEEE 802.15.4 links may be susceptible to threats as listed in RFC3756 [10]. Bootstrapping may also impose additional threats. Nevertheless, security should not cause significant transmission overhead. Kaspar, et al. Expires September 29, 2007 [Page 8] Internet-Draft 6LoWPAN Mesh Routing Requirements March 2007 4. Requirements This section lists the requirements on mesh routing protocols for LoWPANs. The first few of these requirements are rather unique to LoWPANs and might not be required in other networks; R01: Existing MANET protocols (e.g., AODV, OLSR, DYMO) SHOULD be reused. R02: 6LoWPAN routing MUST be performed in the adaptation layer, as defined in [3]. R03: Protocol control messages MUST not create fragmentation of physical layer (PHY) layer frames. R04: 6LoWPAN routing protocols MUST keep power consumption at a minimum. The LQI (Link Quality Indicator) provided by the MAC layer MUST be matched with other indicators to make good decisions on route calculation. R05: The solution MUST be simple and of low complexity. R05.1: Operating with low routing state SHOULD be maintained (e.g., devices may have only 32 forwarding entries available). R06: Code length SHOULD be considered to fit within LoWPAN devices' small memory size. R07: Both addressing modes, 16 bit short addresses and 64 bit extended addresses MUST be supported. R08: For neighbor discovery, 6LoWPAN devices MUST avoid sending "Hello" messages to check on periodic sleeping states. Instead, link layer mechanisms (such as acknowledgments or beacon responses) SHOULD be utilized to keep track of active neighbors. More general requirements, important for LoWPANs, are listed below. Many of these requirements are dependent on the 6LoWPAN architecture; R09: The procedure of local repair and related control messages (e.g., Route Error Messages) MAY be omitted. R10: A 6loWPAN routing protocol MUST allow for gateways to forward packets out of the local domain and it MUST be possible to query a 6LoWPAN device from outside of the local domain. R11: 6LoWPAN routing protocols MUST be robust and SHOULD work independent of the sleep schedule (e.g., flooding) of hibernating Kaspar, et al. Expires September 29, 2007 [Page 9] Internet-Draft 6LoWPAN Mesh Routing Requirements March 2007 nodes. R12: Bootstrapping mechanisms MAY be a prerequisite for 6LowPAN routing. R13: The solution MUST allow for dynamically adaptive topologies. It may support local mobility and global mobility. R14: The solution MUST be as highly scalable as defined by the LoWPAN architecture (e.g. a large geography). R15: Protocol control messages MUST be secured. L2 (WEP-like) security might be enough. Kaspar, et al. Expires September 29, 2007 [Page 10] Internet-Draft 6LoWPAN Mesh Routing Requirements March 2007 5. Analysis of Existing Mesh Routing Candidates This section is still to be defined. An objective analysis on existing MANET routing protocols should be carried out to evaluate their suitability within LoWPANs. Kaspar, et al. Expires September 29, 2007 [Page 11] Internet-Draft 6LoWPAN Mesh Routing Requirements March 2007 6. Security Considerations Security issues are handled as described in Section 3.5 Kaspar, et al. Expires September 29, 2007 [Page 12] Internet-Draft 6LoWPAN Mesh Routing Requirements March 2007 7. References [1] IEEE Computer Society, "IEEE Std. 802.15.4-2003", October 2003. [2] Kushalnagar, N., Montenegro, G., and C. Schumacher, "6LoWPAN: Overview, Assumptions, Problem Statement and Goals, draft-ietf-6lowpan-problem-07 (work in progress)", February 2007. [3] Montenegro, G., Kushalnagar, N., Hui, J., and D. Culler, "Transmission of IPv6 Packets over IEEE 802.15.4 Networks, draft-ietf-6lowpan-format-10 (work in progress)", October 2005. [4] Chakrabarti, S. and S. Daniel Park, "LoWPAN Mobility Requirements and Goals, draft-chakrabarti-mobopts-lowpan-req-01 (work in progress)", March 2007. [5] Chakrabarti, S. and E. Nordmark, "LoWPAN Neighbor Discovery Extensions, draft-chakrabarti-6lowpan-ipv6-nd-03 (work in progress)", March 2007. [6] Perkins, C., Belding-Royer, E., and S. Das, "Ad hoc On-Demand Distance Vector (AODV) Routing", RFC 3561, July 2003. [7] Clausen, T. and P. Jacquet, "Optimized Link State Routing Protocol (OLSR)", RFC 3626, October 2003. [8] Chakeres, I., "Dynamic MANET On-demand (DYMO) Routing, draft-ietf-manet-dymo-06 (work in progress)", June 2005. [9] Pfister, K. and B. Boser, "Smart Dust: Wireless Networks of Millimeter-Scale Sensor Nodes". [10] Nikander, P., Kempf, J., and E. Nordmark, "IPv6 Neighbor Discovery (ND) Trust Models and Threats", RFC 3756, May 2004. [11] Bradner, S., "Intellectual Property Rights in IETF Technology", BCP 79, RFC 3979, March 2005. Kaspar, et al. Expires September 29, 2007 [Page 13] Internet-Draft 6LoWPAN Mesh Routing Requirements March 2007 Authors' Addresses Dominik Kaspar ETRI / PEC 161 Gajeong-dong Yuseong-gu Daejeon 305-700 Korea Phone: +82-42-860-1072 Email: dominik@etri.re.kr Eunsook Kim ETRI / PEC 161 Gajeong-dong Yuseong-gu Daejeon 305-700 Korea Phone: +82-42-860-6124 Email: eunah@etri.re.kr Myungki Shin ETRI / PEC 161 Gajeong-dong Yuseong-gu Daejeon 305-700 Korea Phone: +82-42-860-4847 Email: mkshin@etri.re.kr Hyoungjun Kim ETRI / PEC 161 Gajeong-dong Yuseong-gu Daejeon 305-700 Korea Phone: +82-42-860-6576 Email: hjk@etri.re.kr Kaspar, et al. Expires September 29, 2007 [Page 14] Internet-Draft 6LoWPAN Mesh Routing Requirements March 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 September 29, 2007 [Page 15]