Subject: [6tsch] uRes: distributed scheduling

From: Thomas Watteyne <[email-masked]>
Date: Thu, 31 Jan 2013 09:39:01 -0800

Qin,
Thanks for introducing uRes. As per Don's suggestion, I'm branching this
thread and editing the subject.
Thomas

On Thu, Jan 31, 2013 at 6:42 AM, Mischa Dohler <[email-masked]>wrote:

> Qin,
>
> I like this and would like to hear more about it. Do you have some
> papers/results?
>
> You can turn the problem as you want* but if you really want a multihop
> system to scale (beyond some 500-1000 nodes), you need a distributed system
> and some machine learning** on top. This is because in static link
> topologies, the aggregate set of locally-chosen links will converge
> eventually to the optimal path; there will be no routing solution for
> ergodic (completely dynamic) link topologies beyond DTN approaches (just
> take it); and non-ergodic (but also non-static) link topologies, where
> links are occasionally in outage, can only be handled in a distributed
> fashion.
>
> So I am all in for seeing how you could make .15.4e & RPL work closely
> together in a distributed fashion.
>
> Thanks,
> Mischa.
>
> * The adhoc community is very good at this: they have published zillions
> of papers, proposed millions of protocols, have loads of RFCs but no viable
> product after 50 years of work - mobility/dynamics are very fundamental
> problems which you can only solve meaningfully with one-hop star-topology
> technology ... wait ... this is cellular.
>
> ** We recently standardized some machine learning approaches in a
> broadband standard; setting was different but problem the same.
>
> ______________________________**____
>
> Mischa Dohler
>
> Director of Research, CTTC
> Distinguished Lecturer, IEEE
> Editor-in-Chief, ETT
> BoD, Worldsensing
>
> Mob: +34 679 094 007
> Tel: +34 936 452 909
> Fax: +34 936 452 901
>
> www.cttc.es/home/mdohler
> ______________________________**____
>
>
> On 30/01/2013 22:37, [email-masked] wrote:
>
>> Hi,
>>
>> As Thomas and Xavi explained, RPL is responsible for choosing a *Path*,
>> i.e. next hop neighbor, and asking TSCH to forward packets; and TSCH
>> provides a mechanism to use *Links* (neighbor, slot, channel, TX/RX),
>> which is the mapping of a *Path*, to conduct forwarding. Thus, the missing
>> piece is how to establish and maintain the *Links*.  My understanding is
>> that 6tsch will fill the gap. In addition, considering resource
>> constraints of devices and characteristics of IoT, 6tsch should be very
>> simple and flexible for wide range of application in terms of mobility,
>> density, latency,and so on.
>>
>> In UC@Berkeley, we have designed a protocol, called uRes. The function of
>> uRes is to establish and maintain the *Links* with neighbors. uRes is a
>> distributed protocol, i.e. the computation and communication for link
>> reservation just happen locally. uRes is coded in Information Elements
>> (IEs) of IEEE802.15.4e, thus, just fits to TSCH and provides flexibility
>> for further optimization and extension. uRes has been implemented in
>> OpenWSN (openwsn.berkeley.edu).
>>
>>
>> Regards
>> Qin
>>
>>
>>
>>
>>  On 30/01/13 07:04, Thomas Watteyne wrote:
>>>
>>>> Maybe too much room to be handled entirely by RPL. As I see it, RPL
>>>> only wants to know about some cost associated with the topology, and
>>>> uses that to compute multi-hop routes. In particular, I believe RPL is
>>>> more interested in /paths/ (the "performance" of the connection
>>>> between two neighbors), rather than the individual /links /making up
>>>> each path. In my opinion (and this is, I believe, perfectly in line
>>>> with *Xavi*'s comment), we could define a /6tsch/ layer which sits
>>>> between TSCH and RPL. The goal of this layer would be to (1) turn some
>>>> throughput requirements into /links /in the schedule and (2) collect
>>>> information and feedback /path/ statistics to RPL.
>>>>
>>> [...]
>>>
>>>  To come back to *Michael*'s comment, I believe that, with this setup,
>>>> RPL actually can be using traditional metrics (ETX, bandwidth,
>>>> latency, etc), the /6tsch/ layer taking care of MAC specifics.
>>>>
>>>>  Yep, that makes sense!  And as per Michael's comments, RPL can then
>>> handle the routing across different L2s.
>>>
>>>
>>> On 29/01/13 15:09, Michael Richardson wrote:
>>>
>>>> I agree. It's just that this is a new kind of metric: in the past we
>>>> have things like abtracted ETX, bandwidth available, power, latency,
>>>> etc... none of these things are a cyclic f(t). This new info is.
>>>>
>>> Is it appropriate for the 6tsch routing metrics to change (or as you put
>>> it, to be a cyclic function) *within* the period of a slotframe?
>>>
>>> For example, if node A is trying to transmit to node D and can go via
>>> either node B or node C, then the "best route" may toggle back and forth
>>> between B and C depending on which has the next available link(s),
>>> potentially multiple times per slotframe period.  Is this good
>>> behaviour?  I guess in the LoWPAN world it might be.
>>>
>>>
>>> I think I'd better stop asking open-ended questions now and go read some
>>> stuff :-)
>>>
>>> -----Nick
>>>
>>> --
>>> Nick Moore <[email-masked]> 0409 656 267
>>>
>>> ______________________________**_________________
>>> 6tsch mailing list
>>> [email-masked]
>>> https://www.ietf.org/mailman/**listinfo/6tsch<https://www.ietf.org/mailman/listinfo/6tsch>
>>>
>>>
>> ______________________________**_________________
>> 6tsch mailing list
>> [email-masked]
>> https://www.ietf.org/mailman/**listinfo/6tsch<https://www.ietf.org/mailman/listinfo/6tsch>
>>
>
> ______________________________**_________________
> 6tsch mailing list
> [email-masked]
> https://www.ietf.org/mailman/**listinfo/6tsch<https://www.ietf.org/mailman/listinfo/6tsch>
>

---

From: [email-masked]
Date: Thu, 31 Jan 2013 11:52:00 -0800

Hi Mischa,

Instead of talking about distributed/centralized scheduling policy, I
would like to clarify the function of 6tsch according to my understanding.

6tsch is a sub-layer between RPL and TSCH. Basically, 6tsch should provide
two functions, one is to establish and maintain the *Links* (neighbor,
slot, channel, TX/RX), which reflects bandwidth requirement from upper
layer, and is used by TSCH; another function is to provide statistics on
Link/Path Quality, which will be used by RPL to choose Path, and by itself
to maintain good Path quality.

Ideally, 6tsch should not correlate with link scheduling policies. In
another word, it should support both link schedulers running on some
center and link scheduler running on each node. Fortunately, TSCH already
provide services like add-link/remove-link, which allow the center device
set its scheduling results into each node. Then, the missing part is some
sort mechanism which allow nodes establish and maintain their *Links*
locally. That is what uRes is designed for.

Qin

> _______________________________________________
> 6tsch mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/6tsch
>

---

From: [email-masked]
Date: Thu, 31 Jan 2013 11:52:03 -0800

Hi Mischa,

Qin

---

From: [email-masked]
Date: Thu, 31 Jan 2013 11:52:06 -0800

Hi Mischa,

Qin