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]