[Docs] [txt|pdf] [Tracker] [Email] [Diff1] [Diff2] [Nits]

Versions: 00 01 02 03 04 05 06 07 08

6LoWPAN Working Group                                          D. Kaspar
Internet-Draft                                                    E. Kim
Expires: January 10, 2008                                        M. Shin
                                                                  H. Kim
                                                            July 9, 2007

           Problem Statement, Design Goals and Requirements
                        for 6LoWPAN Mesh Routing

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-

   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

   The list of Internet-Draft Shadow Directories can be accessed at

   This Internet-Draft will expire on January 10, 2008.

Copyright Notice

   Copyright (C) The IETF Trust (2007).

Kaspar, et al.          Expires January 10, 2008                [Page 1]

Internet-Draft      6LoWPAN Mesh Routing Requirements          July 2007


   This document provides the problem statement for mesh routing below
   the IP layer (in 6LoWPAN's adaptation layer).  It also defines major
   design goals and requirements for 6LoWPAN mesh routing considering
   the low-power characteristics of the network and its devices.

Table of Contents

   1.  Problem Statement  . . . . . . . . . . . . . . . . . . . . . .  3
   2.  Scenario Considerations  . . . . . . . . . . . . . . . . . . .  6
   3.  LoWPAN Mesh Routing Design Goals . . . . . . . . . . . . . . .  8
     3.1.  Power Conservation . . . . . . . . . . . . . . . . . . . .  8
     3.2.  Low Protocol Complexity  . . . . . . . . . . . . . . . . .  9
     3.3.  Reliability  . . . . . . . . . . . . . . . . . . . . . . . 10
     3.4.  Mobility . . . . . . . . . . . . . . . . . . . . . . . . . 10
     3.5.  Security . . . . . . . . . . . . . . . . . . . . . . . . . 10
   4.  Requirements . . . . . . . . . . . . . . . . . . . . . . . . . 11
   5.  Security Considerations  . . . . . . . . . . . . . . . . . . . 13
   6.  References . . . . . . . . . . . . . . . . . . . . . . . . . . 14
   Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 15
   Intellectual Property and Copyright Statements . . . . . . . . . . 16

Kaspar, et al.          Expires January 10, 2008                [Page 2]

Internet-Draft      6LoWPAN Mesh Routing Requirements          July 2007

1.  Problem Statement

   Low-power wireless personal area networks (LoWPANs) are formed by
   devices complying to the IEEE 802.15.4 standard [1].  LoWPAN devices
   are distinguished by their low bandwidth, short range, scarce memory
   capacity, limited processing capability and other attributes of
   inexpensive hardware.  In this document, the characteristics of nodes
   participating in LoWPANs are assumed to be those described in [2].

   IEEE 802.15.4 networks support star and mesh topologies and consist
   of two different device types: reduced-function devices (RFDs) and
   full-function devices (FFDs).  RFDs have the most limited
   capabilities and are intended to perform only simple and basic tasks.
   RFDs may only associate with a single FFD at a time, but FFDs may
   form arbitrary topologies and accomplish more advanced functions,
   such as multi-hop routing.

   However, neither the IEEE 802.15.4 standard nor the 6LoWPAN format
   specification ("IPv6 over IEEE 802.15.4" [3]) provide any information
   as to how mesh topologies could be obtained and maintained.  Routing
   in mesh networks has been the subject of much research, also in the
   IETF.  A number of experimental protocols have been developed in the
   Mobile Ad-hoc Networks (MANET) working group, such as AODV [7], OLSR
   [8], or DYMO [9].  However, the modification/simplification of
   existing routing protocols may be required for mesh routing to be
   feasible in a LoWPAN domain, because more stringent requirements
   apply to LoWPANs than to higher performance networks.  LoWPAN nodes
   are characterized by much lower power supplies, smaller memory sizes,
   and lower processing power, which creates new challenges on obtaining
   robust and reliable mesh routing within LoWPANs.

   The 6LoWPAN problem statement document ("6LoWPAN Problems and Goals"
   [2]) briefly mentions four requirements on routing protocols; (a) low
   overhead on data packets, (b) low routing overhead, (c) minimal
   memory computation, and (d) support for sleeping nodes considering
   battery saving.  These four high-level requirements only describe the
   need for low overhead and power saving.  But, based on the
   fundamental features of LoWPAN, more detailed routing requirements
   are presented in this document, which can lead to further analysis
   and protocol design.

   The target of this document is mesh routing in the adaptation layer
   defined by the 6lowpan format document ("IPv6 over IEEE 802.15.4"
   [3]), while other efforts in the IETF concentrate on IP-layer routing
   for LoWPANs, such as the MANET working group and the current "RSN"
   mailing list.  The most significant difference is that "mesh under"
   routing is directly based on the IEEE 802.15.4 standard, therefore
   using (64-bit or 16-bit shortened) MAC addresses, instead of IP

Kaspar, et al.          Expires January 10, 2008                [Page 3]

Internet-Draft      6LoWPAN Mesh Routing Requirements          July 2007

   addresses.  On the Network Layer (L3), a LoWPAN is seen as a single
   IP link.  In case an existing L3 routing mechanism is to be applied
   to a LoWPAN, it must support this addressing scheme.  Additionally,
   because of the low-performance characteristics of LoWPANs, a light-
   weight routing protocol must be produced that meets the design goals
   and requirements presented in this document.

   Figure 1 shows the place of 6LoWPAN mesh routing in the entire
   network stack;

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

                                 Figure 1

   In order to avoid packet fragmentation and the overhead for
   reassembly, all data to be transmitted should fit into a single IEEE
   802.15.4 physical frame, as shown in Figure 2.

   Routing control packets are placed after the 6LoWPAN Dispatch.
   Multiple routing protocols can be supported by the usage of different
   Dispatch bit sequences.

Kaspar, et al.          Expires January 10, 2008                [Page 4]

Internet-Draft      6LoWPAN Mesh Routing Requirements          July 2007

   Figure 2 shows the place of 6LoWPAN mechanisms, such as mesh routing
   control packets, in the big picture of a IEEE 802.15.4 physical

  |<---------------------- PHY Protocol Data Unit -------------------->|
             |<----------- MAC Protocol Data Unit -------------------->|
                      |<-- Adaptation Layer --->|
  | PHY      | MAC    | 6LoWPAN  | 6LoWPAN      |    |     |     | MAC |
  | Preamble | Header | Dispatch | Mechanism    | IP | UDP | App | FCS |
  | & Header |        |          | (w/HC, etc.) |    |     |     |     |
  |<---6---->|<-------------------- 125 octets ----------------->|<-2->|

                                 Figure 2

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

   1.  Existing routing solutions do not operate in 6LoWPAN's adaptation
       layer (and do not support the addressing scheme defined by IEEE

   2.  The precise 6LoWPAN routing requirements must be defined.

   3.  It needs to be clarified how existing routing solutions can be
       adapted to meet the low-power requirements presented in
       Section 4.

Kaspar, et al.          Expires January 10, 2008                [Page 5]

Internet-Draft      6LoWPAN Mesh Routing Requirements          July 2007

2.  Scenario Considerations

   IP-based low-power WPAN technology is still in its early stage of
   development, but the range of conceivable usage scenarios is
   tremendous.  The numerous possible applications of sensor networks
   make it obvious that mesh topologies will be prevalent in LoWPAN
   environments and routing will be a necessity for expedient
   communication.  Research efforts in the area of sensor networking
   have put forth a large variety of multi-hop routing algorithms [4].
   Most related work focuses on optimizing routing for specific
   application scenarios, which can largely be categorized into the
   following models of communication:

   o  Flooding (may be optimal in very small networks)

   o  Data-aware routing (dissemination vs. gathering)

   o  Event-driven vs. query-based routing

   o  Geographic routing

   Depending on the topology of a LoWPAN and the application(s) running
   over it, these different types of routing may be used.  However, this
   draft abstracts from application-specific communication and fetches
   general routing requirements valid for any type of routing in

   In general, the requirements on a routing protocol are depending on
   the network architecture, the hardware parameters of the
   participating nodes and the properties of the network as a whole;

   a.  Network Properties:

       *  Device Number, Density and Network Diameter:
          These parameters directly affect the routing state (e.g. the
          number of entries in a routing table or neighbor list).
          Especially in large and dense networks, policies must be
          applied for discarding "low-quality" routing entries in order
          to prevent memory overflow.

       *  Connectivity:
          Due to external factors or programmed disconnections, a LoWPAN
          can be in several states of connectivity; anything in the
          range from "always connected" to "rarely connected".  This
          poses great challenges to the dynamic discovery of routes
          across a LoWPAN.

Kaspar, et al.          Expires January 10, 2008                [Page 6]

Internet-Draft      6LoWPAN Mesh Routing Requirements          July 2007

       *  Mobility:
          Location changes can be induced by unpredictable external
          factors or by controlled motion, which may in turn cause route
          changes.  The routing state and the volume of control messages
          is heavily dependent on the number of moving nodes in a LoWPAN
          and their speed.

       *  Deployment:
          In a LoWPAN, it is possible for nodes to be scattered randomly
          or to be deployed in an organized manner.  The deployment can
          occur at once, or as an iterative process, which may also
          affect the routing state.

       *  Network Architecture, Topology and Applications:
          The design of a LoWPAN and the requirements on its application
          have a big impact on the most efficient routing type to be
          used (data-aware routing, geographic routing, ...).

   b.  Node Parameters:

       *  Processing Speed and Memory Size:
          These basic parameters define the maximum size of the routing

       *  Power Consumption and Power Source:
          The number and topology of battery- and mains-powered nodes in
          a LoWPAN affect routing protocols in their selection of
          optimal paths for network lifetime maximization.

       *  Transmission Range, Rate and Bandwidth:
          These parameters indirectly affect routing.  For example, a
          high transmission range may cause a dense network, which in
          turn results in more direct neighbors of a node and a larger
          routing state.

Kaspar, et al.          Expires January 10, 2008                [Page 7]

Internet-Draft      6LoWPAN Mesh Routing Requirements          July 2007

3.  LoWPAN Mesh Routing Design Goals

   This section outlines the fundamental design goals, which serve to
   define the issues and to impose a list of requirements for
   forthcoming LoWPAN routing solutions.  The general design goals for
   routing are to provide a loop-free, layer-transparent, robust, and
   scalable solution.  Based on these fundamental routing goals, this
   section describes special features and goals concerning LoWPAN
   routing design.  LoWPANs have two unique properties to consider;

   o  Power conservation: some devices are mains-powered, but most are
      battery-operated and need to last several months to a few years
      with a single AA battery (see Section 3.1).

   o  Low performance: tiny devices, memory sizes, processors, etc. (see
      Section 3.2).

   These fundamental features of LoWPANs can affect the design of
   routing solutions, so that existing routing specifications should be
   simplified and modified to the smallest extent possible, in order to
   fit the low-power requirements of LoWPANs.

3.1.  Power Conservation

   Saving energy is crucially important to LoWPAN devices that are not
   mains-powered but have to rely on a depleting source, such as a
   battery.  The lifetime of a LoWPAN node depends on the energy it can
   store and harvest.  Power-aware routing is a non-trivial task,
   because it is affected by many mutually conflicting goals;

   o  Minimization of total energy consumed in the network

   o  Maximization of the time until a network partition occurs

   o  Minimizing the energy variance at each node

   o  Minimizing the cost per packet

   Compared to functions such as computational operations or taking
   sensor samples, radio communications is by far the dominant factor of
   power consumption [10].  Therefore, optimization of mesh routing
   protocols in terms of achieving a minimal number of control messages
   is essential for the longevity of battery-powered nodes.  Routing
   overhead must be minimized in order to prevent fragmentation of
   frames on the physical layer (PHY), reducing the energy required for
   transmission and preventing the need for packet reassembly.

   In order to find energy-optimal routing paths, LoWPAN mesh routing

Kaspar, et al.          Expires January 10, 2008                [Page 8]

Internet-Draft      6LoWPAN Mesh Routing Requirements          July 2007

   protocols should minimize power consumption by utilizing a
   combination of the link quality indication (LQI) provided by the MAC
   layer and other measures, such as hop count.  Route repair and route
   error messages should be avoided for minimizing the overall number of
   control messages and the required energy for sending them.

   Neighbor discovery is a major precondition to allow routing in a
   network.  Especially in a low-power environment, where nodes might be
   in periodic sleeping states, it is difficult to define whether a node
   is a neighbor of another or not.  In addition to that, LoWPAN devices
   must be very economical in terms of power consumption and should
   avoid sending "Hello" messages.  Instead, link layer mechanisms (such
   as acknowledgments or beacon responses) should be utilized to keep
   track of active neighbors.  Neighbor discovery for LoWPANs is
   described more detailed in [6].

   Transparent IP routing between LoWPAN domains and higher layer
   networks must be provided bidirectionally.  A LoWPAN mesh routing
   protocol must allow for gateways to forward packets out of the local
   domain and it must be possible to query a LoWPAN device from outside
   of the local domain.  Strategies must be considered to avoid battery
   depletion of nodes by too many queries from higher level networks.
   End-to-end communication is not a design goal of LoWPAN.

3.2.  Low Protocol Complexity

   A routing protocol of low complexity certainly assists to achieve the
   previously described goal of reducing power consumption.  However,
   this section's focus is on designing a LoWPAN protocol that is
   robust, easy to analyze and implicitly less prone to security
   attacks.  A LoWPAN routing protocol solution should consider the
   limited memory size and computation capabilities of participating
   devices.  And even though implementation details are out of IETF
   scope, due to the hardware restrictions of LoWPAN devices, code
   length should be considered to fit within their small memory size.

   Because network layer routing imposes too much overhead for LoWPANs
   and link layer techniques are out of scope of IETF, LoWPAN mesh
   routing should be performed within the adaptation layer defined in
   [3].  Both addressing modes provided by the IEEE 802.15.4 standard,
   16-bit short addresses and 64-bit extended addresses, must be
   considered by LoWPAN mesh routing protocols.  It is also assumed that
   nodes participating in LoWPAN mesh routing are assigned only a single
   address/identifier and do not support multiple interfaces.

   A LoWPAN routing protocol should be designed to minimize the required
   memory size, computational and algorithmical complexity.  Possible
   techniques might include the reduction of routing tables or omission

Kaspar, et al.          Expires January 10, 2008                [Page 9]

Internet-Draft      6LoWPAN Mesh Routing Requirements          July 2007

   local repair procedures.

3.3.  Reliability

   Another important trait of LoWPAN devices is their unreliability due
   to limited system capabilities, and also because they might be
   closely coupled to the physical world with all its unpredictable
   variation, noise, and asynchrony.  It is predicted that LoWPANs will
   be comprised of significantly higher numbers of devices than counted
   in current networks, causing user interaction and maintenance to
   become impractical and therefore requiring robustness and self-
   healing capabilities in their fundamental network structure.  The
   design of mesh routing protocols must consider the fact that packets
   are to be reliably delivered over a much higher number of hops, too.
   Mesh routing must be robust to unreliable nodes.  One method for
   estimating the reliability of a node is to use the link quality
   indication (LQI) provided by the MAC layer in combination with other

   The required reliability is heavily dependent on the individual
   application scenario and the LoWPAN architecture.

3.4.  Mobility

   Routing must be functional both in fixed and dynamically adaptive
   topologies.  Mesh networks are likely to consist of nodes with a
   certain degree of mobility.  Due to the low performance
   characteristics of LoWPAN devices, mobility support should be
   provided for unmodified nodes.  Fast mobility detection will be a
   huge challenge and LoWPAN nodes might even change their location
   while being in state of hibernation.  Routing must be robust and
   remain energy-efficient in all such cases.  The detailed mobility
   requirements and goals are described in [5].  Also, as recently seen
   in discussions related to MANEMO (Network mobility for MANET), a
   similar point was stated regarding network mobility in LoWPAN

   The required mobility is heavily dependent on the individual
   application scenario and the LoWPAN architecture.

3.5.  Security

   Security threats within LoWPANs may be different from existing threat
   models in ad-hoc network environments.  Neighbor Discovery in IEEE
   802.15.4 links may be susceptible to threats as listed in RFC3756
   [11].  Bootstrapping may also impose additional threats.
   Nevertheless, security should not cause significant transmission

Kaspar, et al.          Expires January 10, 2008               [Page 10]

Internet-Draft      6LoWPAN Mesh Routing Requirements          July 2007

4.  Requirements

   This section lists the requirements on mesh routing protocols for

      R01: 6LoWPAN routing MUST be performed in the adaptation layer, as
      defined in [3].

      R02: Both addressing modes, 16-bit short addresses and 64-bit
      extended addresses MUST be supported.

      R03: Protocol control messages SHOULD not create fragmentation of
      physical layer (PHY) layer frames.

      R04: 6LoWPAN routing protocols SHOULD keep power consumption at a
      minimum.  PHY/MAC-layer indicators (such as LQI) SHOULD be matched
      with other metrics (such as hop count) for route decisions.

      R05: Routing solutions SHOULD be simple and of low computational

         R05.1: Operation with low routing state (such as routing tables
         and neighbor lists) SHOULD be maintained.  For example, devices
         may have only 32 forwarding entries available.

         R05.2: Routing tables and neighbor lists SHOULD support 16-bit
         short and 64-bit extended addresses.

         R05.3: Code length SHOULD be considered to fit within LoWPAN
         devices' small memory size.

      R06: 6LoWPAN routing protocols MUST be loop-free.

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

      R08: 6LoWPAN routing protocols SHOULD be robust and SHOULD work
      independent of unresponsive nodes.

      R09: The solution SHOULD allow for dynamically adaptive topologies
      and nodes changing their location.

      R10: The routing solution(s) SHOULD be scalable.

      R11: The procedure of local repair and related control messages
      for intermediate nodes MAY be omitted.

Kaspar, et al.          Expires January 10, 2008               [Page 11]

Internet-Draft      6LoWPAN Mesh Routing Requirements          July 2007

      R12: Protocol control messages MAY be secured.

      R13: A 6loWPAN routing protocol MAY allow for gateways to forward
      packets out of the local domain and it MAY be possible to query a
      6LoWPAN device from outside of the local domain.

Kaspar, et al.          Expires January 10, 2008               [Page 12]

Internet-Draft      6LoWPAN Mesh Routing Requirements          July 2007

5.  Security Considerations

   Security issues are handled as described in Section 3.5

Kaspar, et al.          Expires January 10, 2008               [Page 13]

Internet-Draft      6LoWPAN Mesh Routing Requirements          July 2007

6.  References

   [1]   IEEE Computer Society, "IEEE Std. 802.15.4-2003", October 2003.

   [2]   Kushalnagar, N., Montenegro, G., and C. Schumacher, "6LoWPAN:
         Overview, Assumptions, Problem Statement and Goals,
         draft-ietf-6lowpan-problem-08 (work in progress)",
         February 2007.

   [3]   Montenegro, G., Kushalnagar, N., Hui, J., and D. Culler,
         "Transmission of IPv6 Packets over IEEE 802.15.4 Networks,
         draft-ietf-6lowpan-format-13 (work in progress)", October 2005.

   [4]   Bulusu, N. and S. Jha, "Wireless Sensor Networks", July 2005.

   [5]   Chakrabarti, S. and S. Daniel Park, "LoWPAN Mobility
         Requirements and Goals, draft-chakrabarti-mobopts-lowpan-req-01
         (work in progress)", March 2007.

   [6]   Chakrabarti, S. and E. Nordmark, "LoWPAN Neighbor Discovery
         Extensions, draft-chakrabarti-6lowpan-ipv6-nd-03 (work in
         progress)", March 2007.

   [7]   Perkins, C., Belding-Royer, E., and S. Das, "Ad hoc On-Demand
         Distance Vector (AODV) Routing", RFC 3561, July 2003.

   [8]   Clausen, T. and P. Jacquet, "Optimized Link State Routing
         Protocol (OLSR)", RFC 3626, October 2003.

   [9]   Chakeres, I., "Dynamic MANET On-demand (DYMO) Routing,
         draft-ietf-manet-dymo-06 (work in progress)", June 2005.

   [10]  Pfister, K. and B. Boser, "Smart Dust: Wireless Networks of
         Millimeter-Scale Sensor Nodes".

   [11]  Nikander, P., Kempf, J., and E. Nordmark, "IPv6 Neighbor
         Discovery (ND) Trust Models and Threats", RFC 3756, May 2004.

Kaspar, et al.          Expires January 10, 2008               [Page 14]

Internet-Draft      6LoWPAN Mesh Routing Requirements          July 2007

Authors' Addresses

   Dominik Kaspar
   161 Gajeong-dong
   Daejeon  305-700

   Phone: +82-42-860-1072
   Email: dominik@etri.re.kr

   Eunsook Kim
   161 Gajeong-dong
   Daejeon  305-700

   Phone: +82-42-860-6124
   Email: eunah@etri.re.kr

   Myungki Shin
   161 Gajeong-dong
   Daejeon  305-700

   Phone: +82-42-860-4847
   Email: mkshin@etri.re.kr

   Hyoungjun Kim
   161 Gajeong-dong
   Daejeon  305-700

   Phone: +82-42-860-6576
   Email: hjk@etri.re.kr

Kaspar, et al.          Expires January 10, 2008               [Page 15]

Internet-Draft      6LoWPAN Mesh Routing Requirements          July 2007

Full Copyright Statement

   Copyright (C) The IETF Trust (2007).

   This document is subject to the rights, licenses and restrictions
   contained in BCP 78, and except as set forth therein, the authors
   retain all their rights.

   This document and the information contained herein are provided on an

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

   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


   Funding for the RFC Editor function is provided by the IETF
   Administrative Support Activity (IASA).

Kaspar, et al.          Expires January 10, 2008               [Page 16]

Html markup produced by rfcmarkup 1.129d, available from https://tools.ietf.org/tools/rfcmarkup/