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

Versions: 00 01

Network Working Group                                        K. Kim, Ed.
Internet-Draft                                                    S. Yoo
Expires: January 10, 2006                                        J. Park
                                                         Ajou University
                                                     S. Daniel Park, Ed.
                                                     SAMSUNG Electronics
                                                                  J. Lee
                                                                     NCA
                                                            July 9, 2005


               Hierarchical Routing over 6LoWPAN (HiLow)
         draft-daniel-6lowpan-hilow-hierarchical-routing-00.txt

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 10, 2006.

Copyright Notice

   Copyright (C) The Internet Society (2005).

Abstract

   The EUI-64 identifier of a 6LoWPAN device can be used as the





Kim, et al.             Expires January 10, 2006                [Page 1]


Internet-Draft                    HiLow                        July 2005


   interface identifier of the IPv6 address, which can be used for for
   on-demand multi-hop routing in 6LoWPAN.  One of the distinctive
   feature of 6LoWPAN is the capability of the dynamic assignment of 16-
   bit short addresses.  By utilizing this dynamically assigned  short
   address, a hierarchical routing can be employed.  This document
   defines a dynamic address assignment scheme and  hierarchical routing
   (HiLow) based on the assignment.

Table of Contents

   1.  Introduction . . . . . . . . . . . . . . . . . . . . . . . . .  3
   2.  Terminology  . . . . . . . . . . . . . . . . . . . . . . . . .  3
     2.1   Requirements notation  . . . . . . . . . . . . . . . . . .  4
   3.  Data Structures  . . . . . . . . . . . . . . . . . . . . . . .  5
     3.1   Neighbor Table Entry . . . . . . . . . . . . . . . . . . .  5
   4.  Message Formats  . . . . . . . . . . . . . . . . . . . . . . .  5
   5.  Dynamic Address Assignment for Hierarchical Routing  . . . . .  6
   6.  Routing Operations . . . . . . . . . . . . . . . . . . . . . .  8
   7.  Route Maintenance  . . . . . . . . . . . . . . . . . . . . . .  8
   8.  Interoperability . . . . . . . . . . . . . . . . . . . . . . .  9
   9.  IANA Consideration . . . . . . . . . . . . . . . . . . . . . .  9
   10.   Security Considerations  . . . . . . . . . . . . . . . . . .  9
   11.   Acknowledgments  . . . . . . . . . . . . . . . . . . . . . .  9
   12.   References . . . . . . . . . . . . . . . . . . . . . . . . .  9
       Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . 10
       Intellectual Property and Copyright Statements . . . . . . . . 12

























Kim, et al.             Expires January 10, 2006                [Page 2]


Internet-Draft                    HiLow                        July 2005


1.  Introduction

   6LowPAN is a low-power wireless personal area network(LoWPAN)  which
   is comprised of the IEEE  802.15.4-2003 standard[ieee802.15.4]
   devices.  In [I-D.montenegro-lowpan-ipv6-over-802.15.4], the interface
   identifier [RFC3513] for a 6LoWPAN device is based on the EUI-64
   [EUI64] address.  The interface identifier can be used for
   constructing routing tables for multi-hop routing in 6LoWPAN.
   However, considering the limited capabilities (low power, limited
   memory space, and small packet size) of 6LoWPAN devices and the large
   number of devices which is expected to be deployed in 6LoWPAN, the
   on-demand multi-hop routing with the use of the routing table and the
   EUI-64 identifier may have limitations of the scalability.

   One of the distinctive feature of 6LoWPAN is the capability of the
   dynamic assignment of 16-bit short addresses.  By utilizing this
   short address, hierarchical routing can be employed.  Even though
   hierarchical routing produces a sub-optimal routing path, it can
   significantly reduce the overhead of maintaining routing tables.

   This document defines a dynamic address assignment scheme and
   Hierarchical routing for 6LoWPAN (HiLow) based on the assignment.

