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

Thomas Watteyne <watteyne@eecs.berkeley.edu> Mon, 16 September 2013 18:17 UTC

Return-Path: <twatteyne@gmail.com>
X-Original-To: 6tsch@ietfa.amsl.com
Delivered-To: 6tsch@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id C863311E8139 for <6tsch@ietfa.amsl.com>; Mon, 16 Sep 2013 11:17:07 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.461
X-Spam-Level:
X-Spam-Status: No, score=-1.461 tagged_above=-999 required=5 tests=[AWL=0.516, BAYES_00=-2.599, FM_FORGED_GMAIL=0.622, HTML_MESSAGE=0.001, NO_RELAYS=-0.001]
Received: from mail.ietf.org ([12.22.58.30]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id QMkOXjEIN-6D for <6tsch@ietfa.amsl.com>; Mon, 16 Sep 2013 11:17:05 -0700 (PDT)
Received: from mail-pb0-x232.google.com (mail-pb0-x232.google.com [IPv6:2607:f8b0:400e:c01::232]) by ietfa.amsl.com (Postfix) with ESMTP id D3BD111E810D for <6tsch@ietf.org>; Mon, 16 Sep 2013 11:17:05 -0700 (PDT)
Received: by mail-pb0-f50.google.com with SMTP id uo5so4369376pbc.23 for <6tsch@ietf.org>; Mon, 16 Sep 2013 11:17:00 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:sender:from:date:message-id:subject:to:content-type; bh=37FogDLZh6TuUxAK9C2Ue7SKxLOkgy8h2H3XwnnlWts=; b=FYdbj/5EoJ/MnXmIvPEv8tV+RkBomzMZTR8VPuA2J0k/3RBH/ILwYc6slqW1lGNvGl hWZ3gWwYwCs56c0moUxew3xvvRa+ue68OACdk6FFbnpKKk5fXihmSu3VExZvR4XJ6PDn fyxFig/lHqfWGl7FyuFHyP5TdMYDoRzFYQKKb77NYVFJ2UCCnOqtjtqiAIHBisROEV/S PzfNg0x6FhfEDcMJomfAQhxpHtliTwzN2kRAMZ8gJVrg2PgbHtoeeeZcidky+oVrJEN+ NhI5vakh6BV+lzgFpDGtGRfBRcgpylqKWs9vj2gEOqIb0ZEddpRUmWlwkGMgS6N7rsB1 EwvA==
X-Received: by 10.68.4.197 with SMTP id m5mr30397360pbm.46.1379355420516; Mon, 16 Sep 2013 11:17:00 -0700 (PDT)
MIME-Version: 1.0
Sender: twatteyne@gmail.com
Received: by 10.66.147.193 with HTTP; Mon, 16 Sep 2013 11:16:38 -0700 (PDT)
From: Thomas Watteyne <watteyne@eecs.berkeley.edu>
Date: Mon, 16 Sep 2013 11:16:38 -0700
X-Google-Sender-Auth: 0rPKXM-2i9R5c-sgPIFVEhl3Zac
Message-ID: <CADJ9OA-6T82049Ok1VV-VJTRsddR7So+uH7QyW=LjiWTkOhp9A@mail.gmail.com>
To: 6TSCH <6tsch@ietf.org>
Content-Type: multipart/alternative; boundary=bcaec52154e1dbe86504e6843513
Subject: [6tsch] blacklisting (was "report flow contents")
X-BeenThere: 6tsch@ietf.org
X-Mailman-Version: 2.1.12
Precedence: list
List-Id: "Discuss link layer model for Deterministic IPv6 over the TSCH mode of IEEE 802.15.4e, and impacts on RPL and 6LoWPAN such as resource allocation" <6tsch.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/6tsch>, <mailto:6tsch-request@ietf.org?subject=unsubscribe>
List-Archive: <http://www.ietf.org/mail-archive/web/6tsch>
List-Post: <mailto:6tsch@ietf.org>
List-Help: <mailto:6tsch-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/6tsch>, <mailto:6tsch-request@ietf.org?subject=subscribe>
X-List-Received-Date: Mon, 16 Sep 2013 18:17:07 -0000

*[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, <P.Zand@utwente.nl> 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" <qinwang@berkeley.edu> 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, <P.Zand@utwente.nl> 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: 6tsch-bounces@ietf.org [mailto:6tsch-bounces@ietf.org] 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 <qinwang@berkeley.edu>du>:
>> > 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
>> > <diego.dujovne@mail.udp.cl> 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 <qinwang@berkeley.edu>du>:
>> >> > 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
>> >> > <watteyne@eecs.berkeley.edu> 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
>> >> >> <diego.dujovne@mail.udp.cl> 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
>> >> >> 6tsch@ietf.org
>> >> >> https://www.ietf.org/mailman/listinfo/6tsch
>> >> >>
>> >> >
>> >> >
>> >> > _______________________________________________
>> >> > 6tsch mailing list
>> >> > 6tsch@ietf.org
>> >> > 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
>> 6tsch@ietf.org
>> https://www.ietf.org/mailman/listinfo/6tsch
>>
>
>