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

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

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)

---

From: Ana Minaburo <[email-masked]>
Date: Wed, 17 May 2017 17:47:15 +0200

Hello Carles, 

The support for both types of feedback needs to be mandatory, and I agree about using the Rule ID to identify whether I’m sending a bitmap or the list of absolute numbers.

But the decision about which is  better is more difficult to take, I think it does not depend on the rate lost/total number of fragments but on the number of bytes I need to represent all this information vs the ACK size.

One possibility to define the use of both types of feedback could be: When the number of lost packet is less than the max size of the ACK - 1 bytes (for Rule ID + Total fragments) the list may be used, and when there are more packets than the ACK size - 1 byte the bitmap may be used. At least we have a clear decision where to use each choice.

Ana

> On 17 May 2017, at 10:25, Carles Gomez Montenegro <[email-masked]> wrote:
> 
> Hi everyone,
> 
> _______________________________________________
> lp-wan mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/lp-wan

---

From: "Carles Gomez Montenegro" <[email-masked]>
Date: Thu, 18 May 2017 08:36:22 +0200

Hi Ana,

Thanks for your comments!

Please see some inline responses below:

> The support for both types of feedback needs to be mandatory, and I agree
> about using the Rule ID to identify whether I’m sending a bitmap or the
> list of absolute numbers.

OK!

> But the decision about which is  better is more difficult to take, I think
> it does not depend on the rate lost/total number of fragments but on the
> number of bytes I need to represent all this information vs the ACK size.

Yes, it does not depend on the percentage of lost fragments, but on i) how
many lost fragments there have been for an IPv6 packet, and also on ii)
the total number of fragments (since the most efficient type of ACK can be
chosen based on these two parameters).

One detail here (mentioned in your previous email) is that in some cases
(i.e. technologies and the direction in terms of uplink/downlink), a 7-bit
field would suffice to encode the absolute fragment number for the "list",
assuming we intend to support a maximum IPv6 packet size of 1280 bytes. In
other cases, an 8-bit field would be needed.

> One possibility to define the use of both types of feedback could be: When
> the number of lost packet is less than the max size of the ACK - 1 bytes
> (for Rule ID + Total fragments) the list may be used, and when there are
> more packets than the ACK size - 1 byte the bitmap may be used. At least
> we have a clear decision where to use each choice.

That is one option, although in some cases it would not lead to using the
shortest possible ACK (see e.g. Example 2 below).

I think a receiver can have freedom to create the most convenient type of
ACK for each received fragmented IPv6 packet, based on the total number of
fragments and on the amount of lost fragments for that packet...

Cheers,

Carles

---

From: Carsten Bormann <[email-masked]>
Date: Thu, 18 May 2017 11:43:02 +0200

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 <[email-masked]> wrote:
> 
> Hi everyone,
>