2.  Terminology

      Association
         A IEEE 802.15.4 device can be assigned a dynamic 16 bit short
         address during an association operation with a neighbor device
         (or router) which is also called a parent.  After getting the
         short address, a device can communicate with its parent or
         child by using only the assigned short address.

      Coordinator
         A full-function device (FFD) which is the principal controller
         of a 6LoWPAN.  It is also called as PAN coordinator.  It MAY
         initiate the synchronization of the entire 6LoWPAN by
         transmitting beacons.

      Current Node
         When a node, a IEEE 802.15.4 device in a 6LoWPAN, receives a
         IPv6 packet, the node is called the current node in this
         document.

      Depth (D)
         The hop distance from the coordinator of a 6LoWPAN to the
         device.        The depth of the coordinator is 0.





Kim, et al.             Expires January 10, 2006                [Page 3]


Internet-Draft                    HiLow                        July 2005



      Disassociation
         The disassociation operation removes an existing association
         with its neighbor device.

      End Device
         RFD or FFD in a 6LoWPAN, which is neither the coordinator nor a
         router.

      Full Function Device (FFD)
         A device implementing the complete protocol set of IEEE
         802.15.4.  It is capable of operating as a router (multi-hop
         packet forwarding) for its associated neighbors.

      Maximum Number of Children (MC)
         The maximum number of children which a parent can have.

      Neighbor Table
         A node maintains the neighbor table which has the information
         of neighbor devices in its personal operating space.

      PAN Id
         The 16 bit 6LoWPAN identifier which is administratively
         assigned to a 6LoWPAN.

      Personal Operating Space (POS)
         The area within the reception range of the wireless
         transmission of a IEEE 802.15.4 packet.

      Reduced Function Device (RFD)
         The IEEE 802.15.4 device of 6LoWPAN which does not have enough
         power and memory space for maintaining a routing table.

      Router
         a FFD which has the capability of routing packets to the next
         hop device in 6LoWPAN.

      (Short) Address
         A 16 bit address dynamically assigned to a device from its
         parent.  The short address is assumed if only 'address' is used
         in this document.


2.1  Requirements notation

   The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
   "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
   document are to be interpreted as described in [RFC2119].



Kim, et al.             Expires January 10, 2006                [Page 4]


Internet-Draft                    HiLow                        July 2005


3.  Data Structures

3.1  Neighbor Table Entry

   The neighbor table includes the following entries:

      o   PANId (16 bits)

      o   Neighbor.16 bit short address (16 bits)

      o   Neighbor.IEEE EUI 64 bit address (64 bits)

      o   Neighbor.Device type (2 bits)
         00 : Coordinator
         01 : Router
         10 : End device
         11 : Reserved

      o   Neighbor.Relationship (2 bits)
         00 : Parent
         01 : Child
         10-11 : Reserved

      o   Neighbor.Depth (8 bits)


4.  Message Formats

   This document assumes that the multi-hop routing occurs in the
   adaptation layer by following the message format of [I-D.montenegro-
   lowpan-ipv6-over-802.15.4].  The following shows the message format
   used for the hierarchical routing.

   0                   1                   2                   3
   0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   | LF|prot_type|M|  Final Destination            |  IPv6 packet  |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
          <Fig. 1. Unfragmented encapsulation header format>

   LF:
      This 2 bit field SHALL specify the relative position of the link
      fragment, as encoded by the following table.








Kim, et al.             Expires January 10, 2006                [Page 5]


Internet-Draft                    HiLow                        July 2005


      00 Unfragmented
      11 Interior Fragment

   prot_type :
      This 7 bit field is present in the link fragment.

   M :
      This bit is used to signal whether there is a "Final Destination"
      field as used for the ad hoc mesh routing or the hierarchical
      routing.  If set to 1, the "Final Destination" field precedes the
      IPv6 packet.


   The "Final Destination" field is defined as follows:

   0                   1                   2                   3
   0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |S| Hops Left   |      Address of final destination             |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
              <Fig. 2. Final Destination Field>


      S:
         This field is 0 if the Address field is EUI 64 bit, or 1 if the
         final destination is 16 bit short.
      Hops Left:
         This 7 bit field SHALL be decremented by each forwarding node
         before sending this packet towards its next hop.  The packet is
         discarded if Hops Left is decremented to 0.
      Address:
         This is the final destination's link-layer address which is
         either 16 bit short or EUI 64.

