[Docs] [txt|pdf] [Tracker] [WG] [Email] [Diff1] [Diff2] [Nits]

Versions: (draft-dt-roll-p2p-rpl) 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 RFC 6997

Internet Engineering Task Force                            M. Goyal, Ed.
Internet-Draft                         University of Wisconsin Milwaukee
Intended status: Experimental                                E. Baccelli
Expires: August 11, 2011                                           INRIA
                                                               A. Brandt
                                                           Sigma Designs
                                                               R. Cragie
                                                           Gridmerge Ltd
                                                             J. Martocci
                                                        Johnson Controls
                                                              C. Perkins
                                                             Tellabs Inc
                                                        February 7, 2011


   Reactive Discovery of Point-to-Point Routes in Low Power and Lossy
                                Networks
                       draft-ietf-roll-p2p-rpl-02

Abstract

   Point to point (P2P) communication between arbitrary IPv6 routers and
   hosts in a Low power and Lossy Network (LLN) is a key requirement for
   many applications.  RPL, the IPv6 Routing Protocol for LLNs,
   constrains the LLN topology to a Directed Acyclic Graph (DAG) and
   requires the P2P routing to take place along the DAG links.  Such P2P
   routes may be suboptimal and may lead to traffic congestion near the
   DAG root.  This document specifies a P2P route discovery mechanism,
   complementary to the RPL base functionality.  This mechanism allows
   an RPL-aware IPv6 router or host to discover and establish, on
   demand, one or more routes to another RPL-aware IPv6 router or host
   in the LLN such that the discovered routes meet a specified cost
   criteria.

Status of this Memo

   This Internet-Draft is submitted to IETF in full conformance with the
   provisions of BCP 78 and BCP 79.

   Internet-Drafts are working documents of the Internet Engineering
   Task Force (IETF).  Note that other groups may also distribute
   working documents as Internet-Drafts.  The list of current Internet-
   Drafts is at http://datatracker.ietf.org/drafts/current/.

   Internet-Drafts are draft documents valid for a maximum of six months
   and may be updated, replaced, or obsoleted by other documents at any
   time.  It is inappropriate to use Internet-Drafts as reference
   material or to cite them other than as "work in progress."

   This Internet-Draft will expire on August 11, 2011.



Goyal, et al.            Expires August 11, 2011                [Page 1]

Internet-Draft         draft-ietf-roll-p2p-rpl-02          February 2011


