Internet Engineering Task Force M. Goyal, Ed.
Internet-Draft University of Wisconsin Milwaukee
Intended status: Experimental E. Baccelli
Expires: August 11, 2011 INRIA
A. Brandt
Sigma Designs
R. Cragie
Gridmerge Ltd
J. Martocci
Johnson Controls
C. Perkins
Tellabs Inc
February 7, 2011
Reactive Discovery of Point-to-Point Routes in Low Power and Lossy
Networks
draft-ietf-roll-p2p-rpl-02
Abstract
Point to point (P2P) communication between arbitrary IPv6 routers and
hosts in a Low power and Lossy Network (LLN) is a key requirement for
many applications. RPL, the IPv6 Routing Protocol for LLNs,
constrains the LLN topology to a Directed Acyclic Graph (DAG) and
requires the P2P routing to take place along the DAG links. Such P2P
routes may be suboptimal and may lead to traffic congestion near the
DAG root. This document specifies a P2P route discovery mechanism,
complementary to the RPL base functionality. This mechanism allows
an RPL-aware IPv6 router or host to discover and establish, on
demand, one or more routes to another RPL-aware IPv6 router or host
in the LLN such that the discovered routes meet a specified cost
criteria.
Status of this Memo
This Internet-Draft is submitted to IETF in full conformance with the
provisions of BCP 78 and BCP 79.
Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF). Note that other groups may also distribute
working documents as Internet-Drafts. The list of current Internet-
Drafts is at http://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress."
This Internet-Draft will expire on August 11, 2011.
Goyal, et al. Expires August 11, 2011 [Page 1]
Internet-Draft draft-ietf-roll-p2p-rpl-02 February 2011
Copyright Notice
Copyright (c) 2011 IETF Trust and the persons identified as the
document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents
(http://trustee.ietf.org/license-info) in effect on the date of
publication of this document. Please review these documents
carefully, as they describe your rights and restrictions with respect
to this document. Code Components extracted from this document must
include Simplified BSD License text as described in Section 4.e of
the Trust Legal Provisions and are provided without warranty as
described in the Simplified BSD License.
Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3
2. The Use Cases . . . . . . . . . . . . . . . . . . . . . . . . 4
3. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 5
4. Applicability . . . . . . . . . . . . . . . . . . . . . . . . 6
5. Functional Overview . . . . . . . . . . . . . . . . . . . . . 7
6. Propagation of Discovery Messages . . . . . . . . . . . . . . 8
6.1. The Route Discovery Option . . . . . . . . . . . . . . . . 9
6.2. Setting a DIO Carrying a Route Discovery Option . . . . . 10
6.3. Joining a Temporary DAG . . . . . . . . . . . . . . . . . 12
6.4. Processing a DIO Carrying a Route Discovery Option . . . . 12
6.5. Additional Processing of a DIO Carrying a Route
Discovery Option At An Intermediate Router . . . . . . . . 13
6.6. Additional Processing of a DIO Carrying a Route
Discovery Option At The Target Node . . . . . . . . . . . 14
7. Propagation of Discovery Reply Messages . . . . . . . . . . . 14
7.1. The Discovery Reply Object (DRO) . . . . . . . . . . . . . 15
7.1.1. The Source Route Option . . . . . . . . . . . . . . . 17
7.1.2. Processing a DRO At An Intermediate Router . . . . . . 19
7.2. DRO as Acknowledgement for Backward Source Routes . . . . 19
7.3. DRO as Carrier of Forward/Bidirectional Source Routes . . 19
7.4. Establishing Hop-by-hop Routes Via DRO . . . . . . . . . . 20
8. Security Considerations . . . . . . . . . . . . . . . . . . . 20
9. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 20
10. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 20
11. References . . . . . . . . . . . . . . . . . . . . . . . . . . 21
11.1. Normative References . . . . . . . . . . . . . . . . . . . 21
11.2. Informative References . . . . . . . . . . . . . . . . . . 22
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 22
Goyal, et al. Expires August 11, 2011 [Page 2]
Internet-Draft draft-ietf-roll-p2p-rpl-02 February 2011
1. Introduction
RPL [I-D.ietf-roll-rpl] provides multipoint-to-point (MP2P) routes
from nodes in a Low power and Lossy Network (LLN) to a sink node by
organizing the nodes along a Directed Acyclic Graph (DAG) rooted at
the sink. The nodes determine their position in the DAG so as to
optimize their routing cost on the path towards the DAG root. A node
advertises its position (the "rank") in the DAG by originating a
DODAG Information Object (DIO) message. The DIO message is sent via
link-local multicast and also includes information such as the DAG
root's identity, routing metrics/constraints
[I-D.ietf-roll-routing-metrics] and the objective function (OF) in
use. When a node joins the DAG, it determines its own rank in the
DAG based on that advertised by its neighbors and originates its own
DIO message.
RPL enables point-to-multipoint (P2MP) routing from a node to its
descendants in the DAG by allowing a node to send a Destination
Advertisement Object (DAO) upwards along the DAG. The DAO carries
potentially aggregated information regarding the descendants (and
other local prefixes) reachable through the node originating this
DAO.
RPL also provides mechanisms for point-to-point (P2P) routing between
any two nodes in the DAG. If the destination is within the source's
radio range, the source may directly send packets to the destination.
Otherwise, a packet's path from the source to the destination depends
on the storing/non-storing operation mode of the DAG. In non-storing
mode operation, only the DAG root maintains downward routing
information and hence a packet travels all the way to the DAG root,
which then sends it towards its destination using a source route. In
storing mode operation, if the destination is a DAG descendant and
the source maintains "downwards" hop-by-hop routing state about this
descendant, it can forward the packet to a descendant router closer
to the destination. Otherwise, the source sends the packet to a DAG
parent, which then applies the same set of rules to forward the
packet further. Thus, a packet travels up the DAG until it reaches a
node that knows of the downwards route to the destination and then it
travels down the DAG towards its destination. A node may or may not
maintain routing state about a descendant depending on whether its
immediate children send it such information in their DAOs. Thus, in
the best case with storing mode operation, the "upwards" segment of
the P2P route between a source and a destination ends at the first
common ancestor of the source and the destination. In the worst
case, the "upwards" segment would extend all the way to the DAG root.
In both storing and non-storing mode operations, if the destination
did not originate a DAO, the packet will travel all the way to the
DAG's root, where it will be dropped.
Goyal, et al. Expires August 11, 2011 [Page 3]
Internet-Draft draft-ietf-roll-p2p-rpl-02 February 2011
The P2P routing functionality available in RPL may be inadequate for
applications in the home and commercial building domains for the
following reasons [I-D.brandt-roll-rpl-applicability-home-building]
[RFC5826][RFC5867]:
o The need to maintain routes "proactively", i.e., every possible
destination in the DAG must originate a DAO.
o Depending on the network topology and OF/metrics in use, the
constraint to route only along a DAG may cause significantly
suboptimal P2P routes and severe traffic congestion near the DAG
root.
Thus, there is a need for a mechanism that provides source-initiated
discovery of P2P routes that are not along an existing DAG. This
document describes such a mechanism, complementary to the basic RPL
functionality.
The specified mechanism is based on a reactive on-demand approach,
which enables a node to discover one or more routes in either
direction between itself and another node in the LLN without any
restrictions regarding the existing DAG-membership of the links that
such routes may use. The discovered routes may be source routes or
hop-by-hop routes. The discovered routes may not be the best
available but are guaranteed to satisfy the desired constraints in
terms of the routing metrics and are thus considered "good enough"
from the application's perspective.
A complementary functionality, necessary to help decide whether to
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
such functionality, described in [I-D.goyal-roll-p2p-measurement],
can be used to determine the metric constraints for use in the route
discovery mechanism described in this document.
2. The Use Cases
The mechanisms described in this document are intended to be employed
as complementary to RPL in specific scenarios that need point-to-
point (P2P) routes between arbitrary routers.
One use case, common in a home environment, involves a remote control
(or a motion sensor) that suddenly needs to communicate with a lamp
module, whose network address is a-priori known. In this case, the
source of data (the remote control or the motion sensor) must be able
to discover a route to the destination (the lamp module) "on demand".
Goyal, et al. Expires August 11, 2011 [Page 4]
Internet-Draft draft-ietf-roll-p2p-rpl-02 February 2011
Another use case, common in a large commercial building environment,
involves a large LLN deployment where P2P communication along a
particular DAG among hundreds (or thousands) of routers creates
severe traffic congestion near that DAG's root, and thus routes
across this DAG are desirable.
The use cases also include scenarios where energy or latency
constraints are not satisfied by the P2P routes along a DAG because
they involve traversing many more intermediate routers than necessary
to reach the destination.
3. Terminology
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and
"OPTIONAL" in this document are to be interpreted as described in
[RFC2119].
Additionally, this document uses terminology from
[I-D.ietf-roll-terminology] and [I-D.ietf-roll-rpl]. Specifically,
the term node refers to an RPL router or an RPL host as defined in
[I-D.ietf-roll-rpl]. This document introduces the following terms:
Origin : The RPL node initiating the route discovery. The origin
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
discovered.
Intermediate Router: An RPL router that is neither the origin nor the
target.
Forward Route: A route from the origin to the target.
Backward Route: A route from the target to the origin.
Bidirectional Route: A route that can carry traffic in both
directions.
Source Route: A complete and ordered list of routers that can be used
by a packet to travel from a source node to a destination node. Such
source routes can be carried by a packet in a Type 4 Routing Header
[I-D.ietf-6man-rpl-routing-header].
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.
Goyal, et al. Expires August 11, 2011 [Page 5]
Internet-Draft draft-ietf-roll-p2p-rpl-02 February 2011
Propagation Constraints: The constraints on the routing metrics
[I-D.ietf-roll-routing-metrics] that MUST be satisfied before an
intermediate router or the target will process the Route Discovery
Option (defined in this document) contained inside a DODAG
Information Object (DIO).
Route Constraints: Additional constraints on the routing metrics
[I-D.ietf-roll-routing-metrics] that the target MUST enforce on the
received DIOs.
4. Applicability
The route discovery mechanism, described in this document, may be
invoked by an origin when no route exists between itself and the
target or when the existing routes do not satisfy the desired
performance requirements. The mechanism is designed to discover one
or more "good enough" routes in either direction between an origin
and a target. In some application contexts, the metric constraints
that the discovered routes must satisfy are intrinsically known or
can be specified by the application. For example, an origin that
expects a target to be less than 5 hops away may use "hop-count < 5"
as the propagation or route constraint. In other application
contexts, the origin may need to measure the cost of an existing
route to the target to determine the propagation/route constraints.
For 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 that the origin decides, as the propagation/route
constraint. The functionality required to measure the cost of an
existing route between the origin and the target is described in
[I-D.goyal-roll-p2p-measurement]. In case, there is no existing
route between the origin and target or the cost measurement for the
existing route fails, the origin will have to guess the propagation/
route constraints used in the initial route discovery. Once, the
initial route discovery succeeds or fails, the origin will have a
better estimate for the constraints to be used in the subsequent
route discovery.
This document describes an on-demand discovery mechanism for P2P
routes that is complementary to the proactive routes offered by RPL
base functionality. The mechanism described in this document may
result in discovery of better P2P routes than the ones available
along a DAG designed to optimize routing cost to the DAG's root. The
improvement in route quality depends on a number of factors including
the network topology, the routing metrics in use and the prevalent
conditions in the network. A network designer may take in
consideration both the benefits (potentially better routes; no need
to maintain routes proactively) and costs (control messages generated
Goyal, et al. Expires August 11, 2011 [Page 6]
Internet-Draft draft-ietf-roll-p2p-rpl-02 February 2011
during the route discovery process) when using this mechanism.
5. Functional Overview
This section contains a high level description of the route discovery
mechanism proposed in this document.
The route discovery begins with the origin generating a "Discovery"
message. The origin indicates in the message:
o The target;
o The relevant routing metrics;
o The constraints on how far the Discovery message may travel
(henceforth called the propagation constraints);
o Additional constraints that the target must enforce (henceforth
called the route constraints);
o The direction (forward: from the origin to the target; backward:
from the target to the origin; or bidirectional) of the route
being discovered;
o The desired number of routes (in case forward/bidirectional routes
are being discovered);
o Whether the route is a source route or a hop-by-hop one.
The Discovery message propagates via IPv6 link-local multicast with a
receiving router discarding the message if it does not satisfy the
propagation constraints or if the hop-by-hop routes are desired and
the router cannot store the state for such a route. As a copy of the
Discovery message travels towards the target, it accumulates the
relevant routing metric values as well as the route it takes. When
the target receives a Discovery message, it applies both the
propagation constraints and the route constraints on the routing
metrics inside the Discovery message. Thus, the discovered routes
satisfy both the propagation constraints as well as the route
constraints, although the propagation of Discovery messages is guided
by propagation constraints alone. Using only a subset of the
constraints as propagation constraints simplifies the operation of
intermediate routers, an important consideration in many LLN
application domains [RFC5826][RFC5867].
The route discovery process may result in the discovery of several
routes. This document does not specify how the target selects routes
Goyal, et al. Expires August 11, 2011 [Page 7]
Internet-Draft draft-ietf-roll-p2p-rpl-02 February 2011
among the ones discovered. Example selection methods include
selecting routes as they are discovered or selecting the best routes
discovered over a certain time period.
If the origin had requested the discovery of backward source-routes,
the target caches one or more discovered source-routes.
Additionally, the target sends one or more "Discovery Reply" messages
to the origin to acknowledge the discovery of these routes.
If the origin had requested the discovery of "n" forward source-
routes, the target sends "n" discovered source-routes it selects to
the origin in one or more Discovery Reply messages.
If the origin had requested the discovery of "n" bidirectional
source-routes, the target caches "n" discovered source-routes it
selects and also sends these routes to the origin in one or more
Discovery Reply messages.
If the origin had requested the discovery of "n" forward/backward/
bidirectional hop-by-hop routes, the target sends out a Discovery
Reply message to the origin for each one of the "n" discovered routes
it selects. The Discovery Reply message travels towards the origin
along the discovered route. As this message travels towards the
origin, it establishes appropriate forward/backward routing state in
the routers on the path.
6. Propagation of Discovery Messages
RPL uses DIO message propagation to build a DAG. The DIO message
travels via IPv6 link-local multicast. Each node joining the DAG
determines a rank for itself and ignores the subsequent DIO messages
received from lower (higher in numerical value) ranked neighbors.
Thus, the DIO messages propagate outward from the DAG root rather
than return inward towards the DAG root. The DIO message generation
at a node is further controlled by a trickle timer that allows a node
to avoid generating unnecessary messages [I-D.ietf-roll-trickle].
The link-local multicast based propagation, trickle-controlled
generation and the rank-based poisoning of messages traveling in the
wrong direction (towards the DAG root) provide powerful incentives to
use the DIO message as the Discovery message and propagate the DIO/
Discovery message by creating a "temporary" DAG. Such an approach
also allows reuse of the routing metrics, objective function and
packet forwarding framework developed for RPL. The routing metrics
used for the creation of this temporary DAG SHOULD be same as (or be
a subset of) the routing metrics being used for route discovery.
Similarly, the objective function, used for rank calculation in the
temporary DAG, SHOULD be same as the objective function that
Goyal, et al. Expires August 11, 2011 [Page 8]
Internet-Draft draft-ietf-roll-p2p-rpl-02 February 2011
determines the aggregated cost of a route when limited to the routing
metrics being used for temporary DAG creation.
The propagation constraints limit the spread of the temporary DAG.
The temporary DAG restricts the network topology within which the
route discovery takes place. The routes accumulated by the DIOs lie
within this restricted topology and implicitly satisfy the
propagation constraints. As the target receives a DIO, it
additionally applies the route constraints on the accumulated route.
Thus, for successful route discovery, the propagation constraints and
the route constraints MUST be compatible. The division of the
overall constraints in the two categories is an implementation
specific decision. If desired, an implementation MAY consider all
the constraints as propagation constraints and keep the set of route
constraints empty.
6.1. The Route Discovery Option
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type = 9 | Option Length | D |H| N | L |O|Reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
| Target Address |
| |
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
| Metric Container |
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| OCP |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Figure 1: Format of the Route Discovery Option
In order to be used as a Discovery message, a DIO MUST carry a "Route
Discovery" option illustrated in Figure 1. A DIO MUST NOT carry more
than one Route Discovery options. A router MUST ignore the second
and subsequent Route Discovery options carried by a DIO. A Route
Discovery option consists of the following fields:
o Option Type = 0x09 (to be confirmed by IANA).
o Option Length = The length of Route Discovery option including any
Metric Container and OCP fields.
Goyal, et al. Expires August 11, 2011 [Page 9]
Internet-Draft draft-ietf-roll-p2p-rpl-02 February 2011
o D: A 2-bit field that indicates the direction of the desired
routes:
* D = 0x00: Forward;
* D = 0x01: Backward;
* D = 0x02: Bidirectional.
The D field also specifies the direction in which the link-level
metrics being used for route discovery should be measured.
o H: This flag, when set, indicates if hop-by-hop routes are
desired. The flag is cleared if source routes are desired.
o N: A 3-bit unsigned integer indicating the number of routes
desired. Used when forward or bidirectional routes are being
discovered.
o L: A 4-bit field containing an exponent of 2, such that 2 raised
to the power L specifies, in units of seconds, the minimum "Life
Time" of the temporary DAG, i.e., the minimum duration a router
joining the temporary DAG must maintain its membership in the DAG.
o O: This flag, when set, indicates that an OCP field is present in
the Route Discovery option.
o Target Address: The IPv6 address of the target.
o Metric Container: Contains the route constraints that the target
MUST apply. Any metric objects contained in this metric container
MUST be ignored.
o OCP: 16 bit unsigned integer. An optional field, present only if
the O flag is set, This field indicates the objective function
that MAY be used by the target to compare two discovered routes.
6.2. Setting a DIO Carrying a Route Discovery Option
A DIO message that carries a Route Discovery option MUST set the Base
Object, described in [I-D.ietf-roll-rpl], in the following manner:
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
different RPLInstanceID values are used in two or more concurrent
route discoveries it initiates.
Goyal, et al. Expires August 11, 2011 [Page 10]
Internet-Draft draft-ietf-roll-p2p-rpl-02 February 2011
o Grounded (G) Flag: MUST be cleared since the objective of DAG
formation is propagation of Route Discovery option. This DAG is
temporary in nature and is not used for routing purpose.
o Destination Advertisement Supported (A) Flag: MUST be cleared for
same reasons as described above.
o Destination Advertisement Trigger (T) Flag: MUST be cleared.
o Mode of Operation (MOP): This document suggests a new value (0x04)
for this field (to be confirmed by IANA).
o DODAGPreference (Prf): TBD
o Destination Advertisement Trigger Sequence Number (DTSN): TBD
o DODAGID: IPv6 address of the origin.
The other fields in the Base Object are set as per the rules
described in [I-D.ietf-roll-rpl].
The DODAG Configuration option, carried in the DIO message, specifies
the parameters for the trickle timer operation that governs the
generation of DIO messages by routers joining the temporary DAG. The
future versions of this document will specify the default values to
be used for these parameters. The other fields defined in the DODAG
Configuration option are set as follows:
o The MaxRankIncrease field MUST be set to 0 to disable local repair
of the temporary DAG.
o This document RECOMMENDS a value 1 for the MinHopRankInc field.
o Objective Code Point (OCP): The OCP to be used for temporary DAG
formation. The objective function used for temporary DAG
formation SHOULD be compatible with the objective function to
determine the aggregated cost of a discovered route.
A DIO, that contains a Route Discovery option, MUST specify the
propagation constraints in one or more Metric Container options
placed outside the Route Discovery option. As mentioned before, the
route constraints are listed in the Metric Container option placed
inside the Route Discovery option. The routing metrics being used
for temporary DAG formation SHOULD be same as or a subset of the
routing metrics being used for route discovery. These routing
metrics MUST be placed in the Metric Container options placed outside
the Route Discovery option. Any link-level metrics being used for
route discovery MUST be measured in the direction indicated by the D
Goyal, et al. Expires August 11, 2011 [Page 11]
Internet-Draft draft-ietf-roll-p2p-rpl-02 February 2011
field in Route Discovery option. Any metric object contained inside
the Metric Container inside the Route Discovery option MUST be
ignored.
A DIO, carrying a Route Discovery option, MUST NOT carry any Route
Information or Prefix Information options described in
[I-D.ietf-roll-rpl].
6.3. Joining a Temporary DAG
When a node joins a temporary DAG advertized by a DIO carrying the
Route Discovery option, it MUST maintain its membership in the DAG
for the Minimum Life Time duration listed in the Route Discovery
option. Maintaining membership in the DAG implies remembering:
o The RPLInstanceID, the DODAGID and the DODAGVersionNumber for the
temporary DAG;
o The node's rank in the temporary DAG as well as the address of at
least one DAG parent;
o The propagation and the route constraints being used;
o In case of intermediate routers, the values for the routing
metrics, along with the associated source route from the origin
untill this node (carried in a Record Route IPv6 Extension Header
proposed in [I-D.thubert-6man-reverse-routing-header]), contained
in the best DIO (in terms of the routing metrics and potentially
using the OCP specified in the DODAG Configuration option)
received so far.
Although the main purpose of a temporary DAG's existence is to
facilitate the propagation of the Route Discovery option, the
temporary DAG MAY also be used for the Discovery Reply Object
(defined in Section 7.1 to travel from the target to the origin.
Hence, a node in a temporary DAG SHOULD also remember the address of
at least one DAG parent that provides the best known path back to the
origin. A node SHOULD delete information about a temporary DAG once
the duration of its membership in the DAG has exceeded the DAG's
minimum life time.
6.4. Processing a DIO Carrying a Route Discovery Option
The rules for DIO processing and transmission, described in Section 7
of RPL [I-D.ietf-roll-rpl], apply to DIOs carrying a Route Discovery
option as well except as modified in this document.
The following rules for processing a DIO carrying a Route Discovery
Goyal, et al. Expires August 11, 2011 [Page 12]
Internet-Draft draft-ietf-roll-p2p-rpl-02 February 2011
Option apply to both intermediate routers and the target.
A node MUST discard a DIO with no further processing if:
o The DIO contains two or more Route Discovery options;
o The node can not evaluate one or more of the propagation
constraints listed in a Metric Container inside the DIO.
A node MUST discard a DIO with no further processing if any of the
following conditions are found to be true while processing a Route
Discovery option contained in that DIO:
o The H field is set, i.e., hop-by-hop routes are desired, and the
node chooses not to participate in a hop-by-hop route;
o The node cannot maintain its membership in the temporary DAG for
the minimum life time specified in the Route Discovery option.
A node MUST update the values of link-level routing metrics included
inside the DIO in accordance with the D field in the Route Discovery
option. If the D field is 0x00, i.e., the forward routes are being
discovered, any link-level routing metric MUST be measured in the
direction towards the node receiving the DIO. If the D field is
0x01, i.e., the backward routes are being discovered, any link-level
routing metric MUST be measured in the direction towards the node
originating the DIO. If the D field is 0x02, i.e., the bidirectional
routes are being discovered, any link-level routing metric MUST be
calculated so as to take in account the metric's value in both
directions. The rules for calculating bidirectional metric values
will be specified in a separate document.
6.5. Additional Processing of a DIO Carrying a Route Discovery Option
At An Intermediate Router
An intermediate router MUST process a received DIO, carrying a Route
Discovery option, in accordance with the following rules.
An intermediate router MUST discard the DIO with no further
processing if the routing metric values do not satisfy one or more
propagation constraints listed in the DIO. The router MAY check the
route constraints listed inside the Route Discovery option and
discard the DIO with no further processing if these constraints are
not met.
An intermediate router MUST determine if this DIO is the best it has
received so far for this temporary DAG in terms of the routing
metrics (potentially using the OCP in the DODAG Configuration
Goyal, et al. Expires August 11, 2011 [Page 13]
Internet-Draft draft-ietf-roll-p2p-rpl-02 February 2011
object). If yes, the intermediate router MUST remember the routing
metric values contained in this DIO along with the route travelled by
the DIO so far and reset the trickle timer associated with the
temporary DAG.
When the trickle timer associated with the temporary DAG fires, an
intermediate router MUST generate a new DIO for this temporary DAG
carrying the Route Discovery option, the best metric values it knows
and the source route associated with these values (in a Record Route
IPv6 extension header [I-D.thubert-6man-reverse-routing-header]).
6.6. Additional Processing of a DIO Carrying a Route Discovery Option
At The Target Node
A node MUST process a received DIO, carrying a Route Discovery option
that lists this node as the target, in accordance with the following
rules.
A target MUST discard the DIO with no further processing if it can
not evaluate the route constraints listed inside the Route Discovery
option or if the routing metric values do not satisfy one or more of
the propagation and route constraints.
Otherwise, the target considers the source route accumulated by the
received DIO as one of the discovered routes. This document does not
prescribe a particular method for selecting routes among the
discovered ones. Suppose the Route Discovery option requires 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" routes it discovers or selecting the "n" best routes
discovered over a certain time period, potentially using the OCP
specified in the Route Discovery option for route comparison.
After selecting one or more discovered routes, the target MUST send
one or more RPL Control Messages carrying a Discovery Reply Object
(defined in the next section) back to the origin (identified by the
DODAGID field in the DIO Base Object) as specified in Section 7.
A target MUST NOT forward a DIO carrying a Route Discovery option any
further.
7. Propagation of Discovery Reply Messages
Goyal, et al. Expires August 11, 2011 [Page 14]
Internet-Draft draft-ietf-roll-p2p-rpl-02 February 2011
7.1. The Discovery Reply Object (DRO)
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 | D |H| N | Reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
| DODAGID(*) |
| |
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
| Target Address(*) |
| |
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Option(s)...
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+...
Figure 2: Format of the Discovery Reply Object (DRO)
This document defines a new RPL Control Message type, the Discovery
Reply Object (DRO) with code 0x04 (to be confirmed by IANA), that
serves one of the following functions:
o An acknowledgement from the target to the origin regarding the
successful discovery of backward source routes;
o Carries one or more forward/bidirectional source routes from the
target to the origin;
o Establishes one hop-by-hop forward/backward/bidirectional route as
it travels from the target to the origin.
The format for a Discovery Reply Object (DRO) is shown in Figure 2.
A DRO consists of the following fields:
o RPLInstanceID: The RPLInstanceID of the temporary DAG used for
route discovery.
o Version: The Version of the temporary DAG used for route
discovery.
o D: A 2-bit field that indicates the direction of the discovered
routes:
Goyal, et al. Expires August 11, 2011 [Page 15]
Internet-Draft draft-ietf-roll-p2p-rpl-02 February 2011
* D = 0x00: Forward;
* D = 0x01: Backward;
* D = 0x02: Bidirectional.
This field has the same value as the corresponding field in the
Route Discovery option.
o H: A flag that is set if the DRO is establishing an hop-by-hop
route. If this flag is set, the DRO MUST travel from the target
to the origin along the hop-by-hop route being established and
MUST include one Source Route option (defined in Section 7.1.1)
that contains the remaining routers on this route (as described in
Section 7.4). Since the state that a node needs to maintain
regarding a hop-by-hop route includes the RPLInstanceID, the
DODAGID and the IPv6 address of the route's destination, a DRO
with H flag set MUST also include:
* The DODAGID of the temporary DAG used for route discovery; and
* The Target Address if the hop-by-hop route is forward or
bidirectional.
The H flag MUST be clear if the DRO carries (or is an
acknowledgement for the discovery of) one or more source routes
contained in the Source Route options. The target can unicast
such a DRO to the origin or send it along the temporary DAG used
for route discovery. If the DRO is unicast to the origin, it MUST
NOT include the DODAGID and Target Address fields. If the DRO is
sent along the temporary DAG, it MUST include the DODAGID field
and MUST NOT include the Target Address field.
o N: A 3-bit field that indicates the number of source routes
carried or acknowledged in the DRO. This field MUST have value 1
if the DRO is establishing a hop-by-hop route.
o Reserved: These bits are reserved for future use. These bits MUST
be set to zero on transmission and MUST be ignored on reception.
o DODAGID: The DODAGID of the temporary DAG used for route
discovery. The DODAGID also identifies the origin. This field
MUST be present in the DRO if the H flag is set or if the H flag
is clear but the DRO needs to travel along the temporary DAG.
Otherwise, this field need not be present in the DRO. The
RPLInstanceID, the Version and the DODAGID together uniquely
identify the temporary DAG used for route discovery and can be
copied from the Base Object of the DIO advertizing the temporary
Goyal, et al. Expires August 11, 2011 [Page 16]
Internet-Draft draft-ietf-roll-p2p-rpl-02 February 2011
DAG.
o Target Address: The IPv6 address of the target generating the
Discovery Reply Object. This field MUST be present in the DRO if
the H flag is set and the hop-by-hop route being established is
forward or bidirectional.
o Options: The Discovery Reply Object MAY carry up to N Source Route
options (defined in the next section) with each such option
carrying a source route and optionally followed by a Metric
Container option that lists the aggregated values for the routing
metrics for the source route.
7.1.1. The Source Route Option
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type = 10 | Option Length | Compr | Pad | D | Resvd |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
. Address[1..n] .
. .
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Figure 3: Format of the Source Route Option
The Source Route option, illustrated in Figure 3, carries a source
route. When a Source Route option carries a complete source route
between the origin and the target, it MAY be immediately followed by
a Metric Container option that contains the aggregated values of the
routing metrics for this source route.
A Source Route option consists of the following fields:
o Option Type = 0x0A (to be confirmed by IANA).
o Option Length = Variable, depending on the size of the Addresses
vector.
o Compr: 4-bit unsigned integer indicating the number of prefix
octets that are elided from each address. For example, Compr
value will be 0 if full IPv6 addresses are carried in the
Addresses vector.
Goyal, et al. Expires August 11, 2011 [Page 17]
Internet-Draft draft-ietf-roll-p2p-rpl-02 February 2011
o Pad: 4-bit unsigned integer. Number of octets that are used for
padding between Address[n] and the end of the Source Route option.
o D: A 2-bit field that indicates the direction of the source route:
* D = 0x00: Forward, i.e., from the origin to the target;
* D = 0x01: Backward i. e., from the target to the origin;
* D = 0x02: Bidirectional.
Note that the D field in a Source Route option is independent from
the D field in the DRO containing the Source Route option.
o Resvd: These bits are reserved for future use. These bits MUST be
set to zero on transmission and MUST be ignored on reception.
o Address[1..n]: Vector of addresses, numbered 1 to n. Each vector
element has size (16 - Compr) octets.
Note that the format of the Source Route option is very similar to
that of proposed Type 4 Routing Header
[I-D.ietf-6man-rpl-routing-header].
A common network configuration for an RPL domain is that all routers
within an LLN share a common prefix. The Source Route option uses
the Compr field to allow compaction of the Address[1..n] vector when
all entries share the same prefix as the DODAGID or the Target
Address of the encapsulating Discovery Reply Object. The shared
prefix octets are not carried within the Source Route option and each
entry in Address[1..n] has size (16 - Compr) octets. When Compr is
non-zero, there may exist unused octets between the last entry,
Address[n], and the end of the Source Route option. The Pad field
indicates the number of unused octets that are used for padding.
Note that when Compr is 0, Pad MUST be null and carry a value 0.
The Source Route option MUST NOT specify a path that visits a router
more than once. When generating a Source Route option, the target
may not know the mapping between IPv6 addresses and routers.
Minimally, the target MUST ensure that:
o The IPv6 Addresses do not appear more than once;
o The IPv6 addresses of the origin and the target do not appear in
the Address vector.
Multicast addresses MUST NOT appear in a Source Route option.
Goyal, et al. Expires August 11, 2011 [Page 18]
Internet-Draft draft-ietf-roll-p2p-rpl-02 February 2011
7.1.2. Processing a DRO At An Intermediate Router
When an intermediate router receives a DRO with a clear H flag, it
MUST forward the DRO to a parent node in the temporary DAG.
When an intermediate router receives a DRO that has H flag set and
contains multiple Source Route options, the router MUST drop the DRO
with no further processing.
When an intermediate router receives a DRO that has H flag set and
contains a single Source Route option, the router processes the DRO
as described in Section 7.4.
7.2. DRO as Acknowledgement for Backward Source Routes
After selecting one or more backward source routes, a target MAY send
a DRO message to the origin as an acknowledgement for the discovered
routes. A DRO, serving as an acknowledgement for backward source
route discovery, has its D field set to 0x01 (indicating backward)
while the H flag is cleared (indicating source route). The N field
is set to indicate the number of discovered backward source routes
being acknowledged. Such a DRO message MUST NOT contain any option.
The target MAY unicast this DRO message to the origin or it MAY
forward the DRO message to a parent in the temporary DAG. The target
should take into consideration the minimum life time of the temporary
DAG when deciding to use it to send the DRO to the origin.
7.3. DRO as Carrier of Forward/Bidirectional Source Routes
The target MUST convey the discovered forward/bidirectional source
routes to the origin via the Source Route options inside one or more
DRO messages. Such a DRO message MUST have its D field set to 0x00
(if it carries forward routes) or 0x02 (if its carries bidirectional
routes). Also, the H flag MUST be cleared and the N field MUST
indicate the number of Source Route options in the DRO. Each Source
Route option inside the DRO MAY immediately be followed by a Metric
Container option that carries the aggregated values of the relevant
routing metrics for this source route.
The target MAY unicast this DRO message to the origin or it MAY
forward the DRO message to a parent in the temporary DAG. The target
should take into consideration the minimum life time of the temporary
DAG when deciding to use it to send the DRO to the origin.
Goyal, et al. Expires August 11, 2011 [Page 19]
Internet-Draft draft-ietf-roll-p2p-rpl-02 February 2011
7.4. Establishing Hop-by-hop Routes Via DRO
In order to establish a hop-by-hop route, the target MUST send a DRO
message along the discovered route, which is specified in a Source
Route option. The D field in the DRO MUST reflect the direction of
the discovered route. The H bit in the DRO MUST be set and the DRO
MUST include the DODAGID field. If a forward or bidirectional hop-
by-hop route is being established, the DRO MUST include the Target
Address field as well. The N field in the DRO MUST be set to 1 and
the DRO MUST include exactly one Source Route option. The target
forwards the DRO to the next hop along the discovered route and
includes the discovered route, excluding itself and the origin,
inside the Source Route option in backward direction. Thus, the D
field in the Source Route option MUST be 0x01.
If the hop-by-hop route is in the backward direction, the target MUST
establish the hop-by-hop state for the route before sending the DRO
message. Such hop-by-hop state includes the RPLInstanceID, the
DODAGID and the route's destination ( in this case, the origin's
address or the DODAGID).
A router receiving a DRO message MUST drop the DRO if the router
cannot establish the hop-by-hop state for the route or if its own
address does not appear as the first element in the Address vector in
the Source Route option. Otherwise, the router MUST establish the
hop-by-hop state in the direction specified in the D field in the
DRO. The hop-by-hop state in the forward direction includes the
RPLInstanceID, the DODAGID and the target's address. The hop-by-hop
state in the backward direction includes the RPLInstanceID, the
DODAGID and the origin's address. After establishing the hop-by-hop
state, the router MUST remove its own address from the route
contained in the Source Route option and forward the DRO to the next
hop (Address[0] in the Source Route option).
8. Security Considerations
TBA
9. IANA Considerations
TBA
10. Acknowledgements
Authors gratefully acknowledge the contributions of the following
Goyal, et al. Expires August 11, 2011 [Page 20]
Internet-Draft draft-ietf-roll-p2p-rpl-02 February 2011
individuals (in alphabetical order) in the development of this
document: Dominique Barthel, Thomas Clausen, Richard Kelsey, Zach
Shelby, Pascal Thubert and JP Vasseur.
11. References
11.1. Normative References
[I-D.goyal-roll-p2p-measurement]
Goyal, M. and E. Baccelli, "A Mechanism to Measure the
Quality of a Point-to-point Route in a Low Power and Lossy
Network", draft-goyal-roll-p2p-measurement-01 (work in
progress), October 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-01 (work in progress),
October 2010.
[]
Hui, J., Vasseur, J., Culler, D., and V. Manral, "An IPv6
Routing Header for Source Routes with RPL",
draft-ietf-6man-rpl-routing-header-01 (work in progress),
October 2010.
[I-D.ietf-roll-routing-metrics]
Vasseur, J., Kim, M., Pister, K., Dejean, N., and D.
Barthel, "Routing Metrics used for Path Calculation in Low
Power and Lossy Networks",
draft-ietf-roll-routing-metrics-17 (work in progress),
January 2011.
[I-D.ietf-roll-rpl]
Winter, T., Thubert, P., Brandt, A., Clausen, T., Hui, J.,
Kelsey, R., Levis, P., Pister, K., Struik, R., and J.
Vasseur, "RPL: IPv6 Routing Protocol for Low power and
Lossy Networks", draft-ietf-roll-rpl-17 (work in
progress), December 2010.
[I-D.ietf-roll-trickle]
Levis, P., Clausen, T., Hui, J., Gnawali, O., and J. Ko,
"The Trickle Algorithm", draft-ietf-roll-trickle-08 (work
in progress), January 2011.
[]
Thubert, P., "Reverse Routing Header",
Goyal, et al. Expires August 11, 2011 [Page 21]
Internet-Draft draft-ietf-roll-p2p-rpl-02 February 2011
draft-thubert-6man-reverse-routing-header-00 (work in
progress), June 2010.
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119, March 1997.
11.2. Informative References
[I-D.brandt-roll-rpl-applicability-home-building]
Brandt, A., Baccelli, E., and R. Cragie, "Applicability
Statement: The use of RPL in Building and Home
Environments",
draft-brandt-roll-rpl-applicability-home-building-01 (work
in progress), November 2010.
[I-D.ietf-roll-terminology]
Vasseur, J., "Terminology in Low power And Lossy
Networks", draft-ietf-roll-terminology-04 (work in
progress), September 2010.
[RFC5826] Brandt, A., Buron, J., and G. Porcu, "Home Automation
Routing Requirements in Low-Power and Lossy Networks",
RFC 5826, April 2010.
[RFC5867] Martocci, J., De Mil, P., Riou, N., and W. Vermeylen,
"Building Automation Routing Requirements in Low-Power and
Lossy Networks", RFC 5867, June 2010.
Authors' Addresses
Mukul Goyal (editor)
University of Wisconsin Milwaukee
3200 N Cramer St
Milwaukee, WI 53201
USA
Phone: +1 414 2295001
Email: mukul@uwm.edu
Emmanuel Baccelli
INRIA
Phone: +33-169-335-511
Email: Emmanuel.Baccelli@inria.fr
URI: http://www.emmanuelbaccelli.org/
Goyal, et al. Expires August 11, 2011 [Page 22]
Internet-Draft draft-ietf-roll-p2p-rpl-02 February 2011
Anders Brandt
Sigma Designs
Emdrupvej 26A, 1.
Copenhagen, Dk-2100
Denmark
Phone: +45-29609501
Email: abr@sdesigns.dk
Robert Cragie
Gridmerge Ltd
89 Greenfield Crescent
Wakefield WF4 4WA
UK
Phone: +44-1924910888
Email: robert.cragie@gridmerge.com
Jerald Martocci
Johnson Controls
507 E Michigan St
Milwaukee, WI 53202
USA
Phone: +1 414-524-4010
Email: jerald.p.martocci@jci.com
Charles Perkins
Tellabs Inc.
charliep@computer.org
Goyal, et al. Expires August 11, 2011 [Page 23]