Re: [Roll] Interest in opportunistic routing?

[Simon Duquennoy <[e-mail]>]

Dear Ines,

Do you mean you see ORPL fitting 6TiSCH? I was mostly targeting ROLL, as I
see ORPL as a mac-independent addition to RPL.
That being said, yes, thanks for the invite, I'll definitely consider
presenting it at the next plugfest (potentially along with a TSCH
implementation in Contiki that we hope to have by then).

Best regards,
Simon



On Sat, Mar 8, 2014 at 5:20 PM, Ines Robles
<[e-mail]>wrote:

> 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
>>
>>
>
> _______________________________________________
> Roll mailing list
> [e-mail]
> https://www.ietf.org/mailman/listinfo/roll
>
>