Subject: Re: [6tisch] OTF & chunks

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Fri, 21 Mar 2014 12:47:31 +0000

Hi Nicola

Hi Pascal, Qin, Tom,
I've got your points. I agree that chunks should not be sublet to children. This is not what I was meaning. Perhaps, a node should be given the possibility to create a new chunk (not overlapped with that shared with its parent) and communicate neighbor-to-neighbor the new chunk to its children. Chunks would color different interfering zones also in this case.

[PT] very cool... this is exactly what we want to do with chunks.

Chunks partition the slotframe matrix, and should be not overlapped. Overlapped chunks could happen, but a schuduling technique (out of scope of IETF) could be in charge of allowing such overlaps only for pair of nodes which are far and possibly not keen to interfering each other. Such partition can be made by the PCE, but also in a decentralized fashion.

[PT] yes

Some examples: TASA creates chunks in centralized fashion, DeTAS in a decentralized one. Here, I guess, we are abstracting from specific allocation algorithms. At the same time, IMHO, all possibilities should be accounted, am I right? Until now, chunks would work with centralized algorithm. My proposal is to extend chunks to be computed in a decentralized/distributed way, thus requiring specific IE to be exchanged neighbor-to-neighbor. How that computation is perfomed is out of scope, of course. But I believe it should be allowed in some way.

[PT] I can understand how the CUD matrix can be formatted and that formatting distributed, e.g. a regular expression. Distributing the format can be a harder task, I mean what happens in zones where the formattings overlap?

Cheers,

Pascal

2014-03-21 8:09 GMT+01:00 Pascal Thubert (pthubert) <[email-masked]<mailto:[email-masked]>>:
Hello Qin,

I think Tom was very clear and I fully share his views and concerns. Topologies and topographies are very different beasts, each one very difficult to learn and maintain. Let me detail my thoughts in complement to Tom's words.

As a Distance Vector protocol, RPL allows devices to ignore both to space control and memory space. This was a conscious design point. I do not see the motes growing all of a sudden to the capacity to know about both.

The computation in the system (or network) manager is opaque to the outside and I do not know what people did effectively. This being said, for all I know from the outside, the computation ignores other networks even within interference domain.So the simplifying assumption that I expect to find there is to assume a single interference domain for all and use a chunk only once.

With 6TiSCH, we synchronize multiple DODAGs connected to a same backbone, allowing devices to jump from one DODAG to the next. The expectation for a chunk is that around a device that allocates the chunk, a domain will form where that chunk will not be reused. But outside that domain, the chunk will be reused so we can grow the network to the 10s of thousands.

As a result, each given chunk will create a partition of the network, "coloring" zones around the non-interfering RPL parents that use it. That coloring is related to the topology in that the colored zone comprises a RPL parent and its children. It is also related to topography in that colored zones do not overlap.

We have to design the way this will happen and that will probably be very similar to what we call automated site survey, or Radio Resource Management, or in Cisco marketing parlance, clean air. We know it is doable for having done similar work before, and so we can assume that this WG will achieve that goal. But we must work to make it very simple and with a minimum amount of state in the devices.

All in all, I'm afraid that subletting chunks to children is actually a drift from IETF work to IRTF or academic research.

Cheers,

Pascal

From: Qin Wang [mailto:[email-masked]<mailto:[email-masked]>]
Sent: jeudi 20 mars 2014 22:10
To: Tom Phinney; Pascal Thubert (pthubert)
Cc: Nicola Accettura; [email-masked]<mailto:[email-masked]>
Subject: Re: [6tisch] OTF & chunks

Hi Tom,

I fully agree that the radio environment is time-varying.

But, according to my understanding, in the centralized approaches like ISA100.11a and wirelessHART,  network manager can make un-conflicting (or approximate un-conflicting) schedule for each node. I guess the scheduling process bases on the information about network topology(or topograpy). Similarly, PCE should be able to make this kind of un-conflicting schedule after it get the topograpy information. Of course, sometime later, the un-conflicting situation may change while the radio environment changes significantly. Do you agree?

Now, question is if we can think a parent as a local PCE if it has the topograpy information of its subnet. My feeling is positive, but not very sure. If the answer is yes, I think the scheduling algorithm run in central PCE should be able to run on the parent, but only operate the chunk owned by the parent, instead of whole cells in the matrix of [slotOffset, channelOffset] of a slotframe. Make sense?

Thanks
Qin

On Thursday, March 20, 2014 4:31 PM, Tom Phinney <[email-masked]<mailto:[email-masked]>> wrote:
Hi Qin,

Radio propagation and interference are not constant in time or space. Even for fixed-location motes the actual extent of interference changes with frequency, atmospheric conditions, movement of any metal or person within the volume of space near the sending or receiving antennae, etc. Then there is the "hidden station" problem. Knowledge of three-dimensional topography is not enough; one would need a site survey to determine, for a given configuration of interfering and reflecting elements, the useful propagation and destructive interference extents in 3-space of each transmitter, and similarly the path attenuation seen by each receiver relative to each of those senders.

Useful approximations of connectivity and interference can be acquired without such a site survey, but only between pairs of communicating nodes. The approximations degrade rapidly when one attempts to extend this pairwise-transitively to additional nodes. Thus the idea that a parent can determine the suitability of propagation and extent of interference for child-to/from-grandchild communication is questionable.

Note that I used the word "topography" since the "topology" of the connectivity graph is not affected by the kind of movement of nodes that would change interference relationships, so long as intentionally-communicating pairs remained in communication.

-Tom
====
On 2014.03.20 12:25, Qin Wang wrote:
Hi Pascal,

