Subject: [6tisch] SF0 Cell Estimation Algorithm (draft-ietf-6tisch-6top-sf0-02)

From: Yasuyuki Tanaka <[email-masked]>
Date: Fri, 11 Nov 2016 18:20:28 +0100

Hi all,

I'd appreciate it if someone could help me understand SF0 Cell
Estimation Algorithm mentioned in draft-ietf-6tisch-6top-sf0-02...

https://tools.ietf.org/html/draft-ietf-6tisch-6top-sf0-02#section-5

What I've read from the draft is that the Cell Estimation Algorithm
tries to have at least as many TX cells to a neighbor as RX cells
which has been allocated for the neighbor as requested. It seems the
algorithm assumes the communication triggering SF0 is symmetric.

This idea explains why REQUIREDCELLS is given "by adding the current
number of effectively used cells and the new incoming cells
requirement." In the draft, cells requested to the allocation policy
by the cell estimation algorithm are always TX. The numbers of
SCHEDULEDCELLS and REQUIREDCELLS are only about TX cells.

Is it correct? If this is the case, I wonder where the assumption,
communication with a neighbor is symmetric, comes from.

Supposing communication is asymmetric, where a node which has
allocated RX cells for a neighbor rarely sends data to it, TX cell
allocation triggered by an incoming cell requirement could not only be
in vain but also cause unnecessary 6P transactions. With this
scenario, it seems better that the estimation algorithm does not to
take into account "incoming cell requirements."  I may overlook
something...

I have another thing to ask, but I'd like to clarify the above first.

Best,
Yatch

---

From: "Prof. Diego Dujovne" <[email-masked]>
Date: Fri, 11 Nov 2016 17:14:29 -0300

2016-11-11 17:14 GMT-03:00 Prof. Diego Dujovne <[email-masked]>:

> Yasuyuki,
>               -02 version does not take into account symmetry.
> In fact, we do not specify which type of cells (RX,TX) we
> are allocating, we only say that we need to allocate them as
> an introduction to the section.
>               We implicitly assume that we are allocating TX
> traffic (which is RX from the point of view of the neighbour).
> The opposite sense is correct: If the neighbour needs TX traffic,
> it is RX for the node.
>               We do not specify on the draft where (i.e. from which
> neighbour)
> the incoming traffic comes from. In fact, the incoming traffic can arrive
> from any neighbour. However, if we assume that we are using RPL, all the
> traffic from the child nodes is forwarded to the parent in the TX sense,
> while downstream traffic would be parent->node->slave.
>              IMHO, I believe you are right when you say that taking into
> account only the outgoing traffic is a good estimator on the number of
> required cells, since it includes not only the locally generated traffic
> but also the
> traffic from the neighbours traversing the node to that neighbour.
> Furthermore, it would be more accurate (and overprovisioning could be
> smaller)
> because we assume also that we are not using track nor flow identifiers to
> map incoming traffic from the other nodes to the neighbours.
>              I think the symmetry interpretation comes from
> the idea that we are measuring the incoming cell requests from
> a specific neighbour and then adding the outgoing number of cells
> to the same neighbour and calculate the total amount of required cells.
> But we still have to differentiate between TX and RX cells.
>             Hope this helps.
>             Let me know your thoughts about it.
>             Regards,
>
>                                         Diego Dujovne
>
>
>
>
>
>
> 2016-11-11 14:20 GMT-03:00 Yasuyuki Tanaka <[email-masked]
> >:
>
>> Hi all,
>>
>> _______________________________________________
>> 6tisch mailing list
>> [email-masked]
>> https://www.ietf.org/mailman/listinfo/6tisch
>>
>
>
>
> --
> DIEGO DUJOVNE
> Profesor Asociado
> Escuela de Informática y Telecomunicaciones
> Facultad de Ingeniería - Universidad Diego Portales - Chile
> www.ingenieria.udp.cl
> (56 2) 676 8125
>

-- 
DIEGO DUJOVNE
Profesor Asociado
Escuela de Informática y Telecomunicaciones
Facultad de Ingeniería - Universidad Diego Portales - Chile
www.ingenieria.udp.cl
(56 2) 676 8125

---

From: Yasuyuki Tanaka <[email-masked]>
Date: Sat, 12 Nov 2016 03:33:53 +0100

Hi Diego,
Thank you for your prompt reply! I appreciate it!!

