One document matched: draft-dt-roll-p2p-rpl-00.txt
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]
| PAFTECH AB 2003-2026 | 2026-04-21 19:32:36 |