Internet Engineering Task Force M. Goyal, Ed. Internet-Draft University of Wisconsin Milwaukee Intended status: Informational P2P Team Expires: October 30, 2010 April 28, 2010 Mechanisms to Support Point-to-Point Routing in Low Power and Lossy Networks draft-dt-roll-p2p-rpl-00 Abstract This draft presents mechanisms to determine the end-to-end cost of an existing route and to discover/establish "on demand" one or more routes between two nodes in a low power and lossy network. This draft also proposes functionality that would enable RPL to provide these P2P mechanisms. 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 October 30, 2010. Copyright Notice Copyright (c) 2010 IETF Trust and the persons identified as the document authors. All rights reserved. This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (http://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as Goyal & Team Expires October 30, 2010 [Page 1]
Internet-Draft draft-dt-roll-p2p-rpl-00 April 2010 described in the Simplified BSD License. Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.1. Targeted Use Cases . . . . . . . . . . . . . . . . . . . . 4 2. Required Functionality . . . . . . . . . . . . . . . . . . . . 5 3. High Level Description of Mechanisms . . . . . . . . . . . . . 5 3.1. Mechanisms to determine the end-to-end cost of an existing route . . . . . . . . . . . . . . . . . . . . . . 5 3.1.1. Node A determining the end-to-end cost of an existing route from itself to a remote node B . . . . 5 3.1.2. Node A determining the end-to-end cost of an existing route from a remote node B to itself . . . . 6 3.2. Mechanism to discover/establish a P2P route between two nodes . . . . . . . . . . . . . . . . . . . . . . . . 7 4. RPL Mechanisms Required . . . . . . . . . . . . . . . . . . . 8 4.1. Message Types . . . . . . . . . . . . . . . . . . . . . . 8 4.2. Objective Function . . . . . . . . . . . . . . . . . . . . 9 4.3. Route Stack . . . . . . . . . . . . . . . . . . . . . . . 9 4.4. Source Route . . . . . . . . . . . . . . . . . . . . . . . 9 4.5. Across-DAG Routing State . . . . . . . . . . . . . . . . . 9 4.6. Transport of Routing Metrics . . . . . . . . . . . . . . . 10 4.7. Propagation of Discovery Messages . . . . . . . . . . . . 10 5. Security Considerations . . . . . . . . . . . . . . . . . . . 12 6. Authors and Contributors . . . . . . . . . . . . . . . . . . . 12 7. Informative References . . . . . . . . . . . . . . . . . . . . 13 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 13 Goyal & Team Expires October 30, 2010 [Page 2]
Internet-Draft draft-dt-roll-p2p-rpl-00 April 2010 1. Introduction RPL-07 [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 DAG root initiates the DAG formation by originating a Destination Information Object (DIO) message. The DIO message is sent via link-local multicast and carries information about the originating node's position (the "rank") in the DAG. On receiving DIO messages sent by its neighbors, a node determines its own "rank" in the DAG and originates its own DIO message. RPL-07 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 the aggregated information regarding the descendants (and other local prefixes) reachable through the originating node. RPL-07 also provides mechanisms for point-to-point (P2P) routing between any two nodes in the DAG. If the destination is within the source's "range", the source may directly send packets to the destination. Otherwise, if the destination is a DAG descendant and the source maintains "downwards" routing state about this descendant, it can forward the packet along this route. Otherwise, the source sends the packet to a DAG parent, which then applies the same set of rules to forward the packet further. Thus, a packet travels up the DAG until it reaches a 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 and whether the node can store this information. Thus, in the best case scenario, the "upwards" segment of the P2P route between a source and a destination ends at the first common ancestor of the source and the destination. In the worst case, the "upwards" segment would extend all the way to the DAG's root. If the destination did not originate a DAO, the packet will travel all the way to the DAG's root, where it will be dropped. The P2P routing functionality available in RPL-07 suffers from several shortcomings [I-D.brandt-roll-rpl-applicability-home-building]: o The need to maintain routes "proactively", i.e. every possible destination in the DAG must originate a DAO. o The constraint to route only along a DAG leading to significantly suboptimal P2P routes and traffic congestion near the DAG root. Goyal & Team Expires October 30, 2010 [Page 3]
Internet-Draft draft-dt-roll-p2p-rpl-00 April 2010 These shortcomings mean that RPL-07 does not meet the requirements of many LLN applications, including those in home and commercial building domains [RFC5826] [I-D.ietf-roll-building-routing-reqs]. Such applications require a mechanism for "reactive route discovery" and the ability to route "across DAGs". In other words, a node should be able to discover or establish "on demand" one or more "good enough" routes in either direction to a destination with no constraints regarding the existing DAG-membership of the links that such routes may use. A complementary functionality, necessary to help decide whether to initiate a route discovery, is a mechanism to determine the end-to-end cost of an existing route, where the cost may depend on one or more routing metrics in a particular manner. Accordingly, this draft presents a high level description of the two mechanisms mentioned above: o A mechanism to determine the end-to-end cost of an existing route; and o A mechanism to discover/establish one or more "good enough" routes between any two nodes in a low power and lossy network. This draft also proposes the functionality that future versions of RPL should support in order to implement these mechanisms. 1.1. Targeted Use Cases The mechanisms described in this document are intended to be employed as complementary to RPL in specific scenarios that need point-to- point (P2P) routes between arbitrary nodes. One target use case, common in a home environment, involves a remote control (or a motion sensor) that suddenly needs to communicate with a lamp module, whose network address it knows apriori. In this case, the source of data (the remote control or the motion sensor) must be able to discover a route to the destination (the lamp module) "on demand". Another target use case, common in a large commercial building environment, involves a large LLN deployment where P2P communication along a particular DAG among hundreds (or thousands) of nodes creates severe traffic congestion near that DAG's root, and thus routes across this DAG are desirable. Targeted use cases also include scenarios where energy or delay constraints are not satisfied by the P2P routes along a DAG because they involve traversing many more intermediate nodes than necessary to reach the destination. Goyal & Team Expires October 30, 2010 [Page 4]
Internet-Draft draft-dt-roll-p2p-rpl-00 April 2010 2. Required Functionality o A mechanism for a node to determine the end-to-end cost of an existing route from itself to another node or from another node to itself; * This route may be a source-route (i.e., en-route nodes, other than the source, do not maintain state about the route) or a loose source-route (i.e., the source and some en-route nodes maintain state about the route) or an hop-by-hop one (i.e., all en-route nodes maintain state about the next hop to the destination); * This route may be the one along a DAG or the one established using the mechanisms specified in this draft; * A node may use the cost learned using this mechanism to decide whether to initiate a new route discovery. o A mechanism for a node to discover/establish one or more "good enough" routes from itself to another node or from another node to itself or in both directions; * Such routes may be source-routes or loose source-routes or hop- by-hop ones. 3. High Level Description of Mechanisms 3.1. Mechanisms to determine the end-to-end cost of an existing route 3.1.1. Node A determining the end-to-end cost of an existing route from itself to a remote node B Node A sends a "Measurement Request" message towards node B. Node A indicates in the message: o The nature of the route the message must travel on (e.g. source- route specified in the message or a loose source-route or hop-by- hop along a specific DAG or along an "across DAG" route established using the mechanisms specified in this draft); o The nature of the routing cost (e.g. the routing metrics that determine the routing cost and how these metrics combine to yield the routing cost); o The method for accumulating the end-to-end cost, specifically whether: Goyal & Team Expires October 30, 2010 [Page 5]
Internet-Draft draft-dt-roll-p2p-rpl-00 April 2010 * An intermediate node should update the end-to-end cost so far before forwarding the message further; or * An intermediate node should append the local cost to the message so that the destination (node B) can aggregate the local costs into the end-to-end cost. o If the message should accumulate the reverse source-route from node B to node A. The Measurement Request message accumulates the end-to-end routing cost or the individual local costs (and the reverse route if desired) as it travels to node B. On receiving a Measurement Request message, Node B calculates the end-to-end cost if necessary and sends this cost back to node A via a "Measurement Reply" message. This Measurement Reply message may travel towards node A using any existing route. For example, it may be sent to node A along a DAG or along the reverse route accumulated by the Measurement Request message. 3.1.2. Node A determining the end-to-end cost of an existing route from a remote node B to itself Node A sends a Measurement Request message to node B. This message can travel towards node B using any existing route. For example, it may be sent to node B along a DAG or along a source route. Node A indicates in the message: o The nature of the route the Measurement Reply message, to be sent by node B in response to this message, must travel on (e.g. (loose) source route specified by node B or hop-by-hop along a specific DAG or along an "across DAG" route established using the mechanisms specified in this draft); o The nature of the routing cost; o The method for accumulating the end-to-end cost (each hop updating the end-to-end cost or appending its local cost to the message); On receiving the Measurement Request message, node B sends a Measurement Reply message towards node A. Node B specifies in the message the following information as indicated in the received Measurement Request message: o The (loose) source route to node A or the nature of the hop-by-hop route the message must travel on; Goyal & Team Expires October 30, 2010 [Page 6]
Internet-Draft draft-dt-roll-p2p-rpl-00 April 2010 o The nature of the routing cost; o The method for accumulating the end-to-end cost. The Measurement Reply message accumulates the end-to-end routing cost as it travels towards node A. Depending on the method used for accumulating the end-to-end cost, node A may need to calculate the end-to-end cost using the local costs contained in the message. 3.2. Mechanism to discover/establish a P2P route between two nodes Node A originates a "Discovery" message listing node B as the target. Node A also indicates in the message: o The nature of the routing cost; o The method for accumulating the end-to-end cost; o The criteria used to determine if a route is "good enough"; o The direction (forward: A to B; backward: B to A; or both) of the route being discovered; o The desired number of routes; o Whether the route is a source-route or a loose source-route or a hop-by-hop one; and o A limit on the "distance" the Discovery message may travel. The Discovery message propagates via link-local multicast with each receiving node making the decision regarding whether to forward the message further based on the "distance" (from node A) that this particular copy of the message has already traveled. Note that we do not require a receiving node to use the "good enough" criteria to make the forwarding decision. This is because the evaluation of the "good enough" criteria may be too complex for a constrained intermediate node to perform. The calculation of the "distance" that a copy of the Discovery message has already travelled should be simple enough for a constrained node to perform. A node capable of evaluating the "good enough" criteria may optionally decide not to forward a copy of the Discovery message further because the aggregated cost of the route so far does not meet the "good enough" criteria. The underlying mechanism being used to propagate the Discovery message may put further restrictions on its propagation. A node should not propagate the Discovery message further if hop-by-hop routes are desired and the node can not store state for this route. If loose source-routes are the objective of route discovery, a node Goyal & Team Expires October 30, 2010 [Page 7]
Internet-Draft draft-dt-roll-p2p-rpl-00 April 2010 may indicate in a Discovery message it forwards its ability to store state. As a copy of the Discovery message travels towards node B, it accumulates the relevant forward/backward costs as well as the route it takes. When node B receives a copy of the Discovery message, it determines whether the route traveled by the message meets the "good enough" criteria. For the first "n" good enough routes it discovers, where n is the number of routes requested by node A, node B does the following: o If node A had requested the discovery of a backwards (i.e. from B to A) source-route, node B simply caches the route. o Otherwise, node B sends out a "Discovery Reply" message to node A: * If node A had requested the discovery of a forward (from A to B) or bidirectional source-route, the Discovery Reply message carries such a route back to node A. This message can travel towards node A in any manner chosen by node B. For example, node B may source-route the message or send it towards A along a DAG. * If node A had requested a hop-by-hop route, the Discovery Reply message travels towards A using the source-route accumulated by the Discovery message. As this message travels towards A, it establishes appropriate forward/backward routing state in the en-route nodes. * If node A had requested a loose source-route, the Discovery Reply message travels towards A using the complete source-route accumulated by the Discovery message. On receiving this message, a node capable of storing state stores the source- route piece between itself and the previous storing node, prunes this piece from the source-route carried in the packet and forwards the message further towards A. A node incapable of storing state simply forwards the packet along the source-route it carries. 4. RPL Mechanisms Required 4.1. Message Types The proposed mechanisms define the following message types: o Measurement Request message Goyal & Team Expires October 30, 2010 [Page 8]
Internet-Draft draft-dt-roll-p2p-rpl-00 April 2010 o Measurement Reply message o Discovery message o Discovery Reply message Among the existing message types defined in RPL-07, the Destination Information Object (DIO) message can be used as the Discovery message as described in Section 4.7. RPL-07 requires further extension to include definitions for other message types described in this draft. 4.2. Objective Function The Measurement Request and Reply messages discussed earlier need to carry information regarding o The nature of the routing cost. The Discovery message needs to carry information regarding o The nature of the routing cost and o The criteria used to determine if a route is "good enough". This information can be conveyed via suitably defined objective functions. 4.3. Route Stack The Discovery message (and sometimes the Measurement Request message) needs to accumulate the route it travels on. These messages can use the Route Stack option, currently available for DAO messages, for this purpose. 4.4. Source Route All message types described in this draft, except the Discovery message, need the ability to travel along a complete or partial source-route. Any source-routing mechanism RPL defines in future should be sufficient for this purpose. 4.5. Across-DAG Routing State The routing state the nodes establish as a result of the mechanisms described in this draft should be annotated as being "across DAG" in nature. In order to avoid loops, such routing state should not be mixed with DAG-specific routing state while making packet forwarding decisions. Goyal & Team Expires October 30, 2010 [Page 9]
Internet-Draft draft-dt-roll-p2p-rpl-00 April 2010 It should be possible to associate the "across DAG" routing state with the destination of the route and the objective function giving the measured cost of the route. It should be possible for a packet to indicate its desire to be routed along an "across DAG" path satisfying a particular objective function. 4.6. Transport of Routing Metrics The Metric Container option defined in RPL-07 can be used to carry both the aggregated end-to-end and the local values for the routing metrics being used to define the routing cost. Additional metric objects may need to be defined to carry the aggregated end-to-end routing cost and a source-route unmodified from one node to another; 4.7. Propagation of Discovery Messages RPL-07 uses DIO message propagation to build a DAG. The DIO message travels via 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 outwards rather than return inwards 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. 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. To facilitate the use of a DIO as the Discovery message, we suggest the creation of a new "Route Discovery" option that each DIO/ Discovery message must carry. The Route Discovery option should include fields to specify: o A target destination for route discovery; o The maximum rank allowed in the temporary DAG advertised by the DIO/Discovery message; o The minimum "Life Time" of the temporary DAG, i.e., the minimum duration a node must maintain membership in the temporary DAG; o The direction of the route to be discovered and the number of routes desired; Goyal & Team Expires October 30, 2010 [Page 10]
Internet-Draft draft-dt-roll-p2p-rpl-00 April 2010 o Whether the route is a source-route or a loose source-route or hop-by-hop. The upper limit on the DAG rank provides a control over how far the DIO/Discovery message may travel. A node should not join the temporary DAG advertised by a DIO/Discovery message at a rank higher than this limit. A node (say node A) can use such targeted and scoped DIO as the Discovery message to discover a route to node B in the following manner. Node A originates a DIO/Discovery message listing node B as the target (inside the Route Discovery option). This DIO/Discovery message advertises a temporary DAG to facilitate the DIO message propagation as well as an upper limit on the rank that a node may hold in this DAG. A node, incapable of storing state, should ignore a DIO/Discovery message searching for a hop-by-hop route. Otherwise, when a node first receives a DIO/Discovery message advertising a particular temporary DAG, it starts a trickle timer and does the following at the expiry of this timer: o The node calculates a rank for itself based on the DIO/Discovery messages it has received so far; o If the calculated rank is less than the upper limit allowed for this DAG, the node joins the DAG and generates a DIO/Discovery message advertising its rank in the DAG and including in it the Route Discovery option received from other DIO/Discovery messages. o The node restarts the trickle timer. Having selected a rank for itself in the temporary DAG, the node ignores any DIO/Discovery messages originated by nodes with lower (higher in numerical value) ranks, thereby poisoning the spread of DIO/Discovery messages in the wrong direction. The node continues to process the DIO/Discovery messages it receives from higher-ranked nodes possibly improving its own rank and re-originates its DIO/ Discovery message at the periodic expiry of the trickle timer if it has a better rank or costs to advertise than the ones reported in its previous DIO/Discovery message. A node may optionally restrict its origination of the DIO/Discovery message to a certain number of times. For example, a node may choose to generate its DIO/Discovery message just once - at the first expiry of the trickle timer. Thus, the DIO/Discovery message propagates as the nodes join the temporary DAG. In this manner, the DIO/Discovery message ultimately reaches node B, the target of route discovery. A node maintains its membership in the temporary DAG for a time Goyal & Team Expires October 30, 2010 [Page 11]
Internet-Draft draft-dt-roll-p2p-rpl-00 April 2010 duration at least as large as the DAG Life Time specified inside the Route Discovery option. The node initiating the route discovery selects the Life Time duration on the basis of the estimated time required for the route discovery to complete. A member node is free to leave the temporary DAG (i.e. delete all the state information regarding this DAG) any time after the expiry of the Life Time duration since joining this DAG. While a node is a member of a temporary DAG, it needs to remember its rank in the DAG so that it can poison the DIO messages traveling in the wrong direction. A member node may not need to remember the identity of its DAG parents since the temporary DAG is not used for routing. The sole purpose of a temporary DAG's existence is to facilitate the propagation of DIO/Discovery messages. Consequently, we advocate the use of a simple method to calculate a node's rank in this DAG. For example, using hop count as the rank may suffice. Use of a simple rank calculation method facilitates the participation of severely constrained nodes, common in the home and building environments, in the route discovery process. Note that the use of a simple rank calculation method does not mean that the method used for the routing cost calculation has to be simple as well. The routing cost calculation may still take in account multiple routing metrics in a complex manner while the rank calculation is based on a simple method. 5. Security Considerations TBD 6. Authors and Contributors In addition to the editor, the authors of this draft include the following individuals (listed in alphabetical order). Emmanuel Baccelli, INRIA, Paris, France. Email:emmanuel.baccelli@inria.fr Anders Brandt, Sigma Designs, Emdrupvej 26A, 1., Copenhagen, Dk-2100, Denmark. Phone: +45 29609501; Email: abr@sdesigns.dk Robert Cragie, Gridmerge Ltd, 89 Greenfield Crescent, Wakefieldm WF4 4WA, UK. Phone: +44 1924910888; Email: robert.cragie@gridmerge.com Jerald Martocci, Johnson Controls, Milwaukee, WI 53202, USA. Phone: +1 414 524 4010; Email:jerald.p.martocci@jci.com Goyal & Team Expires October 30, 2010 [Page 12]
Internet-Draft draft-dt-roll-p2p-rpl-00 April 2010 Charles Perkins, Tellabs Inc., USA. Email:charliep@computer.org Authors gratefully acknowledge the contributions of Richard Kelsey and Zach Shelby in the development of this draft. 7. Informative References [I-D.brandt-roll-rpl-applicability-home-building] Brandt, A., Baccelli, E., and R. Cragie, "Applicability Statement: The use of RPL in Building and Home Environments", draft-brandt-roll-rpl-applicability-home-building-00 (work in progress), April 2010. [I-D.ietf-roll-building-routing-reqs] Martocci, J., Riou, N., Mil, P., and W. Vermeylen, "Building Automation Routing Requirements in Low Power and Lossy Networks", draft-ietf-roll-building-routing-reqs-09 (work in progress), January 2010. [I-D.ietf-roll-rpl] Winter, T., Thubert, P., and R. Team, "RPL: IPv6 Routing Protocol for Low power and Lossy Networks", draft-ietf-roll-rpl-07 (work in progress), March 2010. [RFC5826] Brandt, A., Buron, J., and G. Porcu, "Home Automation Routing Requirements in Low-Power and Lossy Networks", RFC 5826, April 2010. Authors' Addresses Mukul Goyal (editor) University of Wisconsin Milwaukee 3200 N Cramer St Milwaukee, WI 53211 USA Phone: +1 414 2295001 Email: mukul@uwm.edu P2P Team Goyal & Team Expires October 30, 2010 [Page 13]