Autoconf Working Group H. Jeong
Internet-Draft S. Oh
Intended status: Standards Track D. Kim
Expires: October 21, 2007 KNU
J. Park
H. Kim
ETRI
C. Toh
KNU
April 19, 2007
Passive Duplicate Address Detection for On-demand Routing Protocols
draft-jeong-autoconf-pdad-on-demand-01
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 October 21, 2007.
Copyright Notice
Copyright (C) The IETF Trust (2007).
Jeong, et al. Expires October 21, 2007 [Page 1]
Internet-Draft PDAD for On-demand Routing April 2007
Abstract
This document describes passive DAD techniques 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 techniques using additional information
including sequence, location, or neighbor knowledge.
Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3
2. Message Format . . . . . . . . . . . . . . . . . . . . . . . . 4
3. PDAD Techniques 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) technique . 6
3.1.2. Using neighbor information:
PDAD-RREQ-with-Neighbor-knowledge (RQN) technique . . 6
3.2. Techniques to detect address conflicts of destination
nodes . . . . . . . . . . . . . . . . . . . . . . . . . . 7
3.2.1. Using sequence number: PDAD-RREP-with-SEQ (RPS)
technique . . . . . . . . . . . . . . . . . . . . . . 7
3.2.2. Using location information:
PDAD-RREP-with-Location-information (RPL) technique . 7
3.2.3. Using neighbor information:
PDAD-RREP-with-Neighbor-knowledge (RPN) technique . . 7
3.3. Obtaining Additional Information . . . . . . . . . . . . . 8
3.4. Participation of intermediate nodes . . . . . . . . . . . 8
4. Security Considerations . . . . . . . . . . . . . . . . . . . 9
5. Normative References . . . . . . . . . . . . . . . . . . . . . 10
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 11
Intellectual Property and Copyright Statements . . . . . . . . . . 13
Jeong, et al. Expires October 21, 2007 [Page 2]
Internet-Draft PDAD for On-demand Routing April 2007
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 techniques 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 techniques using additional information
including sequence, location, or neighbor knowledge.
Jeong, et al. Expires October 21, 2007 [Page 3]
Internet-Draft PDAD for On-demand Routing April 2007
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
techniques. Since the RQL, RPS, and RPL techniques 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 techniques
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 <addr-block> field.
Jeong, et al. Expires October 21, 2007 [Page 4]
Internet-Draft PDAD for On-demand Routing April 2007
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 October 21, 2007 [Page 5]
Internet-Draft PDAD for On-demand Routing April 2007
3. PDAD Techniques for On-demand Routing Protocols
This document presents several techniques to detect address conflicts
of source and destination nodes using additional information
including location, neighbor knowldege and sequence information.
These additional information is included into routing control packets
exchanged for route discovery.
3.1. Techniques to detect address conflicts of source nodes
This section describes two techniques that can detect address
conflicts when receiving RREQ packets from multiple nodes using the
same address. In these techniques, an RREQ packet contains location
or neighbor information that can be used to detect address conflict
of source nodes.
3.1.1. Using location information: PDAD-RREQ-with-Location-information
(RQL) technique
In order to differentiate between RREQ packets which contain the same
source address but are issued from other nodes, RQL technique
includes location information (location_src) (refer to
Section 3.3)into RREQ packets.
When an RREQ packet is flooded from a source node, the source node
includes its location in the RREQ packet (location_src). When a
source node receives an RREQ packet with the same source IP address
and different location from its own recorded location (location_own),
this means that an address conflict exists.
3.1.2. Using neighbor information: PDAD-RREQ-with-Neighbor-knowledge
(RQN) technique
In RQN technique, instead of using location information, a list of
neighbor nodes is used. A list of neighbor nodes(neighbor_own) is
captured and recorded when the node's IP address is configured. In
order to reduce a size of packet, a subset of neighbor nodes can be
utilized to detect the address duplication.
When an RREQ packet is transmitted, the list(neighbor_src) is
included in the RREQ packet. When a source node recognizes
difference between the information of neighbor nodes(neighbor_src) in
the received RREQ packet and its recorded list(neighbor_own), it can
detect the address conflict.
Jeong, et al. Expires October 21, 2007 [Page 6]
Internet-Draft PDAD for On-demand Routing April 2007
3.2. Techniques to detect address conflicts of destination nodes
In this section, three techniques are described to detect address
conflicts of destination nodes.
3.2.1. Using sequence number: PDAD-RREP-with-SEQ (RPS) technique
RPS technique requires an incremental PDAD-sequence number to be
included in each RREP packet transmitted by a destination node. In
order to perform the RPS DAD functionality, a field which can contain
an additional PDAD-sequence should be added in the RREP packet.
Whenever the destination node replies with a new RREP packet because
it has received an RREQ packet which traversed a better route, the
PDAD-sequence number increases and is put into the RREP packet.
Therefore, when a source node receives more than one RREP packet with
the same PDAD-sequence number and the same destination address, the
source node can detect the address conflict of destination nodes.
3.2.2. Using location information: PDAD-RREP-with-Location-information
(RPL) technique
Similar to Section 3.1.1, in order to differentiate between RREP
packets which contain the same source address (The source address of
RREP packets is the destination address of RREQ packets.), but are
issued from other nodes, RPL technique includes location
information(location_dst) obtained into RREP packets. The
location(location_dst) obtained when a node configures its IP address
is recorded and utilized to detect address conflicts.
Sending an RREP packet, a destination node includes its recorded
location(location_dst). When a source node receives more than one
RREP packet with different location, it will conclude the existence
of duplicate addresses for destination nodes.
3.2.3. Using neighbor information: PDAD-RREP-with-Neighbor-knowledge
(RPN) technique
Similar to Section 3.1.2, the list of neighbor nodes(neighbor_dst)
obtained when a node configures its IP address is captured and
recorded. Then, it is utilized to detect the address duplication.
When a destination node replies with an RREP packet, a list of
neighbor nodes of the destination node(neighbor_dst) is included in
the RREP packet. When a source node receives more than one RREP
packet with different neighbor lists(neighbor_dst), it will determine
the existence of duplicate addresses for destination nodes.
Jeong, et al. Expires October 21, 2007 [Page 7]
Internet-Draft PDAD for On-demand Routing April 2007
3.3. Obtaining Additional Information
In order to detect address conflicts with RQL, RPL, RQN and RPN,
additional information is required, such as location information and
neighboring list. The node's location(location_own) where a node
joins a network is recorded and utilized to detect address conflicts.
However, this technique requires all nodes to be equipped with
devices to obtain location information, such as GPS (Global
Positioning System) devices.
Each node can acquired addresses of neighboring nodes through the
exchange of "hello" messages. A list of neighbor nodes(neighbor_own)
is captured and recorded when the node's IP address is configured.
3.4. 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 (location_src),
(location_dst) and their list of neighboring nodes' addresses
(neighbor_src), (neighbor_dst) will be put into the RREQ and RREP
packets. Each intermediate node receiving the RREQ or RREP packets
will create a table entry with <source_node, the_location> or
<source_node, the_list_of_neighbor_nodes'_addresses>. 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.
Jeong, et al. Expires October 21, 2007 [Page 8]
Internet-Draft PDAD for On-demand Routing April 2007
4. Security Considerations
TBD
Jeong, et al. Expires October 21, 2007 [Page 9]
Internet-Draft PDAD for On-demand Routing April 2007
5. Normative 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," Work In Progress
draft-ietf-manet-packetbb-04.txt, January 2007.
Jeong, et al. Expires October 21, 2007 [Page 10]
Internet-Draft PDAD for On-demand Routing April 2007
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
Oh Sutaek
Kyungpook National University
1370 Sankyuk-dong, Puk-gu
Daegu 702-701
Korea
Phone: +82 53 940 8590
Fax: +82 53 957 4846
Email: stoh@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
Jeong, et al. Expires October 21, 2007 [Page 11]
Internet-Draft PDAD for On-demand Routing April 2007
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
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 October 21, 2007 [Page 12]
Internet-Draft PDAD for On-demand Routing April 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.
Acknowledgment
Funding for the RFC Editor function is provided by the IETF
Administrative Support Activity (IASA).
Jeong, et al. Expires October 21, 2007 [Page 13]