Internet Engineering Task Force M. Goyal, Ed.
Internet-Draft University of Wisconsin
Intended status: Experimental Milwaukee
Expires: November 14, 2011 E. Baccelli
INRIA
A. Brandt
Sigma Designs
R. Cragie
Gridmerge Ltd
J. Martocci
Johnson Controls
May 13, 2011
Reactive Discovery of Point-to-Point Routes in Low Power and Lossy
Networks
draft-ietf-roll-p2p-rpl-03
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 IPv6 router or host to discover and establish, on demand, one or
more routes to another IPv6 router or host in the LLN such that the
discovered routes meet specified constraints.
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 November 14, 2011.
Goyal, et al. Expires November 14, 2011 [Page 1]
Internet-Draft draft-ietf-roll-p2p-rpl-03 May 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 . . . . . . . . . . . . . . . . . . . . . 6
6. Propagation of Discovery Messages . . . . . . . . . . . . . . 8
6.1. The Route Discovery Option . . . . . . . . . . . . . . . . 9
6.2. Setting a DIO Carrying a Route Discovery Option . . . . . 12
6.3. Joining a Temporary DAG . . . . . . . . . . . . . . . . . 13
6.4. Changes to Trickle Operation For DIOs Carrying a Route
Discovery Option . . . . . . . . . . . . . . . . . . . . . 13
6.5. Processing a DIO Carrying a Route Discovery Option . . . . 14
6.6. Additional Processing of a DIO Carrying a Route
Discovery Option At An Intermediate Router . . . . . . . . 15
6.7. Additional Processing of a DIO Carrying a Route
Discovery Option At The Target Node . . . . . . . . . . . 15
7. Propagation of Discovery Reply Messages . . . . . . . . . . . 16
7.1. The Discovery Reply Object (DRO) . . . . . . . . . . . . . 17
7.2. Processing a DRO At An Intermediate Router . . . . . . . . 18
7.3. Processing a DRO At The Origin . . . . . . . . . . . . . . 19
8. Security Considerations . . . . . . . . . . . . . . . . . . . 20
9. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 20
10. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 20
11. References . . . . . . . . . . . . . . . . . . . . . . . . . . 20
11.1. Normative References . . . . . . . . . . . . . . . . . . . 20
11.2. Informative References . . . . . . . . . . . . . . . . . . 21
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 21
Goyal, et al. Expires November 14, 2011 [Page 2]
Internet-Draft draft-ietf-roll-p2p-rpl-03 May 2011
1. Introduction
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
organizing the routers along a Directed Acyclic Graph (DAG) rooted at
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
router 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 router 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 router to its
descendants in the DAG by allowing a router to send a Destination
Advertisement Object (DAO) upwards along the DAG. In non-storing
mode operation, a router's DAO contains a list of its preferred DAG
parents. The routers unicast their DAOs to the DAG root, which then
uses this information to arrive at source-routes from itself to the
individual routers. In storing mode operation, a router's DAO
carries potentially aggregated information regarding its descendants
and other local prefixes reachable through the router. The router
sends its DAO to a selected set of DAG parents, which then use this
information in their routing tables and in their own DAOs.
RPL also provides mechanisms for point-to-point (P2P) routing between
any two routers 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 the
"downwards" 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 router that knows of the downwards route to
the destination and then it travels down the DAG towards its
destination. A router 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
Goyal, et al. Expires November 14, 2011 [Page 3]
Internet-Draft draft-ietf-roll-p2p-rpl-03 May 2011
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.
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 need not be 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 router to discover one or more routes in either
direction between itself and another router 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.ietf-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.
Goyal, et al. Expires November 14, 2011 [Page 4]
Internet-Draft draft-ietf-roll-p2p-rpl-03 May 2011
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".
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]. 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 is both forward and backward.
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.
Hop-by-hop Route: The route characterized by each router on the route
Goyal, et al. Expires November 14, 2011 [Page 5]
Internet-Draft draft-ietf-roll-p2p-rpl-03 May 2011
using its routing table to determine the next hop on the route.
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 routes that meet the specified constraints 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 constraint. In other
application contexts, the origin may need to measure the cost 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
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
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
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 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
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"
Goyal, et al. Expires November 14, 2011 [Page 6]
Internet-Draft draft-ietf-roll-p2p-rpl-03 May 2011
message. The origin indicates in the message:
o The target;
o The relevant routing metrics;
o The constraints that the discovered route must satisfy. These
constraints also limit how far the Discovery message may travel;
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
towards the target accumulating the relevant routing metric values as
well as the route it takes. A receiving router (including the
target) discards the Discovery message if the accumulated routing
metric values do not satisfy the listed constraints. A router may
also discard the Discovery message 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
routes. This document does not specify how the target selects routes
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 a "Discovery Reply" message 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 the discovered source-routes to the origin
in "n" Discovery Reply messages, with one Discovery Reply message
carrying one discovered source-route.
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 "n" Discovery
Reply messages.
Goyal, et al. Expires November 14, 2011 [Page 7]
Internet-Draft draft-ietf-roll-p2p-rpl-03 May 2011
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 router 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 router is further controlled by a Trickle timer that allows a
router to avoid generating unnecessary messages [RFC6206]. 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. This document defines a new
RPL option, Route Discovery Option (RDO), which when carried inside a
DIO message identifies that message as doing P2P route discovery by
creating a temporary DAG as specified in this document.
The use of trickle timers to delay the propagation of DIO messages
may cause some nodes to generate these messages even when the desired
routes have already been discovered. In order to preempt the
generation of such unnecessary messages, the target may set a "stop"
bit in the Discovery Reply message (Section 7) to let the nodes in
the LLN know about the completion of the route discovery process.
Goyal, et al. Expires November 14, 2011 [Page 8]
Internet-Draft draft-ietf-roll-p2p-rpl-03 May 2011
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 | Compr | Rem |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
| Target |
| |
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
| Address[1..n] |
| |
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
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 (RDO) illustrated in Figure 1. A Discovery Reply
Object (DRO), defined in Section 7.1, MUST also carry a Route
Discovery Option. A DIO/DRO message MUST NOT carry more than one
Route Discovery Option. A router MUST discard a DIO/DRO if it
contains more than one Route 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;
* 0x02: Bidirectional.
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 field. Also, the IPv6 addresses
accumulated in the Address vector MUST be accessible in the
direction indicated by the D field. When the Route Discovery
Option is carried inside a DRO, this field MUST be set to zero on
Goyal, et al. Expires November 14, 2011 [Page 9]
Internet-Draft draft-ietf-roll-p2p-rpl-03 May 2011
transmission and ignored on reception.
o HopByHop (H): This flag, when set to 1, indicates that hop-by-hop
routes are desired. The flag is cleared when the source routes
are desired.
o Number of Routes (N): When the Route Discovery Option is being
carried inside a DIO:
* The value in this field plus one indicates the number of routes
desired.
* 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.
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
joining the temporary DAG must maintain its membership in the DAG.
The mapping between the values in this field and the minimum life
time of the temporary DAG is as follows:
* 0x00: 1 second;
* 0x01: 4 seconds;
* 0x02: 16 seconds;
* 0x03: 64 seconds;
Note that a router MAY detach from the temporary DAG sooner if it
receives a DRO message concerning this DAG with "stop" bit set.
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 Rem: When the Route Discovery Option is carried inside a DIO, this
field indicates the number of empty fields inside the Address
vector. When the Route Discovery Option is carried inside a DRO,
this field indicates the number of fields in the Address vector
Goyal, et al. Expires November 14, 2011 [Page 10]
Internet-Draft draft-ietf-roll-p2p-rpl-03 May 2011
yet to be visited.
o Target: The IPv6 address of the target after eliding Compr number
of prefix octets.
o Address[1..n]: A vector of IPv6 addresses representing a route
from the origin towards the target:
* Each element in the vector has size (16 - Compr) octets.
* The total number of elements inside the Address vector is given
by n = (Option Length - 4 - (16 - Compr))/(16 - Compr).
* When the Route Discovery Option is carried inside a DIO, the
Address vector is used to accumulate a route optimized in the
direction specified by the D field.
* The IPv6 addresses in the Address vector MUST be accessible in
the direction specified by the D field.
* The Address vector MUST carry the accumulated route such that
the first element in the Address vector contains the IPv6
address of the router next to the origin and so on.
* The origin and target addresses MUST NOT be included in the
Address vector.
* A router adding its address to the vector MUST ensure that its
address does not already exist in the vector. A router
specifying a complete route in the Address vector MUST ensure
that the vector does not contain any address more than once.
* The Address vector MUST NOT contain any multicast addresses.
* A DRO message travels from the target to the origin along a
route accumulated in the Address vector inside a Route
Discovery Option. Hence, the IPv6 addresses stored in the
Address vector MUST be accessible in the backward direction
also.
* 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.
Goyal, et al. Expires November 14, 2011 [Page 11]
Internet-Draft draft-ietf-roll-p2p-rpl-03 May 2011
6.2. Setting a DIO Carrying a Route Discovery Option
The Base Object in a DIO message carrying a Route Discovery Option
MUST be set 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.
o Version Number: MUST be set to zero. The temporary DAG used for
P2P route discovery does not exist long enough to have new
versions.
o Grounded (G) Flag: MUST be cleared since this DAG is temporary in
nature and MUST not be used for routing purpose.
o Mode of Operation (MOP), DTSN: These fields MUST be set to value 0
since this DAG does not support downward routing.
o DODAGPreference (Prf): This field MUST be set to value 0 (least
preferred).
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
fashion as per the rules described in [I-D.ietf-roll-rpl].
The DODAG Configuration option, carried in the DIO message, MUST be
set in the following manner:
o MaxRankIncrease: This field MUST be set to 0 to disable local
repair of the temporary DAG.
o The other fields in the DODAG Configuration option, including the
Trickle timer parameters and the OCP, can be set in the desired
fashion as per the rules described in [I-D.ietf-roll-rpl].
A DIO, carrying a Route Discovery Option, MUST NOT carry any Route
Information or Prefix Information options described in
[I-D.ietf-roll-rpl].
The origin MUST NOT originate a DIO with a particular RPLInstanceID
for the P2P route discovery more than once in a given
P2PDISCOVERY_TIMEOUT duration.
Goyal, et al. Expires November 14, 2011 [Page 12]
Internet-Draft draft-ietf-roll-p2p-rpl-03 May 2011
6.3. Joining a Temporary DAG
When a router joins a temporary DAG advertized by a DIO carrying a
Route Discovery Option, it SHOULD maintain its membership in the DAG
for the suggested 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 router's rank in the temporary DAG;
o The best values of the routing metrics, along with the associated
route from the origin untill this router (carried inside the Route
Discovery Option) in the DIOs received so far.
The only purpose of a temporary DAG's existence is to facilitate the
propagation of the Discovery messages. The temporary DAG MUST NOT be
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
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.
6.4. Changes to Trickle Operation For DIOs Carrying a Route Discovery
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
perspective of P2P route discovery, are as follows:
Goyal, et al. Expires November 14, 2011 [Page 13]
Internet-Draft draft-ietf-roll-p2p-rpl-03 May 2011
o A router should generate a DIO quickly when it has a better route
to advertise.
o The DIO generation policy must not lead to a DIO storm.
To meet these requirements,
o A DIO, carrying a Route Discovery Option, SHOULD be suppressed if
the router does not have a better route to advertise. This rule
applies irrespecive of the values of the redundancy constant and
the number of "consistent" DIOs received in the preceding Trickle
interval.
o A DIO, carrying a Route Discovery Option, SHOULD NOT be suppressed
if the router has a better route to advertise. This rule applies
irrespecive of the values of the redundancy constant and the
number of "consistent" DIOs received in the preceding Trickle
interval.
o A router SHOULD consider the receipt of a DIO, that leads to an
improvement in the aggregated routing metrics values the router
could advertise for this temporary DAG, as an "inconsistency" and
hence reset the Trickle timer governing the DIO generation for
this temporary DAG [RFC6206].
6.5. Processing a DIO Carrying a Route Discovery Option
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
option as well except as modified in this document.
The following rules for processing a DIO carrying a Route Discovery
Option apply to both intermediate routers and the target.
A router SHOULD update the values of link-level routing metrics
included inside the DIO in the direction indicated by 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
SHOULD 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 SHOULD 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 SHOULD be calculated so as to take in account
the metric's value in both directions.
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
Goyal, et al. Expires November 14, 2011 [Page 14]
Internet-Draft draft-ietf-roll-p2p-rpl-03 May 2011
the routing metric values do not satisfy one or more of the mandatory
constraints.
6.6. Additional Processing of a DIO Carrying a Route Discovery Option
At An Intermediate Router
When an intermediate router receives a DIO containing a Route
Discovery Option, it MUST determine if this DIO is the best it has
received so far for this temporary DAG in terms of the routing
metrics listed in the DIO. If yes, the router MUST add its own IPv6
address to the accumulated route at location Address[n-Rem+1] inside
the Route Discovery Option and stores this route in memory along with
the routing metrics associated with this route. When a router
includes itself in an accumulated route, it MUST ensure that the IPv6
address added to the route is accessible in both the backward
direction and the direction indicated by the D field in the Route
Discovery Option. The router MUST also reset the Trickle timer
associated with the temporary DAG whenever it updates the best route
it has seen so far. When the Trickle timer fires, an intermediate
router checks whether DIO generation is suppressed or not as per
Section 6.4. If DIO generation is allowed, the router generates a
new DIO DIO for this temporary DAG carrying the best routing metric
values it knows and a Route Discovery Option that carried in its
Address vector the best route the router has seen so far.
6.7. Additional Processing of a DIO Carrying a Route Discovery Option
At The Target Node
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.
Goyal, et al. Expires November 14, 2011 [Page 15]
Internet-Draft draft-ietf-roll-p2p-rpl-03 May 2011
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
forward hop-by-hop route (D=0x00, H=1), 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.
The target MAY include a Metric Container Option in the DRO. This
Metric Container contains the end-to-end routing metric values for
the route specified in the Address vector inside the Route Discovery
Option contained in the DRO message.
A target MUST NOT forward a DIO carrying a Route Discovery option any
further.
7. Propagation of Discovery Reply Messages
Goyal, et al. Expires November 14, 2011 [Page 16]
Internet-Draft draft-ietf-roll-p2p-rpl-03 May 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 |S| Reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
| DODAGID |
| |
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| 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 Acknowledge to the origin the successful discovery of backward
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
it travels from the target to the origin.
A DRO message also serves the function of letting the routers in 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
DRO message MUST carry one Route Discovery Option and travel from the
target to the origin via link-local multicast along the route
specified in the Route Discovery Option.
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.
Goyal, et al. Expires November 14, 2011 [Page 17]
Internet-Draft draft-ietf-roll-p2p-rpl-03 May 2011
o Stop (S): This flag, when set by the target, indicates that the
route discovery being performed by the temporary DAG (identified
by the RPLInstanceID, DODAGID and VersionNumber field inside the
DRO) is over. The routers, receiving such a DRO, SHOULD cancel
any pending DIO transmissions for this DAG and MAY detach from the
temporary DAG immediately. The target SHOULD set the stop flag in
a DRO when it does not need to receive any more routes via DIOs.
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. The
RPLInstanceID, the Version and the DODAGID together uniquely
identify the temporary DAG used for route discovery and can be
copied from the DIO message advertizing the temporary DAG.
o Options: The DRO message MUST carry one Route Discovery Option
that MUST specify a complete route between the target and the
origin. The DRO message MAY carry a Metric Container Option that
contains the aggregated routing metrics values for the route
specified in Route Discovery Option.
7.2. Processing a DRO At An Intermediate Router
When a router receives a DRO message that does not list its IPv6
address in the DODAGID field, the router MUST process the received
message in the following manner:
o If the stop flag inside the received DRO is set and the router
currently belongs to the temporary DAG identified by the
(RPLInstanceID, DODAGID and Version Number fields of the) DRO, the
router SHOULD cancel any pending DIO transmissions for this
temporary DAG. Additionally, the router MAY detach from the
temporary DAG immediately.
o An intermediate router MUST ignore any Metric Container Option
contained in the DRO message.
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
carried in the Route Discovery Option. In this case, the router
MUST do the following:
* If the H flag inside the Route Discovery Option inside the DRO
message is set, the router MUST store state for the P2P route
carried inside the Route Discovery Option. This state consists
of:
Goyal, et al. Expires November 14, 2011 [Page 18]
Internet-Draft draft-ietf-roll-p2p-rpl-03 May 2011
+ The RPLInstanceID and the DODAGID fields of the DRO.
+ The route's destination, either origin (identified by
DODAGID field in DRO) or target (identified by Target field
in Route Discovery Option).
+ The IPv6 address of the next hop.
For routes in the forward direction (D=0x00 in the Route
Discovery Option), the route's destination is the target and
the next hop address is 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 backward
direction (D=0x01 in the Route Discovery Option), the route's
destination is the origin and the next hop address is
Address[Rem-1] (unless Rem = 1, in which case the origin itself
is the next hop). If the route is bidirectional (D = 0x02 in
the Route Discovery Option), two routing states are created,
one in forward direction and one in backward direction.
* The router MUST decrement the Rem field inside the Route
Discovery Option and send the DRO further via link-local
multicast.
7.3. Processing a DRO At The Origin
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
corresponding P2P route discovery and processes the Route Discovery
Option contained in the DRO in the following manner.
If the Route Discovery Option identifies the discovered route as a
backward source/hop-by-hop route (D=0x01, H=0 or H=1), the origin
considers the DRO receipt as the acknowledgement of successful
completion of the P2P route discovery process.
If the Route Discovery Option identifies the discovered route as a
forward/bidirectional source route (D=0x00 or 0x02, H=0), the origin
stores the discovered route, contained in the Address vector, in its
memory.
If the Route Discovery Option identifies the discovered route as a
forward/bidirectional hop-by-hop route (D=0x00 or 0x02, H=1), the
origin stores the state for the discovered route in forward
direction, in the manner described in Section 7.2, in its memory.
If the received DRO message contains a Metric Container Option as
well, the origin MAY store the values of the routing metrics
Goyal, et al. Expires November 14, 2011 [Page 19]
Internet-Draft draft-ietf-roll-p2p-rpl-03 May 2011
associated with the discovered route in its memory. This information
may be useful in formulating the constraints for any future P2P route
discovery to the target.
8. Security Considerations
TBA
9. IANA Considerations
TBA
10. Acknowledgements
Authors gratefully acknowledge the contributions of the following
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.ietf-roll-p2p-measurement]
Goyal, M., Baccelli, E., Brandt, A., Cragie, R., Martocci,
J., and C. Perkins, "A Mechanism to Measure the Quality of
a Point-to-point Route in a Low Power and Lossy Network",
draft-ietf-roll-p2p-measurement-00 (work in progress),
April 2011.
[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-19 (work in progress),
March 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-19 (work in
progress), March 2011.
Goyal, et al. Expires November 14, 2011 [Page 20]
Internet-Draft draft-ietf-roll-p2p-rpl-03 May 2011
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119, March 1997.
[RFC6206] Levis, P., Clausen, T., Hui, J., Gnawali, O., and J. Ko,
"The Trickle Algorithm", RFC 6206, March 2011.
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-05 (work in
progress), March 2011.
[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 November 14, 2011 [Page 21]
Internet-Draft draft-ietf-roll-p2p-rpl-03 May 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
Goyal, et al. Expires November 14, 2011 [Page 22]