ROLL Working Group                                            P. Thubert
Internet-Draft                                                     Cisco
Intended status: Standards Track                             T. Watteyne
Expires: October 2, 2009                                     UC Berkeley
                                                               Z. Shelby
                                                               Sensinode
                                                              D. Barthel
                                                             Orange Labs
                                                          March 31, 2009


                        LLN Routing Fundamentals
                   draft-thubert-roll-fundamentals-00

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), its areas, and its working groups.  Note that
   other groups may also distribute working documents as Internet-
   Drafts.

   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."

   The list of current Internet-Drafts can be accessed at
   http://www.ietf.org/ietf/1id-abstracts.txt.

   The list of Internet-Draft Shadow Directories can be accessed at
   http://www.ietf.org/shadow.html.

   This Internet-Draft will expire on October 2, 2009.

Copyright Notice

   Copyright (c) 2009 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 in effect on the date of
   publication of this document (http://trustee.ietf.org/license-info).
   Please review these documents carefully, as they describe your rights
   and restrictions with respect to this document.




Thubert, et al.          Expires October 2, 2009                [Page 1]


Internet-Draft          LLN Routing Fundamentals              March 2009


Abstract

   This document describes a basic set of fundamental mechanisms for
   routing on a Low-power and Lossy Network (LLN).  It does not intend
   to specify a full-blown protocol.  It is rather offered as a basis to
   support the discussion while designing the ROLL protocol.













































Thubert, et al.          Expires October 2, 2009                [Page 2]


Internet-Draft          LLN Routing Fundamentals              March 2009


Table of Contents

   1.  Introduction . . . . . . . . . . . . . . . . . . . . . . . . .  4
     1.1.  Terminology  . . . . . . . . . . . . . . . . . . . . . . .  5
     1.2.  Needs  . . . . . . . . . . . . . . . . . . . . . . . . . .  6
   2.  Tree Discovery . . . . . . . . . . . . . . . . . . . . . . . .  7
     2.1.  Overview . . . . . . . . . . . . . . . . . . . . . . . . .  8
     2.2.  Discovery Information  . . . . . . . . . . . . . . . . . .  9
     2.3.  Tree Selection . . . . . . . . . . . . . . . . . . . . . . 11
     2.4.  States . . . . . . . . . . . . . . . . . . . . . . . . . . 11
     2.5.  Stability  . . . . . . . . . . . . . . . . . . . . . . . . 12
   3.  Route Dissemination  . . . . . . . . . . . . . . . . . . . . . 12
     3.1.  Overview . . . . . . . . . . . . . . . . . . . . . . . . . 12
     3.2.  Disseminated Information . . . . . . . . . . . . . . . . . 14
     3.3.  LLN Router Operation . . . . . . . . . . . . . . . . . . . 15
   4.  Forwarding . . . . . . . . . . . . . . . . . . . . . . . . . . 19
     4.1.  Upstream Forwarding  . . . . . . . . . . . . . . . . . . . 19
     4.2.  Downstream Forwarding  . . . . . . . . . . . . . . . . . . 21
   5.  Multicast Support  . . . . . . . . . . . . . . . . . . . . . . 22
     5.1.  Overview . . . . . . . . . . . . . . . . . . . . . . . . . 22
     5.2.  Receiver Flow  . . . . . . . . . . . . . . . . . . . . . . 22
     5.3.  Source flow  . . . . . . . . . . . . . . . . . . . . . . . 23
   6.  Advanced Features  . . . . . . . . . . . . . . . . . . . . . . 23
     6.1.  Interaction with other routing protocols . . . . . . . . . 23
       6.1.1.  AODV/DYMO  . . . . . . . . . . . . . . . . . . . . . . 23
       6.1.2.  OSPF/OLSR  . . . . . . . . . . . . . . . . . . . . . . 24
       6.1.3.  MIP6/NEMO  . . . . . . . . . . . . . . . . . . . . . . 25
     6.2.  Route Optimization . . . . . . . . . . . . . . . . . . . . 25
       6.2.1.  Node-to-node routing . . . . . . . . . . . . . . . . . 25
       6.2.2.  Offline Path Computation . . . . . . . . . . . . . . . 25
       6.2.3.  Graph forwarding . . . . . . . . . . . . . . . . . . . 26
     6.3.  Density  . . . . . . . . . . . . . . . . . . . . . . . . . 27
     6.4.  Digraph Dissemination  . . . . . . . . . . . . . . . . . . 28
     6.5.  Multiple LBRs and Trees  . . . . . . . . . . . . . . . . . 28
     6.6.  Aggregation for Route Dissemination  . . . . . . . . . . . 28
     6.7.  Advanced Forwarding  . . . . . . . . . . . . . . . . . . . 29
   7.  Security Considerations  . . . . . . . . . . . . . . . . . . . 29
   8.  IANA Considerations  . . . . . . . . . . . . . . . . . . . . . 30
   9.  Acknowledgments  . . . . . . . . . . . . . . . . . . . . . . . 30
   10. References . . . . . . . . . . . . . . . . . . . . . . . . . . 30
     10.1. Normative References . . . . . . . . . . . . . . . . . . . 30
     10.2. Informative References . . . . . . . . . . . . . . . . . . 30
   Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 32








Thubert, et al.          Expires October 2, 2009                [Page 3]


Internet-Draft          LLN Routing Fundamentals              March 2009


1.  Introduction

   This document describes a basic set of fundamental mechanisms for
   routing on a Low-power and Lossy Network (LLN) appropriate for
   scenarios identified by the ROLL working group.  It does not intend
   to specify a full-blown protocol.  It is rather offered as a basis to
   support the discussion while designing the ROLL protocol.  The
   fundamental mechanisms proposed stem from our analysis that current
   academic, industrial and IETF protocols suitable to ROLL scenarios
   are reduceable to those basic mechanisms.

   Those mechanisms provide a core set of functionality that can be
   complemented by specific extensions to implement the needs expressed
   in the ROLL routing requirement drafts:

   o  Urban WSNs Routing Requirements in Low Power and Lossy Networks
      [I-D.ietf-roll-urban-routing-reqs]

   o  Building Automation Routing Requirements in Low Power and Lossy
      Networks [I-D.ietf-roll-building-routing-reqs]

   o  Home Automation Routing Requirements in Low Power and Lossy
      Networks [I-D.ietf-roll-home-routing-reqs]

   o  Industrial Routing Requirements in Low Power and Lossy Networks
      [I-D.ietf-roll-indus-routing-reqs]

   The constraints expressed in the routing requirement documents (such
   as on node memory and communication cost) narrow the choice of
   fundamental mechanisms down to very simple ones.

   Due to the highly directed flows in LLNs, a tree structure comes
   naturally to mind as a bare minimum.  In a slightly more elaborate
   mechanism, we propose that each router memorizes a few best neighbor
   routers (not only among its parents up the tree, but also among its
   siblings), to choose from (using some routing metric) when routing
   towards LLN Border Routers (LBR).  However, to reduce complexity, we
   propose that only the best parent be used for routing advertisements
   up the structure towards the LBRs, giving each of them a simple tree
   representation to be used to route downstream traffic or to make
   other global decisions.  Since links and nodes are expected to come
   and go over time, mechanisms for tree reorganization are described.
   However, on a shorter time scale, transient link failures are bound
   to happen.  In such a case, we recommend that the link-layer passes
   packets back to the network layer for re-routing along alternate
   paths.

   In terms of routing, the basic fundamental methods include uni/



Thubert, et al.          Expires October 2, 2009                [Page 4]


Internet-Draft          LLN Routing Fundamentals              March 2009


   anycast routing up the graph and unicast routing down the tree
   (either hop-by-hop or source-based).  The best neighbor selection
   mechanism is left to the protocol design phase.  We even suggest that
   it be left as a plug-in for future evolution.  However, a set of
   basic tree discovery and forwarding rules, described here, prevents
   loops from forming, in most cases, whatever the routing algorithm
   eventually implemented.

   More advanced mechanisms which can be built upon the fundamental
   mechanisms are also described.  They include route optimizations,
   dissemination of a digraph, dissemination and maintenance of multiple
   overlapping trees, prefix aggregation and advanced forwarding rules.

   This document is organized as follows:

      Section 1.1 defines the terminology used in this document.

      Section 2 concentrates on the basic tree discovery and maintenance
      mechanism.

      Section 3 introduces the basic distance-vector route dissemination
      mechanism.

      Section 4 describes the upstream and downstream forwarding rules.

      Section 5 describes multicast support.

      Section 6 describes advanced mechanisms which can be built upon
      these fundamentals.

1.1.  Terminology

   The terminology used in this document is consistent with and
   incorporates that described in [I-D.ietf-roll-terminology].  This
   terminology is extended in this document as follows:

   Discovery:  a mechanism by which a logical representation of the
      network is built.

   Router:  a network node that is capable of forwarding packets on
      behalf of other nodes.  In ROLL routing requirement documents, it
      appears that most nodes are expected to be routers.

   Default Router:  the router to turn to when a node has no information
      on where to forward a packet






Thubert, et al.          Expires October 2, 2009                [Page 5]


Internet-Draft          LLN Routing Fundamentals              March 2009


   Route Dissemination:  the action of establishing state within the
      network so that routers know how to route packets related to some
      source-destination pairs.

   Graph:  a set of vertices and edges to represent a network of nodes
      and links.  A Directed Acyclic Graph (DAG) is a graph with
      directional edges where no loop is formed.

   Tree:  a simple form of graph in which there is only one possible
      route from any node to a specific node called the root.  An LLN is
      said to be Grounded if it is connected to a high-capacity backbone
      or link to a network such as the Internet.  By contrast, an LLN is
      said to be Floating if it is not grounded.

   Tree Depth:  the maximum number of edges that need to be traversed
      from any tree node to the root.

   Uniform Path Metric:  A scalar measure for the quality of the bi-
      directional path between the LLN Router and the root.

1.2.  Needs

   The ROLL working group has identified typical scenarios and their
   related requirements for LLN routing.  The main requirements on any
   fundamental mechanisms used for achieving the ROLL protocol can be
   summarized as follows:

   o  Support for operation in both full IPv6 [RFC2460] and minimal
      6LoWPAN [RFC4944] networks.

   o  Optimized for traffic directed between nodes and LBRs.

   o  The use of multiple default routers whenever possible.

   o  Support for multiple LBRs out of the LLN.

   o  Minimal network state needed by routers, with a hard bound better
      than O(D).

   o  Support for complex unicast, anycast and multicast flows.

   o  Localized response upon link failures without requiring global
      updates.

   o  Minimal control overhead scaling within O(log(L)) of the data
      rate.





Thubert, et al.          Expires October 2, 2009                [Page 6]


Internet-Draft          LLN Routing Fundamentals              March 2009


   o  Support for link and node costs along routes.


2.  Tree Discovery

   A tree is the simplest and most basic acyclic graph structure.  Even
   if it is not sufficient to ensure by itself the multipath forwarding
   proposed below, a tree provides the ideal structure for best path
   routing between source and sink in a convergecast.

   In many occasions, LLNs do not have a clear and stable physical
   structure and it becomes necessary to overlay a logical
   representation to define links and enable IPv6 operations.  LLN Tree
   Discovery is the component of the LLN fundamentals that builds and
   maintains logical tree structures over the LLN.

   The nodes in the LLN discovery tree are Routers; the root is an
   arbitrary elected Router if the network is isolated; it is the LLN
   Border Router (LBR) if the LLN is connected to the infrastructure via
   a backhaul link.  A federating backbone such as an extended LoWPAN
   backbone is the virtual root of the federated tree.  In that case,
   the LBRs are attached at a depth of one and are in charge of
   performing the root operations on behalf of that virtual root.

   A tree is identified by a Tree ID which can take the form of an IPv6
   address: in the case of a LoWPAN configuration with a backbone, the
   LoWPAN prefix is used as the Tree ID.  In the case of an isolated
   network, that will be an address of the root.

   This section describes

   1.  a minimum extension to IPv6 Neighbor Discovery Router
       Advertisements in order to ensure that LLN Routers organize in a
       tree structure, and

   2.  a minimum common algorithmic part that all LLN Routers are
       required to implement in order to ensure that, whatever their
       individual routing decisions, routing loops between LLN Routers
       are avoided and a basic optimization is achieved.

   LLN Discovery is based on an autonomous decision by each Router with
   no global state convergence such as traditionally found in IGPs.  In
   order to enable backward compatibility and interoperability, LLN
   Discovery allows Routers to make different decisions from identical
   inputs, based on their own configuration and their own algorithms,
   though it is highly preferable that the decision algorithm be
   consistent in a given deployment to achieve the specific goals of
   that deployment.



Thubert, et al.          Expires October 2, 2009                [Page 7]


Internet-Draft          LLN Routing Fundamentals              March 2009


   The signalling mechanism that is used to form the trees is an
   extension to the ICMP Router Advertisement (RA) message, namely the
   Tree Information Option (TIO).  The TIO allows LLN Routers to
   advertise the tree they belong to, and to select and move to the best
   location within the available trees.  LLN Routers propagate the TIO
   in RA messages down the tree, updating some metrics such as the Tree
   Depth, leaving other information such as the Tree ID unchanged, and
   resending the result in its own RAs.  This is compatible with RA
   period reduction techniques such as the use of Trickle.

2.1.  Overview

   LLN Tree Discovery is a form of distance vector protocol for use in
   wireless meshed networks.  Tree Discovery locates the nearest exit
   and forms Directed Graphs towards that exit, composed of a best path
   tree and alternate forwarding options.

   By introducing the concept of routing plug-ins, LLN Tree Discovery
   enables LLN Routers to implement different policies for selecting
   their preferred parent in the Tree.  Tree Discovery does not specify
   the plug-in operation, but rather specifies a set of rules to be
   implemented by all plug-ins to ensure interoperability.

   The Tree Depth is the underlying criterion that garantees loop-free
   operations even if plug-ins implement different policies, and even if
   these policies do not use Depth as a routing metric.

   In order to organize and maintain a loopfree structure, the parent
   selection plug-ins in the LLN Routers MUST obey the following rules
   and definitions:

   1.  An LLN Router that is not attached to a parent Router is the root
       of its own floating tree.  Its depth is zero.  An LLN Router that
       looses its current parent and has no alternate parent that it can
       attach to also adopts a depth of zero, but remembers the Tree ID
       and the sequence counter in the TIO of the lost parent for a
       period of time which covers multiple TIOs.

   2.  An LLN Border Router that is attached to a federating backbone
       acts as root and advertises a depth of one.  An LBR that is not
       attached to a federating backbone is a root and exposes a depth
       of zero.

   3.  A router sending an RA without TIO is considered a grounded
       parent Router at depth 0.

   4.  The root of a tree exposes the tree in the Router Advertisement
       (RA) Tree Information Option (TIO) and LLN Routers propagate the



Thubert, et al.          Expires October 2, 2009                [Page 8]


Internet-Draft          LLN Routing Fundamentals              March 2009


       TIO down.

   5.  An LLN Router that is already part of a tree MAY move at any time
       and with no delay in order to get closer to the root of its
       current tree, i.e. in order to reduce its own tree depth.  But an
       LLN Router MUST NOT move down the tree that it is attached to.
       LLN Routers MUST ignore RAs that are received from other routers
       located deeper within the same tree.

   6.  A LLN Router may move from its current tree into any different
       tree at any time and whatever the depth it reaches in the new
       tree but, before it can do so, it may have to wait for a Tree Hop
       Timer to elapse.  If the router was root of its own floating
       tree, it may join its previous tree (identified by the last
       parent Tree ID) only if the sequence number in the TIO was
       incrememented since the LLN Router left that tree, indicating
       that the candidate parent was not attached behind this LLN Router
       and kept getting subsequent TIOs from the same tree.  The LLN
       Router will join that other tree if it is preferable for reasons
       of connectivity, configured preference, free medium time, size,
       security, bandwidth, tree depth, or whatever metrics the LLN
       Router cares to use.

   7.  If an LLN Router has selected a new parent router but has not
       moved yet (because it is waiting for Tree Hop Timer to elapse),
       the LLN Router is said to be unstable and it refrains from
       sending Router Advertisement - Tree Information Options.

   8.  When a LLN Router joins a tree, it moves within its own tree or
       receives a modified TIO from its current parent router, the LLN
       Router sends out an unsolicited Router Advertisement message with
       TIO that propagates the new tree information.

   9.  This allows the new higher parts of the tree to be updated first,
       eventually dragging their sub-tree with them, and allowing
       stepped sub-tree reconfigurations, limiting relative movements.

2.2.  Discovery Information

   The Tree Information Option carries a number of metrics and other
   information that allows an LLN Router to discover a tree and select
   its parent while avoiding loop generation.

   TIO Base option







Thubert, et al.          Expires October 2, 2009                [Page 9]


Internet-Draft          LLN Routing Fundamentals              March 2009


      The Tree Information Option is a container option, which might
      contain a number of suboptions.  The base option regroups the
      minimum information set that is mandatory to operate the LLN
      Discovery Algorithm.

      Grounded (G):  The Grounded (G) flag is set when the tree is
         attached to a fixed network infrastructure (such as the
         Internet).

      Sequence Number:  An integer that is incremented by the root for
         each TIO sent on a link.  It is propagated unchanged down the
         tree.

      Boot Time Random:  A random number used to resolve collisions.
         Its value is computed at boot time and recomputed in case of a
         collision.  Each LLN Router in the propagation chain sets this
         TIO field to its own value.

      Tree Depth:  If the root is attached to a federating backbone, its
         Tree Depth is 1, otherwise it is 0.  The Tree Depth of an LLN
         Router is the depth of its parent as received in a TIO,
         incremented by at least one.  All the nodes in the tree
         advertise their Tree Depth in the Tree Information Options that
         they append to the RA messages as part of the propagation
         process.

      Tree Delay:  An unsigned integer set by the root indicating the
         delay before changing the tree configuration.  It is expected
         to be at least an order of magnitude shorter than the RA
         interval and at least an order of magnitude larger than the
         typical propagation delay inside the LLN.

      Path Digest:  An unsigned integer CRC, updated by each Router.
         This is the result of a computation on a bit string obtained by
         appending the received value and the Router address used to
         attach to his parent.  LBRs use a 'previous value' of zeroes to
         initially set the Path Digest.

      Tree ID:  An unsigned integer which uniquely identifies a tree.
         This value is set by the root to one of its ULA or global
         addresses or prefixes.

       Uniform Path Metric:  A scalar measure for the quality of the bi-
         directional path between the LLN Router and the root.







Thubert, et al.          Expires October 2, 2009               [Page 10]


Internet-Draft          LLN Routing Fundamentals              March 2009


      The following values MUST not change during the propagation of the
      TIO down the tree: G, Tree Delay and Tree ID.  All other fields
      are updated at each hop of the propagation.

      In addition to the minimum set of information required, a number
      of options can are used, e.g. for bandwidth, stability, preference
      etc.

2.3.  Tree Selection

   The tree selection is implementation and algorithm dependent.  In
   order to limit erratic movements, and all metrics being equal, LLN
   Routers SHOULD stick to their previous selection.  Also, LLN Routers
   SHOULD provide a means to filter out candidate parent Routers whose
   availability is detected as fluctuating, at least when more stable
   choices are available.  For instance, the LLN Router MAY place the
   failed parent Router in a Hold Down mode that prevents the parent
   Router from being reused for a given period of time.

   The known trees are associated with the parent Router that advertises
   them and kept in a list by extending the Default Router List.  DRL
   entries are extended to store the information received from the last
   TIO.  These entries are managed by states and timers described in the
   next section.

   When LLN connection to a fixed network is either not possible or not
   recommended, for security or other reasons, scattered trees should as
   much as possible be aggregated into larger trees in order to allow
   inner connectivity.  How to balance these trees is implementation
   dependent, and MAY use a specific visitor-counter suboption in the
   TIO.

   An LLN Router SHOULD verify that bidirectional connectivity is
   available with a candidate parent Router before it attaches to that
   candidate.  Some link-layers such as 802.11 infrastructure mode will
   provide for this, while others such as 802.15.4 will not.  If the
   link-layer does not guarantee bidirectional connectivity, then the
   LLN Router needs to make sure that it can reach the LBR.  This is
   achieved using Neighbor Solicitation and refraining from attaching to
   an LBR for which no neighbor cache exists, or the state is still
   INCOMPLETE.

2.4.  States

   Parent routers in the DRL may or may not be usable for attachment
   depending on runtime conditions.  The following states are defined:





Thubert, et al.          Expires October 2, 2009               [Page 11]


Internet-Draft          LLN Routing Fundamentals              March 2009


   Current  This parent Router is currently used for attachment

   Candidate  This parent Router can be used for attachment.

   Held-Up  This parent Router can not be used till Tree Hop Timer
      elapses.

   Held-Down  This parent Router can not be used till Hold Down Timer
      elapses.  At the end of the hold-down period, the router is
      removed from the DRL.  It will be reinserted if it appears again
      in an RA.

   Collision  This parent Router can not be used until it transmits its
      next RA.

2.5.  Stability

   An LLN Router is instable when it is prepared to move shortly to
   another parent Router.  This happens typically when the LLN Router
   has selected a more preferred candidate parent Router and has to wait
   for the Tree Hop Timer to elapse before roaming.  Instability may
   also occur when the current parent Router is lost and the next best
   is still held up.  Instability is resolved when the Tree Hop Timer of
   all the parent Router(s) causing instability elapse.  Such parent
   Router is changes state to Current or Held- Down.

   Instability is transient (on the order of Tree Hop Timers).  When an
   LLN Router is unstable, it MUST NOT send RAs with TIO.  This avoids
   loops when LLN Router A wishes to attach to LLN Router B and LLN
   Router B wishes to attach to LLN Router A. Unless RAs crisscross, a
   LLN Router receives TIO from stable parent Routers, which do not plan
   to attach to it, so the LLN Router can safely attach to them.


3.  Route Dissemination

3.1.  Overview

   Route Dissemination is the second component of the LLN fundamental
   mechanisms.  As explained previously, the first component, LLN Tree
   Discovery, establishes a logical tree structure over the LLN and sets
   up default routes towards the root.  To establish the routing states
   towards the nodes in the LLN and enable complete reachability along
   the tree, it suffices for Route Dissemination to advertise up the
   tree the host, prefix and multicast routes.

   As a result, the Default Router for an LLN Router is its parent up in
   the tree (upstream); and the more specific routes are always oriented



Thubert, et al.          Expires October 2, 2009               [Page 12]


Internet-Draft          LLN Routing Fundamentals              March 2009


   down the tree (downstream).

   LLN Tree Discovery does not only provide loop avoidance for the Route
   Dissemination protocol; LLN Tree Discovery also triggers Route
   Dissemination each time a topological change occurs.  The loopfree
   structure must be restored before Route Dissemination can operate
   again and repaint the tree with prefixes, addresses and group
   membership.

   Each logical tree that LLN Tree Discovery forms is considered a
   separate routing topology.  If an LLN Router belongs to multiple of
   such topologies, then it is expected that both the Route
   Dissemination signaling and the data packets are flagged to follow
   the topology for which the packet was introduced in the network.

   The ROLL Route Dissemination protocol design follows a hierarchical
   model where a whole structure that is reachable via a node of the
   tree is abstracted as located within that node for the upper level of
   network abstraction, exposing only the list of reachable prefixes,
   hosts, and multicast group listeners as opposed to the topological
   information to get there.

   This allows an extreme conciseness of the routing information, with
   no topological knowledge past the first hop.  That conciseness
   enables some degree of movement within the nested structure; in
   particular, a movement within a subtree is not seen outside of that
   subtree, so most of the connectivity is maintained at all times while
   there might never be such a thing as a convergence.

   The ROLL Route Dissemination protocol defines a new information
   vector called the Route Information Option (RIO) to disseminate
   atomic routing information towards the root of the tree.  Due to a
   topological change, a RIO can be received from a sub-tree where the
   originating router was but is no more, until its parents realize it
   is gone and stop advertising.  By construction of the tree, there can
   be a single child to reach a given unicast resource, so older unicast
   routes can be flushed right away if a more recent advertisement comes
   from a different child.  Multicast routes can only be explicitely
   removed or timed out.

   A parent maintains a state for each information it learns from Route
   Dissemination.  Advertisements are sequenced and the last sequence
   number is kept.  An out-of-sequence RIO must be disregarded.  If the
   RIO information appears valid, it is forwarded to the parent's parent
   in the next burst, carried by a RIO, together with the parent's own
   information.





Thubert, et al.          Expires October 2, 2009               [Page 13]


Internet-Draft          LLN Routing Fundamentals              March 2009


3.2.  Disseminated Information

   Route Dissemination extends RFC4861 and RFC4191 to allow a node to
   include a new Route Information Option in ND messages such as
   Neighbor Advertisements (NAs).

   In order to track the freshness of an advertisement, the RIO includes
   a sequence counter that is incremented each time the advertisment is
   reissued.

   A depth is also added for tracking purposes; the depth is incremented
   at each hop as the RIO is propagated up the tree.

   Receiving a Tree Discovery TIO from the parent triggers the sending
   of a delayed advertisement back, with the collection of all known
   information.

   An NA is also sent to the new parent once it has been selected after
   a movement, or when the list of advertised information has changed.

   Route Dissemination may advertise positive (prefix is present) or
   negative (removed) RIOs.  A no-RIO is stimulated by the disappearance
   of a route below.  This is discovered by timing out after a request
   (a Tree Discovery TIO) or by receiving a no-RIO.  A no-RIO is a RIO
   with a RIO Lifetime of 0.

   The RIO base option carries sequenced route information for unicast
   and multicast; it contains:

   Resource type:  Prefix, host, or multicast group

   Prefix Length:  Number of valid leading bits in the IPv6 Prefix.

   RIO Lifetime:  The length of time in seconds (relative to the time
      the packet is sent) that the prefix is valid for route
      determination.  A value of all one bits (0xFFFFFFFF) represents
      infinity.  A value of all zero bits (0x00000000) indicates a loss
      of reachability.

   RIO Depth:  Set to 0 by the router that owns the resource and issues
      the RIO.  Incremented by all routers that propagate the RIO
      towards the root.

   RIO Sequence:  Incremented by the router that owns the resource for
      each new RIO for that prefix.  Left unchanged by all routers that
      propagate the RIO.  A lollipop mechanism is used to wrap from
      0xFFFF directly to 10.




Thubert, et al.          Expires October 2, 2009               [Page 14]


Internet-Draft          LLN Routing Fundamentals              March 2009


   Prefix:  Variable-length field containing a prefix, an IPv6 address
      or a multicast group id.  The Prefix Length field contains the
      number of valid leading bits in the prefix in the former case.
      The bits in the prefix after the prefix length (if any) are
      reserved and MUST be initialized to zero by the sender and ignored
      by the receiver.

3.3.  LLN Router Operation

   The LLN Router operation is autonomous, based on the information
   provided by the potential parents in sight.  Each router selects a
   parent in a loopfree and case-optimized fashion, and installs a
   default route up the tree via the selected parent.  The resulting
   tree may never be globally stable enough to be mapped in a global
   graph.  So the adaptation to local movements must be rapid and
   localized.

   Route Dissemination information can be redistributed in another
   routing protocol, e.g.  MANET or IGP.  But the MANET or the IGP route
   information SHOULD NOT be redistributed into Route Dissemination.
   This creates a hierarchy of routing protocols where Route
   Dissemination routes stand somewhere between connected and IGP
   routes.  See Section Section 6.1 for more discussion on integration
   with other routing protocols.

   As a result:

   o  LLN Discovery establishes a tree using extended Neighbor Discovery
      RS/RA flows.

   o  A routing algorithm exploits the tree to get optimally out of LLN
      (default route).

   o  Route Dissemination extends Neighbor Discovery in order to quickly
      establish hop-by-hop routes down the tree.

   o  Source Routing can be used to provide additional routes towards
      nodes in the LLN.  When there is existing hop-by-hop state in
      routers, the source routing information can be compressed.

   Route Dissemination maintains abstract lists of known information.
   An entry contains the following abstract information:

   o  The state of the entry: ELAPSED, PENDING, or CONFIRMED.

   o  A reference to the adjacency that was created for that prefix.





Thubert, et al.          Expires October 2, 2009               [Page 15]


Internet-Draft          LLN Routing Fundamentals              March 2009


   o  A reference to the ND entry that was created for the advertiser
      Neighbor.

   o  The IPv6 address of the advertiser Neighbor.

   o  The logical equivalent of the full Route Dissemination
      information.

   o  A reference to the interface of the advertiser Neighbor.

   o  A 'reported' Boolean to keep track whether this prefix was
      reported already to the parent parent.

   o  A counter of retries to count how many TIOs were sent on the
      interface to the neighbor without reachability confirmation for
      the prefix.

   Route Dissemination stores the entries in either one of 3 abstract
   lists; the Connected, the Reachable and the Unreachable lists.  In
   practice all part of a route table.

   The Connected list corresponds to the resources owned by the LLN
   Router.

   As long as an router keeps receiving RIOs for a given information
   timely, its entry is listed in the Reachable list.

   Once scheduled to be destroyed, an entry is moved to the Unreachable
   list if the router has a parent to which it sends RIOs, otherwise the
   entry is cleaned up right away.  The entry is removed from the
   Unreachable list when the parent changes or when a no-RIO is sent to
   the parent indicating the loss of the prefix.

   Route Dissemination requires 2 timers; the DelayNA timer and the
   DestroyTimer.

   o  The DelayNA timer is armed upon a stimulation to send a RIO (such
      as a TIO from the parent).  When the timer is armed, all entries
      in the Reachable list as well as all entries for Connected list
      are set to not reported yet.

   o  The DelayNA timer has a duration that is DEF_NA_LATENCY divided by
      2 with the tree depth.

   o  The DestroyTimer is armed when at least one entry has exhausted
      its retries, which means that a number of TIO were sent over the
      interface but that the entry was not confirmed with a RIO.  When
      the destroy timer elapses, for all exhausted entries, the



Thubert, et al.          Expires October 2, 2009               [Page 16]


Internet-Draft          LLN Routing Fundamentals              March 2009


      associated route is removed, and the entry is scheduled to be
      destroyed.

   o  The Destroy timer has a duration of min (MAX_DESTROY_INTERVAL,
      RA_INTERVAL).

   RIO Processing

      When ND sends a NA to the parent, Route Dissemination extends the
      message with RIO options for:

      *  All the entries that are not 'DELETED'.

      *  All the entries in the removed list as no-RIO.

      *  All the pentries in the advertised list that are not reported
         yet.The entries are then set to reported.

      When ND receives a NA from a visitor over a given interface, RIOs
      are processed in a loop.  For known information, the sequence
      counter in the RIO is checked against the last received and the
      update is used only if the sequence is newer.  This filters out
      obsolete advertisements when a node has moved between 2 subtrees
      attached to a same node.

      If an information is advertised as a no-RIO, the associated route
      is removed, and the entry is transferred to the removed list.
      Otherwise, the proper routing table is looked up:

      *  If a preferred route to that source from another protocol
         already exists, the RIO is ignored.

      *  If a new route can be created, a new entry is allocated to
         track it, as CONFIRMED, but not reported.

      *  If a Route Dissemination route existed already via the same
         Neighbor, it is CONFIRMED.

      *  If an older unicast route existed via a different Neighbor,
         this is equivalent to a no-RIO for the previous entry followed
         by a new RIO for the new entry.  So the old entry is scheduled
         to be destroyed, whereas the new one is installed.

   Unicast Route Dissemination messages from child to parent







Thubert, et al.          Expires October 2, 2009               [Page 17]


Internet-Draft          LLN Routing Fundamentals              March 2009


      When sending Route Dissemination to its parent, a router includes
      the RIOs about not already reported entries in the Reachable and
      Connected lists, as well as no-RIOs for all the entries in the
      Unreachable list.

      Depending on its policy, the receiving router SHOULD install a
      route for the resource in the RIO via the link local address of
      the source router and it SHOULD propagate the information, either
      as a RIO or by means of redistribution into a routing protocol.

      The TIO from the root is used to synchronize the whole tree.  Its
      period is expected to range from 500ms to hours, depending on the
      stability of the configuration and the bandwidth available.

      When an router receives a TIO over an egress interface from the
      current parent parent, the DelayNA is armed to force a full
      update.  The router also issues a propagated TIO over all its
      relevant interfaces, after a small jitter that aims at minimizing
      collisions of TIO messages over the radio as it is propagated down
      the tree.

      The design choice behind this is NOT TO synchronize the parent and
      children databases, but instead to update them regularly to cover
      from the loss of packets.  The rationale for that choice is
      movement.  If the topology can be expected to change frequently,
      synchronization might be an excessive goal in terms of exchanges
      and protocol complexity.  This results in a simple protocol with
      no real peering.

      When the router sends a TIO over an interface, for all entries on
      that interface:

      *  If the entry is CONFIRMED, it goes PENDING with the retry count
         set to 0.

      *  If the entry is PENDING, the retry count is incremented.  If it
         reaches a maximum threshold, the entry goes ELAPSED If at least
         one entry is ELAPSED at the end of the process: if the Destroy
         timer is not running then it is armed with a jitter.

      Since the DelayNA has a duration that decreases with the depth, it
      is expected to receive all RIOs from all children before the timer
      elapses and the full update is sent to the parent.

   Other events






Thubert, et al.          Expires October 2, 2009               [Page 18]


Internet-Draft          LLN Routing Fundamentals              March 2009


      Finally, Route Dissemination listens to a series of events, such
      as:

      *  router stopped or unable to run: Route Dissemination routes are
         cleaned up.  Route Dissemination is inactive.

      *  Route Dissemination operation stopped: All entries in the
         abstract lists are freed.  All the Route Dissemination routes
         are destroyed.

      *  Interface going down: for all entries in the Reachable list on
         that interface, the associated route is removed, and the entry
         is scheduled to be destroyed.

      *  Neighbor being removed from the ND list: if the entry is in the
         Reachable list the associated route is removed, and the entry
         is scheduled to be destroyed.

      *  Roaming: All entries in the Reachable list are set to not
         'reported' and DelayNA is armed.


4.  Forwarding

   The fundamental mechanisms described in this draft build a DAG to
   enable communication from the LLN Router nodes to the LLN Border
   Routers (upstream); a second mechanism informs LLN Routers about
   their children in the tree, hence enabling LLN Boarder Router to LLN
   Router communication (downstream) and node-to-node routing along the
   tree.  While the previous sections focus on how routing information
   is disseminated throughout the LLN and used for routing, this section
   focuses on the forwarding policies used by LLN Routers.

   Reliability can be increased by allowing for secondary next-hop nodes
   for upstream traffic, while downstream traffic is sent along the tree
   formed by route dissemination.

4.1.  Upstream Forwarding

   Forwarding in a LLN needs to account for requirements that are
   unusual in the IP world:

   perfect loop freedom is a non-goal

      the specification allows the wheel model where a packet circulates
      a bit around the destination till it finally makes it.





Thubert, et al.          Expires October 2, 2009               [Page 19]


Internet-Draft          LLN Routing Fundamentals              March 2009


   transient forwarding failure are commonplace

      This specification introduces the capability for the layer 2 to
      give a packet back to layer 3 in order to try another adjacency.

   Using the LLN Tree Discovery procedure, LLN Routers expose their path
   metrics using the Uniform Path Metric field in the TIO.  Neighbor LLN
   Routers with a lesser depth in the tree then self are forwarding
   parents.  Neighbor LLN Routers with a same depth in the tree are
   siblings.  Forwarding via parents ensures a loop free operation
   whereas forwarding via siblings may not be loopfree unless additional
   measures are taken.

   The approach taken in this specification is to favor forwarding via
   parents but enable forwarding via siblings as a backup option.
   Preferring the parents enables a forwarding gradient towards the LBR
   that limits the chances of multiple consecutive hops over siblings.
   This specification also prevents from returning a packet back to the
   neighbor that just passed it.  This simple rule coupled with the
   forwarding gradient protect against loops for a vast majority of
   cases, and the specification relies on a appropriate setting of the
   TTL in a given deployment to protect against meltdowns.

   In more details:

   o  A LLN router MUST send upstream data to its forwarding parent with
      smallest metric.  Note that, depending on the way the routing
      protocol determines this metric, and the dynamics of the tree, the
      best forwarding parent at a given point of time is not necessarily
      the parent with the smallest depth or the parent in the logical
      tree defined by the Tree Discovery procedure.

   o  If the transmission of an upstream packet to that preferred parent
      fails (due to a node or link failure, or mobility), the LLN router
      MAY attempt to forward the packet again via other parents, as
      ordered by best metric.

   o  If the transmission to both primary and secondary forwarding
      parents fails, the LLN Router MAY forward the packet via siblings,
      as ordered by best metric.

   o  When the transmission fails and the packet is retried via a
      different neighbor, the router MUST decrease the TTL by one.

   In order to enable these rules, a LLN router maintains a blacklist
   per packet being forwarded that contains:





Thubert, et al.          Expires October 2, 2009               [Page 20]


Internet-Draft          LLN Routing Fundamentals              March 2009


   o  the neighbor that forwarded the packet to self

   o  neighbors to which forwarding of this packet failed

   These rules are illustrated in the following figure which represents
   a subset of an LLN.


        D,1,3   B,1,7
            |   /
            |  /
            | /
   C,2,9--- A,2,8

   An LLN Router is identified by <Id,Depth,Metric>.  LLN Router A has
   three neighbors B,C,D. D is A's primary forwarding parent as it is
   the neighbor with the smallest Metric amoung neighbors with smaller
   depth.  If transmission to D fails, A sends the packet to B, which is
   of smaller depth.  If transmission to B fails, A transmits to C.
   Because C is at the same depth as A, a blacklisting policy is used to
   avoid that C retransmits to A.

4.2.  Downstream Forwarding

   Downstream routing using LLN fundamental mechanisms can occur using
   either hop-by-hop state, source routing or a combination of them
   (loose source route).  By default the LLN Dissemination mechanism
   builds up hop-by-hop distance-vector routing information in each of
   the routers along the tree up to the root for each address, prefix or
   group ID.

   Source routing can optionally be supported by either requesting a
   route record header from a node, or by having nodes send periodic
   route record headers up to the root.  Route Dissemination also allows
   a compression of the Routing header when the routes match the
   topology as traced by Record Route on a per packet basis.  In
   particular, if a Route Dissemination route exists to the first entry
   in the Record Route header via the source of the packet, then the
   router can override the source of the packet with its address without
   adding the original source to the Record Route.  At that point, the
   routing header operation becomes loose, in other words an hybrid
   between transparent hop-by-hop (stateful) and source routing.

   Therefore three different downstream techniques are supported:

   o  Hop-by-hop forwarding.  When only partial route dissemination data
      reaches a LLN Border Router, it only knows the next-hop to a given
      LLN Router in the network.  In this case, each LLN Router relaying



Thubert, et al.          Expires October 2, 2009               [Page 21]


Internet-Draft          LLN Routing Fundamentals              March 2009


      downstream data will select the next-hop according to the
      information it receives during route dissemination.

   o  Full source routing.  When all the route dissemination data
      reaches a LLN Border Router, it one can choose to specify the full
      list of LLN Routers to be traversed in each downstream data
      packet.

   o  Loose source routing.  When the source route information is
      compressed because of existing state in the routers along the
      path.


5.  Multicast Support

5.1.  Overview

   Wherever we mention <MLD>, one can read MLDv2,3 for IPv6.  Doing IGMP
   over the LLN involves:

   o  LLN Border Router acting as a local Rendez-vous Point (RP) for the
      LLN and as source towards the Internet for all multicast flows
      started in the LLN.

   o  transporting <MLD> in Route Dissemination and recursive
      coalescence of the multicast requests.

5.2.  Receiver Flow

   The LBR is considered as a Rendezvous Point (RP) for all multicast
   flows issued from inside the LLN.  Multicast packets are passed up
   the tree to the LBR.

   Nodes talk <MLD> to their parent router.  The parent router forward
   the registration and inject their own as a special type of RIO for
   multicast groups, towards the LBR.  The LBR MAY participate to
   multicast in the infrastructure it is connected to and forward all
   the packets coming from the LLN.

   Between the parent router and the LBR, <MLD> requests are transported
   in the RIO; each hop aggregates the requests in a fashion that is
   similar to proxy IGMP, but this happens recursively between child
   node to parent router up to the LBR.  On the way, multicast routing
   states are installed in each router from the receiver to the root,
   enabling multicast routing down the LLN tree.






Thubert, et al.          Expires October 2, 2009               [Page 22]


Internet-Draft          LLN Routing Fundamentals              March 2009


5.3.  Source flow

   As a Node, the source is unaware of the ROLL protocol, and it uses
   standard protocols with the router (say in IPv6: Neighbor Discovery,
   <MLD> etc...).  So when it has a multicast packet to send, the source
   just forwards it to its default router, which is the expected
   standard behavior.  RRs on the way recursively forward to their
   parent.  At each hop, if a multicast route indicates that a listener
   is reachable via another child (but that from which the packet was
   received) then the packet is duplicated and forwarded to that child
   down the tree.

   If the LLN Border Router is configured to do so, it will source the
   packet to a real RP in the Internet.


6.  Advanced Features

   The fundamental mechanisms described in this document are sufficient
   to allow for upstream and downstream communication inside the LLN.
   They form a common basis upon which future LLN routing protocols can
   be designed.  This section indicates some possible advanced features
   which can be integrated to increase efficiency for a particular
   useage scenarios.

6.1.  Interaction with other routing protocols

   While network design and specific use cases are out of scope for this
   document, it must be noted that the ROLL fundamentals mechanisms
   described herein might be used in conjunction with other routing
   protocols vin order to fulfill the requirements of a particular
   deployment.  Here follows a non exhaustive series of examples
   illustrating such interactions.

6.1.1.  AODV/DYMO

   In the example of a closed loop between a sensor and a switch, a
   constrained optimized route must be installed between the 2 devices.

   Defining such a specific route is costly and should be performed on-
   demand when the bulk of the traffic is buffered data from source to
   sink.

   A reactive MANET protocol such as AODV [RFC3561], DSR [RFC4728] or
   DYMO [I-D.ietf-manet-dymo] can be deployed to enable such routing,
   though the QoS-constrained approach for AODV is stalled as a draft
   ([I-D.perkins-manet-aodvqos]).




Thubert, et al.          Expires October 2, 2009               [Page 23]


Internet-Draft          LLN Routing Fundamentals              March 2009


6.1.2.  OSPF/OLSR

   A federating backbone is the virtual root of a collection of trees
   that forms a single routing topology.  If that topology shares a same
   prefix, a sensor device can move freely within the topology without
   renumbering.The 6LoWPAN backbone link is an example of such a
   federating backbone and in that case, the protocol that enables any
   to any reachability is simply IPv6 Neighbor Discovery [RFC4861].

   In a generalized case with routing and multiple subnets, a
   traditional IGP such as OSPF [RFC2740] or a MANET protocol such as
   OLSR [RFC3626] can be deployed within the federating backbone between
   the LBR to advertise the routes learnt from the ROLL fundamentals
   dissemination protocol through the redistribution of route
   information.

   In turn, the routed federating backbone is just the instantiation at
   Depth 0 of the more general concept of beltlines.  A beltline is a
   set of routers of a same depth in a same tree that form a subarea
   where an IGP is run and route information from the LLN Route
   Dissemination protocol is redistributed.  This creates routes around
   the root and reduces the load that routing along the tree imposes on
   the lower depth of the tree.

   Note that in turn, beltline routes ARE NOT redistributed into LLN
   Route Dissemination information.  As a result, the beltlines routes
   are orthogonal to the route dissemination routes, and they should
   never collide, which optimizes the value of the control plane of the
   combination.

   Beltline routes should be used with caution in order to maintain
   stability and optimize the resulting routes:

   o  beltline routes should only be used when a certain topological
      stability was asserted

   o  using beltline routes discourages the reorganization of the tree,
      mostly when that causes a router to change its depth

   o  a divide and conquer approach to limit the size of a beltline
      enables to manage the cost of the control plane

   o  a beltline of depth 2 or more should be an arc as opposed to full
      circle.In the example of a closed loop between a sensor and a
      switch, a constrained optimized route must be installed between
      the 2 devices.





Thubert, et al.          Expires October 2, 2009               [Page 24]


Internet-Draft          LLN Routing Fundamentals              March 2009


6.1.3.  MIP6/NEMO

   MIP6 [RFC3775]and NEMO [RFC3963] enables a subtree to move away from
   the tree and maintain reachability as if the nodes in the subtree
   were still located in their topologically correct position.  This can
   be useful when a RIO aggregation is performed (see Section 6.6) to
   enable reachability of a stray device.  MIP6 be also be useful to
   enable a mobile display device such as a PDA to keep accessing a
   sensor network remotely without injecting the sensor network prefix
   into the infrastructure for security reasons.

6.2.  Route Optimization

   Whereas upstream and downstream communication is made possible by the
   fundamental mechanisms described in this document, applications may
   require more require traffic engineering, which may include:

6.2.1.  Node-to-node routing

   Node-to-node routing is ensured along the tree by the Route
   Dissemination protocol, and the packets flow via he first common
   parent.  This can be optimized if the LLN Border Router has a clear
   view of the topology (see 'Offline Path Computation' section).  In
   this case, the LLN Border Router can indicate the direct path between
   both LLN Routers, calculated offline, to the source, the destination,
   or both.  This technique induces a trade-off between multi-hop route
   efficiency and signaling overhead to setup this direct node-to-node
   path for instance as suggested in Section 6.1.1.

6.2.2.  Offline Path Computation

   Whereas nodes might not have the capacity to store and manage enough
   information to perform constrained routing, it is possible for node
   to report there neighborhood information to the LLN Border routers.
   LLN Border routers can then share their partial topology databases
   and get a full picture of the network.

   From there, it is possible to get LLN Border routers to compute
   shorter or constrained paths and either distribute them (e.g.  LDP)
   or pass the source route information to the end nodes.

   An OSPF example of that goes like this.  Nodes run HELLO or similar,
   and send their LSA in unicast to their LLN Border routers.  The LLN
   Border routers act as proxy for the nodes and share those LSAs with
   other LLN Border routers over the backbone.  At some point they
   converge and an LLN Border router will run SPF on behalf of all its
   registered nodes, one at a time.  The SPF computation should end at a
   certain distance from the node for which it makes more sense to go



Thubert, et al.          Expires October 2, 2009               [Page 25]


Internet-Draft          LLN Routing Fundamentals              March 2009


   through the backbone anyway.  Then the LLN Border router sends the
   set of routes to the node as an new topology that can be used in a
   MTR fashion.

6.2.3.  Graph forwarding

   Distance Vector and Link State routing protocols are traditionally
   designed in terms of:


   Links -> Metrics -> Routes -> network runtime

   Unless traffic engineering kicks in, either the routes are
   established over the shortest path and the alternate links are wasted
   or the traffic is load balanced in a fashion that represents the
   ratio of costs as opposed to the ratio of capacity of the paths.

   Also, the runtime of the network is opaque to the forwarding plane,
   so the only way to guarantee some end-to-end bandwidth for a class of
   traffic is to blindly reserve it, leading to even more waste of
   bandwidth when the reservation is not fully utilized.

   In order to optimize the network utilization, it would be beneficial
   to detect the saturation of the shortest path and load balance the
   extra traffic over alternate routes.  In the case of ROLL, it is also
   critical to be able to make a reroute decision on a per packet basis
   when hop by hop retries are exhausted.  Arpanet introduced a feedback
   loop into the routing protocol by making the metrics dynamic:


   Links ->  Metrics -> Routes -> network runtime
             ^                                  |
             |__________________________________|

   But this approach was unsuccessful, causing instabilities and
   disrupting the network.  With dynamic metrics, the duration of the
   convergence time - or frozen time -,increases with the number of
   links and the frequency of the metric updates.  During that time, the
   response of the network is undefined and temporary loops occur.

   An approach to solve this problem is having 2 independent sets of
   metrics: In one hand, the topological metrics that are rather static
   and mostly administratively set; and in the other hand the volatile
   metrics that are based on dynamic measurements of the network
   characteristics.

   The topological metrics are used by the ROLL routing protocol to
   initially build the tree as described in this specification.  The



Thubert, et al.          Expires October 2, 2009               [Page 26]


Internet-Draft          LLN Routing Fundamentals              March 2009


   volatile metrics are then used by a forwarding protocol to balance
   the traffic for that destination over the upstream links, thus
   modifying the way the graph is being used in runtime, without
   changing its structure.

   To get there, the control plane operates in 2 phases, in a lollipop
   fashion:


   Links->Metrics->Routes->netw. runtime->runtime metrics->forwarding
                              ^                                |
                              |________________________________|
   <--------------------------> <----------------------------------->
       ROLL routing protocol        ROLL forwarding protocol

   The ROLL fundamentals proposal builds shortest path trees to the
   exits but adds the capability to forward over another branch if
   sending a packet to a parent fails, either via any alternate parent
   or a sibbling.  So the paths that we really want to monitor are along
   the tree itself and one hop away from the tree.  To get there, the
   root emits a beacon that is multicasted down the tree and heard one
   hop away.  That beacon gathers the metrics that will be used for
   alternate parents and sibblings selection and nodes keep track of the
   beacon they hear for all the parents and sibblings they want to
   track.  From the beacon, they can infer the quality of the path
   through all the alternates and compare them.

6.3.  Density

   In a dense environment, it is useless that all routers that can
   provide backhauling service actually do so; in practice, limiting the
   number of routers that accept attached nodes saves memory in the
   attached nodes and reduces the cost of signalling.  Also, limiting
   the number of forwarding LLN Routers in the tree improves the
   multicast operations.

   Algorithms such a Trickle could be used by a LLN Router to decide to
   stop providing its access services for attached nodes if there are a
   number of neighboring routers that provide similar services.  The
   simplest abstraction of such similarity is that a multiple routers
   advertising a same depth, though such a simple similarity does not
   address the specifics of a router selection in the plugins.  In a
   more general fashion, a LLN Router can associate the concept of
   similarity with the characteristics of its own parent router
   selection plug in.






Thubert, et al.          Expires October 2, 2009               [Page 27]


Internet-Draft          LLN Routing Fundamentals              March 2009


6.4.  Digraph Dissemination

   The fundamental techniques described in this draft coverlays a tree
   for source/sink traffic over the physical topology.  This tree could
   be converted into a (bi)graph with additional overhead.  A LLN Router
   would therefore send route dissemination data to both its primary and
   secondary forwarding parents, hence informing a LLN Border Router of
   disjoint paths.  This makes sense in applications where the gains in
   increase downstream reliability outweigh the additional signaling
   overhead.

6.5.  Multiple LBRs and Trees

   The ROLL tree discovery technique propagates increasing depths and
   metrics throughout the network; upstream messages travel on a
   decreasing metric path back to the ROLL border router.  When the LLN
   features multiple LBRs, the following options appear:

   o  If the different LBRs share the same TreeID, a LLN Router
      implicitly sends its upstream data to the LBR which is closest in
      terms of aggregated metric.  This should be used whenever LBR play
      the same role.

   o  Different LBRs may choose to use different TreeIDs.  In this case,
      a LLN Router is part of multiple trees, one for eachTreeID.  When
      sending an upstream message, a LLN Router chooses on which TreeID
      it wishes to send, i.e. to which LBR.

   o  A hybrid case can exist in which some LBRs share the same TreeID
      while others have their dedicated tree ID.

   An alternative when having multiple LBR is to construct multiple
   trees (e.g. one for each LBR) and choose a default tree for
   forwarding data.  Using an alternate tree is possible only when
   labeling the data packet accordingly; an unlabeled packet is
   forwarded on the default tree.

6.6.  Aggregation for Route Dissemination

   Aggregation of prefixes on a same router

      When deploying an router with multiple interfaces, it makes sense
      to assign an aggregation prefix (shorter than /64) to the router
      and partition it as /64 prefixes over the router interfaces.  An
      router that owns a contiguous set of prefixes should only report
      the aggregation of these prefixes through Route Dissemination.





Thubert, et al.          Expires October 2, 2009               [Page 28]


Internet-Draft          LLN Routing Fundamentals              March 2009


   Aggregation of prefixes by a parent acting as ROLL Home

      There are also a number of cases where a ROLL aggregation is
      shared within a toon of LLN Routers.  For instance, a toon formed
      by firefighters and their commander.  In that case, it is still
      possible to use aggregation techniques with Route Dissemination
      and improve its scalability.  In that case, the commander is
      configured as the Route Dissemination aggregator for the group
      prefix.  In run time, it absorbs the individual RIO information it
      receives from the toon members down its subtree and only reports
      the aggregation up the TD tree.  This works fine when the whole
      toon is attached within the commander's subtree.

      But other cases might occur for which additional support is
      required:

      1.  the commander is attached within the subtree of one of its
          toon members.

      2.  A toon member is somewhere else within the TD tree.

      3.  A toon member is somewhere else in the Internet.

      In all those cases, a node situated above the commander in the TD
      tree but not above the toon member will see the advertisements for
      the aggregation owned by the commander but not that of the
      individual toon member prefix.  So it will route all the packets
      for the toon member towards the commander, but the commander will
      have no route to the toon and will fail to forward.

6.7.  Advanced Forwarding

   A blacklisting policy can be used to avoid routing loops when an
   upstream data packet is sent between neighbor LLN Routers of the same
   depth.  Alternatively, more general techniques can be used to avoid
   loops.  One is to record the sequence of already traversed nodes in
   the data packet as it travels along a multi-hop path.  When receiving
   a packet, a LLN Router may know whether it has already relayed that
   packet; if yes, it can know from which neighbors it had received it
   and to which it had sent.  A distributed version of depth first
   search can then be used to avoid routing loops.  This extension
   enables upstream packets to be sent to neighbors with a larger depth.


7.  Security Considerations

   As this draft suggests the use of new options carried in ICMP ND
   messages; the same security considerations as in [RFC4861] apply, in



Thubert, et al.          Expires October 2, 2009               [Page 29]


Internet-Draft          LLN Routing Fundamentals              March 2009


   particular with regards to the use of Secure ND [RFC3971] to protect
   against address theft.  Additionally link-layer security should be
   applied in the case of 6LoWPAN where SeND is not typically possible.


8.  IANA Considerations

   This draft would require two new ICMP options for use with ND: the
   Tree Information Option (TIO) and the Route Information Option (RIO).


9.  Acknowledgments

   The authors would like to thank Robert Assimiti, Kris Pister, Mischa
   Dohler, Julien Abeille, Ryuji Wakikawa, Teco Boot, Patrick
   Wetterwald, Bryan Mclaughlin and Carlos J. Bernardos for useful
   design considerations.


10.  References

10.1.  Normative References

   [RFC2460]  Deering, S. and R. Hinden, "Internet Protocol, Version 6
              (IPv6) Specification", RFC 2460, December 1998.

   [RFC4944]  Montenegro, G., Kushalnagar, N., Hui, J., and D. Culler,
              "Transmission of IPv6 Packets over IEEE 802.15.4
              Networks", RFC 4944, September 2007.

10.2.  Informative References

   [I-D.ietf-manet-dymo]
              Chakeres, I. and C. Perkins, "Dynamic MANET On-demand
              (DYMO) Routing", draft-ietf-manet-dymo-17 (work in
              progress), March 2009.

   [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-05
              (work in progress), February 2009.

   [I-D.ietf-roll-home-routing-reqs]
              Porcu, G., "Home Automation Routing Requirements in Low
              Power and Lossy Networks",
              draft-ietf-roll-home-routing-reqs-06 (work in progress),
              November 2008.



Thubert, et al.          Expires October 2, 2009               [Page 30]


Internet-Draft          LLN Routing Fundamentals              March 2009


   [I-D.ietf-roll-indus-routing-reqs]
              Networks, D., Thubert, P., Dwars, S., and T. Phinney,
              "Industrial Routing Requirements in Low Power and Lossy
              Networks", draft-ietf-roll-indus-routing-reqs-04 (work in
              progress), January 2009.

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

   [I-D.ietf-roll-urban-routing-reqs]
              Dohler, M., Watteyne, T., Winter, T., Barthel, D.,
              Jacquenet, C., Madhusudan, G., and G. Chegaray, "Urban
              WSNs Routing Requirements in Low Power and Lossy
              Networks", draft-ietf-roll-urban-routing-reqs-05 (work in
              progress), March 2009.

   [I-D.perkins-manet-aodvqos]
              Perkins, C. and E. Belding-Royer, "Quality of Service for
              Ad hoc On-Demand Distance Vector Routing",
              draft-perkins-manet-aodvqos-01 (work in progress),
              November 2001.

   [RFC2740]  Coltun, R., Ferguson, D., and J. Moy, "OSPF for IPv6",
              RFC 2740, December 1999.

   [RFC3561]  Perkins, C., Belding-Royer, E., and S. Das, "Ad hoc On-
              Demand Distance Vector (AODV) Routing", RFC 3561,
              July 2003.

   [RFC3626]  Clausen, T. and P. Jacquet, "Optimized Link State Routing
              Protocol (OLSR)", RFC 3626, October 2003.

   [RFC3775]  Johnson, D., Perkins, C., and J. Arkko, "Mobility Support
              in IPv6", RFC 3775, June 2004.

   [RFC3963]  Devarapalli, V., Wakikawa, R., Petrescu, A., and P.
              Thubert, "Network Mobility (NEMO) Basic Support Protocol",
              RFC 3963, January 2005.

   [RFC3971]  Arkko, J., Kempf, J., Zill, B., and P. Nikander, "SEcure
              Neighbor Discovery (SEND)", RFC 3971, March 2005.

   [RFC4728]  Johnson, D., Hu, Y., and D. Maltz, "The Dynamic Source
              Routing Protocol (DSR) for Mobile Ad Hoc Networks for
              IPv4", RFC 4728, February 2007.




