Hello Xavi

 

From: Xavier Vilajosana Guillen [mailto:xvilajosana@eecs.berkeley.edu]
Sent: samedi 23 novembre 2013 07:37
To: Qin Wang
Cc: Pascal Thubert (pthubert); Maria Rita PALATTELLA; 6tisch@ietf.org; Prof. Diego Dujovne
Subject: Re: [6tisch] time slot allocation

 

Hi, 

 

have some questions about chunk management vs not using chunks. As far as I understand a chunk is a block of the schedule that is allocated to a node by some management entity, the chunk is uniquely assigned to a node. Chunks can be of different sizes and the management of chunks is similar to the management of memory in linux systems (can be allocated/deallocated, have different sizes, etc..). A buddy algorithm can be used for that purpose, but requires communication.

 

[PT] Chunks can be reused in a different interference domain, and the formatting of slot-frame into chunks may be done by some management entity, but the allocation of a chunk to a node may be done though auto-configuration, just grabbing chunk-id that does not seem to be in use around. We could actually have heuristics for that such as forcing a parent that owns a chunk to use preferably some cells from that chunk so the use of those cells would be a signature of the bundle. Screening for energy in the air in those particular cells would indicate that the chunk is in use by a potential interferer and this node should peek a different chunk-id. We probably want to keep cells apart to limit the gap between cells, so buddy may not be the way, see below:

 

The questions are:

 

1)how do we plan to deal with fragmentation of the schedule? fragmentation can cause inefficiencies or even having nodes that are not able to allocate their desired bw because cells are taken by others.

[PT] A chunk is a lost of cells but it is not contiguous. In fact, we probably want the other way around, a list of well-distributed cells in time and frequency  within the schedule.

 

2)who will manage chunks and what messages are required (coordination?)

[PT] Chunks can be preprogrammed in a static schedule. We could have a simple rule to auto-compute them based on prime numbers.

Or chunks could be computed with the schedule by the PCE. The idea is that each cell would be tagged with the chunk-id.

 

3)what is the advantage of allocating a cell in a chunk vs allocating a cell in the whole schedule? Can we quantify it? In order to avoid collisions when allocating cells a node needs to know if there are others using the same cell and they are in the collision range, using chunks requires that other nodes in the neighborhood know that the particular chunk is being used (implies messaging), not using a chunk and allocating a cell directly to the schedule requires the same knowledge.

 

[PT] If there is a need to ask around whether a cell is being used before self can use a cell, then the chunk divides that overhead by the number of cells in a chunk.

 

I think that the concept of chunk might be useful but we need to understand very well the implications/requirements because a partition on the schedule is only a logical organization. I understand that some assumptions can be made but we have to make sure that this implicit knowledge is general enough so the mechanism is useful in most of the cases.

 

[PT] Agreed! Can we propose a simple auto-chunking of minimal schedule? Say we have 100 slots / 16 channels. Say we decide to autoformat 50 bundles of 32 cells. The first 2 time slots give you one cell per bundle, and then a +7 modulo 16 rotation in the channel every 2 slots give you automatically the other slots in that chunk. The first of every ten cells in a chunk must be used preferably so it can be screened as a signature of others to discover if that chunk is being used.

A node that find no energy on those signature cells and has no history that a neighbor claimed the associated chunk-id can claim it via a 2-3 hops flooding, and if no competition arises, decide to own the chunk, using preferably the signature slots.

 

What do you think?

 

my 5 cents :-)

X

 

On Fri, Nov 22, 2013 at 2:44 PM, Qin Wang <qinwang@berkeley.edu> wrote:

Pascal,

 

I'm not sure. The main difference between hard cell and soft cell is if 6top can reallocate it or not. My understanding is that chunk is created by PCE to ensure there is no conflict among the chunks owned by those parents who are in the same radio area. If a cell selected from such kind of chunk is re-allocated by 6top locally, the new cell may conflict with some cell in other chunk, unless the cell is only moved in the chunk. Right? Is it what you want?

 

Maybe, the "soft" here means the binding between a hard cell and its owner is soft, instead of that the binding between bandwidth and (slotOffset, channelOffset) is soft. What do you think?

 

Thanks

Qin

 

Thanks

Qin

 

On Sat, Nov 23, 2013 at 4:21 AM, Pascal Thubert (pthubert) <pthubert@cisco.com> wrote:

I certainly agree, Qin, but for the term hard cell.

 

I think the co-next cell inherits its properties form the root cell, and when used for RPL bundles links, I think that probably means soft.

What do you think?

 

Pascal

 

From: Qin Wang [mailto:qinwang@berkeley.edu]
Sent: vendredi 22 novembre 2013 19:35
To: Pascal Thubert (pthubert)
Cc: Prof. Diego Dujovne; Maria Rita PALATTELLA; 6tisch@ietf.org

Subject: Re: [6tisch] time slot allocation

 

Hi Pascal,

 

I think the concept of co-next can address my problem. 

 

