Network Working Group K. Kim, Ed.
Internet-Draft S. Yoo
Expires: January 10, 2006 M. Jung
Ajou University
S. Daniel Park, Ed.
SAMSUNG Electronics
J. Lee
NCA
July 9, 2005
6LoWPAN Ad Hoc Routing Protocol(LOAD)
draft-daniel-6lowpan-load-adhoc-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
6LoWPAN Ad hoc Routing Protocol(LOAD) is intended for use by IEEE
Kim, et al. Expires January 10, 2006 [Page 1]
Internet-Draft LOAD July 2005
802.15.4 devices in a 6LoWPAN. It is a simple on-demand routing
protocol in the adaption layer for IPv6 packets.
Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3
2. Requirements notation . . . . . . . . . . . . . . . . . . . . 3
3. Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
4. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 4
5. Data Structures . . . . . . . . . . . . . . . . . . . . . . . 5
5.1 Routing Table Entry . . . . . . . . . . . . . . . . . . . 5
5.2 Route Request Table Entry . . . . . . . . . . . . . . . . 5
5.3 Message Format . . . . . . . . . . . . . . . . . . . . . . 6
5.3.1 Route Request (RREQ) . . . . . . . . . . . . . . . . . 6
5.3.2 Route Reply (RREP) . . . . . . . . . . . . . . . . . . 7
5.3.3 Route Error (RERR) . . . . . . . . . . . . . . . . . . 8
6. Operation . . . . . . . . . . . . . . . . . . . . . . . . . . 8
6.1 Generating Route Request . . . . . . . . . . . . . . . . . 8
6.2 Processing and Forwarding Route Request . . . . . . . . . 9
6.3 Generating Route Reply . . . . . . . . . . . . . . . . . . 9
6.4 Receiving and Forwarding Route Reply . . . . . . . . . . . 9
6.5 Local Repair and RERR . . . . . . . . . . . . . . . . . . 9
7. IANA Consideration . . . . . . . . . . . . . . . . . . . . . . 10
8. Security Considerations . . . . . . . . . . . . . . . . . . . 10
9. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 10
10. References . . . . . . . . . . . . . . . . . . . . . . . . . 10
10.1 Normative Reference . . . . . . . . . . . . . . . . . . . 10
10.2 Informative Reference . . . . . . . . . . . . . . . . . . 11
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . 11
Intellectual Property and Copyright Statements . . . . . . . . 13
Kim, et al. Expires January 10, 2006 [Page 2]
Internet-Draft LOAD July 2005
1. Introduction
Because devices in the 6LoWPAN have small packet size, low bandwidth
and low power, the existing AODV protocol [RFC3561] is not suitable
for 6LoWPAN[I-D.kushalnagar-lowpan-goals-assumptions]. The 6LoWPAN
Ad hoc Routing Protocol (LOAD) is a simplified on-demand routing
protocol based on AODV for 6LoWPAN. LOAD enables multihop routing
between IEEE 802.15.4 devices to establish and maintain routing paths
in 6LoWPAN.
This document defines the message formats, the routing table entry
fields, and the operation of LOAD.
2. 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].
3. Overview
This section describes the overview and the characteristics of LOAD.
LOAD is assumed to use the adaption layer for the segmentation and
reassembly of IPv6 packets as defined in [I-D.montenegro-lowpan-
ipv6-over-802.15.4]. LOAD is defined to be operating on top of the
adaptation layer instead of the transport layer. Also, LOAD assumes
the use of either one of the two different addresses for routing: the
EUI-64 address and the 16 bit short address of the 6LoWPAN device.
LOAD doesn't use the destination sequence number to reduce the size
of the control messages and simplify the route discovery process.
For ensuring loop freedom, only the final destination generates a
RREP in response to a RREQ.
LOAD MAY use the local repair for a link break. During a local
repair, only the final destination generates a RREP.
LOAD uses the path cost, which is the accumulated link cost from the
originator to the destination, as a metric for routing. However, if
the link costs of every link are the same value, then the metric for
routing becomes the same as the hop distance.
LOAD MAY utilize the acknowledgement option of the transmission at
the MAC layer for the link layer acknowledgement. Thus, LOAD does
not use the hello messages of AODV.
The basic operations of LOAD are route discovery, managing routing
table entries and maintaining local connections. For these
Kim, et al. Expires January 10, 2006 [Page 3]
Internet-Draft LOAD July 2005
operations, LOAD maintains the following three tables: the neighbor
table, the routing table, and the route request table.
There are two different types of 6LoWPAN devices: the reduced
function device and the full function device. LOAD MAY utilize both
of the two device types for mesh routing.
6LoWPAN devices MAY have inactive periods to save power consumption.
LOAD MAY adjust the inactive periods of the intermediate nodes and
utilize the periods for routing decision (TBD).
LOAD MAY be used cooperatively with the hierarchical routing which
does not require the routing table and the routing request table.
The efficent cooperation is TBD.
4. Terminology
This section defines the terminology of LOAD that is not defined in
[RFC3753] and [RFC3561].
final destination
An interface ID of IPv6 Address or short address to which data
packets are to be transmitted. Same as "destination" in
[RFC3561].
link cost
A Link Quality (LQ) between a node and its neighbor node.
link quality indicator (LQI)
A mechanism to measure the Link Quality (LQ) in IEEE 802.15.4
PHY layer [ieee802.15.4]. It measures LQ by receiving the
signal energy level. A high LQ value implies the good quality
of communication (i.e. low link cost).
path cost
An accumulated link cost as a LOAD control message passes
through nodes.
reverse path
A path set up to forward a route reply (RREP) packet back to
the originating node from the final destination node. Same as
"reverse route" in [RFC3561].
Kim, et al. Expires January 10, 2006 [Page 4]
Internet-Draft LOAD July 2005
5. Data Structures
5.1 Routing Table Entry
LOAD deals with routing table management. Routing table information
MUST be kept and used following fields with each routing table entry:
final destination address
The 16 bit or 64 bit link layer final destination address of
the route.
status
The status of the route.
next hop address
The 16 bit or 64 bit link layer address of the next hop to
final destination.
5.2 Route Request Table Entry
Route request table is used for discovering routes. It stores the
route request information until a route is discovered.
route request ID
a unique sequence number to identify RREQ.
originator address
The 16 bit or 64 bit link layer address of the originator which
issues RREQs.
reverse path address
The 16 bit or 64 bit link layer address of backward path to the
originator.
path cost
The accumulated link cost from the current node to the final
destination node.
valid time
Kim, et al. Expires January 10, 2006 [Page 5]
Internet-Draft LOAD July 2005
The time of the expiration or deletion of a route in
milliseconds.
5.3 Message Format
5.3.1 Route Request (RREQ)
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type |R|D|O| RREQ ID |Reserved | Path cost |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Link Layer Final Destination Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Link Layer Originator Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
<Fig. 1. RREQ message format>
The RREQ message format is shown in Fig. 1 and contains the following
fields:
Type 1 for indicating a RREQ message.
R 1 Local Repair.
D 1 for the 16 bit address of the final destination,
0 for the EUI 64 address.
O 1 for the 16 bit address of the originator,
0 for the EUI 64 address.
Reserved 0; ignored on reception.
Path cost The cost from the originator to the final
destination.
RREQ ID A sequence number uniquely identifying the particular
RREQ.
Link layer Final Destination Address
The link layer 16 bit or 64 bit address of the
destination for which a route is supplied.
Link layer Originator Address
The link layer 16 bit or 64 bit address of the node
which originated the Route Request.
Kim, et al. Expires January 10, 2006 [Page 6]
Internet-Draft LOAD July 2005
5.3.2 Route Reply (RREP)
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type |R|D|O| Reserved |Prefix Sz| Path cost |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Link layer Final Destination Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Link layer Originator Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
<Fig. 2. RREP message format>
The RREP message format is shown in Fig. 2 and contains the following
fields:
Type 2 for indicating a RREP message.
R 1 Local Repair.
D 1 for the 16 bit address of the final destination,
0 for the EUI 64 address.
O 1 for the 16 bit address of the originator,
0 for the EUI 64 address.
Reserved 0; ignored on reception.
Prefix Sz TBD.
Path cost The cost from the originator to the final
destination.
RREQ ID A sequence number uniquely identifying the particular
RREQ.
Link layer Final Destination Address
The link layer 16 bit or 64 bit address of the
destination for which a route is supplied.
Link layer Originator Address
The link layer 16 bit or 64 bit address of the node
which originated the Route Request.
Kim, et al. Expires January 10, 2006 [Page 7]
Internet-Draft LOAD July 2005
5.3.3 Route Error (RERR)
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type |D|O| Reserved | Error Code |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Unreachable Link layer Final Destination Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
<Fig. 3. RERR message format>
The RERR message format is shown in Fig. 3 and contains the following
fields:
Type 3 for indicating a RERR message.
D 1 for the 16 bit address of the final destination,
0 for the EUI 64 address.
O 1 for the 16 bit address of the originator,
0 for the EUI 64 address.
Reserved 0; ignored on reception.
Error Code Numeric value for describing error.
0x00 = No available route
0x01 = Low battery
0x02 - 0xff = reserved (TBD)
Unreachable Link layer Final Destination Address
The link layer 16 bit or 64 bit address of the final
destination that has become unreachable due to a
link break.
6. Operation
6.1 Generating Route Request
The basic operations of LOAD are route discovery, managing routing
table entries and maintaining local connections. A node maintains
the following three tables for routing: the neighbor table, the
routing table, and the routing request table.
During the discovery period, an originator, a node that requests a
route discovery, generates a Route Request (RREQ) message with the
RREQID which was incremented by one from the previous RREQID value.
Kim, et al. Expires January 10, 2006 [Page 8]
Internet-Draft LOAD July 2005
6.2 Processing and Forwarding Route Request
Upon receiving a RREQ, an intermediate node tries to find the entry
of the same originator address and RREQID pair in the route request
table. If the entry is found, the node just discards the RREQ.
Otherwise, the node creates a reverse path toward the originator in
the routing table and a RREQ entry in the route request table. Then,
the node forwards the RREQ.
6.3 Generating Route Reply
When the final destination receives a RREQ, it unicasts a RREP to the
originator in reply.
6.4 Receiving and Forwarding Route Reply
Upen receiving a RREP, an intermediate node checks whether it has a
route entry for the destination of the RREP (i.e. the originator of
the corresponding RREQ). If it does not have the route entry, it
just discards the RREP. Otherwise, it also checks for the existence
of the RREQ entry in the route request table. If the entry has worse
path cost (i.e. higher path cost) than that of the RREP, the node
updates the entry with the information of the RREP and forwards it to
the previous hop node toward the destination of the RREP. If the
entry is better than the RREP, the node just discards the RREP.
During the delivery of the RREP to the originator node, the path cost
field of the RREP is accumulated on every node from the destination
node to the originator node. When the RREP reaches the originator
node, the path cost of the RREP represents the overall link cost from
the originator to the final destination.
6.5 Local Repair and RERR
If a link break occurs or a device fails during the delivery of data
packets, the upstream node of the link break MAY repair the route
locally. To repair a route, the node disseminates a RREQ with the
originator address set to its own address and the final destination
address set to the data packet's final destination address. In this
case, the R flag of the RREQ is set to 1. The data packet is
buffered during the route discovery period. If the final destination
node receives the RREQ for a route repair, the node responds with a
RREP of which the R flag is set to 1.
If the repairing node cannot receive a RREP from the final
destination until the end of the route discovery period, the node
unicasts a RERR with an error code that indicates the reason of the
repair failure to the originator node. Then, the buffered data
Kim, et al. Expires January 10, 2006 [Page 9]
Internet-Draft LOAD July 2005
packet is discarded.
When the repairing node receives a RREP from the final destination
during the route discovery period, it updates the routing table entry
information from the RREP. Then the node transmits the buffered data
packet to the final destination through the new route.
If the originator that sends a data packet receives the RERR, it MAY
try to reinitiate route discovery
7. IANA Consideration
This document needs an additional IANA registry for the prot_type
value that indicates the LOAD format.
8. Security Considerations
The security considerations of the [RFC3561] are applicable to this
document. As described in the charter of the 6lowpan w.g., LOAD will
also try to reuse existing security considerations related to Ad hoc
routing protocols. Further considerations will be studied in the next
version.
9. Acknowledgments
Thanks to the authors of RFC 3753 and RFC 3561, as parts of this
document are patterned after theirs. Thanks to Prof. Byeong-Hee Roh,
Dae-hong Son, and Minho Lee for their useful discussions and supports
for writing this document.
10. References
10.1 Normative Reference
[I-D.kushalnagar-lowpan-goals-assumptions]
Kushalnagar, N. and G. Montenegro, "6LoWPAN: Overview,
Assumptions, Problem Statement and Goals",
draft-kushalnagar-lowpan-goals-assumptions-00 (work in
progress), February 2005.
[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 10]
Internet-Draft LOAD July 2005
[RFC2434] Narten, T. and H. Alvestrand, "Guidelines for Writing an
IANA Considerations Section in RFCs", BCP 26, RFC 2434,
October 1998.
[RFC3561] Perkins, C., Belding-Royer, E., and S. Das, "Ad hoc On-
Demand Distance Vector (AODV) Routing", RFC 3561,
July 2003.
[RFC3753] Manner, J. and M. Kojo, "Mobility Related Terminology",
RFC 3753, June 2004.
[ieee802.15.4]
IEEE Compure Society, "IEEE Std. 802.15.4-2003", IEEE Std.
802.15.4-2003, October 2003.
10.2 Informative Reference
[RFC1884] Hinden, R. and S. Deering, "IP Version 6 Addressing
Architecture", RFC 1884, December 1995.
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
Myung-Ho Jung
Ajou university
Wonchun-dong, Youngtong-gu
Suwon-si, Gyeonggi-do 443-749
KOREA
Kim, et al. Expires January 10, 2006 [Page 11]
Internet-Draft LOAD July 2005
Phone: +82-31-219-1892
Email: router@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 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 12]
Internet-Draft LOAD 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 13]