draft-ietf-roll-p2p-rpl-03.txt   draft-ietf-roll-p2p-rpl-04.txt 
Internet Engineering Task Force M. Goyal, Ed. Internet Engineering Task Force M. Goyal, Ed.
Internet-Draft University of Wisconsin Internet-Draft University of Wisconsin
Intended status: Experimental Milwaukee Intended status: Experimental Milwaukee
Expires: November 14, 2011 E. Baccelli Expires: January 12, 2012 E. Baccelli
M. Philipp
INRIA INRIA
A. Brandt A. Brandt
Sigma Designs Sigma Designs
R. Cragie R. Cragie
Gridmerge Ltd Gridmerge Ltd
J. Martocci J. Martocci
Johnson Controls Johnson Controls
May 13, 2011 July 11, 2011
Reactive Discovery of Point-to-Point Routes in Low Power and Lossy Reactive Discovery of Point-to-Point Routes in Low Power and Lossy
Networks Networks
draft-ietf-roll-p2p-rpl-03 draft-ietf-roll-p2p-rpl-04
Abstract Abstract
Point to point (P2P) communication between arbitrary IPv6 routers and Point to point (P2P) communication between arbitrary IPv6 routers in
hosts in a Low power and Lossy Network (LLN) is a key requirement for a Low power and Lossy Network (LLN) is a key requirement for many
many applications. RPL, the IPv6 Routing Protocol for LLNs, applications. RPL, the IPv6 Routing Protocol for LLNs, constrains
constrains the LLN topology to a Directed Acyclic Graph (DAG) and the LLN topology to a Directed Acyclic Graph (DAG) and requires the
requires the P2P routing to take place along the DAG links. Such P2P P2P routing to take place along the DAG links. Such P2P routes may
routes may be suboptimal and may lead to traffic congestion near the be suboptimal and may lead to traffic congestion near the DAG root.
DAG root. This document specifies a P2P route discovery mechanism, This document specifies a P2P route discovery mechanism,
complementary to the RPL base functionality. This mechanism allows complementary to the RPL base functionality. This mechanism allows
an IPv6 router or host to discover and establish, on demand, one or an IPv6 router to discover and establish, on demand, a route to
more routes to another IPv6 router or host in the LLN such that the another IPv6 router in the LLN such that the discovered route meets
discovered routes meet specified constraints. specified constraints.
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). Note that other groups may also distribute Task Force (IETF). Note that other groups may also distribute
working documents as Internet-Drafts. The list of current Internet- working documents as Internet-Drafts. The list of current Internet-
Drafts is at http://datatracker.ietf.org/drafts/current/. Drafts is at http://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six months Internet-Drafts are draft documents valid for a maximum of six months
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."
This Internet-Draft will expire on November 14, 2011. This Internet-Draft will expire on January 12, 2012.
Copyright Notice Copyright Notice
Copyright (c) 2011 IETF Trust and the persons identified as the Copyright (c) 2011 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 Provisions Relating to IETF Documents
(http://trustee.ietf.org/license-info) in effect on the date of (http://trustee.ietf.org/license-info) in effect on the date of
publication of this document. Please review these documents publication of this document. Please review these documents
skipping to change at page 2, line 27 skipping to change at page 2, line 27
the Trust Legal Provisions and are provided without warranty as the Trust Legal Provisions and are provided without warranty as
described in the Simplified BSD License. described in the Simplified BSD License.
Table of Contents Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3
2. The Use Cases . . . . . . . . . . . . . . . . . . . . . . . . 4 2. The Use Cases . . . . . . . . . . . . . . . . . . . . . . . . 4
3. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 5 3. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 5
4. Applicability . . . . . . . . . . . . . . . . . . . . . . . . 6 4. Applicability . . . . . . . . . . . . . . . . . . . . . . . . 6
5. Functional Overview . . . . . . . . . . . . . . . . . . . . . 6 5. Functional Overview . . . . . . . . . . . . . . . . . . . . . 6
6. Propagation of Discovery Messages . . . . . . . . . . . . . . 8 6. P2P Route Discovery By Creating a Temporary DAG . . . . . . . 8
6.1. The Route Discovery Option . . . . . . . . . . . . . . . . 9 6.1. The Route Discovery Option . . . . . . . . . . . . . . . . 9
6.2. Setting a DIO Carrying a Route Discovery Option . . . . . 12 6.2. Setting a DIO Carrying a Route Discovery Option . . . . . 12
6.3. Joining a Temporary DAG . . . . . . . . . . . . . . . . . 13 6.3. Joining a Temporary DAG . . . . . . . . . . . . . . . . . 13
6.4. Changes to Trickle Operation For DIOs Carrying a Route 6.4. Trickle Operation For DIOs Carrying a Route Discovery
Discovery Option . . . . . . . . . . . . . . . . . . . . . 13 Option . . . . . . . . . . . . . . . . . . . . . . . . . . 13
6.5. Processing a DIO Carrying a Route Discovery Option . . . . 14 6.5. Processing a DIO Carrying a Route Discovery Option . . . . 14
6.6. Additional Processing of a DIO Carrying a Route 6.6. Additional Processing of a DIO Carrying a Route
Discovery Option At An Intermediate Router . . . . . . . . 15 Discovery Option At An Intermediate Router . . . . . . . . 15
6.7. Additional Processing of a DIO Carrying a Route 6.7. Additional Processing of a DIO Carrying a Route
Discovery Option At The Target Node . . . . . . . . . . . 15 Discovery Option At The Target . . . . . . . . . . . . . . 15
7. Propagation of Discovery Reply Messages . . . . . . . . . . . 16 7. The Discovery Reply Object (DRO) . . . . . . . . . . . . . . . 16
7.1. The Discovery Reply Object (DRO) . . . . . . . . . . . . . 17 7.1. Processing a DRO At An Intermediate Router . . . . . . . . 18
7.2. Processing a DRO At An Intermediate Router . . . . . . . . 18 7.2. Processing a DRO At The Origin . . . . . . . . . . . . . . 19
7.3. Processing a DRO At The Origin . . . . . . . . . . . . . . 19 8. The Discovery Reply Object Acknowledgement (DRO-ACK) . . . . . 20
8. Security Considerations . . . . . . . . . . . . . . . . . . . 20 9. Packet Forwarding Along a P2P Route . . . . . . . . . . . . . 20
9. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 20 10. Security Considerations . . . . . . . . . . . . . . . . . . . 21
10. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 20 11. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 21
11. References . . . . . . . . . . . . . . . . . . . . . . . . . . 20 12. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 21
11.1. Normative References . . . . . . . . . . . . . . . . . . . 20 13. References . . . . . . . . . . . . . . . . . . . . . . . . . . 21
11.2. Informative References . . . . . . . . . . . . . . . . . . 21 13.1. Normative References . . . . . . . . . . . . . . . . . . . 21
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 21 13.2. Informative References . . . . . . . . . . . . . . . . . . 22
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 23
1. Introduction 1. Introduction
RPL [I-D.ietf-roll-rpl] provides multipoint-to-point (MP2P) routes RPL [I-D.ietf-roll-rpl] provides multipoint-to-point (MP2P) routes
from routers in a Low power and Lossy Network (LLN) to a sink by from routers in a Low power and Lossy Network (LLN) to a sink by
organizing the routers along a Directed Acyclic Graph (DAG) rooted at organizing the routers along a Directed Acyclic Graph (DAG) rooted at
the sink. The routers determine their position in the DAG so as to the sink. The routers determine their position in the DAG so as to
optimize their routing cost on the path towards the DAG root. A optimize their routing cost on the path towards the DAG root. A
router advertises its position (the "rank") in the DAG by originating router advertises its position (the "rank") in the DAG by originating
a DODAG Information Object (DIO) message. The DIO message is sent a DODAG Information Object (DIO) message. The DIO message is sent
skipping to change at page 4, line 25 skipping to change at page 4, line 25
o The need to maintain routes "proactively", i.e., every possible o The need to maintain routes "proactively", i.e., every possible
destination in the DAG must originate a DAO. destination in the DAG must originate a DAO.
o Depending on the network topology and OF/metrics in use, the o Depending on the network topology and OF/metrics in use, the
constraint to route only along a DAG may cause significantly constraint to route only along a DAG may cause significantly
suboptimal P2P routes and severe traffic congestion near the DAG suboptimal P2P routes and severe traffic congestion near the DAG
root. root.
Thus, there is a need for a mechanism that provides source-initiated Thus, there is a need for a mechanism that provides source-initiated
discovery of P2P routes that need not be along an existing DAG. This discovery of a P2P route that need not be along an existing DAG.
document describes such a mechanism, complementary to the basic RPL This document describes such a mechanism, complementary to the basic
functionality. RPL functionality.
The specified mechanism is based on a reactive on-demand approach, The specified mechanism is based on a reactive on-demand approach,
which enables a router to discover one or more routes in either which enables a router to discover a route to another router in the
direction between itself and another router in the LLN without any LLN without any restrictions regarding the existing DAG-membership of
restrictions regarding the existing DAG-membership of the links that the links that the route may use. The specified mechanism allows for
such routes may use. The discovered routes may be source routes or the discovery of sources routes as well as hop-by-hop ones. The
hop-by-hop routes. The discovered routes may not be the best discovered route may not be the best available but is guaranteed to
available but are guaranteed to satisfy the desired constraints in satisfy the desired constraints in terms of the routing metrics and
terms of the routing metrics and are thus considered "good enough" is thus considered "good enough" from the application's perspective.
from the application's perspective.
A complementary functionality, necessary to help decide whether to A complementary functionality, necessary to help decide whether to
initiate a route discovery, is a mechanism to measure the end-to-end initiate a route discovery, is a mechanism to measure the end-to-end
cost of an existing route. Section 4 provides further details on how cost of an existing route. Section 4 provides further details on how
such functionality, described in [I-D.ietf-roll-p2p-measurement], can such functionality, described in [I-D.ietf-roll-p2p-measurement], can
be used to determine the metric constraints for use in the route be used to determine the metric constraints for use in the route
discovery mechanism described in this document. discovery mechanism described in this document.
2. The Use Cases 2. The Use Cases
skipping to change at page 5, line 33 skipping to change at page 5, line 33
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and
"OPTIONAL" in this document are to be interpreted as described in "OPTIONAL" in this document are to be interpreted as described in
[RFC2119]. [RFC2119].
Additionally, this document uses terminology from Additionally, this document uses terminology from
[I-D.ietf-roll-terminology] and [I-D.ietf-roll-rpl]. This document [I-D.ietf-roll-terminology] and [I-D.ietf-roll-rpl]. This document
introduces the following terms: introduces the following terms:
Origin : The RPL node initiating the route discovery. The origin Origin : The RPL node initiating the route discovery.
acts as one end point of the routes to be discovered.
Target : The RPL node at the other end point of the routes to be Target : The RPL node at the other end point of the route(s) to be
discovered. discovered.
Intermediate Router: An RPL router that is neither the origin nor the Intermediate Router: An RPL router that is neither the origin nor the
target. target.
Forward Route: A route from the origin to the target. Forward Route: A route in the forward direction, i.e., from the
origin to the target.
Backward Route: A route from the target to the origin. Backward Route: A route in the backward direction, i.e., from the
target to the origin.
Bidirectional Route: A route that is both forward and backward. Bidirectional Route: A route that can be used in both forward and
backward directions.
Source Route: A complete and ordered list of routers that can be used Source Route: A complete and ordered list of routers that can be used
by a packet to travel from a source to a destination node. by a packet to travel from a source to a destination node.
Hop-by-hop Route: The route characterized by each router on the route Hop-by-hop Route: The route characterized by each router on the route
using its routing table to determine the next hop on the route. using its routing table to determine the next hop on the route.
4. Applicability 4. Applicability
The route discovery mechanism, described in this document, may be The route discovery mechanism, described in this document, may be
invoked by an origin when no route exists between itself and the invoked by an origin when no route exists between itself and the
target or when the existing routes do not satisfy the desired target or when the existing routes do not satisfy the desired
performance requirements. The mechanism is designed to discover one performance requirements. The mechanism is designed to discover and
or more routes that meet the specified constraints in either establish one hop-by-hop route or discover one or more source routes
direction between an origin and a target. In some application such that the discovered route(s) meet the specified constraints. In
contexts, the metric constraints that the discovered routes must some application contexts, the constraints that the discovered
satisfy are intrinsically known or can be specified by the route(s) must satisfy are intrinsically known or can be specified by
application. For example, an origin that expects a target to be less the application. For example, an origin that expects a target to be
than 5 hops away may use "hop-count < 5" as the constraint. In other less than 5 hops away may use "hop-count < 5" as the constraint. In
application contexts, the origin may need to measure the cost of an other application contexts, the origin may need to measure the cost
existing route to the target to determine the constraints. For of an existing route to the target to determine the constraints. For
example, an origin that measures the total ETX of its along-DAG route example, an origin that measures the total ETX of its along-DAG route
to the target to be 20 may use "ETX < x*20", where x is a fraction to the target to be 20 may use "ETX < x*20", where x is a fraction
that the origin decides, as the constraint. The functionality that the origin decides, as the constraint. The functionality
required to measure the cost of an existing route between the origin required to measure the cost of an existing route between the origin
and the target is described in [I-D.ietf-roll-p2p-measurement]. In and the target is described in [I-D.ietf-roll-p2p-measurement]. In
case, there is no existing route between the origin and target or the case, there is no existing route between the origin and target or the
cost measurement for the existing route fails, the origin will have cost measurement for the existing route fails, the origin will have
to guess the constraints used in the initial route discovery. Once, to guess the constraints used in the initial route discovery. Once,
the initial route discovery succeeds or fails, the origin will have a the initial route discovery succeeds or fails, the origin will have a
better estimate for the constraints to be used in the subsequent better estimate for the constraints to be used in the subsequent
skipping to change at page 6, line 49 skipping to change at page 7, line 5
conditions in the network. A network designer may take in conditions in the network. A network designer may take in
consideration both the benefits (potentially better routes; no need consideration both the benefits (potentially better routes; no need
to maintain routes proactively) and costs (control messages generated to maintain routes proactively) and costs (control messages generated
during the route discovery process) when using this mechanism. during the route discovery process) when using this mechanism.
5. Functional Overview 5. Functional Overview
This section contains a high level description of the route discovery This section contains a high level description of the route discovery
mechanism proposed in this document. mechanism proposed in this document.
The route discovery begins with the origin generating a "Discovery" The P2P route discovery takes place by forming a temporary DAG rooted
message. The origin indicates in the message: at the origin. The DIOs used to create the temporary DAG also carry
the following information:
o The target; o The target
o The relevant routing metrics; o The relevant routing metrics
o The constraints that the discovered route must satisfy. These o The constraints that the discovered route must satisfy. These
constraints also limit how far the Discovery message may travel; constraints also limit how far the Discovery message may travel.
o The direction (forward: from the origin to the target; backward: o The nature of the route(s) to be discovered: hop-by-hop or source
from the target to the origin; or bidirectional) of the route routes. This specification allows for the discovery of one hop-
being discovered; by-hop route or up to four source routes in the forward direction.
o The desired number of routes (in case forward/bidirectional routes o The desired number of routes (if source routes are being
are being discovered); discovered)
o Whether the route is a source route or a hop-by-hop one. o Whether the route(s) need to be bidirectional. If bidirectional
route(s) are being discovered, the target may store the route in
backward direction for use as a source route. This specification
does not provide for the establishment of backward hop-by-hop
routes.
The Discovery message propagates via IPv6 link-local multicast As the routers join the temporary DAG, they keep track of the best
towards the target accumulating the relevant routing metric values as (partial) route(s) they have seen and advertise these routes, along
well as the route it takes. A receiving router (including the with the corresponding routing metrics, in their DIOs. The routing
target) discards the Discovery message if the accumulated routing metrics are measured in forward direction unless bidirectional routes
metric values do not satisfy the listed constraints. A router may are being discovered, in which case the measurement of routing
also discard the Discovery message if it does not wish to be a part metrics need to take in account both forward and backward directions.
of the discovered route due to limited resources or due to policy A router, including the target, discards a received DIO if the
reasons. aggregated routing metrics on the route advertised by the DIO do not
satisfy the listed constraints. These constraints can be used to
limit the propagation of DIO messages used for P2P route discovery.
A router may also discard a received DIO if it does not wish to be a
part of the discovered route due to limited resources or due to
policy reasons.
The route discovery process may result in the discovery of several When the target receives a DIO, it checks whether the route
routes. This document does not specify how the target selects routes advertised therein satisfies the routing constraints. If yes, the
among the ones discovered. Example selection methods include target may select the route for further processing as described next.
selecting routes as they are discovered or selecting the best routes This document does not specify a particular method for the target to
discovered over a certain time period. select a route among the ones that satisfy the route constraints.
Example selection methods include selecting any route that meets the
constraints or selecting the best route(s) discovered over a certain
time period.
If the origin had requested the discovery of backward source-routes, If one or more source routes are being discovered, the target sends
the target caches one or more discovered source-routes. the discovered source routes to the origin via Discovery Reply Object
Additionally, the target sends a "Discovery Reply" message to the (DRO) messages, defined in Section 7, with one DRO message carrying
origin to acknowledge the discovery of these routes. one discovered route. On receiving a DRO message, the origin stores
the route contained therein in its memory.
If the origin had requested the discovery of "n" forward source- If a hop-by-hop route is being discovered, the target sends a DRO
routes, the target sends the discovered source-routes to the origin message to the origin after selecting a suitable route among the ones
in "n" Discovery Reply messages, with one Discovery Reply message that satisfy the route constraints. The DRO message travels towards
carrying one discovered source-route. the origin along the discovered route, establishing state for this
route in the routers on the path.
If the origin had requested the discovery of "n" bidirectional The target may store a discovered route in its memory if it is
source-routes, the target caches "n" discovered source-routes it bidirectional and use it as a backward source-route to send packets
selects and also sends these routes to the origin in "n" Discovery to the origin.
Reply messages.
If the origin had requested the discovery of "n" forward/backward/ The target may request the origin to acknowledge the receipt of a DRO
bidirectional hop-by-hop routes, the target sends out a Discovery message by sending back a DRO Acknowledgement (DRO-ACK) message
Reply message to the origin for each one of the "n" discovered routes (Section 8). The origin unicasts a DRO-ACK message to the target.
it selects. The Discovery Reply message travels towards the origin When the target does not receive the requested DRO-ACK within a
along the discovered route. As this message travels towards the certain time interval of sending a DRO, it resends the DRO message
origin, it establishes appropriate forward/backward routing state in carrying the same route as before.
the routers on the path.
6. Propagation of Discovery Messages 6. P2P Route Discovery By Creating a Temporary DAG
RPL uses DIO message propagation to build a DAG. The DIO message RPL uses DIO message propagation to build a DAG. The DIO message
travels via IPv6 link-local multicast. Each router joining the DAG travels via IPv6 link-local multicast. Each router joining the DAG
determines a rank for itself and ignores the subsequent DIO messages determines a rank for itself and ignores the subsequent DIO messages
received from lower (higher in numerical value) ranked neighbors. received from lower (higher in numerical value) ranked neighbors.
Thus, the DIO messages propagate outward from the DAG root rather Thus, the DIO messages propagate outward from the DAG root rather
than return inward towards the DAG root. The DIO message generation than return inward towards the DAG root. The DIO message generation
at a router is further controlled by a Trickle timer that allows a at a router is further controlled by a Trickle timer that allows a
router to avoid generating unnecessary messages [RFC6206]. The link- router to avoid generating unnecessary messages [RFC6206]. The link-
local multicast based propagation, Trickle-controlled generation and local multicast based propagation, Trickle-controlled generation and
the rank-based poisoning of messages traveling in the wrong direction the rank-based poisoning of messages traveling in the wrong direction
(towards the DAG root) provide powerful incentives to use the DIO (towards the DAG root) provide powerful incentives to use the DIO
message as the Discovery message and propagate the DIO/Discovery message for P2P route discovery by creating a "temporary" DAG. Such
message by creating a "temporary" DAG. Such an approach also allows an approach also allows the reuse of the routing metrics, objective
reuse of the routing metrics, objective function and packet function and packet forwarding framework developed for RPL. This
forwarding framework developed for RPL. This document defines a new document defines a new RPL option, Route Discovery Option (RDO),
RPL option, Route Discovery Option (RDO), which when carried inside a which when carried inside a DIO message identifies that message as
DIO message identifies that message as doing P2P route discovery by doing P2P route discovery by creating a temporary DAG as specified in
creating a temporary DAG as specified in this document. this document.
The use of trickle timers to delay the propagation of DIO messages The use of trickle timers to delay the propagation of DIO messages
may cause some nodes to generate these messages even when the desired may cause some nodes to generate these messages even when the desired
routes have already been discovered. In order to preempt the routes have already been discovered. In order to preempt the
generation of such unnecessary messages, the target may set a "stop" generation of such unnecessary messages, the target may set a "stop"
bit in the Discovery Reply message (Section 7) to let the nodes in bit in the DRO message to let the nodes in the LLN know about the
the LLN know about the completion of the route discovery process. completion of the route discovery process.
6.1. The Route Discovery Option 6.1. The Route Discovery Option
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type = 9 | Option Length | D |H| N | L | Compr | Rem | | Type = 9 | Option Length |D|H| N | Compr | L | Rem |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | | |
| Target | | Target |
| | | |
| | | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | | |
| Address[1..n] | | Address[1..n] |
| | | |
| | | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Figure 1: Format of the Route Discovery Option Figure 1: Format of the Route Discovery Option
In order to be used as a Discovery message, a DIO MUST carry a Route In order to perform P2P route discovery as specified in this
Discovery Option (RDO) illustrated in Figure 1. A Discovery Reply document, a DIO MUST carry a Route Discovery Option (RDO) illustrated
Object (DRO), defined in Section 7.1, MUST also carry a Route in Figure 1. A Discovery Reply Object (DRO) message, defined in
Discovery Option. A DIO/DRO message MUST NOT carry more than one Section 7, MUST also carry a Route Discovery Option. A DIO/DRO
Route Discovery Option. A router MUST discard a DIO/DRO if it message MUST NOT carry more than one Route Discovery Option. A
contains more than one Route Discovery Option. A Route Discovery router MUST discard a DIO/DRO if it contains more than one Route
Option consists of the following fields: Discovery Option. A Route Discovery Option consists of the following
fields:
o Option Type = 0x09 (to be confirmed by IANA).
o Option Length = The length of the option in bytes.
o Direction (D): This 2-bit field indicates the direction of the
desired routes:
* 0x00: Forward;
* 0x01: Backward; o Option Type: 0x09 (to be confirmed by IANA).
* 0x02: Bidirectional. o Option Length: The length of the option in bytes.
When the Route Discovery Option is carried inside a DIO, the link- o Direction (D): This flag indicates the direction in which the
level metric objects contained in the DIO SHOULD be measured in desired routes should be optimized. The flag is set to 1 if the
the direction indicated by the D field. Also, the IPv6 addresses routes are to be optimized for use in both forward and backward
accumulated in the Address vector MUST be accessible in the directions. If the discovered routes need be optimized in the
direction indicated by the D field. When the Route Discovery forward direction only, the flag is reset to 0. Note that the
Option is carried inside a DRO, this field MUST be set to zero on discovered routes must have bidirectional reachability
transmission and ignored on reception. irrespective of the value of D flag. This is because the DRO
messages travel from the target to the origin along one of the
discovered routes. When the Route Discovery Option is carried
inside a DIO, the link-level metric objects contained in the DIO
SHOULD be measured in the direction indicated by the D flag. When
the Route Discovery Option is carried inside a DRO message, this
flag should be set to zero on transmission and ignored on
reception.
o HopByHop (H): This flag, when set to 1, indicates that hop-by-hop o Hop-by-hop (H): This flag is set to 1 if a hop-by-hop route is
routes are desired. The flag is cleared when the source routes desired. The flag is reset to zero if source routes are desired.
are desired. This specification allows for the establishment of one hop-by-hop
route and up to four source routes in the forward direction. This
specification does not allow for the establishment of hop-by-hop
routes in the backward direction. If a bidirectional route is
discovered, the target MAY use the route in backward direction as
a source route to reach the origin, irrespective of the value of H
flag.
o Number of Routes (N): When the Route Discovery Option is being o Number of Routes (N): When the Route Discovery Option is being
carried inside a DIO: carried inside a DIO and the source routes are being discovered,
the value in this field plus one indicates the desired number of
* The value in this field plus one indicates the number of routes routes. When a hop-by-hop route is being discovered or when the
desired. Route Discovery Option is being carried inside a DRO message, this
field MUST be set to zero on transmission and ignored on
* This field is relevant only when the forward or bidirectional
routes are being discovered.
* When the backward routes are being discovered, this field MUST
be set to zero on transmission and ignored on reception.
When the Route Discovery Option is being carried inside a DRO,
this field MUST be set to zero on transmission and ignored on
reception. reception.
o Compr: 4-bit unsigned integer indicating the number of prefix
octets that are elided from the Target field and the Address
vector. For example, Compr value will be 0 if full IPv6 addresses
are carried in the Target field and the Address vector.
o Life Time (L): A 2-bit field that indicates the suggested life o Life Time (L): A 2-bit field that indicates the suggested life
time of the temporary DAG, i.e., the suggested duration a router time of the temporary DAG, i.e., the suggested duration a router
joining the temporary DAG must maintain its membership in the DAG. joining the temporary DAG must maintain its membership in the DAG.
The mapping between the values in this field and the minimum life The mapping between the values in this field and the minimum life
time of the temporary DAG is as follows: time of the temporary DAG is as follows:
* 0x00: 1 second; * 0x00: 1 second;
* 0x01: 4 seconds; * 0x01: 4 seconds;
* 0x02: 16 seconds; * 0x02: 16 seconds;
* 0x03: 64 seconds; * 0x03: 64 seconds;
Note that a router MAY detach from the temporary DAG sooner if it Note that a router MAY detach from the temporary DAG sooner if it
receives a DRO message concerning this DAG with "stop" bit set. receives a DRO message concerning this DAG with "stop" bit set.
When a Route Discovery Option is included inside a DRO message,
o Compr: 4-bit unsigned integer indicating the number of prefix this field MUST be set to zero on transmission and ignored on
octets that are elided from the Target field and the Address reception.
vector. For example, Compr value will be 0 if full IPv6 addresses
are carried in the Target field and the Address vector.
o Rem: When the Route Discovery Option is carried inside a DIO, this o Rem: When the Route Discovery Option is carried inside a DIO, this
field indicates the number of empty fields inside the Address field indicates the number of empty fields inside the Address
vector. When the Route Discovery Option is carried inside a DRO, vector. When the Route Discovery Option is carried inside a DRO
this field indicates the number of fields in the Address vector message, this field indicates the number of fields in the Address
yet to be visited. vector yet to be visited.
o Target: The IPv6 address of the target after eliding Compr number o Target: The IPv6 address of the target after eliding Compr number
of prefix octets. of prefix octets.
o Address[1..n]: A vector of IPv6 addresses representing a route o Address[1..n]: A vector of IPv6 addresses representing a (partial)
from the origin towards the target: route in the forward direction:
* Each element in the vector has size (16 - Compr) octets. * Each element in the vector has size (16 - Compr) octets.
* The total number of elements inside the Address vector is given * The total number of elements inside the Address vector is given
by n = (Option Length - 4 - (16 - Compr))/(16 - Compr). by n = (Option Length - 4 - (16 - Compr))/(16 - Compr).
* When the Route Discovery Option is carried inside a DIO, the * When the Route Discovery Option is carried inside a DIO, the
Address vector is used to accumulate a route optimized in the Address vector is used to accumulate a route optimized in the
direction specified by the D field. direction specified by the D field.
* The IPv6 addresses in the Address vector MUST be accessible in * The IPv6 addresses in the Address vector MUST be accessible in
the direction specified by the D field. both forward and backward directions. Accessibility in the
backward direction is required because the DRO message uses the
route accumulated in the Address vector to travel from the
target to the origin.
* The Address vector MUST carry the accumulated route such that * The Address vector MUST carry the accumulated route in the
the first element in the Address vector contains the IPv6 forward direction, i.e., the first element in the Address
address of the router next to the origin and so on. vector must contain the IPv6 address of the router next to the
origin and so on.
* The origin and target addresses MUST NOT be included in the * The origin and target addresses MUST NOT be included in the
Address vector. Address vector.
* A router adding its address to the vector MUST ensure that its * A router adding its address to the vector MUST ensure that its
address does not already exist in the vector. A router address does not already exist in the vector. A router
specifying a complete route in the Address vector MUST ensure specifying a complete route in the Address vector MUST ensure
that the vector does not contain any address more than once. that the vector does not contain any address more than once.
* The Address vector MUST NOT contain any multicast addresses. * The Address vector MUST NOT contain any multicast addresses.
* A DRO message travels from the target to the origin along a * When the Route Discovery Option is carried inside a DRO
route accumulated in the Address vector inside a Route message, the Address vector MUST contain a complete route
Discovery Option. Hence, the IPv6 addresses stored in the between the origin and the target such that the first element
Address vector MUST be accessible in the backward direction in the vector contains the IPv6 address of the router next to
also. the origin and the last element contains the IPv6 address of
the router next to the target.
* When the Route Discovery Option is carried inside a DRO, the
Address vector MUST contain a complete route between the origin
and the target such that the first element in the vector
contains the IPv6 address of the router next to the origin and
the last element contains the IPv6 address of the router next
to the target.
6.2. Setting a DIO Carrying a Route Discovery Option 6.2. Setting a DIO Carrying a Route Discovery Option
The Base Object in a DIO message carrying a Route Discovery Option The Base Object in a DIO message carrying a Route Discovery Option
MUST be set in the following manner: MUST be set in the following manner:
o RPLInstanceID: RPLInstanceID MUST be a local value as described in o RPLInstanceID: RPLInstanceID MUST be a local value as described in
Section 5.1 of [I-D.ietf-roll-rpl]. The origin MUST ensure that Section 5.1 of [I-D.ietf-roll-rpl]. The origin MUST NOT use the
different RPLInstanceID values are used in two or more concurrent same RPLInstanceID in two or more concurrent route discoveries.
route discoveries it initiates. The origin MAY use the same RPLInstanceID value to establish hop-
by-hop P2P routes to different target routers.
o Version Number: MUST be set to zero. The temporary DAG used for o Version Number: MUST be set to zero. The temporary DAG used for
P2P route discovery does not exist long enough to have new P2P route discovery does not exist long enough to have new
versions. versions.
o Grounded (G) Flag: MUST be cleared since this DAG is temporary in o Grounded (G) Flag: MUST be cleared since this DAG is temporary in
nature and MUST not be used for routing purpose. nature and MUST NOT be used for routing purpose.
o Mode of Operation (MOP), DTSN: These fields MUST be set to value 0 o Mode of Operation (MOP), DTSN: These fields MUST be set to value 0
since this DAG does not support downward routing. since this DAG does not support downward routing.
o DODAGPreference (Prf): This field MUST be set to value 0 (least o DODAGPreference (Prf): This field MUST be set to value 0 (least
preferred). preferred).
o DODAGID: This field MUST be set to the IPv6 address of the origin. o DODAGID: This field MUST be set to the IPv6 address of the origin.
o The other fields in the Base Object can be set in the desired o The other fields in the Base Object can be set in the desired
fashion as per the rules described in [I-D.ietf-roll-rpl]. fashion as per the rules described in [I-D.ietf-roll-rpl].
The DODAG Configuration option, carried in the DIO message, MUST be The DODAG Configuration option, carried in the DIO message, MUST be
set in the following manner: set in the following manner:
o MaxRankIncrease: This field MUST be set to 0 to disable local o MaxRankIncrease: This field MUST be set to 0 to disable local
repair of the temporary DAG. repair of the temporary DAG.
o Trickle parameters SHOULD be set as described in Section 6.4.
o The Default Lifetime and Lifetime Unit parameters in DODAG
Configuration option indicate the life time of the state the
routers maintain for a hop-by-hop route established using the
mechanism described in this draft.
o The other fields in the DODAG Configuration option, including the o The other fields in the DODAG Configuration option, including the
Trickle timer parameters and the OCP, can be set in the desired OCP, can be set in the desired fashion as per the rules described
fashion as per the rules described in [I-D.ietf-roll-rpl]. in [I-D.ietf-roll-rpl].
A DIO, carrying a Route Discovery Option, MUST NOT carry any Route A DIO, carrying a Route Discovery Option, MUST NOT carry any Route
Information or Prefix Information options described in Information or Prefix Information options described in
[I-D.ietf-roll-rpl].
The origin MUST NOT originate a DIO with a particular RPLInstanceID [I-D.ietf-roll-rpl].
for the P2P route discovery more than once in a given
P2PDISCOVERY_TIMEOUT duration.
6.3. Joining a Temporary DAG 6.3. Joining a Temporary DAG
When a router joins a temporary DAG advertized by a DIO carrying a When a router joins a temporary DAG advertized by a DIO carrying a
Route Discovery Option, it SHOULD maintain its membership in the DAG Route Discovery Option, it SHOULD maintain its membership in the DAG
for the suggested Life Time duration listed in the Route Discovery for the suggested Life Time duration listed in the Route Discovery
Option. Maintaining membership in the DAG implies remembering: Option. Maintaining membership in the DAG implies remembering:
o The RPLInstanceID, the DODAGID and the DODAGVersionNumber for the o The RPLInstanceID, the DODAGID and the DODAGVersionNumber for the
temporary DAG; temporary DAG;
o The router's rank in the temporary DAG; o The router's rank in the temporary DAG;
o The best values of the routing metrics, along with the associated o The best values of the routing metrics, along with the associated
route from the origin untill this router (carried inside the Route route(s) from the origin until this router (carried inside the
Discovery Option) in the DIOs received so far. Route Discovery Option) in the DIOs received so far.
The only purpose of a temporary DAG's existence is to facilitate the The only purpose of a temporary DAG's existence is to facilitate the
propagation of the Discovery messages. The temporary DAG MUST NOT be propagation of the Discovery messages. The temporary DAG MUST NOT be
used to route packets. A router SHOULD detach from the temporary DAG used to route packets. A router SHOULD detach from the temporary DAG
once the duration of its membership in the DAG has exceeded the DAG's once the duration of its membership in the DAG has exceeded the DAG's
suggested life time. A router MAY detach from a temporary DAG sooner suggested life time. A router MAY detach from a temporary DAG sooner
when it receives a DRO about the temporary DAG with stop flag set. when it receives a DRO about the temporary DAG with stop flag set.
6.4. Changes to Trickle Operation For DIOs Carrying a Route Discovery 6.4. Trickle Operation For DIOs Carrying a Route Discovery Option
Option
The DIOs carrying a Route Discovery Option create a DAG solely for
the purpose of P2P route discovery. This DAG is temporary in nature,
i.e., it exists just long enough to allow the completion of the P2P
route discovery process. Low latency is a critical requirement for
P2P route discovery in many application scenarios in home and
building automation LLNs [RFC5826][RFC5867]. This means that the
Imin and Imax parameters, used in Trickle timer operation to control
the generation of DIOs for this temporary DAG, can not be too large.
Low values for Imin/Imax mean frequent generation of DIOs advertising
same information as before. These DIO transmissions would mostly be
unnecessary, expensive in terms of energy consumption and may cause
congestion in the LLN during the P2P route discovery. One way to
avoid the potential DIO storm, caused by frequent DIO generation, is
to set the redundancy constant to a small value. A small redundacy
constant would suppress a DIO transmission if sufficient "consistent"
DIOs have been heard during the preceding Trickle interval. However,
a small redundancy constant may also cause a router to not generate
its DIO even when the router has a better route to report.
Thus, the key requirements regarding DIO generation, from the An RPL router uses a Trickle timer [RFC6206] to control DIO
perspective of P2P route discovery, are as follows: transmissions. The Trickle control of DIO transmissions provides
quick resolution of any "inconsistency" while avoiding redundant DIO
transmissions. The Trickle algorithm also imparts protection against
loss of DIOs due to inherent lack of reliability in wireless
communication. When controlling the transmissions of a DIO carrying
a Route Discovery Option, a Trickle timer SHOULD follow the following
rules:
o A router should generate a DIO quickly when it has a better route o The receipt of a DIO, that allows the router to advertise a better
to advertise. route (in terms of the routing metrics and the OCP in use) than
before, is considered "inconsistent" and hence resets the Trickle
timer. Note that the first receipt of a DIO advertising a
particular temporary DAG is always considered an inconsistent
event under this rule.
o The DIO generation policy must not lead to a DIO storm. o The receipt of a DIO, that advertises a better route than the
router but does not lead to the router advertising a better route
itself, is considered "consistent".
To meet these requirements, o The receipt of a DIO, that advertises as good a route as the
router itself, is considered "consistent".
o A DIO, carrying a Route Discovery Option, SHOULD be suppressed if o The receipt of a DIO, that advertises a worse route than what the
the router does not have a better route to advertise. This rule router advertises, is considered neither "consistent" nor
applies irrespecive of the values of the redundancy constant and "inconsistent", i.e., the receipt of such a DIO has no impact on
the number of "consistent" DIOs received in the preceding Trickle the Trickle operation.
interval.
o A DIO, carrying a Route Discovery Option, SHOULD NOT be suppressed o The recommended values of Imin and Imax are same as in base RPL
if the router has a better route to advertise. This rule applies specification [I-D.ietf-roll-rpl], i.e., 8ms and 2.3 hours
irrespecive of the values of the redundancy constant and the respectively.
number of "consistent" DIOs received in the preceding Trickle
interval.
o A router SHOULD consider the receipt of a DIO, that leads to an o The recommended value of redundancy constant "k" is 1. With this
improvement in the aggregated routing metrics values the router value of "k", a DIO transmission will be suppressed if the router
could advertise for this temporary DAG, as an "inconsistency" and receives even a single "consistent" DIO during a timer interval.
hence reset the Trickle timer governing the DIO generation for
this temporary DAG [RFC6206].
6.5. Processing a DIO Carrying a Route Discovery Option 6.5. Processing a DIO Carrying a Route Discovery Option
The rules for DIO processing and transmission, described in Section 8 The rules for DIO processing and transmission, described in Section 8
of RPL [I-D.ietf-roll-rpl], apply to DIOs carrying a Route Discovery of RPL [I-D.ietf-roll-rpl], apply to DIOs carrying a Route Discovery
option as well except as modified in this document. option as well except as modified in this document.
The following rules for processing a DIO carrying a Route Discovery The following rules for processing a DIO carrying a Route Discovery
Option apply to both intermediate routers and the target. Option apply to both intermediate routers and the target.
A router SHOULD update the values of link-level routing metrics A router SHOULD discard a received DIO with no further processing if
included inside the DIO in the direction indicated by the D field in it does not have bidirectional reachability with the neighbor that
the Route Discovery Option. If the D field is 0x00, i.e., the originated the received DIO. This is to ensure that a discovered
forward routes are being discovered, any link-level routing metric route can be used to send a DRO message from the target to the
SHOULD be measured in the direction towards the node receiving the origin. Note that bidirectional reachability does not mean that the
DIO. If the D field is 0x01, i.e., the backward routes are being link must have the same values for a routing metric in both
discovered, any link-level routing metric SHOULD be measured in the directions. A router SHOULD update the values of the link-level
direction towards the node originating the DIO. If the D field is routing metrics included inside the DIO in the direction indicated by
0x02, i.e., the bidirectional routes are being discovered, any link- the D flag in the Route Discovery Option. If the D flag is 0, i.e.,
level routing metric SHOULD be calculated so as to take in account the discovered routes need not be bidirectional, the link-level
the metric's value in both directions. routing metrics SHOULD be measured in the forward direction, i.e.,
towards the node receiving the DIO. If the D flag is 1, i.e.,
bidirectional routes are desired, the link-level routing metrics
SHOULD be calculated so as to take in account the metric's value in
both forward and backward directions.
A router MUST discard the DIO with no further processing if it can A router MUST discard the DIO with no further processing if it can
not evaluate the mandatory route constraints listed in the DIO or if not evaluate the mandatory route constraints listed in the DIO or if
the routing metric values do not satisfy one or more of the mandatory the routing metric values do not satisfy one or more of the mandatory
constraints. constraints.
6.6. Additional Processing of a DIO Carrying a Route Discovery Option 6.6. Additional Processing of a DIO Carrying a Route Discovery Option
At An Intermediate Router At An Intermediate Router
When an intermediate router receives a DIO containing a Route When an intermediate router receives a DIO containing a Route
Discovery Option, it MUST determine if this DIO is the best it has Discovery Option, it MUST determine whether this DIO advertises a
received so far for this temporary DAG in terms of the routing better route than the router itself and whether the receipt of the
metrics listed in the DIO. If yes, the router MUST add its own IPv6 DIO would allow the router to advertise a better route than before.
address to the accumulated route at location Address[n-Rem+1] inside Accordingly, the router SHOULD consider this DIO as consistent/
the Route Discovery Option and stores this route in memory along with inconsistent from Trickle perspective as described in Section 6.4.
the routing metrics associated with this route. When a router If the received DIO would allow the router to improve the route it
includes itself in an accumulated route, it MUST ensure that the IPv6 advertises, the router MUST add its IPv6 address to the route inside
address added to the route is accessible in both the backward the received DIO at location Address[n-Rem+1] and store this route in
direction and the direction indicated by the D field in the Route memory for inclusion in its future DIOs. When an intermediate router
Discovery Option. The router MUST also reset the Trickle timer adds itself to a route, it MUST ensure that the IPv6 address added to
associated with the temporary DAG whenever it updates the best route the route is accessible in both forward and backward directions. To
it has seen so far. When the Trickle timer fires, an intermediate improve the diversity of the routes being discovered, an intermediate
router checks whether DIO generation is suppressed or not as per router SHOULD remember multiple partial routes, the best it knows in
Section 6.4. If DIO generation is allowed, the router generates a terms of the routing metrics, that it can advertise in the Route
new DIO DIO for this temporary DAG carrying the best routing metric Discovery Option inside its DIO. When the router generates its DIO,
values it knows and a Route Discovery Option that carried in its it SHOULD randomly select the partial route to be included in the
Address vector the best route the router has seen so far. Route Discovery Option from the set of best routes it has seen so
far.
6.7. Additional Processing of a DIO Carrying a Route Discovery Option 6.7. Additional Processing of a DIO Carrying a Route Discovery Option
At The Target Node At The Target
The target considers the route accumulated inside a Route Discovery
Option in a received DIO as acceptable if the routing metrics inside
the DIO satisfy all the mandatory constraints. The target would
select some routes among the acceptable ones for further processing.
This document does not prescribe a particular method for the target
to select routes. Suppose the Route Discovery Option requests the
discovery of "n" routes. The target may select these "n" routes in
any manner it desires. Example selection methods include selecting
the first "n" acceptable routes or selecting the "n" best routes
discovered over a certain time period.
If the Route Discovery Option identifies the selected route as a
backward source route (D=0x01, H=0), the target stores the discovered
route, obtained by reversing the contents of the Address vector, in
its memory. The target sends a Discovery Reply Object (DRO) message
back to the origin (identified by the DODAGID field in the DIO) after
selecting the desired number of such routes. In this DRO, the target
includes a Route Discovery Option, which can simply be the copied
from one of the DIOs carrying a selected route. The mechanism for
the propagation of DRO messages is described in Section 7.
If the Route Discovery Option identifies the selected route as a
forward source route (D=0x00, H=0), the target sends a DRO message
back to the origin. In this DRO, the target includes a Route
Discovery Option, which has same contents as the Route Discovery
Option contained in the received DIO.
If the Route Discovery Option identifies the selected route as a
bidirectional source route (D=0x02, H=0), the target stores the
discovered route, obtained by reversing the contents of the Address
vector, in its memory and sends a DRO message back to the origin. In
this DRO, the target includes a Route Discovery Option, which has
same contents as the Route Discovery Option contained in the received
DIO.
If the Route Discovery Option identifies the selected route as a
backward hop-by-hop route (D=0x01, H=1), the target stores the state
for the discovered route, in the manner described in Section 7.2, in
its memory and sends a DRO message back to the origin. In this DRO,
the target includes a Route Discovery Option, which has same contents
as the Route Discovery Option contained in the received DIO.
If the Route Discovery Option identifies the selected route as a The target discards a received DIO with no further processing if the
forward hop-by-hop route (D=0x00, H=1), the target sends a DRO routing metrics inside the DIO do not satisfy the the mandatory
message back to the origin. In this DRO, the target includes a Route constraints. Otherwise, the target MAY select the route contained in
Discovery Option, which has same contents as the Route Discovery the Route Discovery Option for further processing. This document
Option contained in the received DIO. does not prescribe a particular method for the target to select such
routes. Example selection methods include selecting the desired
number of routes as they are identified or selecting the best routes
discovered over a certain time period. If multiple routes are
desired, the target SHOULD avoid selecting routes that have large
segments in common. If a discovered route is bidirectional (D=1),
the target MAY store the route in backward direction, obtained by
reversing the discovered forward route, for use as a source route to
reach the origin. After selecting a route, the target sends a
Discovery Reply Object (DRO) message back to the origin (identified
by the DODAGID field in the DIO). In this DRO, the target includes a
Route Discovery Option that contains the selected route inside the
Address vector. The Route Discovery Option included in the DRO
message MUST copy the H flag from the Route Discovery Option inside
the received DIO message. The other fields inside the Route
Discovery Option MUST be set as specified in Section 6.1. The
mechanism for the propagation of DRO messages is described in
Section 7.
The target MAY include a Metric Container Option in the DRO. This The target MAY set the A flag inside the DRO message if it desires
Metric Container contains the end-to-end routing metric values for the origin to send back a DRO-ACK message on receiving the DRO. In
the route specified in the Address vector inside the Route Discovery this case, the target waits for DRO_ACK_WAIT_TIME duration for the
Option contained in the DRO message. DRO-ACK message to arrive. Failure to receive the DRO-ACK message
within this time duration causes the target to retransmit the DRO
message. The target MAY retransmit the DRO message in this fashion
up to MAX_DRO_RETRANSMISSIONS times.
A target MUST NOT forward a DIO carrying a Route Discovery option any The target MAY include a Metric Container Option in the DRO message.
further. This Metric Container contains the end-to-end routing metric values
for the route specified in the Route Discovery Option. The target
MAY set the stop flag inside the DRO message if it has already
selected the desired number of routes. A target MUST NOT forward a
DIO carrying a Route Discovery option any further.
7. Propagation of Discovery Reply Messages 7. The Discovery Reply Object (DRO)
7.1. The Discovery Reply Object (DRO)
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| RPLInstanceID | Version |S| Reserved | | RPLInstanceID | Version |S|A|Seq| Reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | | |
| DODAGID | | DODAGID |
| | | |
| | | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Option(s)... | Option(s)...
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+...
Figure 2: Format of the Discovery Reply Object (DRO) Figure 2: Format of the Discovery Reply Object (DRO)
This document defines a new RPL Control Message type, the Discovery This document defines a new RPL Control Message type, the Discovery
Reply Object (DRO) with code 0x04 (to be confirmed by IANA), that Reply Object (DRO) with code 0x04 (to be confirmed by IANA), that
serves one of the following functions: serves one of the following functions:
o Acknowledge to the origin the successful discovery of backward o Carry a discovered source route from the target to the origin;
source routes;
o Carry one forward/bidirectional source route from the target to
the origin;
o Establish one hop-by-hop forward/backward/bidirectional route as o Establish a hop-by-hop route as it travels from the target to the
it travels from the target to the origin. origin.
A DRO message also serves the function of letting the routers in the A DRO message MAY also serve the function of letting the routers in
LLN know that a P2P route discovery is complete and no more DIO the LLN know that a P2P route discovery is complete and no more DIO
messages need to be generated for the corresponding temporary DAG. A messages need to be generated for the corresponding temporary DAG. A
DRO message MUST carry one Route Discovery Option and travel from the DRO message MUST carry one Route Discovery Option and travel from the
target to the origin via link-local multicast along the route target to the origin via link-local multicast along the route
specified in the Route Discovery Option. specified in the Route Discovery Option.
The format for a Discovery Reply Object (DRO) is shown in Figure 2. The format for a Discovery Reply Object (DRO) is shown in Figure 2.
A DRO consists of the following fields: A DRO consists of the following fields:
o RPLInstanceID: The RPLInstanceID of the temporary DAG used for o RPLInstanceID: The RPLInstanceID of the temporary DAG used for
route discovery. route discovery.
o Version: The Version of the temporary DAG used for route o Version: The Version of the temporary DAG used for route
discovery. discovery.
o Stop (S): This flag, when set by the target, indicates that the o Stop (S): This flag, when set by the target, indicates that the
route discovery being performed by the temporary DAG (identified P2P route discovery is over. The routers, receiving such a DRO,
by the RPLInstanceID, DODAGID and VersionNumber field inside the SHOULD cancel any pending DIO transmissions for the temporary DAG
DRO) is over. The routers, receiving such a DRO, SHOULD cancel created for the route discovery and MAY detach from this DAG
any pending DIO transmissions for this DAG and MAY detach from the immediately. Note that the stop flag serves to stop further DIO
temporary DAG immediately. The target SHOULD set the stop flag in transmissions for a P2P route discovery but it does not affect the
a DRO when it does not need to receive any more routes via DIOs. processing of DRO messages at either the origin or the
intermediate routers. In other words, a router (the origin or an
intermediate router) MUST continue to process the DRO messages
even if an earlier DRO message (with same RPLInstanceID, DODAGID
and Version Number fields) had the stop flag set.
o Ack Required (A): This flag, when set by the target, indicates
that the origin SHOULD unicast a DRO-ACK message to the target
when it receives the DRO.
o Sequence Number (Seq): This 2-bit field indicates the sequence
number for the DRO. This field is relevant when the A flag is
set, i.e., the target requests an acknowledgement from the origin
for a received DRO. The origin includes the RPLInstanceID, the
DODAGID and the Sequence Number of the received DRO inside the
DRO-ACK message it sends back to the target.
o Reserved: These bits are reserved for future use. These bits MUST o Reserved: These bits are reserved for future use. These bits MUST
be set to zero on transmission and MUST be ignored on reception. be set to zero on transmission and MUST be ignored on reception.
o DODAGID: The DODAGID of the temporary DAG used for route o DODAGID: The DODAGID of the temporary DAG used for route
discovery. The DODAGID also identifies the origin. The discovery. The DODAGID also identifies the origin. The
RPLInstanceID, the Version and the DODAGID together uniquely RPLInstanceID, the Version and the DODAGID together uniquely
identify the temporary DAG used for route discovery and can be identify the temporary DAG used for route discovery and can be
copied from the DIO message advertizing the temporary DAG. copied from the DIO message advertizing the temporary DAG.
o Options: The DRO message MUST carry one Route Discovery Option o Options: The DRO message MUST carry one Route Discovery Option
that MUST specify a complete route between the target and the that MUST specify a complete route between the target and the
origin. The DRO message MAY carry a Metric Container Option that origin. The DRO message MAY carry a Metric Container Option that
contains the aggregated routing metrics values for the route contains the aggregated routing metrics values for the route
specified in Route Discovery Option. specified in Route Discovery Option.
7.2. Processing a DRO At An Intermediate Router 7.1. Processing a DRO At An Intermediate Router
When a router receives a DRO message that does not list its IPv6 When a router receives a DRO message that does not list its IPv6
address in the DODAGID field, the router MUST process the received address in the DODAGID field, the router MUST process the received
message in the following manner: message in the following manner:
o If the stop flag inside the received DRO is set and the router o If the stop flag inside the received DRO is set and the router
currently belongs to the temporary DAG identified by the currently belongs to the temporary DAG identified by the
(RPLInstanceID, DODAGID and Version Number fields of the) DRO, the (RPLInstanceID, DODAGID and Version fields of the) DRO, the router
router SHOULD cancel any pending DIO transmissions for this SHOULD cancel any pending DIO transmissions for this temporary
temporary DAG. Additionally, the router MAY detach from the DAG. Additionally, the router MAY detach from the temporary DAG
temporary DAG immediately. immediately.
o An intermediate router MUST ignore any Metric Container Option o An intermediate router MUST ignore any Metric Container Option
contained in the DRO message. contained in the DRO message.
o If Address[Rem] element inside the Route Discovery Option lists o If Address[Rem] element inside the Route Discovery Option lists
the router's own IPv6 address, the router is a part of the route the router's own IPv6 address, the router is a part of the route
carried in the Route Discovery Option. In this case, the router carried in the Route Discovery Option. In this case, the router
MUST do the following: MUST do the following:
* If the H flag inside the Route Discovery Option inside the DRO * If the H flag inside the Route Discovery Option inside the DRO
message is set, the router MUST store state for the P2P route message is set, the router SHOULD store the state for the
carried inside the Route Discovery Option. This state consists forward hop-by-hop route carried inside the Route Discovery
of: Option. This state consists of:
+ The RPLInstanceID and the DODAGID fields of the DRO. + The RPLInstanceID and the DODAGID fields of the DRO.
+ The route's destination, either origin (identified by + The route's destination, the target (identified by Target
DODAGID field in DRO) or target (identified by Target field field in Route Discovery Option).
in Route Discovery Option).
+ The IPv6 address of the next hop. + The IPv6 address of the next hop, Address[Rem+1] (unless Rem
value equals the number of elements in the Address vector,
in which case the target itself is the next hop).
For routes in the forward direction (D=0x00 in the Route The router MUST drop the DRO message without further processing
Discovery Option), the route's destination is the target and if the H flag inside the Route Discovery Option is set but the
the next hop address is Address[Rem+1] (unless Rem value equals router chooses not to store the state for the hop-by-hop route.
the number of elements in the Address vector, in which case the
target itself is the next hop). For routes in the backward * If the router already maintains a hop-by-hop state listing the
direction (D=0x01 in the Route Discovery Option), the route's target as the destination and carrying same RPLInstanceID and
destination is the origin and the next hop address is DODAGID fields as the received DRO and the next hop information
Address[Rem-1] (unless Rem = 1, in which case the origin itself in the state does not match the next hop indicated in the
is the next hop). If the route is bidirectional (D = 0x02 in received DRO, the router MUST drop the DRO message with no
the Route Discovery Option), two routing states are created, further processing.
one in forward direction and one in backward direction.
* The router MUST decrement the Rem field inside the Route * The router MUST decrement the Rem field inside the Route
Discovery Option and send the DRO further via link-local Discovery Option and send the DRO further via link-local
multicast. multicast.
7.3. Processing a DRO At The Origin 7.2. Processing a DRO At The Origin
When a router receives a DRO message that lists its IPv6 address in When a router receives a DRO message that lists its IPv6 address in
the DODAGID field, the router recognizes itself as the origin for the the DODAGID field, the router recognizes itself as the origin for the
corresponding P2P route discovery and processes the Route Discovery corresponding P2P route discovery and processes the Route Discovery
Option contained in the DRO in the following manner. Option contained in the DRO in the following manner.
If the Route Discovery Option identifies the discovered route as a If the stop flag inside the received DRO is set and the origin still
backward source/hop-by-hop route (D=0x01, H=0 or H=1), the origin belongs to the temporary DAG it initiated, it SHOULD cancel any
considers the DRO receipt as the acknowledgement of successful pending DIO transmissions for this temporary DAG. Additionally, the
completion of the P2P route discovery process. origin MAY detach from the temporary DAG immediately.
If the Route Discovery Option identifies the discovered route as a If the Route Discovery Option inside the DRO identifies the
forward/bidirectional source route (D=0x00 or 0x02, H=0), the origin discovered route as a source route (H=0), the origin SHOULD store in
stores the discovered route, contained in the Address vector, in its its memory the discovered route contained in the Address vector.
memory.
If the Route Discovery Option identifies the discovered route as a If the Route Discovery Option inside the DRO identifies the
forward/bidirectional hop-by-hop route (D=0x00 or 0x02, H=1), the discovered route as a hop-by-hop route (H=1), the origin SHOULD store
origin stores the state for the discovered route in forward in its memory the state for the discovered route in the manner
direction, in the manner described in Section 7.2, in its memory. described in Section 7.1.
If the received DRO message contains a Metric Container Option as If the received DRO message contains a Metric Container Option as
well, the origin MAY store the values of the routing metrics well, the origin MAY store the values of the routing metrics
associated with the discovered route in its memory. This information associated with the discovered route in its memory. This information
may be useful in formulating the constraints for any future P2P route may be useful in formulating the constraints for any future P2P route
discovery to the target. discovery to the target.
8. Security Considerations If the A flag is set to one in the received DRO message, the origin
SHOULD generate a DRO-ACK message as described in Section 8 and
unicast the message to the target. The origin MAY source route the
DRO-ACK message to the target using the route contained in the
received DRO. If the received DRO established a hop-by-hop route to
the target, the origin MAY send the DRO-ACK message along this route.
Section 9 describes how a packet may be forwarded along a route
discovered using the mechanism described in this document.
8. The Discovery Reply Object Acknowledgement (DRO-ACK)
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| RPLInstanceID | Version |Seq| Reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
| DODAGID |
| |
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Figure 3: Format of the Discovery Reply Object Acknowledgement (DRO-
ACK)
A DRO message may fail to reach the origin due to a number of
reasons. Unlike the DIO messages that benefit from Trickle-
controlled retransmissions, the DRO messages are prone to loss due to
reasons associated with wireless communication. Since a DRO message
travels via link-local multicast, it can not use link-level
acknowledgements to improve the reliability of its transmission.
Also, an intermediate router may drop the DRO message (e.g., because
of its inability to store the state for the hop-by-hop route the DRO
is establishing). To protect against the potential failure of a DRO
message to reach the origin, the target MAY request the origin to
send back a DRO Acknowledgement (DRO-ACK) message on receiving a DRO
message. Failure to receive such an acknowledgement within the
DRO_ACK_WAIT_TIME interval of sending the DRO message forces the
target to resend the message.
DRO Acknowledgement is a new RPL Control Message type with code 0x05
(to be confirmed by IANA). A DRO-ACK message MUST travel as a
unicast message from the origin to the target. The format for a DRO-
ACK message is shown in Figure 3. Various fields in a DRO-ACK
message MUST have the same values as the corresponding fields in the
DRO message. The field marked as "Reserved" MUST be set to zero on
transmission and MUST be ignored on reception.
9. Packet Forwarding Along a P2P Route
This document specifies a mechanism to discover P2P routes, which can
be either source routes or hop-by-hop ones. A packet MAY use an RH4
header [I-D.ietf-6man-rpl-routing-header] to travel along a P2P
source route. Travel along a P2P hop-by-hop route requires
specifying the RPLInstanceID and the DODAGID to identify the route.
This is because P2P route discovery does not use globally unique
RPLInstanceID values and hence both the RPLInstanceID, which is a
local value assigned by the origin, and the DODAGID, which is an IPv6
address belonging to the origin, are required to uniquely identify a
P2P hop-by-hop route to a particular destination. A packet MAY
include an RPL option [I-D.ietf-6man-rpl-option] inside the IPv6 hop-
by-hop options header to travel along a P2P hop-by-hop route. In
this case, the origin MUST set the DODAGID of the P2P route as the
source IPv6 address of the packet. Further, the origin MUST specify
the RPLInstanceID, associated with the P2P route, inside the RPL
option and set the O flag inside the RPL option to 1. A router
receiving this packet will check the O flag inside the RPL option and
correctly infer the source IPv6 address of the packet as the DODAGID
of the hop-by-hop route to be used for forwarding the packet further.
10. Security Considerations
TBA TBA
9. IANA Considerations 11. IANA Considerations
TBA TBA
10. Acknowledgements 12. Acknowledgements
Authors gratefully acknowledge the contributions of the following Authors gratefully acknowledge the contributions of the following
individuals (in alphabetical order) in the development of this individuals (in alphabetical order) in the development of this
document: Dominique Barthel, Thomas Clausen, Richard Kelsey, Zach document: Dominique Barthel, Thomas Clausen, Richard Kelsey, Phil
Shelby, Pascal Thubert and JP Vasseur. Levis, Zach Shelby, Pascal Thubert and JP Vasseur.
11. References 13. References
11.1. Normative References 13.1. Normative References
[I-D.ietf-roll-p2p-measurement] [I-D.ietf-roll-p2p-measurement]
Goyal, M., Baccelli, E., Brandt, A., Cragie, R., Martocci, Goyal, M., Baccelli, E., Brandt, A., Cragie, R., Martocci,
J., and C. Perkins, "A Mechanism to Measure the Quality of J., and C. Perkins, "A Mechanism to Measure the Quality of
a Point-to-point Route in a Low Power and Lossy Network", a Point-to-point Route in a Low Power and Lossy Network",
draft-ietf-roll-p2p-measurement-00 (work in progress), draft-ietf-roll-p2p-measurement-00 (work in progress),
April 2011. April 2011.
[I-D.ietf-roll-routing-metrics] [I-D.ietf-roll-routing-metrics]
Vasseur, J., Kim, M., Pister, K., Dejean, N., and D. Vasseur, J., Kim, M., Pister, K., Dejean, N., and D.
skipping to change at page 21, line 11 skipping to change at page 22, line 21
Vasseur, "RPL: IPv6 Routing Protocol for Low power and Vasseur, "RPL: IPv6 Routing Protocol for Low power and
Lossy Networks", draft-ietf-roll-rpl-19 (work in Lossy Networks", draft-ietf-roll-rpl-19 (work in
progress), March 2011. progress), March 2011.
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119, March 1997. Requirement Levels", BCP 14, RFC 2119, March 1997.
[RFC6206] Levis, P., Clausen, T., Hui, J., Gnawali, O., and J. Ko, [RFC6206] Levis, P., Clausen, T., Hui, J., Gnawali, O., and J. Ko,
"The Trickle Algorithm", RFC 6206, March 2011. "The Trickle Algorithm", RFC 6206, March 2011.
11.2. Informative References 13.2. Informative References
[I-D.brandt-roll-rpl-applicability-home-building] [I-D.brandt-roll-rpl-applicability-home-building]
Brandt, A., Baccelli, E., and R. Cragie, "Applicability Brandt, A., Baccelli, E., and R. Cragie, "Applicability
Statement: The use of RPL in Building and Home Statement: The use of RPL in Building and Home
Environments", Environments",
draft-brandt-roll-rpl-applicability-home-building-01 (work draft-brandt-roll-rpl-applicability-home-building-01 (work
in progress), November 2010. in progress), November 2010.
[I-D.ietf-6man-rpl-option]
Hui, J. and J. Vasseur, "RPL Option for Carrying RPL
Information in Data-Plane Datagrams",
draft-ietf-6man-rpl-option-03 (work in progress),
March 2011.
[I-D.ietf-6man-rpl-routing-header]
Hui, J., Vasseur, J., Culler, D., and V. Manral, "An IPv6
Routing Header for Source Routes with RPL",
draft-ietf-6man-rpl-routing-header-03 (work in progress),
March 2011.
[I-D.ietf-roll-terminology] [I-D.ietf-roll-terminology]
Vasseur, J., "Terminology in Low power And Lossy Vasseur, J., "Terminology in Low power And Lossy
Networks", draft-ietf-roll-terminology-05 (work in Networks", draft-ietf-roll-terminology-05 (work in
progress), March 2011. progress), March 2011.
[RFC5826] Brandt, A., Buron, J., and G. Porcu, "Home Automation [RFC5826] Brandt, A., Buron, J., and G. Porcu, "Home Automation
Routing Requirements in Low-Power and Lossy Networks", Routing Requirements in Low-Power and Lossy Networks",
RFC 5826, April 2010. RFC 5826, April 2010.
[RFC5867] Martocci, J., De Mil, P., Riou, N., and W. Vermeylen, [RFC5867] Martocci, J., De Mil, P., Riou, N., and W. Vermeylen,
skipping to change at page 22, line 4 skipping to change at page 23, line 24
Phone: +1 414 2295001 Phone: +1 414 2295001
Email: mukul@uwm.edu Email: mukul@uwm.edu
Emmanuel Baccelli Emmanuel Baccelli
INRIA INRIA
Phone: +33-169-335-511 Phone: +33-169-335-511
Email: Emmanuel.Baccelli@inria.fr Email: Emmanuel.Baccelli@inria.fr
URI: http://www.emmanuelbaccelli.org/ URI: http://www.emmanuelbaccelli.org/
Matthias Philipp
INRIA
Email: Matthias.Philipp@inria.fr
Anders Brandt Anders Brandt
Sigma Designs Sigma Designs
Emdrupvej 26A, 1. Emdrupvej 26A, 1.
Copenhagen, Dk-2100 Copenhagen, Dk-2100
Denmark Denmark
Phone: +45-29609501 Phone: +45-29609501
Email: abr@sdesigns.dk Email: abr@sdesigns.dk
Robert Cragie Robert Cragie
 End of changes. 93 change blocks. 
374 lines changed or deleted 466 lines changed or added

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