Copyright Notice

   Copyright (c) 2011 IETF Trust and the persons identified as the
   document authors.  All rights reserved.

   This document is subject to BCP 78 and the IETF Trust's Legal
   Provisions Relating to IETF Documents
   (http://trustee.ietf.org/license-info) in effect on the date of
   publication of this document.  Please review these documents
   carefully, as they describe your rights and restrictions with respect
   to this document.  Code Components extracted from this document must
   include Simplified BSD License text as described in Section 4.e of
   the Trust Legal Provisions and are provided without warranty as
   described in the Simplified BSD License.


Table of Contents

   1.  Introduction . . . . . . . . . . . . . . . . . . . . . . . . .  3
   2.  The Use Cases  . . . . . . . . . . . . . . . . . . . . . . . .  4
   3.  Terminology  . . . . . . . . . . . . . . . . . . . . . . . . .  5
   4.  Applicability  . . . . . . . . . . . . . . . . . . . . . . . .  6
   5.  Functional Overview  . . . . . . . . . . . . . . . . . . . . .  7
   6.  Propagation of Discovery Messages  . . . . . . . . . . . . . .  8
     6.1.  The Route Discovery Option . . . . . . . . . . . . . . . .  9
     6.2.  Setting a DIO Carrying a Route Discovery Option  . . . . . 10
     6.3.  Joining a Temporary DAG  . . . . . . . . . . . . . . . . . 12
     6.4.  Processing a DIO Carrying a Route Discovery Option . . . . 12
     6.5.  Additional Processing of a DIO Carrying a Route
           Discovery Option At An Intermediate Router . . . . . . . . 13
     6.6.  Additional Processing of a DIO Carrying a Route
           Discovery Option At The Target Node  . . . . . . . . . . . 14
   7.  Propagation of Discovery Reply Messages  . . . . . . . . . . . 14
     7.1.  The Discovery Reply Object (DRO) . . . . . . . . . . . . . 15
       7.1.1.  The Source Route Option  . . . . . . . . . . . . . . . 17
       7.1.2.  Processing a DRO At An Intermediate Router . . . . . . 19
     7.2.  DRO as Acknowledgement for Backward Source Routes  . . . . 19
     7.3.  DRO as Carrier of Forward/Bidirectional Source Routes  . . 19
     7.4.  Establishing Hop-by-hop Routes Via DRO . . . . . . . . . . 20
   8.  Security Considerations  . . . . . . . . . . . . . . . . . . . 20
   9.  IANA Considerations  . . . . . . . . . . . . . . . . . . . . . 20
   10. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 20
   11. References . . . . . . . . . . . . . . . . . . . . . . . . . . 21
     11.1. Normative References . . . . . . . . . . . . . . . . . . . 21
     11.2. Informative References . . . . . . . . . . . . . . . . . . 22
   Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 22





Goyal, et al.            Expires August 11, 2011                [Page 2]

Internet-Draft         draft-ietf-roll-p2p-rpl-02          February 2011


1.  Introduction

   RPL [I-D.ietf-roll-rpl] provides multipoint-to-point (MP2P) routes
   from nodes in a Low power and Lossy Network (LLN) to a sink node by
   organizing the nodes along a Directed Acyclic Graph (DAG) rooted at
   the sink.  The nodes determine their position in the DAG so as to
   optimize their routing cost on the path towards the DAG root.  A node
   advertises its position (the "rank") in the DAG by originating a
   DODAG Information Object (DIO) message.  The DIO message is sent via
   link-local multicast and also includes information such as the DAG
   root's identity, routing metrics/constraints
   [I-D.ietf-roll-routing-metrics] and the objective function (OF) in
   use.  When a node joins the DAG, it determines its own rank in the
   DAG based on that advertised by its neighbors and originates its own
   DIO message.

   RPL enables point-to-multipoint (P2MP) routing from a node to its
   descendants in the DAG by allowing a node to send a Destination
   Advertisement Object (DAO) upwards along the DAG.  The DAO carries
   potentially aggregated information regarding the descendants (and
   other local prefixes) reachable through the node originating this
   DAO.

   RPL also provides mechanisms for point-to-point (P2P) routing between
   any two nodes in the DAG.  If the destination is within the source's
   radio range, the source may directly send packets to the destination.
   Otherwise, a packet's path from the source to the destination depends
   on the storing/non-storing operation mode of the DAG.  In non-storing
   mode operation, only the DAG root maintains downward routing
   information and hence a packet travels all the way to the DAG root,
   which then sends it towards its destination using a source route.  In
   storing mode operation, if the destination is a DAG descendant and
   the source maintains "downwards" hop-by-hop routing state about this
   descendant, it can forward the packet to a descendant router closer
   to the destination.  Otherwise, the source sends the packet to a DAG
   parent, which then applies the same set of rules to forward the
   packet further.  Thus, a packet travels up the DAG until it reaches a
   node that knows of the downwards route to the destination and then it
   travels down the DAG towards its destination.  A node may or may not
   maintain routing state about a descendant depending on whether its
   immediate children send it such information in their DAOs.  Thus, in
   the best case with storing mode operation, the "upwards" segment of
   the P2P route between a source and a destination ends at the first
   common ancestor of the source and the destination.  In the worst
   case, the "upwards" segment would extend all the way to the DAG root.
   In both storing and non-storing mode operations, if the destination
   did not originate a DAO, the packet will travel all the way to the
   DAG's root, where it will be dropped.



Goyal, et al.            Expires August 11, 2011                [Page 3]

Internet-Draft         draft-ietf-roll-p2p-rpl-02          February 2011


   The P2P routing functionality available in RPL may be inadequate for
   applications in the home and commercial building domains for the
   following reasons [I-D.brandt-roll-rpl-applicability-home-building]
   [RFC5826][RFC5867]:

   o  The need to maintain routes "proactively", i.e., every possible
      destination in the DAG must originate a DAO.

   o  Depending on the network topology and OF/metrics in use, the
      constraint to route only along a DAG may cause significantly
      suboptimal P2P routes and severe traffic congestion near the DAG
      root.

   Thus, there is a need for a mechanism that provides source-initiated
   discovery of P2P routes that are not along an existing DAG.  This
   document describes such a mechanism, complementary to the basic RPL
   functionality.

   The specified mechanism is based on a reactive on-demand approach,
   which enables a node to discover one or more routes in either
   direction between itself and another node in the LLN without any
   restrictions regarding the existing DAG-membership of the links that
   such routes may use.  The discovered routes may be source routes or
   hop-by-hop routes.  The discovered routes may not be the best
   available but are guaranteed to satisfy the desired constraints in
   terms of the routing metrics and are thus considered "good enough"
   from the application's perspective.

   A complementary functionality, necessary to help decide whether to
   initiate a route discovery, is a mechanism to measure the end-to-end
   cost of an existing route.  Section 4 provides further details on how
   such functionality, described in [I-D.goyal-roll-p2p-measurement],
   can be used to determine the metric constraints for use in the route
   discovery mechanism described in this document.


2.  The Use Cases

   The mechanisms described in this document are intended to be employed
   as complementary to RPL in specific scenarios that need point-to-
   point (P2P) routes between arbitrary routers.

   One use case, common in a home environment, involves a remote control
   (or a motion sensor) that suddenly needs to communicate with a lamp
   module, whose network address is a-priori known.  In this case, the
   source of data (the remote control or the motion sensor) must be able
   to discover a route to the destination (the lamp module) "on demand".




Goyal, et al.            Expires August 11, 2011                [Page 4]

Internet-Draft         draft-ietf-roll-p2p-rpl-02          February 2011


   Another use case, common in a large commercial building environment,
   involves a large LLN deployment where P2P communication along a
   particular DAG among hundreds (or thousands) of routers creates
   severe traffic congestion near that DAG's root, and thus routes
   across this DAG are desirable.

   The use cases also include scenarios where energy or latency
   constraints are not satisfied by the P2P routes along a DAG because
   they involve traversing many more intermediate routers than necessary
   to reach the destination.


3.  Terminology

   The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
   "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and
   "OPTIONAL" in this document are to be interpreted as described in
   [RFC2119].

   Additionally, this document uses terminology from
   [I-D.ietf-roll-terminology] and [I-D.ietf-roll-rpl].  Specifically,
   the term node refers to an RPL router or an RPL host as defined in
   [I-D.ietf-roll-rpl].  This document introduces the following terms:

   Origin : The RPL node initiating the route discovery.  The origin
   acts as one end point of the routes to be discovered.

   Target : The RPL node at the other end point of the routes to be
   discovered.

   Intermediate Router: An RPL router that is neither the origin nor the
   target.

   Forward Route: A route from the origin to the target.

   Backward Route: A route from the target to the origin.

   Bidirectional Route: A route that can carry traffic in both
   directions.

   Source Route: A complete and ordered list of routers that can be used
   by a packet to travel from a source node to a destination node.  Such
   source routes can be carried by a packet in a Type 4 Routing Header
   [I-D.ietf-6man-rpl-routing-header].

   Hop-by-hop Route: The route characterized by each router on the route
   using its routing table to determine the next hop on the route.




Goyal, et al.            Expires August 11, 2011                [Page 5]

Internet-Draft         draft-ietf-roll-p2p-rpl-02          February 2011


   Propagation Constraints: The constraints on the routing metrics
   [I-D.ietf-roll-routing-metrics] that MUST be satisfied before an
   intermediate router or the target will process the Route Discovery
   Option (defined in this document) contained inside a DODAG
   Information Object (DIO).

   Route Constraints: Additional constraints on the routing metrics
   [I-D.ietf-roll-routing-metrics] that the target MUST enforce on the
   received DIOs.


4.  Applicability

   The route discovery mechanism, described in this document, may be
   invoked by an origin when no route exists between itself and the
   target or when the existing routes do not satisfy the desired
   performance requirements.  The mechanism is designed to discover one
   or more "good enough" routes in either direction between an origin
   and a target.  In some application contexts, the metric constraints
   that the discovered routes must satisfy are intrinsically known or
   can be specified by the application.  For example, an origin that
   expects a target to be less than 5 hops away may use "hop-count < 5"
   as the propagation or route constraint.  In other application
   contexts, the origin may need to measure the cost of an existing
   route to the target to determine the propagation/route constraints.
   For example, an origin that measures the total ETX of its along-DAG
   route to the target to be 20 may use "ETX < x*20", where x is a
   fraction that the origin decides, as the propagation/route
   constraint.  The functionality required to measure the cost of an
   existing route between the origin and the target is described in
   [I-D.goyal-roll-p2p-measurement].  In case, there is no existing
   route between the origin and target or the cost measurement for the
   existing route fails, the origin will have to guess the propagation/
   route constraints used in the initial route discovery.  Once, the
   initial route discovery succeeds or fails, the origin will have a
   better estimate for the constraints to be used in the subsequent
   route discovery.

   This document describes an on-demand discovery mechanism for P2P
   routes that is complementary to the proactive routes offered by RPL
   base functionality.  The mechanism described in this document may
   result in discovery of better P2P routes than the ones available
   along a DAG designed to optimize routing cost to the DAG's root.  The
   improvement in route quality depends on a number of factors including
   the network topology, the routing metrics in use and the prevalent
   conditions in the network.  A network designer may take in
   consideration both the benefits (potentially better routes; no need
   to maintain routes proactively) and costs (control messages generated



Goyal, et al.            Expires August 11, 2011                [Page 6]

Internet-Draft         draft-ietf-roll-p2p-rpl-02          February 2011


   during the route discovery process) when using this mechanism.


5.  Functional Overview

   This section contains a high level description of the route discovery
   mechanism proposed in this document.

   The route discovery begins with the origin generating a "Discovery"
   message.  The origin indicates in the message:

   o  The target;

   o  The relevant routing metrics;

   o  The constraints on how far the Discovery message may travel
      (henceforth called the propagation constraints);

   o  Additional constraints that the target must enforce (henceforth
      called the route constraints);

   o  The direction (forward: from the origin to the target; backward:
      from the target to the origin; or bidirectional) of the route
      being discovered;

   o  The desired number of routes (in case forward/bidirectional routes
      are being discovered);

   o  Whether the route is a source route or a hop-by-hop one.

   The Discovery message propagates via IPv6 link-local multicast with a
   receiving router discarding the message if it does not satisfy the
   propagation constraints or if the hop-by-hop routes are desired and
   the router cannot store the state for such a route.  As a copy of the
   Discovery message travels towards the target, it accumulates the
   relevant routing metric values as well as the route it takes.  When
   the target receives a Discovery message, it applies both the
   propagation constraints and the route constraints on the routing
   metrics inside the Discovery message.  Thus, the discovered routes
   satisfy both the propagation constraints as well as the route
   constraints, although the propagation of Discovery messages is guided
   by propagation constraints alone.  Using only a subset of the
   constraints as propagation constraints simplifies the operation of
   intermediate routers, an important consideration in many LLN
   application domains [RFC5826][RFC5867].

   The route discovery process may result in the discovery of several
   routes.  This document does not specify how the target selects routes



Goyal, et al.            Expires August 11, 2011                [Page 7]

Internet-Draft         draft-ietf-roll-p2p-rpl-02          February 2011


   among the ones discovered.  Example selection methods include
   selecting routes as they are discovered or selecting the best routes
   discovered over a certain time period.

   If the origin had requested the discovery of backward source-routes,
   the target caches one or more discovered source-routes.
   Additionally, the target sends one or more "Discovery Reply" messages
   to the origin to acknowledge the discovery of these routes.

   If the origin had requested the discovery of "n" forward source-
   routes, the target sends "n" discovered source-routes it selects to
   the origin in one or more Discovery Reply messages.

   If the origin had requested the discovery of "n" bidirectional
   source-routes, the target caches "n" discovered source-routes it
   selects and also sends these routes to the origin in one or more
   Discovery Reply messages.

   If the origin had requested the discovery of "n" forward/backward/
   bidirectional hop-by-hop routes, the target sends out a Discovery
   Reply message to the origin for each one of the "n" discovered routes
   it selects.  The Discovery Reply message travels towards the origin
   along the discovered route.  As this message travels towards the
   origin, it establishes appropriate forward/backward routing state in
   the routers on the path.


6.  Propagation of Discovery Messages

   RPL uses DIO message propagation to build a DAG.  The DIO message
   travels via IPv6 link-local multicast.  Each node joining the DAG
   determines a rank for itself and ignores the subsequent DIO messages
   received from lower (higher in numerical value) ranked neighbors.
   Thus, the DIO messages propagate outward from the DAG root rather
   than return inward towards the DAG root.  The DIO message generation
   at a node is further controlled by a trickle timer that allows a node
   to avoid generating unnecessary messages [I-D.ietf-roll-trickle].
   The link-local multicast based propagation, trickle-controlled
   generation and the rank-based poisoning of messages traveling in the
   wrong direction (towards the DAG root) provide powerful incentives to
   use the DIO message as the Discovery message and propagate the DIO/
   Discovery message by creating a "temporary" DAG.  Such an approach
   also allows reuse of the routing metrics, objective function and
   packet forwarding framework developed for RPL.  The routing metrics
   used for the creation of this temporary DAG SHOULD be same as (or be
   a subset of) the routing metrics being used for route discovery.
   Similarly, the objective function, used for rank calculation in the
   temporary DAG, SHOULD be same as the objective function that



Goyal, et al.            Expires August 11, 2011                [Page 8]

Internet-Draft         draft-ietf-roll-p2p-rpl-02          February 2011


   determines the aggregated cost of a route when limited to the routing
   metrics being used for temporary DAG creation.

   The propagation constraints limit the spread of the temporary DAG.
   The temporary DAG restricts the network topology within which the
   route discovery takes place.  The routes accumulated by the DIOs lie
   within this restricted topology and implicitly satisfy the
   propagation constraints.  As the target receives a DIO, it
   additionally applies the route constraints on the accumulated route.
   Thus, for successful route discovery, the propagation constraints and
   the route constraints MUST be compatible.  The division of the
   overall constraints in the two categories is an implementation
   specific decision.  If desired, an implementation MAY consider all
   the constraints as propagation constraints and keep the set of route
   constraints empty.

6.1.  The Route Discovery Option

       0                   1                   2                   3
        0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |   Type = 9    | Option Length | D |H|  N  |   L   |O|Reserved |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |                                                               |
       |                       Target Address                          |
       |                                                               |
       |                                                               |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |                                                               |
       |                     Metric Container                          |
       |                                                               |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |              OCP              |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+


              Figure 1: Format of the Route Discovery Option

   In order to be used as a Discovery message, a DIO MUST carry a "Route
   Discovery" option illustrated in Figure 1.  A DIO MUST NOT carry more
   than one Route Discovery options.  A router MUST ignore the second
   and subsequent Route Discovery options carried by a DIO.  A Route
   Discovery option consists of the following fields:

   o  Option Type = 0x09 (to be confirmed by IANA).

   o  Option Length = The length of Route Discovery option including any
      Metric Container and OCP fields.



Goyal, et al.            Expires August 11, 2011                [Page 9]

Internet-Draft         draft-ietf-roll-p2p-rpl-02          February 2011


   o  D: A 2-bit field that indicates the direction of the desired
      routes:

      *  D = 0x00: Forward;

      *  D = 0x01: Backward;

      *  D = 0x02: Bidirectional.

      The D field also specifies the direction in which the link-level
      metrics being used for route discovery should be measured.

   o  H: This flag, when set, indicates if hop-by-hop routes are
      desired.  The flag is cleared if source routes are desired.

   o  N: A 3-bit unsigned integer indicating the number of routes
      desired.  Used when forward or bidirectional routes are being
      discovered.

   o  L: A 4-bit field containing an exponent of 2, such that 2 raised
      to the power L specifies, in units of seconds, the minimum "Life
      Time" of the temporary DAG, i.e., the minimum duration a router
      joining the temporary DAG must maintain its membership in the DAG.

   o  O: This flag, when set, indicates that an OCP field is present in
      the Route Discovery option.

   o  Target Address: The IPv6 address of the target.

   o  Metric Container: Contains the route constraints that the target
      MUST apply.  Any metric objects contained in this metric container
      MUST be ignored.

   o  OCP: 16 bit unsigned integer.  An optional field, present only if
      the O flag is set, This field indicates the objective function
      that MAY be used by the target to compare two discovered routes.

6.2.  Setting a DIO Carrying a Route Discovery Option

   A DIO message that carries a Route Discovery option MUST set the Base
   Object, described in [I-D.ietf-roll-rpl], in the following manner:

   o  RPLInstanceID: RPLInstanceID MUST be a local value as described in
      Section 5.1 of [I-D.ietf-roll-rpl].  The origin MUST ensure that
      different RPLInstanceID values are used in two or more concurrent
      route discoveries it initiates.





Goyal, et al.            Expires August 11, 2011               [Page 10]

Internet-Draft         draft-ietf-roll-p2p-rpl-02          February 2011


   o  Grounded (G) Flag: MUST be cleared since the objective of DAG
      formation is propagation of Route Discovery option.  This DAG is
      temporary in nature and is not used for routing purpose.

   o  Destination Advertisement Supported (A) Flag: MUST be cleared for
      same reasons as described above.

   o  Destination Advertisement Trigger (T) Flag: MUST be cleared.

   o  Mode of Operation (MOP): This document suggests a new value (0x04)
      for this field (to be confirmed by IANA).

   o  DODAGPreference (Prf): TBD

   o  Destination Advertisement Trigger Sequence Number (DTSN): TBD

   o  DODAGID: IPv6 address of the origin.

   The other fields in the Base Object are set as per the rules
   described in [I-D.ietf-roll-rpl].

   The DODAG Configuration option, carried in the DIO message, specifies
   the parameters for the trickle timer operation that governs the
   generation of DIO messages by routers joining the temporary DAG.  The
   future versions of this document will specify the default values to
   be used for these parameters.  The other fields defined in the DODAG
   Configuration option are set as follows:

   o  The MaxRankIncrease field MUST be set to 0 to disable local repair
      of the temporary DAG.

   o  This document RECOMMENDS a value 1 for the MinHopRankInc field.

   o  Objective Code Point (OCP): The OCP to be used for temporary DAG
      formation.  The objective function used for temporary DAG
      formation SHOULD be compatible with the objective function to
      determine the aggregated cost of a discovered route.

   A DIO, that contains a Route Discovery option, MUST specify the
   propagation constraints in one or more Metric Container options
   placed outside the Route Discovery option.  As mentioned before, the
   route constraints are listed in the Metric Container option placed
   inside the Route Discovery option.  The routing metrics being used
   for temporary DAG formation SHOULD be same as or a subset of the
   routing metrics being used for route discovery.  These routing
   metrics MUST be placed in the Metric Container options placed outside
   the Route Discovery option.  Any link-level metrics being used for
   route discovery MUST be measured in the direction indicated by the D



Goyal, et al.            Expires August 11, 2011               [Page 11]

Internet-Draft         draft-ietf-roll-p2p-rpl-02          February 2011


   field in Route Discovery option.  Any metric object contained inside
   the Metric Container inside the Route Discovery option MUST be
   ignored.

   A DIO, carrying a Route Discovery option, MUST NOT carry any Route
   Information or Prefix Information options described in
   [I-D.ietf-roll-rpl].

6.3.  Joining a Temporary DAG

   When a node joins a temporary DAG advertized by a DIO carrying the
   Route Discovery option, it MUST maintain its membership in the DAG
   for the Minimum Life Time duration listed in the Route Discovery
   option.  Maintaining membership in the DAG implies remembering:

   o  The RPLInstanceID, the DODAGID and the DODAGVersionNumber for the
      temporary DAG;

   o  The node's rank in the temporary DAG as well as the address of at
      least one DAG parent;

   o  The propagation and the route constraints being used;

   o  In case of intermediate routers, the values for the routing
      metrics, along with the associated source route from the origin
      untill this node (carried in a Record Route IPv6 Extension Header
      proposed in [I-D.thubert-6man-reverse-routing-header]), contained
      in the best DIO (in terms of the routing metrics and potentially
      using the OCP specified in the DODAG Configuration option)
      received so far.

   Although the main purpose of a temporary DAG's existence is to
   facilitate the propagation of the Route Discovery option, the
   temporary DAG MAY also be used for the Discovery Reply Object
   (defined in Section 7.1 to travel from the target to the origin.
   Hence, a node in a temporary DAG SHOULD also remember the address of
   at least one DAG parent that provides the best known path back to the
   origin.  A node SHOULD delete information about a temporary DAG once
   the duration of its membership in the DAG has exceeded the DAG's
   minimum life time.

6.4.  Processing a DIO Carrying a Route Discovery Option

   The rules for DIO processing and transmission, described in Section 7
   of RPL [I-D.ietf-roll-rpl], apply to DIOs carrying a Route Discovery
   option as well except as modified in this document.

   The following rules for processing a DIO carrying a Route Discovery



Goyal, et al.            Expires August 11, 2011               [Page 12]

Internet-Draft         draft-ietf-roll-p2p-rpl-02          February 2011


   Option apply to both intermediate routers and the target.

   A node MUST discard a DIO with no further processing if:

   o  The DIO contains two or more Route Discovery options;

   o  The node can not evaluate one or more of the propagation
      constraints listed in a Metric Container inside the DIO.

   A node MUST discard a DIO with no further processing if any of the
   following conditions are found to be true while processing a Route
   Discovery option contained in that DIO:

   o  The H field is set, i.e., hop-by-hop routes are desired, and the
      node chooses not to participate in a hop-by-hop route;

   o  The node cannot maintain its membership in the temporary DAG for
      the minimum life time specified in the Route Discovery option.

   A node MUST update the values of link-level routing metrics included
   inside the DIO in accordance with the D field in the Route Discovery
   option.  If the D field is 0x00, i.e., the forward routes are being
   discovered, any link-level routing metric MUST be measured in the
   direction towards the node receiving the DIO.  If the D field is
   0x01, i.e., the backward routes are being discovered, any link-level
   routing metric MUST be measured in the direction towards the node
   originating the DIO.  If the D field is 0x02, i.e., the bidirectional
   routes are being discovered, any link-level routing metric MUST be
   calculated so as to take in account the metric's value in both
   directions.  The rules for calculating bidirectional metric values
   will be specified in a separate document.

6.5.  Additional Processing of a DIO Carrying a Route Discovery Option
      At An Intermediate Router

   An intermediate router MUST process a received DIO, carrying a Route
   Discovery option, in accordance with the following rules.

   An intermediate router MUST discard the DIO with no further
   processing if the routing metric values do not satisfy one or more
   propagation constraints listed in the DIO.  The router MAY check the
   route constraints listed inside the Route Discovery option and
   discard the DIO with no further processing if these constraints are
   not met.

   An intermediate router MUST determine if this DIO is the best it has
   received so far for this temporary DAG in terms of the routing
   metrics (potentially using the OCP in the DODAG Configuration



Goyal, et al.            Expires August 11, 2011               [Page 13]

Internet-Draft         draft-ietf-roll-p2p-rpl-02          February 2011


   object).  If yes, the intermediate router MUST remember the routing
   metric values contained in this DIO along with the route travelled by
   the DIO so far and reset the trickle timer associated with the
   temporary DAG.

   When the trickle timer associated with the temporary DAG fires, an
   intermediate router MUST generate a new DIO for this temporary DAG
   carrying the Route Discovery option, the best metric values it knows
   and the source route associated with these values (in a Record Route
   IPv6 extension header [I-D.thubert-6man-reverse-routing-header]).

6.6.  Additional Processing of a DIO Carrying a Route Discovery Option
      At The Target Node

   A node MUST process a received DIO, carrying a Route Discovery option
   that lists this node as the target, in accordance with the following
   rules.

   A target MUST discard the DIO with no further processing if it can
   not evaluate the route constraints listed inside the Route Discovery
   option or if the routing metric values do not satisfy one or more of
   the propagation and route constraints.

   Otherwise, the target considers the source route accumulated by the
   received DIO as one of the discovered routes.  This document does not
   prescribe a particular method for selecting routes among the
   discovered ones.  Suppose the Route Discovery option requires the
   discovery of "n" routes.  The target may select these "n" routes in
   any manner it desires.  Example selection methods include selecting
   the first "n" routes it discovers or selecting the "n" best routes
   discovered over a certain time period, potentially using the OCP
   specified in the Route Discovery option for route comparison.

   After selecting one or more discovered routes, the target MUST send
   one or more RPL Control Messages carrying a Discovery Reply Object
   (defined in the next section) back to the origin (identified by the
   DODAGID field in the DIO Base Object) as specified in Section 7.

   A target MUST NOT forward a DIO carrying a Route Discovery option any
   further.


7.  Propagation of Discovery Reply Messages








Goyal, et al.            Expires August 11, 2011               [Page 14]

Internet-Draft         draft-ietf-roll-p2p-rpl-02          February 2011


7.1.  The Discovery Reply Object (DRO)

       0                   1                   2                   3
        0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       | RPLInstanceID |    Version    | D |H|  N  |     Reserved      |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |                                                               |
       |                         DODAGID(*)                            |
       |                                                               |
       |                                                               |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |                                                               |
       |                       Target Address(*)                       |
       |                                                               |
       |                                                               |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       | Option(s)...
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+...


           Figure 2: Format of the Discovery Reply Object (DRO)

   This document defines a new RPL Control Message type, the Discovery
   Reply Object (DRO) with code 0x04 (to be confirmed by IANA), that
   serves one of the following functions:

   o  An acknowledgement from the target to the origin regarding the
      successful discovery of backward source routes;

   o  Carries one or more forward/bidirectional source routes from the
      target to the origin;

   o  Establishes one hop-by-hop forward/backward/bidirectional route as
      it travels from the target to the origin.

   The format for a Discovery Reply Object (DRO) is shown in Figure 2.
   A DRO consists of the following fields:

   o  RPLInstanceID: The RPLInstanceID of the temporary DAG used for
      route discovery.

   o  Version: The Version of the temporary DAG used for route
      discovery.

   o  D: A 2-bit field that indicates the direction of the discovered
      routes:




Goyal, et al.            Expires August 11, 2011               [Page 15]

Internet-Draft         draft-ietf-roll-p2p-rpl-02          February 2011


      *  D = 0x00: Forward;

      *  D = 0x01: Backward;

      *  D = 0x02: Bidirectional.

      This field has the same value as the corresponding field in the
      Route Discovery option.

   o  H: A flag that is set if the DRO is establishing an hop-by-hop
      route.  If this flag is set, the DRO MUST travel from the target
      to the origin along the hop-by-hop route being established and
      MUST include one Source Route option (defined in Section 7.1.1)
      that contains the remaining routers on this route (as described in
      Section 7.4).  Since the state that a node needs to maintain
      regarding a hop-by-hop route includes the RPLInstanceID, the
      DODAGID and the IPv6 address of the route's destination, a DRO
      with H flag set MUST also include:

      *  The DODAGID of the temporary DAG used for route discovery; and

      *  The Target Address if the hop-by-hop route is forward or
         bidirectional.

      The H flag MUST be clear if the DRO carries (or is an
      acknowledgement for the discovery of) one or more source routes
      contained in the Source Route options.  The target can unicast
      such a DRO to the origin or send it along the temporary DAG used
      for route discovery.  If the DRO is unicast to the origin, it MUST
      NOT include the DODAGID and Target Address fields.  If the DRO is
      sent along the temporary DAG, it MUST include the DODAGID field
      and MUST NOT include the Target Address field.

   o  N: A 3-bit field that indicates the number of source routes
      carried or acknowledged in the DRO.  This field MUST have value 1
      if the DRO is establishing a hop-by-hop route.

   o  Reserved: These bits are reserved for future use.  These bits MUST
      be set to zero on transmission and MUST be ignored on reception.

   o  DODAGID: The DODAGID of the temporary DAG used for route
      discovery.  The DODAGID also identifies the origin.  This field
      MUST be present in the DRO if the H flag is set or if the H flag
      is clear but the DRO needs to travel along the temporary DAG.
      Otherwise, this field need not be present in the DRO.  The
      RPLInstanceID, the Version and the DODAGID together uniquely
      identify the temporary DAG used for route discovery and can be
      copied from the Base Object of the DIO advertizing the temporary



Goyal, et al.            Expires August 11, 2011               [Page 16]

Internet-Draft         draft-ietf-roll-p2p-rpl-02          February 2011


      DAG.

   o  Target Address: The IPv6 address of the target generating the
      Discovery Reply Object.  This field MUST be present in the DRO if
      the H flag is set and the hop-by-hop route being established is
      forward or bidirectional.

   o  Options: The Discovery Reply Object MAY carry up to N Source Route
      options (defined in the next section) with each such option
      carrying a source route and optionally followed by a Metric
      Container option that lists the aggregated values for the routing
      metrics for the source route.

7.1.1.  The Source Route Option

       0                   1                   2                   3
        0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |   Type = 10   | Option Length | Compr |  Pad  | D |   Resvd   |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |                                                               |
       .                      Address[1..n]                          .
       .                                                               .
       |                                                               |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+


                Figure 3: Format of the Source Route Option

   The Source Route option, illustrated in Figure 3, carries a source
   route.  When a Source Route option carries a complete source route
   between the origin and the target, it MAY be immediately followed by
   a Metric Container option that contains the aggregated values of the
   routing metrics for this source route.

   A Source Route option consists of the following fields:

   o  Option Type = 0x0A (to be confirmed by IANA).

   o  Option Length = Variable, depending on the size of the Addresses
      vector.

   o  Compr: 4-bit unsigned integer indicating the number of prefix
      octets that are elided from each address.  For example, Compr
      value will be 0 if full IPv6 addresses are carried in the
      Addresses vector.





Goyal, et al.            Expires August 11, 2011               [Page 17]

Internet-Draft         draft-ietf-roll-p2p-rpl-02          February 2011


   o  Pad: 4-bit unsigned integer.  Number of octets that are used for
      padding between Address[n] and the end of the Source Route option.

   o  D: A 2-bit field that indicates the direction of the source route:

      *  D = 0x00: Forward, i.e., from the origin to the target;

      *  D = 0x01: Backward i. e., from the target to the origin;

      *  D = 0x02: Bidirectional.

      Note that the D field in a Source Route option is independent from
      the D field in the DRO containing the Source Route option.

   o  Resvd: These bits are reserved for future use.  These bits MUST be
      set to zero on transmission and MUST be ignored on reception.

   o  Address[1..n]: Vector of addresses, numbered 1 to n.  Each vector
      element has size (16 - Compr) octets.

   Note that the format of the Source Route option is very similar to
   that of proposed Type 4 Routing Header
   [I-D.ietf-6man-rpl-routing-header].

   A common network configuration for an RPL domain is that all routers
   within an LLN share a common prefix.  The Source Route option uses
   the Compr field to allow compaction of the Address[1..n] vector when
   all entries share the same prefix as the DODAGID or the Target
   Address of the encapsulating Discovery Reply Object.  The shared
   prefix octets are not carried within the Source Route option and each
   entry in Address[1..n] has size (16 - Compr) octets.  When Compr is
   non-zero, there may exist unused octets between the last entry,
   Address[n], and the end of the Source Route option.  The Pad field
   indicates the number of unused octets that are used for padding.
   Note that when Compr is 0, Pad MUST be null and carry a value 0.

   The Source Route option MUST NOT specify a path that visits a router
   more than once.  When generating a Source Route option, the target
   may not know the mapping between IPv6 addresses and routers.
   Minimally, the target MUST ensure that:

   o  The IPv6 Addresses do not appear more than once;

   o  The IPv6 addresses of the origin and the target do not appear in
      the Address vector.

   Multicast addresses MUST NOT appear in a Source Route option.




Goyal, et al.            Expires August 11, 2011               [Page 18]

Internet-Draft         draft-ietf-roll-p2p-rpl-02          February 2011


7.1.2.  Processing a DRO At An Intermediate Router

   When an intermediate router receives a DRO with a clear H flag, it
   MUST forward the DRO to a parent node in the temporary DAG.

   When an intermediate router receives a DRO that has H flag set and
   contains multiple Source Route options, the router MUST drop the DRO
   with no further processing.

   When an intermediate router receives a DRO that has H flag set and
   contains a single Source Route option, the router processes the DRO
   as described in Section 7.4.

7.2.  DRO as Acknowledgement for Backward Source Routes

   After selecting one or more backward source routes, a target MAY send
   a DRO message to the origin as an acknowledgement for the discovered
   routes.  A DRO, serving as an acknowledgement for backward source
   route discovery, has its D field set to 0x01 (indicating backward)
   while the H flag is cleared (indicating source route).  The N field
   is set to indicate the number of discovered backward source routes
   being acknowledged.  Such a DRO message MUST NOT contain any option.

   The target MAY unicast this DRO message to the origin or it MAY
   forward the DRO message to a parent in the temporary DAG.  The target
   should take into consideration the minimum life time of the temporary
   DAG when deciding to use it to send the DRO to the origin.

7.3.  DRO as Carrier of Forward/Bidirectional Source Routes

   The target MUST convey the discovered forward/bidirectional source
   routes to the origin via the Source Route options inside one or more
   DRO messages.  Such a DRO message MUST have its D field set to 0x00
   (if it carries forward routes) or 0x02 (if its carries bidirectional
   routes).  Also, the H flag MUST be cleared and the N field MUST
   indicate the number of Source Route options in the DRO.  Each Source
   Route option inside the DRO MAY immediately be followed by a Metric
   Container option that carries the aggregated values of the relevant
   routing metrics for this source route.

   The target MAY unicast this DRO message to the origin or it MAY
   forward the DRO message to a parent in the temporary DAG.  The target
   should take into consideration the minimum life time of the temporary
   DAG when deciding to use it to send the DRO to the origin.







Goyal, et al.            Expires August 11, 2011               [Page 19]

Internet-Draft         draft-ietf-roll-p2p-rpl-02          February 2011


7.4.  Establishing Hop-by-hop Routes Via DRO

   In order to establish a hop-by-hop route, the target MUST send a DRO
   message along the discovered route, which is specified in a Source
   Route option.  The D field in the DRO MUST reflect the direction of
   the discovered route.  The H bit in the DRO MUST be set and the DRO
   MUST include the DODAGID field.  If a forward or bidirectional hop-
   by-hop route is being established, the DRO MUST include the Target
   Address field as well.  The N field in the DRO MUST be set to 1 and
   the DRO MUST include exactly one Source Route option.  The target
   forwards the DRO to the next hop along the discovered route and
   includes the discovered route, excluding itself and the origin,
   inside the Source Route option in backward direction.  Thus, the D
   field in the Source Route option MUST be 0x01.

   If the hop-by-hop route is in the backward direction, the target MUST
   establish the hop-by-hop state for the route before sending the DRO
   message.  Such hop-by-hop state includes the RPLInstanceID, the
   DODAGID and the route's destination ( in this case, the origin's
   address or the DODAGID).

   A router receiving a DRO message MUST drop the DRO if the router
   cannot establish the hop-by-hop state for the route or if its own
   address does not appear as the first element in the Address vector in
   the Source Route option.  Otherwise, the router MUST establish the
   hop-by-hop state in the direction specified in the D field in the
   DRO.  The hop-by-hop state in the forward direction includes the
   RPLInstanceID, the DODAGID and the target's address.  The hop-by-hop
   state in the backward direction includes the RPLInstanceID, the
   DODAGID and the origin's address.  After establishing the hop-by-hop
   state, the router MUST remove its own address from the route
   contained in the Source Route option and forward the DRO to the next
   hop (Address[0] in the Source Route option).


8.  Security Considerations

   TBA


9.  IANA Considerations

   TBA


10.  Acknowledgements

   Authors gratefully acknowledge the contributions of the following



Goyal, et al.            Expires August 11, 2011               [Page 20]

Internet-Draft         draft-ietf-roll-p2p-rpl-02          February 2011


   individuals (in alphabetical order) in the development of this
   document: Dominique Barthel, Thomas Clausen, Richard Kelsey, Zach
   Shelby, Pascal Thubert and JP Vasseur.


11.  References

11.1.  Normative References

   [I-D.goyal-roll-p2p-measurement]
              Goyal, M. and E. Baccelli, "A Mechanism to Measure the
              Quality of a Point-to-point Route in a Low Power and Lossy
              Network", draft-goyal-roll-p2p-measurement-01 (work in
              progress), October 2010.

   [I-D.ietf-6man-rpl-option]
              Hui, J. and J. Vasseur, "RPL Option for Carrying RPL
              Information in Data-Plane Datagrams",
              draft-ietf-6man-rpl-option-01 (work in progress),
              October 2010.

   [I-D.ietf-6man-rpl-routing-header]
              Hui, J., Vasseur, J., Culler, D., and V. Manral, "An IPv6
              Routing Header for Source Routes with RPL",
              draft-ietf-6man-rpl-routing-header-01 (work in progress),
              October 2010.

   [I-D.ietf-roll-routing-metrics]
              Vasseur, J., Kim, M., Pister, K., Dejean, N., and D.
              Barthel, "Routing Metrics used for Path Calculation in Low
              Power and Lossy Networks",
              draft-ietf-roll-routing-metrics-17 (work in progress),
              January 2011.

   [I-D.ietf-roll-rpl]
              Winter, T., Thubert, P., Brandt, A., Clausen, T., Hui, J.,
              Kelsey, R., Levis, P., Pister, K., Struik, R., and J.
              Vasseur, "RPL: IPv6 Routing Protocol for Low power and
              Lossy Networks", draft-ietf-roll-rpl-17 (work in
              progress), December 2010.

   [I-D.ietf-roll-trickle]
              Levis, P., Clausen, T., Hui, J., Gnawali, O., and J. Ko,
              "The Trickle Algorithm", draft-ietf-roll-trickle-08 (work
              in progress), January 2011.

   [I-D.thubert-6man-reverse-routing-header]
              Thubert, P., "Reverse Routing Header",



