Re: [lp-wan] Supporting "bitmap" and "list" ACK types

[Carles Gomez Montenegro <[e-mail]>]

Hi Carsten,

(Yes, this is a response to the message you sent below ~4.5 years ago! :))

Well, we finally have some more complete answers regarding the overhead of
several receiver feedback techniques to report lost/received fragments.

(Not aiming to create any scares, as in fact we -the WG- already knew some
of this. Also, in this study, we assume that a single ACK provides
feedback on the delivery success or failure of the whole set of fragments
that carry a packet. Results thus apply mostly for large window sizes,
similar to the "packet mode" that we considered long ago for
fragmentation.)

Quick summary of conclusions:
Compressed bitmap tends to offer the best performance for small packets
and high error rates. As packet size increases, regardless of the L2 MTU,
List of Deltas (LoD) variants tend to become optimal. Regarding the
latter, for  uniform errors, 3-bit and 4-bit "bases" for the delta
encodings offer the  best trade-off. For burst errors, a 2-bit LoD "base"
offers the best performance, as it minimizes the encoding overhead for the
very frequent delta of "1". Finally, for high quality links with very low
error rate, and uniformly distributed errors, List of Lost Fragments
provides the most efficient encoding.

If anyone is curious, more details can be found here:
https://ieeexplore.ieee.org/document/9540899

Or here (public postprint version):
https://www.researchgate.net/publication/354712382_Evaluation_of_Receiver-Feedback_Techniques_for_Fragmentation_over_LPWANs.

Cheers,

Carles (on behalf of Sergio, Rafael and myself)



> Use delta coding, with 0 as end of list (so no length is needed).
> Code each delta as a base-8 SDNV (RFC 6256 defines base-128 SDNVs), put
> into nibbles.
> Optionally, spend a number of the SDNV code points for run lengths and/or
> embedded bitmaps.
> (Use figure 3 of RFC 2687 as an inspiration, if needed.)
>
> This NACK format can easily be designed so it is much smaller than either
> bitmaps or byte-wise sequence numbers for all realistic cases and
> insignificantly larger than a bitmap for the most pathological case; no
> need to waste rule space.
>
> Grüße, Carsten
>
>> On May 17, 2017, at 10:25, Carles Gomez Montenegro
>> <[e-mail]> wrote:
>>
>> Hi everyone,
>>
>> In the last interim WG meeting, the problem of a large bitmap was
>> discussed.
>>
>> One proposal was considering that if the number of fragment losses (for
>> a
>> given fragmented IPv6 packet) is low, sending the list of the absolute
>> numbers of lost fragments might be a more lightweight approach than
>> sending the whole bitmap (see Example 1 below). In other situations, the
>> bitmap will be more efficient (Example 2).
>>
>> Therefore, it would be good for a receiver to support both types of
>> feedback, and use the most efficient one for each specific situation.
>> Whether a bitmap or a list (of lost fragments) is used would be
>> indicated
>> in the Rule ID for the ACK.
>>
>> Any objections to / comments on this?
>>
>> Cheers,
>>
>> Carles
>>
>>
>> -----------------------
>>
>> Example 1
>> *********
>>
>> - Number of fragments carrying the IPv6 packet: 90
>> - Number of lost fragments: 1 (out of 90)
>> - Size of each absolute fragment number: 8 bits
>>
>> The sizes for the "bitmap" and "list" would be:
>>
>> - Bitmap size: 12 bytes
>> - List size: 1 byte (Note: an additional byte could be used to indicate
>> the
>>  total number of fragments received as additional information just in
>> case
>>  the MIC fails)
>>
>>
>> Example 2
>> *********
>>
>> - Number of fragments carrying the IPv6 packet: 6
>> - Number of lost fragments: 4 (out of 6)
>> - Size of each absolute fragment number: 8 bits
>>
>> - Bitmap size: 1 byte
>> - List size: 4 bytes (possibly, plus a further "number of frags" byte)