Autoconf Working Group H. Jeong Internet-Draft D. Kim Expires: April 19, 2007 KNU J. Park H. Kim ETRI C. Toh KNU October 16, 2006 Passive Duplicate Address Detection for On-demand Routing Protocols draft-jeong-autoconf-pdad-on-demand-00 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 April 19, 2007. Copyright Notice Copyright (C) The Internet Society (2006). All Rights Reserved. Jeong, et al. Expires April 19, 2007 [Page 1] Internet-Draft PDAD for On-demand Routing October 2006 Abstract This document describes passive DAD schemes over on-demand ad-hoc routing protocols such as AODV and DYMO. In order to achieve these two goals: (a) improving the accuracy of detecting address conflicts and (b) reducing the time taken to detect these conflicts, this document provides several schemes using additional information including sequence, location, or neighbor knowledge. Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 2. Message Format . . . . . . . . . . . . . . . . . . . . . . . . 4 3. PDAD Algorithm for On-demand Routing Protocols . . . . . . . . 6 3.1. Techniques to detect address conflicts of source nodes . . 6 3.1.1. Using location information: PDAD-RREQ-with-Location-information (RQL) scheme . . . 6 3.1.2. Using neighbor information: PDAD-RREQ-with-Neighbor-knowledge (RQN) scheme . . . . 6 3.2. Techniques to detect address conflicts of destination nodes . . . . . . . . . . . . . . . . . . . . . . . . . . 6 3.2.1. Using sequence number: PDAD-RREP-with-SEQ (RPS) scheme . . . . . . . . . . . . . . . . . . . . . . . . 6 3.2.2. Using location information: PDAD-RREP-with-Location-information (RPL) scheme . . . 7 3.2.3. Using neighbor information: PDAD-RREP-with-Neighbor-knowledge (RPN) scheme . . . . 7 3.3. Participation of intermediate nodes . . . . . . . . . . . 8 4. Security Considerations . . . . . . . . . . . . . . . . . . . 9 5. References . . . . . . . . . . . . . . . . . . . . . . . . . . 10 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 11 Intellectual Property and Copyright Statements . . . . . . . . . . 13 Jeong, et al. Expires April 19, 2007 [Page 2] Internet-Draft PDAD for On-demand Routing October 2006 1. Introduction Recently, research interest in MANET (Mobile Ad Hoc Networks) has increased because of the proliferation of small, inexpensive, portable, mobile personal computing devices. In proactive routing protocols such as OLSR1[1], routing information to all possible destinations in the network is maintained by each node so that a packet can be transmitted over an already-existing routing path. In reactive routing protocols such as AODV[2], a routing path is acquired on-demand when a source desires to send packets to a destination. In order to send and receive packets between two nodes, they should have their unique addresses in the network. Since IP (Internet Protocol) technologies have been applied to MANET, a unique IP address should be assigned to each node. Therefore, IP address auto- configuration techniques have been developed to remove the overhead of manual configuration. In particular, the IETF Autoconf working group has been created to address this issue. In a MANET, node mobility can cause the network to be partitioned into several sub-networks. In partitioned networks, new joining nodes have their unique addresses independent of other partitioned networks. In other words, the same addresses can exist between partitioned networks. Therefore, when several partitioned networks or independent networks are merged into one network, potential address conflicts must be resolved. Since the address uniqueness should be guaranteed, address conflicts need to be detected through a DAD (Duplicate Address Detection) procedure. Generally, DAD protocols are categorized into two classes: (a) active DAD, and (b) passive DAD. In active DAD mechanisms, when networks are merged, the address uniqueness should be always checked. When duplicate addresses are detected, address conflict resolutions are invoked; winner and loser nodes must be determined, and losers are assigned new addresses in the merged network. However, in passive DAD schemes, instead of checking uniqueness of addresses whenever a network merge occurs, hints of address conflicts, which are derived by analyzing incoming routing protocol packets, are utilized to perform address conflict resolution. This document describes passive DAD schemes over on-demand ad-hoc routing protocols such as AODV and DYMO. In order to achieve these two goals: (a) improving the accuracy of detecting address conflicts and (b) reducing the time taken to detect these conflicts, this document provides several schemes using additional information including sequence, location, or neighbor knowledge. Jeong, et al. Expires April 19, 2007 [Page 3] Internet-Draft PDAD for On-demand Routing October 2006 2. Message Format In the Generalized MANET Packet/Message Format[3] specification which defines the message format used in MANET routing protocols, the tlv- block is also defined in order to add additional fields into the message. Thus, the RREP sequence number (refer to Section 3.2.1) or location information of the nodes (refer to Section 3.1.1 and Section 3.2.2) can be put into the message-tlv-block of the RREQ/RREP message, and the addresses of neighbor nodes (refer to Section 3.1.2 and Section 3.2.3) can be listed into the address-tlv-block of it. Figure 1 shows the structure of the tlv-block used in our passive DAD schemes. Since the RQL, RPS, and RPL schemes only need one field to contain sequence number or location, it is sufficient to use the message-tlv-block. However, since the RQN and RPN schemes must list the addresses of neighbor nodes, the address-tlv-block is used. The Semantics field indicates whether or not the specific field in the tlv-block is used in the message and how to be used (refer to [3] for the detail usage). Although an address conflict resolution is beyond the scope of the current work, a new type of packet, PDADRERR, is defined in order to notify the corresponding nodes of such address duplication, where the duplicate address is indicated in the field. Jeong, et al. Expires April 19, 2007 [Page 4] Internet-Draft PDAD for On-demand Routing October 2006 Message TLV Types +----------------------+------+--------+----------------------------+ | Name | Type | Length | Value | +----------------------+------+--------+----------------------------+ | PDADSeqNum | 10 - | 8 | incremental sequence number| | | TBD | bits | | | | | | | | PDADLocation | 11 - | 32 | location information of | | | TBD | bits | originator of the message | | | | * | | +----------------------+------+--------+----------------------------+ Address TLV Type +----------------------+------+--------+----------------------------+ | PDADNeighbor | 12 - | 0 bits |IP addresses of originator's| | | TBD | | neighbor nodes | | | | | | +----------------------+------+--------+----------------------------+ Figure 1: Message/Address TLV Types Jeong, et al. Expires April 19, 2007 [Page 5] Internet-Draft PDAD for On-demand Routing October 2006 3. PDAD Algorithm for On-demand Routing Protocols 3.1. Techniques to detect address conflicts of source nodes 3.1.1. Using location information: PDAD-RREQ-with-Location-information (RQL) scheme The current location (x_rreq, y_rreq) where a new route discovery is invoked, or the location (x_join, y_join) where a node joins a network is recorded and utilized to detect address conflicts. Thereafter, when an RREQ packet is flooded from a source node, the source node includes its (x_rreq, y_rreq) or (x_join, y_join) in the RREQ packet. When a source node receives an RREQ packet with different location from its own recorded location (x_rreq, y_rreq) or (x_join, y_join), the address conflict is easily detected. Since the current location of the source node might have changed due to node mobility when receiving an RREQ packet from other nodes using the same address, the location where the route discovery is invoked should be recorded for the comparison. However, this scheme requires all nodes to be equipped with devices to obtain location information, such as GPS (Global Positioning System) devices. 3.1.2. Using neighbor information: PDAD-RREQ-with-Neighbor-knowledge (RQN) scheme A list of neighbor nodes is used for detecting address conflicts. Since nodes with many neighbor nodes produce a large-sized packet, a subset of neighbor nodes can be utilized to detect the address duplication. Therefore, in this case, a subset of neighbor nodes (neighbor_list_rreq) when a node invokes a route discovery, or a subset of neighbor nodes (neighbor_list_join) when a node joins the network is utilized for the same reason mentioned in Section 3.1.1. When an RREQ packet is transmitted, the subset is included in the RREQ packet. When a source node recognizes a difference in the information of neighbor nodes, it can detect the address conflict. 3.2. Techniques to detect address conflicts of destination nodes 3.2.1. Using sequence number: PDAD-RREP-with-SEQ (RPS) scheme This scheme requires an incremental sequence number to be included in each RREP packet transmitted by a destination node. This sequence number is different from the number defined in AODV or DYMO for the purpose of a route discovery or maintenance. A new sequence field is needed to perform the DAD functionality. Whenever a destination node replies with a new RREP packet due to detection of the existence of better route through receiving other RREQ packets, the sequence number increases and is put into the RREP packet. Therefore, when a Jeong, et al. Expires April 19, 2007 [Page 6] Internet-Draft PDAD for On-demand Routing October 2006 source node receives more than one RREP packets with the same sequence number and same destination address, the source node will conclude that multiple nodes are using the same destination address. Since an RREQ packet contains a sequence number generated by a source node, the sequencing of RREP packets is reset when a new RREQ packet is generated by the source node. 3.2.2. Using location information: PDAD-RREP-with-Location-information (RPL) scheme Similar to Section 3.1.1, either the location (x_rrep, y_rrep) where the first RREP packet corresponding to a new RREQ packet is sent, or the location (x_join, y_join) where a node joins a network is recorded and utilized to detect address conflicts. When sending an RREP packet, a destination node includes its (x_rrep, y_rrep) or (x_join, y_join). When a source node receives more than one RREP packet with different location, it will conclude the existence of duplicate addresses for the destination nodes. When a destination node sends another RREP packet due to a recognition of better route, if it uses its new current location, the source node may misunderstand the existence of duplicate addresses due to different location information caused by node mobility. Therefore, we utilize the (x_rrep, y_rrep) or (x_join, y_join). In case of using (x_rrep, y_rrep), the recorded location information is updated into the new location information when a new RREQ packet with a different sequence number in the packet is generated by the source node. 3.2.3. Using neighbor information: PDAD-RREP-with-Neighbor-knowledge (RPN) scheme Similarly to Section 3.1.2, the subset of neighbor nodes (neighbor_list_rrep) when the first RREP corresponding to a new RREQ packet is sent, or the subset of neighbor nodes (neighbor_list_rrep) when a node joins a network is recorded and utilized to detect the address duplication. When a destination replies with an RREP packet, a subset of neighbor nodes of the destination node, that is, (neighbor_list_rrep) or (neighbor_list_join), is included in the RREP packet. When a source node receives more than one RREP packet with different neighbor lists, it will determine the existence of duplicate addresses for the destination nodes. In case of using a (neighbor_list_rrep), the subset is updated into new neighbor nodes when a new RREQ packet with a different sequence number is generated by the source node. The neighbor list can be acquired during a route discovery procedure, or through the exchange of ''hello" messages. During the route discovery procedure, a Jeong, et al. Expires April 19, 2007 [Page 7] Internet-Draft PDAD for On-demand Routing October 2006 destination node creates a neighbor list from the neighboring nodes that forwarded an RREQ packet to the destination node. 3.3. Participation of intermediate nodes To reduce the time needed to detect address conflicts, intermediate nodes between a source node and a destination node in the network can participate. When a source and destination nodes send RREQ and RREP packets respectively, their recorded location (x_join, y_join) or their subset of neighboring nodes' addresses (neighbor_list_join) will be put into the RREQ and RREP packets. Each intermediate node receiving the RREQ or RREP packets will create a table entry with or . The table entry will be removed after a timeout value expires in a soft-state manner. Therefore, when an intermediate node receives RREQ or RREP packets from a source node or a destination node using the same address, the location or neighbors in the RREQ or RREP packets will be different from those in the table entry, which can detect the address conflict. The protocol utilizes (x_join, y_join) or neighbor_list_join where a node joins the network, neither (x_rreq, y_rreq) nor (neighbor_list_rreq), where a source node invokes a route discovery procedure. If (x_rreq, y_rreq) or (neighbor_list_rreq) is put into an RREQ or RREP packet, intermediate nodes cannot distinguish between a case in which a new RREQ packet to acquire a new path is received from the same source node and a case in which other nodes with the same address exist. However, some intermediate nodes will detect an address conflict for a source or destination address at almost the same time and notify all other nodes in the network of the address conflict. Here, in order to avoid a broadcast message implosion because the intermediate nodes try to announce the address conflict, the proposed techniques can be used to avoid the broadcast storm problem. Jeong, et al. Expires April 19, 2007 [Page 8] Internet-Draft PDAD for On-demand Routing October 2006 4. Security Considerations TBD Jeong, et al. Expires April 19, 2007 [Page 9] Internet-Draft PDAD for On-demand Routing October 2006 5. References [1] C. Perkins, E. Royer and S. Das, "Ad hoc On-Demand Distance Vector (AODV) routing," RFC 3561, IETF, July 2003. [2] T. Clausen and P. Jacquet, "Optimized Link State Routing Protocol (OLSR)," RFC 3626, IETF, October 2003. [3] T. Clausen, C. Dearlove, J. Dean and C. Adjih, "Generalized MANET Packet/Message Format," IETF Internet-Draft, draft-ietf-manet-packetbb-02.txt, July 2006. Jeong, et al. Expires April 19, 2007 [Page 10] Internet-Draft PDAD for On-demand Routing October 2006 Authors' Addresses Hongjong Jeong Kyungpook National University 1370 Sankyuk-dong, Puk-gu Daegu 702-701 Korea Phone: +82 53 940 8590 Fax: +82 53 957 4846 Email: hjjeong@monet.knu.ac.kr Dongkyun Kim Kyungpook National University 1370 Sankyuk-dong, Puk-gu Daegu 702-701 Korea Phone: +82 53 950 7571 Fax: +82 53 957 4846 Email: dongkyun@knu.ac.kr Jungsoo Park ETRI / PEC 161 Gajeong-dong, Yuseong-gu Daejeon 305-350 Korea Phone: +82 42 860 6514 Fax: +82 42 861 5404 Email: pjs@etri.re.kr Hyoungjun Kim ETRI / PEC 161 Gajeong-dong, Yuseong-gu Daejeon 305-350 Korea Phone: +82 42 860 6576 Fax: +82 42 861 5404 Email: khj@etri.re.kr Jeong, et al. Expires April 19, 2007 [Page 11] Internet-Draft PDAD for On-demand Routing October 2006 C.K. Toh Kyungpook National University 1370 Sankyuk-dong, Puk-gu Daegu 702-701 Korea Phone: +82 53 950 7571 Fax: +82 53 957 4846 Email: ckt@eee.hku.hk Jeong, et al. Expires April 19, 2007 [Page 12] Internet-Draft PDAD for On-demand Routing October 2006 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 (2006). 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. Jeong, et al. Expires April 19, 2007 [Page 13]