5.  Dynamic Address Assignment for Hierarchical Routing

   One of the distinct features of 6LoWPAN is allowing dynamic
   configuration of the 16 bit short address in the MAC layer.  In
   addition to the EUI-64 address, a IEEE 802.15.4 device can be
   assigned a 16-bit short address after completing the association
   operation with its parent (or router).  This section describes the
   assignment of the dynamic address for the hierarchical routing which
   is specified in the next section.

   When a IEEE 802.15.4 device (or child) want to join a 6LoWPAN, it
   first tries to discover an existing 6LoWPAN.  IEEE 802.15.4 specifies
   active and passive scanning procedures for this discovery operation.
   By following either one of the scanning procedures, the child device



Kim, et al.             Expires January 10, 2006                [Page 6]


Internet-Draft                    HiLow                        July 2005


   determines whether there is a 6LoWPAN in its POS.  If there is no
   6LoWPAN in its POS, the child device becomes the initiator (or
   coordinator ) of a new 6LoWPAN and assigns it's short address by 0.
   Otherwise, the child device can find an existing neighbor device (or
   parent) which is already a member of the 6LoWPAN.  After finding a
   parent, the child tries to associate with the parent at the IEEE
   802.15.4 MAC layer, and receives a 16 bit short address from the
   parent if the association is successful.

   A parent assigns a 16 bit short address to a child by the assignment
   scheme described in Fig. 3.  The scheme requires one parameter, MC,
   the maximum number of children a parent can have.  If the parent does
   not have any child before this association, the new child becomes the
   first child and receives a short address by the following fomular:

   FC = MC * AP + 1

   , where FC is the first child address, and AP is the address of the
   parent.

   If the new child is not the first child of the parent, it receives
   the maximum address of the existing children of the parent plus one.
   For this assignment a router SHOULD maintain a neighbor table which
   has the information about it's children and parent.

   MC = 4

                       (0)              <= Coordinator
                     //   \\
                   /  |   |  \
                 /   /     \   \
               (1) (2)    (3)  (4)        <= Routers
              // \\ ......... // \\
           /  /   \ \       / /   \  \
         (5) (6) (7)(8)..(17)(18)(19)(20)
                        // \\
                     /  /   \  \
       ...........(69) (70)(71) (72)........

              <Fig. 3. The assignment scheme of the short address>

   By the nature of the scheme, it has no depth limitation and is
   efficient for gradually incremental networks.  The only parameter,
   MC, specifies the maximum number of children a router can have.  This
   scheme conforms well to the homogeneous 6LoWPAN in which the density
   of the devices is almost constant in the entire network.  The future
   revision of this draft will include the enhancement of adapting to
   the heterogeneous 6LoWPAN which has some high density areas and some



Kim, et al.             Expires January 10, 2006                [Page 7]


Internet-Draft                    HiLow                        July 2005


   low density areas in the network by relaxing NC.

6.  Routing Operations

   For the routing operation, the following symbols are defined.

   D   :   the destination
   C   :   the current node
   AC :  the address of the current node
   AP :  the address of the parent of the current node
   SA :  the set of the ascendant nodes of the destination
   SD :  the set of the descendant nodes of the destination
   AA (D, k) :  the address of the ascendant node of depth D of the node
      k
   DD : the depth of the destination
   DC : the depth of the current node

   First of all, it is assumed that every node knows it's own depth.
   When a node receives an IPv6 packet, it is called the current node as
   described in the teminology section.  The address of the parent of
   the current node, AP, can be calculated as follows:

   AP = [(AC - 1) / MC]

   , where [ ] is the symbol of the floor operation.  (For instance,
   [8.3] becomes 8.)

   The current node determines first whether it is either the ascendant
   or decendant nodes of the destination by using this fomular.  When
   the current node receives a packet, the next hop node to forward the
   packet can be calculated by the following three cases.

   If C is the member of SA:
      The next hop node  is AA(DC+1, D).
   If C is the member of SD:
      The next hop node  is AA(DC-1, C).
   Otherwise:
      The next hop node  is AA(DC-1, C).

7.  Route Maintenance

   The neighbor table of a node maintains the information of the parent
   and the children.  When a node loses the association from its parent,
   it SHOULD try to re-associate with its previous parent by utilizing
   the information in its neighbor table.  To identify the loss of the
   association, a node MAY use the periodical reception of beacons if
   the 6LoWPAN in the beacon-enabled mode.  Sometimes, the association
   cannot be recovered by the following reasons: drained battery, node's



