Internet DRAFT - draft-zhu-roll-addr-autoconf
draft-zhu-roll-addr-autoconf
ROLL Wan-Ting Zhu
Internet Draft De-Yun Gao
Expires: November 11, 2013 Hong-Ke Zhang
Wei-Cheng Zhao
Beijing Jiaotong University
May 10, 2013
Address Autoconfiguration for RPL
draft-zhu-roll-addr-autoconf-00.txt
Abstract
This document presents a straightforward address
autoconfiguration mechanism for RPL over low power and lossy
networks (LLN). A solution is proposed to add the capability
of reusable address allocation. In this solution, nodes are
assigned with unique IPv6 addresses according to their positions
in the network. The amount of routing entries kept at each node
is reduced. Also, this document introduces a dynamic adjustment
strategy for adapting to uneven distribution of node density.
Status of this Memo
This Internet-Draft is submitted to IETF in full conformance
with the provisions of BCP 78 and 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 November 11, 2013.
Zhu et al. Expires November 11, 2013 [Page 1]
Internet-Draft Address Autoconfiguration for RPL May 10, 2013
Copyright Notice
Copyright (c) 2013 IETF Trust and the persons identified as the
document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents
(http://trustee.ietf.org/license-info) in effect on the date of
publication of this document. Please review these documents
carefully, as they describe your rights and restrictions with respect
to this document. Code Components extracted from this document must
include Simplified BSD License text as described in Section 4.e of
the Trust Legal Provisions and are provided without warranty as
described in the Simplified BSD License.
Table of Contents
1. Introduction ................................................ 3
2. Terminology ................................................. 4
3. Overview .................................................... 5
4. Message Formats ............................................. 6
4.1. Address Solicitation ................................... 6
4.2. Address Information and Address Lease Response ......... 7
4.3. Address Advertisement and Address Acknowledgement ...... 8
4.4. REJECTION and APPROVE ................................. 10
4.5. Address Lease Request and Address Lease Parent Request
.. 10
4.6. Address Lease Notification ............................ 12
5. Address Autoconfiguration .................................. 13
5.1. Address Assignment .................................... 13
5.2. Address Lease ......................................... 15
5.3. Address Reusing........................................ 16
5.4. Partitioning and Merging .............................. 16
6. Routes ..................................................... 18
6.1. Upward Routes ......................................... 18
6.2. Downward Routes........................................ 18
7. Security Considerations .................................... 18
8. IANA Considerations ........................................ 18
9. References ................................................. 19
9.1. Normative References .................................. 19
9.2. Informative References ................................ 20
10. Acknowledgments ........................................... 21
Authors' Addresses ............................................ 21
Zhu et al. Expires November 11, 2013 [Page 2]
Internet-Draft Address Autoconfiguration for RPL May 10, 2013
1. Introduction
The IPv6 Routing Protocol for Low power and lossy networks (RPL)
[RFC6550] was designed with the objective to meet the application-
specific routing requirements. There may be multiple instances of RPL
running concurrently on a network. And the traffic patterns are not
simply multipoint-to-point, but in many cases they are point-to-
multipoint or point-to-point. Therefore, a mechanism for assigning
addresses to RPL nodes is required. This document provides a way to
autoconfigure nodes with one or more IPv6 addresses by considering
the characteristic properties of RPL.
The Destination Oriented Directed Acyclic Graph (DODAG) is the core
of RPL. The ICMPv6 messages called DODAG Information Objects (DIOs)
are broadcasted periodically by each node to construct and maintain
the DODAG, containing information about the rank, the objective
function, and so on. This Rank value plays a key role in RPL, which
represents the location of a node within a DODAG, and is essential
for nodes to determine their preferred parents.
In this environment, the main task of address autoconfiguration
protocol is to deal with address duplication. This document specifies
how to allocate and assign a unique address to a new node.
Furthermore, our addressing scheme is based on the concept of
hierarchical levels considering the particularity of RPL topology in
order to achieve scalability. These levels are indicative of the
locations of nodes within a DODAG Version. Traditional
autoconfiguration mechanisms, such as DHCP [RFC2131] or some other
similar mechanisms, are all built on a client-server model and are
not suitable for low power and lossy networks that are usually
unstable with relatively low packet delivery rates.
In this document, nodes can be configured with global unique
addresses for IPv6 enables a huge address space. Global unique
addresses are advantageous to the networks which each node can
communicate with each of its potential peers and administrative tasks,
such as downloading binary codes or monitoring individual sensor
nodes.
This document specifies how to handle complex situations where death
and replenishment of the nodes exist. In this solution, addresses can
be reused in the address space. Nodes will send messages to notify
their neighbors before leaving the network, and the addresses of the
leaving nodes will be reused. Moreover, network partitioning and
merging occur potentially since nodes may join or leave the network
at any time. It is possible that two or more nodes have the same
addresses, when multiple partitions merge.
Zhu et al. Expires November 11, 2013 [Page 3]
Internet-Draft Address Autoconfiguration for RPL May 10, 2013
The address autoconfiguration mechanism in this document is designed
to be suitable for the networks which contain the uneven distribution
of node density. In some conditions the node density of the sensor
networks cannot be predicted exactly. In the high density area, there
may be no unused addresses in the parents due to the restriction of
node address space. This will lead to the problem that some new nodes
could not join the network. However, in this scheme, parents can
obtain the unassigned addresses held by the neighbors to assign the
new nodes.
2. Terminology
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and
"OPTIONAL" in this document are to be interpreted as described in RFC
2119 [RFC2119].
Additionally, this document uses the terminologies described in [I-D.
ietf-roll-terminology], [RFC6550], and introduces the following
terminology:
Lease: Lease refers to the behavior that a node requests an unused
address from another node to assign its own child.
Address Lease Table: An address lease table records the debtor node
and maintains a set of addresses which are leased by another node.
Brother node: One node's brother nodes must have the same parent with
it.
Creditor: A creditor is a node that gets ready to lease an address to
another node. And it should be a member of the brother node set.
Debtor: A debtor is a node that intends to lease an address from
other nodes. One node's creditor may also be another node's debtor.
Orphan: An orphan is a node that loses its parent.
Address Solicitation: The message is used for the purpose of
requesting an address from a parent. (See Section 4.1)
Address Information: The message is used for the purpose of
advertising a node's own address information. (See Section 4.2)
Address Advertisement: The message is used for the purpose of
informing parents of the addresses that the child nodes intend to use.
(See Section 4.3)
Zhu et al. Expires November 11, 2013 [Page 4]
Internet-Draft Address Autoconfiguration for RPL May 10, 2013
REJECTION message: The message is used for the purpose of indicating
the requested address which has already been utilized. (See Section
4.4)
APPROVE message: The message is used for the purpose of indicating a
node which can get the requested address approved. (See Section 4.4)
Address Lease Request: The message is used when a node intends to
borrow an unused address from other nodes. (See Section 4.5)
Address Lease Response: The message is used when a node agrees to
lend an address to another node. (See Section 4.2)
Address Lease Parent Request: The message is used when a node has
lost its original parent and intended to get a new parent. (See
Section 4.5)
Address Lease Notification: A notification message contains the
debtor nodes and the corresponding leased addresses. (See Section 4.6)
Address Acknowledgement: The message is used when a node has
confirmed its allocated address. (See Section 4.3)
3. Overview
This section outlines the address autoconfiguration mechanism for RPL.
The network topology is constructed and maintained as specified in
RFC6550 [RFC6550]. As described in this reference, RPL organizes a
topology as a Directed Acyclic Graph (DAG) that consists of one or
more Destination Oriented DAGs (DODAGs). If there are multiple roots
in a DAG, the roots are expected to be federated by a common backbone.
This document defines how the address autoconfiguration mechanism
operates in a single DODAG. In addition, this mechanism also uses
trickle [RFC6206] to optimize the dissemination.
RPL has defined the process of parent selection through the Objective
Function (OF) [RFC6552]. When a node has determined its preferred
parent node, it can trigger the address allocation process
immediately without waiting for the whole topology to be constructed.
The address configuration procedure is comprised of two phases: (a)
address allocation and (b) address conflict detection.
In the address allocation phase, when a node associates to the
network, a packet containing the parent's address will be sent to it.
Child node randomly generates a fixed n bits string and concatenates
this random number with the received parent's address as its own
Zhu et al. Expires November 11, 2013 [Page 5]
Internet-Draft Address Autoconfiguration for RPL May 10, 2013
address. That means the address of parent node becomes the prefix
address of child node. If there is no unused address in the parent
and its neighbor still holds unassigned address, the parent can
borrow an address from the neighbor to assign its child node. Besides,
the neighbor node should mark the selected address in its Address
Lease Table. This method also can be used to handle the network
partitioning and merging. The address of a node has correlation with
the distance of the node from the DODAG root and its length strictly
increases in the Down direction. Finally, the node sends its address
back to its parent and waits for getting the address approved by the
parent.
In the address conflict detection phase, parent nodes verify the
uniqueness of the children's address. When conflict happens, parents
notify the corresponding children to regenerate a different address.
When a node dies or leaves the network, the address of this node will
be reused.
The assigned addresses can bear some routing information. In our
scheme, upward routes are established through the longest prefix
match or default route. Then for the downward routes, the amount of
routing entries kept at the node is significantly reduced, which
increases routing efficiency. Moreover, the messages can travel down
to the target group of nodes.
This address autoconfiguration mechanism is detailed in the following
sections.
4. Message Formats
This section defines the particular messages used in this address
autoconfiguration mechanism. In accordance with the RPL Control
Message [RFC6550], this document defines the particular messages by
defining new options. These new options presented in this
specification all follow the RPL Control Message Option generic
format as specified in RFC6550 (see Section 6 in RFC6550 for more
details).
4.1. Address Solicitation
The Address Solicitation option MAY be present in DAO or DIS messages,
and its format is as follows:
Zhu et al. Expires November 11, 2013 [Page 6]
Internet-Draft Address Autoconfiguration for RPL May 10, 2013
0
0 1 2 3 4 5 6 7
+-+-+-+-+-+-+-+-+
| Type = 0x10 |
+-+-+-+-+-+-+-+-+
Figure 1 Format of the Address Solicitation Option
The Address Solicitation option is used for a node to request Address
Information messages from its parent. A parent just receives Address
Solicitation messages from its children. When an RPL message which
contains this option is not sent by its child, the receiver MUST
silently ignore the option.
Option Type: 0x10. (to be confirmed by IANA)
4.2. Address Information and Address Lease Response
The Address Information option and the Address Lease Response option
MAY be present in DIO messages, and the format is as follows:
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=0x11/0x16 | Option Length | Prefix Length |A| N | Resvd |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Valid Lifetime |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
+ +
| |
+ Prefix +
| |
+ +
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Figure 2 Format of the Address Information Option and the Address
Lease Response Option
The Address Information option is used to advertise a node's own
address information for address autoconfiguration. A node can assign
its own address according to the received Address Information message.
The address of parent becomes the prefix address of child.
Zhu et al. Expires November 11, 2013 [Page 7]
Internet-Draft Address Autoconfiguration for RPL May 10, 2013
The Address Lease Response option is used to respond to the Address
Lease Request messages when a node agrees to lend an address to
another node.
Option Type: 0x11, indicates that this is an Address Information
message. 0x16, indicates that this is an Address Lease Response
message. (to be confirmed by IANA)
Option Length: 22. 8-bit unsigned integer, representing the length in
octets of the option, not including the Option Type and Length fields.
Prefix Length: 8-bit unsigned integer. The number of valid leading
bits in the prefix.
A: 1-bit autonomous address configuration flag. When set, indicates
that this prefix can be used for address configuration as specified
in this specification.
N: 3-bit unsigned integer. The permissible length of a random number
(in bits) that child node generates. The n bits random number will
afterward be concatenated with the parent's address as the child's
address. The value of n should satisfy 2^n>Cm, where Cm is the
maximum number of supported child nodes.
Resvd: 4-bit unused field. It MUST be initialized to zero by the
sender and MUST be ignored by the receiver.
Valid Lifetime: 32-bit unsigned integer. The length of time in
seconds that the prefix is valid. A value of all one bits (0xffffffff)
represents infinity.
Prefix: An IPv6 address or a prefix of an IPv6 address. The Prefix
field contains the node's own address or the creditor node's address.
It depends on the Option Type field.
Unassigned bits of the option are reserved. They MUST be set to zero
on transmission and MUST be ignored on reception.
4.3. Address Advertisement and Address Acknowledgement
The Address Advertisement option and the Address Acknowledgement
option MAY be present in DAO messages, and the format is as follows:
Zhu et al. Expires November 11, 2013 [Page 8]
Internet-Draft Address Autoconfiguration for RPL May 10, 2013
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=0x12/0x19 | Option Length | Address Length| Addr Sequence |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|S| Flag | Reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
+ +
| |
+ Address +
| |
+ +
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Figure 3 Format of the Address Advertisement Option and the Address
Acknowledgement Option
The Address Advertisement option is used for a node to inform its
parent of the address that it intends to use.
The Address Acknowledgement option is used when the child node
confirms a leased address and notifies its parent to insert the
corresponding routing entry.
Option Type: 0x12, indicates that this is a Address Advertisement
message. 0x19, indicates that this is an Address Acknowledgement
message. (to be confirmed by IANA)
Option Length: 22.
Address Length: 8-bit unsigned integer. The number of valid leading
bits in the Address field.
Addr Sequence: 8-bit unsigned integer. Incremented at each unique
Address Advertisement message from a node and echoed in the REJECTION
or APPROVE message.
Flags: 7-bit unused field is reserved for flags. The field MUST be
initialized to zero by the sender and MUST be ignored by the receiver.
S: The 1-bit flag is the Address Sequence predicate. If the S flag is
cleared then the Address Sequence field is not valid and the Address
Sequence field MUST be set to zero on transmission and ignored upon
receipt.
Zhu et al. Expires November 11, 2013 [Page 9]
Internet-Draft Address Autoconfiguration for RPL May 10, 2013
Reserved: This field is unused. It MUST be initialized to zero by the
sender and MUST be ignored by the receiver.
Address: An IPv6 address or a prefix of an IPv6 address. The Address
field contains a node's own address. The node randomly generates n
bits string and then concatenates the n bits with the parent's
address as its own address.
Unassigned bits of the option are reserved. They MUST be set to zero
on transmission and MUST be ignored on reception.
4.4. REJECTION and APPROVE
The REJECTION option and the APPROVE option MAY be present in DAO-ACK
messages, and the format is as follows:
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=0x13/0x14 | Option Length | Reserved | Addr Sequence |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Figure 4 Format of the REJECTION Option and the APPROVE Option
The REJECTION option is used to indicate that the requested address
has already been utilized by another node.
The APPROVE option is used to indicate that the child can get the
requested address approved.
Option Type: 0x13, indicates that this is a REJECTION message. 0x14,
indicates that this is an APPROVE message. (to be confirmed by IANA)
Option Length: 2.
Reserved: 8-bit unused field. It MUST be initialized to zero by the
sender and MUST be ignored by the receiver.
Addr Sequence: 8-bit unsigned integer. The Address Sequence is used
to correlate an Address Advertisement message and a REJECTION or
APPROVE message. Incremented at each unique Address Advertisement
message and echoed in the REJECTION or APPROVE message.
4.5. Address Lease Request and Address Lease Parent Request
The Address Lease Request option and the Address Lease Parent Request
option MAY be present in DIS messages, and the format is as follows:
Zhu et al. Expires November 11, 2013 [Page 10]
Internet-Draft Address Autoconfiguration for RPL May 10, 2013
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=0x15/0x17 | Option Length | Prefix Length | N | Resvd |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| RPLInstanceID | Version Number| Rank |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
+ +
| |
+ Address +
| |
+ +
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Figure 5 Format of the Address Lease Request Option and the Address
Lease Parent Request Option
The Address Lease Request option is used for a node to request
Address Lease Response messages from its brother nodes.
The and Address Lease Parent Request option is used when an orphan
node intends to get a new parent.
Option Type: 0x15, indicates that this is a Address Lease Request
message. 0x17, indicates that this is an Address Lease Parent Request
message. (to be confirmed by IANA)
Option Length: 22.
Prefix Length: 8-bit unsigned integer. The number of valid leading
bits in the Address. The Prefix Length field, as well as the N field,
provide necessary information for longest prefix match.
N: 3-bit unsigned integer. The permissible length of a random number
(in bits) that child node generates. (see Section 4.2. )
Flags: 5-bit unused field are reserved for flags. The field MUST be
initialized to zero by the sender and MUST be ignored by the receiver.
RPLInstanceID: 8-bit unsigned integer containing the RPLInstanceID.
Version Number: 8-bit unsigned integer containing the value of
DODAGVersionNumber.
Zhu et al. Expires November 11, 2013 [Page 11]
Internet-Draft Address Autoconfiguration for RPL May 10, 2013
Rank: 16-bit unsigned integer indicating the DODAG rank of the node
sending the message.
Address: An IPv6 address or a prefix of an IPv6 address of the node
sending the message.
A receiver can determine whether it is a candidate creditor node (or
debtor node) through the Prefix Length field, N, Rank and Address
field.
Unassigned bits of the option are reserved. They MUST be set to zero
on transmission and MUST be ignored on reception.
4.6. Address Lease Notification
The Address Lease Notification option MAY be present in DAO or DIO
messages, and its format is as follows:
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=0x18 | Option Length | Flags | Reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
+ +
| |
+ Address1 +
| |
+ +
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
+ +
| |
+ Address2 +
| |
+ +
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Figure 6 Format of the Address Lease Notification Option
The Address Lease Notification option is used for a node to inform
the common parent or the creditor node of the debtor node's own
address and the corresponding leased address. (see Section 5.4. )
Option Type: 0x18. (to be confirmed by IANA)
Zhu et al. Expires November 11, 2013 [Page 12]
Internet-Draft Address Autoconfiguration for RPL May 10, 2013
Option Length: 34.
Flags: 8-bit unused field reserved for flags. The field MUST be
initialized to zero by the sender and MUST be ignored by the receiver.
Reserved: 8-bit unused field. It MUST be initialized to zero by the
sender and MUST be ignored by the receiver.
Address1: An IPv6 address or a prefix of an IPv6 address of the
debtor node.
Address2: An IPv6 address or a prefix of an IPv6 address that is
leased by the debtor node.
The receiver MUST silently ignore this option, if it is not the
corresponding common parent or creditor node.
Unassigned bits of this option are reserved. They MUST be set to zero
on transmission and MUST be ignored on reception.
5. Address Autoconfiguration
This address autoconfiguration mechanism is used to operate in RPL.
As we know, RPL had defined the process of parent selection through
the Objective Function (OF) and constructed the topologies. Moreover,
a node can execute the address configuration process immediately
without waiting for the whole topology to be constructed, when it has
determined its preferred parent node.
5.1. Address Assignment
The address assignment procedure consists of two phases: (a) address
allocation and (b) address conflict detection. Firstly, we must
choose an integer n for the entire sensor network and initiate the
protocol by broadcasting a packet which contains the value. The value
of n should satisfy 2^n>Cm, where Cm is the maximum number of
supported child nodes.
The address allocation procedure is detailed as follows:
1. The parent sends its children the Address Information messages
that contain its own address.
Zhu et al. Expires November 11, 2013 [Page 13]
Internet-Draft Address Autoconfiguration for RPL May 10, 2013
2. Child node generates its own address through randomly generates n-
bit string and then concatenates this string with the parent's
address. As a result, the address of its parent becomes the
address prefix of the node. For example, if the received parent's
address is "0011" and the random 4 bits string is "0101", then
this child's own address is "00110101".
3. The child node sends an Address Advertisement message containing
its address back to its parent, after waiting for a random time in
order to avoid collisions.
4. The child waits for a fixed amount of time to listen for REJECTION
or APPROVE packet from its parent.
5. If the node receives an APPROVE from its parent node, it will
confirm its address and send the address to its children in the
Address Information messages.
The address conflict detection procedure is detailed as follows:
1. The parent waits to receive an Address Advertisement from the
direct children of itself.
2. After the parent receives a child's address, it will check if the
address has already been allocated to another node.
3. If the received address has not been allocated, a parent will send
out an APPROVE message as a response and remember this approved
address. Then the node goes back to Step 1. The addresses that a
parent remembers are only temporary and are deleted once the nodes
leave or die.
4. If the received address has already been allocated, a parent will
send out a REJECTION message as a response. Then the node goes
back to Step 1.
The address assignment algorithm thus guarantees the uniqueness of
each sensor node's address.
In addition, some reserved addresses can't be assigned to a node. For
example, a value of all one bits is a broadcast address.
If the network contains multiple roots, then the roots are expected
to be federated by a common backbone. Thus many existing address
assignment protocols are enabled to serve the root nodes. The issue
of address assignment among the root nodes is out of scope for this
specification.
Zhu et al. Expires November 11, 2013 [Page 14]
Internet-Draft Address Autoconfiguration for RPL May 10, 2013
5.2. Address Lease
In some conditions the node density of the sensor networks cannot be
predicted exactly. There may be no unused address in the parent due
to the restriction of node address space. This will lead to the
problem that nodes could not join the network. This addressing
autoconfiguration mechanism provides a solution to improve the
probability of nodes joining to the network. There is a need for
special Address Lease Tables in order to record the debtor nodes and
the corresponding leased addresses.
The address lease procedure is detailed as follows:
1. A new node wants to join the network, then this node A send an
Address Solicitation to its parent node B. The node B will check
whether the number of child nodes is reached to the maximum number.
2. If the node B has a free address, then the node B sends its own
address to the node A, in order to complete the whole address
assignment procedure.
3. If the node B has no a free address, then the node B locally
broadcasts the Address Lease Request to discover its candidate
creditor node set. The candidate creditor node set should be a
restricted subset of the brother node set. The member of the
brother node set must have the same parent with the node B.
Further, the node B can discover all its brother node by longest
prefix match. The preferred creditor node is a member of the
candidate creditor node set. The exact policies for selecting the
preferred creditor node are implementation-dependent and Rank-
dependent. But it is more important that the preferred creditor
node must have one or more unallocated addresses. The preferred
creditor node is conceptually a single brother node although it
may be a set of multiple nodes if those candidate nodes are
equally preferred and have identical rank, preferably choosing the
node sending the strongest signal. If there is no satisfactory
brother node, then the node B's parent is regarded as the
preferred creditor node.
4. The preferred creditor node C received Address Lease Request can
send a Address Lease Response to the node B with its own address.
The node B will forward the Address Lease Response to the node A.
5. The node A generates its own address through the address
allocation procedure and sends it to its parent node B. The node B
will forward the Address Advertisement to the creditor node C.
Zhu et al. Expires November 11, 2013 [Page 15]
Internet-Draft Address Autoconfiguration for RPL May 10, 2013
6. Creditor node C should run the address conflict detection
procedure and send back an APPROVE or REJECTION message. The node
B will forward the message to the node A. Furthermore, the
creditor node C must insert this approved address to the Address
Lease Table and notify the common parent of this information ( if
the preferred creditor node C is the node B's parent, then it
could not send the Notification).
7. The node A should confirm its address on the basis of the received
APPROVE or REJECTION message. And finally, it should send the
Address Acknowledgement back. Then, the node B inserts the child's
address into its routing table.
This address lease algorithm increases the probability that nodes
join the network, especially in the high node density area.
5.3. Address Reusing
In order to improve the utilization of addresses, the addresses of
nodes should can be reused.
When a node leaves, it must send messages, such as No-Path DAO
messages, to notify each of its parents. Then, the parent should
delete the corresponding entry from its routing table. If the parent
detects that the leaving node's address is a borrowed address, it
should notify its parent and creditor node to delete the
corresponding entries. The address of the leaving node will be reused.
When a node dies, it might not send a leaving notification to its
parent. The parent does not receive any traffic from its child within
a certain period of time. Then it sends queries to the child multiple
times. If there is still no reply to it, then the parent should
delete the corresponding entry from its routing table.
5.4. Partitioning and Merging
Due to topology change or node failure, nodes may join or leave the
network at any time. Therefore, network partitioning and merging
potentially occur. In order to balance between cost of maintenance
and consistency, especially for large-scale deployments, we exploit
the concept of address lease to handle this complex situation.
A node that loses its parent is called an Orphan in this document.
The procedure is detailed as follows:
Zhu et al. Expires November 11, 2013 [Page 16]
Internet-Draft Address Autoconfiguration for RPL May 10, 2013
1. After waiting for a certain period of time, the orphan node D
locally broadcasts the Address Lease Parent Request messages to
discover its candidate debtor node set by longest prefix match. If
the orphan node D's former parent is the node E, then the
candidate debtor node set should be a restricted subset of the
node E's brother node set. The member of the brother node set must
have the same parent with the node E. The preferred debtor node is
a member of the candidate debtor node set. The exact policies for
selecting the preferred debtor node is implementation-dependent
and Rank-dependent, according to the method of choosing a
preferred parent node in RPL. If there is no satisfactory brother
node, then the node E's parent is regarded as the preferred debtor
node. The orphan node will choose the preferred debtor node as its
new parent. The preferred debtor node must be of rank less than
the node D's.
2. If a debtor node F has agreed to become the orphan node's parent,
then the orphan node D should send an Address Advertisement
containing its own address to the debtor node F.
3. The debtor node F must check whether it is fortunately the node
D's former parent. If the node F is the node D's former parent,
then it just should insert the corresponding entry to the routing
table.
4. Otherwise, the debtor node F must notify its parent G that the
node D is the child of node F now (if the preferred debtor node F
is the node E's parent, then it could not send the Notification).
The parent G should insert the corresponding entry to the routing
table. When a new node joining the network is assigned the same
address of the node D's former parent, the node G must send a
Address Lease Notification to it in order to inform the new child
that the address of the node D has been used. And the new child
should insert the corresponding entry to the Address Lease Table
in order to record the debtor node and the corresponding leased
address (i.e. the address of the node D).
When two different partitions merge, nodes in the sub-DODAG do not
need to reconfigure their address. For large-scale deployments, this
scheme can significantly reduce the cost of network maintenance.
Zhu et al. Expires November 11, 2013 [Page 17]
Internet-Draft Address Autoconfiguration for RPL May 10, 2013
6. Routes
6.1. Upward Routes
RPL provisions routes Up towards DODAG roots and further details may
be found in RFC6550. In our scheme, the data packets can be
forwarded upwards through the longest prefix match or default route.
6.2. Downward Routes
Downward routes support the applications that require P2MP or P2P
traffic. Each node's routine routing table only needs to store one-
hop routing table entries.
For the downward routes, when a node receives a data packet, it
should first look up a matching entry in the Address Lease Table and
the routine routing table according to the longest matching prefix.
The length of the matching prefix of this entry must be longer than
current node's. If two or more entries in these two tables satisfy
the condition (i.e. have the same length of matching prefix), the
successor in routine routing table should be chosen.
Therefore, the amount of routing entries held by a node is
significantly reduced, which increases routing efficiency. Moreover,
the messages can travel down toward the target group of nodes.
7. Security Considerations
This document does not specify any security considerations. This
address autoconfiguration mechanism expects to utilize link-layer or
other security mechanisms to meet security requirements. These
external security mechanisms are considered to be out of scope for
this specification. Additional considerations can be found in
the RPL protocol [RFC6550].
8. IANA Considerations
IANA is requested to create a registry for the Message Options in
this document. And we define these values following the RPL
protocol [RFC6550].
New values may be allocated only by an IETF Review. Each value should
be tracked with the following qualities:
o Value
o Meaning
Zhu et al. Expires November 11, 2013 [Page 18]
Internet-Draft Address Autoconfiguration for RPL May 10, 2013
o Defining RFC
+-------+-----------------------------------+-------------------+
| Value | Meaning | Reference |
+-------+-----------------------------------+-------------------+
| 0x10 | Address Solicitation | This document |
| | | |
| 0x11 | Address Information | This document |
| | | |
| 0x12 | Address Advertisement | This document |
| | | |
| 0x13 | REJECTION | This document |
| | | |
| 0x14 | APPROVE | This document |
| | | |
| 0x15 | Address Lease Request | This document |
| | | |
| 0x16 | Address Lease Response | This document |
| | | |
| 0x17 | Address Lease Parent Request | This document |
| | | |
| 0x18 | Address Lease Notification | This document |
| | | |
| 0x19 | Address Acknowledgement | This document |
+-------+-----------------------------------+-------------------+
RPL Control Message Options
9. References
9.1. Normative References
[RFC6550] T. Winter, P. Thubert, A. Brandt, J. Hui, R. Kelsey, P.
Levis, K. Pister, R. Struik, JP. Vasseur, and R. Alexander,
"RPL: IPv6 Routing Protocol for Low-Power and Lossy
Networks", RFC6550, March 2012.
[RFC2119] S.Bradner, "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119, March 1997.
[RFC6552] P.Thubert, "RPL Objective Function 0", RFC6552, March 2012.
[I-D.ietf-roll-terminology] JP.Vasseur, "Terminology in Low power And
Lossy Networks", draft-ietf-roll-terminology-12, September
2013.
[RFC6206] P.Levis, T.Clausen, J.Hui, O.Gnawali, and J.Ko, "The
Trickle Algorithm", RFC6206, March 2011.
Zhu et al. Expires November 11, 2013 [Page 19]
Internet-Draft Address Autoconfiguration for RPL May 10, 2013
9.2. Informative References
[RFC2131] R. Droms, "Dynamic Host Configuration Protocol", RFC2131,
March 1997.
Zhu et al. Expires November 11, 2013 [Page 20]
Internet-Draft Address Autoconfiguration for RPL May 10, 2013
10. Acknowledgments
Many thanks to Linjuan Zhang, Lin Zhu, Yingliang Chang, and Weiwei Wu
for their support.
Authors' Addresses
Wan-Ting Zhu, De-Yun Gao, Hong-Ke Zhang, Wei-Cheng Zhao
National Engineering Lab for NGI Interconnection Devices
Beijing Jiaotong University, China
Phone: +8613521693762
Email: 11111019@bjtu.edu.cn
gaody@bjtu.edu.cn
hkzhang@bjtu.edu.cn
11111018@bjtu.edu.cn
Zhu et al. Expires November 11, 2013 [Page 21]
