Re: [Roll] Interest in opportunistic routing?

[Simon Duquennoy <[e-mail]>]

Dear Pascal,

AFAICT it does go along the same lines as Quentin's work. The main
difference is that we support addressable nodes, i.e. not only upwards but
also downwards routing.

As you're asking for more, let me elaborate a bit on how I see our protocol
(ORPL) integrated in RPL :)
* routing decision (assuming storing mode): the forwarding decision is made
at the receiver, not at the sender. Upon receiving a packet, a node decides
whether to forward it based on (1) its rank and (2) the inclusion of the
destination IPv6 address into its routing table.
  - If the packet is going up and the node has a lower rank then it will
forward with upwards anycast.
  - If the packet is going up or down and the node has a higher rank, and
the destination IPv6 address is in the routing table (i.e. the destination
is below in the DODAG) then it will forward with downwards anycast.
One interesting thing is any-to-any routing is that ORPL has many more
common ancestors to use than RPL. In our experiments, any-to-any routing is
where the benefits of ORPL are most significant, with the latency between
leaf nodes improved with a factor up to 15 (case where RPL has a common
ancestor several hops away whereas ORPL exploits many ancestors closer to
the source and destination).
* routing tables: the standard RPL tables will do. It is however worth
noting that because anycast transmission do not target a specific receiver,
all we need at every node is not a full routing table (<destination,next
hop> pairs) but only a set of reachable destinations. This makes the table
potentially more compact. In the paper we investigate fancy structures for
this such as Bloom filter but I regard this as out of the scope for a
potential integration in standard RPL.
* routing metric: ORPL can work with any routing metric, the only
requirement is to have a DODAG. In the SenSys'13 paper we use our own
metric, which is opportunistic routing-oriented. It helps but isn't
strictly required (could possibly be the object of a separate draft)

Regarding performance: our testbed experiments are on duty-cycled 802.15.4
nodes. We get great reliability. In the current implementation of ORPL
(posterior to the paper) we have most of the runs with 100% delivery ratio
(about 1500 packets sent and received end-to-end during the course of an
hour). The reason is that ORPL is not affected at all by isolated link
losses. It doesn't even notice it. If the link a parent is dead for some
time then another parent will forward the packet. The other side benefits
are latency and energy: when having duty cycled nodes, anycast nicely uses
the first that wakes up and gets the packet successfully, making the wakeup
procedure cheaper. A final note: opportunistic routing is great especially
in dense environments, as there are more links to exploit. In sparser
environments, as far as we have observed, the benefits reduce but are still
present.

The SenSys'13 paper contains a detailed design and thorough experimental
evaluation:
http://www.simonduquennoy.net/papers/duquennoy13orpl.pdf

If you want to know even more, I'm open to having a phone call.

Best,
Simon



On Fri, Mar 7, 2014 at 4:28 PM, Pascal Thubert (pthubert) <
[e-mail]> wrote:

>  I'd love to hear more. This work reminds me of interesting Results
> Quentin showed at his PhD...
>
> Pascal
>
> Le 7 mars 2014 à 14:47, "Simon Duquennoy" <[e-mail]> a écrit :
>
>    On Fri, Mar 7, 2014 at 1:37 PM, Michael Richardson <
> [e-mail]> wrote:
>
>>
>> Simon Duquennoy <[e-mail]> wrote:
>>     > We have designed an opportunistic extension of RPL, where the basic
>> idea is to
>>     > exploit all links of the DODAG rather than the tree defined by
>> links to
>>     > preferred parents. We do this using anycast: transmissions are
>> intended either
>>     > (upwards) to any parent or (downwards) to any child having the
>> destination
>>     > below in the DODAG.
>>
>> This is very interesting.
>>
>>     > We have a working prototype [1] in Contiki that we evaluated
>> thoroughly in a
>>     > 135-node testbed [2]. In a 4-min packet interval data collection,
>> we increase
>>     > the reliability of RPL from 97.4 to 99.5%, while halving the
>> latency (below
>>     > 0.5s) and radio duty cycle (below 0.5%).
>>
>>     > If there is interest, we can come up with a simplified version of
>> the design
>>     > presented in the paper, and propose a way to integrate it in RPL
>> through only a
>>     > few minor additions. To be more specific, the simplified version
>> would use the
>>     > existing RPL routing tables rather than Bloom filters, and would be
>> MAC-layer
>>     > agnostic (the only assumption being that the MAC layer supports
>>     > anycast).
>>
>> I'm not familliar with the concept of anycast at layer-2.
>> I think that ethernet supports this, but that actually one would have the
>> multicast bit set.  I think that you'd have to do the same thing on
>> 802.11.
>> I guess that 15.4 has a specific support for this, or is just a choice of
>> a
>> particular unicast mac?
>>
>
>  Dear Michael, all,
>
>  There is no specific support for anycast in 802.15.4, but the standard
> MAC layers can easily be used for anycast (often by setting
> multicast/broadcast + ACK bits).
> I've see prototypes for 802.15.4 beacon-enabled [1], for a 15.4e RIT-like
> MAC [2], and for a CSL-like MAC (our own implementation uses ContikiMAC,
> which is similar CSL).
> Should also be possible with 15.4 TSCH or even 802.11 PSM.
> Doing this on an always-on link like ethernet or traditional 802.11 is
> more tricky because you need an agreement procedure so that only one
> neighbor that received the packet forwards it. There exist solutions for
> WiFi, such as ExOR [3], which introduced opportunistic for 802.11 back in
> 2005. I don't think we want to go into this though; I'd rather simply
> stipulate that anycast is required at the MAC layer and possibly give some
> hints on how to support it on the most common MAC protocols.
>
>  Best,
> Simon
>
>  [1]
> http://clarinet.u-strasbg.fr/~theoleyre/uploads/Publis/pavkovic11rpl.pdf
>  [2] http://www.ti5.tuhh.de/publications/2012/EWSN12_Orinoco.pdf
> [3] http://en.wikipedia.org/wiki/ExOR_(wireless_network_protocol)
>
>
>> --
>> Michael Richardson <[e-mail]>, Sandelman Software Works
>> IETF ROLL WG co-chair.    http://datatracker.ietf.org/wg/roll/charter/
>>
>>
>> _______________________________________________
>> Roll mailing list
>> [e-mail]
>> https://www.ietf.org/mailman/listinfo/roll
>>
>>
>    _______________________________________________
> Roll mailing list
> [e-mail]
> https://www.ietf.org/mailman/listinfo/roll
>
>
> _______________________________________________
> Roll mailing list
> [e-mail]
> https://www.ietf.org/mailman/listinfo/roll
>
>