Re: [Roll] Interest in opportunistic routing?

[Ines Robles <[e-mail]>]

Hi Simon,

Thank you very much for share ORPL with us.

I think it would be good to present it in the plugfests in next IETFs, in
case that it takes place.

The plugfest for this last IETF [
http://www.ietf.org/proceedings/89/slides/slides-89-6tisch-0.pdf] starting
in slide 65.

Kind Regards,

Ines.


2014-03-07 15:17 GMT-03:00 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
>>>
>>>
>>
>
> _______________________________________________
> Roll mailing list
> [e-mail]
> https://www.ietf.org/mailman/listinfo/roll
>
>