Subject: Re: [lp-wan] ACK compression

From: <[email-masked]>
Date: Tue, 20 Aug 2019 12:29:00 +0000

Hello Olivier,

Thanks for reviving this thread, and thanks for proposing a contribution.
I agree with Pascal, your algorithm needs further improvement.
For example, if I use your proposed algorithm to compress the following two bitmaps, they both result in the same compressed bitmap. How is the receiver going to decide which one was the orignal one?
Pascal's proposed step 3.5 is one way of solving this issue. However, it adds one bit to the  compressed bitmap (before padding). Maybe this is not a big deal. Another way is to create an exception in the encoding, so that is does not cost more than the current algorithm to compress out 1's, and it costs a bit more to compress out 0's.
Also, beware of the SCHC Receiver -Abort which is already an exception in the SCHC ACK encoding. Whatever you propose must be distinguishable from a SCHC Receiver-Abort, or the SCHC Receiver-Abort must be changed as well.
Best regards

Dominique

   |---- 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 ->|

   |---- SCHC ACK Header ----|--------      Bitmap     --------|

             |-- T --|-M-| 1 |

   +--- ... -+- ... -+---+---+---------------------------------+

   | Rule ID |  DTag | W |C=0|1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0|

   +--- ... -+- ... -+---+---+---------------------------------+

           next L2 Word boundary ->|

Both result in the same compressed bitmap:

   |---- SCHC ACK Header ----|CpBmp|

             |-- T --|-M-| 1 |

   +--- ... -+- ... -+---+---+-----+

   | Rule ID |  DTag | W |C=0|1 0 1|

   +--- ... -+- ... -+---+---+-----+

           next L2 Word boundary ->|

De : lp-wan <[email-masked]<mailto:[email-masked]>> on behalf of Pascal Thubert <[email-masked]<mailto:[email-masked]>>
Date : Monday 19 August 2019 11:35
À : Olivier Gimenez <[email-masked]<mailto:[email-masked]>>, "[email-masked]<mailto:[email-masked]>" <[email-masked]<mailto:[email-masked]>>
Objet : Re: [lp-wan] ACK compression

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]<mailto:[email-masked]>>
Sent: lundi 19 août 2019 10:49
To: Pascal Thubert (pthubert) <[email-masked]<mailto:[email-masked]>>; [email-masked]<mailto:[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,

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

   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 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 |
   +--- ... -+- ... -+---+---+-----+
           next L2 Word boundary ->|

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

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>.

_________________________________________________________________________________________________________________________

Ce message et ses pieces jointes peuvent contenir des informations confidentielles ou privilegiees et ne doivent donc
pas etre diffuses, exploites ou copies sans autorisation. Si vous avez recu ce message par erreur, veuillez le signaler
a l'expediteur et le detruire ainsi que les pieces jointes. Les messages electroniques etant susceptibles d'alteration,
Orange decline toute responsabilite si ce message a ete altere, deforme ou falsifie. Merci.

This message and its attachments may contain confidential or privileged information that may be protected by law;
they should not be distributed, used or copied without authorisation.
If you have received this email in error, please notify the sender and delete this message and its attachments.
As emails may be altered, Orange is not liable for messages that have been modified, changed or falsified.
Thank you.

---

From: <[email-masked]>
Date: Tue, 20 Aug 2019 12:36:00 +0000

By " and it costs a bit more to compress out 0's." , I meant " and it costs somewhat more to compress out 0's.", not literally one bit.

Dominique

De : lp-wan <[email-masked]<mailto:[email-masked]>> on behalf of Dominique Barthel <[email-masked]<mailto:[email-masked]>>
Date : Tuesday 20 August 2019 14:29
À : Olivier Gimenez <[email-masked]<mailto:[email-masked]>>, "[email-masked]<mailto:[email-masked]>" <[email-masked]<mailto:[email-masked]>>
Cc : Pascal Thubert <[email-masked]<mailto:[email-masked]>>
Objet : Re: [lp-wan] ACK compression

Hello Olivier,

Dominique

             |-- T --|-M-| 1 |

             |-- T --|-M-| 1 |

             |-- T --|-M-| 1 |

All the best,

Pascal

Hi,

---

From: Olivier Gimenez <[email-masked]>
Date: Thu, 22 Aug 2019 09:18:41 +0000

Pascal, Dominique, thank you for your comments

You are right, there is an issue with the algorithm I proposed. Please find following an updated proposition.

Also I think that my example was wrong and misleading: an uncompressed bitmap when penultimate tile is lost is not finishing by 0 but 1, and bitmap size is the number of fragments (2^N with N = FCN size). This is shown in  figure 29 of draft-ietf-lpwan-ipv6-static-context-hc-21

Olivier

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

   o  Build a temporary SCHC ACK message that contains the Header
      followed by the original Bitmap (see Section 8.2.2.3<https://tools.ietf.org/html/draft-ietf-lpwan-ipv6-static-context-hc-21#section-8.2.2.3> for a
      description of Bitmaps).

   o  Select following case regarding bitmap’s last two bits

   o  Case b’11

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

        x  While the bit on the left of the scissors is 1 and belongs to the
           Bitmap, keep moving left, then stop.  When this is done,

        x  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.

        x  At this point, cut and drop off any bits to the right of the
           scissors
   o Case b’01
        x  Position scissors at the penultimate bit (after the last 0)

        x  While the bit on the left of the scissors is 0 and belongs to the
           Bitmap, keep moving left, then stop.  When this is done,

        x  If the scissors are on an L2 word boundary of the SCHC ACK
           Bitmap, move right until next L2 word boundary. When this is done,

        x  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.

So the examples might be, for FCN size N = 4

Uncompressed bitmap 1:

   |---- SCHC ACK Header ----|--------      Bitmap     ------|

             |-- T --|-M-| 1 |   2^N                         |

   +--- ... -+- ... -+---+---+-------------------------------+

   | Rule ID |  DTag | W |C=0|1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1|

   +--- ... -+- ... -+---+---+-------------------------------+

compressed bitmap 1:

   |---- SCHC ACK Header ----|-----   Bitmap    ----|

             |-- T --|-M-| 1 |

   +--- ... -+- ... -+---+---+----------------------+

   | Rule ID |  DTag | W |C=0|1 0 1 0 0 0 0 0 0 0 0 |

   +--- ... -+- ... -+---+---+----------------------+

Uncompressed bitmap 2:

   |---- SCHC ACK Header ----|--------      Bitmap     ------|

             |-- T --|-M-| 1 |   2^N                         |

   +--- ... -+- ... -+---+---+-------------------------------+

   | Rule ID |  DTag | W |C=0|1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1|

   +--- ... -+- ... -+---+---+-------------------------------+

compressed bitmap 2:

   |---- SCHC ACK Header ----|Bitmap|

             |-- T --|-M-| 1 |

   +--- ... -+- ... -+---+---+------+

   | Rule ID |  DTag | W |C=0|1 0 0 |

   +--- ... -+- ... -+---+---+------+

           next L2 Word boundary -> |

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.