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

Qin Wang <qinwang@berkeley.edu> Mon, 16 September 2013 21:34 UTC

Return-Path: <qinwang@berkeley.edu>
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 A416611E8112 for <6tsch@ietfa.amsl.com>; Mon, 16 Sep 2013 14:34:09 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.505
X-Spam-Level:
X-Spam-Status: No, score=-2.505 tagged_above=-999 required=5 tests=[AWL=0.471, BAYES_00=-2.599, FM_FORGED_GMAIL=0.622, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_LOW=-1]
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 l5kDXvzSMux2 for <6tsch@ietfa.amsl.com>; Mon, 16 Sep 2013 14:34:05 -0700 (PDT)
Received: from mail-ie0-f170.google.com (mail-ie0-f170.google.com [209.85.223.170]) by ietfa.amsl.com (Postfix) with ESMTP id 4495211E81E9 for <6tsch@ietf.org>; Mon, 16 Sep 2013 14:34:05 -0700 (PDT)
Received: by mail-ie0-f170.google.com with SMTP id x13so8772382ief.15 for <6tsch@ietf.org>; Mon, 16 Sep 2013 14:34:03 -0700 (PDT)
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:in-reply-to:references:date :message-id:subject:from:to:cc:content-type; bh=oSg/8waazBC4Syy7EpDBPS+Yd/+qj5sssp/6YEtQ1fk=; b=G0E8vOeDvdhaoQYnBsTvsdVpClQ2o3//rBt7wCDtPZ4xuo8XqCQMhCeg1qhXyz7PN1 PcQsTbt/bGHqpPzL9qoWevzZhG1b4nh7t0hXVyD5q/32RNY1CTkfFr7w86BlefFLHKIN y99e2xcNNaQDPvAY/QgQdRWdNcupJ73Cq1ooq5VRdT74ibbdxBCNtx3/RWsH5Qx68dkW XrBzgeBf0KROruMGXayMnO2E46BDsx9RYhhYQZS4JJFvblXF0+wr2t+x0UutK2PcAnZp dT2LhWDbqVkD+g4ZCFdWplvxeuBfYx2SLaNoc/GWu8sCorNyk9G54yJpkopWeCRPSdvg OzPQ==
X-Gm-Message-State: ALoCoQmsmkvb/0vOjPFbsYeZweP2xdvRwWn54cDS+tp17efZxlvkibVtFSflzNAsBF3OHUxKrFuX
MIME-Version: 1.0
X-Received: by 10.43.152.78 with SMTP id kv14mr4694839icc.13.1379367243693; Mon, 16 Sep 2013 14:34:03 -0700 (PDT)
Received: by 10.64.139.234 with HTTP; Mon, 16 Sep 2013 14:34:03 -0700 (PDT)
In-Reply-To: <CADJ9OA-6T82049Ok1VV-VJTRsddR7So+uH7QyW=LjiWTkOhp9A@mail.gmail.com>
References: <CADJ9OA-6T82049Ok1VV-VJTRsddR7So+uH7QyW=LjiWTkOhp9A@mail.gmail.com>
Date: Tue, 17 Sep 2013 05:34:03 +0800
Message-ID: <CAAzoce5tX8qnw0kUCGV4KiVO6rMaV8Z2s8Xf+zsAdvVh4Y5rdw@mail.gmail.com>
From: Qin Wang <qinwang@berkeley.edu>
To: Thomas Watteyne <watteyne@eecs.berkeley.edu>
Content-Type: multipart/alternative; boundary=001a11c30a84934a0604e686f675
Cc: 6TSCH <6tsch@ietf.org>
Subject: Re: [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 21:34:09 -0000

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 <watteyne@eecs.berkeley.edu
> 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, <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
>>>
>>
>>
>
> _______________________________________________
> 6tsch mailing list
> 6tsch@ietf.org
> https://www.ietf.org/mailman/listinfo/6tsch
>
>