Re: [6tsch] blacklisting (was "report flow contents")

[Thomas Watteyne <[e-mail]>]

*> (1) Network wide blacklisting can be used to avoid some frequencies
occupied by other networks in the same area.*
Agreed.

*> (2) Per-link blacklisting can be used when overprovision is applied.*
Agreed. In a centralized case, the PCE could (1) monitor per-channel
statistics on a bundle, (2) over-provision, (3) blacklist. It would be very
interesting to evaluate what the cost vs. benefits are if this is used (a
great academic project!). I believe we should have the mechanisms to be
able to do this in the future, if it turns out it's worthwhile the signal
overhead.

Thomas

On Mon, Sep 16, 2013 at 2:34 PM, Qin Wang <[e-mail]> wrote:

> Hi Thomas,
>
> I fully agree with you. + 2 more comments.
>
> (1) Network wide blacklisting can be used to avoid some frequencies
> occupied by other networks in the same area.
>
> (2) Per-link blacklisting can be used when overprovision is applied. For
> example, we need the bandwidth from nodeA to nodeB is 15 cells per
> slotframe. Assume it is known that channel-22 is very bad, and others are
> in good condition. Then, we can schedule 16 cells in one slotframe, and
> skip channel-22 every time when encountering it.
>
> What do you think?
>
> Thanks
> Qin
>
>
> On Tue, Sep 17, 2013 at 2:16 AM, Thomas Watteyne <
> [e-mail]> wrote:
>
>> *[changed thread subject from 'report flow contents' to 'blacklisting
>> (was "report flow contents")']*
>>
>> All,
>>
>> Great discussion!
>>
>> Allow me to sum up.
>>
>> Problem statement:
>>
>>    - At 2.4GHz, 16 orthogonal frequencies are available.
>>    - "blind" channel hopping exploits frequencies diversity by hopping
>>    on all 16 frequencies
>>    - because of interference and multi-path fading, some frequencies
>>    exhibit a worse Packet Delivery Ratio (PFD) than others
>>       - if because of interference, it is possible that same set of
>>       frequencies are "bad" in the whole network
>>       - if because of multi-path fading, the set of "bad" frequencies is
>>       different for every pair of neighbor nodes
>>
>> Network-wide blacklisting:
>>
>>    - goal: prevent all nodes in the network to use a given frequency
>>    - decision can be made by PCE after receiving statistics, or
>>    administratively by operator configuration
>>    - different mechanisms to blacklist a channel:
>>       - modify the hopping pattern to include the same frequency twice
>>       and remove another one. Can be done on-the-fly.
>>       - consider there are only 15 frequencies, and build a schedule
>>       with 15 channel offsets. Needs to be done before network starts (or long
>>       process of "freeing-up" one channel offset)
>>    - efficiency is limited since:
>>       - because of multi-path fading, a "bad" channel might not be bad
>>       for all bundles
>>       - limits frequency diversity
>>
>> Per-link blacklisting:
>>
>>    - goal: prevent a bundle (i.e. two neighbors scheduled to
>>    communicate) to use a given frequency
>>    - decision can be made based on the per-frequency statistics gathered
>>    (packet counters and/or RSSI/LQI)
>>    - problem:
>>       - changing the hopping pattern for a single bundle can create
>>       interference with other bundles since collisions are possible if hopping on
>>       different sets of frequencies.
>>    - solution (used by ISA100):
>>       - cancel a scheduled communication if that communication happens
>>       on the blacklisted channel
>>       - note that this will reduce the bandwidth of that bundle by 1/16,
>>       so needs possibly to be combined with adding 1/16 more cells to that bundle.
>>
>> Did I miss something?
>>
>> Thomas
>>
>>
>> On Mon, Sep 16, 2013 at 9:35 AM, <[e-mail]> wrote:
>>
>>>  Hi Qin,
>>>
>>>  "Link-by-link" adaptive channel hopping in ISA is used by a node to
>>> select the best frequencies for its further communication with its
>>> particular neighbor.
>>> And, cell over-provision (i.e. the combination of "channel offset" and
>>> "slot" info used for communication with a particular neighbor), might be
>>> used for evaluating the internal interference and BW requirements between
>>> two neighbors. Am I right?
>>>
>>> Best wishes,
>>> Pouria Zand
>>>
>>> On Sep 16, 2013, at 4:34 PM, "Qin Wang" <[e-mail]> wrote:
>>>
>>>   Hi Pouria and Diego,
>>>
>>>  I think the "link-by-link" adaptive channel hopping mechanism of
>>> ISA100.11a AND cell over-provision mechanism of 6top can be used together.
>>> Make sense?
>>>
>>>  Thanks
>>> Qin
>>>
>>>
>>> On Mon, Sep 16, 2013 at 8:56 AM, <[e-mail]> wrote:
>>>
>>>> Hi Diego,
>>>>
>>>> ISA100.11a considers the adaptive channel hopping on a link-by-link
>>>> basis, in addition to traditional blacklisting on the whole network. This
>>>> mechanism is described as following:
>>>>
>>>> "Additionally, a device may autonomously treat transmit links on
>>>> problematic channels as idle, thus reducing unnecessary interference and
>>>> wasted energy on channels with a history of poor connectivity. A device
>>>> skipping links in this manner should periodically test the links to verify
>>>> that they remain problematic. Such selective channel utilization can be
>>>> disabled by the system manager on a link-by-link basis, through the
>>>> attribute dlmo.Link[].Type.SelectiveAllowed. [1]"
>>>>
>>>> In this scheme, the sender/receiver consider the poor channel as idle.
>>>> The sender and receiver (on the poor edge) will still follow the defined
>>>> hopping pattern and they will not conflict with the rest of the network.
>>>> Potential Drawbacks: 1/16 of the resources might be wasted on that
>>>> edge, but the poor channel of that edge will be skipped, locally.
>>>> Important Strength: The overhead of this scheme is low.
>>>>
>>>> Best wishes,
>>>> puoria
>>>>
>>>> 1. IEC 62734: Industrial communication networks - Fieldbus
>>>> specifications - Wireless systems for industrial automation: process
>>>> control and related applications - ISA100.11a.
>>>>
>>>> -----Original Message-----
>>>> From: [e-mail] [mailto:[e-mail]] On Behalf
>>>> Of Prof. Diego Dujovne
>>>>  Sent: Friday, September 13, 2013 9:07 PM
>>>> To: Qin Wang
>>>>  Cc: Thomas Watteyne; 6TSCH
>>>> Subject: Re: [6tsch] report flow contents
>>>>
>>>>  Hi Qin,
>>>>           On the centralized case, changing the channel hopping
>>>> sequence (and thus blacklisting the channels with interference) on the
>>>> whole network, and not in a peer basis is not efficient in terms of channel
>>>> usage. Let me explain this with an
>>>> example:
>>>>
>>>> Let's say there is are 4 nodes: A, B, C and D. A and B are interfered
>>>> only on channel 4 by an external source, while C and D listen interference
>>>> only on channel 8. If I disable channel 4 and 8 by blacklisting both
>>>> channels from the hopping sequence, A and B won't be able to use channel 8
>>>> and C and D won't be able to use channel 4, both interference free between
>>>> them.
>>>>
>>>> On the distributed case, if two nodes are already connected and if both
>>>> detect a interfered channel they will (someway) agree to blacklist that
>>>> channel from the hopping sequence. But we have not arrived to this case yet
>>>> on 6TiSCH.
>>>>
>>>> On the other side, if we blacklist by changing the hopping sequence, a
>>>> node talking to different neighbours will have different channel hopping
>>>> sequences. And this increases complexity too.
>>>>
>>>> I don't have an answer (just questions) on how to reduce the
>>>> probability of using an interfered channel, but it seems that the current
>>>> tsch scheme does not allow a simple way to blacklist channels unless it is
>>>> done network-wide. To sum up, I'm worrying about reducing channel diversity.
>>>>
>>>> Thoughts?
>>>>
>>>>                                                          Diego
>>>>
>>>>
>>>>
>>>>
>>>>
>>>>
>>>> 2013/9/13 Qin Wang <[e-mail]>:
>>>> > Hi Diego,
>>>> >
>>>> > I understand, theoretically, dynamic allocation may have some
>>>> > advantages in terms of increasing reliability. But, in the channel
>>>> > hopping network, it is challenge for a node to catch up the channel
>>>> > hopping sequence change in its neighbors. Thus, I think, if updating
>>>> > channel hopping sequence, it could be better to do it in network
>>>> wide. What do you think?
>>>> >
>>>> > Thanks
>>>> > Qin
>>>> >
>>>> >
>>>> > On Fri, Sep 13, 2013 at 11:28 PM, Prof. Diego Dujovne
>>>> > <[e-mail]> wrote:
>>>> >>
>>>> >> Qin,
>>>> >>       I think frequency blacklisting on a node-pair basis (either
>>>> >> centralized or distributed) would break the schedule matrix
>>>> >> structure, which overrides narrowband interference by channel
>>>> >> hopping.
>>>> >> If frequencies are blacklisted on all slots, that would waste
>>>> >> resources. Narrowband interference can harm the link locally, but the
>>>> >> same frequency may be interference-free in other parts of the net.
>>>> >>       The dynamic allocation I propose was only an example. If you
>>>> >> have 16 frequencies and 2 of them have interference, and the channel
>>>> >> offset is sequential, you may loose 2 packets every 16. Am I right on
>>>> >> this?
>>>> >>
>>>> >> Thoughts?
>>>> >>
>>>> >>                                                       Diego
>>>> >>
>>>> >>
>>>> >> 2013/9/13 Qin Wang <[e-mail]>:
>>>> >> > Thomas,
>>>> >> >
>>>> >> > I agree with you that it is not clear what is the advantage and
>>>> >> > disadvantage of adaptive channel hopping in reality.
>>>> >> >
>>>> >> > In mind, based on the per-frequency report, PCE can do two things:
>>>> >> > (1) update channel hopping sequence is a frequency is really bad
>>>> >> > network wide;
>>>> >> > (2) avoid use some bad channel when it runs cell allocation
>>>> algorithm.
>>>> >> > The
>>>> >> > two things happen in PCE, so, will not make negative impact on the
>>>> >> > network.
>>>> >> > Thought?
>>>> >> >
>>>> >> > Thanks
>>>> >> >
>>>> >> > Qin
>>>> >> >
>>>> >> >
>>>> >> >
>>>> >> >
>>>> >> > On Fri, Sep 13, 2013 at 10:46 PM, Thomas Watteyne
>>>> >> > <[e-mail]> wrote:
>>>> >> >>
>>>> >> >> Qin, Diego,
>>>> >> >>
>>>> >> >> My 2 cents. I agree with you that it would be nice for the PCE to
>>>> >> >> be able to get some per-channel information. Although adaptive
>>>> >> >> channel hopping (i.e.
>>>> >> >> selectively blacklisting frequencies for a specific bundle) is
>>>> >> >> appealing in principle, it's unclear (at least to me) whether the
>>>> >> >> gains clearly outweigh the overhead (complexity, signalign
>>>> >> >> traffic) one has to pay to coordinate this [1-5].
>>>> >> >>
>>>> >> >> My opinion is that we should enable both metrics averages over all
>>>> >> >> channels, and per-channel metrics. In some configurations, one can
>>>> >> >> imagine gathering the former by default, and querying for the
>>>> >> >> latter on specific occasions. Having the option of gathering
>>>> >> >> per-channel information does enable us to be future-proof against
>>>> >> >> future adaptive channel hopping algorithm.
>>>> >> >>
>>>> >> >> For sure, this makes for a great question: how do a pair of motes
>>>> >> >> and the PCE have to communicate to enable adaptive channel hopping
>>>> >> >> on that link? The answer to that might directly impact the
>>>> >> >> application payload formats we have are talking about. Is this
>>>> >> >> something you be interested in looking further into?
>>>> >> >>
>>>> >> >> Thomas
>>>> >> >>
>>>> >> >> [1] A Decentralized Scheduling Algorithm for Time Synchronized
>>>> >> >> Channel Hopping. Andrew Tinka, Thomas Watteyne, Kris Pister,
>>>> Alexandre M.
>>>> >> >> Bayen.
>>>> >> >> ICST Transactions on Mobile Communications and Applications,
>>>> 11(7-9).
>>>> >> >> European Union Digital Library link.
>>>> >> >> doi:10.4108/icst.trans.mca.2011.e5.
>>>> >> >> September 2011.
>>>> >> >> [2] A Decentralized Scheduling Algorithm for Time Synchronized
>>>> >> >> Channel Hopping. Andrew Tinka, Thomas Watteyne, Kris Pister.
>>>> >> >> International Conference on Ad Hoc Networks (ADHOCNETS), Victoria,
>>>> >> >> BC, Canada, 18-20 August 2010.
>>>> >> >> [3] Mitigating Multipath Fading Through Channel Hopping in
>>>> >> >> Wireless Sensor Networks. Thomas Watteyne, Steven Lanzisera, Ankur
>>>> >> >> Mehta, Kris Pister.
>>>> >> >> IEEE
>>>> >> >> International Conference on Communications (ICC), Cape Town, South
>>>> >> >> Africa,
>>>> >> >> 23-27 May, 2010.
>>>> >> >> [4] Feasibility Analysis of Controller Design for Adaptive Channel
>>>> >> >> Hopping. Branko Kerkez, Thomas Watteyne, Mario Magliocco, Steven
>>>> >> >> Glaser, Kris Pister. First International Workshop on Performance
>>>> >> >> Methodologies and Tools for Wireless Sensor Networks (WSNPerf),
>>>> >> >> Pisa, Italy, 23 October 2009.
>>>> >> >> [5] Reliability Through Frequency Diversity: Why Channel Hopping
>>>> >> >> Makes Sense. Thomas Watteyne, Ankur Mehta, Kris Pister. Sixth ACM
>>>> >> >> International Symposium on Performance Evaluation of Wireless Ad
>>>> >> >> Hoc, Sensor, and Ubiquitous Networks (PE-WASUN), Tenerife, Canary
>>>> >> >> Islands, Spain, 26-30 October 2009.
>>>> >> >>
>>>> >> >> On Fri, Sep 13, 2013 at 7:23 AM, Prof. Diego Dujovne
>>>> >> >> <[e-mail]> wrote:
>>>> >> >>>
>>>> >> >>> Hello Qin,
>>>> >> >>>               I think that a per-frequency report will help the
>>>> >> >>> PCE to decide which frequency to use, and maybe temporarily
>>>> >> >>> black-list them. For example, a dynamic scheme may include
>>>> >> >>> sampling the blacklisted frequencies every X minutes to re-enable
>>>> >> >>> them once the interference has disappeared.
>>>> >> >>>              This will require the node to refresh the RSSI and
>>>> >> >>> LQI values in a opportunistic way (every time the a cell uses
>>>> >> >>> that frequency) to save energy.
>>>> >> >>>
>>>> >> >>> Any thoughts?
>>>> >> >>>
>>>> >> >>>                             Diego
>>>> >> >>
>>>> >> >>
>>>> >> >> _______________________________________________
>>>> >> >> 6tsch mailing list
>>>> >> >> [e-mail]
>>>> >> >> https://www.ietf.org/mailman/listinfo/6tsch
>>>> >> >>
>>>> >> >
>>>> >> >
>>>> >> > _______________________________________________
>>>> >> > 6tsch mailing list
>>>> >> > [e-mail]
>>>> >> > https://www.ietf.org/mailman/listinfo/6tsch
>>>> >> >
>>>> >>
>>>> >>
>>>> >>
>>>> >> --
>>>> >> DIEGO DUJOVNE
>>>> >> Académico Escuela de Ingeniería en Informática y Telecomunicaciones
>>>> >> Facultad de Ingeniería UDP www.ingenieria.udp.cl
>>>> >> (56 2) 676 8125
>>>> >
>>>> >
>>>>
>>>>
>>>>
>>>> --
>>>> DIEGO DUJOVNE
>>>> Académico Escuela de Ingeniería en Informática y Telecomunicaciones
>>>> Facultad de Ingeniería UDP
>>>> www.ingenieria.udp.cl
>>>> (56 2) 676 8125
>>>> _______________________________________________
>>>> 6tsch mailing list
>>>> [e-mail]
>>>> https://www.ietf.org/mailman/listinfo/6tsch
>>>>
>>>
>>>
>>
>> _______________________________________________
>> 6tsch mailing list
>> [e-mail]
>> https://www.ietf.org/mailman/listinfo/6tsch
>>
>>
>