One document matched: draft-jeong-autoconf-pdad-on-demand-00.txt
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 <addr-block> 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
<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.
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]
| PAFTECH AB 2003-2026 | 2026-04-23 11:05:26 |