[6tisch] Questions on TSCH CSMA-CA retransmission algorithm in IEEE 802.15.4-2015

[Tero Kivinen <[e-mail]>]

Yasuyuki Tanaka writes:
> Could anyone help me understand correctly the TSCH CSMA-CA
> retransmission algorithm described in Section 6.2.5.3 of IEEE
> 802.15.4-2015, starting from page-64?

During the 2015 revision process we used quite a lot trying to make
that figure and text correct... And it is quite possible we did not
manage to do it... 

> I have some questions...:
> 
> ---
> 
> [1] What does it mean exactly by "the backoff window"?
> 
> There is no "backoff window" found in Figure 6-6 nor in the latter
> part of Section 6.2.5.3...
> 
> I think that "the backoff window"indicates BE (Backoff Exponent), but
> it's unclear...

Backoff window is not very clearly defined in the standard, and as
commented in other emails it is expressed as number of shared links up
to 2^BE-1. It cannot be expressed as time or backup period (as is done
in 6.2.5.1 for regular CSMA-CA) as there is no fixed time for it. How
long this will be depends on the schedule. I.e. if you have only one
shared link in your schedule this is twice as long as what it is if
you have two shared links.

Perhaps we should add some text in standard to explain it better. 


> [2] Should we reset BE every time retransmission process starts?
>
> Two conditions to reset the backoff window (BE?) are mentioned in page-64:
> 
> - "A successful transmission in a shared link resets the backoff window
>   to the minimum value."
> 
> - "The backoff window is reset to the minimum value if the
>   transmission in a dedicated link is successful and the transmit
>   queue is then empty."
> 
> In page-65, I see another condition if the backoff windows and BE are
> the same thing:
> 
> - "A device upon encountering a transmission failure in a shared link
>   shall initialize the BE to macMinBe."
> 
> It seems the former conditions and the latter condition conflict each
> other.

As commented already the text in page 65 consider the case where we
are doing initial transmission, not retransmission. This text is
actually unneeded, as the Figure 6-6 already does the resetting of the
BE on each retransmission.

> I'm not sure, after all the retransmissions for the last frame in
> shared links failed, the next retransmission process should reset BE or
> not. What about the case when the transmission for the last frame in a
> dedicated link was successful but the transmission queue was NOT
> empty?

Figure 6-6 do reset BE every time.

> [3] Errors in Figure 6-6
> 
> I don't think Figure 6-6 is correct...
> 
> - In the frist transmission attempt (the right-most branch):

This part should not be here at all. This is Retransmission backoff
algorithm, which is only done when doing retranmission, not the
initial transmission.

This is copy of the TSCH part of the Figure 6-5 left side, except it
is is missing the NB = 0 part.

If you read section 6.2.5.2 it says:

	As illustrated in Figure 6-5, when a TSCH device has a packet
	to transmit, it shall wait for a link to the destination
	device.

So the idea is that Figure 6-5 tells how you do CSMA-CA on initial
transmission. It does not include the transmission part of the waiting
for the ack. This also includes how to do initial CSMA-CA for TSCH.
The end result of Figure 6-5 is explained in page 62:

	Figure 6-5 illustrates the steps of the CSMA-CA algorithm. If
	the algorithm ends in “Success,” the MAC is allowed to begin
	transmission of the frame. Otherwise, the algorithm terminates
	with a channel access failure.

So after that figure 6-5 you know the channel is clear and you can
send, then you transmit the frame and wait for Ack. If you do not
receive Ack, and you are using TSCH you go to the section 6.2.5.3 and
start working on the retransmission algorithm. So you should never
really come to the figure 6-6 with frame that is not retransmission,
so the first question "Retransmission" will always return Y...

>   o Boxes of "transmit frame" and "transmission acknowledged?" are
>     missing after "N" to "TschCca=On?"

This is because it was copied from the CSMA-CA parts of the figure
6-5, and that did not include actual transmission, only to find out if
channel is clear for sending. So ignore that right side of the figure
6-6, and use left side of 6-5 for initial transmission...

The 6.2.5.3 says that Figure 6-6 is only used for retransmission:

	To reduce the probability of repeated collisions when the
	packets are retransmitted, the retransmission backoff
	algorithm shown in Figure 6-6 shall be implemented for shared
	links.

>   o It says transmission fails when NB exceeds macMaxFrameRetries; but
>     I think, it would enter the retransmission process instead of
>     "Failure". Which is correct?

No. This is identical than what Figure 6-5 does and this is indeed
correct. I.e., if we fail CCA on the channel we do consider it as a
failure to transmit when using TSCH. As we do not do backoffs in TSCH
and the next retransmission is going to be on the other channel we do
not wait a while and try to do CCA again like we do for Figure 6-5
middle and right parts. In those cases we do CCA for
macMaxCsmaBackoffs times, but with TSCH this is not feasible, so if
CCA fails, we just assume the sending of the frame failed, increment
NB (which has slightly different meaning than in 6-5 here) and try
again.

Note, that in Figure 6-5 the NB is defined as "NB is the number of
times the CSMA-CA algorithm was required to back off while attempting
the current transmission; this value shall be initialized to zero
before each new transmission attempt." In Figure 6-6 the NB also
includes actual failed retransmissions.

> - In the retransmission process without PCA (the middle branch):
> 
>   o "NB" is not initialized; should "NB=0" be there along with
>     "BE=macMinBe"?

NB was initialized in the Figure 6-5 when we did initial transmission,
and if there was any CCA failures there which caused us to increment
NB, they carry on to Figure 6-6.

>   o BE should be updated by "BE=min(BE+1, macMaxBe)" instead of
>     "BE=min(BE-1,macMinBe)", shouldn't it?

I do remember that we did have multiple versions of this figure with
different formulas there, and all of them were very confusing...

Hmm... it seems we did have sponsor ballot comment i-9 from Pat Kinney
which included part saying:

	8. In box 'NB = NB +1, BE = min(BE-1, macMinBe) change 'BE =
	min(BE-1, macMinBe)' to 'BE = min(BE+1, macMaxBe)' to
	correspond with page 31 text.

And that comment was accepted, but then it was not implemented in the
actual document. So I think you are right that the BE=min(BE+1,
macMaxBe) is right.

> I didn't look closer the left-most branch (retransmission with PCA),
> by the way.

Nobody looks closely on the PCA branch :-)
-- 
[e-mail]