Subject: [lp-wan] Ambiguity problem in Packet mode: possible solutions

From: "Carles Gomez Montenegro" <[email-masked]>
Date: Wed, 17 May 2017 10:29:52 +0200

Hi LPWANners,

Yet another item for discussion: ambiguity in Packet mode and possible
solutions.

The problem
***********

Use of a CFN in Packet mode involves a possible issue when some fragments
are lost and need to be resent. In the example below, three fragments are
lost and are resent. However, the fact that two different fragments with
the same CFN are resent may lead to ambiguity.

          Sender               Receiver
             |-------CFN=6-------->|
             |-------CFN=5-------->|
             |-------CFN=4---X---->|
             |-------CFN=3-------->|
             |-------CFN=2---X---->|
             |-------CFN=1-------->|
             |-------CFN=0-------->|
             |-------CFN=6-------->|
             |-------CFN=5-------->|
             |-------CFN=4---X---->|
             |-------CFN=7-------->|MIC checked
             |<-------ACK----------|bitmap:1101011110100001
  retry A    |-------CFN=4-------->|
  retry B    |-------CFN=2-------->|
  retry C    |-------CFN=4-------->|MIC checked =>
             |<-------ACK----------|no bitmap
           (End)

- If retries B and C are unsuccessful, the receiver will only get one
  fragment with CFN=4 (retry A).

- If retries A and B are unsuccessful, the receiver will only get one
  fragment with CFN=4 (retry C).

Then: how can the receiver tell in any of the two situations above which
one of the two fragments with CFN=4 has been received?

Solutions
*********

1.- AFN for retries
*******************

One attempt to solve this is in -03: there is a format for first
transmission attempts (which uses the CFN) and a format for
retransmissions (which uses the Absolute Fragment Number, AFN). This would
avoid ambiguity, but in the interim some concerns were expressed. Since
the fragmentation header for retries will be larger than the one for first
attempts, data in the first transmission attempt cannot fill the whole L2
MTU, so that data in a retry still fits the L2 MTU. In addition, in some
technologies, the whole MTU needs to be filled.

2.- AFN always
**************

A solution is to use the AFN for both first transmission attempts and
retries (or, equivalently, a CFN field with a large enough size). This
would avoid ambiguity. However, the fragmentation header size will be
larger than with the usually short CFN (e.g. adding 1 byte to the header).
When the underlying LPWAN technology supports ~10 bytes of L2 MTU, this
approach may increase the number of fragments needed to carry a large IPv6
packet by ~10%.

3.- Fragment renumbering
************************

This mechanism renumbers the CFN of lost fragments (and thus avoids
increasing fragmentation header size) by numbering retransmitted fragments
as if they were a new sequence of fragments, e.g.:

          Sender               Receiver
             |-------CFN=6-------->|
             |-------CFN=5-------->|
             |-------CFN=4---X---->|
             |-------CFN=3-------->|
             |-------CFN=2---X---->|
             |-------CFN=1-------->|
             |-------CFN=0-------->|
             |-------CFN=6-------->|
             |-------CFN=5-------->|
             |-------CFN=4---X---->|
             |-------CFN=7-------->|MIC checked
             |<-------ACK----------|bitmap:1101011110100001
  retry A    |-------CFN=6-------->|
  retry B    |-------CFN=5-------->|
  retry C    |-------CFN=4-------->|MIC checked =>
             |<-------ACK----------|no bitmap
           (End)

There is still some non-zero probability of ambiguity with this approach.
However, such probability would be low. Ambiguity will happen if at least
2^N-1  consecutive retransmitted fragments are lost. This can also happen
for first transmission attempts, and N should be set to a large enough
value. (Note that in this case, the receiver can still tell after the MIC
check that the packet has not been correctly received, even if it cannot
tell what has been lost.)

We currently recommend N >= 3 for Packet (and Window) mode. We may "steal"
one more bit from the Rule ID space (now N=4) and ambiguity may only
happen if the packet sent requires at least 16 fragments to be carried,
there are at least 15 lost fragments (for the first round of
transmissions) and then at least 15 consecutive losses from retransmitted
fragments. Furthermore, typical error burstiness in wireless links may be
less severe in LPWAN, considering that time between two consecutive
transmissions may be large (due to message rate limitations), thus long
fragment loss bursts should be less likely here.

4. Fountain code
****************

Another solution suggested in the interim was using a fountain code and a
short-sized ACK that just tells how many fragments have been missed. The
CFN would be used (no need for an AFN).

However, the sender may need to send an excess of E encoded "fragments"
(in addition to the actual number of fragments) to allow the receiver
recover the complete packet with high probability [1]. The exact amount of
overhead may depend on the specific fountain code used and could also be
configurable.

How would the overhead of this solution compare with that of the other
solutions above?

-----

What does the WG think about these 4 possible options? Any preference?
Anything in particular to avoid?

(I would like to have WG feedback before addressing this in -04...)

Thanks!

Carles

[1]
https://docs.switzernet.com/people/emin-gabrielyan/060112-capillary-references/ref/MacKay05.pdf