ROLL J. Guo Internet-Draft P. Orlik Intended status: Standards Track G. Bhatti Expires: October 5, 2013 Mitsubishi Electric Research Laboratories April 3, 2013 Loop Free DODAG Local Repair draft-guo-roll-loop-free-dodag-repair-01 Abstract IETF has been developing IPv6 based standards for Low-power and Lossy Networks (LLNs) to meet requirements of constrained applications, such as field monitoring, inventory control and so on. IPv6 Routing Protocol for LLNs (RPL) has been published in [RFC6550]. Based on routing metrics and constraints [RFC6551], RPL builds Directed Acyclic Graph (DAG) topology to establish bidirectional routes for LLNs for traffic types of multipoint-to-point, point-to-multipoint, and point-to-point. RPL routes are optimized for traffic to or from one or more roots that act as sinks. As a result, a DAG is partitioned into one or more Destination Oriented DAGs (DODAGs), one DODAG per sink. RPL is widely considered as a feasible routing protocol for LLNs. However, DODAG loops caused by local DODAG repair mechanism is an issues to be addressed. This draft introduces a loop free local DODAG repair mechanism. This draft also introduces a piggybacked data option for transferring delay sensitive data during route repair process. The piggybacked data can be included in DODAG Repair Request (DRQ) message or DODAG Information Solicitation (DIS) message. Guo, et al. Expires October 5, 2013 [Page 1] Internet-Draft Loop Free DODAG Repair April 3, 2013 Status of this Memo This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF). Note that other groups may also distribute working documents as Internet-Drafts. The list of current Internet- Drafts is at http://datatracker.ietf.org/drafts/current/. 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." This Internet-Draft will expire on April 4, 2013. Copyright Notice Copyright (c) 2012 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. Guo, et al. Expires October 5, 2013 [Page 2] Internet-Draft Loop Free DODAG Repair April 3, 2013 Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . . 5 3. ICMPv6 RPL Control Message Extension . . . . . . . . . . . . . . 6 3.1. DODAG Repair Request (DRQ) . . . . . . . . . . . . . . . . 6 3.1.1. Format of the DRQ Base Object . . . . . . . . . . . 6 3.1.2. Secure DRQ . . . . . . . . . . . . . . . . . . . . . 7 3.1.3. DRQ Options . . . . . . . . . . . . . . . . . . . . 8 3.2. DODAG Repair Reply (DRP). . . . . . . . . . . . . . . . . . 8 3.2.1. Format of the DRP Base Object . . . . . . . . . . . 8 3.2.2. Secure DRP . . . . . . . . . . . . . . . . . . . . . 9 3.2.3. DRP Options . . . . . . . . . . . . . . . . . . . . 9 3.3. Format of the Path Option . . . . . . . . . . . . . . . . . 9 4. DODAG Local Repair . . . . . . . . . . . . . . . . . . . . . . 10 4.1. DODAG Local Repair in Storing Mode . . . . . . . . . . . . 11 4.1.1. DRQ Message Processing . . . . . . . . . . . . . . 11 4.1.2. DRP Message Processing . . . . . . . . . . . . . . 12 4.2. DODAG Local Repair in Non-Storing Mode . . . . . . . . . . 13 4.2.1. DRQ Message Processing . . . . . . . . . . . . . . . 14 4.2.2. DRP Message Processing . . . . . . . . . . . . . . . 14 5. DIS Message with Piggybacked Data . . . . . . . . . . . . . . . 15 5.1. Format of the Modified DIS Base Object . . . . . . . . . . 17 5.2. Modified DIS Options . . . . . . . . . . . . . . . . . . . 17 5.3. Process of the Modified DIS message . . . . . . . . . . . 17 6. Security Considerations . . . . . . . . . . . . . . . . . . . . 17 7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . . 18 8. References . . . . . . . . . . . . . . . . . . . . . . . . . . 18 8.1. Normative References . . . . . . . . . . . . . . . . . . . 18 8.2. Informative References . . . . . . . . . . . . . . . . . . 19 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 19 Guo, et al. Expires October 5, 2013 [Page 3] Internet-Draft Loop Free DODAG Repair April 3, 2013 1. Introduction Low-power and Lossy Networks (LLNs) are a class of networks in which nodes and their communication links are constrained. LLN nodes typically operate with constrains on processing power, physical size, memory, power consumption, lifetime, and rate of activity. Their communication links are characterized by high loss rate, low data rate, instability, low transmission power, and short transmission range. There can be from a few dozen up to thousands of nodes within a LLN. Routing in LLNs is different from routing in mobile ad-hoc networks. IETF has developed an IPv6 Routing Protocol for LLNs (RPL) in [RFC6550]. RPL supports multipoint-to-point traffic and point-to- multipoint traffic. The support for point-to-point traffic is also available. RPL builds Directed Acyclic Graph (DAG) topology, which is partitioned into one or more Destination Oriented DAGs (DODAGs). DODAG is basic logical structure in RPL. RPL nodes construct and maintain DODAG through the DODAG Information Object (DIO) message which is transmitted via link-local multicasting by using the Trickle timer [RFC6206]. The sink in a DODAG is called the DODAG root. RPL defines rules to transmit the DIO messages within a DODAG. The DODAG root configures the DODAG parameters including RPLInstanceID, DODAGVersionNumber, DODAGID, Rank, etc. and advertises the DODAG parameters in the DIO messages. To join a DODAG, a node selects a set of DODAG parents, on the routes towards the DODAG root, and a preferred DODAG parent as the preferred next hop node for upward traffic. Once a node joins a DODAG, it transmits DIO messages to advertise the DODAG parameters. The traffic inside a LLN flows along the edges of the DODAG, either upward or downward. In RPL, upward routes, having the DODAG root as destination, are provided by the DODAG construction mechanism using DIO messages. Downward routes, from the DODAG root to any other destination, are provided by these destinations transmitting the Destination Advertisement Object (DAO) messages. Three different modes of operation (MOP) for downward routes are specified in [RFC6550]: 1) No downward routes maintained by RPL. 2) Storing mode of operation in which each router stores downward routing tables for its sub-DODAG. In Storing mode, the DAO message is sent to DAO parents. A node unicasts the DAO messages to the selected parent(s). Transmission of the DAO messages propagates from the nodes towards the DODAG root, where each intermediate router adds its downward routing stack to the DAO messages. In Storing mode, downward traffic is sent by using the downward Guo, et al. Expires October 5, 2013 [Page 4] Internet-Draft Loop Free DODAG Repair April 3, 2013 routing tables. 3) Non-Storing mode of operation in which only the DODAG root stores routes to all nodes in the network. In Non-Storing mode, the DAO message is sent to the DODAG root. A node unicasts the DAO messages to the DODAG root, which then calculates routes to all destinations by piecing together the information collected from the DAO messages. In Non-Storing mode, downward traffic is sent by way of source routing. An RPL node may act as a leaf node or as a router. RPL defines operation rules for both leaf node and router in [RFC6550]. For example, a leaf node does not extend DODAG connectivity. An RPL router needs to implement Trickle [RFC6206]. An RPL router implementation needs to support the MOP in use by the DODAG, that is, support for upward routes only or support for upward routes and downward routes in Storing mode or support for upward routes and downward routes in Non-Storing mode. RPL has been implemented and tested. It has been shown that DODAG loops occur quite often [83rd IETF Meeting Presentation]. The cause of DODAG loops comes from rank increase by DODAG local repair mechanism. This draft introduces a method for repairing DODAG locally without causing any DODAG loops. The DODAG local repair method applies to both Storing and Non-Storing modes of operation in RPL. 2. Terminology The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in [RFC2119]. Additionally, this draft employs terminologies defined in [RFC6550], and extends following terminologies: DIO: DODAG Information Object in which the rank is represented by two integers. Up: Up refers to the direction from leaf node or router node towards the DODAG root. Down: Down refers to the direction from the DODAG root towards leaf node or router node. This draft introduces the following new terminologies: DRQ: DODAG Repair Request DRP: DODAG Repair Reply Guo, et al. Expires October 5, 2013 [Page 5] Internet-Draft Loop Free DODAG Repair April 3, 2013 Rank_DRQ: The rank of the node generating the DRQ message. Rank_DRP: The rank of the node transmitting the DRP message. DRQID: IPv6 address of the node generating DRQ message. DRSN: Sequence number of the DRQ message of the node generating DRQ message. 3. ICMPv6 RPL Control Message Extension This draft uses RPL control messages defined in in Figure 6 and Figure 7 of [RFC6550]. In addition, to repair DODAG locally, two new RPL control messages, DODAG Repair Request (DRQ) message and DODAG Repair Reply (DRP) message, are introduced. The code field for the DRQ and DRP messages needs to be assigned by IANA. The message base for DRQ and DRP are defined as follows. 3.1. DODAG Repair Request (DRQ) The DRQ message is used by a node to repair a DODAG locally if a parent becomes unreachable. A node may also use the DRQ message to discover additional parents if it is necessary. 3.1.1. Format of the DRQ Base Object 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | RPLInstanceID |Version Number | RankQ | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | DRSN | HC | MH |P| Reserved | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | + + | | + DODAGID + | | + + | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | + + | | + DRQID + | | + + Guo, et al. Expires October 5, 2013 [Page 6] Internet-Draft Loop Free DODAG Repair April 3, 2013 | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Option(s)... +-+-+-+-+-+-+-+-+ Figure 1: The DRQ Base Object RPLInstanceID: 8-bit unsigned field as described in [RFC6550] to indicate which RPL Instance the DODAG is a part. Version Number: 8-bit unsigned integer as described in [RFC6550] to indicate the DODAGVersionNumber. RankQ: 16-bit unsigned integer indicating rank of the node generating the DRQ message. DRSN: 8-bit field indicating sequence number of the DRQ message at the node generating the DRQ message. HC: 4-bit field to indicate the number of hops traveled by a DRQ message. MH: 4-bit field to indicate the maximum number of hops a DRQ message can travel. If a DRQ message reaches the maximum number of hops, it must be ignored. P: 1-bit flag to indicate if the sender has included the piggybacked data. If P = 1, piggybacked data is present and a receiver MAY consider to forward piggybacked data towards the DODAG root. If P = 0, piggybacked is not present. A node sets P flag to 1 only if its parent set is empty and it has a delay sensitive packet to transmit. For example, if a building monitoring sensor detects fire, it must send a notification as soon as possible. Reserved: 15 bits of the DRQ Base are reserved. They must be set to zero on transmission and must be ignored on reception. DODAGID: 128-bit field as defined in [RFC6550]. A DODAGID is the identifier of a DODAG root. The DODAGID is unique within the scope of a RPL Instance in the LLN. The DODAGID must be a routable IPv6 address belonging to the DODAG root. DRQID: 128-bit IPv6 address of the node generating the DRQ message. 3.1.2. Secure DRQ A Secure DRQ message follows the format in Figure 7 of [RFC6550], where the base format is the DRQ message shown in Figure 1. Guo, et al. Expires October 5, 2013 [Page 7] Internet-Draft Loop Free DODAG Repair April 3, 2013 3.1.3. DRQ Options The DRQ message may carry valid options. This draft allows for the DRQ message to carry the following options: 0x00 Pad1 0x01 PadN Path: This option field is present only if MOP is Non-Storing. The Path field contains IPv6 addresses of traversed nodes by the DRQ message along the path. PiggyData: This option field is present only if flag P = 1. PiggyData field contains data to be forward to the root.. 3.2. DODAG Repair Reply (DRP) Upon receiving a DRQ message, a router with lower rank and non- empty DODAG parent set may generate a DRP message in responding to a received DRQ message. 3.2.1. Format of the DRP Base Object 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | RPLInstanceID |Version Number | RankQ | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | RankP | DRSN | Reserved | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | + + | | + DODAGID + | | + + | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | + + | | + DRPID + | | + + | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Option(s)... +-+-+-+-+-+-+-+-+ Guo, et al. Expires October 5, 2013 [Page 8] Internet-Draft Loop Free DODAG Repair April 3, 2013 Figure 2: The DRP Base Object RPLInstanceID: 8-bit unsigned field as described in [RFC6550] to indicate which RPL Instance the DODAG is a part. Version Number: 8-bit unsigned integer as described in [RFC6550] to indicate the DODAGVersionNumber. RankQ: 16-bit unsigned integer indicating rank of the node generating the DRQ message. RankP: 16-bit unsigned integer indicating rank of the node transmitting the DRP message. DRSN: 8-bit field indicating the sequence number of DRQ message at the node generating the DRQ message. Reserved: 8 bits of the DRP Base are reserved. They must be set to zero on transmission and must be ignored on reception. DODAGID: 128-bit field as defined in [RFC6550]. A DODAGID is the identifier of a DODAG root. The DODAGID is unique within the scope of a RPL Instance in the LLN. The DODAGID MUST be a routable IPv6 address belonging to the DODAG root. DRPID: 128-bit IPv6 address of the node that is destination of the DRP message. 3.2.2. Secure DRP A Secure DRP message follows the format in Figure 7 of [RFC6550], where the base format is the DRP message shown in Figure 2. 3.2.3. DRP Options The DRP message may carry valid options. This draft allows for the DRP message to carry the following options: 0x00 Pad1 0x01 PadN Path: This option is present only if MOP is Non-Storing. The Path field contains IPv6 addresses of traversed nodes by the DRQ message along the path. 3.3. RPL Control Message Options The formats of option Pad1 and PadN are described in Figure 20 and Guo, et al. Expires October 5, 2013 [Page 9] Internet-Draft Loop Free DODAG Repair April 3, 2013 Figure 21 of [RFC6550], respectively. The format of the Path option is as follows: 0 1 2 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- - - - - - - - | Option Type | Option Length | Path Data +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- - - - - - - - Figure 3: Format of the Path Option Option Type: 8-bit identifier of the type of option. The Option Type value needs to be assigned by IANA. Option Length: 8-bit unsigned integer, representing the length in octets of the option Path Data field, not including the Option Type and Option Length fields. Path Data: A variable length field that contains a list of IPv6 addresses. The format of the PiggyData option 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Option Type | Option Length | RPLInstanceID |Version Number | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | + + | | + DODAGID + | | + + | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | + + | | + SourceID + | | + + | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Payload +-+-+-+-+-+-+-+-+ Guo, et al. Expires October 5, 2013 [Page 10] Internet-Draft Loop Free DODAG Repair April 3, 2013 Figure 4: Format of the PiggyData Option Option Type: 8-bit identifier of the type of option. The Option Type value needs to be assigned by IANA. Option Length: 8-bit unsigned integer, representing the length in octets of the option PiggyData field, not including the Option Type and Option Length fields. RPLInstanceID, Version Number and DODAGID are described in RFC 6550. SourceID is same as DRQID. PiggyData: A variable length field that contains payload of piggybacked data. 4. Loop Free DODAG Local Repair In RPL, the rank plays very important role in the DODAG construction and maintenance. The rank of a node defines a position of the node relative to other nodes with respect to the DODAG root. Each node maintains its own rank. The DODAG root has the lowest rank. Nodes maintain their ranks based on parent-child relationship such that a child must have a rank strictly greater than ranks of all its DODAG parents. The DODAG root has no parent. The acyclic structure of the DODAG is guaranteed as long as the rank of any node is strictly greater than ranks of its DODAG parents. It is safe for a node to decrease its rank, as long as its rank remains greater than the ranks of its DODAG parents. However, rank increase can cause DODAG loops. The DODAG local repair methods provided in this draft does not increase the rank, and therefore, is loop free. When a DODAG parent becomes unreachable, a node may switch to another DODAG parent for upward traffic. DODAG may be locally repaired by the node transmitting a DRQ message. The DRQ message is transmitted by the DRQ message generator via link-local multicasting to all-RPL- nodes. Upon receiving a DRQ message, a link-local neighboring router which is not the DODAG root discards the DRQ message if it does not have any DODAG parent. If the link-local neighboring router is the DODAG root, it accepts the DRQ message and generates a DRP message. If the link-local neighboring router is not the DODAG root and has a non- empty DODAG parent set and its rank is lower than RankQ, it accepts the DRQ message and generates a DRP message. If the link-local neighboring router is not the DODAG root and has a non-empty DODAG parent set and its rank is greater than or equal to RankQ, it forwards the DRQ message to its preferred DODAG parent. This Guo, et al. Expires October 5, 2013 [Page 11] Internet-Draft Loop Free DODAG Repair April 3, 2013 forwarding process continues until the DRQ message is discarded by a router that has an empty DODAG parent set or the DRQ message reaches a node which is either the DODAG root or a router that has a non- empty DODAG parent set and a rank lower than RankQ, a DRP message is then generated. The DRP message is unicasted. In Storing mode, the DRP message generator transmits the DRP message to the DRQ message generator by using a downward routing table. In Non-Storing mode, the DRP message generator transmits the DRP message to the DRQ message generator by way of source routing via the Path option. 4.1. DODAG Local Repair in Storing Mode In Storing mode, if a DODAG parent becomes unreachable, a node removes that DODAG parent from its DODAG parent set. If the updated DODAG parent set becomes empty, the node shall transmit a DRQ message to discover new DODAG parents. If the updated DODAG parent set is not empty, the node checks if the removed DODAG parent is its preferred DODAG parent. If yes, the node shall select a new preferred DODAG parent. Whether or not the removed DODAG parent is the preferred DODAG parent, the node may transmit a DRQ message to discover additional parents. The node may also schedule a No-Path DAO message transmission if the removed DODAG parent is its DAO parent. To transmit a DRQ message in Storing mode, the node generates a DRQ message. It sets RPLInstanceID, DODAGVersionNumber and DODAGID by using the maintained DODAG parameters. It sets RankQ to its rank. The node increases its DRSN by 1 and sets HC = 0, and MH to an appropriate value. There is no Path option field in Storing mode. 4.1.1. DRQ Message Processing When a router receives a DRQ message, it discards the DRQ message if its DODAG parent set is empty. Otherwise, the router performs the following filtering process and discards the DRQ message if any of following conditions is true: i) RPLInstanceID or DODAGVersionNumber or DODAGID in the DRQ message is not equal to the respective value maintained by the router. ii) The DRQ message was received already by comparing DRQID and DRSN. iii) HC is equal to MH. iv) The DRQ message is transmitted by router's DODAG parent. Guo, et al. Expires October 5, 2013 [Page 12] Internet-Draft Loop Free DODAG Repair April 3, 2013 v) The DRQ message is generated by router itself or by its DODAG parent. If the DRQ message passes filtering process, the receiving router processes the DRQ message further. If the receiving router is the DODAG root, it accepts the DRQ message and generates a DRP message. To generate a DRP message, the DODAG root copies RPLInstanceID, DODAGVersionNumber, DRSN, and DODAGID from the DRQ message. It sets DRPID to DRQID, RankQ to the RankQ in DRQ message, and RankP to its rank. The DODAG root forwards the DRP message to the node from which it received the DRQ message. If the receiving router is not the DODAG root and its rank is lower than RankQ, the router accepts the DRQ message and generates a DRP message as the root does. The router forwards the DRP message to the node from which it received the DRQ message. If the receiving router is not the DODAG root and its rank is greater than or equal to RankQ, it adds a route entry to node DRQID into its downward routing table, increases value of HC field by 1 and forwards the DRQ message to its preferred DODAG parent. If P = 1 and the receiver is the DODAG root, the root processes piggybacked data. The root MAY also mark downward routes to sender as invalid and waits for new DAO messages to reestablish downward routes. If P = 1 and the receiver is not the DODAG root, besides generating DRP message, the receiver MAY forward the piggybacked data to its parent. 4.1.2. DRP Message Processing When a node receives a DRP message, it first performs filtering process and discards the DRP message if any of following conditions is true: i) RPLInstanceID or DODAGVersionNumber or DODAGID in the DRP message is not equal to the respective value maintained by the receiving node. ii) The DRP message was received already by comparing DRPID and DRSN. iii) The receiving node is leaf node and is not the DRQ message generator. If DRP message passes filtering process, the receiving node processes the DRP message further. Guo, et al. Expires October 5, 2013 [Page 13] Internet-Draft Loop Free DODAG Repair April 3, 2013 The receiving node can be a leaf node or a router. If the receiving node is the DRQ message generator and the DRP message sender is not in its DODAG parent set, it may add the DRP message sender into its DODAG parent set and select a new preferred DODAG parent. The receiving node may schedule a DAO message transmission if the DRP message sender is added into its DAO parent set. If the receiving node is not the DRQ message generator, it must be a router. If the receiving router has no route entry to node DRPID in its downward routing table, it discards the DRP message. If the receiving router has a downward route entry to node DRPID and its rank is greater than or equal to RankQ, it checks if it can decrease its rank such that RankQ > its rank > RankP. If not, the receiving router discards the DRP message. If yes, the receiving router decreases its rank to an appropriate value and may add the DRP message sender into its DODAG parent set if the sender is not in its DODAG parent set. The receiving router updates its DODAG parent set caused by its rank decrease, that is, removing DODAG parents whose ranks are greater than or equal to its new rank. If its preferred DODAG parent is removed, it selects a new preferred DODAG parent. The receiving router then updates the RankP of the DRP message to its rank, and forwards the DRP message to next hop node on the downward route. It may schedule a No-Path DAO message transmission if any of its DAO parents is removed due to its rank decrease or the DRP sender was added into its DAO parent set. If the receiving router has a downward route entry to node DRPID and its rank is lower than RankQ, it updates the RankP field of the DRP message to its rank, and forwards the DRP message to next hop node on the downward route. The rank of receiving router is less than RankQ if the receiving router is on multiple DODAG repair downward routes. When the receiving router receives a DRP message, it may decrease its rank. Therefore, subsequent DRP messages may carry a RankQ greater than or equal to the rank of receiving router. If the receiving router is only on a single DODAG repair downward route, its rank must be greater than or equal to RankQ based on the DRQ message process procedure. 4.2. DODAG Local Repair in Non-Storing Mode The handling of unreachable parent in Non-Storing mode is similar to that in Storing mode. However, there are two differences. The first difference is that after removing a DAO parent from its DAO parent Guo, et al. Expires October 5, 2013 [Page 14] Internet-Draft Loop Free DODAG Repair April 3, 2013 set, if its DODAG parent set is not empty, a node may schedule a DAO message transmission instead of the No-Path DAO message transmission. The second difference is that to generate a DRQ message in Non- Storing mode, a node adds a Path option field by inserting its IPv6 address into the Path option field. 4.2.1. DRQ Message Processing When a router receives a DRQ message, it performs same filtering process as that in Storing mode. If the DRQ message passes filtering process, the receiving router processes the DRQ message further. If the receiving router is the DODAG root, it accepts the DRQ message and generates a DRP message similarly as in Storing mode. In addition, the DODAG root adds a Path option in DRP message and copies Path option field from DRQ message to Path option field of DRP message. The DODAG root transmits the DRP message to destination node DRPID along the route specified by the Path option, and on the downward route, intermediate routers obtain route information from the Path option field of DRP message. If the receiving router is not the DODAG root and its rank is lower than Rank_DRQ, it accepts the DRQ message and generates a DRP message as the DODAG root does. It then transmits the DRP message to destination node DRPID along the route specified by the Path option. If the receiving router is not the DODAG root and its rank is greater than or equal to RankQ, it updates the DRQ message by inserting its own IPv6 address into the Path option field, increasing the value of HC field by 1 and forwards the DRQ message to its preferred DODAG parent. If P = 1 and the receiver is the DODAG root, the DODAG root processes piggybacked data. The DODAG root MAY also mark downward routes to node REQID as invalid and waits for new DAO messages to reestablish downward routes. If P = 1 and the receiver is not the DODAG root, besides generating the DRP message, the receiver MAY forward the piggybacked data to its parent. 4.2.2. DRP Message Processing When a node receives a DRP message, it performs the same filtering process as in Storing mode. If the DRP message passes filtering process, the receiving node processes the DRP message further. The receiving node can be a leaf node or a router. Guo, et al. Expires October 5, 2013 [Page 15] Internet-Draft Loop Free DODAG Repair April 3, 2013 If the receiving node is the DRQ message generator and the DRP message sender is not in its DODAG parent set, it may add the DRP message sender into its DODAG parent set. The receiving node may select a new preferred DODAG parent. It may also schedule a DAO message transmission if the DRP message sender is added into its DAO parent set. If the receiving node is not DRQ message generator, it must be a router. If the receiving router is not on the route specified by Path option, it discards the DRP message. If the receiving router is on the route specified by Path option and its rank is greater than or equal to RankQ, the receiving router checks if it can decrease its rank such that RankQ > its rank > RankP. If no, the receiving node discards the DRP message. If yes, the receiving node decreases its rank to an appropriate value and may add the DRP message sender into its DODAG parent set if the sender is not in its DODAG parent set. The receiving router updates its DODAG parent set by removing any DODAG parent whose rank is greater than or equal to its new rank. If its preferred DODAG parent is removed, it selects a new preferred DODAG parent. The receiving router updates the RankP of DRP message to its new rank, and forwards the DRP message to the destination node DRPID by obtaining next hop node via the Path option field. Furthermore, the receiving router may schedule a DAO message transmission if any of its DAO parents was removed due to its rank decrease or the DRP sender was added into its DAO parent set. If the receiving router is on the route specified by Path option and its rank is lower than RankQ, the receiving router updates the RankP to its rank, and forwards the DRP message to destination node DRPID by obtaining next hop node via Path option. The rank of receiving router is less than RankQ if the receiving router is on multiple DODAG repair downward routes. When the receiving router receives a DRP message, it may decrease its rank. Therefore, subsequent DRP messages may carry a RankQ greater than or equal to the rank of receiving router. If the receiving router is only on a single DODAG repair downward route, its rank must be greater than or equal to RankQ based on the DRQ message process procedure. 5. DIS Message with Piggybacked Data For some delay sensitive applications, data must be sent to data sink as soon as possible. For example, if a building monitoring sensor detects fire, it must send the alert message to system controller Guo, et al. Expires October 5, 2013 [Page 16] Internet-Draft Loop Free DODAG Repair April 3, 2013 without delay since in this case, any delay could be costly. If a node has a delay sensitive dada and an empty parent set, it MAY piggyback data into the DIS message. To accomplish this, a modified DIS message is proposed. 5.1 Format of the Modified DIS Base Object 0 1 2 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- - - - - - - - |P| Flags | Reserved | Option(s) ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- - - - - - - - Figure 5: Modified Format of the DIS Base Object P: 1-bit flag to indicate if sender has included a piggybacked data option. If P = 1, piggybacked data is present, and the receiver MAY consider to forward piggybacked data towards the DODAG root. If P = 0, piggybacked is not present. A sender sets P flag to 1 only if its parent set is empty and it has a delay sensitive data to transmit. Flags: 7-bit unused filed reserved for flags. The filed MUST be initialized to zero by the sender and MUST be ignored by the receiver. 8-bit Reserved filed and Option(s) field are same as described in RFC 6550. 5.2 Modified DIS Options Besides options specified in RFC 6550, the DIS message MAY carry PiggyData option as shown in Figure 4. However, this option is present only if flag P = 1. 5.3 Process of the Modified DIS Message If flag P = 0, the process of the DIS message is same as specified in RFC 6550. If flag P = 1, the receiver MAY perform extra process. If receiver is the DODAG root, the root processes piggybacked data. The root MAY also mark downward routes to node REQID as invalid and waits for new DAO messages to reestablish downward routes. If the receiver is not the DODAG root and sender is not its parent, it MAY forward the piggybacked data to its parent. 6. Security Considerations Guo, et al. Expires October 5, 2013 [Page 17] Internet-Draft Loop Free DODAG Repair April 3, 2013 This draft introduces an alternative rank computation method and a DODAG local repair mechanism. In general, the security considerations for the DODAG construction and maintenance are similar to the ones for the operation of RPL as described in Section 19 of [RFC6550]. Section 10 of RPL specification [RFC6550] describes a variety of security mechanisms that provide data confidentiality, authentication, replay protection and delay protection services. Each RPL control message has a secure version that allows the specification of the level of security and the algorithms used to secure the message. New RPL control messages (DRQ and DRP) defined in this draft have secure versions as well. 7. IANA Considerations This draft defines two new RPL Control Messages types and a new RPL Control Message Option. Code field for the DODAG Repair Request (DRQ) message needs to be assigned by IANA. Code field for the DODAG Repair Reply (DRP) message needs to be assigned by IANA. Option Type field for Path option field needs to be assigned by IANA. 8. References 8.1. Normative References [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997. [RFC4443] Conta, A., Deering, S., and M. Gupta, "Internet Control Message Protocol (ICMPv6) for the Internet Protocol Version 6 (IPv6) Specification", RFC 4443, March 2006. [RFC6550] Winter, T., Thubert, P., Brandt, A., Hui, J., Kelsey, R., Levis, P., Pister, K., Struik, R., Vasseur, JP., and R. Alexander, "RPL: IPv6 Routing Protocol for Low-Power and Lossy Networks", RFC 6550, March 2012. [RFC6206] Levis, P., Clausen, T., Hui, J., Gnawali, O., Ko, J., "The Trickle Algorithm", RFC 6206, March 2011. [RFC6551] Vasseur, JP., Kim, M., Pister, K., Dejean, N., and D. Barthel, "Routing Metrics Used for Path Calculation in Low-Power and Lossy Networks", RFC 6551, March 2012. Guo, et al. Expires October 5, 2013 [Page 18] Internet-Draft Loop Free DODAG Repair April 3, 2013 8.2. Informative References [83rd IETF Meeting Presentation] Clausen, T., Yi, J., Colin de Verdiere, A., Herberg, U., "Experiences with RPL: IPv6 Routing Protocol for Low power and Lossy Networks", Paris, France, March 2012. Authors' Addresses Jianlin Guo Mitsubishi Electric Research Laboratories 201 Broadway Cambridge, Massachusetts 02139 USA Phone: +1 617 621 7541 Email: guo@merl.com Philip Orlik Mitsubishi Electric Research Laboratories 201 Broadway Cambridge, Massachusetts 02139 USA Phone: +1 617 621 7570 Email: porlik@merl.com Ghulam Bhatti Mitsubishi Electric Research Laboratories 201 Broadway Cambridge, Massachusetts 02139 USA Phone: +1 617 621 7513 Email: gbhatti@merl.com Guo, et al. Expires October 5, 2013 [Page 19]