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]