Subject: Re: [lp-wan] ACK compression

From: Olivier Gimenez <[email-masked]>
Date: Mon, 19 Aug 2019 07:56:14 +0000

Dear,

It has not been a lot of discussion on that topic, here is my proposition. My changes are underlined and in italic (3rd bullet of first paragraph, added 3 figures)

Please see my first email, quoted at the end of my email for the context.

Best regards
Olivier

8.3.2.1.  Bitmap Compression

   For transmission, the Compressed Bitmap in the SCHC ACK message is
   defined by the following algorithm (see Figure 16 for a follow-along
   example):

*         Build a temporary SCHC ACK message that contains the Header followed by the original Bitmap (see Section 8.2.2.3 for a description of Bitmaps).

*         Position scissors at the end of the Bitmap, after its last bit.

*         While the bit on the left of the scissors is the same than the last SCHC bit and belongs to the Bitmap, keep moving left, then stop.  When this is done,

*         While the scissors are not on an L2 Word boundary of the SCHC ACK  message and there is a Bitmap bit on the right of the scissors,  keep moving right, then stop.

*         At this point, cut and drop off any bits to the right of the scissors

   When one or more bits have effectively been dropped off as a result
   of the above algorithm, the SCHC ACK message is a multiple of L2
   Words, no padding bits will be appended.

