Subject: [Roll] editing of section 3

From: Philip Levis <[email-masked]>
Date: Thu, 5 Nov 2009 19:52:36 -0800

Feedback/comments appreciated. Mostly, do people feel this makes  
things clearer? Please note some terminology is in flux (e.g. this  
text still uses inward/outward rather than up/down).

Phil

3.  Protocol Model

   The aim of this section is to describe RPL in the spirit of
   [RFC4101].  Protocol details can be found in further sections.

   3.1 Overview

  Each RPL instance constructs a routing topology optimized for a  
certain Objective
  Function (OF). An instance may provide routes to certain destination  
prefixes.
  A single RPL instance consists of one or more DAG roots. These roots  
may
  operate independently, or may coordinate over a non-RPL backchannel.  
Each root
  has a unique identifier, such that nodes can identify the root of a  
route.

  3.1.1: Multipoint-to-Point Traffic

  Multipoint-to-Point (MP2P) is a dominant traffic flow in many
  LLN applications ([I-D.ietf-roll-building-routing-reqs],
  [I-D.ietf-roll-home-routing-reqs], [RFC5673], and [RFC5548]).  The
  destinations of MP2P flows are designated nodes that have some  
application
  significance, such as providing connectivity to the larger Internet or
  core private IP network. RPL supports MP2P traffic by allowing MP2P
  destinations to be DAG roots.

3.1.2 Point-to-Multipoint Traffic Flows

  Point-to-multipoint (P2MP) is a traffic pattern required by several
  LLN applications[cite]. RPL supports P2MP traffic by using a  
destination
  advertisement mechanism that sets up routes toward destination  
prefixes and
  away from roots. Destination advertisements can update routing  
tables as
  the underlying DAG topology changes.

3.1.3 Point-to-Point Traffic Flows

  RPL DAGs provide a basic structure for point-to-point (P2P) traffic.
  For a RPL network to support P2P traffic, a root must be able to
  route packets to a destination. Nodes within the network may also
  have routing tables to destinations. A packet flows towards a root
  until it reaches a node that has a known route to the destination.
  RPL supports the case where a P2P destination is a `one-hop' neighbor.

  RPL neither specifies nor precludes additional mechanisms for
  computing and installing more optimal routes to support arbitrary P2P
  traffic.

3.2.  DAG Construction and the DAG Information Object (DIO)

  RPL creates minimum cost routes to DAG roots. RPL nodes construct  
these
  DAGs through DAG Information Object (DIO) messages.
  A DIO identifies the DAG root, the Objection Function (OF) of the DAG,
  the position of the transmitter within the DAG, and other routing
  information. RPL uses DIOs to establish and maintain routes. RPL
  adapts the rate at which nodes send DIOs. When a DAG is inconsistent
  or needs repair, RPL sends DIOs more frequently. As the DAG
  stabilizes, the DIO rate tapers off, reducing the maintenance cost
  of a steady and well-working DAG.

3.2.1  Grounded and Floating DAGs

  DAGs can be grounded or floating. A grounded DAG that offers  
connectivity to
  to an external routed infrastructure. A floating DAG offers no such
  external connectivity, and provides routes only to nodes within the  
DAG.

3.2.2  Objective Function (OF)

  The Objective Function (OF) conveys and controls the optimization
  objectives of route selection within a DAG. The Objective Function
  defines the cost function a RPL instance uses to compute minimum
  cost routes. Examples of simple optimization
  functions include minimizing latency, maximizing throughput, or
  minimizing energy spent. An Objective Code Poiint (OCP) specifies
  the Objective Function of the DAG. Further details can be found in
  [I-D.ietf-roll-routing-metrics].

  This document describes a default OF, OF0 (designated by OCP value  
of 0x0000).
  OF0 may be used to d code efine RPL behaviors in the case where a  
node encounters a
  DIO message  containing a point that it does not support, if allowed  
by
  policy. [I-D.ietf-roll-routing-metrics] contains additional OFs.

3.2.3  Administrative Preference

  An DAG instance may specify that some DAG roots should be used over  
others
  through an administrative preference. Administrative preference  
offers a
  way to control traffic and engineer DAG formation in order to better
  support application requirements or needs.

3.2.4  Distributed Algorithm Operation

  A high level overview of the distributed algorithm which constructs
  the DAG is as follows:

  o  Some nodes are DAG roots, with associated administrative  
preferences.

  o  Nodes advertise their presence, DAG instance, and routing cost
     with DIO messages sent to the link-local multicast address.

  o  Nodes listen for DIOs and use their information to join a new DAG,
     maintain their position within an existing DAG, or improve their
     position within an existing DAG as according to the DAG's Objective
     Function.

  o  The nodes provision routing table entries for the destinations
     specified by the DIO towards their DAG Parents.  Nodes may
     provision a DAG Parent as a default gateway.

  o  RPL supports both global and local DAG repair. Each DAG root
     maintains a sequence number. Incrementing this sequence number
     institutes a global repair, allowing nodes to choose an arbitrary
     new position within a DAG.

  o  Nodes may locally repair or change the topology, moving within
     the DAG without requiring a global repair event. The OCP
     specifies the limits of this local repair.

  o  Using both DIOs and possibly information in data packets,
     RPL nodes detect possible routing loops. When a RPL node detects a
     possible routing loop, it adapts its DIO transmission rate to
     quickly apply these local repair to the topology. This process
     and its limitations is discussed in greater detail in 3.4.

3.3  Outward Routes and the Destination Advertisement Object (DAO)

  RPL uses DIO messages to establish Inward routes from nodes within  
the LLN
  to DAG roots. It uses Destination Advertisement Object (DAO) messages
  to establish Outward routes from DAG roots to nodes within the DAG.  
DAO
  messages and Outward traffic are an optional feature for applications
  that require P2MP traffic. DIO messages advertise whether a DAG
  instance supports DAOs.

3.3.1  Destination Advertisement Object (DAO)

  A Destination Advertisement Object conveys destination information
  so that a root (and other nodes within the network) can establish  
Outward
  routes. A DAO message includes prefix information to identify  
destinations,
  reverse route information to record routes, and information to  
determine the
  freshness of a particular advertisement. Nodes send DAOs Inward  
towards
  DAG Roots.

  Nodes that can maintain routing state may aggregate routes they
  received in the DAOs they transmit. Nodes that cannot maintain
  routing state forward DAOs toward the DAG Root and adds
  the next-hop address to a Reverse Route Stack carried within
  the DAO message.

3.3.2.  `One-Hop' Neighbors

  In addition to sending DAOs toward DAG roots, RPL nodes may  