Kim, et al.             Expires January 10, 2006                [Page 8]


Internet-Draft                    HiLow                        July 2005


   mobility, and malfunction, etc.  In that case, the node SHOULD try to
   associate with new parent in its POS.

   When the current node tries to forward a packet by using the
   hierarchical routing, and the next-hop node (its child or parent) is
   not reachable by some reason, it SHALL try to recover the path or to
   report this forwarding error to the source of the packet.  The
   detailed operation is TBD.

8.  Interoperability

   The interoperability issues with the external IPv6 networks is out of
   scope of this document.  The use of the short address for mapping
   into the IPv6 128 bit address is TBD.  The interworking with the on-
   demand routing in the mesh network is TBD.

9.  IANA Consideration

   The proto_type in the message formats of Section 4 is already shown
   in [I-D.montenegro-lowpan-ipv6-over-802.15.4] and the same value is
   used to this document. So, there is no IANA consideration.

10.  Security Considerations

   TBD.

11.  Acknowledgments

   Thanks to Prof. Byeong-Hee Roh, Chae-Seong Lim, and Minho Lee for
   their useful discussions and supports for writing this document.

12.  References

   [EUI64]    IEEE
              http://standards.ieee.org/regauth/oui/tutorials/
              EUI64.html, "GUIDELINES FOR 64-BIT GLOBAL IDENTIFIER
              (EUI-64) REGISTRATION AUTHORITY".

   [I-D.montenegro-lowpan-ipv6-over-802.15.4]
              Montenegro, G., "Transmission of IPv6 Packets over IEEE
              802.15.4 Networks",
              draft-montenegro-lowpan-ipv6-over-802.15.4-02 (work in
              progress), February 2005.

   [RFC2119]  Bradner, S., "Key words for use in RFCs to Indicate
              Requirement Levels", BCP 14, RFC 2119, March 1997.





Kim, et al.             Expires January 10, 2006                [Page 9]


Internet-Draft                    HiLow                        July 2005


   [RFC2461]  Narten, T., Nordmark, E., and W. Simpson, "Neighbor
              Discovery for IP Version 6 (IPv6)", RFC 2461,
              December 1998.

   [RFC3513]  Hinden, R. and S. Deering, "Internet Protocol Version 6
              (IPv6) Addressing Architecture", RFC 3513, April 2003.


Authors' Addresses

   Ki-Hyung Kim, Editor
   Ajou University
   San 5 Wonchun-dong, Yeongtong-gu
   Suwon-si, Gyeonggi-do  442-749
   KOREA

   Phone: +82 31 219 2433
   Email: kkim86@ajou.ac.kr


   Seung Wha Yoo
   Ajou University
   San 5 Wonchun-dong, Yeongtong-gu
   Suwon-si, Gyeonggi-do  442-749
   KOREA

   Phone: +82 31 219 1603
   Email: swyoo@ajou.ac.kr


   Jun-Sung Park
   Ajou University
   San 5 Wonchun-dong, Yeongtong-gu
   Suwon-si, Gyeonggi-do  442-749
   KOREA

   Phone: +82 31 219 1895
   Email: myjs77@hotmail.com


   Soohong Daniel Park, Editor
   Mobile Platform Laboratory, SAMSUNG Electronics
   416 Maetan-3dong, Yeongtong-gu
   Suwon-si, Gyeonggi-do  442-742
   KOREA

   Phone: +82 31 200 4508
   Email: soohong.park@samsung.com



Kim, et al.             Expires January 10, 2006               [Page 10]


Internet-Draft                    HiLow                        July 2005


   Jae Ho Lee
   National Computerization Agency
   NCA Bldg, 77, Mugyo-dong, Chung-ku
   Seoul,   100-775
   KOREA

   Phone: +82 2 2131 0250
   Email: ljh@nca.or.kr











































Kim, et al.             Expires January 10, 2006               [Page 11]


Internet-Draft                    HiLow                        July 2005


Intellectual Property Statement

   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.


Disclaimer of Validity

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


Copyright Statement

   Copyright (C) The Internet Society (2005).  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.


Acknowledgment

   Funding for the RFC Editor function is currently provided by the
   Internet Society.




Kim, et al.             Expires January 10, 2006               [Page 12]


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