Subject: [Roll] Optimization to trickle-mcast

From: Owen Kirby <[email-masked]>
Date: Thu, 12 May 2011 13:17:04 -0700

Hi,

I wrote this up a while back before trickle-mcast was adopted as a ROLL 
WG document, I think it could be used to optimize the multicast 
performance of a dense RPL network by eliminating unnecessary 
retransmissions. If it doesn't break anything, it only requires a small 
change to the multicast forwarding logic.

Thanks,
Owen Kirby

The problem:
------------
With trickle multicast as it is current written, the number of frames
resulting from a single multicast packet scales linearly with the number of
devices on the network (eg: O(n)). This causes particular pain in dense
networks where many devices are retransmitting within range each other.
Excessive retransmissions increase battery life, network congestion, and
the probability of channel-access collisions.

Consider the case of a dense network consisting of many nodes all within
one hop of the DAG root (A), or another mains-powered router (B) or (C):

             o
        o
     o    (A)   o
         /   \       o
        /     \    o
   o   /   o   (C)   o
     (B)
    o               o
         o     o

The goal of a multicast packet, is to reach every node on the DAG, and to
accomplish this goal we only need to retransmit the multicast from nodes
(A), (B), and (C). By identifying these three nodes as mutlicast forwarders
we can efficiently multicast to all devices in this network, regardless of
the number of devices in this network.

However, not all networks may be so convenient, and there may be cases where
a few devices are not located in the "dense clump", yet are still interested
in multicast transmissions. Such a network might look something like:

             o
        o
     o    (A)   o
         /   \       o
        /     \    o
   o   /   o   (C)   o
     (B)          \
    o              (D) ------ (e)
         o     o

In this network, device (e) would form a route to the DAG root through its
best parent (D), and informs the root by sending a DAO. A successful 
multicast
packet now requires retransmissions from (A), (B), (C) and (D).

If we had a mechanism to identify these key devices, then we can reduce the
number of retransmission on a network (and the probability of 
collisions); thus
increasing reliability and battery life. In a RPL network, we can identify
these key devices by inspecting the routing messages. Routers which have 
child
nodes can be considered key devices, and devices without children need not
waste energy by retransmitting multicasts.

The solution:
-------------
By default, only the DAG root is considered a multicast forwarder. A 
multicast
forwarder MUST retransmit multicast packets with non-local scope. Devices
that are not forwarders SHOULD NOT retransmit multicast packets.

Any member of the DAG that finds itself in a routing path MUST become a
multicast forwarder. In this case, any device that is unable to reach the
DAG root directly must select a suitable RPL parent, which also indicates
that the parent may be required to retransmit multicasts from the DAG for
the child to be able to receive them.

We propose the following:

1) RPL devices have a boolean flag isMulticastForwarder.
   a) The DAG root MUST always have isMulticastForwarder==TRUE.
   b) RPL leaf nodes MUST always have isMulticastForwader==FALSE.
   c) RPL routers SHOULD initialize isMulticastForwader=FALSE.

2) When a RPL router identifies that it is in a routing path, it MUST set
   isMulticastForwader=TRUE. A router can determine this by one of the 
following:
   a) Receiving a DAO in storing mode.
   b) Forwarding a DAO in non-storing mode.
   c) Forwarding a packet containing the RPL hop-by-hop option.
   d) An explicit notification using a unicast DAO to the parent with a
      multicast target address (FF00::/8). We recommend this option to give
      room for future optimization, and to deal with link asymmetry.

3) When receiving a multicast packet with non-local scope, devices 
SHOULD NOT
   retransmit it unless isMulticastForwarder==TRUE. Devices that forward 
the
   packet MUST do so according to draft-ietf-trickle-mcast-01 to prevent
   flooding.

4) In the case of 2.d, every node must send a unicast DAO to its parent(s)
   with a target address of FF00::/8 when it joins a DAG. Using longer
   prefixes may allow for future optimizations by limiting the size of the
   multicast forwarding tree based on the multicast address.

Link Asymmetry:
---------------
RPL parent selection is based of the quality of link from the child to its
parent (as defined by the objective function). However the multicast 
path use
the link in both directions, depending on where the source is located. 
As such,
strong link asymmetry may have adverse effects on the selection of 
multicast
routers. If the objective function selects an asymmetric route to the 
DAG root,
then multicast forwarding will work better if an explicit DAO with a 
multicast
address is sent to a parent with a symmetric link.

Network stability:
------------------
The efficiency of this proposal depends on minimizing the number of 
multicast
forwarders. However, we have only defined a mechanism to set
isMulticastForwarder and no mechanism to clear it. Therefore, in a network
with significant routing churn, the ratio of multicast forwarders to routers
in the DAG will increase towards 100% over time. If the ratio reaches 100%
then this proposal will behave exactly the same as the trickle multicast 
draft.

It is strongly recommended that a mechanism to clear isMulticastForwarder
should be defined when a path is no longer used. As an example, if using
an explicit notification, the DAO transit lifetime could specify a timeout
and isMulticastForwarder could be replaced with a timer that tracks the
maximum lifetime received from all children.