ng_sixlowpan: make lookup in reassembly buffer more efficient

[OlegHahm]

As discussed in #2781 (comment) the current implementation of the lookup for fragments in the reassembly buffer is quite expensive, because up to seven comparisons have to be made for each fragment reception. This might be improved by using a bloomfilter that checks first if the fragment may be in the buffer, before the full check is performed.

[cgundogan]

Alhough, I have no idea about the code right now, but just want to give some hints:
Might a reordering of checks reduce the check count on average?

Regarding the bloom filter: There are quite some bytes involved (src_addr, dst_addr, src_len, dst_len, tag, size). We will need to compute the required bloom filter size to ensure x% guarantee. My gut tells me that this could grow quite quick in size depending on how many unique entries we want the filter to be able to hold.

[Osblouf]

Hi, I'm new to RIOT and i think that this issue would be a great way to start.
As @cgundogan pointed, maybe reordering checks will do the job but I would like to run some tests with bloom filter (like using bloom filter only for addresses). The thing is, using bloom filter will use computation power when adding a new entry in the buffer and when removed. What do you guys think ?

[OlegHahm]

Hi @Osblouf, cool to hear that you'll like to take a look into this. Implementing different solutions and comparing the timings sounds like a good plan.

[PeterKietzmann]

Hi @Osblouf! Did you already give it a try?

[PeterKietzmann]

@miri64 afaik sixlowpan has change quite a bit since ng_sixlowpan. Is this issue still valid?

[miri64]

The lookup of the reassembly buffer is still the same. The RFC says the (src_addr, dst_addr, src_len, dst_len, tag, size)-tuple SHALL be used and AFAIK for the new virtual reassembly buffer only (src_addr, src_len, tag) are used. It should make sense to reduce the selection for that and use the others only if there are discrepancies.

[stale]

This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. If you want me to ignore this issue, please mark it with the "State: don't stale" label. Thank you for your contributions.

[miri64]

The lookup of the reassembly buffer is still the same. The RFC says the (src_addr, dst_addr, src_len, dst_len, tag, size)-tuple SHALL be used and AFAIK for the new virtual reassembly buffer only (src_addr, src_len, tag) are used. It should make sense to reduce the selection for that and use the others only if there are discrepancies.

This is not true after all (see #11000)...

[miri64]

The lookup of the reassembly buffer is still the same. The RFC says the (src_addr, dst_addr, src_len, dst_len, tag, size)-tuple SHALL be used and AFAIK for the new virtual reassembly buffer only (src_addr, src_len, tag) are used. It should make sense to reduce the selection for that and use the others only if there are discrepancies.

This is not true after all (see #11000)...

And back again: #12300

[stale]

This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. If you want me to ignore this issue, please mark it with the "State: don't stale" label. Thank you for your contributions.

[stale]

This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. If you want me to ignore this issue, please mark it with the "State: don't stale" label. Thank you for your contributions.

[miri64]

We did basically that in an early version of the Virtual Ressembling End-point for our ICN ACM 2020 paper. The result was a much higher packet buffer usage, we needed to set the packet buffer to 12KiB to have good results in the first place. Given that this is because each packet snip takes up 20 bytes in the packet buffer, so an extra ~1/5 of a fragment's data, I expect a similar result for the actual reassembly buffer, so I don't think this is a viable option.