ROLL J. Guo
Internet-Draft P. Orlik
Intended status: Standards Track G. Bhatti
Expires: January 3, 2013 Mitsubishi Electric Research Laboratories
July 2, 2012
Loop Free RPL
draft-guo-roll-loop-free-rpl-00
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 and lack of a loop free DODAG
local repair mechanism are two open issues to be addressed. This
draft introduces an alternative rank and an Objective Function to
eliminate DODAG loops in RPL. Based on the proposed rank and
Objective Function, this draft introduces a loop free DODAG local
repair mechanism.
Guo, et al. Expires January 2, 2013 [Page 1]
Internet-Draft Loop Free RPL July 1, 2012
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 September 30, 2012.
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 January 2, 2013 [Page 2]
Internet-Draft Loop Free RPL July 1, 2012
Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . . 5
3. Alternative Rank . . . . . . . . . . . . . . . . . . . . . . . . 6
3.1. Alternative Rank Definition . . . . . . . . . . . . . . . . 6
3.2. Rank Split Operation . . . . . . . . . . . . . . . . . . . 7
4. ICMPv6 RPL Control Message Extension . . . . . . . . . . . . . . 7
4.1. Format of the Modified DIO Base Object . . . . . . . . . . 7
4.2. DODAG Repair Request (DRQ) . . . . . . . . . . . . . . . . 8
4.2.1. Format of the DRQ Base Object . . . . . . . . . . . 8
4.2.2. Secure DRQ . . . . . . . . . . . . . . . . . . . . . 9
4.2.3. DRQ Options . . . . . . . . . . . . . . . . . . . . 9
4.3. DODAG Repair Reply (DRP) . . . . . . . . . . . . . . . . . 10
4.3.1. Format of the DRP Base Object . . . . . . . . . . . 10
4.3.2. Secure DRP . . . . . . . . . . . . . . . . . . . . 11
4.3.3. DRP Options . . . . . . . . . . . . . . . . . . . . 11
4.4. Format of the Path Option . . . . . . . . . . . . . . . . 12
5. DODAG Construction . . . . . . . . . . . . . . . . . . . . . . 12
6. DODAG Local Repair . . . . . . . . . . . . . . . . . . . . . . 13
6.1. DODAG Local Repair in Storing Mode . . . . . . . . . . . . 14
6.1.1. DRQ Message Processing . . . . . . . . . . . . . . 15
6.1.2. DRP Message Processing . . . . . . . . . . . . . . 15
6.2. DODAG Local Repair in Non-Storing Mode . . . . . . . . . . 17
6.2.1. DRQ Message Processing . . . . . . . . . . . . . . . 17
6.2.2. DRP Message Processing . . . . . . . . . . . . . . . 18
6.2.2.1. Direction Bit D = Up . . . . . . . . . . . 18
6.2.2.2. Direction Bit D = Down . . . . . . . . . . 18
7. Security Considerations . . . . . . . . . . . . . . . . . . . . 19
8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . . 19
9. References . . . . . . . . . . . . . . . . . . . . . . . . . . 20
9.1. Normative References . . . . . . . . . . . . . . . . . . . 20
9.2. Informative References . . . . . . . . . . . . . . . . . . 20
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 20
Guo, et al. Expires January 2, 2013 [Page 3]
Internet-Draft Loop Free RPL July 1, 2012
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 January 2, 2013 [Page 4]
Internet-Draft Loop Free RPL July 1, 2012
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. This draft introduces an
alternative rank and an Objective Function to eliminate DODAG loops
in RPL. In this draft, a node's rank never increases, even if a
parent becomes unreachable. As a result, the introduced rank and
Objective Function prevent DODAG loops from occurring. This draft
also introduces a method for repairing DODAG locally without causing
any DODAG loop. 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 towards the
DODAG root.
Down: Down refers to the direction from the DODAG root towards leaf
node or router.
This draft introduces the following new terminologies:
Guo, et al. Expires January 2, 2013 [Page 5]
Internet-Draft Loop Free RPL July 1, 2012
DRQ: DODAG Repair Request
DRP: DODAG Repair Reply
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. Alternative Rank
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, the increase in rank increase can
cause DODAG loops. RPL allows rank increase which is the source of
DODAG loops in RPL. A node's rank increase may also cause all nodes
in sub-DODAG to increase their ranks, which may lead to instability
in the rank values.
3.1. Alternative Rank Definition
DODAG loops in RPL can be avoided if nodes do not increase their
ranks. In order to meet this restriction, this draft defines the rank
of a node as a proper fraction:
Rank = m/n (1)
where m and n are integers such that 0 <= m < n.
The principle of this alternative rank definition comes from the fact
that there are an infinite number of proper fractions between any two
proper fractions. This guarantees that a node can decrease its rank
for any number of times and still keep its rank greater than ranks of
its DODAG parents.
In this draft, a node maintains its rank as two integers, that is,
Guo, et al. Expires January 2, 2013 [Page 6]
Internet-Draft Loop Free RPL July 1, 2012
numerator and denominator. The fractional value is used in rank
operations, such as rank comparison.
The ROOT_RANK is defined as 0/1 and maintained as 0 and 1. The DODAG
root sets its rank to ROOT_RANK. The INFINITE_RANK is defined as 1/1
and maintained as 1 and 1. The INFINITE_RANK can not be advertised in
the DIO messages by any node.
3.2. Rank Split Operation
For any two ranks R1 = m/n and R2 = p/q, the rank split operation is
defined as:
sp(R1, R2) = (m+p)/(n+q) (2)
It can be shown that if R1 < R2, then R1 < sp(R1,R2) < R2. That is,
the split operation splits two ranks R1 and R2 and generates a new
rank sp(R1,R2) that is in between R1 and R2.
4. ICMPv6 RPL Control Message Extension
This draft uses RPL control messages defined in [RFC6550] except the
DIO message. The rank is advertised in the RPL control message using
two integers, numerator and denominator, instead of the fractional
value. As a result, the format of DIO Base Object is modified. In
addition, to repair a DODAG locally, two new RPL control messages,
DODAG Repair Request (DRQ) message and DODAG Repair Reply (DRP)
message, are introduced. RPL control message format is defined in
Figure 6 and Figure 7 of [RFC6550]. 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.
4.1. Format of the Modified DIO 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 | Rank_N |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Rank_D |G|0| MOP | Prf | DTSN |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Flags | Reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
+ +
| |
+ DODAGID +
| |
Guo, et al. Expires January 2, 2013 [Page 7]
Internet-Draft Loop Free RPL July 1, 2012
+ +
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Option(s)...
+-+-+-+-+-+-+-+-+
Figure 1: The Modified DIO Base Object
Rank_N: 16-bit unsigned integer indicating the numerator of
fractional rank of the node generating DIO message.
Rank_D: 16-bit unsigned integer indicating the denominator of
fractional rank of the node generating DIO message.
The rest of fields are same as being described in [RFC6550].
4.2. 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.
4.2.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 | Rank_N |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Rank_D | DRSN | HC | MH |F|Resvd|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
+ +
| |
+ DODAGID +
| |
+ +
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
+ +
| |
+ DRQID +
| |
+ +
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Option(s)...
Guo, et al. Expires January 2, 2013 [Page 8]
Internet-Draft Loop Free RPL July 1, 2012
+-+-+-+-+-+-+-+-+
Figure 2: 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.
Rank_N: 16-bit unsigned integer indicating the numerator of
fractional rank of the node generating the DRQ message.
Rank_D: 16-bit unsigned integer indicating the denominator of
fractional rank of the node generating the DRQ message.
DRSN: 6-bit field indicating sequence number of the DRQ message of
the node generating the DRQ message.
HC: 3-bit field to indicate the number of hops traveled by a DRQ
message.
MH: 3-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.
F: 1-bit flag to indicate if the Path option is present in the DRQ
message.
Resvd: 3 unassigned 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.
4.2.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 2.
4.2.3. DRQ Options
The DRQ message may carry valid options.
Guo, et al. Expires January 2, 2013 [Page 9]
Internet-Draft Loop Free RPL July 1, 2012
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 and
flag F is set. The Path field contains IPv6 addresses of traversed
nodes by the DRQ message along the path.
4.3. 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.
4.3.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_N |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| RankQ_D | RankP_N |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| RankP_D | DRSN |D|F| Resvd |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
+ +
| |
+ DODAGID +
| |
+ +
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
+ +
| |
+ DRPID +
| |
+ +
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Option(s)...
+-+-+-+-+-+-+-+-+
Figure 3: The DRP Base Object
RPLInstanceID: 8-bit unsigned field as described in [RFC6550] to
indicate which RPL Instance the DODAG is a part.
Guo, et al. Expires January 2, 2013 [Page 10]
Internet-Draft Loop Free RPL July 1, 2012
Version Number: 8-bit unsigned integer as described in [RFC6550] to
indicate the DODAGVersionNumber.
RankQ_N: 16-bit unsigned integer indicating the numerator of
fractional rank of the node generating the DRQ message.
RankQ_D: 16-bit unsigned integer indicating the denominator of
fractional rank of the node generating the DRQ message.
RankP_N: 16-bit unsigned integer indicating the numerator of
fractional rank of the node sending the DRP message.
RankP_D: 16-bit unsigned integer indicating the denominator of
fractional rank of the node sending the DRP message.
DRSN: 6-bit field indicating the sequence number of DRQ message of
the node generating the DRQ message.
D: 1-bit field indicating whether the DRP message is traveling
upwards or downwards. This field is only used in Non-Storing
mode and must be ignored in Storing mode.
F: 1-bit field indicating if the Path option is present in the DRP
message.
Resvd: 8 unassigned 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.
4.3.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 3.
4.3.3. DRP Options
The DRP message may carry valid options.
This draft allows for the DRP message to carry the following options:
0x00 Pad1
Guo, et al. Expires January 2, 2013 [Page 11]
Internet-Draft Loop Free RPL July 1, 2012
0x01 PadN
Path: This option is present only if MOP is Non-Storing and flag F
is set. The Path field contains IPv6 addresses of traversed nodes
by the DRQ message and the upward DRP message along the path.
4.4. RPL Control Message Options
The formats of option Pad1 and PadN are described in Figure 20 and
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 4: 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.
5. DODAG Construction
In RPL, a DODAG is uniquely identified by the (RPLInstanceID,
DODAGID) tuple and a DODAG Version is uniquely identified by the
(RPLInstanceID, DODAGID, DODAGVersionNumber) tuple. The
DODAGVersionNumber is monotonically incremented by the DODAG root.
To construct a new DODAG, the DODAG root configures DODAG parameters
and transmits a DIO message with new (RPLInstanceID, DODAGID) tuple.
To construct a new DODAG Version, the DODAG root transmits a DIO
message with an increased DODAGVersionNumber. The DIO message is
transmitted via link-local multicasting to all-RPL-nodes. Nodes
obtain the DODAG parameters configured by the DODAG root in received
DIO messages.
Upon receiving a DIO message transmitted by the DODAG root containing
new (RPLInstanceID, DODAGID) tuple or new DODAGVersionNumber, the
first hop neighboring nodes of the DODAG root may decide to join new
Guo, et al. Expires January 2, 2013 [Page 12]
Internet-Draft Loop Free RPL July 1, 2012
DODAG or new DODAG Version advertised in received DIO message. To do
so, the first hop nodes add the DODAG root into their DODAG parent
set and store the DODAG parameters advertised in received DIO
message. The first hop nodes keep all DODAG parameters unchanged
except the rank. The first hop nodes set their ranks such that their
ranks > ROOT_RANK and their ranks <= sp(ROOT_RANK, INFINITE_RANK).
Upon joining a new DODAG or a new DODAG Version, the first hop
routers generate and transmit the DIO messages by following rules
specified in [RFC6550] to advertise the DODAG parameters. A router
must not transmit the DIO messages for DODAG Versions of which it is
not a member. A router that is not the DODAG root must not change the
DODAG parameters received in DIO messages except the rank and DTSN
fields. All other DODAG parameters, such as the DODAGID and
DODAGVersionNumber, must be propagated unchanged down the DODAG as
nodes join new DODAG or new DODAG Version.
Upon receiving the DIO messages transmitted by the first hop
neighboring routers, the second hop neighboring nodes of the DODAG
root that want to join new DODAG or new DODAG Version perform same
procedure as the first hop neighboring nodes do. However, in this
case, the second hop nodes may receive multiple DIO messages from the
first hop routers within the same DODAG or DODAG Version. The second
hop nodes use received DIO messages to calculate their ranks and
select a subset of the DIO message senders as their DODAG parents. To
calculate its rank, a second hop node find the maximum rank,
Rank_Max, among all ranks of its DODAG parents and sets its rank such
that its rank > Rank_Max and its rank <= sp(Rank_Max, INFINITE_RANK).
The second hop routers then generate and transmit the DIO messages
same as the first hop router do.
It is possible that a first hop neighboring node of the DODAG root
may also receive the DIO messages transmitted by other first hop
neighboring routers. The first hop node may perform same procedure as
the second hop nodes do to select more DODAG parents and calculate
its rank.
This DIO message propagation process continues until all nodes
receive the DIO messages, select the DODAG parents and store their
DODAG parameters, that is, the DODAG is completely constructed.
Among its DODAG parents, a node selects one preferred DODAG parent to
be used as the preferred next hop node along upward routes to the
DODAG root. A node also selects some of its DODAG parents as its DAO
parents and schedules the DAO transmission.
6. DOADG Local Repair
When a DODAG parent becomes unreachable, a node may switch to another
Guo, et al. Expires January 2, 2013 [Page 13]
Internet-Draft Loop Free RPL July 1, 2012
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 Rank_DRQ (=
Rank_N/Rank_D), 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 Rank_DRQ, it forwards the DRQ message to its preferred DODAG
parent. This 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 router which is either the DODAG root or a router
that has a non-empty DODAG parent set and a rank lower than Rank_DRQ,
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
is forwarded up to the DODAG root, which then transmits the DRP
message down to the DRQ message generator by using source routing.
6.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 Rank_N and Rank_D to
the numerator and denominator of its fractional rank, respectively.
The node increases its DRSN by 1 and sets HC = 0, MH to an
Guo, et al. Expires January 2, 2013 [Page 14]
Internet-Draft Loop Free RPL July 1, 2012
appropriate value, and F = 0. There is no Path option field in
Storing mode.
6.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.
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, F, and DODAGID
from the DRQ message. It sets DRPID to DRQID, RankQ_N and RankQ_D to
the Rank_N and Rank_D in DRQ message, respectively. It sets RankP_N
and RankP_D to the numerator and denominator of its fractional rank,
respectively. The direction bit D is set to Down. Since flag F = 0 in
Storing mode, there is no Path option field in the DRP message. 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 Rank_DRQ, 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 Rank_DRQ, 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.
6.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
Guo, et al. Expires January 2, 2013 [Page 15]
Internet-Draft Loop Free RPL July 1, 2012
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.
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 Rank_DRQ (= RankQ_N/RankQ_D), it
decreases its rank to sp(Rank_DRQ, Rank_DRP), where Rank_DRP =
RankP_N/RankP_D. 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 sp(Rank_DRQ, Rank_DRP). If its
preferred DODAG parent is removed, it selects a new preferred DODAG
parent. The receiving router then updates the RankP_N and RankP_D
fields of the DRP message to the numerator and denominator of its
fractional rank, respectively, 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.
If the receiving router has a downward route entry to node DRPID and
its rank is lower than Rank_DRQ, it updates the RankP_N and RankP_D
fields of DRP message to the numerator and denominator of its
fractional rank, respectively, and forwards the DRP message to next
hop node on the downward route. In Storing mode, the rank of
receiving router is less than Rank_DRQ 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,
Guo, et al. Expires January 2, 2013 [Page 16]
Internet-Draft Loop Free RPL July 1, 2012
subsequent DRP messages may carry a Rank_DRQ 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 Rank_DRQ based on the DRQ message process procedure.
6.2. DODAG Local Repair in Non-Storing Mode
The handling of parent unreachability in Non-Storing mode is similar
to that in Storing mode. The first difference is that after removing
a DAO parent from its DAO parent 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, if its DODAG parent set
is empty, a node sets flag F to 1 and adds a Path option field by
inserting its IPv6 address into the Path option field. If its DODAG
parent set is not empty, the node may or may not set flag F = 1. The
third difference is that the DRP message is first forwarded up to the
DODAG root, which then sends the DRP message down to destination node
DRPID via source routing.
6.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. The
direction bit D is set to Down. If flag F = 1 in the DRQ message, the
DODAG root sets F = 1 in DRP message and copies Path option field
from DRQ message to Path option field of DRP message. If flag F = 0,
the DODAG root transmits the DRP message to destination node DRPID by
using source routing mechanism specified in RPL. If flag F = 1, the
DODAG root transmits the DRP message to destination node DRPID by
using the route provided in Path option field, 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
similarly as the DODAG root does. The direction bit D is set to Up in
this case. If flag F = 1 in DRQ message, it sets flag F = 1 in the
DRP message, copies the Path option field from DRQ message to the
Path option field of DRP message and then insets its own IPv6 address
into the Path option field of DRP message. The receiving router
forwards the DRP message to its preferred DODAG parent.
If the receiving router is not the DODAG root and its rank is greater
Guo, et al. Expires January 2, 2013 [Page 17]
Internet-Draft Loop Free RPL July 1, 2012
than or equal to Rank_DRQ, it checks if flag F = 1 in DRQ message. If
yes, 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 no, the
receiving router increases the value of HC field by 1 and forwards
the DRQ message to its preferred DODAG parent.
6.2.2. DRP Message Processing
When a node receives a DRP message, it performs the same filtering
process as in Storing mode. In addition, if the direction bit D = Up
and its DODAG parent set is empty, the receiving node discards the
DRP message.
If the DRP message passes filtering process, the receiving node
processes the DRP message further.
6.2.2.1. Direction Bit D = Up
In this case, the receiving node must be a router.
If the receiving router is the DODAG root, it updates RankP_N and
RankP_D to the numerator and denominator of its fractional rank,
respectively, and changes direction bit D to Down. If flag F = 0, the
DODAG root transmits the DRP message down to destination node DRPID
by using source routing mechanism specified in RPL. If flag F = 1,
the DODAG root transmits the DRP message down to destination node
DRPID by using the route provided in the Path option field of DRP
message.
If the receiving router is not the DODAG root and flag F = 1, the
receiving router updates the DRP message by inserting its own IPv6
address into the Path option field of DRP message and forwards the
DRP message to its preferred DODAG parent. If flag F = 0, the
receiving router forwards the DRP message to its preferred DODAG
parent.
6.2.2.2. Direction Bit D = Down
In this case, 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. 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.
Guo, et al. Expires January 2, 2013 [Page 18]
Internet-Draft Loop Free RPL July 1, 2012
If the receiving node is not DRQ message generator, it must be a
router.
If the receiving router is not on the downward route, it discards the
DRP message. Otherwise, if its rank is lower than Rank_DRQ, the
receiving router updates the RankP_N and RankP_D fields of the DRP
message to the numerator and denominator of its fractional rank,
respectively, and forwards the DRP message to destination node DRPID
by obtaining route information provided in RPL source routing
mechanism (if F = 0) or in the Path option field (if F = 1). If its
rank is greater than or equal to Rank_DRQ, the receiving router
decreases its rank to sp(Rank_DRQ, Rank_DRP) and updates its DODAG
parent set by removing any DODAG parent whose rank is greater than or
equal to sp(Rank_DRQ, Rank_DRP). If its preferred DODAG parent is
removed, it selects a new preferred DODAG parent. The receiving
router updates the RankP_N and RankP_D fields of DRP message to the
numerator and denominator of its fractional rank, respectively, and
forwards the DRP message to the destination node DRPID by obtaining
route information provided in RPL source routing mechanism (if F = 0)
or in the Path option field (if F = 1). Furthermore, the receiving
router may schedule a DAO message transmission if any of its DAO
parents was removed due to its rank decrease.
7. Security Considerations
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.
8. 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.
Guo, et al. Expires January 2, 2013 [Page 19]
Internet-Draft Loop Free RPL July 1, 2012
Option Type field for Path option field needs to be assigned by IANA.
9. References
9.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.
9.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
Guo, et al. Expires January 2, 2013 [Page 20]
Internet-Draft Loop Free RPL July 1, 2012
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 January 2, 2013 [Page 21]