I would like clarify what it means to 6top furthermore. I think it means besides Shared and Dedicated, there is a new cell type, i.e. Co-next cell. A Co-next cell is a Hard cell, belongs to a chunk of  a parent, and will be assigned by parent to its children statically or dynamically. There are many ways for a parent to assign a co-next cell to a child, e.g. pre-assignment (i.e. what Maria Rita and I discussed), "want-more" oriented assignment.

 

What do you think?

 

Thanks

Qin

 

On Fri, Nov 22, 2013 at 11:42 PM, Pascal Thubert (pthubert) <pthubert@cisco.com> wrote:

Hello Qin:

 

If the parent knows that the next cell in a bundle is not used (child did not set the more bit) then the parent may reaffect the particular cell to another child opportunistically.

This means that we introduce a ‘want-more’ bit in the frame from a child and the parent answers with the slot offset of the freecell.

 

Let’s chat at the call…

 

Pascal

 

From: 6tisch [mailto:6tisch-bounces@ietf.org] On Behalf Of Qin Wang
Sent: vendredi 22 novembre 2013 16:35
To: Prof. Diego Dujovne
Cc: Maria Rita PALATTELLA; 6tisch@ietf.org

Subject: Re: [6tisch] time slot allocation

 

Hi Deigo,

 

First of all, when we say "next cell", we refer to the next active cell in a bundle, instead of slotOffset+1.

 

Then, regarding to the motivation to have next_slot_used, I think it is because over-provision and dynamic traffic may happen. With next_slot_used indicator, we can save energy in those situations. Thought?

 

Thanks

Qin

 

On Fri, Nov 22, 2013 at 11:17 PM, Prof. Diego Dujovne <diego.dujovne@mail.udp.cl> wrote:

Maria Rita, Qin:

                      An active-cell list within a Bundle would require to maintain a shared
table between nodes, which can be less power-hungry than a relative jump to the next
cell. On the other side, a relative jump may limit the maximum number of cells inside
a Bundle, thinking about the longest jump between cells.

                      Another possibility may be a bare linked-list of cells within the

Bundle, using more bits, but with an absolute index number to identify the cell,

again limiting the Bundle size.

                      Altogether, the next-cell approach, although less efficient, may
keep things simple if cells are consecutive.

                     My question is, which is the purpose of jumping between cells

inside a Bundle?

                      Any thoughts?

                      Thank you,

                                                   Diego Dujovne

                     

                        

                    

 

 

2013/11/22 Maria Rita PALATTELLA <maria-rita.palattella@uni.lu>

Qin, I see your point about the next-slot-used and its number of bits.

Keeping in mind that each bundle can have a different size, what about using the next-slot-used bit for specifying only the active cells? Meaning that, following your example, if only cell-1 is used, by saying that cell 1 is used, we will implicitly say that all the others will not be used. If, instead, cell-1 and cell-3 are used, then we will specify cell-1 and cell-3 are active, instead of saying: cell-1 is active, cell-2 is not active, cell-3 is active, cell-4 is not active.

What do you think?

Maria Rita

 

 

From: Qin Wang [mailto:qinwang@berkeley.edu]
Sent: Friday, November 22, 2013 3:46 PM

To: Maria Rita PALATTELLA
Cc: 6tisch@ietf.org
Subject: Re: [6tisch] time slot allocation

 

Hi Maria Rita,

 

Regarding to 1), you are right, when a node use a specific cell within a chunck, a CREATE.hardcell will be triggered.

 

Regarding to 2), for example, assume there are 4 cells in a bundle, nodeA only wants to use cell-1 to send data to nodeB. If next_slot_used is only 1 bit, one possible approach is that nodeA sends data to nodeB on cell-1 and tell nodeB cell-2 will not be used, and sends data with empty payload on cell-3 and tells nodeB cell-4 will not be used; another possible approach is nodeA only sends data on cell-1, then nodeB can sleep on cell-2, but has to idle-listen on cell-3 and cell-4. No matter which approach, some energy will be wasted. With more than one bits next_slot_used, nodeB can sleep on cell-2, cell-3,and cell-4 based on the indicator obtained on cell-1. Right? However, as you said, many bits of next_slot_used may bring redundant and waste bandwidth. Thus, I think 2 or 3 bits may be a value of trade-off. What do you think?

 

Thanks

Qin

  

 

On Fri, Nov 22, 2013 at 7:07 PM, Maria Rita PALATTELLA <maria-rita.palattella@uni.lu> wrote:

Hello Qin,

 

Thanks for your comments.

 

1)      About 6top <-> chunk commands,  the CREATE.chunk command should be invoked by a PCE, and  involve a given node (the one receiving the set of cells to be used with any neighbor).  But then, when the node will use a specific cell within the chunk  with a specific neighbor, shouldn’t a CREATE.hardcell be  triggered?  About the DELETE.chunk command, as you are suggesting, it should trigger a set of DELETE.hardcell.

 

2)      About Next-Slot-Used, yes, it should be associated to a Bundle. IMHO, it doesn’t make sense to add more than 1 bit for indicating that the next N slots will not be used. With  the next-slot-used 1 bit,  you will know, step by step, if the next one is used or not. I think the other bits indicating the not-used N slots will bring redundant information.  What do you think?

 