Because the SCHC Fragment sender knows the size of the original
   Bitmap, it can reconstruct the original Bitmap from the Compressed
   Bitmap received in the SCH ACK message.

   Figure 16 shows an example where L2 Words are actually bytes and
   where the original Bitmap contains 17 bits, the last 15 of which are
   all set to 1.

   |---- SCHC ACK Header ----|--------      Bitmap     --------|
             |-- T --|-M-| 1 |
   +--- ... -+- ... -+---+---+---------------------------------+
   | Rule ID |  DTag | W |C=0|1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1|
   +--- ... -+- ... -+---+---+---------------------------------+
           next L2 Word boundary ->|

            Figure 16: SCHC ACK Header plus uncompressed Bitmap - Trailing 1 compression

   Figure 17 shows that the last 14 bits are not sent.

   |---- SCHC ACK Header ----|CpBmp|
             |-- T --|-M-| 1 |
   +--- ... -+- ... -+---+---+-----+
   | Rule ID |  DTag | W |C=0|1 0 1|
   +--- ... -+- ... -+---+---+-----+
           next L2 Word boundary ->|

       Figure 17: Resulting SCHC ACK message with Compressed Bitmap - Trailing 1 compression

   Figure 18 shows an example of a SCHC ACK with tile indices ranging
   from 6 down to 0, where the Bitmap indicates that the second and the
   fourth tile of the window have not been correctly received.

   |---- SCHC ACK Header ----|--- Bitmap --|
             |-- T --|-M-| 1 |6 5 4 3 2 1 0| (tile #)
   +---------+-------+---+---+-------------+
   | Rule ID |  DTag | W |C=0|1 0 1 0 1 1 1|      uncompressed Bitmap
   +---------+-------+---+---+-------------+
       next L2 Word boundary ->|<-- L2 Word -->|

   +---------+-------+---+---+-------------+~~~+
   | Rule ID |  DTag | W |C=0|1 0 1 0 1 1 1|Pad|  transmitted SCHC ACK
   +---------+-------+---+---+-------------+~~~+
       next L2 Word boundary ->|<-- L2 Word -->|

          Figure 18: Example of a SCHC ACK message, missing tiles

   Figure 19 shows an example of a SCHC ACK with FCN ranging from 6 down
   to 0, where integrity check has not been performed or has failed and
   the Bitmap indicates that there is no missing tile in that window.

   |---- SCHC ACK Header ----|--- Bitmap --|
             |-- T --|-M-| 1 |6 5 4 3 2 1 0| (tile #)
   +---------+-------+---+---+-------------+
   | Rule ID |  DTag | W |C=0|1 1 1 1 1 1 1|  with uncompressed Bitmap
   +---------+-------+---+---+-------------+
       next L2 Word boundary ->|

   +--- ... -+- ... -+---+---+-+
   | Rule ID |  DTag | W |C=0|1|                  transmitted SCHC ACK
   +--- ... -+- ... -+---+---+-+
       next L2 Word boundary ->|

         Figure 19: Example of a SCHC ACK message, no missing tile

   Figure 20 shows an example where L2 Words are actually bytes and where the original Bitmap contains 17 bits, the last 6 of which are all set to 0 due to missing tiles.

   |---- SCHC ACK Header ----|--------      Bitmap     --------|
             |-- T --|-M-| 1 |
   +--- ... -+- ... -+---+---+---------------------------------+
   | Rule ID |  DTag | W |C=0|1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0|
   +--- ... -+- ... -+---+---+---------------------------------+
           next L2 Word boundary ->|

            Figure 20: SCHC ACK Header plus uncompressed Bitmap - Trailing 0 compression

   Figure 21 shows that the last 6 bits are not sent.

   |---- SCHC ACK Header ----|CpBmp|
             |-- T --|-M-| 1 |
   +--- ... -+- ... -+---+---+-----+
   | Rule ID |  DTag | W |C=0|1 1 1 1 1 1 1 1 1 1 1 1 |
   +--- ... -+- ... -+---+---+-----+
           next L2 Word boundary ->|

       Figure 21: Resulting SCHC ACK message with Compressed Bitmap - Trailing 0 compression

From: Olivier Gimenez
Sent: 07 May 2019 18:15
To: [email-masked]
Subject: ACK compression

Dear,

In the discussion following the draft-ietf-lpwan-schc-over-lorawan v04 with Dominique Barthel we are wondering if an improvement can be made:
In the LoRaWAN profile, from device to SCHC gateway, we tried to minimise the number of windows in order to minimise the number of required downlinks. This has a side effect:  bitmap can be up to 16 bytes.

Let's assume that the profile does not allow to put the last tile in the all-1 message.
Fragment 1:   | ruleId=b'000000 | Dtag=b'0 | W= b'00 | FCN=126 | 4 tiles |               => Receiver's bitmap b'1111 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000
Fragment 2:   | ruleId=b'000000 | Dtag=b'0 | W= b'00 | FCN=122 | 4 tiles |               => Lost, receiver's bitmap stays unchanged
Fragment 3:   | ruleId=b'000000 | Dtag=b'0 | W= b'00 | FCN=118 | 4 tiles |               => Received, receiver's bitmap becomes b'1111 0000 1111 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000
Fragment 4:   | ruleId=b'000000 | Dtag=b'0 | W= b'00 | FCN=114 | 4 tiles |                  => Lost, receiver's bitmap stays unchanged
Fragment 5 - All 1:   | ruleId=b'000000 | Dtag=b'0 | W= b'00 | FCN=127 | MIC |         => Received, MIC is wrong, receiver returns ACK
ACK :                | ruleId=b'000000 | Dtag=b'0 | W= b'00 | C=0 | bitmap = b'1111 0000 1111 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 | => Compression will not reduce the bitmap size in this case

What we are thinking is to allow compression of trailing bits also for 0 with the same rule than 1, which will result in the ACK:
Compressed ACK :                | ruleId=b'000000 | Dtag=b'0 | W= b'00 | C=0 | bitmap = b'1111 0000 1111 00

The sender knows how many tiles have been send, so it can resend tiles 122->119 and 114>111. What are your thoughts ?

Thank you

Best regards
Olivier

To view our privacy policy, including the types of personal information we collect, process and share, and the rights and options you have in this respect, see www.semtech.com/legal.

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Mon, 19 Aug 2019 08:12:34 +0000

Hello Olivier:

The drawings do not align well and the number of bits do not correspond so I cannot read your examples properly.
All I can say is that in order to work, you need the last bit of the compressed form to be the same as the elided bits.
So your "While the scissors are not on an L2 Word" in step 4 will not give the appropriate result if the scissor is already on the word boundary. In that case you need to go to the next boundary.
I suggest a step 3.5 which is to move the scissors right after the first while series.

All the best,

Pascal

From: lp-wan <[email-masked]> On Behalf Of Olivier Gimenez
Sent: lundi 19 août 2019 09:56
To: [email-masked]
Subject: Re: [lp-wan] ACK compression

Dear,

Best regards
Olivier

From: Olivier Gimenez
Sent: 07 May 2019 18:15
To: [email-masked]<mailto:[email-masked]>
Subject: ACK compression

Dear,

Thank you

Best regards
Olivier

To view our privacy policy, including the types of personal information we collect, process and share, and the rights and options you have in this respect, see www.semtech.com/legal<http://www.semtech.com/legal>.

---

From: Olivier Gimenez <[email-masked]>
Date: Mon, 19 Aug 2019 08:49:14 +0000

From: Pascal Thubert (pthubert) <[email-masked]>
All I can say is that in order to work, you need the last bit of the compressed form to be the same as the elided bits.
So your "While the scissors are not on an L2 Word" in step 4 will not give the appropriate result if the scissor is already on the word boundary. In that case you need to go to the next boundary.
I suggest a step 3.5 which is to move the scissors right after the first while series.

Hi,

I do not understand why it does not work; in the following SCHC ACK example the Bitmap is on 10 bits, L2 words are 8 bits
|  3   bits |   1 bit | 1 bit | 1 bit |      10 bits             |
| Rule ID |  DTag |   W   |C=0   |1 1 0 0 0 0 0 0 0 0|

Compressed SCHC ACK would be
|  3   bits |   1 bit | 1 bit | 1 bit | 2 bits |
| Rule ID |  DTag |   W   |C=0   |1 1       |

This SCHC ACK is aligned to L2 word. The scissor has been put on the word boundary and I do not understand why it does not work: the sender is able to know that last 8 tiles are missing as it knows that the 2 first are OK and it send 10 tiles.

Sorry for the mistake on examples, here is the correction with 17 tiles in the bitmap

   |---- SCHC ACK Header ----|--------      Bitmap     --------|
             |-- T --|-M-| 1 |
   +--- ... -+- ... -+---+---+---------------------------------+
   | Rule ID |  DTag | W |C=0|1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0|
   +--- ... -+- ... -+---+---+---------------------------------+
           next L2 Word boundary ->|

   |---- SCHC ACK Header ----|CpBmp|
             |-- T --|-M-| 1 |
   +--- ... -+- ... -+---+---+-----+
   | Rule ID |  DTag | W |C=0|1 1 1 1 1 1 1 1 1 1 1 |
   +--- ... -+- ... -+---+---+-----+
           next L2 Word boundary ->|

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Mon, 19 Aug 2019 09:35:08 +0000

Maybe that's me, Olivier.

Say you receive  1 0 1 0 1 0 1 0 and there are 5 elided bits. Is the original  1 0 1 0 1 0 1 0 - 1 1 1 1 1  or  1 0 1 0 1 0 1 0 - 0 0 0 0 0 ?

I inferred that the proposed algo to uncompress is (quit simply) to fill the missing bitmap with the last bits in the compressed form, which is OK if you re-added some of the removed bits in the second loop or in my step 3.5.

I guess you were smarter than that, I need to see the full decompression algorithm.

All the best,

Pascal

From: Olivier Gimenez <[email-masked]>
Sent: lundi 19 août 2019 10:49
To: Pascal Thubert (pthubert) <[email-masked]>; [email-masked]
Subject: RE: ACK compression

From: Pascal Thubert (pthubert) <[email-masked]<mailto:[email-masked]>>
All I can say is that in order to work, you need the last bit of the compressed form to be the same as the elided bits.
So your "While the scissors are not on an L2 Word" in step 4 will not give the appropriate result if the scissor is already on the word boundary. In that case you need to go to the next boundary.
I suggest a step 3.5 which is to move the scissors right after the first while series.

Hi,