You are right. If the parent has no knowledge about its children, grand-children's and grand-grand-children's topology, the renting, re-renting, and... may result in collision area. But if, like DeTas case, every parent has the topology knowledge (almost same information as PCE has), I think the collision could be avoided. Right?

Thanks
Qin

On Friday, March 21, 2014 2:57 AM, Pascal Thubert (pthubert) <[email-masked]><mailto:[email-masked]> wrote:
The problem, Qin, is that a chunk is only owned inside an interference domain.

If a parent subrents a piece of chunk to a child and the child uses it for a grand child to child communication, the grand child frame might interfere too far...

Cheers,
Pascal

Le 20 mars 2014 à 19:15, "Qin Wang" <[email-masked]<mailto:[email-masked]>> a écrit :
Hi Nicola,

I can see your point. Based on what you suggest about chunk, I think we can extent chunk related function as follows.
(1) If a node receives a set of cells from PCE or its parent (a chunk), it can ask its children to delegate part of the chunk (sub-chunk) or the whole chunk.
(2) The negotiation to allocate softcells can base on a given slotframe or a part of the slotframe (i.e. a chunk). Actually, it can be achieved based on current version of 6top, by using chunkID to define candidate list (see the sublayer draft).

What do you think?

Thanks
Qin

On Friday, March 21, 2014 1:13 AM, Nicola Accettura <[email-masked]<mailto:[email-masked]>> wrote:
Hi Qin,
of course, my understanding is the same as yours. Actually, I would like to better feature what I meant.

Hard cells are allocated by exchanging 6top messages in the neighborhood, but the delivery of such messages is triggered by entities different from 6top. For instance, a PCE coordinating scheduling duties in centralized approaches. Decentralized or semi-centralized approaches would employ hard cells as well. The key role is played by a central manager which is intended to organize the cell allocation on each node in the network.

Soft cells, instead, could be used when a distributed approach is more fitting to the application scenario (e.g., when mobility should be accounted for). In this sense, OTF has been thought as a distributed solution that relies on 6top soft-cell allocation/reallocation/deletion.

Let's consider chunks. As far as I understood, they can be fruitfully exploited for avoiding collisions. A chunk is a subset of cells into the slotframe. If a node holds a chunk, it will be allowed to allocate cells in that subset. If the chunks related to each node in the network are well distributed or interleaved, each pair of nodes will allocate cells without interfering with other ones. For example, DeTAS (I presented some implementation at the plugfest) would benefit from chunks.

In the current state of the 6TOP sublayer draft, it seems that chunks cannot be computed dynamically on each node. I mean, only the PCE can do this work or they should be preconfigured. I think it would be better to extend the chunk properties, allowing the exchange of IE messages for setting up proper chunks on each node. It is like having two levels of allocation: nodes exchange messages in order to choose a subset (chunk) of the slotframe where they could then allocate cells (after another round of message exchange). Is that viable?

In addition, I think that chunks could be useful in both centralized and distributed approaches for mitigating collisions. OTF would benefit for sure from allowing soft cells to be reserved in a chunk more than in the whole slotframe. Although OTF is distributed, there is always a central entity which can tune properly the network behavior. It would be like RPL: it is distributed, but the LLN sink is in charge of constructing the network. What am I missing?

Thanks
Nicola

2014-03-20 16:01 GMT+01:00 Qin Wang <[email-masked]<mailto:[email-masked]>>:
Hi Nicola,

Let's go back one step to discuss the reason to introduce Chunk into 6top. My understanding is as follows.

6top supports centralized approach, i.e. PCE schedules hardcells for each node. 6top supports distributed approach, i.e. a pair of node allocate/reallocate some softcells by negotiation. Then, Chunk is a semi-centralized approach, i.e. a parent node is a local center, which delegate the PCE and manages a set of hardcell (i.e. Chunk), Comparing centralized approach, the Chunk approach will have advantage in terms of scalability and adaptability to dynamic radio environment, traffic load and other change in local.

Pascal, please point out if I'm wrong.

Thanks
Qin

On Thursday, March 20, 2014 6:57 PM, Nicola Accettura <[email-masked]<mailto:[email-masked]>> wrote:
Dear all,
the current version of the OTF draft speaks about the necessity of chunks as follows:

"OTF is prone to schedule collision.  Nodes might not be aware of the cells allocated by other pairs of neighbors nodes.  A collision occurs when the same cell is allocated by different pairs in the same interference space.  The 6top sublayer cannot differentiate collisions from other sources of packet loss.  The probability ofhaving allocation collision may be kept low by grouping cells into chunks (see [I-D.ietf-6tisch-terminology] and [I-D.ietf-6tisch-architecture] for more details).  The use of chunks is outside the scope of this current version of the OTF draft."

Actually, as featured in the 6TOP sublayer draft, chunks can be managed by a PCE or configured by upper layers:

"6top allows an upper layer to ask a node to manage a portion of a slotframe, called a chunk.  Chunks can be delegated explicitly by the PCE to a node, or claimed automatically by any node that participates to the distributed cell scheduling process.  The cells in a chunk can be appropriated by the node, i.e. the node is in charge of managing the chunk."
IMHO, to be useful in distributed and/or decentralized contexts chunks should be given the possibility to be negotiated within specific IE. What do you think about it?

In addition, the 6TOP sublayer draft allows only hard cells to be selected in a chunk. This is clearly not suitable for OTF, which is supposed to work only with soft cells. Am I missing something?

Cheers
Nicola

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

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

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

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

_______________________________________________

6tisch mailing list

[email-masked]<mailto:[email-masked]>

https://www.ietf.org/mailman/listinfo/6tisch

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