periodically
  emit a link-local multicast DAO message advertising available
  destination prefixes.  This mechanism allow provisioning a trivial
  `one-hop' route to local neighbors.

3.4.  Loop Detection and Limiting Local Repair

  RPL nodes maintains route cost information within a DAG. Because links
  may fail or change over time, nodes can move within a DAG. If routers
  only move Inward, the DAG remains consistent. However, if a router  
moves
  Outward, it can create a routing loop. RPL embeds information in data
  packets that enable it to quickly detect potential loops and locally  
repair
  the DAG. A data packet includes the route cost metric of the  
transmitter:
  if a router receives a packet from a router that advertises a cost  
lower
  than its own, there may be a routing loop.

  Allowing nodes to move Outward can, in the case of a Floating DAG,
  lead to the count-to-infinity problem, where nodes continuously move
  Outward as they search for a route to a DAG Root.
  RPL allows a DAG Instance to specify the amount of local repair a  
router may
  apply. If a router is unable to find a valid route after this amount  
of repair,
  it marks itself as Floating until the DAG Root applies a global  
repair by
  incrementing its sequence number. If the local repair limit is zero,  
then
  a router cannot move Outward without a global repair. If the local  
repair
  limit is infinity, then routers may locally repair freely and can  
suffer
  from the count-to-infinity problem.

---

From: Alexandru Petrescu <[email-masked]>
Date: Mon, 09 Nov 2009 12:49:04 +0100

Philip Levis a écrit :
> Feedback/comments appreciated. Mostly, do people feel this makes things 
> clearer? Please note some terminology is in flux (e.g. this text still 
> uses inward/outward rather than up/down).

When trying to make the description clearer...

As a side note.  I like rfc4101 too, especially because each example it 
gives is using (1) a topology and (2) a message exchange.

I think it would be helpful if section 3 of RPL did so too.

A simple and meaningful topology is very important.  Meaningful i.e. one 
can easiliy put addresses on it and have a clear idea about its subnet 
structure.  I.e. I can go to the lab now and do it.

This topology is missing from RPL document current.  It draws topologies 
in the appendix but they are not understandable (to me), because I don't 
see where and how could I put addresses, how many interfaces, etc.

The (2) message exchange is completely missing from the current RPL 
document.  Something like this, quote from rfc4101:
>           Client                                       Server
>           ------                                       ------
>                                       <-- Change L(CCID, 3 2)
>           Confirm R(CCID, 3, 3 2)  -->
>                      * agreement that CCID/Server = 3 *

Alex

>  Each RPL instance constructs a routing topology optimized for a certain 
> Objective
>  A single RPL instance consists of one or more DAG roots. These roots may
>  has a unique identifier, such that nodes can identify the root of a route.
> 
>  destinations of MP2P flows are designated nodes that have some application
>  LLN applications[cite]. RPL supports P2MP traffic by using a destination
>  advertisement mechanism that sets up routes toward destination prefixes 
> and
>  away from roots. Destination advertisements can update routing tables as
>  RPL creates minimum cost routes to DAG roots. RPL nodes construct these
>  external connectivity, and provides routes only to nodes within the DAG.
> 
>  This document describes a default OF, OF0 (designated by OCP value of 
> 0x0000).
>  OF0 may be used to d code efine RPL behaviors in the case where a node 
> encounters a
>  DIO message  containing a point that it does not support, if allowed by
>  An DAG instance may specify that some DAG roots should be used over others
>  through an administrative preference. Administrative preference offers a
>  o  Some nodes are DAG roots, with associated administrative preferences.
> 
>  RPL uses DIO messages to establish Inward routes from nodes within the LLN
>  to establish Outward routes from DAG roots to nodes within the DAG. DAO
>  so that a root (and other nodes within the network) can establish Outward
>  freshness of a particular advertisement. Nodes send DAOs Inward towards
>  DAG Roots.
> 
>  In addition to sending DAOs toward DAG roots, RPL nodes may periodically
>  only move Inward, the DAG remains consistent. However, if a router moves
>  the DAG. A data packet includes the route cost metric of the transmitter:
>  if a router receives a packet from a router that advertises a cost lower
>  apply. If a router is unable to find a valid route after this amount of 
> repair,
>  it marks itself as Floating until the DAG Root applies a global repair by
>  incrementing its sequence number. If the local repair limit is zero, then
>  a router cannot move Outward without a global repair. If the local repair
>  limit is infinity, then routers may locally repair freely and can suffer
> _______________________________________________
> Roll mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/roll
>