Thubert, et al.          Expires October 2, 2009               [Page 31]


Internet-Draft          LLN Routing Fundamentals              March 2009


   [RFC4861]  Narten, T., Nordmark, E., Simpson, W., and H. Soliman,
              "Neighbor Discovery for IP version 6 (IPv6)", RFC 4861,
              September 2007.


Authors' Addresses

   Pascal Thubert
   Cisco Systems
   Village d'Entreprises Green Side
   400, Avenue de Roumanille
   Batiment T3
   Biot - Sophia Antipolis  06410
   FRANCE

   Phone: +33 4 97 23 26 34
   Email: pthubert@cisco.com


   Thomas Watteyne
   UC Berkeley
   497 Cory Hall #1774
   Berkeley Sensor & Actuator Center
   Berkeley, California  94720-1774
   USA

   Phone: +1 (510) 333-4437
   Email: watteyne@eecs.berkeley.edu


   Zach Shelby
   Sensinode
   Kidekuja 2
   Vuokatti  88600
   FINLAND

   Phone: +358407796297
   Email: zach@sensinode.com













Thubert, et al.          Expires October 2, 2009               [Page 32]


Internet-Draft          LLN Routing Fundamentals              March 2009


   Dominique Barthel
   Orange Labs
   28 chemin du Vieux Chene, BP98
   BP98
   Meylan  38243
   FRANCE

   Phone: +33476764522
   Email: dominique.barthel@orange-ftgroup.com










































Thubert, et al.          Expires October 2, 2009               [Page 33]