[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 RFC 6997

Internet Engineering Task Force                            M. Goyal, Ed.
Internet-Draft                                   University of Wisconsin
Intended status: Experimental                                  Milwaukee
Expires: November 14, 2011                                   E. Baccelli
                                                                   INRIA
                                                               A. Brandt
                                                           Sigma Designs
                                                               R. Cragie
                                                           Gridmerge Ltd
                                                             J. Martocci
                                                        Johnson Controls
                                                            May 13, 2011


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

Abstract

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

Status of this Memo

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

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

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

   This Internet-Draft will expire on November 14, 2011.



Goyal, et al.           Expires November 14, 2011               [Page 1]

Internet-Draft         draft-ietf-roll-p2p-rpl-03               May 2011


Copyright Notice

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

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


Table of Contents

   1.  Introduction . . . . . . . . . . . . . . . . . . . . . . . . .  3
   2.  The Use Cases  . . . . . . . . . . . . . . . . . . . . . . . .  4
   3.  Terminology  . . . . . . . . . . . . . . . . . . . . . . . . .  5
   4.  Applicability  . . . . . . . . . . . . . . . . . . . . . . . .  6
   5.  Functional Overview  . . . . . . . . . . . . . . . . . . . . .  6
   6.  Propagation of Discovery Messages  . . . . . . . . . . . . . .  8
     6.1.  The Route Discovery Option . . . . . . . . . . . . . . . .  9
     6.2.  Setting a DIO Carrying a Route Discovery Option  . . . . . 12
     6.3.  Joining a Temporary DAG  . . . . . . . . . . . . . . . . . 13
     6.4.  Changes to Trickle Operation For DIOs Carrying a Route
           Discovery Option . . . . . . . . . . . . . . . . . . . . . 13
     6.5.  Processing a DIO Carrying a Route Discovery Option . . . . 14
     6.6.  Additional Processing of a DIO Carrying a Route
           Discovery Option At An Intermediate Router . . . . . . . . 15
     6.7.  Additional Processing of a DIO Carrying a Route
           Discovery Option At The Target Node  . . . . . . . . . . . 15
   7.  Propagation of Discovery Reply Messages  . . . . . . . . . . . 16
     7.1.  The Discovery Reply Object (DRO) . . . . . . . . . . . . . 17
     7.2.  Processing a DRO At An Intermediate Router . . . . . . . . 18
     7.3.  Processing a DRO At The Origin . . . . . . . . . . . . . . 19
   8.  Security Considerations  . . . . . . . . . . . . . . . . . . . 20
   9.  IANA Considerations  . . . . . . . . . . . . . . . . . . . . . 20
   10. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 20
   11. References . . . . . . . . . . . . . . . . . . . . . . . . . . 20
     11.1. Normative References . . . . . . . . . . . . . . . . . . . 20
     11.2. Informative References . . . . . . . . . . . . . . . . . . 21
   Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 21






Goyal, et al.           Expires November 14, 2011               [Page 2]

Internet-Draft         draft-ietf-roll-p2p-rpl-03               May 2011


1.  Introduction

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

   RPL enables point-to-multipoint (P2MP) routing from a router to its
   descendants in the DAG by allowing a router to send a Destination
   Advertisement Object (DAO) upwards along the DAG.  In non-storing
   mode operation, a router's DAO contains a list of its preferred DAG
   parents.  The routers unicast their DAOs to the DAG root, which then
   uses this information to arrive at source-routes from itself to the
   individual routers.  In storing mode operation, a router's DAO
   carries potentially aggregated information regarding its descendants
   and other local prefixes reachable through the router.  The router
   sends its DAO to a selected set of DAG parents, which then use this
   information in their routing tables and in their own DAOs.

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



Goyal, et al.           Expires November 14, 2011               [Page 3]

Internet-Draft         draft-ietf-roll-p2p-rpl-03               May 2011


   and a destination ends at the first common ancestor of the source and
   the destination.  In the worst case, the "upwards" segment would
   extend all the way to the DAG root.  In both storing and non-storing
   mode operations, if the destination did not originate a DAO, the
   packet will travel all the way to the DAG's root, where it will be
   dropped.

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

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

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

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

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

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


2.  The Use Cases

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



Goyal, et al.           Expires November 14, 2011               [Page 4]

Internet-Draft         draft-ietf-roll-p2p-rpl-03               May 2011


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

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

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


3.  Terminology

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

   Additionally, this document uses terminology from
   [I-D.ietf-roll-terminology] and [I-D.ietf-roll-rpl].  This document
   introduces the following terms:

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

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

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

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

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

   Bidirectional Route: A route that is both forward and backward.

   Source Route: A complete and ordered list of routers that can be used
   by a packet to travel from a source to a destination node.

   Hop-by-hop Route: The route characterized by each router on the route



Goyal, et al.           Expires November 14, 2011               [Page 5]

Internet-Draft         draft-ietf-roll-p2p-rpl-03               May 2011


   using its routing table to determine the next hop on the route.


4.  Applicability

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

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


5.  Functional Overview

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

   The route discovery begins with the origin generating a "Discovery"



Goyal, et al.           Expires November 14, 2011               [Page 6]

Internet-Draft         draft-ietf-roll-p2p-rpl-03               May 2011


   message.  The origin indicates in the message:

   o  The target;

   o  The relevant routing metrics;

   o  The constraints that the discovered route must satisfy.  These
      constraints also limit how far the Discovery message may travel;

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

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

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

   The Discovery message propagates via IPv6 link-local multicast
   towards the target accumulating the relevant routing metric values as
   well as the route it takes.  A receiving router (including the
   target) discards the Discovery message if the accumulated routing
   metric values do not satisfy the listed constraints.  A router may
   also discard the Discovery message if it does not wish to be a part
   of the discovered route due to limited resources or due to policy
   reasons.

   The route discovery process may result in the discovery of several
   routes.  This document does not specify how the target selects routes
   among the ones discovered.  Example selection methods include
   selecting routes as they are discovered or selecting the best routes
   discovered over a certain time period.

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

   If the origin had requested the discovery of "n" forward source-
   routes, the target sends the discovered source-routes to the origin
   in "n" Discovery Reply messages, with one Discovery Reply message
   carrying one discovered source-route.

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




Goyal, et al.           Expires November 14, 2011               [Page 7]

Internet-Draft         draft-ietf-roll-p2p-rpl-03               May 2011


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


6.  Propagation of Discovery Messages

   RPL uses DIO message propagation to build a DAG.  The DIO message
   travels via IPv6 link-local multicast.  Each router joining the DAG
   determines a rank for itself and ignores the subsequent DIO messages
   received from lower (higher in numerical value) ranked neighbors.
   Thus, the DIO messages propagate outward from the DAG root rather
   than return inward towards the DAG root.  The DIO message generation
   at a router is further controlled by a Trickle timer that allows a
   router to avoid generating unnecessary messages [RFC6206].  The link-
   local multicast based propagation, Trickle-controlled generation and
   the rank-based poisoning of messages traveling in the wrong direction
   (towards the DAG root) provide powerful incentives to use the DIO
   message as the Discovery message and propagate the DIO/Discovery
   message by creating a "temporary" DAG.  Such an approach also allows
   reuse of the routing metrics, objective function and packet
   forwarding framework developed for RPL.  This document defines a new
   RPL option, Route Discovery Option (RDO), which when carried inside a
   DIO message identifies that message as doing P2P route discovery by
   creating a temporary DAG as specified in this document.

   The use of trickle timers to delay the propagation of DIO messages
   may cause some nodes to generate these messages even when the desired
   routes have already been discovered.  In order to preempt the
   generation of such unnecessary messages, the target may set a "stop"
   bit in the Discovery Reply message (Section 7) to let the nodes in
   the LLN know about the completion of the route discovery process.















Goyal, et al.           Expires November 14, 2011               [Page 8]

Internet-Draft         draft-ietf-roll-p2p-rpl-03               May 2011


6.1.  The Route Discovery Option

       0                   1                   2                   3
        0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |   Type = 9    | Option Length | D |H| N | L | Compr |   Rem   |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |                                                               |
       |                           Target                              |
       |                                                               |
       |                                                               |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |                                                               |
       |                       Address[1..n]                           |
       |                                                               |
       |                                                               |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+


              Figure 1: Format of the Route Discovery Option

   In order to be used as a Discovery message, a DIO MUST carry a Route
   Discovery Option (RDO) illustrated in Figure 1.  A Discovery Reply
   Object (DRO), defined in Section 7.1, MUST also carry a Route
   Discovery Option.  A DIO/DRO message MUST NOT carry more than one
   Route Discovery Option.  A router MUST discard a DIO/DRO if it
   contains more than one Route Discovery Option.  A Route Discovery
   Option consists of the following fields:

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

   o  Option Length = The length of the option in bytes.

   o  Direction (D): This 2-bit field indicates the direction of the
      desired routes:

      *  0x00: Forward;

      *  0x01: Backward;

      *  0x02: Bidirectional.

      When the Route Discovery Option is carried inside a DIO, the link-
      level metric objects contained in the DIO SHOULD be measured in
      the direction indicated by the D field.  Also, the IPv6 addresses
      accumulated in the Address vector MUST be accessible in the
      direction indicated by the D field.  When the Route Discovery
      Option is carried inside a DRO, this field MUST be set to zero on



Goyal, et al.           Expires November 14, 2011               [Page 9]

Internet-Draft         draft-ietf-roll-p2p-rpl-03               May 2011


      transmission and ignored on reception.

   o  HopByHop (H): This flag, when set to 1, indicates that hop-by-hop
      routes are desired.  The flag is cleared when the source routes
      are desired.

   o  Number of Routes (N): When the Route Discovery Option is being
      carried inside a DIO:

      *  The value in this field plus one indicates the number of routes
         desired.

      *  This field is relevant only when the forward or bidirectional
         routes are being discovered.

      *  When the backward routes are being discovered, this field MUST
         be set to zero on transmission and ignored on reception.

      When the Route Discovery Option is being carried inside a DRO,
      this field MUST be set to zero on transmission and ignored on
      reception.

   o  Life Time (L): A 2-bit field that indicates the suggested life
      time of the temporary DAG, i.e., the suggested duration a router
      joining the temporary DAG must maintain its membership in the DAG.
      The mapping between the values in this field and the minimum life
      time of the temporary DAG is as follows:

      *  0x00: 1 second;

      *  0x01: 4 seconds;

      *  0x02: 16 seconds;

      *  0x03: 64 seconds;

      Note that a router MAY detach from the temporary DAG sooner if it
      receives a DRO message concerning this DAG with "stop" bit set.

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

   o  Rem: When the Route Discovery Option is carried inside a DIO, this
      field indicates the number of empty fields inside the Address
      vector.  When the Route Discovery Option is carried inside a DRO,
      this field indicates the number of fields in the Address vector



Goyal, et al.           Expires November 14, 2011              [Page 10]

Internet-Draft         draft-ietf-roll-p2p-rpl-03               May 2011


      yet to be visited.

   o  Target: The IPv6 address of the target after eliding Compr number
      of prefix octets.

   o  Address[1..n]: A vector of IPv6 addresses representing a route
      from the origin towards the target:

      *  Each element in the vector has size (16 - Compr) octets.

      *  The total number of elements inside the Address vector is given
         by n = (Option Length - 4 - (16 - Compr))/(16 - Compr).

      *  When the Route Discovery Option is carried inside a DIO, the
         Address vector is used to accumulate a route optimized in the
         direction specified by the D field.

      *  The IPv6 addresses in the Address vector MUST be accessible in
         the direction specified by the D field.

      *  The Address vector MUST carry the accumulated route such that
         the first element in the Address vector contains the IPv6
         address of the router next to the origin and so on.

      *  The origin and target addresses MUST NOT be included in the
         Address vector.

      *  A router adding its address to the vector MUST ensure that its
         address does not already exist in the vector.  A router
         specifying a complete route in the Address vector MUST ensure
         that the vector does not contain any address more than once.

      *  The Address vector MUST NOT contain any multicast addresses.

      *  A DRO message travels from the target to the origin along a
         route accumulated in the Address vector inside a Route
         Discovery Option.  Hence, the IPv6 addresses stored in the
         Address vector MUST be accessible in the backward direction
         also.

      *  When the Route Discovery Option is carried inside a DRO, the
         Address vector MUST contain a complete route between the origin
         and the target such that the first element in the vector
         contains the IPv6 address of the router next to the origin and
         the last element contains the IPv6 address of the router next
         to the target.





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

Internet-Draft         draft-ietf-roll-p2p-rpl-03               May 2011


6.2.  Setting a DIO Carrying a Route Discovery Option

   The Base Object in a DIO message carrying a Route Discovery Option
   MUST be set in the following manner:

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

   o  Version Number: MUST be set to zero.  The temporary DAG used for
      P2P route discovery does not exist long enough to have new
      versions.

   o  Grounded (G) Flag: MUST be cleared since this DAG is temporary in
      nature and MUST not be used for routing purpose.

   o  Mode of Operation (MOP), DTSN: These fields MUST be set to value 0
      since this DAG does not support downward routing.

   o  DODAGPreference (Prf): This field MUST be set to value 0 (least
      preferred).

   o  DODAGID: This field MUST be set to the IPv6 address of the origin.

   o  The other fields in the Base Object can be set in the desired
      fashion as per the rules described in [I-D.ietf-roll-rpl].

   The DODAG Configuration option, carried in the DIO message, MUST be
   set in the following manner:

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

   o  The other fields in the DODAG Configuration option, including the
      Trickle timer parameters and the OCP, can be set in the desired
      fashion as per the rules described in [I-D.ietf-roll-rpl].

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

   The origin MUST NOT originate a DIO with a particular RPLInstanceID
   for the P2P route discovery more than once in a given
   P2PDISCOVERY_TIMEOUT duration.






Goyal, et al.           Expires November 14, 2011              [Page 12]

Internet-Draft         draft-ietf-roll-p2p-rpl-03               May 2011


6.3.  Joining a Temporary DAG

   When a router joins a temporary DAG advertized by a DIO carrying a
   Route Discovery Option, it SHOULD maintain its membership in the DAG
   for the suggested Life Time duration listed in the Route Discovery
   Option.  Maintaining membership in the DAG implies remembering:

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

   o  The router's rank in the temporary DAG;

   o  The best values of the routing metrics, along with the associated
      route from the origin untill this router (carried inside the Route
      Discovery Option) in the DIOs received so far.

   The only purpose of a temporary DAG's existence is to facilitate the
   propagation of the Discovery messages.  The temporary DAG MUST NOT be
   used to route packets.  A router SHOULD detach from the temporary DAG
   once the duration of its membership in the DAG has exceeded the DAG's
   suggested life time.  A router MAY detach from a temporary DAG sooner
   when it receives a DRO about the temporary DAG with stop flag set.

6.4.  Changes to Trickle Operation For DIOs Carrying a Route Discovery
      Option

   The DIOs carrying a Route Discovery Option create a DAG solely for
   the purpose of P2P route discovery.  This DAG is temporary in nature,
   i.e., it exists just long enough to allow the completion of the P2P
   route discovery process.  Low latency is a critical requirement for
   P2P route discovery in many application scenarios in home and
   building automation LLNs [RFC5826][RFC5867].  This means that the
   Imin and Imax parameters, used in Trickle timer operation to control
   the generation of DIOs for this temporary DAG, can not be too large.
   Low values for Imin/Imax mean frequent generation of DIOs advertising
   same information as before.  These DIO transmissions would mostly be
   unnecessary, expensive in terms of energy consumption and may cause
   congestion in the LLN during the P2P route discovery.  One way to
   avoid the potential DIO storm, caused by frequent DIO generation, is
   to set the redundancy constant to a small value.  A small redundacy
   constant would suppress a DIO transmission if sufficient "consistent"
   DIOs have been heard during the preceding Trickle interval.  However,
   a small redundancy constant may also cause a router to not generate
   its DIO even when the router has a better route to report.

   Thus, the key requirements regarding DIO generation, from the
   perspective of P2P route discovery, are as follows:




Goyal, et al.           Expires November 14, 2011              [Page 13]

Internet-Draft         draft-ietf-roll-p2p-rpl-03               May 2011


   o  A router should generate a DIO quickly when it has a better route
      to advertise.

   o  The DIO generation policy must not lead to a DIO storm.

   To meet these requirements,

   o  A DIO, carrying a Route Discovery Option, SHOULD be suppressed if
      the router does not have a better route to advertise.  This rule
      applies irrespecive of the values of the redundancy constant and
      the number of "consistent" DIOs received in the preceding Trickle
      interval.

   o  A DIO, carrying a Route Discovery Option, SHOULD NOT be suppressed
      if the router has a better route to advertise.  This rule applies
      irrespecive of the values of the redundancy constant and the
      number of "consistent" DIOs received in the preceding Trickle
      interval.

   o  A router SHOULD consider the receipt of a DIO, that leads to an
      improvement in the aggregated routing metrics values the router
      could advertise for this temporary DAG, as an "inconsistency" and
      hence reset the Trickle timer governing the DIO generation for
      this temporary DAG [RFC6206].

6.5.  Processing a DIO Carrying a Route Discovery Option

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

   The following rules for processing a DIO carrying a Route Discovery
   Option apply to both intermediate routers and the target.

   A router SHOULD update the values of link-level routing metrics
   included inside the DIO in the direction indicated by the D field in
   the Route Discovery Option.  If the D field is 0x00, i.e., the
   forward routes are being discovered, any link-level routing metric
   SHOULD be measured in the direction towards the node receiving the
   DIO.  If the D field is 0x01, i.e., the backward routes are being
   discovered, any link-level routing metric SHOULD be measured in the
   direction towards the node originating the DIO.  If the D field is
   0x02, i.e., the bidirectional routes are being discovered, any link-
   level routing metric SHOULD be calculated so as to take in account
   the metric's value in both directions.

   A router MUST discard the DIO with no further processing if it can
   not evaluate the mandatory route constraints listed in the DIO or if



Goyal, et al.           Expires November 14, 2011              [Page 14]

Internet-Draft         draft-ietf-roll-p2p-rpl-03               May 2011


   the routing metric values do not satisfy one or more of the mandatory
   constraints.

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

   When an intermediate router receives a DIO containing a Route
   Discovery Option, it MUST determine if this DIO is the best it has
   received so far for this temporary DAG in terms of the routing
   metrics listed in the DIO.  If yes, the router MUST add its own IPv6
   address to the accumulated route at location Address[n-Rem+1] inside
   the Route Discovery Option and stores this route in memory along with
   the routing metrics associated with this route.  When a router
   includes itself in an accumulated route, it MUST ensure that the IPv6
   address added to the route is accessible in both the backward
   direction and the direction indicated by the D field in the Route
   Discovery Option.  The router MUST also reset the Trickle timer
   associated with the temporary DAG whenever it updates the best route
   it has seen so far.  When the Trickle timer fires, an intermediate
   router checks whether DIO generation is suppressed or not as per
   Section 6.4.  If DIO generation is allowed, the router generates a
   new DIO DIO for this temporary DAG carrying the best routing metric
   values it knows and a Route Discovery Option that carried in its
   Address vector the best route the router has seen so far.

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

   The target considers the route accumulated inside a Route Discovery
   Option in a received DIO as acceptable if the routing metrics inside
   the DIO satisfy all the mandatory constraints.  The target would
   select some routes among the acceptable ones for further processing.
   This document does not prescribe a particular method for the target
   to select routes.  Suppose the Route Discovery Option requests the
   discovery of "n" routes.  The target may select these "n" routes in
   any manner it desires.  Example selection methods include selecting
   the first "n" acceptable routes or selecting the "n" best routes
   discovered over a certain time period.

   If the Route Discovery Option identifies the selected route as a
   backward source route (D=0x01, H=0), the target stores the discovered
   route, obtained by reversing the contents of the Address vector, in
   its memory.  The target sends a Discovery Reply Object (DRO) message
   back to the origin (identified by the DODAGID field in the DIO) after
   selecting the desired number of such routes.  In this DRO, the target
   includes a Route Discovery Option, which can simply be the copied
   from one of the DIOs carrying a selected route.  The mechanism for
   the propagation of DRO messages is described in Section 7.



Goyal, et al.           Expires November 14, 2011              [Page 15]

Internet-Draft         draft-ietf-roll-p2p-rpl-03               May 2011


   If the Route Discovery Option identifies the selected route as a
   forward source route (D=0x00, H=0), the target sends a DRO message
   back to the origin.  In this DRO, the target includes a Route
   Discovery Option, which has same contents as the Route Discovery
   Option contained in the received DIO.

   If the Route Discovery Option identifies the selected route as a
   bidirectional source route (D=0x02, H=0), the target stores the
   discovered route, obtained by reversing the contents of the Address
   vector, in its memory and sends a DRO message back to the origin.  In
   this DRO, the target includes a Route Discovery Option, which has
   same contents as the Route Discovery Option contained in the received
   DIO.

   If the Route Discovery Option identifies the selected route as a
   backward hop-by-hop route (D=0x01, H=1), the target stores the state
   for the discovered route, in the manner described in Section 7.2, in
   its memory and sends a DRO message back to the origin.  In this DRO,
   the target includes a Route Discovery Option, which has same contents
   as the Route Discovery Option contained in the received DIO.

   If the Route Discovery Option identifies the selected route as a
   forward hop-by-hop route (D=0x00, H=1), the target sends a DRO
   message back to the origin.  In this DRO, the target includes a Route
   Discovery Option, which has same contents as the Route Discovery
   Option contained in the received DIO.

   The target MAY include a Metric Container Option in the DRO.  This
   Metric Container contains the end-to-end routing metric values for
   the route specified in the Address vector inside the Route Discovery
   Option contained in the DRO message.

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


7.  Propagation of Discovery Reply Messages














Goyal, et al.           Expires November 14, 2011              [Page 16]

Internet-Draft         draft-ietf-roll-p2p-rpl-03               May 2011


7.1.  The Discovery Reply Object (DRO)

       0                   1                   2                   3
        0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       | RPLInstanceID |    Version    |S|           Reserved          |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |                                                               |
       |                         DODAGID                               |
       |                                                               |
       |                                                               |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       | Option(s)...
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+...


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

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

   o  Acknowledge to the origin the successful discovery of backward
      source routes;

   o  Carry one forward/bidirectional source route from the target to
      the origin;

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

   A DRO message also serves the function of letting the routers in the
   LLN know that a P2P route discovery is complete and no more DIO
   messages need to be generated for the corresponding temporary DAG.  A
   DRO message MUST carry one Route Discovery Option and travel from the
   target to the origin via link-local multicast along the route
   specified in the Route Discovery Option.

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

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

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





Goyal, et al.           Expires November 14, 2011              [Page 17]

Internet-Draft         draft-ietf-roll-p2p-rpl-03               May 2011


   o  Stop (S): This flag, when set by the target, indicates that the
      route discovery being performed by the temporary DAG (identified
      by the RPLInstanceID, DODAGID and VersionNumber field inside the
      DRO) is over.  The routers, receiving such a DRO, SHOULD cancel
      any pending DIO transmissions for this DAG and MAY detach from the
      temporary DAG immediately.  The target SHOULD set the stop flag in
      a DRO when it does not need to receive any more routes via DIOs.

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

   o  DODAGID: The DODAGID of the temporary DAG used for route
      discovery.  The DODAGID also identifies the origin.  The
      RPLInstanceID, the Version and the DODAGID together uniquely
      identify the temporary DAG used for route discovery and can be
      copied from the DIO message advertizing the temporary DAG.

   o  Options: The DRO message MUST carry one Route Discovery Option
      that MUST specify a complete route between the target and the
      origin.  The DRO message MAY carry a Metric Container Option that
      contains the aggregated routing metrics values for the route
      specified in Route Discovery Option.

7.2.  Processing a DRO At An Intermediate Router

   When a router receives a DRO message that does not list its IPv6
   address in the DODAGID field, the router MUST process the received
   message in the following manner:

   o  If the stop flag inside the received DRO is set and the router
      currently belongs to the temporary DAG identified by the
      (RPLInstanceID, DODAGID and Version Number fields of the) DRO, the
      router SHOULD cancel any pending DIO transmissions for this
      temporary DAG.  Additionally, the router MAY detach from the
      temporary DAG immediately.

   o  An intermediate router MUST ignore any Metric Container Option
      contained in the DRO message.

   o  If Address[Rem] element inside the Route Discovery Option lists
      the router's own IPv6 address, the router is a part of the route
      carried in the Route Discovery Option.  In this case, the router
      MUST do the following:

      *  If the H flag inside the Route Discovery Option inside the DRO
         message is set, the router MUST store state for the P2P route
         carried inside the Route Discovery Option.  This state consists
         of:



Goyal, et al.           Expires November 14, 2011              [Page 18]

Internet-Draft         draft-ietf-roll-p2p-rpl-03               May 2011


         +  The RPLInstanceID and the DODAGID fields of the DRO.

         +  The route's destination, either origin (identified by
            DODAGID field in DRO) or target (identified by Target field
            in Route Discovery Option).

         +  The IPv6 address of the next hop.

         For routes in the forward direction (D=0x00 in the Route
         Discovery Option), the route's destination is the target and
         the next hop address is Address[Rem+1] (unless Rem value equals
         the number of elements in the Address vector, in which case the
         target itself is the next hop).  For routes in the backward
         direction (D=0x01 in the Route Discovery Option), the route's
         destination is the origin and the next hop address is
         Address[Rem-1] (unless Rem = 1, in which case the origin itself
         is the next hop).  If the route is bidirectional (D = 0x02 in
         the Route Discovery Option), two routing states are created,
         one in forward direction and one in backward direction.

      *  The router MUST decrement the Rem field inside the Route
         Discovery Option and send the DRO further via link-local
         multicast.

