Network Working Group K. Kim, Ed.
Internet-Draft picosNet Corp/Ajou Univ.
Intended status: Standards Track S. Yoo
Expires: December 19, 2007 Ajou University
S. Daniel Park, Ed.
SAMSUNG Electronics
J. Lee
NIA
G. Mulligan
June 17, 2007
Hierarchical Routing over 6LoWPAN (HiLow)
draft-daniel-6lowpan-hilow-hierarchical-routing-01.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 December 19, 2007.
Copyright Notice
Copyright (C) The IETF Trust (2007).
Abstract
The EUI-64 identifier of a 6LoWPAN device can be used as the
Kim, et al. Expires December 19, 2007 [Page 1]
Internet-Draft HiLow June 2007
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 which is very scalable can be
employed. This 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 . . . . . . . . . . . . . . . . . . . . . . 7
7. Route Maintenance . . . . . . . . . . . . . . . . . . . . . . 8
8. Interoperability . . . . . . . . . . . . . . . . . . . . . . . 8
9. IANA Consideration . . . . . . . . . . . . . . . . . . . . . . 9
10. Security Considerations . . . . . . . . . . . . . . . . . . 9
11. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . 9
12. References . . . . . . . . . . . . . . . . . . . . . . . . . 9
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . 9
Intellectual Property and Copyright Statements . . . . . . . . 10
Kim, et al. Expires December 19, 2007 [Page 2]
Internet-Draft HiLow June 2007
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.ietf-6lowpan-format], the interface
identifier [RFC4291] 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 December 19, 2007 [Page 3]
Internet-Draft HiLow June 2007
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 December 19, 2007 [Page 4]
Internet-Draft HiLow June 2007
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.ietf-6lowpan-format]. The following shows the message format
used for the hierarchical routing.
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|1 0|O|F|HopsLft| originator address, final address
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Figure 1: Mesh Addressing Type and Header
Field definitions are as follows:
O: This 1-bit field SHALL be zero if the Originator Address is an
IEEE extended 64 bit address (EUI-64), or 1 if it is a short 16-
bit addresses.
Kim, et al. Expires December 19, 2007 [Page 5]
Internet-Draft HiLow June 2007
F: This 1-bit field SHALL be zero if the Final Destination Address is
an IEEE extended 64 bit address (EUI-64), or 1 if it is a short
16-bit addresses.
Hops Left: This 4-bit field SHALL be decremented by each forwarding
node before sending this packet towards its next hop. The packet
is not forwarded any further if Hops Left is decremented to 0.
The value 0xF is reserved and signifies an 8-bit Deep Hops Left
field immediately following, and allows a source node to specify a
hop limit greater than 14 hops.
Originator Address: This is the link-layer address of the
Originator.
Final Destination Address: This is the link-layer address of the
Final Destination.
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
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. 2. 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:
Kim, et al. Expires December 19, 2007 [Page 6]
Internet-Draft HiLow June 2007
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. 2. 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
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
Kim, et al. Expires December 19, 2007 [Page 7]
Internet-Draft HiLow June 2007
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
When the current node tries to forward a packet by using the
hierarchical routing, and the next-hop node (one of the nodes in the
neighbor table) is not reachable for 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.
Kim, et al. Expires December 19, 2007 [Page 8]
Internet-Draft HiLow June 2007
9. IANA Consideration
The proto_type in the message formats of Section 4 is already shown
in [I-D.ietf-6lowpan-format] and the same value is used to this
document. So, there is no IANA consideration.
10. Security Considerations
TBD.
11. Acknowledgments
Thanks to Chae-sung Lim, Waleed Mansoor, Prof. Byeong-Hee Roh, and
for their useful discussions and supports for writing this document.
12. References
12.1. Normative References
[EUI64] 802.15.4-2003, IEEE Standard.,
"GUIDELINES FOR 64-BIT GLOBAL IDENTIFIER
(EUI-64) REGISTRATION AUTHORITY".
[I-D.ietf-6lowpan-format] N., Kushalnagar., Montenegro, G., Hui,
J., and D. Culler, "6LoWPAN:
Transmission of IPv6 Packets over IEEE
802.15.4 Networks", February 2007.
[RFC2434] Narten, T. and H. Alvestrand,
"Guidelines for Writing an IANA
Considerations Section in RFCs", BCP 26,
[IEEE802.15.4] 802.15.4-2003, IEEE Standard., "Wireless
medium access control and physical layer
specifications for low-rate wireless
personal area networks.", May 2003.
[RFC2119] Bradner, S., "Key words for use in RFCs
to Indicate Requirement Levels", BCP 14,
RFC 2119, March 1997.
[RFC2461] Narten, T., Nordmark, E., W. Simpson,
"Neighbor Discovery for IP Version 6
(IPv6)", RFC 2461, December 1998.
[RFC4291] Hinden, R. and S. Deering, "IP Version 6
Addressing Architecture", RFC 4291,
February 2006.
Kim, et al. Expires December 19, 2007 [Page 9]
Internet-Draft HiLow June 2007
Authors' Addresses
Kim, Ki Hyung (editor)
picosNet Corp/Ajou Univ.
San 5 Wonchun-dong, Yeongtong-gu
Suwon-si, Gyeonggi-do 442-749
KOREA
Phone: +82 31 219 2433
EMail: kkim86@picosnet.com
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
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
Jae Ho Lee
National Information Society Agency
NCA Bldg, 77, Mugyo-dong, Chung-ku
Seoul, 100-775
KOREA
Phone: +82 2 2131 0250
Email: ljh@nia.or.kr
Geoff Mulligan
Email: geoff@mulligan.com
Kim, et al. Expires December 19, 2007 [Page 11]
Internet-Draft HiLow June 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.
Acknowledgement
Funding for the RFC Editor function is provided by the IETF
Administrative Support Activity (IASA).
Kim, et al. Expires December 19, 2007 [Page 12]