I understand it better. Honestly, I'm still confused a little bit,
though...

diego> In fact, we do not specify which type of cells (RX,TX) we are
diego> allocating, we only say that we need to allocate them as an
diego> introduction to the section.

With regard to the type of cells which SF0 Allocation Policy handles,
I thought it was always TX by seeing the following descriptions.

    (from Section 6)
    SCHEDULEDCELLS:  The number of cells scheduled from the current node
       to a particular neighbor.
    REQUIREDCELLS:  The number of cells calculated by the Cell Estimation
       Algorithm from the current node to that neighbor.

I interpreted "cells ... from the current node to a particular (that)
neighbor" as TX cells from the point of view of "the current node", on
which the the allocation policy is working.

But, according to you, this interpretation is wrong; then it follows
that "from" and "to" merely represent the direction of a request for
allocation, don't they? In that case, I'm not sure who decides the
type of newly allocating cells and how it's done...

Anyway, if you assume TX cells are allocated as a result of the
algorithm, I'd suggest specifying that in the document, which is
easier to understand and implement.

diego> I think the symmetry interpretation comes from the idea that we
diego> are measuring the incoming cell requests from a specific
diego> neighbour and then adding the outgoing number of cells to the
diego> same neighbour and calculate the total amount of required
diego> cells.

You're right. I don't get it why REQUIREDCELLS is calculated with "the
new incoming cell requirements from the neighbor" unless the cell
estimation algorithm tries to have the same number of TX cells and RX
cells for a neighbor whose new cell requirements triggers the
algorithm.

...OK, thanks to your RPL example, now I realize a gap between the
draft and me. Although I couldn't see anything about RPL in the draft,
it's there; "outgoing" indicates traffic towards the RPL parent of a
node, and "incoming" indicates traffic from its RPL child nodes,
right?  Your RPL example may imply that the SF0 cell estimation
algorithm could output REQUIREDCELLS to send data to the parent, which
is not a node whose cell requirements triggers the algorithm.

As far as I understand, OTF does such a thing which is called chained
reaction or chained reservation. But, I don't think this is still
within the scope of SF0. SF0 has no idea who is the RPL parent node
nor who is a RPL child node.

Lastly, the following idea I sent before is not good even if
REQUIREDCELLS is the required number of TX cells to a particular
neighbor.

yatch> TX cell allocation triggered by an incoming cell requirement
yatch> could not only be in vain but also cause unnecessary 6P
yatch> transactions.

A new cell requirement (ignore the adjective of "incoming") may lead
decrease of TX cells, a node could receive DELETE request on a TX cell
from its neighbor, which is a RX cell from the point of view of the
neighbor. Therefore, it's helpful for this deallocation of the TX cell
to trigger the algorithm. Speaking of REQUIREDCELLS, I still believe
it's OK to set "the current number of effectively used cells" to it.

That's all! Have a nice weekend!!

Best,
Yatch

On 2016/11/11 21:14, Prof. Diego Dujovne wrote:
>
>
> 2016-11-11 17:14 GMT-03:00 Prof. Diego Dujovne <[email-masked] <mailto:[email-masked]>>:
>
>     Yasuyuki,
>                   We do not specify on the draft where (i.e. from which neighbour)
>     required cells, since it includes not only the locally generated traffic but also the
>     Furthermore, it would be more accurate (and overprovisioning could be smaller)
>     2016-11-11 14:20 GMT-03:00 Yasuyuki Tanaka <[email-masked] <mailto:[email-masked]>>:
>
>         Hi all,
>
>         https://tools.ietf.org/html/draft-ietf-6tisch-6top-sf0-02#section-5 <https://tools.ietf.org/html/draft-ietf-6tisch-6top-sf0-02#section-5>
>
>         [email-masked] <mailto:[email-masked]>
>         https://www.ietf.org/mailman/listinfo/6tisch <https://www.ietf.org/mailman/listinfo/6tisch>
>
>
>
>
>     --
>     DIEGO DUJOVNE
>     Profesor Asociado
>     www.ingenieria.udp.cl <http://www.ingenieria.udp.cl>
>     (56 2) 676 8125
>
>
>
>
> --
> DIEGO DUJOVNE
> Profesor Asociado
> www.ingenieria.udp.cl <http://www.ingenieria.udp.cl>
> (56 2) 676 8125
>
>