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 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 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 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 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 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 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]