Goyal, et al.            Expires August 11, 2011               [Page 21]

Internet-Draft         draft-ietf-roll-p2p-rpl-02          February 2011


              draft-thubert-6man-reverse-routing-header-00 (work in
              progress), June 2010.

   [RFC2119]  Bradner, S., "Key words for use in RFCs to Indicate
              Requirement Levels", BCP 14, RFC 2119, March 1997.

11.2.  Informative References

   [I-D.brandt-roll-rpl-applicability-home-building]
              Brandt, A., Baccelli, E., and R. Cragie, "Applicability
              Statement: The use of RPL in Building and Home
              Environments",
              draft-brandt-roll-rpl-applicability-home-building-01 (work
              in progress), November 2010.

   [I-D.ietf-roll-terminology]
              Vasseur, J., "Terminology in Low power And Lossy
              Networks", draft-ietf-roll-terminology-04 (work in
              progress), September 2010.

   [RFC5826]  Brandt, A., Buron, J., and G. Porcu, "Home Automation
              Routing Requirements in Low-Power and Lossy Networks",
              RFC 5826, April 2010.

   [RFC5867]  Martocci, J., De Mil, P., Riou, N., and W. Vermeylen,
              "Building Automation Routing Requirements in Low-Power and
              Lossy Networks", RFC 5867, June 2010.


