Re: [Roll] Interest in opportunistic routing?

[Simon Duquennoy <[e-mail]>]

As a complement:
* a visualization of ORPL during a 60-minute run:
http://simonduquennoy.net/resources/orpl-animation.html
* the slides of the SenSys'13 presentation:
http://simonduquennoy.net/resources/131111-oprl-sensys.pptx

Thanks,
Simon



On Fri, Mar 7, 2014 at 6:42 PM, Simon Duquennoy <[e-mail]> wrote:

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