7.3.  Processing a DRO At The Origin

   When a router receives a DRO message that lists its IPv6 address in
   the DODAGID field, the router recognizes itself as the origin for the
   corresponding P2P route discovery and processes the Route Discovery
   Option contained in the DRO in the following manner.

   If the Route Discovery Option identifies the discovered route as a
   backward source/hop-by-hop route (D=0x01, H=0 or H=1), the origin
   considers the DRO receipt as the acknowledgement of successful
   completion of the P2P route discovery process.

   If the Route Discovery Option identifies the discovered route as a
   forward/bidirectional source route (D=0x00 or 0x02, H=0), the origin
   stores the discovered route, contained in the Address vector, in its
   memory.

   If the Route Discovery Option identifies the discovered route as a
   forward/bidirectional hop-by-hop route (D=0x00 or 0x02, H=1), the
   origin stores the state for the discovered route in forward
   direction, in the manner described in Section 7.2, in its memory.

   If the received DRO message contains a Metric Container Option as
   well, the origin MAY store the values of the routing metrics



Goyal, et al.           Expires November 14, 2011              [Page 19]

Internet-Draft         draft-ietf-roll-p2p-rpl-03               May 2011


   associated with the discovered route in its memory.  This information
   may be useful in formulating the constraints for any future P2P route
   discovery to the target.


8.  Security Considerations

   TBA


9.  IANA Considerations

   TBA


10.  Acknowledgements

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


11.  References

11.1.  Normative References

   [I-D.ietf-roll-p2p-measurement]
              Goyal, M., Baccelli, E., Brandt, A., Cragie, R., Martocci,
              J., and C. Perkins, "A Mechanism to Measure the Quality of
              a Point-to-point Route in a Low Power and Lossy Network",
              draft-ietf-roll-p2p-measurement-00 (work in progress),
              April 2011.

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

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




Goyal, et al.           Expires November 14, 2011              [Page 20]

Internet-Draft         draft-ietf-roll-p2p-rpl-03               May 2011


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

   [RFC6206]  Levis, P., Clausen, T., Hui, J., Gnawali, O., and J. Ko,
              "The Trickle Algorithm", RFC 6206, March 2011.

11.2.  Informative References

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

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

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

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


Authors' Addresses

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

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


   Emmanuel Baccelli
   INRIA

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




Goyal, et al.           Expires November 14, 2011              [Page 21]

Internet-Draft         draft-ietf-roll-p2p-rpl-03               May 2011


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

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


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

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


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

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























Goyal, et al.           Expires November 14, 2011              [Page 22]


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