Authors' Addresses

   Mukul Goyal (editor)
   University of Wisconsin Milwaukee
   3200 N Cramer St
   Milwaukee, WI  53201
   USA

   Phone: +1 414 2295001
   Email: mukul@uwm.edu


   Emmanuel Baccelli
   INRIA

   Phone: +33-169-335-511
   Email: Emmanuel.Baccelli@inria.fr
   URI:   http://www.emmanuelbaccelli.org/




Goyal, et al.            Expires August 11, 2011               [Page 22]

Internet-Draft         draft-ietf-roll-p2p-rpl-02          February 2011


   Anders Brandt
   Sigma Designs
   Emdrupvej 26A, 1.
   Copenhagen, Dk-2100
   Denmark

   Phone: +45-29609501
   Email: abr@sdesigns.dk


   Robert Cragie
   Gridmerge Ltd
   89 Greenfield Crescent
   Wakefield  WF4 4WA
   UK

   Phone: +44-1924910888
   Email: robert.cragie@gridmerge.com


   Jerald Martocci
   Johnson Controls
   507 E Michigan St
   Milwaukee, WI  53202
   USA

   Phone: +1 414-524-4010
   Email: jerald.p.martocci@jci.com


   Charles Perkins
   Tellabs Inc.

   charliep@computer.org




















Goyal, et al.            Expires August 11, 2011               [Page 23]


Html markup produced by rfcmarkup 1.109, available from https://tools.ietf.org/tools/rfcmarkup/