draft-ietf-roll-rpl-02.txt   draft-ietf-roll-rpl-03.txt 
Networking Working Group T. Winter, Ed. Networking Working Group T. Winter, Ed.
Internet-Draft Internet-Draft
Intended status: Standards Track P. Thubert, Ed. Intended status: Standards Track P. Thubert, Ed.
Expires: March 27, 2010 Cisco Systems Expires: April 7, 2010 Cisco Systems
ROLL Design Team ROLL Design Team
IETF ROLL WG IETF ROLL WG
September 23, 2009 October 4, 2009
RPL: Routing Protocol for Low Power and Lossy Networks RPL: Routing Protocol for Low Power and Lossy Networks
draft-ietf-roll-rpl-02 draft-ietf-roll-rpl-03
Status of this Memo Status of this Memo
This Internet-Draft is submitted to IETF in full conformance with the This Internet-Draft is submitted to IETF in full conformance with the
provisions of BCP 78 and BCP 79. provisions of BCP 78 and BCP 79.
Internet-Drafts are working documents of the Internet Engineering Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF), its areas, and its working groups. Note that Task Force (IETF), its areas, and its working groups. Note that
other groups may also distribute working documents as Internet- other groups may also distribute working documents as Internet-
Drafts. Drafts.
skipping to change at page 1, line 35 skipping to change at page 1, line 35
and may be updated, replaced, or obsoleted by other documents at any and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress." material or to cite them other than as "work in progress."
The list of current Internet-Drafts can be accessed at The list of current Internet-Drafts can be accessed at
http://www.ietf.org/ietf/1id-abstracts.txt. http://www.ietf.org/ietf/1id-abstracts.txt.
The list of Internet-Draft Shadow Directories can be accessed at The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html. http://www.ietf.org/shadow.html.
This Internet-Draft will expire on March 27, 2010. This Internet-Draft will expire on April 7, 2010.
Copyright Notice Copyright Notice
Copyright (c) 2009 IETF Trust and the persons identified as the Copyright (c) 2009 IETF Trust and the persons identified as the
document authors. All rights reserved. document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents in effect on the date of Provisions Relating to IETF Documents in effect on the date of
publication of this document (http://trustee.ietf.org/license-info). publication of this document (http://trustee.ietf.org/license-info).
Please review these documents carefully, as they describe your rights Please review these documents carefully, as they describe your rights
skipping to change at page 3, line 17 skipping to change at page 3, line 17
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 6 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.1. Design Principles . . . . . . . . . . . . . . . . . . . . 6 1.1. Design Principles . . . . . . . . . . . . . . . . . . . . 6
1.2. Expectations of Link Layer Behavior . . . . . . . . . . . 7 1.2. Expectations of Link Layer Behavior . . . . . . . . . . . 7
2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 7 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 7
3. Protocol Model . . . . . . . . . . . . . . . . . . . . . . . . 9 3. Protocol Model . . . . . . . . . . . . . . . . . . . . . . . . 9
3.1. Protocol Properties Overview . . . . . . . . . . . . . . . 9 3.1. Protocol Properties Overview . . . . . . . . . . . . . . . 9
3.1.1. IPv6 Architecture . . . . . . . . . . . . . . . . . . 9 3.1.1. IPv6 Architecture . . . . . . . . . . . . . . . . . . 9
3.1.2. Typical LLN Traffic Patterns . . . . . . . . . . . . . 10 3.1.2. Typical LLN Traffic Patterns . . . . . . . . . . . . . 10
3.1.3. Constraint Based Routing . . . . . . . . . . . . . . . 10 3.1.3. Constraint Based Routing . . . . . . . . . . . . . . . 10
3.2. Protocol Operation . . . . . . . . . . . . . . . . . . . . 10 3.2. Protocol Operation . . . . . . . . . . . . . . . . . . . . 10
3.2.1. DAG Construction . . . . . . . . . . . . . . . . . . . 11 3.2.1. DAG Construction . . . . . . . . . . . . . . . . . . . 12
3.2.2. Destination Advertisement . . . . . . . . . . . . . . 21 3.2.2. Destination Advertisement . . . . . . . . . . . . . . 19
3.3. Other Considerations . . . . . . . . . . . . . . . . . . . 23 3.3. Loop Avoidance and Stability . . . . . . . . . . . . . . . 21
3.3.1. DAG Rank and Loop Avoidance . . . . . . . . . . . . . 23 3.3.1. Greediness and Rank-based Instabilities . . . . . . . 22
3.3.2. DAG Parent Selection, Stability, and Greediness . . . 27 3.3.2. Merging DAGs . . . . . . . . . . . . . . . . . . . . . 22
3.3.3. Merging DAGs . . . . . . . . . . . . . . . . . . . . . 29 3.3.3. DAG Loops . . . . . . . . . . . . . . . . . . . . . . 23
3.4. Local and Temporary Routing Decision . . . . . . . . . . . 32 3.3.4. DAO Loops . . . . . . . . . . . . . . . . . . . . . . 23
3.5. Maintenance of Routing Adjacency . . . . . . . . . . . . . 32 3.3.5. Sibling Loops . . . . . . . . . . . . . . . . . . . . 23
4. Constraint Based Routing in LLNs . . . . . . . . . . . . . . . 33 3.4. Local and Temporary Routing Decision . . . . . . . . . . . 24
4.1. Routing Metrics . . . . . . . . . . . . . . . . . . . . . 33 3.5. Maintenance of Routing Adjacency . . . . . . . . . . . . . 25
4.2. Routing Constraints . . . . . . . . . . . . . . . . . . . 34 4. Constraint Based Routing in LLNs . . . . . . . . . . . . . . . 25
4.3. Constraint Based Routing . . . . . . . . . . . . . . . . . 34 4.1. Routing Metrics . . . . . . . . . . . . . . . . . . . . . 25
5. RPL Protocol Specification . . . . . . . . . . . . . . . . . . 35 4.2. Routing Constraints . . . . . . . . . . . . . . . . . . . 26
5.1. DAG Information Option . . . . . . . . . . . . . . . . . . 35 4.3. Constraint Based Routing . . . . . . . . . . . . . . . . . 26
5.1.1. DAG Information Option (DIO) base option . . . . . . . 35 5. RPL Protocol Specification . . . . . . . . . . . . . . . . . . 27
5.2. Conceptual Data Structures . . . . . . . . . . . . . . . . 42 5.1. DAG Information Option . . . . . . . . . . . . . . . . . . 27
5.2.1. Candidate Neighbors Data Structure . . . . . . . . . . 42 5.1.1. DAG Information Option (DIO) base option . . . . . . . 27
5.2.2. Directed Acyclic Graphs (DAGs) Data Structure . . . . 43 5.2. Conceptual Data Structures . . . . . . . . . . . . . . . . 34
5.3. DAG Discovery and Maintenance . . . . . . . . . . . . . . 44 5.2.1. Candidate Neighbors Data Structure . . . . . . . . . . 34
5.3.1. DAG Discovery Rules . . . . . . . . . . . . . . . . . 45 5.2.2. Directed Acyclic Graphs (DAGs) Data Structure . . . . 35
5.3.2. Reception and Processing of RA-DIO messages . . . . . 47 5.3. DAG Discovery and Maintenance . . . . . . . . . . . . . . 36
5.3.3. RA-DIO Transmission . . . . . . . . . . . . . . . . . 49 5.3.1. DAG Discovery Rules . . . . . . . . . . . . . . . . . 37
5.3.4. Trickle Timer for RA Transmission . . . . . . . . . . 50 5.3.2. Reception and Processing of RA-DIO messages . . . . . 39
5.4. DAG Heartbeat . . . . . . . . . . . . . . . . . . . . . . 52 5.3.3. RA-DIO Transmission . . . . . . . . . . . . . . . . . 41
5.5. DAG Selection . . . . . . . . . . . . . . . . . . . . . . 52 5.3.4. Trickle Timer for RA Transmission . . . . . . . . . . 42
5.6. Administrative rank . . . . . . . . . . . . . . . . . . . 53 5.4. DAG Heartbeat . . . . . . . . . . . . . . . . . . . . . . 44
5.7. Candidate DAG Parent States and Stability . . . . . . . . 53 5.5. DAG Selection . . . . . . . . . . . . . . . . . . . . . . 44
5.7.1. Held-Up . . . . . . . . . . . . . . . . . . . . . . . 53 5.6. Administrative rank . . . . . . . . . . . . . . . . . . . 45
5.7.2. Held-Down . . . . . . . . . . . . . . . . . . . . . . 54 5.7. Candidate DAG Parent States and Stability . . . . . . . . 45
5.7.3. Collision . . . . . . . . . . . . . . . . . . . . . . 54 5.7.1. Held-Up . . . . . . . . . . . . . . . . . . . . . . . 45
5.7.4. Instability . . . . . . . . . . . . . . . . . . . . . 55 5.7.2. Held-Down . . . . . . . . . . . . . . . . . . . . . . 46
5.8. Guidelines for Objective Code Points . . . . . . . . . . . 56 5.7.3. Collision . . . . . . . . . . . . . . . . . . . . . . 46
5.8.1. Objective Function . . . . . . . . . . . . . . . . . . 56 5.7.4. Instability . . . . . . . . . . . . . . . . . . . . . 47
5.8.2. Objective Code Point 0 (OCP 0) . . . . . . . . . . . . 58 5.8. Guidelines for Objective Code Points . . . . . . . . . . . 48
5.9. Establishing Routing State Outward Along the DAG . . . . . 60 5.8.1. Objective Function . . . . . . . . . . . . . . . . . . 48
5.9.1. Destination Advertisement Message Formats . . . . . . 61 5.8.2. Objective Code Point 0 (OCP 0) . . . . . . . . . . . . 50
5.9.2. Destination Advertisement Operation . . . . . . . . . 63
5.10. Multicast Operation . . . . . . . . . . . . . . . . . . . 70 5.9. Establishing Routing State Outward Along the DAG . . . . . 52
5.11. Maintenance of Routing Adjacency . . . . . . . . . . . . . 71 5.9.1. Destination Advertisement Message Formats . . . . . . 53
5.12. Packet Forwarding . . . . . . . . . . . . . . . . . . . . 72 5.9.2. Destination Advertisement Operation . . . . . . . . . 55
5.12.1. Loop Taxonomy . . . . . . . . . . . . . . . . . . . . 73 5.10. Multicast Operation . . . . . . . . . . . . . . . . . . . 62
6. RPL Variables . . . . . . . . . . . . . . . . . . . . . . . . 74 5.11. Maintenance of Routing Adjacency . . . . . . . . . . . . . 63
7. Manageability Considerations . . . . . . . . . . . . . . . . . 75 5.12. Packet Forwarding . . . . . . . . . . . . . . . . . . . . 64
7.1. Control of Function and Policy . . . . . . . . . . . . . . 75 6. RPL Variables . . . . . . . . . . . . . . . . . . . . . . . . 65
7.1.1. Initialization Mode . . . . . . . . . . . . . . . . . 75 7. Manageability Considerations . . . . . . . . . . . . . . . . . 66
7.1.2. DIO Base option . . . . . . . . . . . . . . . . . . . 76 7.1. Control of Function and Policy . . . . . . . . . . . . . . 66
7.1.3. Trickle Timers . . . . . . . . . . . . . . . . . . . . 77 7.1.1. Initialization Mode . . . . . . . . . . . . . . . . . 66
7.1.4. DAG Heartbeat . . . . . . . . . . . . . . . . . . . . 77 7.1.2. DIO Base option . . . . . . . . . . . . . . . . . . . 66
7.1.5. The Destination Advertisement Option . . . . . . . . . 78 7.1.3. Trickle Timers . . . . . . . . . . . . . . . . . . . . 67
7.1.6. Policy Control . . . . . . . . . . . . . . . . . . . . 78 7.1.4. DAG Heartbeat . . . . . . . . . . . . . . . . . . . . 68
7.1.7. Data Structures . . . . . . . . . . . . . . . . . . . 78 7.1.5. The Destination Advertisement Option . . . . . . . . . 68
7.2. Information and Data Models . . . . . . . . . . . . . . . 78 7.1.6. Policy Control . . . . . . . . . . . . . . . . . . . . 68
7.3. Liveness Detection and Monitoring . . . . . . . . . . . . 79 7.1.7. Data Structures . . . . . . . . . . . . . . . . . . . 68
7.3.1. Candidate Neighbor Data Structure . . . . . . . . . . 79 7.2. Information and Data Models . . . . . . . . . . . . . . . 69
7.3.2. Directed Acyclic Graph (DAG) Table . . . . . . . . . . 79 7.3. Liveness Detection and Monitoring . . . . . . . . . . . . 69
7.3.3. Routing Table . . . . . . . . . . . . . . . . . . . . 80 7.3.1. Candidate Neighbor Data Structure . . . . . . . . . . 69
7.3.4. Other RPL Monitoring Parameters . . . . . . . . . . . 80 7.3.2. Directed Acyclic Graph (DAG) Table . . . . . . . . . . 69
7.3.5. RPL Trickle Timers . . . . . . . . . . . . . . . . . . 80 7.3.3. Routing Table . . . . . . . . . . . . . . . . . . . . 70
7.4. Verifying Correct Operation . . . . . . . . . . . . . . . 80 7.3.4. Other RPL Monitoring Parameters . . . . . . . . . . . 70
7.3.5. RPL Trickle Timers . . . . . . . . . . . . . . . . . . 70
7.4. Verifying Correct Operation . . . . . . . . . . . . . . . 71
7.5. Requirements on Other Protocols and Functional 7.5. Requirements on Other Protocols and Functional
Components . . . . . . . . . . . . . . . . . . . . . . . . 81 Components . . . . . . . . . . . . . . . . . . . . . . . . 71
7.6. Impact on Network Operation . . . . . . . . . . . . . . . 81 7.6. Impact on Network Operation . . . . . . . . . . . . . . . 71
8. Security Considerations . . . . . . . . . . . . . . . . . . . 81 8. Security Considerations . . . . . . . . . . . . . . . . . . . 71
9. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 81 9. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 71
9.1. DAG Information Option (DIO) Base Option . . . . . . . . . 81 9.1. DAG Information Option (DIO) Base Option . . . . . . . . . 71
9.2. New Registry for the Flag Field of the DIO Base Option . . 81 9.2. New Registry for the Flag Field of the DIO Base Option . . 71
9.3. DAG Information Option (DIO) Suboption . . . . . . . . . . 82 9.3. DAG Information Option (DIO) Suboption . . . . . . . . . . 72
9.4. Destination Advertisement Option (DAO) Option . . . . . . 82 9.4. Destination Advertisement Option (DAO) Option . . . . . . 72
9.5. Objective Code Point . . . . . . . . . . . . . . . . . . . 82 9.5. Objective Code Point . . . . . . . . . . . . . . . . . . . 72
10. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 83 10. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 73
11. Contributors . . . . . . . . . . . . . . . . . . . . . . . . . 83 11. Contributors . . . . . . . . . . . . . . . . . . . . . . . . . 73
12. References . . . . . . . . . . . . . . . . . . . . . . . . . . 84 12. References . . . . . . . . . . . . . . . . . . . . . . . . . . 74
12.1. Normative References . . . . . . . . . . . . . . . . . . . 84 12.1. Normative References . . . . . . . . . . . . . . . . . . . 74
12.2. Informative References . . . . . . . . . . . . . . . . . . 84 12.2. Informative References . . . . . . . . . . . . . . . . . . 74
Appendix A. Deferred Requirements . . . . . . . . . . . . . . . . 86 Appendix A. Deferred Requirements . . . . . . . . . . . . . . . . 76
Appendix B. Examples . . . . . . . . . . . . . . . . . . . . . . 87 Appendix B. Examples . . . . . . . . . . . . . . . . . . . . . . 77
B.1. Moving Down a DAG . . . . . . . . . . . . . . . . . . . . 88 B.1. Moving Down a DAG . . . . . . . . . . . . . . . . . . . . 78
B.2. Link Removed . . . . . . . . . . . . . . . . . . . . . . . 89 B.2. Link Removed . . . . . . . . . . . . . . . . . . . . . . . 79
B.3. Link Added . . . . . . . . . . . . . . . . . . . . . . . . 89 B.3. Link Added . . . . . . . . . . . . . . . . . . . . . . . . 79
B.4. Node Removed . . . . . . . . . . . . . . . . . . . . . . . 90 B.4. Node Removed . . . . . . . . . . . . . . . . . . . . . . . 80
B.5. New LBR Added . . . . . . . . . . . . . . . . . . . . . . 90 B.5. New LBR Added . . . . . . . . . . . . . . . . . . . . . . 80
B.6. Destination Advertisement . . . . . . . . . . . . . . . . 91 B.6. Destination Advertisement . . . . . . . . . . . . . . . . 81
Appendix C. Additional Examples . . . . . . . . . . . . . . . . . 92 B.7. Example: DAG Parent Selection . . . . . . . . . . . . . . 82
Appendix D. Outstanding Issues . . . . . . . . . . . . . . . . . 96 B.8. Example: DAG Maintenance . . . . . . . . . . . . . . . . . 83
D.1. Additional Support for P2P Routing . . . . . . . . . . . . 96 B.9. Example: Greedy Parent Selection and Instability . . . . . 84
D.2. Loop Detection . . . . . . . . . . . . . . . . . . . . . . 96 B.10. Example: DAG Merge . . . . . . . . . . . . . . . . . . . . 86
D.3. Destination Advertisement / DAO Fan-out . . . . . . . . . 96 Appendix C. Additional Examples . . . . . . . . . . . . . . . . . 88
D.4. Source Routing . . . . . . . . . . . . . . . . . . . . . . 96 Appendix D. Outstanding Issues . . . . . . . . . . . . . . . . . 92
D.5. Address / Header Compression . . . . . . . . . . . . . . . 97 D.1. Additional Support for P2P Routing . . . . . . . . . . . . 92
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 97 D.2. Loop Detection . . . . . . . . . . . . . . . . . . . . . . 92
D.3. Destination Advertisement / DAO Fan-out . . . . . . . . . 92
D.4. Source Routing . . . . . . . . . . . . . . . . . . . . . . 92
D.5. Address / Header Compression . . . . . . . . . . . . . . . 93
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 93
1. Introduction 1. Introduction
Low Power and Lossy Networks (LLNs) are made largely of constrained Low Power and Lossy Networks (LLNs) are made largely of constrained
nodes (with limited processing power, memory, and sometimes energy nodes (with limited processing power, memory, and sometimes energy
when they are battery operated). These routers are interconnected by when they are battery operated). These routers are interconnected by
lossy links, most of the time supporting only low data rates, that lossy links, most of the time supporting only low data rates, that
are usually fairly unstable with relatively low packet delivery are usually fairly unstable with relatively low packet delivery
rates. Another characteristic of such networks is that the traffic rates. Another characteristic of such networks is that the traffic
patterns are not simply unicast, but in many cases point-to- patterns are not simply unicast, but in many cases point-to-
skipping to change at page 10, line 7 skipping to change at page 10, line 7
Further, RPL is designed with consideration to the practical support Further, RPL is designed with consideration to the practical support
and implementation of IPv6 architecture on devices which may operate and implementation of IPv6 architecture on devices which may operate
under severe resource constraints, including but not limited to under severe resource constraints, including but not limited to
memory, processing power, energy, and communication. The RPL design memory, processing power, energy, and communication. The RPL design
does not presume high quality reliable links, and operates over lossy does not presume high quality reliable links, and operates over lossy
links (usually low bandwidth with low packet delivery success rate). links (usually low bandwidth with low packet delivery success rate).
3.1.2. Typical LLN Traffic Patterns 3.1.2. Typical LLN Traffic Patterns
Multipoint-to-point (MP2P) and Point-to-multipoint (P2MP) traffic Multipoint-to-Point (MP2P) and Point-to-multipoint (P2MP) traffic
flows from nodes within the LLN from and to egress points are very flows from nodes within the LLN from and to egress points are very
common in LLNs. Low power and lossy network Border Router (LBR) common in LLNs. Low power and lossy network Border Router (LBR)
nodes may typically be at the root of such flows, although such flows nodes may typically be at the root of such flows, although such flows
are not exclusively rooted at LBRs as determined on an application- are not exclusively rooted at LBRs as determined on an application-
specific basis. In particular, several applications such as building specific basis. In particular, several applications such as building
or home automation do require P2P (Point-to-Point) communication. or home automation do require P2P (Point-to-Point) communication.
As required by the aforementioned routing requirements documents, RPL As required by the aforementioned routing requirements documents, RPL
supports the installation of multiple paths. The use of multiple supports the installation of multiple paths. The use of multiple
paths include sending duplicated traffic along diverse paths, as well paths include sending duplicated traffic along diverse paths, as well
skipping to change at page 10, line 44 skipping to change at page 10, line 44
RPL supports the computation and installation of different paths in RPL supports the computation and installation of different paths in
support of and optimized for a set of application and implementation support of and optimized for a set of application and implementation
specific constraints, as guided by an OCP. Traffic may subsequently specific constraints, as guided by an OCP. Traffic may subsequently
be directed along the appropriate constrained path based on traffic be directed along the appropriate constrained path based on traffic
marking within the IPv6 header. For more details on the approach marking within the IPv6 header. For more details on the approach
towards constraint-based routing, see Section 4. towards constraint-based routing, see Section 4.
3.2. Protocol Operation 3.2. Protocol Operation
A LLN deployment will consist of a number of nodes and a number of
edges (links) between them, whose characteristics will depend on
implementation and link layer (L2) specifics. Due to the nature of
the LLN environment the L2 links are expected to demonstrate a large
degree of variance as to their availability, quality, and other
related parameters. Certain links, demonstrating a viability above a
confidence threshold for particular node and link metrics, as based
on guidelines from [I-D.ietf-roll-routing-metrics], will be extracted
from the L2 graph, and the resulting graph will be used as the basis
on which to operate the routing protocol. Note that as the
characteristics of the L2 topology vary over time the set of viable
links is to be updated and the routing protocol thus continues to
evaluate the LLN. In RPL this process happens in a distributed
manner, and from the perspective of a single node running RPL this
process results in a set of candidate neighbors, with associated node
and link metrics as well as confidence values.
Many of the dominant traffic flows in support of the LLN application
scenarios are MP2P flows ([I-D.ietf-roll-building-routing-reqs],
[I-D.ietf-roll-home-routing-reqs],
[I-D.ietf-roll-indus-routing-reqs], and [RFC5548]). These flows are
rooted at designated nodes that have some application significance,
such as providing connectivity to an external routed infrastructure.
The term "external" is used top refer to the public Internet or a
core private (non-LLN) IP network. In support of this dominant flow
RPL constructs Directed Acyclic Graphs (DAGs) on top of the viable
LLN topology, selecting and orienting links among candidate neighbors
toward DAG roots which root the MP2P flows.
LLN nodes running RPL will construct Directed Acyclic Graphs (DAGs) LLN nodes running RPL will construct Directed Acyclic Graphs (DAGs)
rooted at designated nodes that generally have some application rooted at designated nodes that generally have some application
significance, such as providing connectivity to an external routed significance, such as providing connectivity to an external routed
infrastructure. The term "external" is used top refer to the public infrastructure. The term "external" is used top refer to the public
Internet or a core private (non-LLN) IP network. The DAG is Internet or a core private (non-LLN) IP network. This structure
sufficient to support inward MP2P traffic flows, flowing inward along provides the routing solution for the dominant MP2P traffic flows.
the LLN towards a sink (DAG root), which is one of the dominant The DAG structure further provides each node potentially multiple
traffic flows described in the requirements documents successors for MP2P flows, which may be used for, e.g., local route
([I-D.ietf-roll-building-routing-reqs], repair or load balancing.
[I-D.ietf-roll-home-routing-reqs],
[I-D.ietf-roll-indus-routing-reqs], and [RFC5548]).
By utilizing a DAG for dominant MP2P flows, RPL allows each node to
select and maintain potentially multiple successors capable of
forwarding traffic inwards towards the root. The DAG does not
present as many single points of failure as a tree, and in addition
can offer a node a set of pre-computed successors in support of, e.g.
local route repair in case of a temporary failure, load balancing, or
short term fluctuations in link characteristics.
A DAG also serves to restrict the routing problem on the nodes when Nodes running RPL are able to further restrict the scope of the
it is used as a reference topology. This allows nodes to determine routing problem by using the DAG as a reference topology. By
their positions in a DAG relative to each other and provides a means referencing a rank property that is related to the positions in the
to coordinate route repair in a way that endeavors to avoid loops. DAG, nodes are able to determine their positions in a DAG relative to
These mechanisms will be described in more detail later in this each other. This information is used by RPL in part to construct
specification. rules for movement relative to the DAG that endeavor to avoid loops.
It is important to note that the rank property is derived from
metrics, and not directly from the position in the DAG, as will be
discussed further.
As DAGs are organized, RPL will use a destination advertisement As DAGs are organized, RPL will use a destination advertisement
mechanism to build up routing tables in support of outward P2MP mechanism to build up routing tables in support of outward P2MP
traffic flows. This mechanism, using the DAG as a reference, traffic flows. This mechanism, using the DAG as a reference,
distributes routing information across intermediate nodes (between distributes routing information across intermediate nodes (between
the DAG leaves and the root), guided along the DAG, such that the the DAG leaves and the root), guided along the DAG, such that the
routes toward destination prefixes in the outward direction may be routes toward destination prefixes in the outward direction may be
set up. As the DAG undergoes modification during DAG maintenance, set up. As the DAG undergoes modification during DAG maintenance,
the destination advertisement mechanism can be triggered to update the destination advertisement mechanism can be triggered to update
the outward routing state. the outward routing state.
Arbitrary P2P traffic may flow inward along the DAG until a common A baseline support for P2P traffic in RPL is provided by the DAG, as
parent is reached who has stored an entry for the destination in its P2P traffic may flow inward along the DAG until a common parent is
routing table and is capable of directing the traffic outward along reached who has stored an entry for the destination in its routing
the correct outward path. In the present specification RPL does not table and is capable of directing the traffic outward along the
specify nor preclude any additional mechanisms that may be capable to correct outward path. RPL also provides support for the trivial case
compute and install more optimal routes into LLN nodes in support of where a P2P destination may be a `one-hop' neighbor. In the present
arbitrary P2P traffic according to some routing metric. specification RPL does not specify nor preclude any additional
mechanisms that may be capable to compute and install more optimal
routes into LLN nodes in support of arbitrary P2P traffic according
to some routing metric.
3.2.1. DAG Construction 3.2.1. DAG Construction
3.2.1.1. Overview of a Typical Case
RPL constructs one or more DAGs, over gradients defined by optimizing RPL constructs one or more DAGs, over gradients defined by optimizing
cost metrics along paths rooted at designated nodes. cost metrics along paths rooted at designated nodes.
DAGs may be grounded, in which case the DAG root (e.g. an LBR) is The DAG construction algorithm is distributed; each node running RPL
offering connectivity to an external routed infrastructure such as invokes a set of DAG construction rules and objective functions when
the public Internet or a private core (non-LLN) IP network. A considering its role with respect to neighboring nodes such that the
typical goal for a node participating in DAG construction may be to DAG structure emerges.
find and join a grounded DAG. Any DAG which is not grounded is
floating, and routes may still be provisioned toward the DAG root
although with no expectations of reaching an external infrastructure.
In the context of a particular LLN application one or more nodes will
be capable of, e.g. serving as an LBR or acting as a data collection
point, and thus be provisioned to act as the most preferred DAG
roots. These nodes will initiate and continue the process of
constructing a DAG by occasionally emitting IPv6 Router Advertisement
(RA) messages containing the necessary information for neighboring
nodes to evaluate the DAG root as a potential DAG parent. This
information will include at least a DAGID, an administrative
preference, and an Objective Code Point (OCP). The DAGID is an
identifier unique to the DAG. The administrative preference offers a
way to engineer the formation of the DAG in support of the
application, by providing a mechanism by which the DAG may look more
or less attractive for other nodes to join. The OCP provides
information as to which metrics and optimization goals are being
employed across the DAG.
Nodes who hear RA messages, advertising a specific DAGID, will take
into consideration several criteria when processing the extracted DAG
information. A node may seek a DAG advertising a specific OCP,
reflecting the implementation specific routing constraints understood
by the node. In particular, a node will be seeking to find a least
cost path satisfying some objective function as indicated by the OCP
according to some routing metrics defined in
[I-D.ietf-roll-routing-metrics]. For example, the least cost path
may be determined in part by minimizing energy along a path, or
latency, or avoiding the use of battery powered nodes. A node may be
seeking to explicitly join a grounded DAG. Further, a node may seek
the most desirable administrative preference when selecting a DAG,
all else being equal. Based on the evaluation of such criteria, a
node may determine if the node who emitted the RA message should be
considered as a potential DAG parent. If so, then the node may add
the advertising node to its set of candidate DAG parents for the
advertised DAGID, and after waiting for a designated delay, the node
may follow the procedures to activate the advertising node as a DAG
parent and may then be considered to have joined the DAG designated
by DAGID.
When a node adds the first DAG parent to the set of DAG parents for a
particular DAGID, the node is said to have joined, or attached to,
the DAG designated by DAGID. Adding additional DAG parents beyond
the first simply increases path diversity inwards toward the DAG
root. When a node removes the last DAG parent from the set of DAG
parents for a particular DAGID, the node is said to have left, or
detached from, the DAG designated by DAGID. RPL will coordinate the
joining, leaving, and movement of nodes within a DAGID in such a way
so as to avoid the formation of loops, as described further below.
As nodes join the DAG they are able advertise the fact by
multicasting the DAG information in RA messages (to neighbors with a
link-local scope). In this way, nodes are able to join the DAG at
ever-increasing rank outward from the DAG root. As nodes continue to
receive DAG multicasts they may continue to expand their set of DAG
parents, while employing loop avoidance strategies as described
below, in order to build path diversity inwards toward the DAG root.
Using the information conveyed in the metrics of its most preferred
DAG parent, its own metrics, and the conventions and functions
indicated by the OCP, a node is able to compute a rank value within
the DAG which it will use to coordinate its DAG maintenance.
Once a preferred parent is selected, the node can compute its own
rank in the DAG and determine alternate parents. Any node inwards
from this node, that is with a lower rank than this node, can be used
as an alternate parent for forwarding.
In addition to identifying DAG parents, a node also may hear the RA
messages of other neighboring nodes at the same rank within the DAG.
In this way a node can discover DAG siblings. As it selects its
initial position within a DAG, a node MAY increment its rank it order
to have at least one sibling but it SHOULD NOT increase it as to
obtain more parents.
A node may order its set of DAG parents according to some
implementation specific preference, and it SHOULD install a DAG
parent as a default gateway. To this list the node may also append a
similarly ordered set of DAG siblings. By forwarding traffic
intended for the default destination towards the DAG parents, the
node is able to support the main Multipoint-to-point (MP2P) traffic
flows required by a typical LLN application. By using the ordered
set of DAG parents and DAG siblings the node is able to take
advantage of path diversity. For example, preferring to forward
traffic towards parents guarantees to get the traffic inwards, closer
to the DAG root, by definition, regardless of which parent is
selected. In this example, if forwarding towards parents is not
possible, perhaps due to a transient phenomena, then a node may then
choose to forward traffic towards siblings, moving across the DAG at
the same level (neither inwards or outwards). When receiving traffic
forwarded from a sibling, the traffic should not be forwarded back to
the same sibling in order to avoid a 2-node loop.
By employing this procedure, the LLN is able to set up a path-
constrained DAG, rooted at designated nodes, with other nodes
organized along paths leading inward toward the DAG root. MP2P
traffic intended for the destinations available to or through the DAG
root, e.g. the default destination or other advertised prefixes,
flows inward along the DAG towards the root, and nodes forwarding
traffic are able to leverage the path diversity of the DAG as
necessary.
Further mechanisms described below will populate the routing tables
along the DAG in support of P2MP and P2P traffic.
3.2.1.2. Further Operation
The sub-DAG of a node is the set of other nodes of greater rank in
the DAG that might use a path towards the DAG root that contains this
node. Rank in the DAG is defined such that nodes contained in the
sub-DAG of a specific node should have a greater rank than the node.
This is an important property that is leveraged for loop avoidance-
if a node has lesser rank then it is not in the sub-DAG. (An
arbitrary node with greater rank may or may not be contained in the
sub-DAG). Paths through siblings are not contained in this set.
As a further illustration, consider the DAG examples in Appendix B.
Consider Node (24) in the DAG Example depicted in Figure 12. In this
example, the sub-DAG of Node (24) is comprised of Nodes (34), (44),
and (45).
A DAG may also be floating. Floating DAGs may be encountered, for
example, during coordinated reconfigurations of the network topology
wherein a node and its sub-DAG breaks off the DAG, temporarily
becomes a floating DAG, and reattaches to a grounded DAG at a
different (more optimal) location. (Such coordination endeavors to
avoid the construction of transient loops in the LLN). A DAG, or a
sub-DAG, may also become floating because of a network element
failure. Note that in the case where a floating DAG exists as a
consequence of DAG repair, the floating DAG is also intended to be
transient and carries a marking to make it less attractive. Some
specific application scenarios may employ permanent floating DAGs,
e.g. DAGs without connectivity to an external routed infrastructure,
as a matter of normal operation. In such cases the floating DAG is
likely to have been provisioned by the application with an
administrative preference which will make it more attractive.
A node will generally join at least one DAG, typically (but not
necessarily) to or through a grounded DAG rooted at an LBR. In some
cases, as suitable to the application scenario, a DAG may still
provision the DAG parents as default gateways and not be connected to
a non-LLN infrastructure such as the public Internet or a private IP
network.
This specification does not preclude a node from joining multiple
DAGs. In one such case, a particular application may require the
node to maintain membership in multiple DAGs in order to satisfy
competing constraints, for example to support different types of
traffic, similar to the concept of MTR (Multi-topology routing) as
supported by other routing protocols such as IS-IS [RFC5120] or OSPF
[RFC4915], although the RPL mechanisms will significantly differ from
the ones specified for these protocols. (Note that not all
constrained traffic cases may require multiple DAGs). In support of
such cases the RPL implementation must independently maintain
requisite information and state for each DAG in parallel. In cases
where a competing constraints must be satisfied toward the same DAG
root, the OCP should differ by definition and may serve to coordinate
the maintenance of the multiple DAGs. Further, additional
recommendations for the operation of loop avoidance/loop detection
mechanisms in the presence of multiple DAGs are under investigation.
An administrative preference, the DAG preference, shall be associated
with each DAG. In cases where a RPL node has a choice of joining
more than one DAG to satisfy a particular constraint, and all else
being equal, the node will seek to join the most preferred DAG as
indicated by the administrative preference. In practice this
mechanism may be assist in engineering the construction of a DAG as
appropriate to an application. For example, nodes that are to become
DAG roots in support of a particular application role, e.g. as a data
sink or a controller, may be provisioned such that they have are more
preferred. Nodes who are serving as the DAG root of a transient DAG,
e.g. for DAG repair, may take on a less desirable preference value.
Nodes will then be able to yield their transient DAGs to join the
DAGs that are more preferred.
3.2.1.3. IP Router Advertisement - DAG Information Option (RA-DIO) 3.2.1.1. IP Router Advertisement - DAG Information Option (RA-DIO)
The IPv6 Router Advertisement (RA) mechanism (as specified in The IPv6 Router Advertisement (RA) mechanism (as specified in
[RFC4861]) is used by RPL in order to build and maintain a DAG. [RFC4861]) is used by RPL in order to build and maintain a DAG.
The IPv6 RA message is augmented with a DAG Information Option (DIO), The IPv6 RA message is augmented with a DAG Information Option (DIO),
forming an RA-DIO message, in order to facilitate the formation and forming an RA-DIO message, to convey information about the DAG
maintenance of DAGs. The information conveyed in the RA-DIO message including:
includes the following:
o A DAGID used to identify the DAG as sourced from the DAG root. o A DAGID used to identify the DAG as sourced from the DAG root.
Typically the (potentially compressed) IPv6 address of the DAG The DAGID must be unique to a single DAG in the scope of the LLN.
root. The DAGID must be unique to a single DAG in the scope of
the LLN. If the DAG root is rooting multiple DAGs, each DAG must
be provisioned with their own IPv6 address and thus derive unique
DAGIDs.
o Objective Code Point (OCP) as described below. o Objective Code Point (OCP) as described below.
o Rank information used by nodes to determine their relationships in o Rank information used by nodes to determine their positions in the
the DAG relative to each other, i.e. parents, siblings, or DAG relative to each other. This is not a metric, although its
children. This is not a metric, although its derivation is derivation is typically closely related to one or more metrics as
typically closely related to one or more metrics as specified by specified by the OCP. The rank information is used to support
the OCP. The rank information is used to support loop avoidance loop avoidance strategies and in support of ordering alternate
strategies and in support of ordering alternate successors when successors when engaged in path maintenance.
engaged in path maintenance.
o Sequence number originated from the DAG root, used to aid in o Sequence number originated from the DAG root, used to aid in
identification of dependent sub-DAGs and coordinate topology identification of dependent sub-DAGs and coordinate topology
changes in a manner so as to avoid loops. changes in a manner so as to avoid loops.
o Indications for the DAG, e.g. grounded or floating. o Indications and configuration for the DAG, e.g. grounded or
floating, administrative preference, ...
o DAG configuration parameters.
o A vector of path metrics. As discussed in o A vector of path metrics, as further described in
[I-D.ietf-roll-routing-metrics] such metrics may be cumulative, [I-D.ietf-roll-routing-metrics].
may report a maximum, minimum, or average scalar value, or a link
property.
o List of additional destination prefixes reachable via the DAG o List of additional destination prefixes reachable inwards along
root. the DAG.
The RA messages are issued whenever a change is detected to the DAG The RA messages are issued whenever a change is detected to the DAG
such that a node is able to determine that a region of the DAG has such that a node is able to determine that a region of the DAG has
become inconsistent. As the DAG stabilizes the period at which RA become inconsistent. As the DAG stabilizes the period at which RA
messages occur is configured to taper off, reducing the steady-state messages occur is configured to taper off, reducing the steady-state
overhead of DAG maintenance. The periodic issue of RA messages, overhead of DAG maintenance. The periodic issue of RA messages,
along with the triggered RA messages in response to inconsistency, is along with the triggered RA messages in response to inconsistency, is
one feature that enables RPL to operate in the presence of unreliable one feature that enables RPL to operate in the presence of unreliable
links. links.
The RA-DIO and related mechanisms are described in more detail in 3.2.1.2. DAG Identification
Section 5.
3.2.1.4. Objective Code Point (OCP) Each DAG is identified by a particular identifier (DAGID) as well as
its supported optimization objectives and available destination
prefixes. The optimization objectives are conveyed as an Objective
Code Point (OCP) as described further below. Available destination
prefixes, which may include destinations available beyond the DAG
root, multicast destinations, or IPv6 node addresses, are advertised
outwards along the DAG and recipient nodes may then provision routing
tables with entries inwards towards the destinations. The RPL
implementation at each node will be provisioned by the application
with sufficient information to determine which objectives and
destinations are required, and thus the RPL implementation may
determine which DAG to join.
The OCP is seeded by the DAG root and serves to convey and control The decision for a node to join a DAG may be optimized according to
the optimization functions used within the DAG. The OCP is further implementation specific policy functions on the node as indicated by
specified in [I-D.ietf-roll-routing-metrics]. Each instance of an one or more specific OCP values. For example, a node may be
allocated OCP indicates: configured for one goal to optimize a bandwidth metric (OCP-1), and
with a parallel goal to optimize for a reliability metric (OCP-2).
Thus two DAGs, with two unique DAGIDs, may be constructed and
maintained in the LLN: DAG-1 would be optimized according to OCP-1,
whereas DAG-2 would be optimized according to OCP-2. A node may then
maintain independent sets of DAG parents and related data structures
for each DAG. Note that in such a case traffic may directed along
the appropriate constrained DAG based on traffic marking within the
IPv6 header. This specification will focus on the case where the
node only joins one DAG; further elaboration on the proper operation
of RPL in the presence of multiple DAGs, including traffic marking
and related rules, are to be specified further in future revisions of
this or companion specifications.
3.2.1.3. Grounded and Floating DAGs
Certain LLN nodes may offer connectivity to an external routed
infrastructure in support of an application scenario. These nodes
are designated `grounded', and may serve as the DAG roots of a
grounded DAG. DAGs that do not have a grounded DAG root are floating
DAGs. In either case routes may be provisioned toward the DAG root,
although in the floating case there is no expectation to reach an
external infrastructure. Some applications will include permanent
floating DAGs.
3.2.1.4. Administrative Preference
An administrative preference may be associated with each DAG root,
and thereby each DAG, in order that some DAGs in the LLN may be more
preferred over other DAGs. For example, a DAG root that is sinking
traffic in support of a data collection application may be configured
by the application to be very preferred. A transient DAG, e.g. a DAG
that is only existing in support of DAG repair until a permanent DAG
is found, may be configured to be less preferred. The administrative
preference offers a way to engineer the formation of the DAG in
support of the application.
3.2.1.5. Objective Code Point (OCP)
The OCP serves to convey and control the optimization objectives in
use within the DAG. The OCP is further specified in
[I-D.ietf-roll-routing-metrics]. Each instance of an allocated OCP
indicates:
o The set of metrics used within the DAG o The set of metrics used within the DAG
o The objective functions used to determine the least cost
constrained paths in order to optimize the DAG o The objective functions used for least cost path determination.
o The function used to compute DAG Rank o The function used to compute DAG Rank
o The functions used to construct derived metrics for propagation o The functions used to accumulate metrics for propagation within a
within a RA-DIO message RA-DIO message
For example, an objective code point might indicate that the DAG is For example, an objective code point might indicate that the DAG is
using the Expected Number of Transmissions (ETX) as a metric, that using the Expected Number of Transmissions (ETX) as a metric, that
the optimization goal is to minimize ETX, that DAG Rank is equivalent the optimization goal is to minimize ETX, that DAG Rank is equivalent
to ETX, and that RA-DIO propagation entails adding the advertised ETX to ETX, and that RA-DIO propagation entails adding the advertised ETX
of the most preferred parent to the ETX of the link to the most of the most preferred parent to the ETX of the link to the most
preferred parent. preferred parent.
By using defined OCPs that are understood by all nodes in a By using defined OCPs that are understood by all nodes in a
particular implementation, and by conveying them in the RA-DIO particular implementation, and by conveying them in the RA-DIO
message, RPL nodes may work to build optimized LLN using a variety of message, RPL nodes may work to build optimized LLN using a variety of
application and implementation specific metrics and goals. application and implementation specific metrics and goals.
A default OCP, OCP 0, is specified with a well-defined default A default OCP, OCP 0, is specified with a well-defined default
behavior. OCP 0 is used to define RPL behaviors in the case where a behavior. OCP 0 is used to define RPL behaviors in the case where a
node encounters a RA-DIO message containing a code point that it does node encounters a RA-DIO message containing a code point that it does
not support. not support.
3.2.1.5. Selection of Feasible DAG Parents 3.2.1.6. Distributed Algorithm Operation
The decision for a node to join a DAG may be optimized according to
implementation specific policy functions on the node as indicated by
one or more specific OCP values. For example, a node may be
configured for one goal to optimize a bandwidth metric (OCP-1), and
with a parallel goal to optimize for a reliability metric (OCP-2).
Thus two DAGs, with two unique DAGIDs, may be constructed and
maintained in the LLN: DAG-1 would be optimized according to OCP-1,
whereas DAG-2 would be optimized according to OCP-2. A node may then
maintain two parallel sets of DAG parents and related data
structures. Note that in such a case traffic may directed along the
appropriate constrained DAG based on traffic marking within the IPv6
header.
As a node hears RA messages from its neighbors it may process their
attached DIO messages. At this time the node may be able to take
into consideration, for example, the following:
o Is the neighboring node heard reliably enough, and are the metrics o Some nodes may be initially provisioned to act as DAG roots,
stable enough, that a local degree of confidence may be either permanent or transient, with associated preferences.
established with respect to the neighboring node? Should the
neighboring node be considered in the set of candidate neighbors?
o In consultation with implementation specific policy (OCP goal), is o Nodes will maintain a data structure containing their candidate
the neighboring node a feasible parent from a constrained-path (viable) neighbors, as based on guidelines in
perspective? [I-D.ietf-roll-routing-metrics] This data structure will also
track DAG information as learned from and associated with each
neighbor.
o According to the implementation specific policy (OCP), does the o Nodes who are members of a DAG, including DAG roots, will
neighboring node offer a better optimized position into the DAG? multicast RA-DIO messages as needed (when inconsistency is
detected), to their link-local neighbors. Nodes will also respond
to Router Solicitation (RS) messages.
o Does the neighboring node offer a DAG with a more desirable o Nodes who receive RA-DIO messages will take into consideration
administrative preference for an otherwise currently satisfied several criteria when processing the extracted DAG information.
optimization objective, all else being equal? The node may discount the RA-DIO according to loop avoidance rules
based on rank as described further below. Nodes will consider the
information in the RA-DIO in order to determine whether or not
that candidate neighbor offers a better attachment point to a DAG
(which the node may or may not be a member of) according to the
implementation specific optimization goals, OCP, and current
metrics.
o Is the neighboring node a peer (sibling) within the DAG? o Nodes may join a new DAG or move within the current DAG, in
response to the information contained in the RA-DIO message, and
in accordance with loop avoidance rules described further in this
specification. For the successors within the DAG, a node manages
a set of DAG Parents. Joining, moving within, and leaving the DAG
is accomplished through managing this set according to the rules
specified by RPL.
Based on such considerations, the node may incorporate the o As nodes join, move within, and leave DAGs they emit updated RA-
neighboring node into the set of DAG parents. When the node inserts DIOs which are received and acted on by neighboring nodes. When
the first DAG parent into the empty DAG parent set, it is able to inconsistencies (such as caused by movement or link loss) are
join the DAG. As the DAG parent set is updated, the node will detected within the DAG structure, RA-DIO messages are emitted
consult a rank computation function indicated by the OCP for the DAG more frequently. When the DAG structure becomes consistent, RA-
in order to determine its own rank value, which it will subsequently DIO messages taper off.
advertise when it emits its own RA-DIO messages.
Following is an overview of the rules used to select a parent (the o As less preferred DAGs encounter more preferred DAGs that offer
detailed mode of operation for the selection of the candidate DAG equivalent or better optimization objectives, the nodes in the
parent(s) is described in Section 5.3. First, it is important to less preferred DAGs may leave to join the more preferred DAGs,
note that the rank of the node is not directly used as a selection finally leaving only the more preferred DAGs. This is an
criteria. The metric of choice as indicated by the OCP advertised by illustration of the mechanism by which an application may engineer
the candidate parents is used to select the parent, although the use DAG construction.
of a cumulative metric to reflect the rank is not precluded.
Consider an example where a node N receives two RAs from node A and B o As the DAG construction operation proceeds, nodes accumulate onto
with (rank, metric) equal to (2,4) and (5,3) respectively. Node N the DAG in progressively outward tiers, centered around the DAG
may chose B as its parent (higher rank but smaller metric). Once the root.
parent, B, is selected, the node computes its own rank according to
the OCP.
If the node receives other RA messages it cannot attach to other o The nodes provision routing table entries for the destinations
parents if choosing that parent would cause the nodes own rank to specified by the RA-DIO towards their DAG Parents. Nodes may
increase. Back to the previous example, suppose that a node C provision a DAG Parent as a default gateway.
appears with a (rank, metric) equal to (5,1). By selecting C as the
new parent, N would have a rank of 6 (making the assumption that the
rank is increased by a value of 1 according to the OCP). Although
the path metric would be lower, this may lead to a DAG Loop should C
belong to the sub-DAG of N as further discussed in Section 3.3.1.
All reliable neighboring nodes of a lesser rank than the node may be 3.2.1.7. DAG Rank
considered as potential DAG parents (Note that, as in the above
example, as a consequence of satisfying a particular OCP goal, the
most preferred parent may not necessarily be the potential parent of
least rank, for example a potential parent of lesser rank may also be
an energy constrained device that is to generally be avoided and thus
not the most preferred). No nodes of greater rank than self may be
in the DAG parent set; to allow such nodes will introduce a
possibility to create loops (by potentially allowing a packet to make
backwards progress as it is forwarded in the DAG). All neighboring
nodes of equal rank may be considered as siblings within the DAG
(even though they may not have parents in common, they may still
provide path diversity towards the DAG root).
The computation of rank, and related properties, are further When nodes select DAG parents, they will select the most preferred
described in Section 3.3.1. parent according to their implementation specific objectives, using
the cost metrics conveyed in the RA-DIO messages along the DAG in
conjunction with the related objective functions as specified by the
OCP.
3.2.1.5.1. Example Based on this selection, the metrics conveyed by the most preferred
DAG parent, the nodes own metrics and configuration, and a related
function defined by the OCP, a node will be able to compute a value
for its rank as a consequence of selecting a most preferred DAG
parent.
For example, suppose that a node (N) is not attached to any DAG, and The rank value feeds back into the DAG parent selection according to
that it is in range of nodes (A), (B), (C), (D), and (E). Let all a loop-avoidance strategy. Once a DAG parent has been added, and a
nodes be configured to use an OCP which defines a policy such that rank value for the node within the DAG has been computed, the nodes
ETX is to be minimized and paths with the attribute `Blue' should be further options with regard to DAG parent selection and movement
avoided. Let the rank computation indicated by the OCP simply within the DAG are restricted in favor of loop avoidance.
reflect the ETX aggregated along the path. Let the links between
node (N) and its neighbors (A-E) all have an ETX of 1 (which is
learned by node (N) through some implementation specific method).
Let node (N) be configured to send IPv6 Router Solicitation (RS)
messages to probe for nearby DAGs.
o Node (N) transmits a Router Solicitation. It is important to note that the DAG Rank is not itself a metric,
although its value is derived from and influenced by the use of
metrics to select DAG parents and take up a position in the DAG. In
other words, routing metrics and OCP (not rank directly) are used to
determine the DAG structure and consequently the path cost. The only
aim of the rank is to inform loop avoidance as explained hereafter.
The computation of the DAG Rank MUST be done in such a way so as to
maintain the following properties for any nodes M and N who are
neighbors in the LLN:
o Node (B) responds. Node (N) investigates the RA-DIO message, and For a node N, and its most preferred parent M, DAGRank(N) >
learns that Node (B) is a member of DAGID 1 at rank 4, and not DAGRank(M) must hold. Further, all parents in the DAG parent set
`Blue'. Node (N) takes note of this, but is not yet confident. must be of a rank less than self's DAGRank(N). In other words,
the rank presented by a node N MUST be greater (deeper) than that
presented by any of its parents.
o Similarly, Node (N) hears from Node (A) at rank 9, Node (C) at If DAGRank(M) < DAGRank(N), then M is probably located in a more
rank 5, and Node (E) at rank 4. preferred position than N in the DAG with respect to the metrics
and optimizations defined by the objective code point. In any
fashion, Node M may safely be a DAG parent for Node N without risk
of creating a loop.
o Node (D) responds. Node (D) has a RA-DIO message that indicates For example, a Node M of rank 3 is likely located in a more
that it is a member of DAGID 1 at rank 2, but it carries the optimum position than a Node N of rank 5. A packet directed
attribute `Blue'. Node (N)'s policy function rejects Node (D), inwards and forwarded from Node N to Node M will always make
and no further consideration is given. forward progress with respect to the DAG organization on that
link; there is no risk of Node M at rank 3 forwarding the
packet back into Node N's sub-DAG at rank of 5 or greater
(which would be a sufficient condition for a loop to occur).
o This process continues until Node (N), based on implementation If DAGRank(M) == DAGRank(N), then M and N are located positions of
specific policy, builds up enough confidence to trigger a decision relatively the same optimality within the DAG. In some cases,
to join DAGID 1. Let Node (N) determine its most preferred parent Node M may be used as a successor by Node N, but with related
to be Node (E). chance of creating a loop that must be detected and broken by some
other means.
o Node (N) adds Node (E) (rank 4) to its set of DAG parents for If Node M is at rank 3 and node N is at rank 3, then they are
DAGID 1. Following the mechanisms specified by the OCP, and given siblings; by definition Node M and N cannot be in each others
that the ETX is 1 for the link between (N) and (E), Node (N) is sub-DAG. They may then forward to each other failing
now at rank 5 in DAGID 1. serviceable parents, making `sideways' progress (but not
reverse progress). If another sibling or more gets involved
there may then be some chance for 3 or more way loops, which is
the risk of sibling forwarding.
o Node (N) adds Node (B) (rank 4) to its set of DAG parents for If DAGRank(M) > DAGRank(N), then node M is located in a less
DAGID 1. preferred position than N in the DAG with respect to the metrics
and optimizations defined by the objective code point. Further,
Node (M) may in fact be in Node (N)'s sub-DAG. There is no
advantage to Node (N) selecting Node (M) as a DAG parent, and such
a selection may create a loop.
o Node (N) is a sibling of Node (C), both are at rank 5. For example, if Node M is of rank 3 and Node N is of rank 5,
then by definition Node N is in a less optimum position than
Node N. Further, Node N at rank 5 may in fact be in Node M's
own sub-DAG, and forwarding a packet directed inwards towards
the DAG root from M to N will result in backwards progress and
possibly a loop.
o Node (N) may now forward traffic intended for the default As an example, the DAG Rank could be computed in such a way so as to
destination inward along DAGID 1 via nodes (B) and (E). In some closely track ETX when the objective function is to minimize ETX, or
cases, e.g. if nodes (B) and (E) are tried and fail, node (N) may latency when the objective function is to minimize latency, or in a
also choose to forward traffic to its sibling node (C), without more complicated way as appropriate to the objective code point being
making inward progress but with the intention that node (C) or a used within the DAG.
following successor can make inward progress. Should Node (C) not
have a viable parent, it should never send the packet back to Node
(N) (to avoid a 2-node loop).
3.2.1.6. DAG Maintenance The DAG rank is subsequently used to restrict the options a node has
for movement within the DAG and to coordinate movements in order to
avoid the creation of loops.
When a node moves within a DAG, the move is defined as updating the 3.2.1.8. Sub-DAG
set of DAG parents for a particular DAGID, i.e. adding or deleting
DAG parents. Not all moves entail changes in rank.
A jump from one DAG to another DAG is attaching to a new DAGID, in The sub-DAG of a node is the set of other nodes of greater rank in
such a way that an old DAGID is replaced by the new DAGID. In the DAG, and thus might use a path towards the DAG root that contains
particular, when an old DAGID is left, all associated parents are no this node. This is an important property that is leveraged for loop
longer feasible, and a new DAGID is joined. avoidance- if a node has lesser rank then it is not in the sub-DAG.
(An arbitrary node with greater rank may or may not be contained in
the sub-DAG). Paths through siblings are not contained in this set.
When a node in a DAG follows a DAG parent, it means that the DAG As a further illustration, consider the DAG examples in Appendix B.
parent has changed its DAGID (e.g. by joining a new DAG) and that the Consider Node (24) in the DAG Example depicted in Figure 9. In this
node updates its own DAGID in order to keep the DAG parent. example, the sub-DAG of Node (24) is comprised of Nodes (34), (44),
and (45).
A frozen sub-DAG is a subset of nodes in the sub-DAG of a node who A frozen sub-DAG is a subset of nodes in the sub-DAG of a node who
have been informed of a change to the node, and choose to follow the have been informed of a change to the node, and choose to follow the
node in a manner consistent with the change, for example in node in a manner consistent with the change, for example in
preparation for a coordinated move. Nodes in the sub-DAG who hear of preparation for a coordinated move. Nodes in the sub-DAG who hear of
a change and have other options than to follow the node do not have a change and have other options than to follow the node do not have
to become part of the frozen sub-DAG, for example such a node may be to become part of the frozen sub-DAG, for example such a node may be
able to remain attached to the original DAG through a different DAG able to remain attached to the original DAG through a different DAG
parent. A further example may be found in Section 3.3.1.1. parent. A further example may be found in Appendix B.8.
When the node encounters new candidate neighbors that offer higher 3.2.1.9. Moving up in a DAG
positions in the DAG, it may incorporate them directly into its set
of DAG parents. In this case the node may update its choice of most
preferred parent, possibly causing its own advertised rank to
decrease, and discarding any former parents now of a deeper rank.
This case is `moving inwards along the DAG' and does not require any
additional coordination for loop avoidance.
If the DAG parent set of the node becomes completely depleted, the A node may safely move `up' in the DAG, causing its DAG rank to
node will have detached from the DAG, and may, if so configured, decrease and moving closer to the DAG root without risking the
become the root of its own transient floating DAG with a less formation of a loop.
desirable administrative preference (thus beginning the process of
establishing the frozen sub-DAG), and then may reattach to the
original DAG at a lower point if it is able (after hearing RA-DIO
messages from alternate attachment points).
When the node encounters candidate parents that are in a different 3.2.1.10. Moving down in a DAG
DAG, and decides to leave the current DAG in order to join the
different DAG (thus doing a jump), it may do so safely without regard
to loop avoidance. However, it may not return immediately to the
current DAG as such movement may result in the creation of a DAG
Loop, in particular if it reattaches back into its own former sub-DAG
in an uncoordinated manner.
When a node, and perhaps a related frozen sub-DAG, jumps to a A node may not consider to move `down' the DAG, causing its DAG rank
different DAG, the move is coordinated by a DAG Hop timer. The DAG to increase and moving further from the DAG root. In the case where
Hop timer allows the nodes who will attach closer to the sink of the a node looses connectivity to the DAG, it must first leave the DAG
new DAG to `jump' first, and then drag dependent nodes behind them, before it may then rejoin at a deeper point. This allows for the
thus endeavoring to efficiently coordinate the attachment of the node to coordinate moving down, freezing its own sub-DAG and
frozen sub-DAG into the new DAG. A further illustration of this poisoning stale routes to the DAG, and minimizing the chances of re-
mechanism may be found in Section 3.3.3. attaching to its own sub-DAG thinking that it has found the original
DAG again. If a node where allowed to re-attach into its own sub-DAG
a loop would most certainly occur, and may not be broken until a
count-to-infinity process elapses. The procedure of detaching before
moving down eliminates the need to count-to-infinity.
Appendix B provides additional examples of DAG discovery and 3.2.1.11. DAG Jumps
maintenance.
A jump from one DAG to another DAG is attaching to a new DAGID, in
such a way that an old DAGID is replaced by the new DAGID. In
particular, when an old DAGID is left, all associated parents are no
longer feasible, and a new DAGID is joined.
When a node in a DAG follows a DAG parent, it means that the DAG
parent has changed its DAGID (e.g. by joining a new DAG) and that the
node updates its own DAGID in order to keep the DAG parent.
3.2.1.12. Floating DAGs for DAG Repair
A DAG may also be floating. Floating DAGs may be encountered, for
example, during coordinated reconfigurations of the network topology
wherein a node and its sub-DAG breaks off the DAG, temporarily
becomes a floating DAG, and reattaches to a grounded DAG. (Such
coordination endeavors to avoid the construction of transient loops
in the LLN).
A DAG, or a sub-DAG temporarily promoted to a DAG, may also become
floating because of a network element failure. If the DAG parent set
of the node becomes completely depleted, the node will have detached
from the DAG, and may, if so configured, become the root of its own
transient floating DAG with a less desirable administrative
preference (thus beginning the process of establishing the frozen
sub-DAG), and then may reattach to the original DAG at a lower point
if it is able (after hearing RA-DIO messages from alternate
attachment points).
3.2.2. Destination Advertisement 3.2.2. Destination Advertisement
As RPL constructs DAGs, nodes may provision routes toward As RPL constructs DAGs, nodes may provision routes toward
destinations advertised through RA-DIO messages through their destinations advertised through RA-DIO messages through their
selected parents, and are thus able to send traffic inward along the selected parents, and are thus able to send traffic inward along the
DAG by forwarding to their selected parents. However, this mechanism DAG by forwarding to their selected parents. However, this mechanism
alone is not sufficient to support P2MP traffic flowing outward along alone is not sufficient to support P2MP traffic flowing outward along
the DAG from the DAG root toward nodes. A destination advertisement the DAG from the DAG root toward nodes. A destination advertisement
mechanism is employed by RPL to build up routing state in support of mechanism is employed by RPL to build up routing state in support of
skipping to change at page 23, line 31 skipping to change at page 21, line 39
along the DAG, and as according to the available resources in the along the DAG, and as according to the available resources in the
network. network.
Further aggregations of NA-DAO messages prefix reachability Further aggregations of NA-DAO messages prefix reachability
information by destinations are possible in order to support information by destinations are possible in order to support
additional scalability. additional scalability.
A further example of the operation of the destination advertisement A further example of the operation of the destination advertisement
mechanism is available in Appendix B.6 mechanism is available in Appendix B.6
3.3. Other Considerations 3.3. Loop Avoidance and Stability
3.3.1. DAG Rank and Loop Avoidance
When nodes select DAG parents, they should select the most preferred
parent according to their implementation specific objectives, using
the cost metrics conveyed in the RA-DIO messages along the DAG in
conjunction with the related objective functions as specified by the
OCP.
Based on this selection, the metrics conveyed by the most preferred
DAG parent, the nodes own metrics and configuration, and a related
function defined by the objective code point, a node will be able to
compute a value for its rank as a consequence of selecting a most
preferred DAG parent.
It is important to note that the DAG Rank is not itself a metric,
although its value is derived from and influenced by the use of
metrics to select DAG parents and take up a position in the DAG. In
other words, routing metrics and OCP (not rank directly) are used to
determine the DAG structure and consequently the path cost. The only
aim of the rank is to inform loop avoidance as explained hereafter.
The computation of the DAG Rank MUST be done in such a way so as to
maintain the following properties for any nodes M and N who are
neighbors in the LLN:
For a node N, and its most preferred parent M, DAGRank(N) >
DAGRank(M) must hold. Further, all parents in the DAG parent set
must be of a rank less than self's DAGRank(N). In other words,
the rank presented by a node N MUST be greater (deeper) than that
presented by any of its parents. (This mechanism serves to avoid
loops in the case where an alternate parent is used- if no
alternate parent is deeper than the preferred parent then loops
are avoided. The risk of loops occurs if there is a chance for an
alternate parent to forward traffic to a deeper successor, which
may be in the sub-DAG, and traffic then makes backwards progress
and comes back to the node again).
If DAGRank(M) < DAGRank(N), then M is probably located in a more
optimum position than N in the DAG with respect to the metrics and
optimizations defined by the objective code point. In any
fashion, Node M may safely be a DAG parent for Node N without risk
of creating a loop. For example, a Node M of rank 3 is located in
a more optimum position than a Node N of rank 5. A packet
directed inwards and forwarded from Node N to Node M will always
make forward progress with respect to the DAG organization on that
link; there is no risk of Node M at rank 3 forwarding the packet
back into Node N's sub-DAG at rank of 5 or greater (which would be
a sufficient condition for a loop to occur).
If DAGRank(M) == DAGRank(N), then M and N are located positions of
relatively the same optimality within the DAG. In some cases,
Node M may be used as a successor by Node N, but with related
chance of creating a loop that must be detected and broken by some
other means. If Node M is at rank 3 and node N is at rank 3, then
they are siblings; by definition Node M and N cannot be in each
others sub-DAG. They may then forward to each other failing
serviceable parents, making `sideways' progress (but not reverse
progress). If another sibling or more gets involved there may
then be some chance for 3 or more way loops, which is the risk of
sibling forwarding.
If DAGRank(M) > DAGRank(N), then node M is located in a less
optimum position than N in the DAG with respect to the metrics and
optimizations defined by the objective code point. Further, Node
(M) may in fact be in Node (N)'s sub-DAG. There is no advantage
to Node (N) selecting Node (M) as a DAG parent, and such a
selection may create a loop. For example, if Node M is of rank 3
and Node N is of rank 5, then by definition Node N is in a less
optimum position than Node N. Further, Node N at rank 5 may in
fact be in Node M's own sub-DAG, and forwarding a packet directed
inwards towards the DAG root from M to N will result in backwards
progress and possibly a loop.
For example, the DAG Rank could be computed in such a way so as to
closely track ETX when the objective function is to minimize ETX, or
latency when the objective function is to minimize latency, or in a
more complicated way as appropriate to the objective code point being
used within the DAG.
The DAG rank is subsequently used to restrict the options a node has
for movement within the DAG and to coordinate movements in order to
avoid the creation of loops.
A node may safely move `up' in the DAG, causing its DAG rank to
decrease and moving closer to the DAG root without risking the
formation of a loop.
A node may not consider to move `down' the DAG, causing its DAG rank
to increase and moving further from the DAG root. Such a move will
entail moving to a less optimum position in the DAG in all cases, as
defined by the objective code point. In the case where a node looses
connectivity to the DAG, it must first leave the DAG before it may
then rejoin at a deeper point. This allows for the node to
coordinate moving down, freezing its own sub-DAG and poisoning stale
routes to the DAG, and minimizing the chances of re-attaching to its
own sub-DAG thinking that it has found the original DAG again. If a
node where allowed to re-attach into its own sub-DAG a loop would
most certainly occur, and may not be broken until a count-to-infinity
process elapses. The procedure of detaching before moving down
eliminates the need to count-to-infinity.
Any neighboring nodes of lesser rank than self are eligible to be
considered as alternate DAG parents for forwarding. But this node
may only adopt such a parent as new preferred parent if that does not
cause the resulting rank for this node to increase.
The goal of a guaranteed consistent and loop free global routing The goal of a guaranteed consistent and loop free global routing
solution for an LLN may not be practically achieved given the real solution for an LLN may not be practically achieved given the real
behavior and volatility of the underlying metrics. The trade offs to behavior and volatility of the underlying metrics. The trade offs to
achieve a stable approximation of global convergence may be too achieve a stable approximation of global convergence may be too
restrictive with respect to the need of the LLN to react quickly in restrictive with respect to the need of the LLN to react quickly in
response to the lossy environment. Globally the LLN may be able to response to the lossy environment. Globally the LLN may be able to
achieve a weak convergence, in particular as link changes are able to achieve a weak convergence, in particular as link changes are able to
be handled locally and result in minimal changes to global topology. be handled locally and result in minimal changes to global topology.
RPL does not aim to guarantee loop free path selection, or strong RPL does not aim to guarantee loop free path selection, or strong
global convergence. In order to reduce control overhead, in global convergence. In order to reduce control overhead, in
particular the expense of mechanisms such as count-to-infinity, RPL particular the expense of mechanisms such as count-to-infinity, RPL
does try to avoid the creation of loops when undergoing topology does try to avoid the creation of loops when undergoing topology
changes. Further mechanisms to mitigate the impact of loops, such as changes. Further mechanisms to mitigate the impact of loops, such as
loop detection when forwarding, are under investigation. loop detection when forwarding, are under investigation.
3.3.1.1. Example 3.3.1. Greediness and Rank-based Instabilities
: : :
: : :
(A) (A) (A)
|\ | |
| `-----. | |
| \ | |
(B) (C) (B) (C) (B)
| | \
| | `-----.
| | \
(D) (D) (C)
|
|
|
(D)
-1- -2- -3-
Figure 1: DAG Maintenance
Consider the example depicted in Figure 1-1. In this example, Node
(A) is attached to a DAG at some rank d. Node (A) is a DAG parent of
Nodes (B) and (C). Node (C) is a DAG parent of Node (D). There is
also an undirected sibling link between Nodes (B) and (C).
In this example, Node (C) may safely forward to Node (A) without
creating a loop. Node (C) may not safely forward to Node (D),
contained within it's own sub-DAG, without creating a loop. Node (C)
may forward to Node (B) in some cases, e.g. the link (C)->(A) is
temporarily unavailable, but with some chance of creating a loop
(e.g. if multiple nodes in a set of siblings start forwarding
`sideways' in a cycle) and requiring the intervention of additional
mechanisms to detect and break the loop.
Consider the case where Node (C) hears a RA-DIO message from a Node
(Z) at a lesser rank and superior position in the DAG than node (A).
Node (C) may safely undergo the process to evict node (A) from its
DAG parent set and attach directly to Node (Z) without creating a
loop, because its rank will decrease.
Now consider the case where the link (C)->(A) becomes nonviable, and
node (C) must move to a deeper rank within the DAG:
o Node (C) must first detach from the DAG by removing Node (A) from
its DAG parent set, leaving an empty DAG parent set. Node (C)
becomes the root of its own floating, less preferred, DAG.
o Node (D), hearing a modified RA-DIO message from Node (C), follows
Node (C) into the floating DAG. This is depicted in Figure 1-2.
In general, any node with no other options in the sub-DAG of Node
(C) will follow Node (C) into the floating DAG, maintaining the
structure of the sub-DAG.
o Node (C) hears a RA-DIO message from Node (B) and determines it is
able to rejoin the grounded DAG by reattaching at a deeper rank to
Node (B). Node (C) starts a DAG Hop timer to coordinate this
move.
o The timer expires and Node (C) adds Node (B) to its DAG parent
set. Node (C) has now safely moved deeper within the grounded DAG
without creating any loops. Node (D), and any other sub-DAG of
Node (C), will hear the modified RA-DIO message sourced from Node
(C) and follow Node (C) in a coordinated manner to reattach to the
grounded DAG. The final DAG is depicted in Figure 1-3
3.3.2. DAG Parent Selection, Stability, and Greediness
If a node is greedy and attempts to move deeper in the DAG, beyond If a node is greedy and attempts to move deeper in the DAG, beyond
its most preferred parent, in order to increase the size of the DAG its most preferred parent, in order to increase the size of the DAG
parent set, then an instability can result. This is illustrated in parent set, then an instability can result. This is illustrated in
Figure 2. Figure 11.
Suppose a node is willing to receive and process a RA-DIO messages Suppose a node is willing to receive and process a RA-DIO messages
from a node in its own sub-DAG, and in general a node deeper than it. from a node in its own sub-DAG, and in general a node deeper than it.
In such cases a chance exists to create a feedback loop, wherein two In such cases a chance exists to create a feedback loop, wherein two
or more nodes continue to try and move in the DAG in order to or more nodes continue to try and move in the DAG in order to
optimize against each other. In some cases this will result in an optimize against each other. In some cases this will result in an
instability. It is for this reason that RPL mandates that a node instability. It is for this reason that RPL mandates that a node
never receive and process RA-DIO messages from deeper nodes. This never receive and process RA-DIO messages from deeper nodes. This
rule creates an `event horizon', whereby a node cannot be influenced rule creates an `event horizon', whereby a node cannot be influenced
into an instability by the action of nodes that may be in its own into an instability by the action of nodes that may be in its own
sub-DAG. sub-DAG.
3.3.2.1. Example A further example of the consequences of greedy operation, and
instability related to processing RA-DIO messages from nodes of
(A) (A) (A) greater rank, may be found in Appendix B.9
|\ |\ |\
| `-----. | `-----. | `-----.
| \ | \ | \
(B) (C) (B) \ | (C)
\ | | /
`-----. | | .-----`
\| |/
(C) (B)
-1- -2- -3-
Figure 2: Greedy DAG Parent Selection
Consider the example depicted in Figure 2. A DAG is depicted in 3
different configurations. A usable link between (B) and (C) exists
in all 3 configurations. In Figure 2-1, Node (A) is a DAG parent for
Nodes (B) and (C), and (B)--(C) is a sibling link. In Figure 2-2,
Node (A) is a DAG parent for Nodes (B) and (C), and Node (B) is also
a DAG parent for Node (C). In Figure 2-3, Node (A) is a DAG parent
for Nodes (B) and (C), and Node (C) is also a DAG parent for Node
(B).
If a RPL node is too greedy, in that it attempts to optimize for an
additional number of parents beyond its preferred parent, then an
instability can result. Consider the DAG illustrated in Figure 2-1.
In this example, Nodes (B) and (C) may most prefer Node (A) as a DAG
parent, but are operating under the greedy condition that will try to
optimize for 2 parents.
When the preferred parent selection causes a node to have only one
parent and no siblings, the node may decide to insert itself at a
slightly higher rank in order to have at least one sibling and thus
an alternate forwarding solution. This does not deprive other nodes
of a forwarding solution and this is considered acceptable
greediness.
o Let Figure 2-1 be the initial condition.
o Suppose Node (C) first is able to leave the DAG and rejoin at a
lower rank, taking both Nodes (A) and (B) as DAG parents as
depicted in Figure 2-2. Now Node (C) is deeper than both Nodes
(A) and (B), and Node (C) is satisfied to have 2 DAG parents.
o Suppose Node (B), in its greediness, is willing to receive and
process a RA-DIO message from Node (C) (against the rules of RPL),
and then Node (B) leaves the DAG and rejoins at a lower rank,
taking both Nodes (A) and (C) as DAG parents. Now Node (B) is
deeper than both Nodes (A) and (C) and is satisfied with 2 DAG
parents.
o Then Node (C), because it is also greedy, will leave and rejoin
deeper, to again get 2 parents and have a lower rank then both of
them.
o Next Node (B) will again leave and rejoin deeper, to again get 2
parents
o And again Node (C) leaves and rejoins deeper...
o The process will repeat, and the DAG will oscillate between
Figure 2-2 and Figure 2-3 until the nodes count to infinity and
restart the cycle again.
o This cycle can be averted through mechanisms in RPL:
* Nodes (B) and (C) stay at a rank sufficient to attach to their
most preferred parent (A) and don't go for any deeper (worse)
alternate parents (Nodes are not greedy)
* Nodes (B) and (C) do not process RA-DIO messages from nodes
deeper than themselves (because such nodes are possibly in
their own sub-DAGs)
3.3.3. Merging DAGs 3.3.2. Merging DAGs
The merging of DAGs is coordinated in a way such as to try and merge The merging of DAGs is coordinated in a way such as to try and merge
two DAGs cleanly, preserving as much DAG structure as possible, and two DAGs cleanly, preserving as much DAG structure as possible, and
in the process effecting a clean merge with minimal likelihood of in the process effecting a clean merge with minimal likelihood of
forming transient DAG loops. The coordinated merge is also intended forming transient DAG loops. The coordinated merge is also intended
to minimize the related control cost. to minimize the related control cost.
3.3.3.1. Example When a node, and perhaps a related frozen sub-DAG, jumps to a
different DAG, the move is coordinated by a set of timers (DAG Hop
: timers). The DAG Hop timers allow the nodes who will attach closer
: to the sink of the new DAG to `jump' first, and then drag dependent
(A) (D) nodes behind them, thus endeavoring to efficiently coordinate the
| | attachment of the frozen sub-DAG into the new DAG.
| |
| |
(B) (E)
| |
| |
| |
(C) (F)
Figure 3: Merging DAGs
Consider the example depicted in Figure 3. Nodes (A), (B), and (C)
are part of some larger grounded DAG, where Node (A) is at a rank of
d, Node (B) at d+1, and Node (C) at d+2. The DAG comprised of Nodes
(D), (E), and (F) is a floating, less preferred, DAG, with Node (D)
as the DAG root. This floating DAG may have been formed, for
example, in the absence of a grounded DAG or when Node (D) had to
detach from a grounded DAG and (E) and (F) followed. All nodes are
using compatible objective code points.
Nodes (D), (E), and (F) would rather join the more preferred grounded A further example of a DAG Merge operation may be found in
DAG if they are able than to remain in the less preferred floating Appendix B.10
DAG.
Next, let links (C)--(D) and (A)--(E) become viable. The following 3.3.3. DAG Loops
sequence of events may then occur in a typical case:
o Node (D) will receive and process a RA-DIO message from Node (C) A DAG loop may occur when a node detaches from the DAG and reattaches
on link (C)--(D). Node (D) will consider Node (C) a candidate to a device in its prior sub-DAG that has missed the whole detachment
neighbor and process the RA-DIO message since Node (C) belongs to sequence and kept advertising the original DAG. This may happen in
a different DAG (different DAGID) than Node (D). Node (D) will particular when RA-DIO messages are missed. Use of the DAG sequence
note that Node (C) is in a grounded DAG at rank d+2, and will number can eliminate this type of loop. If the DAG sequence number
begin the process to join the grounded DAG at rank d+3. Node (D) is not in use, the protection is limited (it depends on propagation
will start a DAG Hop timer, logically associated with the grounded of RA-DIO messages during DAG hop timer), and temporary loops might
DAG at Node (C), to coordinate the jump. The DAG Hop timer will occur. RPL will move to eliminate such a loop as soon as a RA-DIO
have a duration proportional to d+2. message is received from a parent that appears to be going down, as
the child has to detach from it immediately. (The alternate choice
of staying attached and following the parent in its fall would have
counted to infinity and led to detach as well).
o Similarly, Node (E) will receive and process a RA-DIO message from Consider node (24) in the DAG Example depicted in Figure 9, and its
Node (A) on link (A)--(E). Node (E) will consider Node (A) a sub-DAG nodes (34), (44), and (45). An example of a DAG loop would
candidate neighbor, will note that Node (A) is in a grounded DAG be if node (24) were to detach from the DAG rooted at (LBR), and
at rank d, and will begin the process to join the grounded DAG at nodes (34) and (45) were to miss the detachment sequence.
rank d+1. Node (E) will start a DAG Hop timer, logically Subsequently, if the link (24)--(45) were to become viable and node
associated with the grounded DAG at Node (A), to coordinate the (24) heard node (45) advertising the DAG rooted at (LBR), a DAG loop
jump. The DAG Hop timer will have a duration proportional to d. (45->34->24->45) may form if node (24) attaches to node (45).
o Node (F) takes no action, for Node (F) has observed nothing new to 3.3.4. DAO Loops
act on.
o Node (E)'s DAG Hop timer for the grounded DAG at Node (A) expires A DAO loop may occur when the parent has a route installed upon
first. Node (E), upon the DAG Hop timer expiry, removes Node (D) receiving and processing a NA-DAO message from a child, but the child
as its parent, thus emptying the DAG parent set for the floating has subsequently cleaned up the state. This loop happens when a no-
DAG, and leaving the floating DAG. Node (E) then jumps to the DAO was missed till a heartbeat cleans up all states. The DAO loop
grounded DAG by entering Node (A) into the set of DAG parents for is not explicitly handled by the current specification. Split
the grounded DAG. Node (E) is now in the grounded DAG at rank horizon, not forwarding a packet back to the node it came from, may
d+1. Node (E), by jumping into the grounded DAG, has created an mitigate the DAO loop in some cases, but does not eliminate it.
inconsistency by changing its DAGID, and will begin to emit RA-DIO
messages more frequently.
o Node (F) will receive and process a RA-DIO message from Node (E). Consider node (24) in the DAG Example depicted in Figure 9. Suppose
Node (F) will observe that Node (E) has changed its DAGID and will node (24) has received a DA from node (34) advertising a destination
directly follow Node (E) into the grounded DAG. Node (F) is now a at node (45). Subsequently, if node (34) tears down the routing
member of the grounded DAG at rank d+2. Note that any additional state for the destination and node (24) did not hear a no-DAO message
sub-DAG of Node (E) would continue to join into the grounded DAG to clean up the routing state, a DAO loop may exist. node (24) will
in this coordinated manner. forward traffic destined for node (45) to node (34), who may then
naively return it into a loop (if split horizon is not in place). A
more complicated DAO loop may result if node (34) instead passes the
traffic to it's sibling, node (33), potentially resulting in a
(24->34->33->23->13->24) loop.
o Node (D) will receive a RA-DIO message from Node (E). Since Node 3.3.5. Sibling Loops
(E) is now in a different DAG, Node (D) may process the RA-DIO
message from Node (E). Node (D) will observe that, via node (E),
it could attach to the grounded DAG at rank d+2. Node (D) will
start another DAG Hop timer, logically associated with the
grounded DAG at Node (E), with a duration proportional to d+1.
Node (D) now is running two DAG hop timers, one which was started
with duration proportional to d+1 and one proportional to d+2.
o Generally, Node (D) will expire the timer associated with the jump Sibling loops occur when a group of siblings keep choosing amongst
to the grounded DAG at node (E) first. Node (D) may then jump to themselves as successors such that a packet does not make forward
the grounded DAG by entering Node (E) into its DAG parent set for progress. The current draft limits those loops to some degree by
the grounded DAG. Node (D) is now in the grounded DAG at rank split horizon (do not send back to the same sibling) and parent
d+2. preference (always prefer parents vs. siblings).
o In this way RPL has coordinated a merge between the more preferred Consider the DAG Example depicted in Figure 9. Suppose that Node
grounded DAG and the less preferred floating DAG, such that the (32) and (34) are reliable neighbors, and thus are siblings. Then,
nodes within the two DAGs come together in a generally ordered in the case where Nodes (22), (23), and (24) are transiently
manner, avoiding the formation of loops in the process. unavailable, and with no other guiding strategy, a sibling loop may
exist, e.g. (33->34->32->33) as the siblings keep choosing amongst
each other in an uncoordinated manner.
3.4. Local and Temporary Routing Decision 3.4. Local and Temporary Routing Decision
Although implementation specific, it is worth noting that a node may Although implementation specific, it is worth noting that a node may
decide to implement some local routing decision based on some decide to implement some local routing decision based on some
metrics, as observed locally or reported in the RA-DIO message. For metrics, as observed locally or reported in the RA-DIO message. For
example, the routing may reflect a set of successors (next-hop), example, the routing may reflect a set of successors (next-hop),
along with various aggregated metrics used to load balance the along with various aggregated metrics used to load balance the
traffic according to some local policy. Such decisions are local and traffic according to some local policy. Such decisions are local and
implementation specific. implementation specific.
skipping to change at page 36, line 29 skipping to change at page 28, line 29
+ + + +
| DAGID | | DAGID |
+ + + +
| | | |
+ + + +
| | | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| sub-option(s)... | sub-option(s)...
+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+
Figure 4: DIO Base Option Figure 1: DIO Base Option
Type: 8-bit unsigned identifying the DIO base option. The suggested Type: 8-bit unsigned identifying the DIO base option. The suggested
value is 140 to be confirmed by the IANA. value is 140 to be confirmed by the IANA.
Length: 8-bit unsigned integer set to 4 when there is no suboption. Length: 8-bit unsigned integer set to 4 when there is no suboption.
The length of the option (including the type and length fields The length of the option (including the type and length fields
and the suboptions) in units of 8 octets. and the suboptions) in units of 8 octets.
Flag Field: Three flags are currently defined: Flag Field: Three flags are currently defined:
skipping to change at page 39, line 10 skipping to change at page 31, line 10
In addition to the minimum options presented in the base option, In addition to the minimum options presented in the base option,
several suboptions are defined for the RA-DIO message: several suboptions are defined for the RA-DIO message:
5.1.1.1.1. Format 5.1.1.1.1. Format
0 1 2 3 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 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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Subopt. Type | Subopt Length | Suboption Data... | Subopt. Type | Subopt Length | Suboption Data...
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Figure 5: DIO Suboption Generic Format Figure 2: DIO Suboption Generic Format
Suboption Type: 8-bit identifier of the type of suboption. When Suboption Type: 8-bit identifier of the type of suboption. When
processing a RA-DIO message containing a suboption for which processing a RA-DIO message containing a suboption for which
the Suboption Type value is not recognized by the receiver, the the Suboption Type value is not recognized by the receiver, the
receiver MUST silently ignore the unrecognized option, continue receiver MUST silently ignore the unrecognized option, continue
to process the following suboption, correctly handling any to process the following suboption, correctly handling any
remaining options in the message. remaining options in the message.
Suboption Length: 8-bit unsigned integer, representing the length in Suboption Length: 8-bit unsigned integer, representing the length in
octets of the suboption, not including the suboption Type and octets of the suboption, not including the suboption Type and
skipping to change at page 39, line 50 skipping to change at page 31, line 50
The Pad1 suboption does not have any alignment requirements. Its The Pad1 suboption does not have any alignment requirements. Its
format is as follows: format is as follows:
0 0
0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7
+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+
| Type = 0 | | Type = 0 |
+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+
Figure 6: Pad 1 Figure 3: Pad 1
NOTE! the format of the Pad1 option is a special case - it has NOTE! the format of the Pad1 option is a special case - it has
neither Option Length nor Option Data fields. neither Option Length nor Option Data fields.
The Pad1 option is used to insert one octet of padding in the RA-DIO The Pad1 option is used to insert one octet of padding in the RA-DIO
message to enable suboptions alignment. If more than one octet of message to enable suboptions alignment. If more than one octet of
padding is required, the PadN option, described next, should be used padding is required, the PadN option, described next, should be used
rather than multiple Pad1 options. rather than multiple Pad1 options.
5.1.1.1.3. PadN 5.1.1.1.3. PadN
The PadN option does not have any alignment requirements. Its format The PadN option does not have any alignment requirements. Its format
is as follows: is as follows:
0 1 0 1
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- - - - - - - - - +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- - - - - - - - -
| Type = 1 | Subopt Length | Subopt Data | Type = 1 | Subopt Length | Subopt Data
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- - - - - - - - - +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- - - - - - - - -
Figure 7: Pad N Figure 4: Pad N
The PadN option is used to insert two or more octets of padding in The PadN option is used to insert two or more octets of padding in
the RA-DIO message to enable suboptions alignment. For N (N > 1) the RA-DIO message to enable suboptions alignment. For N (N > 1)
octets of padding, the Option Length field contains the value N-2, octets of padding, the Option Length field contains the value N-2,
and the Option Data consists of N-2 zero-valued octets. PadN Option and the Option Data consists of N-2 zero-valued octets. PadN Option
data MUST be ignored by the receiver. data MUST be ignored by the receiver.
5.1.1.1.4. DAG Metric Container 5.1.1.1.4. DAG Metric Container
The DAG Metric Container suboption may be aligned as necessary to The DAG Metric Container suboption may be aligned as necessary to
support its contents. Its format is as follows: support its contents. Its format is as follows:
0 1 0 1
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- - - - - - - - - +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- - - - - - - - -
| Type = 2 | Container Len | DAG Metric Data | Type = 2 | Container Len | DAG Metric Data
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- - - - - - - - - +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- - - - - - - - -
Figure 8: DAG Metric Container Figure 5: DAG Metric Container
The DAG Metric Container is used to report aggregated path metrics The DAG Metric Container is used to report aggregated path metrics
along the DAG. The DAG Metric Container may contain a number of along the DAG. The DAG Metric Container may contain a number of
discrete node, link, and aggregate path metrics as chosen by the discrete node, link, and aggregate path metrics as chosen by the
implementer. The Container Length field contains the length in implementer. The Container Length field contains the length in
octets of the DAG Metric Data. The order, content, and coding of the octets of the DAG Metric Data. The order, content, and coding of the
DAG Metric Container data is as specified in DAG Metric Container data is as specified in
[I-D.ietf-roll-routing-metrics]. [I-D.ietf-roll-routing-metrics].
skipping to change at page 41, line 27 skipping to change at page 33, line 27
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type = 3 | Length | Prefix Length |Resvd|Prf|Resvd| | Type = 3 | Length | Prefix Length |Resvd|Prf|Resvd|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Prefix Lifetime | | Prefix Lifetime |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Destination Prefix (Variable Length) | | Destination Prefix (Variable Length) |
. . . .
. . . .
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Figure 9: DAG Destination Prefix Figure 6: DAG Destination Prefix
The Destination Prefix suboption is used when the DAG root, or The Destination Prefix suboption is used when the DAG root, or
another node located inwards along the DAG on the path to the DAG another node located inwards along the DAG on the path to the DAG
root, needs to indicate that it offers connectivity to destination root, needs to indicate that it offers connectivity to destination
prefixes other than the default. This may be useful in cases where prefixes other than the default. This may be useful in cases where
more than one LBR is operating within the LLN and offering more than one LBR is operating within the LLN and offering
connectivity to different administrative domains, e.g. a home network connectivity to different administrative domains, e.g. a home network
and a utility network. In such cases, upon observing the Destination and a utility network. In such cases, upon observing the Destination
Prefixes offered by a particular DAG, a node MAY decide to join Prefixes offered by a particular DAG, a node MAY decide to join
multiple DAGs in support of a particular application. multiple DAGs in support of a particular application.
skipping to change at page 44, line 51 skipping to change at page 36, line 51
their DAG parents in the DAG by using implementation specific policy their DAG parents in the DAG by using implementation specific policy
functions. DAG discovery specifies a set of rules to be followed by functions. DAG discovery specifies a set of rules to be followed by
all implementations in order to ensure interoperation. DAG discovery all implementations in order to ensure interoperation. DAG discovery
also standardizes the format that is used to advertise the most also standardizes the format that is used to advertise the most
common information that is used in order to select DAG parents. common information that is used in order to select DAG parents.
One of these information, the DAG rank, is used by DAG discovery to One of these information, the DAG rank, is used by DAG discovery to
provide loop avoidance even if nodes implement different policies. provide loop avoidance even if nodes implement different policies.
The DAG Rank is computed as specified by the Objective Code Point in The DAG Rank is computed as specified by the Objective Code Point in
use by the DAG, demonstrating the properties described in use by the DAG, demonstrating the properties described in
Section 3.3.1. The rank should be computed in such a way so as to Section 3.2.1.7. The rank should be computed in such a way so as to
provide a comparable basis with other nodes which may not use the provide a comparable basis with other nodes which may not use the
same metric at all. same metric at all.
The DAG discovery procedures take into account a number of factors, The DAG discovery procedures take into account a number of factors,
including: including:
o RPL rules for loop avoidance based on rank o RPL rules for loop avoidance based on rank
o The OCP function o The OCP function
skipping to change at page 51, line 26 skipping to change at page 43, line 26
DIO message. DIO message.
2. Setting C to zero. 2. Setting C to zero.
3. Setting I to I_min. 3. Setting I to I_min.
4. Setting T to a random value as described above. 4. Setting T to a random value as described above.
5. Restarting the trickle timer to expire after a duration T 5. Restarting the trickle timer to expire after a duration T
When an LLN learns about a DAG through a RA-DIO message and makes the When node learns about a DAG through a RA-DIO message and makes the
decision to join it, it initializes the state of the trickle timer by decision to join it, it initializes the state of the trickle timer by
resetting the trickle timer and listening. Each time it hears a resetting the trickle timer and listening. Each time it hears a
consistent RA for this DAG from a DAG parent, it increments C. consistent RA for this DAG from a DAG parent, it MAY increment C.
When the timer fires at time T, the node compares C to the redundancy When the timer fires at time T, the node compares C to the redundancy
constant, DEFAULT_DIO_REDUNDANCY_CONSTANT. If C is less than that constant, DEFAULT_DIO_REDUNDANCY_CONSTANT. If C is less than that
value, the node generates a new RA and broadcasts it. When the value, the node generates a new RA and broadcasts it. When the
communication interval I expires, the node doubles the interval I so communication interval I expires, the node doubles the interval I so
long as it has previously doubled it fewer than I_doubling times, long as it has previously doubled it fewer than I_doubling times,
resets C, and chooses a new T value. resets C, and chooses a new T value.
5.3.4.2. Determination of Inconsistency 5.3.4.2. Determination of Inconsistency
skipping to change at page 62, line 25 skipping to change at page 54, line 25
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Prefix (Variable Length) | | Prefix (Variable Length) |
. . . .
. . . .
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Reverse Route Stack (Variable Length) | | Reverse Route Stack (Variable Length) |
. . . .
. . . .
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Figure 10: The Destination Advertisement Option (DAO) Figure 7: The Destination Advertisement Option (DAO)
Type: 8-bit unsigned identifying the Destination Advertisement Type: 8-bit unsigned identifying the Destination Advertisement
option. IANA had defined the IPv6 Neighbor Discovery Option option. IANA had defined the IPv6 Neighbor Discovery Option
Formats registry. The suggested type value for the Destination Formats registry. The suggested type value for the Destination
Advertisement Option carried within a NA message is 141, to be Advertisement Option carried within a NA message is 141, to be
confirmed by IANA. confirmed by IANA.
Length: 8-bit unsigned integer. The length of the option (including Length: 8-bit unsigned integer. The length of the option (including
the Type and Length fields) in units of 8 octets. the Type and Length fields) in units of 8 octets.
skipping to change at page 73, line 6 skipping to change at page 65, line 6
forwarded via a sibling, then the TTL MAY be decremented more forwarded via a sibling, then the TTL MAY be decremented more
aggressively (by more than one) to limit the impact of possible aggressively (by more than one) to limit the impact of possible
loops. loops.
Note that the chosen successor MUST NOT be the neighbor who was the Note that the chosen successor MUST NOT be the neighbor who was the
predecessor of the packet (split horizon), except in the case where predecessor of the packet (split horizon), except in the case where
it is intended for the packet to change from an inward to an outward it is intended for the packet to change from an inward to an outward
flow, such as switching from DIO routes to DAO routes as the flow, such as switching from DIO routes to DAO routes as the
destination is neared. destination is neared.
5.12.1. Loop Taxonomy
The following is a summary of the sort of loops that may occur within
RPL. This is provided in part as a basis for discussion of loop
detection at forwarding.
5.12.1.1. DAG Loops
A DAG loop may occur when a node detaches from the DAG and reattaches
to a device in its prior sub-DAG that has missed the whole detachment
sequence and kept advertising the original DAG. This may happen in
particular when RA-DIO messages are missed. Use of the DAG sequence
number can eliminate this type of loop. If the DAG sequence number
is not in use, the protection is limited (it depends on propagation
of RA-DIO messages during DAG hop timer), and temporary loops might
occur. RPL will move to eliminate such a loop as soon as a RA-DIO
message is received from a parent that appears to be going down, as
the child has to detach from it immediately. (The alternate choice
of staying attached and following the parent in its fall would have
counted to infinity and led to detach as well).
Consider node (24) in the DAG Example depicted in Figure 12, and its
sub-DAG nodes (34), (44), and (45). An example of a DAG loop would
be if node (24) were to detach from the DAG rooted at (LBR), and
nodes (34) and (45) were to miss the detachment sequence.
Subsequently, if the link (24)--(45) were to become viable and node
(24) heard node (45) advertising the DAG rooted at (LBR), a DAG loop
(45->34->24->45) may form if node (24) attaches to node (45).
5.12.1.2. DAO Loops
A DAO loop may occur when the parent has a route installed upon
receiving and processing a NA-DAO message from a child, but the child
has subsequently cleaned up the state. This loop happens when a no-
DAO was missed till a heartbeat cleans up all states. The DAO loop
is not explicitly handled by the current specification. Split
horizon, not forwarding a packet back to the node it came from, may
mitigate the DAO loop in some cases, but does not eliminate it.
Consider node (24) in the DAG Example depicted in Figure 12. Suppose
node (24) has received a DA from node (34) advertising a destination
at node (45). Subsequently, if node (34) tears down the routing
state for the destination and node (24) did not hear a no-DAO message
to clean up the routing state, a DAO loop may exist. node (24) will
forward traffic destined for node (45) to node (34), who may then
naively return it into a loop (if split horizon is not in place). A
more complicated DAO loop may result if node (34) instead passes the
traffic to it's sibling, node (33), potentially resulting in a
(24->34->33->23->13->24) loop.
5.12.1.3. Sibling Loops
Sibling loops occur when a group of siblings keep choosing amongst
themselves as successors such that a packet does not make forward
progress. The current draft limits those loops to some degree by
split horizon (do not send back to the same sibling) and parent
preference (always prefer parents vs. siblings).
Consider the DAG Example depicted in Figure 12. Suppose that Node
(32) and (34) are reliable neighbors, and thus are siblings. Then,
in the case where Nodes (22), (23), and (24) are transiently
unavailable, and with no other guiding strategy, a sibling loop may
exist, e.g. (33->34->32->33) as the siblings keep choosing amongst
each other in an uncoordinated manner.
6. RPL Variables 6. RPL Variables
DIO Timer One instance per DAG that a node is a member of. Expiry DIO Timer One instance per DAG that a node is a member of. Expiry
triggers RA-DIO message transmission. Trickle timer with triggers RA-DIO message transmission. Trickle timer with
variable interval in [0, variable interval in [0,
DIOIntervalMin..2^DIOIntervalDoublings]. See Section 5.3.4 DIOIntervalMin..2^DIOIntervalDoublings]. See Section 5.3.4
DAG Hop Timer Up to one instance per candidate DAG parent in the DAG Hop Timer Up to one instance per candidate DAG parent in the
`Held-Up' state per DAG that a node is going to jump to. `Held-Up' state per DAG that a node is going to jump to.
Expiry triggers candidate DAG parent to become a DAG parent in Expiry triggers candidate DAG parent to become a DAG parent in
skipping to change at page 76, line 10 skipping to change at page 66, line 37
Furthermore, the implementation SHOULD to allow configuring whether Furthermore, the implementation SHOULD to allow configuring whether
or not the node should start sending an RS message as an initial or not the node should start sending an RS message as an initial
probe for nearby DAGs, or should simply wait until it received RA probe for nearby DAGs, or should simply wait until it received RA
messages from other nodes that are part of existing DAGs. messages from other nodes that are part of existing DAGs.
7.1.2. DIO Base option 7.1.2. DIO Base option
RPL specifies a number of protocol parameters. RPL specifies a number of protocol parameters.
A RPL implementation SHOULD allow configuring the following routing A RPL implementation SHOULD allow configuring the following routing
protocol parameters: protocol parameters, which are further described in Section 5.1.1:
DAGPreference: 8-bit unsigned integer set by the DAG root to its DAGPreference
preference and unchanged at propagation.
NodePreference: The administrative preference of that LLN Node. NodePreference
DAGDelay: 16-bit unsigned integer set by the DAG root indicating the DAGDelay
delay before changing the DAG configuration,
DIOIntervalDoublings: 8-bit unsigned integer. Configured on the DAG DIOIntervalDoublings
root and used to configure the trickle timer governing when RA-
DIO messages should be sent within the DAG.
DIOIntervalMin: 8-bit unsigned integer. Configured on the DAG root DIOIntervalMin:
and used to configure the trickle timer governing when RA-DIO
messages should be sent within the DAG. The minimum configured
interval for the RA-DIO trickle timer in units of ms is
2^DIOIntervalMin (e.g. a DIOIntervalMin value of 16ms is
expressed as 4).
DAGObjectiveCodePoint The DAG Objective Code Point is used to DAGObjectiveCodePoint
indicate the cost metrics, objective functions, and methods of
computation and comparison for DAGRank in use in the DAG. The
DAG OCP is set by the DAG root.
PathDigest: 32-bit unsigned integer CRC, updated by each LLN Node. PathDigest
This is the result of a CRC-32c computation on a bit string
obtained by appending the received value and the ordered set of
DAG parents at the LLN Node. DAG roots use a 'previous value'
of zeroes to initially set the PathDigest.
DAGID: 128-bit unsigned integer which uniquely identify a DAG. This DAGID
value is set by the DAG root. The global IPv6 address of the
DAG root can be used.
Destination Prefixes List of advertised destinations Destination Prefixes
DAG Root behavior: In some cases, a node may not want to permanently DAG Root behavior: In some cases, a node may not want to permanently
act as a DAG root if it cannot join a grounded DAG. For act as a DAG root if it cannot join a grounded DAG. For
example a battery-operated node may not want to act as a DAG example a battery-operated node may not want to act as a DAG
root for a long period of time. Thus a RPL implementation MAY root for a long period of time. Thus a RPL implementation MAY
support the ability to configure whether or not a node could support the ability to configure whether or not a node could
act as a DAG root for a configured period of time. act as a DAG root for a configured period of time.
DAG Hop Timer: A RPL implementation MUST provide the ability to DAG Hop Timer: A RPL implementation MUST provide the ability to
configure the value of the DAG Hop Timer, expressed in ms. configure the value of the DAG Hop Timer, expressed in ms.
skipping to change at page 77, line 22 skipping to change at page 67, line 36
suppressed, to be invoked if the DAG parent set becomes empty. suppressed, to be invoked if the DAG parent set becomes empty.
7.1.3. Trickle Timers 7.1.3. Trickle Timers
A RPL implementation makes use of trickle timer to govern the sending A RPL implementation makes use of trickle timer to govern the sending
of RA-DIO message. Such an algorithm is determined a by a set of of RA-DIO message. Such an algorithm is determined a by a set of
configurable parameters that are then advertised by the DAG root configurable parameters that are then advertised by the DAG root
along the DAG in RA-DIO messages. along the DAG in RA-DIO messages.
For each DAG, a RPL implementation MUST allow for the monitoring of For each DAG, a RPL implementation MUST allow for the monitoring of
the following parameters: the following parameters, further described in Section 5.3.4:
I: The current length of the communication interval I
T: A timer with a duration set to a random value in the range T
[I/2, I]
C: Redundancy Counter C
I_min: The smallest communication interval in milliseconds. This I_min
value is learned from the RA-DIO message as
(2^DIOIntervalMin)ms. The default value is
DEFAULT_DIO_INTERVAL_MIN.
I_doublings: The number of times I_min should be doubled before I_doublings:
maintaining a constant rate, i.e. I_max = I_min *
2^I_doublings. This value is learned from the RA-DIO message
as DIOIntervalDoublings. The default value is
DEFAULT_DIO_INTERVAL_DOUBLINGS.
A RPL implementation SHOULD provide a command (for example via API, A RPL implementation SHOULD provide a command (for example via API,
CLI, or SNMP MIB) whereby any procedure that detects an inconsistency CLI, or SNMP MIB) whereby any procedure that detects an inconsistency
may cause the trickle timer to reset. may cause the trickle timer to reset.
7.1.4. DAG Heartbeat 7.1.4. DAG Heartbeat
A RPL implementation may allow by configuration at the DAG root to A RPL implementation may allow by configuration at the DAG root to
refresh the DAG states by updating the DAGSequenceNumber. A RPL refresh the DAG states by updating the DAGSequenceNumber. A RPL
implementation SHOULD allow configuring whether or not periodic or implementation SHOULD allow configuring whether or not periodic or
skipping to change at page 87, line 7 skipping to change at page 77, line 7
Networks", RFC 5548, May 2009. Networks", RFC 5548, May 2009.
Appendix A. Deferred Requirements Appendix A. Deferred Requirements
NOTE: RPL is still a work in progress. At this time there remain NOTE: RPL is still a work in progress. At this time there remain
several unsatisfied application requirements, but these are to be several unsatisfied application requirements, but these are to be
addressed as RPL is further specified. addressed as RPL is further specified.
Appendix B. Examples Appendix B. Examples
Consider the example LLN physical topology in Figure 11. In this Consider the example LLN physical topology in Figure 8. In this
example the links depicted are all usable L2 links. Suppose that all example the links depicted are all usable L2 links. Suppose that all
links are equally usable, and that the implementation specific policy links are equally usable, and that the implementation specific policy
function is simply to minimize hops. This LLN physical topology then function is simply to minimize hops. This LLN physical topology then
yields the DAG depicted in Figure 12, where the links depicted are yields the DAG depicted in Figure 9, where the links depicted are the
the edges toward DAG parents. This topology includes one DAG, rooted edges toward DAG parents. This topology includes one DAG, rooted by
by an LBR node (LBR) at rank 1. The LBR node will issue RAs an LBR node (LBR) at rank 1. The LBR node will issue RAs containing
containing DIO, as governed by a trickle timer. Nodes (11), (12), DIO, as governed by a trickle timer. Nodes (11), (12), (13), have
(13), have selected (LBR) as their only parent, attached to the DAG selected (LBR) as their only parent, attached to the DAG at rank 2,
at rank 2, and periodically advertise RA-DIO multicasts. Node (22) and periodically advertise RA-DIO multicasts. Node (22) has selected
has selected (11) and (12) in its DAG parent set, and advertises (11) and (12) in its DAG parent set, and advertises itself at rank 3.
itself at rank 3. Node (22) thus has a set of DAG parents {(11), Node (22) thus has a set of DAG parents {(11), (12)} and siblings
(12)} and siblings {((21), (23)}. {((21), (23)}.
(LBR) (LBR)
/ | \ / | \
.---` | `----. .---` | `----.
/ | \ / | \
(11)------(12)------(13) (11)------(12)------(13)
| \ | \ | \ | \ | \ | \
| `----. | `----. | `----. | `----. | `----. | `----.
| \| \| \ | \| \| \
(21)------(22)------(23) (24) (21)------(22)------(23) (24)
skipping to change at page 87, line 50 skipping to change at page 77, line 50
/ / / | \| \ / / / | \| \
(51)------(52)------(53)------(54)------(55)------(56) (51)------(52)------(53)------(54)------(55)------(56)
Note that the links depicted represent the usable L2 connectivity Note that the links depicted represent the usable L2 connectivity
available in the LLN. For example, Node (31) can communicate available in the LLN. For example, Node (31) can communicate
directly with its neighbors, Nodes (21), (22), (32), and (41). Node directly with its neighbors, Nodes (21), (22), (32), and (41). Node
(31) cannot communicate directly with any other nodes, e.g. (33), (31) cannot communicate directly with any other nodes, e.g. (33),
(23), (42). In this example these links offer bidirectional (23), (42). In this example these links offer bidirectional
communication, and `bad' links are not depicted. communication, and `bad' links are not depicted.
Figure 11: Example LLN Topology Figure 8: Example LLN Topology
(LBR) (LBR)
/ | \ / | \
.---` | `----. .---` | `----.
/ | \ / | \
(11) (12) (13) (11) (12) (13)
| \ | \ | \ | \ | \ | \
| `----. | `----. | `----. | `----. | `----. | `----.
| \| \| \ | \| \| \
(21) (22) (23) (24) (21) (22) (23) (24)
| /| /| | | /| /| |
skipping to change at page 88, line 27 skipping to change at page 78, line 27
| /| \ | \ | \ | /| \ | \ | \
| .----` | `----. | `----. | `----. | .----` | `----. | `----. | `----.
| / | \| \| \ | / | \| \| \
.--------(41) (42) (43) (44) (45) .--------(41) (42) (43) (44) (45)
/ / /| \ | \ / / /| \ | \
.----` .----` .----` | `----. | `----. .----` .----` .----` | `----. | `----.
/ / / | \| \ / / / | \| \
(51) (52) (53) (54) (55) (56) (51) (52) (53) (54) (55) (56)
Note that the links depicted represent directed links in the DAG Note that the links depicted represent directed links in the DAG
overlaid on top of the physical topology depicted in Figure 11. As overlaid on top of the physical topology depicted in Figure 8. As
such, the depicted edges represent the relationship between nodes and such, the depicted edges represent the relationship between nodes and
their DAG parents, wherein all depicted edges are directed and their DAG parents, wherein all depicted edges are directed and
oriented `up' on the page toward the DAG root (LBR). The DAG may oriented `up' on the page toward the DAG root (LBR). The DAG may
provide default routes within the LLN, and serves as the foundation provide default routes within the LLN, and serves as the foundation
on which RPL builds further routing structure, e.g. through the on which RPL builds further routing structure, e.g. through the
destination advertisement mechanism. destination advertisement mechanism.
Figure 12: Example DAG Figure 9: Example DAG
B.1. Moving Down a DAG B.1. Moving Down a DAG
Consider node (56) in the example of Figure 11. In the unmodified Consider node (56) in the example of Figure 8. In the unmodified
example, node (56) is at rank 6 with one DAG parent, {(43)}, and one example, node (56) is at rank 6 with one DAG parent, {(43)}, and one
sibling (55). Suppose, for example, that node (56) wished to expand sibling (55). Suppose, for example, that node (56) wished to expand
its DAG parent set to contain node (55), as {(43), (55)}. Such a its DAG parent set to contain node (55), as {(43), (55)}. Such a
change would require node (56) to detach from the DAG, to defer change would require node (56) to detach from the DAG, to defer
reattachment until a loop avoidance algorithm has completed, and to reattachment until a loop avoidance algorithm has completed, and to
then reattach to the DAG with {(43), (55)} as it's DAG parents. When then reattach to the DAG with {(43), (55)} as it's DAG parents. When
node (56) detaches from the DAG, it is able to act as the root of its node (56) detaches from the DAG, it is able to act as the root of its
own floating DAG and establish its frozen sub-DAG (which is empty). own floating DAG and establish its frozen sub-DAG (which is empty).
Node (56) can then observe that Node (55) is still attached to the Node (56) can then observe that Node (55) is still attached to the
original DAG, that its sequence number is able to increment, and original DAG, that its sequence number is able to increment, and
deduce that Node (55) is safely not behind Node (56). There is then deduce that Node (55) is safely not behind Node (56). There is then
little change for a loop, and Node (56) may safely reattach to the little change for a loop, and Node (56) may safely reattach to the
DAG, with parents {(43), (55)}. At reattachment time, node (56) DAG, with parents {(43), (55)}. At reattachment time, node (56)
would present itself with a rank deeper than that of its deepest DAG would present itself with a rank deeper than that of its deepest DAG
parent (node (55) at rank 6), rank 7. parent (node (55) at rank 6), rank 7.
B.2. Link Removed B.2. Link Removed
Consider the example of Figure 11 when link (13)-(24) goes down. Consider the example of Figure 8 when link (13)-(24) goes down.
o Node (24) will detach and become the root of its own floating DAG o Node (24) will detach and become the root of its own floating DAG
o Node (34) will learn that its DAG parent is now part of its own o Node (34) will learn that its DAG parent is now part of its own
floating DAG, will consider that it can remain a part of the DAG floating DAG, will consider that it can remain a part of the DAG
rooted at node (LBR) via node (33), and will initiate procedures rooted at node (LBR) via node (33), and will initiate procedures
to detach from DAG (LBR) in order to re-attach at a lower rank. to detach from DAG (LBR) in order to re-attach at a lower rank.
o Node (45) will similarly make preparations to remain attached to o Node (45) will similarly make preparations to remain attached to
the DAG rooted at (LBR) by detaching from Node (34) and re- the DAG rooted at (LBR) by detaching from Node (34) and re-
skipping to change at page 89, line 40 skipping to change at page 79, line 40
o Node (45) may now anyway add node (44) to its set of DAG parents, o Node (45) may now anyway add node (44) to its set of DAG parents,
as such an addition does not require any modification to its own as such an addition does not require any modification to its own
rank. rank.
o Node (24) will observe that it may reattach to the DAG rooted at o Node (24) will observe that it may reattach to the DAG rooted at
node (LBR) by selecting node (34) as its DAG parent, thus node (LBR) by selecting node (34) as its DAG parent, thus
reversing the relationship that existed in the initial state. reversing the relationship that existed in the initial state.
B.3. Link Added B.3. Link Added
Consider the example of Figure 11 when link (12)-(42) appears. Consider the example of Figure 8 when link (12)-(42) appears.
o Node (42) will see a chance to get closer to the LBR by adding o Node (42) will see a chance to get closer to the LBR by adding
(12) to its set of DAG parents, {(32), (12)} (12) to its set of DAG parents, {(32), (12)}
o Node (42) may be content to leave its advertised rank at 5, o Node (42) may be content to leave its advertised rank at 5,
reflecting a rank deeper than its deepest parent (32). reflecting a rank deeper than its deepest parent (32).
o Node (42) may now choose to remain where it is, with two parents o Node (42) may now choose to remain where it is, with two parents
{(12), (32)}. Should there be a reason for Node (42) to evict {(12), (32)}. Should there be a reason for Node (42) to evict
Node (32) from its set of DAG parents, Node (42) would then Node (32) from its set of DAG parents, Node (42) would then
advertise itself at rank 2, thus moving up the DAG. In this case, advertise itself at rank 2, thus moving up the DAG. In this case,
Node (53), (54), and (55) may similarly follow and advertise Node (53), (54), and (55) may similarly follow and advertise
themselves at rank 3. themselves at rank 3.
B.4. Node Removed B.4. Node Removed
Consider the example of Figure 11 when node (41) disappears. Consider the example of Figure 8 when node (41) disappears.
o Node (51) and (52) will now have empty DAG parent sets and be o Node (51) and (52) will now have empty DAG parent sets and be
detached from the DAG rooted by (LBR), advertising themselves as detached from the DAG rooted by (LBR), advertising themselves as
the root of their own floating DAGs. the root of their own floating DAGs.
o Node (52) would observe a chance to reattach to the DAG rooted at o Node (52) would observe a chance to reattach to the DAG rooted at
(LBR) by adding Node (53) to its set of DAG parents, after an (LBR) by adding Node (53) to its set of DAG parents, after an
appropriate delay to avoid creating loops. Node (52) will then appropriate delay to avoid creating loops. Node (52) will then
advertise itself in the DAG rooted at (LBR) at rank 7. advertise itself in the DAG rooted at (LBR) at rank 7.
o Node (51) will then be able to reattach to the DAG rooted at (LBR) o Node (51) will then be able to reattach to the DAG rooted at (LBR)
by adding Node (52) to its set of DAG parents and advertising by adding Node (52) to its set of DAG parents and advertising
itself at rank 8. itself at rank 8.
B.5. New LBR Added B.5. New LBR Added
Consider the example of Figure 11 when a new LBR, (LBR2) appears, Consider the example of Figure 8 when a new LBR, (LBR2) appears, with
with connectivity (LBR2)-(52), (LBR2)-(53). connectivity (LBR2)-(52), (LBR2)-(53).
o Nodes (52) and Node (53) will see a chance to join a new DAG o Nodes (52) and Node (53) will see a chance to join a new DAG
rooted at (LBR2) with a rank of 2. Node (52) and (53) may take rooted at (LBR2) with a rank of 2. Node (52) and (53) may take
this chance immediately, as there is no risk of forming loops when this chance immediately, as there is no risk of forming loops when
joining a DAG that has never before been encountered. Note that joining a DAG that has never before been encountered. Note that
the nodes may choose to join the new DAG rooted at (LBR2) if and the nodes may choose to join the new DAG rooted at (LBR2) if and
only if (LBR2) offers more optimum properties in line with the only if (LBR2) offers more optimum properties in line with the
implementation specific local policy. implementation specific local policy.
o Nodes (52) and (53) begin to send RA-DIO messages advertising o Nodes (52) and (53) begin to send RA-DIO messages advertising
skipping to change at page 91, line 7 skipping to change at page 81, line 7
o Node (55) may then join the new DAG at rank 4, possibly to get o Node (55) may then join the new DAG at rank 4, possibly to get
closer to the DAG root. closer to the DAG root.
o The remaining nodes may choose to remain in their current o The remaining nodes may choose to remain in their current
positions within the DAG rooted at node (LBR), since there is no positions within the DAG rooted at node (LBR), since there is no
clear advantage to be gained by moving to DAG (LBR2). clear advantage to be gained by moving to DAG (LBR2).
B.6. Destination Advertisement B.6. Destination Advertisement
Consider the example DAG depicted in Figure 12. Suppose that Nodes Consider the example DAG depicted in Figure 9. Suppose that Nodes
(22) and (32) are unable to record routing state. Suppose that Node (22) and (32) are unable to record routing state. Suppose that Node
(42) is able to perform prefix aggregation on behalf of Nodes (53), (42) is able to perform prefix aggregation on behalf of Nodes (53),
(54), and (55). (54), and (55).
o Node (53) would send a NA-DAO message to Node (42), indicating the o Node (53) would send a NA-DAO message to Node (42), indicating the
availability of destination (53). availability of destination (53).
o Node (54) and Node (55) would similarly send NA-DAO messages to o Node (54) and Node (55) would similarly send NA-DAO messages to
Node (42) indicating their own destinations. Node (42) indicating their own destinations.
skipping to change at page 92, line 5 skipping to change at page 82, line 5
source route to (32) source route to (32)
* Destination (42') is available via Node (22) and the piecewise * Destination (42') is available via Node (22) and the piecewise
source route to (32), (42'). source route to (32), (42').
o Node (12) sends NA-DAO messages to (LBR), allowing (LBR) to learn o Node (12) sends NA-DAO messages to (LBR), allowing (LBR) to learn
routes to the destinations (12), (22), (32), and (42'). (42), routes to the destinations (12), (22), (32), and (42'). (42),
(53), (54), and (55) are available via the aggregation (42'). It (53), (54), and (55) are available via the aggregation (42'). It
is not necessary for Node (12) to propagate the piecewise source is not necessary for Node (12) to propagate the piecewise source
routes to (LBR). routes to (LBR).
B.7. Example: DAG Parent Selection
For example, suppose that a node (N) is not attached to any DAG, and
that it is in range of nodes (A), (B), (C), (D), and (E). Let all
nodes be configured to use an OCP which defines a policy such that
ETX is to be minimized and paths with the attribute `Blue' should be
avoided. Let the rank computation indicated by the OCP simply
reflect the ETX aggregated along the path. Let the links between
node (N) and its neighbors (A-E) all have an ETX of 1 (which is
learned by node (N) through some implementation specific method).
Let node (N) be configured to send IPv6 Router Solicitation (RS)
messages to probe for nearby DAGs.
o Node (N) transmits a Router Solicitation.
o Node (B) responds. Node (N) investigates the RA-DIO message, and
learns that Node (B) is a member of DAGID 1 at rank 4, and not
`Blue'. Node (N) takes note of this, but is not yet confident.
o Similarly, Node (N) hears from Node (A) at rank 9, Node (C) at
rank 5, and Node (E) at rank 4.
o Node (D) responds. Node (D) has a RA-DIO message that indicates
that it is a member of DAGID 1 at rank 2, but it carries the
attribute `Blue'. Node (N)'s policy function rejects Node (D),
and no further consideration is given.
o This process continues until Node (N), based on implementation
specific policy, builds up enough confidence to trigger a decision
to join DAGID 1. Let Node (N) determine its most preferred parent
to be Node (E).
o Node (N) adds Node (E) (rank 4) to its set of DAG parents for
DAGID 1. Following the mechanisms specified by the OCP, and given
that the ETX is 1 for the link between (N) and (E), Node (N) is
now at rank 5 in DAGID 1.
o Node (N) adds Node (B) (rank 4) to its set of DAG parents for
DAGID 1.
o Node (N) is a sibling of Node (C), both are at rank 5.
o Node (N) may now forward traffic intended for the default
destination inward along DAGID 1 via nodes (B) and (E). In some
cases, e.g. if nodes (B) and (E) are tried and fail, node (N) may
also choose to forward traffic to its sibling node (C), without
making inward progress but with the intention that node (C) or a
following successor can make inward progress. Should Node (C) not
have a viable parent, it should never send the packet back to Node
(N) (to avoid a 2-node loop).
B.8. Example: DAG Maintenance
: : :
: : :
(A) (A) (A)
|\ | |
| `-----. | |
| \ | |
(B) (C) (B) (C) (B)
| | \
| | `-----.
| | \
(D) (D) (C)
|
|
|
(D)
-1- -2- -3-
Figure 10: DAG Maintenance
Consider the example depicted in Figure 10-1. In this example, Node
(A) is attached to a DAG at some rank d. Node (A) is a DAG parent of
Nodes (B) and (C). Node (C) is a DAG parent of Node (D). There is
also an undirected sibling link between Nodes (B) and (C).
In this example, Node (C) may safely forward to Node (A) without
creating a loop. Node (C) may not safely forward to Node (D),
contained within it's own sub-DAG, without creating a loop. Node (C)
may forward to Node (B) in some cases, e.g. the link (C)->(A) is
temporarily unavailable, but with some chance of creating a loop
(e.g. if multiple nodes in a set of siblings start forwarding
`sideways' in a cycle) and requiring the intervention of additional
mechanisms to detect and break the loop.
Consider the case where Node (C) hears a RA-DIO message from a Node
(Z) at a lesser rank and superior position in the DAG than node (A).
Node (C) may safely undergo the process to evict node (A) from its
DAG parent set and attach directly to Node (Z) without creating a
loop, because its rank will decrease.
Now consider the case where the link (C)->(A) becomes nonviable, and
node (C) must move to a deeper rank within the DAG:
o Node (C) must first detach from the DAG by removing Node (A) from
its DAG parent set, leaving an empty DAG parent set. Node (C)
becomes the root of its own floating, less preferred, DAG.
o Node (D), hearing a modified RA-DIO message from Node (C), follows
Node (C) into the floating DAG. This is depicted in Figure 10-2.
In general, any node with no other options in the sub-DAG of Node
(C) will follow Node (C) into the floating DAG, maintaining the
structure of the sub-DAG.
o Node (C) hears a RA-DIO message from Node (B) and determines it is
able to rejoin the grounded DAG by reattaching at a deeper rank to
Node (B). Node (C) starts a DAG Hop timer to coordinate this
move.
o The timer expires and Node (C) adds Node (B) to its DAG parent
set. Node (C) has now safely moved deeper within the grounded DAG
without creating any loops. Node (D), and any other sub-DAG of
Node (C), will hear the modified RA-DIO message sourced from Node
(C) and follow Node (C) in a coordinated manner to reattach to the
grounded DAG. The final DAG is depicted in Figure 10-3
B.9. Example: Greedy Parent Selection and Instability
(A) (A) (A)
|\ |\ |\
| `-----. | `-----. | `-----.
| \ | \ | \
(B) (C) (B) \ | (C)
\ | | /
`-----. | | .-----`
\| |/
(C) (B)
-1- -2- -3-
Figure 11: Greedy DAG Parent Selection
Consider the example depicted in Figure 11. A DAG is depicted in 3
different configurations. A usable link between (B) and (C) exists
in all 3 configurations. In Figure 11-1, Node (A) is a DAG parent
for Nodes (B) and (C), and (B)--(C) is a sibling link. In
Figure 11-2, Node (A) is a DAG parent for Nodes (B) and (C), and Node
(B) is also a DAG parent for Node (C). In Figure 11-3, Node (A) is a
DAG parent for Nodes (B) and (C), and Node (C) is also a DAG parent
for Node (B).
If a RPL node is too greedy, in that it attempts to optimize for an
additional number of parents beyond its preferred parent, then an
instability can result. Consider the DAG illustrated in Figure 11-1.
In this example, Nodes (B) and (C) may most prefer Node (A) as a DAG
parent, but are operating under the greedy condition that will try to
optimize for 2 parents.
When the preferred parent selection causes a node to have only one
parent and no siblings, the node may decide to insert itself at a
slightly higher rank in order to have at least one sibling and thus
an alternate forwarding solution. This does not deprive other nodes
of a forwarding solution and this is considered acceptable
greediness.
o Let Figure 11-1 be the initial condition.
o Suppose Node (C) first is able to leave the DAG and rejoin at a
lower rank, taking both Nodes (A) and (B) as DAG parents as
depicted in Figure 11-2. Now Node (C) is deeper than both Nodes
(A) and (B), and Node (C) is satisfied to have 2 DAG parents.
o Suppose Node (B), in its greediness, is willing to receive and
process a RA-DIO message from Node (C) (against the rules of RPL),
and then Node (B) leaves the DAG and rejoins at a lower rank,
taking both Nodes (A) and (C) as DAG parents. Now Node (B) is
deeper than both Nodes (A) and (C) and is satisfied with 2 DAG
parents.
o Then Node (C), because it is also greedy, will leave and rejoin
deeper, to again get 2 parents and have a lower rank then both of
them.
o Next Node (B) will again leave and rejoin deeper, to again get 2
parents
o And again Node (C) leaves and rejoins deeper...
o The process will repeat, and the DAG will oscillate between
Figure 11-2 and Figure 11-3 until the nodes count to infinity and
restart the cycle again.
o This cycle can be averted through mechanisms in RPL:
* Nodes (B) and (C) stay at a rank sufficient to attach to their
most preferred parent (A) and don't go for any deeper (worse)
alternate parents (Nodes are not greedy)
* Nodes (B) and (C) do not process RA-DIO messages from nodes
deeper than themselves (because such nodes are possibly in
their own sub-DAGs)
B.10. Example: DAG Merge
:
:
(A) (D)
| |
| |
| |
(B) (E)
| |
| |
| |
(C) (F)
Figure 12: Merging DAGs
Consider the example depicted in Figure 12. Nodes (A), (B), and (C)
are part of some larger grounded DAG, where Node (A) is at a rank of
d, Node (B) at d+1, and Node (C) at d+2. The DAG comprised of Nodes
(D), (E), and (F) is a floating, less preferred, DAG, with Node (D)
as the DAG root. This floating DAG may have been formed, for
example, in the absence of a grounded DAG or when Node (D) had to
detach from a grounded DAG and (E) and (F) followed. All nodes are
using compatible objective code points.
Nodes (D), (E), and (F) would rather join the more preferred grounded
DAG if they are able than to remain in the less preferred floating
DAG.
Next, let links (C)--(D) and (A)--(E) become viable. The following
sequence of events may then occur in a typical case:
o Node (D) will receive and process a RA-DIO message from Node (C)
on link (C)--(D). Node (D) will consider Node (C) a candidate
neighbor and process the RA-DIO message since Node (C) belongs to
a different DAG (different DAGID) than Node (D). Node (D) will
note that Node (C) is in a grounded DAG at rank d+2, and will
begin the process to join the grounded DAG at rank d+3. Node (D)
will start a DAG Hop timer, logically associated with the grounded
DAG at Node (C), to coordinate the jump. The DAG Hop timer will
have a duration proportional to d+2.
o Similarly, Node (E) will receive and process a RA-DIO message from
Node (A) on link (A)--(E). Node (E) will consider Node (A) a
candidate neighbor, will note that Node (A) is in a grounded DAG
at rank d, and will begin the process to join the grounded DAG at
rank d+1. Node (E) will start a DAG Hop timer, logically
associated with the grounded DAG at Node (A), to coordinate the
jump. The DAG Hop timer will have a duration proportional to d.
o Node (F) takes no action, for Node (F) has observed nothing new to
act on.
o Node (E)'s DAG Hop timer for the grounded DAG at Node (A) expires
first. Node (E), upon the DAG Hop timer expiry, removes Node (D)
as its parent, thus emptying the DAG parent set for the floating
DAG, and leaving the floating DAG. Node (E) then jumps to the
grounded DAG by entering Node (A) into the set of DAG parents for
the grounded DAG. Node (E) is now in the grounded DAG at rank
d+1. Node (E), by jumping into the grounded DAG, has created an
inconsistency by changing its DAGID, and will begin to emit RA-DIO
messages more frequently.
o Node (F) will receive and process a RA-DIO message from Node (E).
Node (F) will observe that Node (E) has changed its DAGID and will
directly follow Node (E) into the grounded DAG. Node (F) is now a
member of the grounded DAG at rank d+2. Note that any additional
sub-DAG of Node (E) would continue to join into the grounded DAG
in this coordinated manner.
o Node (D) will receive a RA-DIO message from Node (E). Since Node
(E) is now in a different DAG, Node (D) may process the RA-DIO
message from Node (E). Node (D) will observe that, via node (E),
it could attach to the grounded DAG at rank d+2. Node (D) will
start another DAG Hop timer, logically associated with the
grounded DAG at Node (E), with a duration proportional to d+1.
Node (D) now is running two DAG hop timers, one which was started
with duration proportional to d+1 and one proportional to d+2.
o Generally, Node (D) will expire the timer associated with the jump
to the grounded DAG at node (E) first. Node (D) may then jump to
the grounded DAG by entering Node (E) into its DAG parent set for
the grounded DAG. Node (D) is now in the grounded DAG at rank
d+2.
o In this way RPL has coordinated a merge between the more preferred
grounded DAG and the less preferred floating DAG, such that the
nodes within the two DAGs come together in a generally ordered
manner, avoiding the formation of loops in the process.
Appendix C. Additional Examples Appendix C. Additional Examples
Consider the expanded example LLN physical topology in Figure 13. In Consider the expanded example LLN physical topology in Figure 13. In
this example an additional LBR is added. Suppose that all nodes are this example an additional LBR is added. Suppose that all nodes are
configured with an implementation specific policy function that aims configured with an implementation specific policy function that aims
to minimize the number of hops, and that both LBRs are configured to to minimize the number of hops, and that both LBRs are configured to
root different DAGIDs. We may now walk through the formation of the root different DAGIDs. We may now walk through the formation of the
two DAGs. two DAGs.
(LBR) (LBR2) (LBR) (LBR2)
 End of changes. 113 change blocks. 
962 lines changed or deleted 808 lines changed or added

This html diff was produced by rfcdiff 1.37a. The latest version is available from http://tools.ietf.org/tools/rfcdiff/