Maria Rita

 

 

From: Qin Wang [mailto:qinwang@berkeley.edu]
Sent: Wednesday, November 20, 2013 4:07 PM
To: Maria Rita PALATTELLA
Cc: 6tisch@ietf.org
Subject: Re: [6tisch] time slot allocation

 

Hi Maria Rita,

 

Thanks you for your summary.

 

Regarding to item 2), I think new 6top commands are needed to support Chunk operations. It is easy to CREATE a chunk, because it is invoked by PCE and will not affect neighbors. But, it may not be that easy to DELETE a chunk after it has been used, because it will affect neighbors and trigger some DELETE.hardcell operations. Right?

 

Regarding to item 3), my understanding is the Next-Slot-Used will be carried in data packet to indicate next slot will be used or not, so as receiver will know if it should listen to or not in the next slot. If it is the case, the Next-Slot-Used indicator should be associated with Bundle, instead of Chunk, right? In addition, does it make sense to add more than one bit to indicate next N slots will not be used? For example, adding 2bits to indicate next 0-3 slots will not be used.

 

What do you think?

 

Qin

 

 

 

 

 

On Wed, Nov 20, 2013 at 6:02 PM, Maria Rita PALATTELLA <maria-rita.palattella@uni.lu> wrote:

Dear all,

 

Let’s keep our interesting discussion on the time slot allocation alive.

 

I will try to sum up our last ideas, mainly the open issues on which we still need to discuss:

 

·        1) Different Approaches for allocating a time slot within the schedule

·        centralized (PCE-like): not-scalable

·         fully distributed (e.g., OTF): risk of collision – need of monitoring the cells usage and the collision occurrence (using 6top?)

·         hybrid (semi-distributed, parent-based allocation) : more-scalable, based on bulk allocation and redistribution

Each approach has pros and cons, and it can be suitable in different scenarios/applications.

For each of them we need to specify HOW to allocate cells, or group of cells with the same neighbor (bundle) or with different neighbors (chunk).

Centralized solutions will mainly use HARD cells, while distributed or hybrid algorithms  are more lucky to use soft cells.

 

·        2) CHUNK – a new concept different from bundle!

·        It could be useful to allocate for a given node a chunk, i.e., a collection of cells in the schedule that can be used by that node to talk to any other neighbor, when needed.

·        Note that a chunk is different from a bundle. As defined in the 6tisch-terminology-draft:

·        Bundle: A group of equivalent scheduled cells, i.e., cells identified by different [slotOffset, channelOffset], which are scheduled for a same purpose, with the same neighbor, with the same flags, and the same slotframe.   The size of the bundle refers to the number of cells it  contains.  Given the length of the slotframe, the size of  the bundle translates directly into bandwidth, either logical, or physical.

·        Q1: How to select the specific cells in a chunk? Or the number of cells in a chunk?

·        Q2: How 6top can support the chunk allocation? New commands/functionalities should be added

 

3) Next-Slot-Used indication

When a group of cells (chunk) is reserved for a given node, a single bit could be used for indicating that the next time slot is actually needed and thus, used by that nod.

Q: how 6top should deal with this?

 

4) Multiply allocated time slots

When a chunk is reserved for a given node, it does not mean that it will use all the cells. Thus, the same time slots could be allocated to different nodes. If several nodes will need the same cell at the same time, a collision could occur.

Q: How can we multiply allocated time slots, while avoiding collision?

Maybe allocating them to nodes that will not interfere, because they are far away, one from the other.

 

·        5) Take into account the ETSI recommendations (e.g., ETSI restrictions on percentage of channel usage), and the ISA100.11a specification, when building the scheduling. (this point was raised up by Don Sturek at IETF88)

 

 

Please, do not hesitate to jump into the discussion and add anything else that is missing.

Thnak you!

Maria Rita

 

 

 

_______________________________________________
6tisch mailing list
6tisch@ietf.org
https://www.ietf.org/mailman/listinfo/6tisch" target="_blank" rel="nofollow">https://www.ietf.org/mailman/listinfo/6tisch

 

 

_______________________________________________
6tisch mailing list
6tisch@ietf.org
https://www.ietf.org/mailman/listinfo/6tisch" target="_blank" rel="nofollow">https://www.ietf.org/mailman/listinfo/6tisch

--
DIEGO DUJOVNE
Académico Escuela de Ingeniería en Informática y Telecomunicaciones
Facultad de Ingeniería UDP
http://www.ingenieria.udp.cl" target="_blank" rel="nofollow">www.ingenieria.udp.cl
(56 2) 676 8125

 

 

 

_______________________________________________
6tisch mailing list
6tisch@ietf.org
https://www.ietf.org/mailman/listinfo/6tisch" target="_blank" rel="nofollow">https://www.ietf.org/mailman/listinfo/6tisch

 

_______________________________________________
6tisch mailing list
6tisch@ietf.org
https://www.ietf.org/mailman/listinfo/6tisch" rel="nofollow">https://www.ietf.org/mailman/listinfo/6tisch