Internet Engineering Task Force M. Goyal, Ed. Internet-Draft University of Wisconsin Milwaukee Intended status: Informational E. Baccelli, Ed. Expires: December 16, 2010 INRIA P2P. Team June 14, 2010 Reactive Discovery of Point-to-Point Routes in Low Power and Lossy Networks draft-dt-roll-p2p-rpl-01 Abstract This document describes a mechanism to discover and establish "on demand" one or more routes between two routers in a low power and lossy network. 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 December 16, 2010. Copyright Notice Copyright (c) 2010 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 Goyal, et al. Expires December 16, 2010 [Page 1] Internet-Draft draft-dt-roll-p2p-rpl-01 June 2010 described in the Simplified BSD License. Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 2. Targeted Use Cases . . . . . . . . . . . . . . . . . . . . . . 4 3. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 4 4. Functional Overview . . . . . . . . . . . . . . . . . . . . . 5 5. Propagation of Discovery Messages . . . . . . . . . . . . . . 7 5.1. The Route Discovery Option . . . . . . . . . . . . . . . . 7 5.2. Setting a DIO Carrying a Route Discovery Option . . . . . 9 5.3. Processing of a DIO Carrying a Route Discovery Option At An Intermediate Node . . . . . . . . . . . . . . . . . 10 5.4. Processing of a DIO Carrying a Route Discovery Option At The Target Router . . . . . . . . . . . . . . . . . . . 12 6. Propagation of Discovery Reply Messages . . . . . . . . . . . 13 6.1. The Discovery Reply Object (DRO) . . . . . . . . . . . . . 13 6.1.1. The Source Route Option . . . . . . . . . . . . . . . 15 6.2. DRO as Acknowledgement for Backward Source Routes . . . . 16 6.3. DRO as Carrier of Forward/Bidirectional Source Routes . . 17 6.4. Establishing Hop-by-hop Routes Via DRO . . . . . . . . . . 17 7. Security Considerations . . . . . . . . . . . . . . . . . . . 18 8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 18 9. Authors and Contributors . . . . . . . . . . . . . . . . . . . 18 10. References . . . . . . . . . . . . . . . . . . . . . . . . . . 18 10.1. Normative References . . . . . . . . . . . . . . . . . . . 18 10.2. Informative References . . . . . . . . . . . . . . . . . . 18 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 19 Goyal, et al. Expires December 16, 2010 [Page 2] Internet-Draft draft-dt-roll-p2p-rpl-01 June 2010 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 router by organizing the routers along a Directed Acyclic Graph (DAG) rooted at the sink. The DAG root initiates the DAG formation by originating a DODAG Information Object (DIO) message. The DIO message is sent via link-local multicast and carries information about the originating router's position (the "rank") in the DAG. On receiving DIO messages sent by its neighbors, a router determines its own "rank" in the DAG 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. The DAO carries the aggregated information regarding the descendants (and other local prefixes) reachable through the originating router. 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 "range", the source may directly send packets to the destination. Otherwise, if the destination is a DAG descendant and the source maintains "downwards" routing state about this descendant, it can forward the packet along this route. 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 and whether the router can store this information. Thus, in the best case scenario, 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's root. 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 suffers from several shortcomings [I-D.brandt-roll-rpl-applicability-home-building]: o The need to maintain routes "proactively", i.e. every possible destination in the DAG must originate a DAO. o The constraint to route only along a DAG potentialy leading to significantly suboptimal P2P routes and traffic congestion near the DAG root. Goyal, et al. Expires December 16, 2010 [Page 3] Internet-Draft draft-dt-roll-p2p-rpl-01 June 2010 These shortcomings are not compatible with the home and commercial building domain application requirements described in [RFC5826] and [I-D.ietf-roll-building-routing-reqs]. Such applications require a mechanism providing source-initiated discovery of P2P routes that are not along a DAG. This document thus describes such a mechanism, complementary to the basic RPL specification. The specified scheme is based on a reactive on-demand approach, which enables a router to discover one or more "good-enough" routes in either direction between itself and another router in the LLN without any constraints regarding the existing DAG-membership of the links that such routes may use. Such routes may be source-routes or hop- by-hop ones. 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. Such functionality will be described in a separate document. 2. Targeted 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 target 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 it knows apriori. 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 target 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. Targeted use cases also include scenarios where energy or delay 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 Goyal, et al. Expires December 16, 2010 [Page 4] Internet-Draft draft-dt-roll-p2p-rpl-01 June 2010 [RFC2119]. Additionally, this document uses terminology from [I-D.ietf-roll-terminology] and [I-D.ietf-roll-rpl], and introduces the following terminology: Origin Router: The router initiating the route discovery. The origin router acts as one end point of the routes to be discovered. Target Router: The other end point of the routes to be discovered. Intermediate Router: A router that is neither the origin nor the target. Forward Route: A route from the origin router to the target router. Backward Route: A route from the target router to the origin router. Bidirectional Route: A route that can be used in both directions: from the origin router to the target router and vice versa. Source Route: A complete and ordered list of routers that can be used by a packet to travel from a source to a destination. Such source routes can be carried by a packet in a proposed Type 4 Routing Header [I-D.hui-6man-rpl-routing-header]. Hop-by-hop Route: A route from a source to a destination where each router in the route knows only the address of the next hop on the route. In this document, the term 'router' refers to any LLN device that can forward packets generated at other devices. 4. Functional Overview Router A originates a "Discovery" message listing router B as the target. Node A also indicates in the message: o The nature of the routing cost, the method for accumulating the end-to-end cost and the criteria used to determine if a route is "good enough"; o The direction (forward: router A to router B; backward: router B to router A; or both) of the route being discovered; o The desired number of routes; Goyal, et al. Expires December 16, 2010 [Page 5] Internet-Draft draft-dt-roll-p2p-rpl-01 June 2010 o Whether the route is a source-route or a hop-by-hop one; and o A limit on the "distance" the Discovery message may travel. The Discovery message propagates via link-local multicast with each receiving router making the decision regarding whether to forward the message further based on the "distance" (from router A) that this particular copy of the message has already traveled. Note that this document does not require a receiving router to use the "good enough" criteria to make the forwarding decision. This is because the evaluation of such criteria may be too complex for a constrained intermediate router to perform for each received copy of the Discovery message. The calculation of the "distance" that a copy of the Discovery message has already travelled should be simple enough for a constrained router to perform. A router may optionally decide not to forward a copy of the Discovery message further because the aggregated cost of the route so far fails the "good enough" criteria. The underlying mechanism being used to propagate the Discovery message may put further restrictions on its propagation. A router should not propagate the Discovery message further if hop-by-hop routes are desired and the router can not store state for this route. As a copy of the Discovery message travels towards router B, it accumulates the relevant forward/backward costs as well as the route it takes. When router B receives a copy of the Discovery message, it determines whether the route traveled by the message meets the "good enough" criteria. If router A had requested the discovery of backward source-routes, router B caches one or more good enough source-routes it identifies. Additionally, router B sends one or more "Discovery Reply" message to router A to acknowledge the discovery of these routes. These acknowledgements allow router A to judge the success of the route discovery. The Discovery Reply messages can travel towards router A in any manner chosen by router B. For example, router B may source- route the messages or send them towards router A along a DAG. If router A had requested the discovery of "n" forward source-routes, router B sends the "n" good enough source-routes it identifies to router A in one or more Discovery Reply messages. Again, these Discovery Reply messages can travel towards router A in any manner chosen by router B. If router A had requested the discovery of "n" bidirectional source- routes, router B caches the "n" good enough source-routes it identifies and also sends these routes to router A in one or more Discovery Reply messages. These Discovery Reply messages can travel towards router A in any manner chosen by router B. Goyal, et al. Expires December 16, 2010 [Page 6] Internet-Draft draft-dt-roll-p2p-rpl-01 June 2010 If router A had requested the discovery of "n" forward/backward/ bidirectional hop-by-hop routes, router B sends out a Discovery Reply message to router A for each one of the "n" good enough routes it identifies. The Discovery Reply message travels towards router A using the source-route accumulated by the Discovery message. As this message travels towards router A, it establishes appropriate forward/ backward routing state in the en-route routers. This "non DAG" routing state should be specially marked to associate it with the routing metrics used to discover the route and to distinguish such state from other DAG-specific routing state the router may have. 5. Propagation of Discovery Messages RPL uses DIO message propagation to build a DAG. The DIO message travels via 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 outwards rather than return inwards 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. 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. 5.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 |S| N | L |O| Max Rank | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | | Target Address | | | | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 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 Goyal, et al. Expires December 16, 2010 [Page 7] Internet-Draft draft-dt-roll-p2p-rpl-01 June 2010 than one Route Discovery options. A Route Discovery option consists of the following fields: o Option Type = 0x09 (to be confirmed by IANA). o Option Length = 20 or 22 octets depending on whether the OCP field is included or not. o D: A 2-bit field that indicates the direction of the desired routes: * D = 0x00: Forward; * D = 0x01: Backward; * D = 0x02: Bidirectional. o S: A flag that indicates whether source routes are desired. The flag is set if the source routes are desired. The flag is clear if hop-by-hop routes are desired. o N: A 3-bit unsigned integer indicating the number of routes desired. o L: A 2-bit field indicating 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: * L = 0x00: Minimum life time is 5 seconds; * L = 0x01: Minimum life time is 10 seconds; * L = 0x02: Minimum life time is 1 minute; * L = 0x03: Minimum life time is 10 minutes. o O: A flag that indicates whether the same OCP is used for route discovery as well as temporary DAG formation. If this flag is clear, the OCP contained in the DODAG Configuration option in the DIO is used for route discovery as well. Otherwise, the OCP specified in the Route Discovery option is used for route selection and the metrics/constraints used for route selection are carried in a Metrics Container option immediately following the Route Discovery option. o Max Rank: A 7-bit unsigned integer that indicates the maximum rank allowed in the temporary DAG advertised by the DIO message. This upper limit on the DAG rank serves as the "distance" referred to Goyal, et al. Expires December 16, 2010 [Page 8] Internet-Draft draft-dt-roll-p2p-rpl-01 June 2010 in Section 4 and provides a control over how far the Route Discovery option contained in the DODAG Configuration option in the DIO message may travel. A router MUST not join the temporary DAG if its rank in the DAG will exceed this limit. Later versions of this draft will map the 128 value space available in this field to 16-bit long limits on the DAG rank. o Target Address: The IPv6 address of the target router. o OCP: 16 bit unsigned integer. An optional field, present only if the O flag is set, that indicates the objective code point (OCP) to be used for route selection. 5.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 4.1 of [I-D.ietf-roll-rpl]. o Grounded (G) Flag: MUST be clear since the objective of DAG formation is the 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 clear for same reasons as described above. o Destination Advertisement Trigger (T) Flag: MUST be clear. o Mode of Operation (MOP): Since the temporary DAG is not to be used for routing purposes, the value of this field is immaterial. To allow constrained routers to join the DAG, the MOP field SHOULD be set to 00 (non-storing). o DODAGPreference (Prf): TBD o Destination Advertisement Trigger Sequence Number (DTSN): TBD o DODAGID: IPv6 address of the router initiating the route discovery. 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 the routers joining the temporary DAG. Goyal, et al. Expires December 16, 2010 [Page 9] Internet-Draft draft-dt-roll-p2p-rpl-01 June 2010 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. This document RECOMMENDS RPL Objective Function 0, as defined in [I-D.ietf-roll-of0], for use as the objective function for the formation of the temporary DAG. A DIO, that contains a Route Discovery option with O flag set, MUST also contain a Metric Container option immediately following the Route Discovery option. This Metric Container option carries the values for the routing metrics as well as the constraints (constituting the "good enough" criteria) used for route selection. Note that if O flag in the Route Discovery option is clear, the OCP and Metric Container used for temporary DAG formation are used for route selection as well. A DIO, carrying a Route Discovery option, MUST not carry any Route Information or Prefix Information options described in [I-D.ietf-roll-rpl]. 5.3. Processing of a DIO Carrying a Route Discovery Option At An Intermediate Node 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. When an intermediate router 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 router's rank in the temporary DAG; o The best Metric Container, along with the associated source route from the initiator of route discovery till this router (carried in a Record Route IPv6 Extension Header proposed in [I-D.thubert-6man-reverse-routing-header]), for the Route Goyal, et al. Expires December 16, 2010 [Page 10] Internet-Draft draft-dt-roll-p2p-rpl-01 June 2010 Discovery option being propagated by the temporary DAG. If the router can not compare Metric Containers, it MUST remember the latest Metric Container it has received, along with the associated source route. A router belonging to a temporary DAG need not remember the identity of its DAG parents since the temporary DAG is not used for routing. The main purpose of a temporary DAG's existence is to facilitate the propagation of the Route Discovery option. The router does not process a Route Discovery option, contained in the received DIO, any further if any of the following conditions are true: o The router does not support the objective function being used for route discovery o The router does not have sufficient information to calculate the relevant routing metrics/constraints in the right direction (as specified by the D field). o The S field is clear, i.e. hop-by-hop routes are desired, but the router can not participate in a hop-by-hop route. o The router is an intermediate router and the router's rank in the temporary DAG, calculated on the basis of the rank and objective function carried in the Base Object in the DIO, exceeds the Max Rank value specified in the Route Discovery option. A router MUST discard the DIO if the Route Discovery option contained in the message does not need further processing. Otherwise, the Route Discovery option is processed as follows. The router updates the Metrics Container associated with the received Route Discovery option as per the specified objective function. The router may optionally check the Metric Container to determine if the aggregated values for the routing metrics meet all the constraints listed in the Metric Container. If not, the Route Discovery option is discarded without further processing. Otherwise, the router updates its in-memory copy of the latest/best Metric Container for this Route Discovery option along with the associated source route updated in the correct direction (based on the D field of the Route Discovery option). Any change in the in-memory copy also requires resetting the trickle timer and generating a new DIO carrying the Route Discovery option, the updated latest/best Metric Container and the associated source route (in a Record Route IPv6 extension header proposed in [I-D.thubert-6man-reverse-routing-header]) when the timer fires. Note that the Metric Container MUST immediately follow the Goyal, et al. Expires December 16, 2010 [Page 11] Internet-Draft draft-dt-roll-p2p-rpl-01 June 2010 Route Discovery option if the O flag in the Route Discovery option is set. 5.4. Processing of a DIO Carrying a Route Discovery Option At The Target Router When the target router joins the 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 router's rank in the temporary DAG; The target router does not process a Route Discovery option, contained in the received DIO, any further if any of the following conditions are true: o The router does not support the objective function used for route discovery o The router does not have sufficient information to calculate the relevant routing metrics/constraints in the right direction (as specified by the D field). The target router MUST discard the DIO if the Route Discovery option contained in the message does not need further processing. Otherwise, the Route Discovery option is processed as follows. The target router updates the Metrics Container associated with the received Route Discovery option as per the specified objective function. The target router then checks the Metric Container to determine if the aggregated values for the routing metrics meet all the constraints listed in the Metric Container. If not, the Route Discovery option is discarded without further processing. Otherwise, the router MAY select the source route accumulated by the received DIO as one of the discovered routes. The target router MUST send one or more RPL Control Messages carrying a Discovery Reply Object (defined in the next section) back to the origin router (identified by the DODAGID field in the DIO Base Object) as discussed in the following sections. The target router MUST NOT forward a DIO carrying a Route Discovery option that lists one of its own addresses as the Target Address. Goyal, et al. Expires December 16, 2010 [Page 12] Internet-Draft draft-dt-roll-p2p-rpl-01 June 2010 6. Propagation of Discovery Reply Messages 6.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 |S| 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 the following functions: o An acknowledgement from the target router to the origin router regarding the successful discovery of backward source routes; o Carries one or more forward/bidirectional source routes from the target to the origin router; o Establishes a hop-by-hop forward/backward/bidirectional route as it travels from the target to the origin router. 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 December 16, 2010 [Page 13] Internet-Draft draft-dt-roll-p2p-rpl-01 June 2010 o DODAGID: The DODAGID of the temporary DAG used for route discovery. The DODAGID also identifies the origin router. 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 DAG. o D: A 2-bit field that indicates the direction of the discovered routes: * 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 S: A flag that is clear if the Discovery Reply Object is establishing an hop-by-hop route. The flag is set if the Discovery Reply Object carries (or is an acknowledgement for the discovery of) one or more source routes. o N: A 3-bit field that indicates the number of source routes carried or acknowledged in the Discovery Reply Object. o Target Address: The IPv6 address of the target router originating the Discovery Reply Object. 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 Options: The Discovery Reply Object MAY carry up to 7 Source Route options (defined in the next section) with each such option carrying a complete forward/bidirectional source route and optionally followed by a Metric Container option that lists the aggregated values for the routing metrics for the source route. Goyal, et al. Expires December 16, 2010 [Page 14] Internet-Draft draft-dt-roll-p2p-rpl-01 June 2010 6.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 | Resvd | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | . Addresses[1..n] . . . | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Figure 3: Format of the Source Route Option The Source Route option, illustrated in Figure 3, carries a complete forward/bidirectional source route from the target router to the origin router. A Source Route option can only be a part of the Discovery Reply Object and MAY be immediately followed by a Metric Container option that contains the aggregated values of the routing metrics for this source route. A Route Discovery 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 interger 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. 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 Address[1..n]: Vector of addresses, numbered 1 to n. Each vector element has size (16 - Compr) octets. 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 Addresses[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 Goyal, et al. Expires December 16, 2010 [Page 15] Internet-Draft draft-dt-roll-p2p-rpl-01 June 2010 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 router may not know the mapping between IPv6 addresses and routers. Minimally, the target router MUST ensure that: o The IPv6 Addresses do not appear more than once; o The IPv6 addresses of the origin and the target routers do not appear in the Address vector; o The Address vector represents a source route in forward direction with Address[1] being the next hop for the origin router. Multicast addresses MUST NOT appear in a Source Route option. 6.2. DRO as Acknowledgement for Backward Source Routes When a target router discovers a backward source route, it sends a DRO message to the origin router as an acknowlegement for the discovered route. Optionally, a target router MAY send a DRO acknowledgement to the origin router after discovering multiple backward source routes. A DRO, serving as an acknowledgement for backward source route discovery, has its D field set to 0x01 (indicating backward) while the S flag is set to 1 (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. This document does not require a particular method for sending such a DRO message to the origin router. The target router MAY send the DRO message to the origin router in any fashion, including: o Using a source route carried in a Type 4 Routing header [I-D.hui-6man-rpl-routing-header]; o Along any DAG connecting the target and the origin routers; o Along the temporary DAG created for route discovery, provided that the target router is reasonably sure that the DAG's life time is sufficiently long and the routers in the DAG do remember one or more of their parents in the DAG. Goyal, et al. Expires December 16, 2010 [Page 16] Internet-Draft draft-dt-roll-p2p-rpl-01 June 2010 6.3. DRO as Carrier of Forward/Bidirectional Source Routes When a target router discovers a forward source route, it sends a DRO message to the origin router carrying the discovered source route inside a Source Route option. Similarly, when a target router discovers a bidirectional source route, it caches the route for its own use and then sends a DRO message to the origin router carrying the discovered route inside a Source Route option. Rather than immediately sending a discovered route back to the origin router, a target router MAY optionally send one DRO message after discovering multiple forward/bidirectional source routes with the sent DRO carrying the discovered source routes (in multiple Source Route options). A DRO message carrying one or more Source Route options MUST have its D field set to 0x00 (for forward routes) or 0x02 (for bidirectional routes). The S flag MUST be set to 1 and the N field MUST indicate the number of Source Route options in the message. A Source Route option MAY immediately be followed by a Metric Container option that carries the aggregated values of the routing metrics for this source route. The target router may send this DRO message to the origin router in any fashion it desires including the options listed in Section 6.2. 6.4. Establishing Hop-by-hop Routes Via DRO In order to establish a hop-by-hop route, the target router sends a DRO message along the reverse of the discovered route (via a Type 4 Routing Header specified in [I-D.hui-6man-rpl-routing-header]). The D field of the message is set to convey the route's direction (forward/backward/bidirectional) and the S flag MUST be clear (indicating hop-by-hop). The N field MUST be set to 1. Such a DRO MUST NOT contain any option. A router receiving such a DRO message SHOULD establish hop-by-hop state in the right direction corresponding to the route carried in the Type 4 Routing Header of the DRO message. If a router does not establish such state, it MUST drop the DRO message. Otherwise, it MUST forward the DRO message along the source route contained in Type 4 Routing Header of the received message. A router SHOULD associate the hop-by-hop routing state, thus established, with the objective function and metrics used for route discovery. Goyal, et al. Expires December 16, 2010 [Page 17] Internet-Draft draft-dt-roll-p2p-rpl-01 June 2010 7. Security Considerations TBA 8. IANA Considerations TBA 9. Authors and Contributors In addition to the editor, the authors of this document include the following individuals (listed in alphabetical order). 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, Wakefieldm WF4 4WA, UK. Phone: +44 1924910888; Email: robert.cragie@gridmerge.com Jerald Martocci, Johnson Controls, Milwaukee, WI 53202, USA. Phone: +1 414 524 4010; Email:jerald.p.martocci@jci.com Charles Perkins, Tellabs Inc., USA. Email:charliep@computer.org Authors gratefully acknowledge the contributions of Richard Kelsey and Zach Shelby in the development of this document. 10. References 10.1. Normative References [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997. 10.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-00 (work in progress), April 2010. [I-D.hui-6man-rpl-routing-header] Hui, J., Vasseur, J., and D. Culler, "A Source Routing Goyal, et al. Expires December 16, 2010 [Page 18] Internet-Draft draft-dt-roll-p2p-rpl-01 June 2010 Header for RPL", draft-hui-6man-rpl-routing-header-00 (work in progress), May 2010. [I-D.ietf-roll-building-routing-reqs] Martocci, J., Riou, N., Mil, P., and W. Vermeylen, "Building Automation Routing Requirements in Low Power and Lossy Networks", draft-ietf-roll-building-routing-reqs-09 (work in progress), January 2010. [I-D.ietf-roll-of0] Thubert, P., "RPL Objective Function 0", draft-ietf-roll-of0-02 (work in progress), June 2010. [I-D.ietf-roll-routing-metrics] Vasseur, J., Kim, M., Networks, D., and H. Chong, "Routing Metrics used for Path Calculation in Low Power and Lossy Networks", draft-ietf-roll-routing-metrics-07 (work in progress), June 2010. [I-D.ietf-roll-rpl] Winter, T., Thubert, P., and R. Team, "RPL: IPv6 Routing Protocol for Low power and Lossy Networks", draft-ietf-roll-rpl-09 (work in progress), June 2010. [I-D.ietf-roll-terminology] Vasseur, J., "Terminology in Low power And Lossy Networks", draft-ietf-roll-terminology-03 (work in progress), March 2010. [I-D.thubert-6man-reverse-routing-header] Thubert, P., "Reverse Routing Header", draft-thubert-6man-reverse-routing-header-00 (work in progress), June 2010. [RFC5826] Brandt, A., Buron, J., and G. Porcu, "Home Automation Routing Requirements in Low-Power and Lossy Networks", RFC 5826, April 2010. Goyal, et al. Expires December 16, 2010 [Page 19] Internet-Draft draft-dt-roll-p2p-rpl-01 June 2010 Authors' Addresses Mukul Goyal (editor) University of Wisconsin Milwaukee 3200 N Cramer St Milwaukee, WI 53211 USA Phone: +1 414 2295001 Email: mukul@uwm.edu Emmanuel Baccelli (editor) INRIA Phone: +33-169-335-511 Email: Emmanuel.Baccelli@inria.fr URI: http://www.emmanuelbaccelli.org/ P2P Team Goyal, et al. Expires December 16, 2010 [Page 20]